机器为什么可以学习？

清新de花

机器为什么可以学习？

2016-11-21

PAC学习模型

自从下定决心认真学习机器学习理论开始，接触到很多基本问题，但其实都不是很理解，比如损失函数、风险函数、经验结构最小化、结构风险最小化、学习方法的泛化能力、VC维等，这些概念在学习中都纯属空泛的概念存在，我都不理解这些概念存在的意义。

为什么会存在这样的问题呢?我自己想了一下，有几个原因：首先，很多相关的书籍在讲授这些概念的时候，很少说这些为什么会有这样的概念问题，为解决什么问题引入的这些概念;然后，还有一些书，在简单表述了这些概念之后就立马挨个介绍算法了，遇到这样的书也会忽视这些基础问题的存在;最后，当初学者在遇到这些概念的时候，看到很多公式和抽象的表达方式，很容易产生挫败感，进而忽视了这些基础。

但是，我觉得这些问题还是很重要的。为什么这么说呢?原因如下：

1、理解这些问题有助于理解为什么机器可以学习，增强学习具体算法的信心，有助于深入进去;

2、理解这些基本问题并掌握基本的分析方法有助于分析具体学习算法的泛化能力;

举例

如图所示，输入为x，是一个三维数据，且元素都为布尔值，如果以D来做训练数据，那么要预测未知的情况，那请问当x为101,110,111的时候，预测输出y是什么呢?

我们看到图表中，会有8中不同的假设(hypothesis)，所以我们无论预测是哪种输出，都有可能让我们的预测是完全错误的。这是不是就说明这种条件下，学习器是不可学习的呢?现在我们就从这个角度出发，看看如何训练我们的学习器，才能让学习器真正学到有用的知识，进而来产生有效的预测。

可能近似正确（probably approximately correct，PAC）学习模型

问题框架

这里我会简要描述一下我们要处理的具体问题。

假定数据按照某概率分布P从X中随机产生，一般，D可为任意分布，并且它对学习型算法是未知的。对于P，所要求的是它的稳定性，即该分布不会随时间变化(不然我们就没有学习的意义了)。训练数据的由P分布随机抽取而产生x，然后x及其目标值(可以理解为y，标签)被提供给学习器

学习器在学习目标函数时考虑可能假设的集合H。

在观察了一系列训练数据后，学习器需要从假设集合H中得到最终的假设g，这是对未知的符合D分布的理想模型f的估计。

最后，我们通过精心挑选出来的假设g对X中新的数据的性能来评估训练器。

错误率

为了描述学习器输出的假设h对真实目标函数f的逼近程度，我们要定义两种错误率：

1、真实错误率(true error)，也可以说是out-of-sample error,即样本之外，对于从任意分布中抽取的所有数据而言。

h的真实错误率是应用h到未来按分布P抽取的数据时的期望错误率

具体定义如下：

2、样本错误率(sample error)，也可以说是in-sample error，即针对所训练的样本数据的。

因为h关于f的错误率不能直接由学习器观察到。学习器只能观察到在训练数据上h的性能如何，所以训练器也只能在此性能基础上选择其假设输出。我们用训练错误率(training error)来指代训练样本中被h误分类的数据所占的比例，以区分真实错误率。

那么，数据集合S的样本错误率为数据集合S中被h误分类的数据所占的比例。训练错误率就是当S为训练数据集合时的样本错误率。

PAC可学习性(PAC Learnability)

我们训练学习器的目标是，能够从合理数量的训练数据中通过合理的计算量可靠的学习到知识。

机器学习的现实情况：

1、除非对每个可能的数据进行训练，否则总会存在多个假设使得真实错误率不为0，即学习器无法保证和目标函数完全一致

2、训练样本是随机选取的，训练样本总有一定的误导性

为此，我们要弱化对学习器的要求：

1、我们不要求学习器输出零错误率的假设，只要求错误率被限制在某常数ε范围内，ε可为任意小。

2、不要求学习器对所有任意抽取的数据都能成功预测，只要求其失败的概率被限定在某个常数μ的范围内，μ可取任意小。

简而言之，我们只要求学习器可能学习到一个近似正确的假设，故得到了“可能近似正确学习”或PAC学习。

