本文主要参考了Shai Shalev-Shwartz的深入理解机器学习第2-7章以及coursera上林轩田的机器学习基石课程,这部分内容较为详细的描述了机器学习的理论部分,主要包括以下三部分内容:

统计学习理论的基本定理,涉及:一致收敛性、PAC学习理论、VC维及没有免费的午餐定理.
三个可学习的概念:PAC可学习、不一致可学习及一致性(Consistency).
三种学习范式:经验风险最小化(ERM)、结构风险最小化(SRM)及最小描述长度(MDL).

最后要强调的是这块理论是针对监督学习中的二分类问题而言的,对于多分类问题,可将VC维拓展为Natarajan维.

统计学习理论的基本定理

在给出最核心的定理之前, 应当接触以下几个概念:

样本空间: 对于监督学习而言为带标签的样本\((x,y)\)的取值空间\(Z=(\mathcal{X}, \mathcal{Y})\), 学习的目标是映射\(f: \mathcal{X}\to\mathcal{Y}\), 以用于产生对新样本\(x_{new}\)的标签的可靠预测\(f(x_{new})\). p.s.对无监督学习而言为不带标签的样本\(x\)的取值空间\(\mathcal{X}\), 学习目标为对\(\mathcal{X}\)的可靠分类.
目标函数: 通常记为\(f\), 即上述监督学习中所说的映射\(f\). 对于分类问题就是我们希望得到的真实的分类函数.
训练集: 通常记为\(S\), 由定义在样本空间\(Z=(\mathcal{X}, \mathcal{Y})\)上的概率分布\(\mathcal{D}\)抽样得到 \[S=\{(x_{1},y_{1}),....,(x_{m},y_{m})\}\]
学习算法: 通常记为\(A\), 即我们构建的、能从数据中学到东西的学习算法, 期望其能从假设类中返回良好的假设.
假设类: 通常记为\(\mathcal{H}\), 对目标函数\(f\)的假设构成的空间, 学习器从中选择.
预测器(predictor): 或者说分类器(classifier)、假设(hypothesis), 通常记为\(h\), 即学习器输出的一个函数:\(h:\mathcal{X}\to\mathcal{Y}\), 且应当和目标函数\(f\)有相近的函数值.
损失函数: 通常记为\(l(h, (x, y))\), 其定义在预测器\(h\)和单个样本\((x, y)\)上. 对于二分类问题, 一个常用的损失函数为\(l(h, (x, y))=I\{y\neq h(x)\}\), 即分对了就为0, 分错了就为1.
训练误差: 通常记为\(L_{S}(h)\), 其定义为预测器\(h\)在训练集\(S\)上的平均损失\[L_{S}(h)=\frac{1}{m}\sum_{i=1}^m l(h, (x_i, y_i))\]
泛化误差: 通常记为\(L_{\mathcal{D}}(h)\), 其定义为预测器\(h\)在\((\mathcal{X}, \mathcal{Y})\)上的平均损失\[\mathbb{E}_{(x, y)\sim (\mathcal{X}, \mathcal{Y})}l(h, (x, y))\]

这里给出的概念及记号借鉴了深入理解机器学习一书中的写法. 下面的内容适合有一定基础的同学阅读, 这里给出最核心的定理:

令\(\mathcal{H}\)是一个由\(\mathcal{X}\to\{0,1\}\)的映射函数构成的假设空间, 且令损失函数为0-1损失. 那么,下述陈述等价:

\(\mathcal{H}\)有一致收敛性.

任何ERM规则都是对于\(\mathcal{H}\)成功的不可知PAC学习器.

\(\mathcal{H}\)是不可知PAC可学习的.

\(\mathcal{H}\)是PAC可学习的.

任何ERM规则都是对于\(\mathcal{H}\)成功的PAC学习器.

\(\mathcal{H}\)的VC维有限.

下面我会一一解释上述出现的名词并证明该定理, 证明分两块

1推2推3推4推6推1
1推2推5推6推1

其中6推1为难点.

一致收敛性

\(\varepsilon\)-代表性样本

\(\varepsilon\)-代表性样本(\(\varepsilon\)-representative sample):

如果满足下列不等式:\(\forall h \in\mathcal{H},|L_{S}(h)-L_{\mathcal{D}}(h)|\le\varepsilon\),训练集\(S\)就称作\(\varepsilon\)-代表性样本.

泛化误差\(L_{\mathcal{D}}(h)\)为\(h\)在概率分布\(\mathcal{D}\)上的表现, 定义为\[L_{\mathcal{D}}(h)=\mathbb{P}_{(x,y)\in \mathcal{D}}[h(x)\neq y]\]它是能反应假设\(h\)的性能的最真实的误差. 但一般情况下, 我们无法知道\(\mathcal{D}\)和\(f\)是什么样子的, 所以无法直接获知真实的误差. 一种思路是转而去关心训练误差和泛化误差界:

训练误差\(L_{S}(h)\)为\(h\)在训练样本\(S\)上的表现, 定义为\[L_{S}(h)=\frac{1}{|S|}\sum_{(x,y)\in S}I\{h(x)\neq y\}\]由于这里的\(S\)已知, 因此能够计算得到训练误差.
泛化误差界定义为\[\sup_{h\in\mathcal{H}}|L_{S}(h)-L_{\mathcal{D}}(h)|\]一般来说, 有关泛化误差界的一些结果如VC界等总是在以\(1-\delta\)概率成立的意义下, 显然这个界会与假设类\(\mathcal{H}\)的选择有关.

控制好了这两个量, 就可以认为泛化误差也被控制住了.

p.s. \(S\)是\(\varepsilon\)-代表性样本即说明哪怕\(h\)是闭着眼睛瞎选的, 它在\(\mathcal{D}\)和\(S\)上的表现都会差不多, 这说明此时训练集\(S\)是足以去代表\(\mathcal{D}\)的.

