Summary-MLT-1

Veröffentlicht am

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

约定的符号与定义

样例集: $$D=\{(x_1,y_1), (x_2,y_2), …, (x_m,y_m)\}, x_i\in\cal X, y_i\in \cal Y=\{-1,+1\}.$$
并假设X中的所有的样本都来源与一个隐含未知的分布$\cal D$, D中的所有样本都是独立地从这个分布上采样得到, 即独立同分布(i.i.d.)样本.

概念(concept)与概念类: 用c表示, 是从样本空间$\cal X$到标记空间$\cal Y$的映射, 若对任何样例(x,y)都有c(x)=y, 则称c为目标概念; 所有我们希望学得的目标概念所构成的集合称为”概念类”, 用$\cal C$表示.

假设(hypothesis)与假设空间: 给定学习算法$\cal L$, 它所考虑的所有概念的集合称为假设空间, 用$\cal H$表示, 且某一个假设$h\in\cal H$. 显然h也是$\cal X$到$\cal Y$的映射.

泛化误差: $$E(h; \cal D)=P_{x\sim D}(h(x)\neq y)$$
经验误差: $$\hat E(h; D)=\frac{1}{m}\sum_{i=1}^m\mathbb{I}(h(x_i)\neq y_i).$$ 并定义假设空间中泛化误差最小的假设$h^*\in\cal H$.

PAC

PAC辨识(PAC Identify): 对$0<\epsilon, \delta<1$, 所有$c\in\cal C$和分布$\cal D$, 若存在学习算法$\cal L$, 其输出假设$h\in\cal H$满足: $$P(E(h)\leq\epsilon)\geq1-\delta$$, 则称学习算法$\cal L$能从假设空间$\cal H$中辨识概念类$\cal C$.

PAC可学习(PAC Learnable): 存在学习算法$\cal L$和多项式函数poly(.,.,.), 使得对于任何$m\geq poly(1/\epsilon, 1/\delta, size(x), size(c))$, $\cal L$能从$\cal H$中PAC辨识概念类$\cal C$, 则称概念类$\cal C$对于假设空间$\cal H$而言是PAC可学习的. 同理, 若考虑算法运行时间, 也可以定义PAC学习算法.

不可知PAC可学习(agnostic PAC learnable): 对$0<\epsilon, \delta<1$, 所有$c\in\cal C$和分布$\cal D$, 若存在学习算法$\cal L$, 其输出假设$h\in\cal H$满足: $$P(E(h)-E(h^*)\leq\epsilon)\geq1-\delta$$, 则称假设空间$\cal H$是不可知PAC可学习的.

注: 这里我们关注的主要是不可知PAC可学习, 不可知PAC可学习关注的是泛化误差界, 而只要学习算法满足经验误差最小化原则(ERM), 即返回的假设的经验误差不会比最优假设的经验误差小, 再通过集中不等式(hoffeding inequality)将经验误差与泛化误差的界bound住, 就可以得到泛化误差界. 因此我们主要关注经验误差与泛化误差的上界$\hat E(h)-E(h)$. 对于单个假设h, 这个上界可以由m控制住, 但是由于union bound, 我们是从假设空间选择一个假设, 因此要考虑整个假设空间, 即假设空间复杂度.

复杂度

VC维: 与数据分布无关, 根据增长函数, 对分, 打散等定义可描述为: 存在大小为d的示例集D能被$\cal H$打散, 任意大小为d+1的示例集D不能被$\cal H$打散, 也就是增长函数$\prod_{\cal H}(m)$在m>d后开始以多项式增长而不是以指数增长. 根据sauer定理, 可以采用关于d的式子控制住增长函数, 因此可以用来衡量假设空间复杂度.

Rademacher复杂度: 一定程度上考虑了数据分布以获得更紧的上界. 函数空间$\cal F$关于$\cal Z$的经验Rademacher复杂度定义为: $$\hat R_Z(\cal F)=\mathbb E_\sigma[\sup_{f\in\cal F}\frac{1}{m}\sum_{i=1}^m\sigma_if(z_i)]$$, 其中$\sigma_i$为取值{-1,+1}的服从均匀分布的随机变量, 上式值越接近1则假设空间表达能力越强. 在此基础上定义Rademacher复杂度: $$R_m(\cal F)=\mathbb E_{Z\subset\cal Z:|Z|=m}[\hat R_Z(\cal F)]$$

泛化性