一个可PAC学习的学习器要满足两个条件：

学习器必须以任意高的概率输出一个错误率任意低的假设

学习过程的时间最多以多项式方式增长

对于PAC学习来说，训练样本的数量和学习所需的计算资源是密切相关的。如果学习器对每个训练样本需要某最小处理时间，那么为了使目标函数f是可PAC学习的，学习器必须在多项式数量的训练样本中进行学习。实际上，为了显示某输出空间的类别C是可PAC学习的，一个典型的途径是证明中每个C可以从多项式数量的训练样本中学习到，而后证明每个样本处理时间也限制于多项式级。

Hoeffding不等式

假设空间的样本复杂度

PAC可学习性很大程度上由所需的训练样本数量决定。随着问题规模的增长所带来的所需训练样本的增长称为学习问题的样本复杂度(sample complexity)。在多数实际问题中，最限制学习器成功的因素是有限的可用的训练数据。

我们通常都喜欢能与训练数据拟合程度更高的假设，当一个学习器在可能时都输出能完美拟合训练数据的假设时，我们称该学习器是一致的(consistent)。这就要求训练错误率是0。

遗憾的是，如果假设空间里不总是能找到一个零错误率的假设，这时，最多能要求学习器输出的假设在训练数据上有最小的错误率。

在更一般的情形下，我们要考虑学习器有非零训练错误率的假设时，仍能找到一个边界来限定学习器所需的样本数量。

Hoeffding边界

描述问题

现在，我们来更准确的描述我们要解决的问题。

令D代表学习器可观察的特定的训练数据集合，而P代表整个数据集合背后满足的概率分布。令Ein(h)代表假设h的训练错误率(在机器学习基石课程中，该错误率被称为in-sample error)，确切的说，Ein(h)是数据集D中被h误分类的训练数据所占比例，Ein(h)是定义在训练数据集D上的，而真实错误率Eout(h)(out-of-sample error)是定义在整个概率分布P上的。现在令g代表H中有最小训练错误率的假设。问：多少训练数据才足以保证真实错误率Eout(h)和训练错误率Ein(h)很接近，并且接近0。

Hoeffding不等式

Hoeffding刻画的是某个事件的真实概率及其m个独立重复试验中观察到的频率之间的差异，更准确的将，它是应用于m个不同的Bernoulli试验。

该不等式给出了一个概率边界，它说明任意选择的假设训练错误率不能代表真实情况。

确认（verification）流程

我们发现满足上面给的边界不等式的h可不可以说它是一个好的学习器呢?当然不能，上面的不等式只能说明h的训练错误率和真实错误率很接近，但却不一定是最小的，即h不一定是最佳的假设。所以，这只是对一个假设做确认的过程。

这里因为只有一个hypothesis在手上，所以我们还不能做选择，但是我们可以给它一些verifying examples来让它做确认，看看h的表现如何，正如上图流程所示。

有限假设空间的错误率的概率边界

Hoeffding不等式告诉我们什么呢?较好拟合训练数据的假设与该假设针对整个数据集合的预测，这两者的错误率差别很大的那种情况发生的概率是很小的。

那么现在的问题是什么呢?如果在多个假设中，其中一个假设针对训练数据的输出都是正确的，那要不要选这个假设作为算法的输出的假设呢?

带着这个问题，我们先了解一下什么叫做不好的数据。

Bad Sample and Bad Data

坏的样本就是训练错误率Ein=0，而真实错误率Eout=1/2的情况。

坏的数据是Ein和Eout差别很大的情况，通常Ein很小，Eout很大。

而Hoeffding说明的是如果把所有的训练数据(从输入空间中，随机选取产生的数据的不同组合)穷举出来，得到的不好的样本(Bad Sample)的概率是很小的。

所以坏的样本就是让算法的预测的准确率和训练时的正确率差别很大的情况(Ein和Eout差别很大)。

上图说明：

对于一个假设hi(每一行)，Hoeffding保证其不好的情况总体的概率是很小的

对于含有BAD的每一列来说，只要有BAD，算法就无法从所有假设中自由做选择

表中D1126这个数据集是好的数据

Bound of BAD Data

我们来算一下坏的数据的概率边界：

这个式子是有限个假设的Hoeffding不等式。

