台湾大学林轩田老师的《机器学习基石》课程由浅入深、内容全面，基本涵盖了机器学习领域的很多方面，作为机器学习的入门资料非常适合。很久之前看过这门课，但是有些地方还是不太明白，二刷这门课，把重要的知识总结起来，算是做一个复习，加深理解，也方便之后查阅。这篇文章介绍了第二部分Why Can Machine Learn？

Why Can Machine Learn?

上一篇文章，我们主要介绍了机器学习的可行性。本文将讨论机器学习的核心问题，严格证明为什么机器可以学习。

Training versus Testing

上一篇文章存在一个问题，即当hypothesis的个数是无限多的时候，比如PLA有无数条线可以完成分类操作时，机器学习的可行性是否仍然成立？上一篇文章总结下来，我们把机器学习的主要目标分成两个核心的问题：

$E_{in}(g)\approx E_{out}(g)$
$E_{in}(g)$ 足够小

在上一篇文章中，介绍到M为可供选择的hypothesis个数，当M很小的时候，由霍夫丁不等式，得到 $E_{in}(g)\approx E_{out}(g)$ ，即能保证第一个核心问题成立。但M很小时，演算法A可以选择的hypothesis有限，不一定能找到使 $E_{in}(g)$ 足够小的hypothesis，即不能保证第二个核心问题成立。当M很大的时候，同样由霍夫丁不等式， $E_{in}(g)$ 与 $E_{out}(g)$ Eout(g)的差距可能比较大，第一个核心问题可能不成立。而M很大，使的演算法A的可以选择的hypothesis就很多，很有可能找到一个hypothesis，使 $E_{in}(g)$ 足够小，第二个核心问题可能成立。

从上面的分析来看，M的选择直接影响机器学习两个核心问题是否满足，M不能太大也不能太小。那么如果M无限大的时候，是否机器就不可以学习了呢？例如PLA算法中直线是无数条的，但是PLA能够很好地进行机器学习，这又是为什么呢？如果我们能将无限大的M限定在一个有限的 $m_H$ 内，问题似乎就解决了。

在考虑M个hypothesis个数的前提下，霍夫丁不等式可改写为：

$P[|E_{in}(g)-E_{out}(g)|>\epsilon]\le 2Mexp(-2\epsilon^2N)$

每个hypothesis下的BAD events $B_m$ 级联的形式满足下列不等式：

$P[B_1\quad or\quad B_2\quad \cdots \quad B_M]\le P[B_1]+P[B_2]+\cdots+P[B_M]$

当 $M=\infty$ 时，上面不等式右边值将会很大，似乎说明BAD events很大， $E_{in}(g)$ 与 $E_{out}(g)$ 也并不接近。但是BAD events $B_m$ 级联的形式实际上是扩大了上界，union bound过大。这种做法假设各个hypothesis之间没有交集，这是最坏的情况，可是实际上往往不是如此，很多情况下，都是有交集的，也就是说M实际上没那么大。也就是说union bound被估计过高了（over-estimating）。所以，我们的目的是找出不同BAD events之间的重叠部分，也就是将无数个hypothesis分成有限个类别。经过分析，我们得到平面上线的种类是有限的，1个点最多有2种线，2个点最多有4种线，3个点最多有8种线，4个点最多有14（ $<2^4$ ）种线等等。我们发现，有效直线的数量总是满足 $\le 2^N$ ，其中，N是点的个数。所以，如果我们可以用effective(N)代替M，霍夫丁不等式可以写成：

$P[|E_{in}(g)-E_{out}(g)|>\epsilon]\le 2effective(N)exp(-2\epsilon^2N)$

已知 $effective(N)<2^N$ ，如果能够保证 $effective(N)\ll 2^N$ ，即不等式右边接近于零，那么即使M无限大，直线的种类也很有限，机器学习也是可能的。