即经验误差与泛化误差之间的关系, 如前面所述, 这是我们主要的目标. 从VC维和Rademacher复杂度的角度分别看. 从VC维看, 分有限假设空间和无限假设空间:

  • 有限假设空间(可分情况): $Pr(h\in\cal H: E(h)>\epsilon\wedge\hat E(h)=0)<\delta\rightarrow\epsilon=O(\frac{\ln|\cal H|+\ln1/\delta}{m})$; 不可分情况: $Pr(|\hat E(h)-E(h)|\leq\sqrt{\frac{\ln|\cal H|+\ln2/\delta}{2m}})\geq1-\delta$.
  • 无限假设空间(有限VC维): $Pr(E(h)-\hat E(h)\leq\sqrt{\frac{8d\ln\frac{2em}{d}+8\ln4/\delta}{m}})\geq1-\delta$, 可以看到, VC维越大, 假设空间越复杂, 泛化误差收敛率也越慢. 由此也可以得到结论: 任何VC维有限的假设空间$\cal H$都是(不可知)PAC可学习的.
    从Rademacher复杂度看, 对任意$h\in\cal H$, 下式以$1-\delta$成立:
    $$E(h)\leq\hat E(h)+R_m(\cal H)+\sqrt{\frac{\ln(1/\delta)}{2m}}\\ E(h)\leq\hat E(h)+R_D(\cal H)+3\sqrt{\frac{\ln(2/\delta)}{2m}}$$
    e.g. 通过引入间隔理论, 可以推导出SVM的Rademacher泛化误差界, 并且不依赖与VC维d: $$E(h)\leq\hat E_\rho(h)+2\sqrt{\frac{r^2\Lambda^2}{m\rho^2}}+\sqrt{\frac{\ln(1/\delta)}{2m}}$$, 其中$r, \Lambda, \rho$分别表示数据的”半径”, 权重w的”半径”, 想要获得的间隔大小.
    注: 这里基于假设空间$\cal H$复杂度的不同衡量标准(VC维, Rademacher复杂度)均与具体的学习算法无关, 对所有的学习算法都适用.

稳定性

为了给出更好的泛化界, 基于算法的分析的确可以给出更好的理论结果, 但这样的理论结果可能无法推广到作用于同一个假设空间的其他算法, 而我们可以将学习算法的一些一般性质与算法特性集合起来得到更好的理论结果, 即稳定性分析.

移除样例的稳定性: 若学习算法$\cal L$满足:$$|l (\cal L_D,z)-l (\cal L_{D^{\verb||i}},z)|\leq\beta,i=1,…,m$$, 则称$\cal L$关于损失函数$l$满足移除样例的$\beta$-均匀稳定性.

替换样例的稳定性: 若学习算法$\cal L$满足:$$|l (\cal L_D,z)-l (\cal L_{D^{i}},z)|\leq\gamma,i=1,…,m$$, 则称$\cal L$关于损失函数$l$满足替换样例的$\gamma$-均匀稳定性.
移除样例的稳定性包含替换样例的稳定性: $\gamma\leq2\beta$. 因此主要讨论替换样例稳定性.

基于稳定性的泛化误差:
$$l (\cal L, D)\leq\hat l (\cal L, D)+\gamma+(2m\gamma+M)\sqrt{\frac{\log(1/\delta)}{2m}}\\ l (\cal L, D)\leq l_{loo} (\cal L, D)+\beta+(4m\beta+M)\sqrt{\frac{\log(1/\delta)}{2m}}$$, 其中M为损失函数上界.

基于核正则化的算法稳定性: 定义$F_D$如下:
$$F_D(h)=\hat l_D(h)+\lambda||h||_K^2$$, 并定义$\sigma$-可容许性: 对于任何两个假设$h,h^{‘}\in\cal H$, 有:
$$|l(h^{‘}(x),y)-l(h(x),y)|\leq\sigma|h^{‘}(x)-h(x)|$$, 则称损失函数$l$对于假设空间$\cal H$是$\sigma$-可容许的. 实际上, 若损失函数$l$是$\rho$-lipschitz连续的, 那么$\sigma=\rho$. 并且, 根据$\sigma$可以得到$\gamma$上界: $$\gamma\leq\frac{\sigma^2r^2}{m\lambda}$$, 其中对于所有$x\in\cal X, K(x,x)\leq r^2$. 因此, 对于某个算法, 只要分析其损失函数得到$\sigma$, 就可以得到$\gamma$上界, 进而利用前述式子得到泛化误差界.

注意: 基于核正则化的算法泛化误差界都具有形式: $l(\cal L,D)-\hat l(\cal L,D)\leq O(\frac{1}{\lambda\sqrt m})$, 因此, 仅当$\lambda\gg1/\sqrt m$时, 上面得到的泛化误差界才有意义.

正则化参数$\lambda$是样本大小m的函数: 对于较大的m, 希望正则化参数较小, 以减小正则化的作用. $\lambda$的大小影响着线性假设空间的范数大小, 较大的$\lambda$会导致较小的假设空间范数. 在这种意义下, $\lambda$也可以看作假设空间复杂程度的一种度量, 而$\lambda$需要满足的条件也可以解释为: 复杂度更小的假设空间具有更好的泛化性保障.

由前述可得定理: 若学习算法$\cal L$时ERM且稳定的, 则假设空间$\cal H$是PAC可学习的. 事实上, 稳定性与假设空间并非无关, 由稳定性定义可知两者通过损失函数$l$联系起来.