对于这个式子来说，如果训练数据的数量N够大的话，那么能保证Ein和Eout差别很小。

统计学习流程

上面的流程总结了我们这篇文章讨论的问题，那就是如果现有有限个假设且训练数据量够多的情况下，那么不管我们如何选择训练数据，训练错误率和真实错误率都会很接近;我们设计算法来找一个Ein最小的，PAC理论就保证了Eout很小。这样机器学习算法是有可能学到有用的知识的!

VC理论

面临待解决的问题

我们证明了PAC学习的样本复杂度随假设空间对数增长，但是以假设空间的个数|H|来刻画样本复制度存在缺点：

对于|H|很大的情形，会使一个很弱的边界，即出现错误的概率很大

对于无限假设空间的情形无法应用

所以，我们要考虑H的复杂度的另一种度量方式，称为H的Vapnik-Chervonenkis维度(简称VC维)，我们用VC(H)代替|H|得到样本复杂度的边界。

打散(shatter)一个数据集合

VC维衡量假设空间复杂度的方法不是用不同假设的数量|H|，而是用给定X中能被H彻底区分的不同实例的数量(举个例子，比如2D空间有两个数据，如果是用感知机模型的话，可以将这两个数据分成两个正例、两个负例、一正一负或一负一正，我们知道在这种情况下，感知机的假设空间是无穷的，但是实际上导致最终分类的只有4中不同结果)。

Dichotomy，一分为二的划分

想象我们现在有一个假设集合，这个假设集合将N个点的数据分成正例和负例的不同组合(用圈和叉来表示)，于是我们就将假设将数据分成不同正负例的组合称为Dichotomy。Hypotheses和Dichotomies的区别如下图所示，Dichotomies最多有2的N次方种可能。于是，我们就打算用Dichotomies的有效数量来取代有限假设空间的Hoeffding不等式中的M。

成长函数Growth Function

由于这里我们定义的Dichotomy是依赖具体的N个输入数据的，为了移除这里的影响，我们现定义成长函数mH(N)，用它来表示对于不同的数据集的Dichotomy的最大值。

以2D的Perceptron举例来说，针对不一样的输入点的个数N，可能有不同的有效分离平面，不一定是2的N次方种。

shatter

一数据集D被假设空间H打散(shatter)，当且仅当对D的每个划分，存在H中的某假设与此划分一致(即当D的每种可能划分可由H中的某个假设来表达时，称H打散D)。

注意：如果一个数据集合没有被假设空间打散，那么必然存在某种划分可被定义在数据集中，但不能由假设空间表示。

H的这种打散数据集合的能力是其在这些数据上定义目标函数的表示能力的度量。可以说被打散的X的子集越大，H的表示能力越强。

Break Point of H

基于上面的介绍我们可以回头看看Hoeffding不等式，我们想要用成长函数mH(N)来代替假设空间的数量|H|，而如果mH(N)和e的负幂次相乘，那么得到一个很小的数，这就对出错的概率作了一个限制;而如果mH(N)是一个幂指数的话，就无法限制错误率。

下面，我们定义一个新的概念——Break Point。如果数据集中的数据个数k是，假设空间H无法打散这个数据集，那么就说k是H的Break Point。比如，2D的Perceptron的情形，当N=4时，数据集应该可以有16种类别情形，而实际上，假设空间的有效个数只是14，那么4就是这个H的Break Point。

Bounding Function

上限函数Bounding Function B(N,k)是Break Point为k时，成长函数mH(N)的最大值，利用上限函数可以不去管假设空间里的具体细节，这样，只要上限函数是多项式的形式的话，就可以解决问题。

这里我们经过计算归纳，得到了上限函数的列表和规律：

经过一番努力，我们可以得到成长函数mH(N)<=上限函数B(N,k) <=多项式函数poly(N)，只要成长函数有Break Point存在，那么该成长函数就是一个多项式。

VC Bound

这里给出VC bound的结论

这个结论通俗来讲就是，数据够多的时候，机器学习算法真的可以学到有用的知识。

小结

上面我们可以知道,要学到有用的东西需要下面几个条件：

好的假设空间，即mH(N)存在Break Point

好的数据，即数据足够多，使得训练误差和真实误差很接近