接下来先介绍一个新名词：二分类（dichotomy）。dichotomy就是将空间中的点（例如二维平面）用一条直线分成正类（蓝色o）和负类（红色x）。令H是将平面上的点用直线分开的所有hypothesis h的集合，dichotomy H与hypotheses H的关系是：hypotheses H是平面上所有直线的集合，个数可能是无限个，而dichotomy H是平面上能将点完全用直线分开的直线种类，它的上界是 $2^N$ 。接下来，我们要做的就是尝试用dichotomy代替M。

再介绍一个新的名词：成长函数（growth function），记为 $m_{H}(H)$ 。成长函数的定义是：对于由N个点组成的不同集合中，某集合对应的dichotomy最大，那么这个dichotomy值就是 $m_{H}(H)$ ，它的上界是 $2^N$ 。成长函数其实就是我们之前讲的effective lines的数量最大值。根据成长函数的定义，二维平面上， $m_{H}(H)$ 随N的变化关系是：

N	$m_{H}(H)$
1	2
2	4
3	$max(\dots,6,8)=8$
4	14<2^N

接下来，我们讨论如何计算成长函数。先看一个简单情况，一维的Positive Rays：

若有N个点，则整个区域可分为N+1段，很容易得到其成长函数 $m_{H}(H)=N+1$ 。注意当N很大时， $(N+1)\ll 2^N$ ，这是我们希望看到的。另一种情况是一维的Positive Intervals：

这种情况下的成长函数为， $m_{H}(H)=\frac{1}{2}N^2+\frac{1}{2}N+1$ ，且 $\ll 2^N$ ，在N很大的时候，仍然是满足的。

假设在二维空间里，如果hypothesis是凸多边形或类圆构成的封闭曲线，如下图所示，左边是convex的，右边不是convex的。那么，它的成长函数是多少呢？

当数据集D按照如下的凸分布时，我们很容易计算得到它的成长函数 $m_{H}(H)=2^N$ 。这种情况下，N个点所有可能的分类情况都能够被hypotheses set覆盖，我们把这种情形称为shattered。也就是说，如果能够找到一个数据分布集，hypotheses set对N个输入所有的分类情况都做得到，那么它的成长函数就是 $2^N$ 。

因此，我们介绍了四种不同的成长函数，其中，positive rays和positive intervals的成长函数都是polynomial的，如果用 $m_H$ 代替M的话，这两种情况是比较好的。而convex sets的成长函数是exponential的，即等于M，并不能保证机器学习的可行性。那么，对于2D perceptrons，它的成长函数究竟是polynomial的还是exponential的呢？

对于2D perceptrons，我们之前分析了3个点，可以做出8种所有的dichotomy，而4个点，就无法做出所有16个点的dichotomy了。所以，我们就把4称为2D perceptrons的break point（5、6、7等都是break point）。令有k个点，如果k大于等于break point时，它的成长函数一定小于2的k次方。

根据break point的定义，我们知道满足 $m_{H}(k)\ne 2^k$ 的k的最小值就是break point。对于我们之前介绍的四种成长函数，他们的break point分别是：

Hypothesis	Break Point	Growth Function
positive rays	2	$m_{H}(N)=N+1$
positive intervals	3	$m_{H}(N)=\frac{1}{2}N^2+\frac{1}{2}N+1$
convex sets	no break point	$m_{H}(N)=2^N$
2D perceptrons	4	$m_{H}(N)\le 2^N$ in some cases

通过观察，我们猜测成长函数可能与break point存在某种关系：对于convex sets，没有break point，它的成长函数是2的N次方；对于positive rays，break point k=2，它的成长函数是O(N)；对于positive intervals，break point k=3，它的成长函数是 $O(N^2)$ 。则根据这种推论，我们猜测2D perceptrons，它的成长函数 $m_{H}(N)=O(N^{k-1})$ 。如果成立，那么就可以用 $m_H$ 代替M，就满足了机器能够学习的条件。

Theory of Generalization

下面引入一个例子，如果k=2，那么当N取不同值的时候，计算其成长函数 $m_H(N)$ 是多少。很明显，当N=1时， $m_H(N)=2$ ,；当N=2时，由break point为2可知，任意两点都不能被shattered（shatter的意思是对N个点，能够分解为 $2^N$ 种dichotomies）； $m_H(N)$ 最大值只能是3；当N=3时，简单绘图分析可得其 $m_H(N)=4$ ，即最多只有4种dichotomies。

