对于一个机器学习任务,通常需要考虑它是不是可学的 (learnable)
PAC学习给出了一个抽象的刻画机器学习能力的框架,基于这个框架,有很多重要问题可以探讨,例如: 某任务在什么样的条件下可学得较好的模型? 某算法在什么条件下可以进行有效的学习? 需要多少训练样本才能获得较好的模型?
基本概念
给定样本集 D={(x1,y1),(x2,y2),...(xm,ym)}D=\{ (\pmb{x_1}, y_1), (\pmb{x_2}, y_2), ...(\pmb{x_m}, y_m)\}D={(x1x1x1,y1),(x2x2x2,y2),...(xmxmxm,ym)}, yi∈{−1,+1}=Yy_i \in \{-1, +1\} = \mathcal{Y}yi∈{−1,+1}=Y, xi∈Xx_i \in \mathcal{X}xi∈X,DDD中所有的样本都是独立同分布从D\mathcal{D}D采样而得。
令hhh为从X\mathcal{X}X到Y\mathcal{Y}Y的一个映射, 其泛化误差(generalization error)为:
E(h;D)=P(x,y)∼D(h(x)≠y)=E(x,y)∼D[I[h(x)≠y]]E(h; \mathcal{D}) = P_{(x, y) \sim \mathcal{D}}(h(x) \neq y) = E_{(x,y) \sim \mathcal{D}}[I[h(x) \neq y]]E(h;D)=P(x,y)∼D(h(x)=y)=E(x,y)∼D[I[h(x)=y]]
hhh在DDD上的经验误差(empirical error)为:
E^(h;D)=1m∑1mI(h(xi)≠yi)\hat{E}(h;D)=\frac{1}{m}\sum_1^mI(h(x_i)\neq y_i)E^(h;D)=m11∑mI(h(xi)=yi)
由于DDD是D\mathcal{D}D的独立同分布采样,所以hhh经验误差的期望等于泛化误差。令ϵ\epsilonϵ为E(h)E(h)E(h)的上限,即E(h)≤ϵE(h) \leq \epsilonE(h)≤ϵ。 通常用ϵ\epsilonϵ表示模型应满足的误差要求,称为误差参数.
令ccc表示概念, 它是从样本空间 X\mathcal{X}X 到标记空间 Y\mathcal{Y}Y的映射。若任何样本(x,y)(x, y)(x,y), 有c(x)=yc(x)=yc(x)=y, 则称ccc为目标概念。所有目标概念所组成的集合称为 概念类C\mathcal{C}C
给定学习算法 L\mathcal{L}L,它考虑所有可能的假设空间H\mathcal{H}H. 假设空间是对于学习算法最大能力的整体刻画。假设空间给定了算法所有可能的映射函数。若目标概念c∈Hc \in \mathcal{H}c∈H, 则H\mathcal{H}H存在假设能将所有样本正确分开,称该学习问题对假设空间是可分的 (separable); 若c∉Hc \notin \mathcal{H}c∈/H, 则称假设空间不存在任何假设能将所有样本完全正确分开,称该学习问题对假设空间是不可分的 (non-separable)
PAC learning
PAC learning(Probably Approximately Correct)是关于机器学习可学性的完整的理论。解释一下这个名字的由来:
Appromately Correct (近似正确), 指的是学出的模型误差比较小, 因为实现零误差 (Absolutely Correct)是很困难且通常是没有必要的,所以考虑的是 Approximately Correct其次,由于数据随机性的存在,也只能从概率上保证Approximately Correct的可能性是很大的 (存在一个概率的下界)
PAC Identify (PAC 辨识): 对于ϵ>0,δ<1\epsilon > 0, \delta<1ϵ>0,δ<1, 所有c∈Cc\in \mathcal{C}c∈C和分布D\mathcal{D}D, 若存在学习算法L\mathcal{L}L, 其输出假设h∈Hh\in \mathcal{H}h∈H满足:
P(E(h)≤ϵ)≥1−δP(E(h) \leq \epsilon) \geq 1-\deltaP(E(h)≤ϵ)≥1−δ
则称学习算法L\mathcal{L}L能从假设空间中PAC辨识概念类C\mathcal{C}C
PAC learnable (PAC 可学): 令mmm表示从分布D\mathcal{D}D独立同分布采样得到样本的数,ϵ>0,δ<1\epsilon > 0, \delta<1ϵ>0,δ<1, 对所有分布D\mathcal{D}D,若存在学习算法 L\mathcal{L}L和多项式函数poly()poly()poly(),使得对于任何m>=poly(1/ϵ,1/δ,size(x),size(c))m >= poly(1/\epsilon, 1/\delta, size(x), size(c))m>=poly(1/ϵ,1/δ,size(x),size(c)), L\mathcal{L}L能从假设空间H\mathcal{H}H中PAC identify 概念类 C\mathcal{C}C, 就称概念类C\mathcal{C}C是PAC可学的
Agnostic PAC Learnable (不可知PAC可学):令mmm表示从分布D\mathcal{D}D独立同分布采样得到样本的数,ϵ>0,δ<1\epsilon > 0, \delta<1ϵ>0,δ<1, 对所有分布D\mathcal{D}D,若存在学习算法 L\mathcal{L}L和多项式函数poly()poly()poly(),使得对于任何m>=poly(1/ϵ,1/δ,size(x),size(c))m >= poly(1/\epsilon, 1/\delta, size(x), size(c))m>=poly(1/ϵ,1/δ,size(x),size(c)), L\mathcal{L}L能从假设空间中输出满足如下的假设hhh:
P(E(h)−minh′∈HE(h′)≤ϵ)>=1−δP(E(h) - \underset{h'\in\mathcal{H}}{min} E(h') \leq \epsilon) >= 1 - \deltaP(E(h)−h′∈HminE(h′)≤ϵ)>=1−δ
PAC Learning Algorithm(PAC学习算法): 若学习算法L\mathcal{L}L使概念类C\mathcal{C}C为PAC可学, 且L\mathcal{L}L的时间复杂度也是多项式函数poly(1/ϵ,1/δ,size(x),size(c))poly(1/\epsilon, 1/\delta, size(x), size(c))poly(1/ϵ,1/δ,size(x),size(c)), 则称概念类CCC是高效PAC可学的,L\mathcal{L}L称概念类CCC的PAC学习算法
(Sample Complexity)样本复杂度: 满足PAC学习算法L\mathcal{L}L所需的最小样本数量m>=poly(1/ϵ,1/δ,size(x),size(c))m >= poly(1/\epsilon, 1/\delta, size(x), size(c))m>=poly(1/ϵ,1/δ,size(x),size(c)), L\mathcal{L}L称为学习算法L\mathcal{L}L的样本复杂度
对于较为困难的学习问题,目标概念ccc往往不存在于假设空间H\mathcal{H}H中,也就是对于任何h∈H,E^(h)≠0h \in \mathcal{H}, \hat{E}(h) \neq 0h∈H,E^(h)=0, 也就是H\mathcal{H}H任意一个假设都会在训练集出现或多或少的错误。
先给出Hoeffding不等式: 给定mmm个取值为[0,1][0,1][0,1]的独立的随机变量x1,x2,...,xmx_1, x_2,...,x_mx1,x2,...,xm, 对任意ϵ>0\epsilon>0ϵ>0, 有如下等式成立:
P(∣1m∑i=1mxi−1m∑i=1mE(xi)∣≥ϵ)≤exp(−2mϵ2))P(|\frac{1}{m}\sum_{i=1}^mx_i-\frac{1}{m}\sum_{i=1}^mE(x_i)| \geq \epsilon ) \leq exp(-2m \epsilon^2))P(∣m1i=1∑mxi−m1i=1∑mE(xi)∣≥ϵ)≤exp(−2mϵ2))
根据Hoeffding不等式,有如下引理:若训练集DDD中包含mmm个从分布D\mathcal{D}D上独立同分布采样而得到的样本,0<ϵ<10< \epsilon <10<ϵ<1, 则对于任意 h∈Hh \in \mathcal{H}h∈H 有:
P(E^(h)−E(h)≥ϵ)≤exp(−2mϵ2)P(\hat{E}(h) - E(h) \geq \epsilon) \leq exp(-2m \epsilon^2)P(E^(h)−E(h)≥ϵ)≤exp(−2mϵ2)P(E(h)−E^(h)≥ϵ)≤exp(−2mϵ2)P(E(h) - \hat{E}(h) \geq \epsilon) \leq exp(-2m \epsilon^2)P(E(h)−E^(h)≥ϵ)≤exp(−2mϵ2)P(∣E^(h)−E(h)∣≥ϵ)≤2exp(−2mϵ2)P(|\hat{E}(h) - E(h)| \geq \epsilon) \leq 2exp(-2m \epsilon^2)P(∣E^(h)−E(h)∣≥ϵ)≤2exp(−2mϵ2)
同样的,可以证明:若训练集DDD中包含mmm个从分布D\mathcal{D}D上独立同分布采样而得到的样本,则对于任意 h∈Hh \in \mathcal{H}h∈H , 下式至少以 1−δ1- \delta1−δ 成立. (只需要令δ=2exp(−2mϵ2)\delta = 2exp(-2m\epsilon^2)δ=2exp(−2mϵ2)即可证明)
E^(h)−12mln2δ<E(h)<E^(h)+12mln2δ\hat{E}(h) - \sqrt{\frac{1}{2m}ln\frac{2}{\delta}} < E(h) < \hat{E}(h) + \sqrt{\frac{1}{2m}ln\frac{2}{\delta}}E^(h)−2m1lnδ2<E(h)<E^(h)+2m1lnδ2
该引理表面,当样本数目mmm较大时, hhh的经验误差可以看成其泛化误差很好的近似
需要指出的是, PAC是一种分布无关的理论模型,因为它对分布D\mathcal{D}D没有任何假设,D\mathcal{D}D可以是任何分布,但是训练集和测试集必须来自同一个分布。另外PAC考虑的是针对某个概念类 C\mathcal{C}C而不是特定概念的可学性,目标概念 c∈Cc \in Cc∈C对于学习算法是未知的。
PAC学习中一个关键因素是假设空间H\mathcal{H}H的复杂度。H\mathcal{H}H越大,包含目标概念的可能性越大,但找到某个具体目标概念的难度也越大。 H\mathcal{H}H有限时,称H\mathcal{H}H为有限假设空间;否则为无限假设空间。有限假设空间可以用概念个数来衡量其复杂度;无限假设空间的复杂度需要一些特别的技术 (VC维)。
PAC可学考虑的是学习算法L\mathcal{L}L输出假设的泛化误差与最优假设泛化误差之间的差别,由于其真实分布未知,通常无法计算。不过由于经验误差和泛化误差有密切联系,可以借助经验误差进行比较。
泛化界
对于一个学习算法来说,判断其性能好坏的依据是泛化误差,即学习算法在未知数据上的预测能力。对于假设空间H\mathcal{H}H, 可以分为有限假设空和无限假设空间,根据目标概念c\mathcal{c}c是否在H\mathcal{H}H中可以分为可分情形和不可分情形
我们来分别讨论一下。
泛化误差上界
有限假设空间
可分情形
对于可分的有限假设空间H\mathcal{H}H, 目标概念c∈Hc \in \mathcal{H}c∈H, 任何在训练集上犯错的假设都不是要找的目标概念,因此可以提出这些在训练集上出错的假设,留下与训练集一致的假设。如果训练集足够大,最终剩下的假设一定会很少,从而能以较大的概率找到目标概念的近似。实际中训练集往往是有限的,所有会剩下不止一个与训练集一致的假设。在PAC学习理论中,只要训练集DDD的大小能使学习算法L\mathcal{L}L至少以1−δ1 - \delta1−δ的概率找到目标近似即可。当H\mathcal{H}H为可分的有限假设空间时,有下面的不等式成立
令H\mathcal{H}H为可分的有限假设空间,DDD为从D\mathcal{D}D独立同分布采样得到的大小为mmm的训练集,学习算法L\mathcal{L}L基于训练集DDD输出与训练集一致的假设h∈Hh \in \mathcal{H}h∈H, 对于 ϵ>0,δ<1\epsilon > 0, \delta < 1ϵ>0,δ<1, 若m≥1ϵ(ln∣H∣+ln1δ)m \geq \frac{1}{\epsilon}(ln|\mathcal{H}| + ln\frac{1}{\delta})m≥ϵ1(ln∣H∣+lnδ1), 有 P(E(h)≤ϵ)≥1−δP(E(h) \leq \epsilon) \geq 1 - \deltaP(E(h)≤ϵ)≥1−δ 这表明H\mathcal{H}H为可分的有限假设空间时,学习算法输出的泛化误差依赖于假设空间的大小∣H∣|\mathcal{H}|∣H∣和训练集的大小mmm。 随着训练集的样本数目逐渐增加,泛化误差的上界逐渐趋近于0, 收敛率为 O(1m)O(\frac{1}{m})O(m1)
不可分情形
不可分情形中,目标概念不在假设空间中,即假设空间中的每个假设都会或多或少的出现分类错误,我们的目标则是希望找到假设空间中泛化误差最小假设的ϵ\epsilonϵ近似。对于学习算法的输出假设hhh来说,泛化误差是在未见数据上的预测能力,但是在训练集上的经验误差是直接可以观察到的。当训练集中样本数目较大时,hhh的经验误差时泛化误差的较好近似。
令H\mathcal{H}H为可分的有限假设空间,DDD为从D\mathcal{D}D独立同分布采样得到的大小为mmm的训练集,h∈Hh \in \mathcal{H}h∈H, 对于 ϵ>0,0<δ<1\epsilon > 0, 0<\delta < 1ϵ>0,0<δ<1, 有 P(∣E(h)−E^(h)∣≤ln∣H∣+ln(2/δ)2m)≥1−δP(|E(h) - \hat{E}(h)| \leq \sqrt{\frac{ln|\mathcal{H}| + ln(2/\delta)}{2m}}) \geq 1 - \deltaP(∣E(h)−E^(h)∣≤2mln∣H∣+ln(2/δ))≥1−δ 这表明H\mathcal{H}H为不可分的有限假设空间时,学习算法输出的泛化误差依赖于假设空间的大小∣H∣|\mathcal{H}|∣H∣和训练集的大小mmm。 随着训练集的样本数目逐渐增加,收敛率为 O(1m)O(\frac{1}{\sqrt m})O(m1)
无限假设空间
对于无限假设空间,需要从VC维和Rademacher复杂度的角度来分析泛化误差界
有限VC维假设空间的泛化误差
对于有限VC维的假设空间,泛化误差的收敛率与VC维的大小有关,VC维越大,假设空间越复杂,泛化误差收敛率越慢.
基于Rademacher复杂度的泛化误差界
泛化误差下界
可分情形
不可分情形