好的算法，即算法可以选出一个训练误差很小的假设

好的运气，因为之前说明的是一个概率问题，所以要有一点点运气，恶劣的情况才不会发生

VC维

定义

定义在输入空间X上的假设空间H的VC维，是可被H打散的X的最大有限子集的大小(数据量的大小)。如果X的任意有限大的子集可被H打散，则VC(H)为无穷大。

结合上面的介绍，我们知道VC维和Break Point的关系是：VC维=‘minimum k’- 1。通俗一点，比VC维大就是Break Point。

终于，我们可以得出结论，VC维是有限的假设就是好的假设。

VC维和学习的关系

VC维和具体的学习算法A没有关系

VC维和输入数据的概率分布P没有关系

VC维和目标函数f没有关系

VC维与模型复杂度、样本复杂度

VC维的物理意义

如果我们将假设集合的数量|H|比作假设集合的自由度，那么VC维就是假设集合在做二元分类的有效的自由度，即这个假设空间能够产生多少Dichotomies的能力(VC维说的是，到什么时候，假设集合还能shatter，还能产生最多的Dichotomies)。

VC维、真实错误率、训练错误率

在上一节中，我们讨论要做到好的预测要满足两个条件，第一是训练误差要接近真实误差，即Ein(g)约等于Eout(g);第二是训练误差要尽量接近0，即Ein(g)约等于0。

现在，我们用VC维这个工具来描述。

如果VC维很小，那么发生预测偏差很大的坏事情的可能性也就很小，那这有利于Ein(g)接近Eout(g);但是，这是我们的假设空间的表达能力受到了限制，这样Ein(g)可能就没有办法做到很小。

如果VC维很大，那么假设空间的表达能力很强，我们很有可能选到一个Ein(g)很小的假设，但是Ein(g)和Eout(g)之差很大的坏事情发生的情况发生的可能性就变得很大，这样Ein(g)和Eout(g)根本不接近，我们就无法确定选择的假设在测试数据的时候表现的很好。

这时，VC维变成了我们一个重要的选择，我们可以用VC维提供的信息来选择更好的模型和假设空间。

模型复杂度（Model Complexity）

我们可以根据VC Bound公式，设发生坏事情的概率是δ，将其恒等变换可以得到训练误差和测试误差的差别ε。所以反过来讲，好事情(训练误差和测试误差的差别小于ε)发生时，Eout(g)被限制在一个范围内。这里根号内的式子定义为Ω(N,Η,δ)，称作模型复杂度,这个参数描述的意义是，我们的假设空间H有多么的强，使得我们的算法在泛化能力上需要付出多少代价。通俗的来讲，假设空间的容量越大，VC维越大，那么模型就越难学习。

VC维传递的信息

如下图所示，我们可以看出随VC维变化，Ein、Eout、模型复杂度都是如何变化的。

这里一个很直接的信息就是模型复杂度随着VC维的变大不断变大，呈正相关趋势。

因为VC维变大时，数据中可以shatter的点就变多了，那么假设空间的容量就变大了，如果是一个合理的学习算法的话，就有机会找到一个更好的假设，使得Ein更小。

而Eout呢?在一开始的时候，Eout随着Ein的下降也下降，但是到某个点，因为我们要付出的代价变大了，Eout开始上升，所以最好的Eout是在中间的某个位置。

这里得到一个重要的结论，VC维越大或者假设空间能力越强大，虽然可以使得训练误差很小，但不见得是最好的选择，因为要为模型复杂度付出代价。

样本复杂度（Sample Complexity）

根据理论而言，样本复杂度大约是VC维的10000倍，而实际应用中，只需要VC维的10倍的量就够了。

我们这里介绍的VC Bound的条件是非常宽松的，这使得在样本复杂度的估计上可以和理论值相差很大，原因如下：

我们利用Hoeffding对任何的分布和任何的目标函数来推测真实的错误率

我们利用成长函数mH(N)来代替假设集合的数量，确保可以使用任何数据

用VC维表示的多项式来代替成长函数，使得我们只通过VC维就可以了解某个假设空间的性质

使用union bound来避免最差的状况

以上有关VC Bound传递的哲学信息可以很好的指导我们进行机器学习算法的实践。

参考资料