一致收敛性

一致收敛性(Uniform Convergence, UC)这一概念从学习成功所需训练集大小的角度刻画了假设类的复杂度:

称假设类\(\mathcal{H}\)具有一致收敛性, 若存在一个函数\[m^{UC}_{\mathcal{H}}:(0,1)\times (0,1)\to\mathbb{N}\] 使得对于\(\forall\varepsilon,\delta\in(0,1)\)、\(Z\)上的任一概率分布\(\mathcal{D}\)、从\(\mathcal{D}\)独立抽样得到的大小为\(m\)的训练集\(S\), 只要\(m\ge m^{UC}_{\mathcal{H}}(\varepsilon,\delta)\), 就有至少在概率\(1-\delta\)下, \(S\)是\(\varepsilon\)-代表性的.

这里的一致指的是对假设类\(\mathcal{H}\)中的假设\(h\)和\(Z\)上任意概率分布\(\mathcal{D}\)的一致性, 满足一致收敛的类也叫做Glivenko-Cantelli类.

p.s. \(\varepsilon\)-代表性可以理解为训练集足够好, 好到泛化误差界\[\sup_{h\in\mathcal{H}}|L_{S}(h)-L_{\mathcal{D}}(h)|\]能被\(\varepsilon\)控制住. 若假设类\(\mathcal{H}\)具有一致收敛性, 那么不管是什么样的要求, 只要训练集的样本数\(m\)足够大且是独立抽样得到, 那我就能在一定概率下保证泛化误差能被\(\varepsilon\)控制住. 假想这么一种情况, 假设类\(\mathcal{H}\)足够复杂, 因此对于任意的\(S\), 遍历\(h\in\mathcal{H}\)就能让\(L_{S}(h)\)遍历\([0,1]\), 继而我总能找到一个\(h\), 使得\[|L_{S}(h)-L_{\mathcal{D}}(h)|>\varepsilon\]事实上, 一致收敛性中对\(h\in\mathcal{H}\)的一致性的要求本质上要求了假设类\(\mathcal{H}\)不能过于复杂.

经验风险最小化(ERM)

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

对于学习器来说, 训练样本是真实世界的一个缩影, 一种很自然的想法就是通过最小化训练误差\(L_{S}(h)\)来寻找\(h\), 这种最小化\(L_{S}(h)\)的学习范式称为是经验风险最小化.

p.s. 按照同时控制训练误差和泛化误差界这两个量的思路, 我们只需要设计好算法来最小化训练误差, 同时恰当选择假设类以控制好泛化误差界, 就能控制住泛化误差, 即所谓的学习成功.

PAC可学习

PAC(Probably Approximately Correct)可学习的概念主要包括不可知PAC可学习(Agnostic PAC Learnability), PAC可学习(PAC Learnability)及广义损失函数下的不可知PAC可学习(Agnostic PAC Learnability for General Loss Functions)这三个概念.

不可知PAC可学习

不可知PAC可学习(Agnostic PAC Learnability):

称假设类\(\mathcal{H}\)是不可知PAC可学习的, 若存在一个函数\[m_{\mathcal{H}}:(0,1)\times(0,1)\to\mathbb{N}\]和一个学习算法\(A\), 使得对于\(\forall\varepsilon,\delta\in(0,1)\)、\(Z\)上的任一概率分布\(\mathcal{D}\)、从\(\mathcal{D}\)独立抽样得到的大小为\(m\)的训练集\(S\), 只要\(m\ge m_{\mathcal{H}}(\varepsilon, \delta)\), 算法\(A\)通过最小化训练误差\(L_{S}(h)\)将以不小于\(1-\delta\)的概率返回一个假设类\(h\), 满足\(L_{\mathcal{D}}(h)\le \min_{h'\in\mathcal{H}}L_{\mathcal{D}}(h')+\varepsilon\).

倘若此时假设类\(\mathcal{H}\)只包含贝叶斯最优分类器, 即以概率1满足\(L_{\mathcal{D}}(h)\le \min_{h'\in\mathcal{H}}L_{\mathcal{D}}(h')+\varepsilon\), 此时我只需将贝叶斯最优分类器的函数值取其对立面(将函数输出结果的01对调), 就能将概率1降为概率0.5. 从这个层面看, 不可知PAC可学习也要求了假设类不能过于复杂.

p.s. 与一致收敛性不同的是, 不可知PAC可学习通过考察假设类中的最优假设和最优秀的算法返回的假设之间的泛化误差差距来控制假设类的复杂度, 因而需要剔除训练误差优秀、泛化误差垃圾的假设; 而一致收敛性要求假设类中的一致性同样要求将训练误差优秀、泛化误差垃圾的假设剔除.

p.s.回头来看定理的第一第二条. \(\mathcal{H}\)有一致收敛性等价于任何ERM规则都是对于\(\mathcal{H}\)成功的不可知PAC学习器, 也就是说不可知PAC学习器再加上一个不错的方法(ERM规则), 就能等同于一致收敛性.

PAC可学习

PAC可学习(PAC Learnability):

称假设类\(\mathcal{H}\)是PAC可学习的, 若存在一个函数\[m_{\mathcal{H}}:(0,1)\times(0,1)\to\mathbb{N}\]和一个学习算法\(A\), 使得对于\(\forall\varepsilon,\delta\in(0,1)\)和在\(Z\)上的任一概率分布\(\mathcal{D}\), 任意的\(f:\mathcal{X}\to\{0,1\}\), 如果在\(\mathcal{H},\mathcal{D},f\)下满足可实现的假设, 那么当样本数量\(m\ge m_{\mathcal{H}}(\varepsilon,\delta)\)时, 其中的样本由分布\(\mathcal{D}\)独立同分布采样得到并由\(f\)标记, 算法将以不小于\(1-\delta\)的概率返回一个假设类\(h\), 使该假设类\(h\)满足\(L_{\mathcal{D}}(h)\le \varepsilon\).