所以，我们发现当N>k时，break point限制了 $m_H(N)$ 值的大小，也就是说影响成长函数 $m_H(N)$ 的因素主要有两个：

抽样数据集N
break point k（这个变量确定了假设的类型）

那么，如果给定N和k，能够证明其 $m_H(N)$ 的最大值的上界是多项式的，则根据霍夫丁不等式，就能用 $m_H(N)$ 代替M，得到机器学习是可行的。所以，证明 $m_H(N)$ 的上界是poly(N)，是我们的目标。

现在，我们引入一个新的函数：bounding function，B(N,k)。Bound Function指的是当break point为k的时候，成长函数 $m_H(N)$ 可能的最大值。也就是说B(N,k)是 $m_H(N)$ 的上界，对应 $m_H(N)$ 最多有多少种dichotomy。那么，我们新的目标就是证明：

$B(N,k)\le ploy(N)$

求解B(N,k)的过程十分巧妙：

当k=1时，B(N,1)恒为1。
当N < k时，根据break point的定义，很容易得到 $B(N,K)=2^N$ 。
当N=k时，此时N是第一次出现不能被shatter的值，所以最多只能有 $2^N-1$ 个dichotomies，则 $B(N,K)=2^N-1$ 。
当N>k时，情况较为复杂，结果为 $B(N,K)\le B(N-1,K)+B(N-1,K-1)$

根据推导公式，下表给出B(N,K)值

根据递推公式，推导出B(N,K)满足下列不等式：

$B(N,k)\le \sum_{i=0}^{k-1}(N^{i})$

也就是说成长函数 $m_H(N)$ 的上界B(N,K)的上界满足多项式分布poly(N)，下一步，如果能将 $m_H(N)$ 代替M，代入到Hoffding不等式中，就能推导得到 $E_{out}\approx E_{in}$ 的结论。最终，我们通过引入成长函数mHmH，得到了一个新的不等式，称为Vapnik-Chervonenkis(VC) bound：

The VC Dimension

再回顾一下机器能够学习必须满足的两个条件：

假设空间H的Size M是有限的，即当N足够大的时候，那么对于假设空间中任意一个假设g， $E_{out}\approx E_{in}$
利用算法A从假设空间H中，挑选一个g，使 $E_{in}(g) \approx 0$ ，则 $E_{out}(g) \approx 0$

这两个条件，正好对应着test和trian两个过程。train的目的是使损失期望 $E_{in}(g) \approx 0$ ；test的目的是使将算法用到新的样本时的损失期望也尽可能小，即 $E_{out}(g) \approx 0$ 。

正因为如此，引入了break point，并推导出只要break point存在，则M有上界，一定存在 $E_{out}\approx E_{in}$ 。接下来介绍VC Dimension的概念，引出VC Dimension与 $E_{in}(g) \approx 0$ ， $E_{out}(g) \approx 0$ ，Model Complexity Penalty的关系。

我们知道如果一个假设空间H有break point k，那么它的成长函数是有界的，它的上界称为Bound function。根据数学归纳法，Bound function也是有界的，且上界为 $N^{k-1}$ ，因此VC bound就可以转换成：

这样，不等式只与k和N相关了，一般情况下样本N足够大，所以我们只考虑k值。有如下结论：

若假设空间H有break point k，且N足够大，则根据VC bound理论，算法有良好的泛化能力
在假设空间中选择一个矩g，使 $E_{in}(g) \approx 0$ ，则其在全集数据中的错误率会较低

VC Dimension就是某假设集H能够shatter的最多inputs的个数，即最大完全正确的分类能力。（注意，只要存在一种分布的inputs能够正确分类也满足）。shatter的英文意思是“粉碎”，也就是说对于inputs的所有情况都能列举出来。例如对N个输入，如果能够将 $2^N$ 种情况都列出来，则称该N个输入能够被假设集H shatter。根据之前break point的定义，假设集不能被shatter任何分布类型的inputs的最少个数。则VC Dimension等于break point的个数减一。

