计算学习理论

第12章 计算学习理论

  • Page267: 计算学习理论(computational learning theory)

    计算学习理论研究的是关于通过“计算”来进行“学习”的理论,即关于机器学习的理论基础,其目的是分析学习任务的困难本质,为学习算法提供理论保证,并根据分析结果指导算法设计。

  • Page268: Jensen不等式

    f(E(x))E(f(x))f(\mathbb{E}(x)) \leqq \mathbb{E}(f(x))

    期望的函数小于函数的期望

  • Page268: Hoeffding不等式

    x1,x2,...,xmx_1,x_2,...,x_mmm个独立随机变量,且满足0xi10\leqq x_i\leqq 1,则对于任意ϵ0\epsilon\geqq 0有: P(1mi=1mxi1mi=1mE(xi)ϵ)exp(2mϵ2)P(\frac{1}{m}\sum_{i=1}^{m}x_i-\frac{1}{m}\sum_{i=1}^m\mathbb{E}(x_i)\geqq \epsilon)\leqq exp(-2m\epsilon^2) P(1mi=1mxi1mi=1mE(xi)ϵ)2exp(2mϵ2)P(\mid \frac{1}{m}\sum_{i=1}^{m}x_i-\frac{1}{m}\sum_{i=1}^m\mathbb{E}(x_i)\mid \geqq \epsilon)\leqq 2exp(-2m\epsilon^2)

  • Page268: McDiarmid 不等式

    x1,x2,...,xmx_1,x_2,...,x_mmm个独立随机变量,且对任意1im1\leqq i\leqq m,函数ff满足

    x1,x2,...,xm,xif(x1,...,xm)f(x1,...,xi1,xi,xi+1,...,xm)ci\sum_{x_1,x_2,...,x_m, x^{'}_i } |f(x_1,...,x_m) - f(x_1, ... , x_{i-1}, x^{'}_i, x_{i+1}, ..., x_m)| \leqq c_i

    则对任意ϵ0\epsilon\geqq 0,有 P(f(x1,...,xm)E(f(x1,...,xm))ϵ)exp(2ϵ2ici2)P(f(x_1,...,x_m)-E(f(x_1,...,x_m))\geqq \epsilon)\leqq exp(\frac{-2\epsilon^2}{\sum_i c_i^2}) P(f(x1,...,xm)E(f(x1,...,xm))ϵ)exp(2ϵ2ici2)P(\mid f(x_1,...,x_m)-E(f(x_1,...,x_m))\mid \geqq \epsilon)\leqq exp(\frac{-2\epsilon^2}{\sum_i c_i^2})

  • Page268: 概率近似正确

  • Page268: 概念类(concept class)

    令c表示概念,这是从样本空间X\mathcal{X}到标记空间Y\mathcal{Y}的映射,它决定示例x的真实标记y,若对任何样例(x,y)有c(x)=y成立,则称c为目标概念,所有我们希望学得的目标概念所构成的集合称为概念类,用符号C\mathcal{C}表示。

  • Page268: 假设空间(hypothesis space)