不可知PAC可学习实际上是PAC可学习的范化, 这里假定样本的标签由\(f(x)\)给出, 这实际上假设了不出现样本相同标签不同的情况. 另外由\(L_{\mathcal{D}}(f)=0\)可知, PAC可学习还要求了假设类\(\mathcal{H}\)必然包含\(f\).

如果假设类\(\mathcal{H}\)是PAC可学习的, 有很多函数\(m_{\mathcal{H}}\)满足PAC可学习的定义给出的条件, 我们定义采样复杂度为满足条件的最小函数, 下面是有限假设类的一个例子:

任意有限假设类是PAC可学习的,其采样复杂度满足:\(m_{\mathcal{H}}(\varepsilon,\delta)\le [\frac{log(|\mathcal{H}|)/\delta}{\varepsilon}]\).

该定理用霍夫丁不等式(Hoeffding's inequality)可证, 霍夫丁不等式的证明可见链接或是深入理解机器学习一书附录B.4, 该定理的详细证明可见深入理解机器学习一书2.3节.

p.s. 霍夫丁不等式(Hoeffding's inequality):

\(\theta_{1},...,\theta_{m}\)是一个独立同分布的r.v.序列, 假设对所有的\(i\), \(E[\theta_{i}]=\mu\),且\(\mathbb{P}[a\le\theta_{i}\le b]=1\), 则对于\(\forall\varepsilon>0\) \[\mathbb{P}[|\frac{1}{m}\sum^{m}_{i=1}\theta_{i}-\mu|>\varepsilon]\le2\exp(-2m\varepsilon^{2}/(b-a)^{2})\]

广义损失函数下的不可知PAC可学习

为了能处理其他学习任务比方说多分类, 回归问题, 我们将损失函数进行如下范化: 广义损失函数:

0-1损失, 这个损失函数用在二分类或者多分类问题中. \[ l_{0-1}(h,(x,y))=0,where\{h(x)=y\};1,where \{h(x)\neq y\}\]
平方损失,这个损失函数用在回归问题中. \[l_{sq}(h,(x,y))=(h(x)-y)^{2}\]

广义损失函数下的不可知PAC可学习(Agnostic PAC Learnability for General Loss Functions):

对于集合\(Z\)和损失函数\(l:\mathcal{H}×Z\to \mathbb{R}_{+}\), 若存在一个函数\(m_{\mathcal{H}}:(0,1)^{2}\to\mathbb{N}\)和一个学习算法\(A\), 使得对于\(\forall\varepsilon,\delta\in(0,1)\)和在\(Z\)上的任一概率分布\(\mathcal{D}\), 当样本数量\(m\ge m_{\mathcal{H}}(\varepsilon,\delta)\)时, 其中的样本由分布\(\mathcal{D}\)独立同分布采样得到, 算法将以不小于\(1-\delta\)的概率返回一个假设类\(h\), 使该假设类\(h\)满足\(L_{\mathcal{D}}(h)\le \min_{h'\in\mathcal{H}}L_{\mathcal{D}}(h')+\varepsilon\).

对不可知的探讨

上文提到不可知PAC可学习是对PAC可学习的范化, 因为假设类\(\mathcal{H}\)中未必有一个完美的分类器\(h\), 而这又有两种可能的深层原因:

\(\mathcal{H}\)取得不够大, 没能包含能将西瓜完美分类的目标函数\(f\).
\(\mathcal{H}\)取得够大了, 但\(\mathcal{H}\)仍没能包含能将西瓜完美分类的目标函数\(f\), 一种合理的推测就是根本不存在能将西瓜完美分类的\(f\). 比方说因为\(\mathcal{X}\)中特征选取不是太好, 某好瓜和某坏瓜在选取的特征上的数据完全一致, 此时\(f\)当然没法把他们区分开来.

前者相对好办, 只要扩大\(\mathcal{H}\), 而后者就需要去寻找或者构造新的特征以区分好坏瓜.

VC维

由上节PAC可学习我们已经知道, 有限假设类假设类\(\mathcal{H}\)是PAC可学习的充分条件. 但是否为必要条件呢? 答案是否定的. 事实上, 无限假设类也能是PAC可学习的, 只要它的VC维有限, 下面来介绍VC维.

我们先来看一个著名的定理: 没有免费的午餐定理(No-Free-Lunch), 这个定理说明了如果不对假设类加以限制, 任何学习算法总有很差表现的时候.

没有免费的午餐定理

没有免费的午餐定理(No-Free-Lunch):

对实例空间\(\mathcal{X}\)上的0-1损失的二分任务, \(A\)表示任意的学习算法. 样本大小\(m\)为小于\(|\mathcal{X}|/2\)的任意数.则在\(\mathcal{X}×\{0,1\}\)上存在一个分布\(\mathcal{D}\), 使得:

存在一个函数\(f:\mathcal{X}\to\{0,1\}\)满足\(L_{\mathcal{D}}(f)=0\).

样本量为\(m\)的样本集\(S\), 由分布\(\mathcal{D}\)独立同分布采样得到, 以至少\(\frac{1}{7}\)的概率满足:\(L_{\mathcal{D}}(A(S))\ge \frac{1}{8}\).

这个定理陈述的是对每个学习器\(A\), 都存在一个学习任务(分布\(\mathcal{D}\))使其失败, 即使这个任务存能被另一个学习器成功学习(比方说关于假设类\(\mathcal{H}=\{f\}\)的一个ERM学习器).

下面是没有免费的午餐定理的证明: 一个直观的看法如下, 令\(C\)是大小为\(2m\)的集合\(\mathcal{X}\)的子集, 任何只观测到空间\(C\)中一半样本的学习算法\(A\), 都不具有信息来反映\(C\)中剩余样本. 因此存在一个可能性, 在\(C\)中未观测到的样本上, 目标函数\(f\)与\(A(S)\)预测的完全不同(详细证明见深入理解机器学习一书5.1节):

从\(\mathcal{X}\to\{0,1\}\)有\(T=2^{|\mathcal{X}|}\)个函数,记为\(f_{1},...,f_{T}\). 对每个\(f_{i}\)取分布\(\mathcal{D_{i}}\)满足\(f_{i}\), 即如果\(y\neq f(x)\), 分布\(\mathcal{D_{i}}\)抽取样本\(x×y\)的概率置为0.
事实上, 此时\(|\mathcal{X}|\)可直接取为\(2m\), 假定对\(|\mathcal{X}|=2m\)定理得证, 那么此时任意加入新样本,只需将新样本的标签取成\(|1-A(S)|\), 就能保证\(L_{\mathcal{D}}(A(S))\)仍大于\(\frac{1}{8}\), 而\(f\)及\(\mathcal{D}\)只需要做相应修改.
对任意学习算法\(A\)从1.中的\(\{\mathcal{D}_{i}\}\)找一个\(\mathcal{D}_{i}\)使得\(E[L_{\mathcal{D_{i}}}(A(S))]\ge \frac{1}{4}\).
\(P[L_{\mathcal{D}_{i}}(A(S))\ge\frac{1}{8}]\ge\frac{1}{7}\)

注意到定理中并没有对假设类\(\mathcal{H}\)加以限制, 假设类\(\mathcal{H}\)的规模是随着样本量大小而指数型增长的, 从而导致学习失败. 于是乎如果我们要想学习成功, 就必须对假设类\(\mathcal{H}\)加以限制, 那么如何去限制呢？

我们已经知道任何有限假设类都是可学习的(Hoeffding测度集中不等式可证).
那么无限类呢?事实上, 有一个叫VC维的东西可以刻画出PAC可学习的假设类的增长速度如何, 直观的去看, VC维有限的假设类就是那些限制在集合\(C\)上并且只能随着\(|C|\)的增长而多项式增长而不是指数型增长的这类假设类, 这也被称为是小的有效规模.

打散

打散(Shattering):

如果限制\(\mathcal{H}\)在\(C\)上是从\(C\)到\(\{0,1\}\)的所有函数的集合, 那么我们称\(\mathcal{H}\)打散了集合\(C\), 此时\(|\mathcal{H}_{C}|=2^{|C|}\).

这里\(\mathcal{H}\)的状态也就是上文说的不加以限制的状态.

VC维

VC维(VC-dimension):

假设类\(\mathcal{H}\)的VC维, 记为\(VCdim(\mathcal{H})\)可以打散的最大的集合的大小. 如果\(\mathcal{H}\)可以打散任何集合大小,我们说\(\mathcal{H}\)的VC维是无穷的.

回头再来看没有免费午餐定理,我们易得下述推论:

\(\mathcal{X}\)为一个无限定义域集, \(\mathcal{H}\)为从\(\mathcal{X}\to\{0,1\}\)上的所有映射集, 即\(VCdim(\mathcal{H})=+\infty\),则\(\mathcal{H}\)不是PAC可学习的.

偏差与复杂性权衡与偏差方差权衡

在PAC可学习框架下, 我们所用的方式是: 对于给定的假设类\(\mathcal{H}\)(先验知识), 采用ERM范式(最小化训练误差)从中选取分类器\(h\).

我们将ERM范式返回的假设\(h_{ERM}\)的泛化误差\(L_{\mathcal{D}}(h_{ERM})\)分解为两部分, 第一部分叫偏差, 由假设类具有的最小风险\(\min_{h\in\mathcal{H}}L_{\mathcal{D}}(h)\)所决定, 它反映了先验知识的质量; 第二部分叫复杂性\(L_{\mathcal{D}}(h_{ERM})-\min_{h\in\mathcal{H}}L_{\mathcal{D}}(h)\), 是由过拟合引起的误差, 取决于假设类的大小或是复杂度, 又称为估计误差. 随着假设类变得越复杂, 偏差会变小, 但是复杂性会变大.

另一种更常见的分解方式是将ERM范式返回的假设\(h_{ERM}\)的泛化误差\(L_{\mathcal{D}}(h_{ERM})\)分解为训练误差\(\min_{h\in\mathcal{H}}L_{S}(h)\)和方差\(L_{\mathcal{D}}(h_{ERM})-\min_{h\in\mathcal{H}}L_{S}(h)\), 随着假设类变得越复杂, 训练误差会越来越小, 而泛化误差会有一个先增后减的过程.

定理的证明

定义说完了, 下面来看证明:

1推2

一句话证明1推2:\(\mathcal{H}\)一致收敛也就是说样本量足够时, \(S\)是\(\varepsilon\)-代表性样本, 现用\(\varepsilon/2\)取代\(\varepsilon\), \(\varepsilon\)-代表性样本的定义及ERM的返回规则得:对\(\forall h\in \mathcal{H}\),\[L_{\mathcal{D}}(h_{S})\le L_{\mathcal{S}}(h_{S})+\varepsilon/2\le L_{\mathcal{S}}(h)+\varepsilon/2 \le L_{\mathcal{D}}(h)+\varepsilon/2+\varepsilon/2=L_{\mathcal{D}}(h)+\varepsilon\]即由ERM(S)返回\(h_{S}\)的泛化误差\(L_{\mathcal{D}}(h_{S})\)能保证学习成功.

2推3

2推3就非常显然, 2是对于假设类\(\mathcal{H}\)采用了ERM学习算法的学习器在\(\mathcal{H}\)能成功, 要证明3只要证明存在一个学习算法能成功, 显然存在(ERM).

3推4

3推4更显然, 3是4的泛化, 所以4的条件成立时3必然能用, 再加上\(f\)满足可实现的假设, 即存在完美的分类器使得泛化误差为0, 得证.

2推5

2推5同上可证.

4推6

4推6用到了没有免费的午餐定理, 这个定理可以叙述为如果\(\mathcal{H}\)的VC维无限, 那么\(\mathcal{H}\)就不是PAC可学习的, 来看这个命题的逆否命题, 即如果\(\mathcal{H}\)是PAC可学习的, 那么\(\mathcal{H}\)的VC维有限.

5推6

5推6的话同样用到了免费的午餐定理, 假设\(\mathcal{H}\)的VC维无穷, 那么\(\mathcal{H}\)不是PAC可学习的, 然后铁定不是采取了ERM之后的PAC可学习的了.

6推1

这里只叙述证明思路:

如果\(VCdim(\mathcal{H})=d<+\infty\), 那么即使\(\mathcal{H}\)无限, 当将其限制在一有限集合\(C\)时, 其有效规模\(|\mathcal{H}_{C}|\)只有\(O(|C|^{d})\).
假设类有一个小的有效规模时其一致收敛成立, 小的有效规模指的是\(|\mathcal{H}_{C}|\)随\(|C|\)按多项式方式增长.

其中第一步实际上是将\(\mathcal{H}\)的VC维有限时, \(\mathcal{H}\)的增长速度为多项式增长这一事实明确下来, 证明用到了Sauer引理, 详细见深入理解机器学习一书6.5.1节; 2.的证明见深入理解机器学习一书6.5.2节.\(□\)

统计学习的基本定理-定量形式

\(\mathcal{H}\)是一个由\(\mathcal{X}\to \{0,1\}\)的映射函数构成的假设类, 且令损失函数为0-1损失. 假定\(VCdim(\mathcal{H})<\infty\), 那么, 存在绝对常数\(C_{1},C_{2}\)使得:

\(\mathcal{H}\)一致收敛, 若其样本复杂度满足: \[C_{1}\frac{d+log(1/\delta)}{\varepsilon^{2}}\le m^{UC}_{\mathcal{H}}(\varepsilon,\delta)\le C_{2}\frac{d+log(1/\delta)}{\varepsilon^{2}}\]

\(\mathcal{H}\)是不可知PAC可学习的, 若其样本复杂度满足: \[C_{1}\frac{d+log(1/\delta)}{\varepsilon^{2}}\le m_{\mathcal{H}}(\varepsilon,\delta)\le C_{2}\frac{d+log(1/\delta)}{\varepsilon^{2}}\]

\(\mathcal{H}\)是PAC可学习的, 若其样本复杂度满足: \[C_{1}\frac{d+log(1/\delta)}{\varepsilon}\le m_{\mathcal{H}}(\varepsilon,\delta)\le C_{2}\frac{dlog(1/\varepsilon)+log(1/\delta)}{\varepsilon^{2}}\]

p.s.由上述定理可以看出, 一致收敛与不可知PAC可学习的需要的样本量一致, 而PAC可学习的需要的样本量少一些. 该定理的证明在深入理解机器学习一书第28章给出.

不一致可学习

上文所讨论的PAC可学习的概念是考虑精度和置信参数来决定样本数量, 且样本标签分布与内在的样本数据分布是一致的. 因此, PAC可学习等价于VC维有限. 下面要讨论的是不一致可学习这个概念, 这个概念是不可知PAC可学习的严格松弛, 它允许样本数量依赖假设空间\(\mathcal{H}\), 下面来看其定义:

不一致可学习(Nonuniform learnability):

称假设类\(\mathcal{H}\)是不一致可学习的若存在一个学习算法\(A\)和一个函数\[m^{NUL}_{\mathcal{H}}:(0,1)\times(0,1)×\mathcal{H}\to\mathbb{N}\]使得对于\(\forall\varepsilon,\delta\in(0,1)\)和\(h\in\mathcal{H}\), 如果样本数量\(m\ge m^{NUL}_{\mathcal{H}}(\varepsilon,\delta,h)\), 那么对每个分布\(\mathcal{D}\), 下式成立的概率不小于\(1-\delta\), \(L_{\mathcal{D}}(A(S))\le L_{\mathcal{D}}(h)+\varepsilon\).

这个概念要求输出假设与假设类中其他假设相比具有\((\varepsilon,\delta)\)的竞争力, 同时从定义也很容易得到不可知PAC可学习一定能推得不一致可学习, 且不一致可学习是不可知PAC可学习的严格松弛. 下面举个例子说明两者的严格松弛关系:

考虑二分问题, 假设\(\mathcal{H}_{n}\)是\(n\)次多项式构成的假设类, 即\(\mathcal{H}_{n}\)为\(h(x)=sign(p(x))\)的分类器的集合.这里\(p(x)\)是\(\mathbb{R}\to\mathbb{R}\)的\(n\)次多项式.令\(\mathcal{H}=\cup_{n\in\mathbb{N}}\mathcal{H}_{n}\). 容易得到\(VCdim(\mathcal{H})=+\infty\), 但\(\mathcal{H}\)是不一致可学习的.

事实上, 有一个定理清晰的描述了两者的关系:

两分类器的假设类\(\mathcal{H}\)是不一致可学习的, 当且仅当它是不可知PAC可学习的可数并.

下面来看这个定理的证明:

必要性: 假定\(\mathcal{H}\)是不一致可学习的, 对于每个\(n\in\mathbb{N}\),令\[\mathcal{H}_{n}=\{h\in\mathcal{H}:m^{NUL}_{\mathcal{H}}(\frac{1}{8},\frac{1}{7},h)\le n\}\]显然\(\mathcal{H}=\cup_{n\in\mathbb{N}}\mathcal{H}_{n}\). 此外, 由\(m^{NUL}_{\mathcal{H}}\)定义知, 对于任何关于\(\mathcal{H}_{n}\)满足可实现性假设的分布\(\mathcal{D}\), \(S\)由\(\mathcal{D}\)独立抽样得到, 选择样本\(S\)的概率大于等于\(\frac{6}{7}\). 则\(L_{\mathcal{D}}(A(S))\le\frac{1}{8}\). 由统计学习基本定理知, \(VCdim(\mathcal{H}_{n})<+\infty\), 因此\(\mathcal{H}_{n}\)是不可知PAC可学习的.
充分性: 充分性的证明依赖于下述引理:

\(\mathcal{H}=\cup_{n\in\mathbb{N}}\mathcal{H}_{n}\), 如果\(\mathcal{H}_{n}\)是一致收敛的, 那么\(\mathcal{H}\)是不一致可学习的.

该引理证明留给下小节, 那么由统计学习基本定理知, 不可知PAC可学习与一致收敛性等价,即得证\(□\)

结构风险最小化SRM

本节主要是关于结构风险最小化(SRM:Structural Risk Minimization)以及利用结构风险最小化算法来证明上节未证明的引理.

目前为止, 我们都是通过具体化一个假设类\(\mathcal{H}\)来利用先验知识, 并且相信这样一个假设类中包含完成当前任务的有效预测器. 而另一种表达先验知识的方法则是将假设类\(\mathcal{H}\)上的偏好具体化.

在结构风险最小化范式中, 我们首先假定假设类\(\mathcal{H}\)能够写成\(\mathcal{H}=\cup_{n\in\mathbb{N}}\mathcal{H}_{n}\),\(\mathcal{H}_{n}\)满足一致收敛, 且样本复杂度函数为\(m^{UC}_{\mathcal{H}_{n}}(\varepsilon,\delta)\), 然后具体化一个权重函数\[\omega:\mathbb{N}\to[0,1],s.t.\sum_{n}\omega(n)\le1\]这个权重函数可也反映每个假设类的重要性, 或是假设类复杂性的度量.例如\(\mathcal{H}\)是所有多项式分类器构成的类, \(\mathcal{H}_{n}\)表示\(n\)次多项式分类器构成的类.定义下式函数\(\varepsilon_{n}\):\(\mathbb{N}×(0,1)\to(0,1)\) \[\varepsilon_{n}(m,\delta)=\min\{\varepsilon\in (0,1):m^{UC}_{\mathcal{H}_{n}}(\varepsilon,\delta)\le m\}\]由\(\mathcal{H}_{n}\)满足一致收敛性, \(\forall m\in\mathbb{N}\),\(\forall\delta\in(0,1)\), 大小为\(m\)的样本\(S\)由\(\mathcal{D}\)独立抽样得到, 下式成立的概率不小于\(1-\delta\) \[\forall h \in \mathcal{H}_{n},|L_{\mathcal{D}}(h)-L_{S}(h)|\le\varepsilon_{n}(m,\delta)\]这就是我们所关心的训练误差与泛化误差之间的差值. 此时权重函数可取成\(\omega(n)=\frac{6}{\pi^{2}n^{2}}\)或是\(\omega(n)=2^{-n}\).

下面将上述例子写成定理的形式,并由此引出结构风险最小化(SRM):

假设类\(\mathcal{H}=\cup_{n\in\mathbb{N}}\mathcal{H}_{n}\),\(\mathcal{H}_{n}\)一致收敛, 且复杂度函数为\(m^{UC}_{\mathcal{H}_{n}}\). 令\(\omega:\mathbb{N}\to[0,1],s.t.\sum_{n}\omega(n)\le1\)为一权重函数. 令\[\varepsilon_{n}(m,\delta)=\min\{\varepsilon\in (0,1):m^{UC}_{\mathcal{H}_{n}}(\varepsilon,\delta)\le m\}\] 则对\(\forall\delta\in(0,1)\),任意的分布\(\mathcal{D}\), 下式成立的概率不小于\(1-\delta\):\[\forall h \in \mathcal{H}_{n},L_{\mathcal{D}}(h)\le L_{S}(h)+\varepsilon_{n(h)}(m,\omega(n(h))·\delta)\]其中\(n(h)=\min\{n:h\in\mathcal{H}_{n}\}\).

证明: 对\(\forall n\in\mathbb{N}\), 定义\(\delta_{n}=\omega(n)\delta\), 固定\(n\), 由一致收敛性, 在选择样本\(S\)的概率不低于\(1-\delta\)的条件下, \[\forall h \in \mathcal{H}_{n},|L_{\mathcal{D}}(h)-L_{S}(h)|\le\varepsilon_{n}(m,\delta_{n})\]应用\(n=1,2,...,\)的联合界, 我们得到上述结论以不低于\[1-\sum_{n}\delta_{n}=1-\delta\sum_{n}\omega(n)\ge1-\delta\]的概率对\(\forall n\in\mathbb{N}\)都成立, 最后令\(n(h)=\min\{n:h\in\mathcal{H}_{n}\}\)自然也成立.\(□\)

结构风险最小化(SRM)则是寻找\(h\)来最小化这个上界, 以保证\(L_{\mathcal{D}}(h)\)不是那么大, 下面是结构风险最小化(SRM)的定义:

先验:\(\mathcal{H}=\cup_{n\in\mathbb{N}}\mathcal{H}_{n}\), \(\mathcal{H}_{n}\)一致收敛, 且复杂度函数为\(m^{UC}_{\mathcal{H}_{n}}\); 权重函数\(\omega:\mathbb{N}\to[0,1],s.t.\sum_{n}\omega(n)\le1\).
定义:\(\varepsilon_{n}(m,\delta)=min\{\varepsilon\in(0,1):m^{UC}_{\mathcal{H}_{n}}(\varepsilon,\delta)\le m\}\); \(n(h)=min\{n:h\in\mathcal{H}_{n}\}\).
输入:训练集\(S\), 置信度\(\delta\).
输出:\(h\in argmin_{h\in\mathcal{H}}[L_{S}(h)+\varepsilon_{n(h)}(m,\omega(n(h))·\delta)]\).

p.s.结构风险最小化(SRM)与经验风险最小化(ERM)最大的不同就是, 经验风险最小化(ERM)只关心训练误差\(L_{\mathcal{S}}(h)\), 而结构风险最小化(SRM)兼顾了训练误差\(L_{\mathcal{S}}(h)\)和训练误差与泛化误差之间的差值\(\varepsilon_{n(h)}(m,\omega(n(h))·\delta)\).

下面用SRM来证明上节未能证明的一个引理:

\(\mathcal{H}=\cup_{n\in\mathbb{N}}\mathcal{H}_{n}\), 如果\(\mathcal{H}_{n}\)是一致收敛的, 那么\(\mathcal{H}\)是不一致可学习的.

事实上利用SRM算法我们能得到下述更进一步的结论:

假设类\(\mathcal{H}=\cup_{n\in\mathbb{N}}\mathcal{H}_{n}\), \(\mathcal{H}_{n}\)一致收敛, 且复杂度函数为\(m^{UC}_{\mathcal{H}_{n}}\).如果\(\omega\):\(\mathbb{N}\to[0,1]\), \(s.t.\omega(n)=\frac{6}{\pi^{2}n^{2}}\), 那么\(\mathcal{H}\)是不一致可学习的, 且满足有\[m^{NUL}_{\mathcal{H}}(\varepsilon,\delta,h)\le m^{UC}_{\mathcal{H}_{n(h)}}(\frac{\varepsilon}{2},\frac{6\delta}{(\pi n(h))^{2}})\]

证明: 假定\(A\)是考虑权重函数\(\omega\)的结构风险最小化算法, 对于\(\forall h\in\mathcal{H}_{n},\forall\varepsilon,\delta\in(0,1)\), 令\(m\ge m^{UC}_{\mathcal{H}_{n(h)}}(\varepsilon,\omega(n(h))·\delta)\),应用上述定理, 可以得到\[\forall h \in \mathcal{H}_{n},L_{\mathcal{D}}(h)\le L_{S}(h)+\varepsilon_{n(h)}(m,\omega(n(h))·\delta)\]这个定理对于由结构风险规则返回的假设\(A(S)\)成立. 通过结构风险最小化的定义可得,\[L_{\mathcal{D}}(A(S))\le\min_{h}[L_{S}(h)+\varepsilon_{n(h)}(m,\omega(n(h))·\delta)]\le L_{S}(h)+\varepsilon_{n(h)}(m,\omega(n(h))·\delta)\]如果\(m\ge m^{UC}_{\mathcal{H}_{n(h)}}(\frac{\varepsilon}{2},\omega(n(h))·\delta)\), 那么\(\varepsilon_{n(h)}(m,\omega(n(h))·\delta)\le\frac{\varepsilon}{2}\). 此外, 从每个\(\mathcal{H}_{n}\)的一致收敛性, 我们可得到下式成立的概率大于\(1-\delta\),\[L_{S}(h)\le L_{\mathcal{D}}(h)+\frac{\varepsilon}{2}\]综上所述, 可得\(L_{\mathcal{D}}(A(S))\le L_{\mathcal{D}}(h)+\varepsilon\), 定理得证.\(□\)

单独比较不一致可学习和不可知PAC可学习是非常有意思的, 算法会在全空间\(\mathcal{H}\)上搜索一个模型, 而不是在特定的\(\mathcal{H}_{n}\)上搜索一个模型, 利用先验知识的缺陷所带来的成本就是增加复杂度与特定的\(h\in\mathcal{H}_{n}\)相竞争.假定对于所有的\(n\), \(VCdim(\mathcal{H}_{n})=n\), 由统计学习的基本定理-定量形式知\[m^{UC}_{\mathcal{H}_{n}}(\varepsilon,\delta)\le C\frac{n+log(1/\delta)}{\varepsilon^{2}}\] 一个直接的计算表明\[m^{NUL}_{\mathcal{H}_{n}}(\varepsilon,\delta,h)-m^{UC}_{\mathcal{H}_{n}}(\frac{\varepsilon}{2},\delta)\le 4C\frac{2\log(2n)}{\varepsilon^{2}}\]代价增加了类的索引, 可以解释为反映已知的假设类\(\mathcal{H}\)的好的先验知识的排序值.

不一致可学习的没有免费午餐定理

在不一致可学习框架下,没有免费的午餐定理(No-Free-Lunch for Nonuniform Learnability)也是成立的,也就是说, 当样本域无限时, 不存在关于所有确定性二分类器所构成的类的不一致学习器(尽管对于每一个分类器存在一个尝试算法能够学习包含这些分类器假设的结构风险最小化).

最小描述长度MDL

\(\mathcal{H}\)为假设类, 将\(\mathcal{H}\)写成单个类的可数并, 即\(\mathcal{H}=\cup_{n\in\mathbb{N}}\{h_{n}\}\).

由Hoeffding不等式知, 每一个单类有一致收敛性, 收敛速率\(m^{UC}(\varepsilon,\delta)=\frac{\log(2/ \delta)}{2\varepsilon^{2}}\), 该结果的证明见深入理解机器学习一书page26. 因此, \[\varepsilon_{n}(m,\delta)=\min\{\varepsilon\in (0,1):m^{UC}(\varepsilon,\delta)\le m\}\]所给出的函数\(\varepsilon_{n}\)变成了\[\varepsilon_{n}(m,\delta)=\sqrt{\frac{\log(2/\delta)}{2m}}\]且结构风险最小化SRM变成了:\[argmin_{h_{n}\in\mathcal{H}}L_{S}(h)+\sqrt{\frac{-\log(\omega(n))+\log(2/\delta)}{2m}}\]等价的, 我们可以认为\(\omega\)是从\(\mathcal{H}\to[0,1]\)的函数, 然后结构结构风险最小化SRM变成了:\[argmin_{h\in\mathcal{H}}L_{S}(h)+\sqrt{\frac{-\log(\omega(h))+\log(2/\delta)}{2m}}\]这节讨论一种特别方便的方式定义权重函数\(\omega(h)=\frac{1}{2^{|h|}}\), 这个函数与假设的描述长度有关. 下面介绍其背景:

对于每个假设类\(\mathcal{H}\), 我们想知道如何描述和表示每一个类的假设\(h\), 英语, 汇编语言, 数学公式等等形式, 当我们选定某种语言形式, 那么一个假设\(h\)肯定能被一些特定字母\(\Sigma\)组成的有限字符串所描述, \(\Sigma\)我们称之为字母表. 例如, 令\(\Sigma=\{0,1\}\), \(\sigma=(0,1,1,1,0)\)为一字符串且字符串的长度\(|\sigma|=5\), 所有有限长度的字符串用\(\Sigma^{+}\)表示, 对假设类\(\mathcal{H}\)的描述可用一个函数\(d:\mathcal{H}\to\Sigma^{+}\)表示, \(d(h)\)将\(\mathcal{H}\)中每个假设\(h\)映射为一个字符串\(d(h)\), \(d(h)\)称为\(h\)的描述长度, \(|h|\)表示\(d(h)\)的长度. 我们要求描述语言\(d(h)\)无前缀, 即不同的\(h\), \(h'\), \(d(h)\)不是\(d(h')\)的前缀. 无前缀的字符串满足如下组合性质:

Kraft不等式:

如果\(S\subset\{0,1\}^{+}\)是一个无前缀的字符串集合,则\(\sum_{\sigma\in S}\frac{1}{2^{|\sigma|}}\le1\).

根据Kraft不等式, 任何无前缀的语言都能给出假设类\(\mathcal{H}\)的权重函数\(\omega\), 我们可简单的设置为\(\omega(h)=\frac{1}{2^{|h|}}\),于是便有了下述定理:

\(\mathcal{H}\)是一假设类, \(d:\mathcal{H}\to\{0,1\}^{+}\)是\(\mathcal{H}\)的一无前缀描述语言,对于样本量\(m\), 置信参数\(\delta>0\)和概率分布\(\mathcal{D}\), 下式成立的概率大于\(1-\delta\):\[\forall h \in \mathcal{H},L_{\mathcal{D}}(h)\le L_{S}(h)+\sqrt{\frac{|h|+\log(2/\delta)}{2m}}\]这里\(|h|\)是指\(d(h)\)的长度.

类似结构风险最小化(SRM), 最小描述长度(MDL)这种考虑了训练误差和减小描述长度, 这就得到了减小描述长度的学习范式. 最小描述长度(MDL:Minimum Description Length):

先验: 假设类\(\mathcal{H}\)由定义在\(\{0,1\}\)上的无前缀语言\(d\)描述;对于任何一个\(h\in\mathcal{H}\), \(|h|\)表示\(d(h)\)的长度.
输入: 训练集\(S\), 置信度\(\delta\).
输出: \(h\in argmin_{h\in\mathcal{H}}L_{S}(h)+\sqrt{\frac{|h|+\log(2/\delta)}{2m}}\)

奥卡姆剃刀原理

上届的定理指出, 对于经验风险相同的两个假设, 描述长度较小的假设, 其真实风险的误差界更小, 因此这个结果表达了一个哲学理念, 这也是著名的奥卡姆剃刀原理(Occam’s Razor):

短的解析更有效.

p.s.假象下列情形, 两个假设\(h\), \(h'\)在数学语言下的描述长度分别为10,100; 但在中文下的长度分别为100,10. 因此这里笔者理解为对大多数语言的来说短的解析, 或是期望意义下的最短的解析.

一致性

最后给出一个比不一致可学习更松弛的可学习概念: 一致性, 这个概念允许所欲要的样本不仅依赖于\(\varepsilon,\delta\)和\(h\),而且依赖于数据所依托的分布\(\mathcal{D}\).

一致性(Consistency):

\(\mathcal{P}\)表示\(Z\)上的概率分布, 称一个学习规则\(A\)关于\(\mathcal{H}\)和\(\mathcal{P}\)满足一致性, 若存在一个函数\[m^{CON}_{\mathcal{H}}:(0,1)^{2}×\mathcal{H}×\mathcal{P}\to\mathbb{N}\]使得对\(\forall h\in\mathcal{H}\),\(\forall\mathcal{D}\in\mathcal{P}\),\(\forall\varepsilon\),\(\delta\in(0,1)\), \(m\ge m^{NUL}_{\mathcal{H}}(\varepsilon,\delta,h,\mathcal{D})\),下式成立的概率不小于1-δ\(L_{\mathcal{D}}(A(S))\le L_{\mathcal{D}}(h)+\varepsilon\).

Memorize算法

考虑如下定义的分类预测算法Memorize, 这个算法对新样本的预测永远都是某个固定的标签,比如说是训练集中出现次数最多的标签. 事实上, Memorize算法对于任何数据集上所有函数构成的类都满足一致性, 但这个算法很明显没有什么用.

写在最后: 本文主要是写了写PAC可学习框架下有关VC维的内容, 这个VC维(Vapnik–Chervonenkis dimension)其实代表两位大牛:svm发明者Vapnik和俄罗斯的数学家Chervonenkis. 进一步内容的Rademacher复杂度则是我下一篇博客的内容, 西瓜书将其放在12.5节, 深入理解机器学习一书则是将其放在第四部分高级理论26-27章, 针对多分类问题的Natarajan维在29章.