用VC Dimension代替break point，那么VC bound的问题也就转换为与VC Dimension和N相关了。同时，如果一个假设集H的VC Dimension确定了，则就能满足机器能够学习的第一个条件 $E_{out}\approx E_{in}$ ，与算法、样本数据分布和目标函数都没有关系，用 $d_{vc}$ 代表VC Dimension。

已知在1D Perceptron， $d_{vc}=2$ ，在2D Perceptrons， $d_{vc}=3$ ，那么我们有如下假设： $d_{vc}=d+1$ ，其中d为维数。要证明的话，只需分两步证明：

$d_{vc}\ge d+1$
$d_{vc}\le d+1$

因此可以证明， $d_{vc}=d+1$

VC Dimension代表了假设空间的分类能力，即反映了H的自由度，产生dichotomy的数量，也就等于features的个数，但也不是绝对的。例如，对2D Perceptrons，线性分类， $d_{vc}=3$ ，则 $W={w_0,w_1,w_2}$ ，也就是说只要3个features就可以进行学习，自由度为3，因此M与 $d_{vc}$ 是成正比的。

机器学习模型的复杂度与样本数量N、假设空间 $H(d_{vc})$ 、ϵ、 $E_{out}$ 和 $E_{in}$ 共同决定。下面绘出 $E_{out}$ 、model complexity、 $E_{in}$ 随 $d_{vc}$ 变化的关系：

通过该图可以得出如下结论：

$d_{vc}$ 越大， $E_{in}$ 越小，Ω越大（复杂）
$d_{vc}$ 越小， $E_{in}$ 越小，Ω越小（简单）
随着 $d_{vc}$ 增大， $E_{out}$ 会先减小再增大

所以，为了得到最小的 $E_{out}$ ，不能一味地增大 $d_{vc}$ 以减小 $E_{in}$ ，因为 $E_{in}$ 太小的时候，模型复杂度会增加，造成 $E_{out}$ 变大。也就是说，选择合适的 $d_{vc}$ ，选择的features个数要合适，才能使假设空间H具有良好的泛化能力。

Noise and Error

那么在数据集中含有Noise的情况下，是否能够进行机器学习？

首先，Data Sets的Noise一般有三种情况：

由于人为因素，正类被误分为负类，或者负类被误分为正类
同样特征的样本被模型分为不同的类
样本的特征被错误记录和使用

之前的数据集是确定的，即没有Noise的，我们称之为Deterministic。现在有Noise了，也就是说在某点处不再是确定分布，而是概率分布了，即对每个(x，y)出现的概率是 $P(y|x)$ 。因为Noise的存在，比如在x点，有0.7的概率y=1，有0.3的概率y=0，即y是按照 $P(y|x)$ 分布的。数学上可以证明如果数据集按照 $P(y|x)$ 概率分布且是iid的，那么以前证明机器可以学习的方法依然奏效，VC Dimension有限即可推断 $E_{in}$ 和 $E_{out}$ 是近似的。 $P(y|x)$ 称之为目标分布（Target Distribution）。它实际上告诉我们最好的选择是什么，同时伴随着多少noise。

机器学习需要考虑的问题是找出的矩g与目标函数f有多相近，我们一直使用 $E_{out}$ 进行误差的估计，那一般的错误测量有哪些形式呢？我们介绍的矩g对错误的衡量有三个特性：

out-of-sample：样本外的未知数据
pointwise：对每个数据点x进行测试
classification：看prediction与target是否一致，classification error通常称为0/1 error

pointwise error是机器学习中最常用也是最简单的一种错误衡量方式。pointwise error一般可以分成两类：0/1 error和squared error。0/1 error通常用在分类（classification）问题上，而squared error通常用在回归（regression）问题上。有Noise的情况下，即数据集按照P(y|x)P(y|x)概率分布，那么VC Dimension仍然成立，机器学习算法推导仍然有效。机器学习cost function常用的Error有0/1 error和squared error两类。