给定学习算法L\mathfrak{L},它所考虑的所有可能概念的集合称为“假设空间”,用符号H\mathcal{H}表示。由于学习算法事先并不知道概念类的真实存在,因此假设空间和概念类往往不同。

  • Page269: PAC辨识(PAC Identify)

    对于0<ϵ,δ<10<\epsilon, \delta<1,所有cCc\in\mathcal{C}和分布D\mathcal{D},若存在学习算法L\mathfrak{L},其输出假设hHh\in\mathcal{H}满足

    P(E(h)ϵ)1δP(E(h)\leqq \epsilon)\geqq 1-\delta

    则称学习算法L\mathfrak{L}能从假设空间H\mathcal{H}中PAC辨识概念类C\mathcal{C},这样的学习算法L\mathfrak{L}能从假设空间H\mathcal{H}中PAC辨识概念类C\mathcal{C}.

  • Page269: PAC可学习(PAC Learnable)

    mm表示从分布D\mathcal{D}中独立同分布采样得到的样例数目,0<ϵ,δ<10<\epsilon,\delta<1,对所有分布D\mathcal{D},若存在学习算法L\mathfrak{L}和多项式函数poly(.,.,.,.)poly(.,.,.,.),使得对于任何mpoly(1/ϵ,1/δ,size(x),size(c))m\geqq poly(1/\epsilon,1/\delta,size(x),size(c)), L\mathfrak{L}能从假设空间H\mathcal{H}中PAC辨识概念类C\mathcal{C},则称概念类C\mathcal{C}对假设空间H\mathcal{H}而言是PAC可学习的,也简称概念类C\mathcal{C}是PAC可学习的。对于计算机算法来说,必须考虑时间复杂度,于是:

  • Page270: PAC学习算法(PAC Learning Algorithm)

    若学习算法L\mathfrak{L}使概念类C\mathcal{C}为PAC可学习的,且L\mathfrak{L}的运行时间也是多项式函数poly(1/ϵ,1/δ,size(x),size(c))poly(1/\epsilon,1/\delta,size(x),size(c)),则称概念类C\mathcal{C}是高效PAC可学习的,称L\mathfrak{L}为概念类C\mathcal{C}的PAC学习算法。

  • Page269: 时间复杂度

    假定学习算法L\mathfrak{L}处理每个样本的时间为常数,则L\mathfrak{L}的时间复杂度等价于样本复杂度。

  • Page270: 样本复杂度

    满足PAC学习算法L\mathfrak{L}所需的mpoly(1/ϵ,1/δ,size(x),size(c))m\geqq poly(1/\epsilon,1/\delta,size(x),size(c))中最小的m,称为学习算法L\mathfrak{L}的样本复杂度。

  • Page269: 不可分(272)(non-seperable)

    对于较为困难的学习问题,目标概念cc往往不存在于假设空间H\mathcal{H}中,假定对于任何hH,E(h)^0h\in\mathcal{H}, \hat{E(h)}\neq0,也就是说,H\mathcal{H}中的任意一个假设都会在训练集上出现或多或少的错误。H\mathcal{H}中不存在任何假设能将所有示例完全正确分开,则称该问题对于学习算法L\mathfrak{L}是不可分的,亦称不一致的。

  • Page269: 不一致(non-consistent)

    即不可分。

  • Page269: 可分(270)(seperable)

    可分情形意味着目标概念cc属于假设空间H\mathcal{H}, 即 cHc\in\mathcal{H}H\mathcal{H}中存在假设能将所有示例按与真实标记一致的方式完全分开,我们将该问题对学习算法L\mathfrak{L}是可分的,亦称一致的。

  • Page270: 恰PAC可学习(properly PAC learnable)

    若学习算法L\mathfrak{L}使概念类C\mathcal{C}为PAC可学习的,且L\mathfrak{L}的运行时间也是多项式函数poly(1/ϵ,1/δ,size(x),size(c))poly(1/\epsilon, 1/\delta, size(x), size(c)),则称概念类C\mathcal{C}是高效PAC可学习的,称L\mathfrak{L}为概念类C\mathcal{C}的PAC学习算法。若在PAC学习中假设空间与概念类完全相同,称为恰PAC可学习,这意味着学习算法的能力与学习任务恰好匹配。

  • Page270: 有限假设空间

    一般而言,H\mathcal{H}越大,其包含任意目标概念的可能性越大,但从中找到某个具体概念的难度也越大,H|\mathcal{H}|有限时,我们称H\mathcal{H}为有限假设空间,否则称为“无限假设空间”。

  • Page273: 不可知PAC可学习(agnostic PAC learnable)

    mm表示从分布D\mathcal{D}中独立同分布采样得到的样例数目,1<ϵ,δ<11<\epsilon, \delta < 1,对所有分布D\mathcal{D},若存在学习算法L\mathcal{L}和多项式函数poly(.,.,.,.)poly(.,.,.,.),使得对于任何mpoly(1/ϵ,1/δ,size(x),size(c))m\leqq poly(1/\epsilon, 1/\delta, size(x), size(c))L\mathfrak{L}能从假设空间H\mathcal{H}中输出满足P(E(h)minhH)ϵ1δP(E(h)-min_{h^{'} \in \mathcal{H}})\leqq\epsilon\geqq 1 - \delta的假设h,则称假设空间H\mathcal{H}是不可知PAC可学习的。

  • Page273: 增长函数

    给定假设空间H\mathcal{H}和示例集D=x1,x2,...,xmD={x_1, x_2, ..., x_m}H\mathcal{H}中每个假设h都能对DD中示例赋予标记,标记结果可表示为

    hD=h(x1),h(x2),...,h(xm)h|_D = {h(x_1), h(x_2), ... , h(x_m)}

    随着m的增大,H\mathcal{H}中所有假设对D中的示例所能赋予标记的可能结果数也会增大。

    对所有mNm\in\mathbb{N},假设空间H\mathcal{H}的增长函数

    H(m)=max{x1,...,xmH}{h(x1),h(x2),...,h(xm)hH}\prod_{\mathcal{H}}(m)= max_{\{x_1, ..., x_m\subseteq \mathcal{H}\}}|\{h(x_1), h(x_2),..., h(x_m)|h\subseteq \mathcal{H}\}|

    表示假设空间H\mathcal{H}对m个示例所能赋予标记的最大可能结果数,可能结果数越大,假设空间的表示能力越强,对学习任务的适应能力也越强,可以利用增长函数来估计经验误差与泛化误差之间的关系。

  • Page273: 对分

    假设空间H\mathcal{H}中不同的假设对于D\mathcal{D}中示例赋予标记的结果可能相同,也可能不同;尽管H\mathcal{H}可能包含无穷多个假设,但其对D\mathcal{D}中示例赋予标记的可能结果是有限的。对m个示例,最多有2m2^m个可能结果,对二分类问题来说,H\mathcal{H}中的假设对D\mathcal{D}中示例赋予标记的每种可能结果称为对D\mathcal{D}的一种对分。

  • Page273: 打散

    若假设空间H\mathcal{H}能实现示例集D\mathcal{D}上的所有对分,即H(m)=2m\prod_{\mathcal{H}}(m)=2^m,则称示例集D\mathcal{D}能被假设空间H\mathcal{H}打散。

  • Page273: VC维(274)

    假设空间的VC维是能被H\mathcal{H}打散的最大示例集的大小,即VC(H)=maxm:H(m)=2mVC(\mathcal{H})=max{m: \prod_{\mathcal{H}}(m)=2^m},可用于度量假设空间的复杂度。

  • Page278: 经验风险最小化(Empirical Risk Minimization, ERM)

    令h表示学习算法L\mathfrak{L}输出的假设,若hh满足E^(h)=minh\hat{E}(h)=min_{h'},则称L\mathfrak{L}为满足经验风险最小化原则的算法。

  • Page279: Rademacher复杂度

    经验误差最小的假设是

    argmaxhH1mi=1myih(xi)argmax_{h\in\mathcal{H}}\frac{1}{m}\sum_{i=1}^m y_i h(x_i)

    然而现实任务中的标记y有时候会收到噪声影响,不再是真实标记,再此情形下,选择假设空间H\mathcal{H}中在训练集上表现最好的假设,有时还不如选择H\mathcal{H}中事先考虑了随机噪声影响的假设。考虑随机变量σi\sigma_i,它以0.5的概率取值-1,0.5的概率取值+1,称为Rademacher随机变量,基于σi\sigma_i可将上式改写为

    suphH1mi=1mσih(xi)sup_{h\in\mathcal{H}}\frac{1}{m}\sum^m_{i=1}\sigma_i h(x_i),

    期望为

    Eσ[suphHi=1mσih(xi)]\mathbb{E}_{\sigma}[sup_{h\in\mathcal{H}}\sum_{i=1}^m \sigma_ih(x_i)]

    考虑实值函数空间 F:ZR\mathcal{F}:\mathcal{Z}\rightarrow\mathcal{R}, 令Z=z1,z2,...,zmZ={z_1,z_2,...,z_m}

    其中ziZz_i\in\mathcal{Z}, 将X\mathcal{X}H\mathcal{H}替换成ZZFF可得,函数空间Z\mathcal{Z}g关于F\mathcal{F}的经验Rademacher复杂度

    R^Z(F)=Eσ[supfF1mi=1mσif(zi)]\hat{R}_Z(\mathcal{F})=\mathbb{E}_{\sigma}[sup_{f\in\mathcal{F}}\frac{1}{m}\sum_{i=1}^m\sigma_i f(z_i)]

    其衡量了函数空间F\mathcal{F}与随机噪声在集合Z\mathcal{Z}中的相关性。对所有从D\mathcal{D}独立同分布采样而得的大小为m的集合Z求期望可得函数空间F\mathcal{F}关于上Z\mathcal{Z}分布的D\mathcal{D}Rademacher复杂度。

  • Page284: 稳定性

    算法在输入发生变化时,输出是否会随之发生较大的变化。

  • Page285: 均匀稳定性

    对任何xX,z=(x,y)x\in\mathcal{X},z=(x,y),若学习算法L\mathcal{L}满足

    l(LD,z)l(LDi,z)β|l(\mathcal{L}_D, z) - l(\mathcal{L}_{D_i},z)|\leqq\beta

    则称L\mathcal{L}关于损失函数ll满足β\beta均匀稳定性。

    其中l为泛化损失,DiD_i为移除DD中第i个样例得到的集合。