我们今天讨论的topic是thoery of generalization，即一般化、举一反三的理论。即在机器学习里面，机器究竟是怎么举一反三的。

Restriction of Break Point

从上节课我们已经知道，我们希望最终可以用growth function \(m_{H}(N)\)来取代逐渐会增长到无限大的M。今天我们要探讨两个问题：

• \(m_{H}(N)\)会不会增长的很慢
• 如果是的话，\(m_{H}(N)\)能不能用来取代长得很快，甚至可能是无限大的M

growth function \(m_{H}(N)\)是指在N个点上，hypothesis set最多能够产生的dichotomy个数。我们来回顾一下我们已经知道的growth function：

我们还知道，一旦k是一个break point，k+1, k+2, …都会是break point。那么在这种情况下，break point还会给我们的growth function更多的限制吗？

假如已知某个H的break point k=2，那它告诉我们什么信息呢？

• N=1时，按照定义，\(m_{H}(N) = 2\)
• N=2时，按照定义，\(m_{H}(N) \le 3 < 4\)
• N=3时呢？按照break point的定义，我们要满足任意两个点不被shatter： 因此，下面这种情况中，第四种情形就不能加入进来： 经过一番尝试，我们发现4个就是极限，第5个就是不能加进来的。因此，遵守任意两个不能被shatter的承诺下，我们能产生的dichotomy最多只有4种。\(m_{H}(N) = 4 << 8\)

我们发现，只要有一个break point，在更大的N处产生dichotomy时，会增加不少的限制。于是我们现在的主意是： 如果我们已经知道了k是一个break point，到底在有N个点时能够产生多少种可能性。如果这个可能性的个数是多项式，那么由于我们的growth function的最大值就是这个数，于是growth function\(m_{H}(N)\)也一定是个多项式。

Bounding Function - Basic Cases

我们定义bounding function B(N,k)为break point为k时，\(m_{H}(N)\)最大的可能值。

如果我们把我们的dichotomy看做一个个长度为N的向量，把它的某些维度遮起来，只看k个维度的话，我们不希望看到\(2^k\)种情况，也就是被shatter的情况。

如果我们能对这个bounding function的性质做出描述，我们就能忽略一些hypothesis set的一些无关的细节。例如B(N, 3)就同时约束了

• positive ray (k=3)
• 1D perceptron (k=3)

这样我们就不用去管这两个hypothesis set的差别。

我们的现在的目标就是证明：\(B(N,k) \le poly(N)\)，即bounding function的成长速度和多项式一样。

我们先来填关于bounding function的一个表：

• B(2,2) = 3
• B(3,2) = 4 （上一节中“图形化”的证明）
• B(N,1) = 1 （前一节的测验题）
• \(B(N,k) = 2^N\;for\;N<k\)
• \(B(N,k) = 2^N - 1\;for\;N=k\)

虽然我们已经填完了表格的大半，但是其实没有填的那部分才是重中之重。

Bounding Function - Inducive Cases

现在我们想办法填B(4,3)的值。我们猜想它的值可能和B(3,?)其中的某一个值有关。

我们可以写一个程序，去搜寻长度为4的vector所组成的dichotomy set在不违反break point是3的情况下，最大是多少。经过一番搜寻，我们发现B(4,3)=11:

那么我们怎么把B(4,3)规约到B(3,?)的情况上去呢？

我们可以整理一下我们找到的B(4,3)的“解”： 把里面的dichotomy分成了两部分：橘色-成双成对的部分，和紫色-形单影只的部分。 \[ B(4,3) = 11 = 2*\alpha + \beta\]

如果我们把\(\mathbf{x}_4\)遮住，则只有\(\alpha+\beta\)个dichotomy。又因为任何3个点不能shatter，所以： \[ \alpha + \beta \le B(3,3)\]

如果我们在把\(\mathbf{x}_4\)遮住以后，只看橙色部分。因为它们在\(\mathbf{x}_4\)上是成双成对的，因此在\(\alpha\)中，我们不能shatter任意两个x。因此： \[ \alpha \le B(3,2)\]

把上面的整理起来的话： \[ \begin{align} B(4,3) & = 2\alpha + \beta \\ \alpha + \beta & \le B(3,3) \\ \alpha & \le B(3,2) \\ \Rightarrow B(4,3) & \le B(3,3) + B(3,2) \end{align} \]

我们稍微推广一下，就有了： \[ \begin{align} B(N,k) & = 2\alpha + \beta \\ \alpha + \beta & \le B(N-1,k) \\ \alpha & \le B(N-1,k-1) \\ \Rightarrow B(N,k) & \le B(N-1,k) + B(N-1,k-1) \end{align} \] 这样，我们便可以继续填表了： 注意，我们填进表中的值并非真正的值，而是上限。

于是，我们现在便有了bounding function的上限，即上限的上限。

有了前面的基础，我们可以尝试证明一个定理： \[ B(N,k) \le \sum_{i=0}^{k-1}{N \choose i} \] 如果能证明这个，当然就好了，因为\({N \choose i}\)中的最高项就是\(N^{k-1}\)。

这里的证明其实是一个很简单的数学归纳法，就不详细展开了。

好消息是，growth function会被bounding function限制住，bounding function会被bounding function的上限限制住，而bounding function的上限又会被一个多项式限制住。这个多项式跟break point k有关。因此只要我们找到了一线曙光k，最终我们的growth function就一定会被多项式bound住。

值得说明的是，其实我们可以证明bounding function的上限其实是等于\(\sum_{i=0}^{k-1}{N \choose i}\)，但是用到的证明技巧可能比较难。

现在我们来看看以前看过的例子，看看我们总结出的关于bounding function的上限的定理是不是适用：

我们最关注的其实是是我们写不出growth function的2D perceptron，但是我们现在能够写出它bounding function的上限了。这说明，我们可以仅仅通过一个break point就能bound住growth function。

A Pictorial Proof

那我们现在有了growth function是像多项式一样地增长，我们能不能就用它替换finite bin的Hoeffding中的M，事情即解决了呢？

可惜，事情并没有这么简单。

我们想要的是： \[ P[|E_{in}(g) - E_{out}(g)| > \epsilon] \le 2*m_{H}(N)exp(-2\epsilon^2N) \] 但实际上，当N够大的时候，我们能证明的是： \[ P[|E_{in}(g) - E_{out}(g)| > \epsilon] \le 2*2*m_{H}(2N)exp(-2\frac{1}{16}\epsilon^2N) \] 这个证明非常的technical，但是其中的有些技巧和我们将来的一些讨论都还蛮有关系的，或用到我们之前的某些证明技巧。所以我们会简略地讲一些，这些常数是怎么出现的。但是不会讨论最底层的那些证明是什么样子的。

第一个步骤，用\(E_{in}’\)来代替\(E_{out}\)：

由于H是无限的，h稍微不同，就会造成\(E_{out}(h)\)的不同。因此，我们要先把\(E_{out}(h)\)替换掉。为了估计\(E_{out}(h)\)，我们抽样一个大小为N的验证数据集D’来计算\(E_{in}'\)，也许我们的\(E_{in}'\)就可以取代\(E_{out}\)。

下面这个图表示了\(E_{in}\)和\(E_{in}'\)的概率分布：

从中我们可以看到，如果坏事情发生，也就是\(E_{in}\)和\(E_{out}\)差的很远，那么有很大几率（大于\(\frac{1}{2}\)）的几率，\(E_{in}\)和\(E_{in}'\)也差得很远。

这件事情拿来用之后，就有：

做完这一步之后，我们就顺利地换掉了\(E_{out}\)。我们通常把D’称为ghost data，因为它其实是不存在的，只是我们想象如果能够再抽一次data。

第二个步骤是，将H中的h分类：

现在我们已经有了在D上做出来的\(E_{in}\)，和在ghost data D’上做出来的\(E_{in}'\)之后，现在我们可以请我们的\(m_{H}\)出场了。 可想而知，如果不同的h在D和D‘上表现一样，那么我们便可以认为它们是一类hypothesis。因此，无限大的H变成了\(|H(\mathbf{x}_1, \ldots, \mathbf{x}_N, \mathbf{x}_1', \ldots, \mathbf{x}_N')|\)种。于是，我们便可以在这\(m_{H}(2N)\)种hypothesis上使用union bound。下面是对应于这段推导的一个示意图：

使用这个将H中的hypothesis分类的技巧之后，有：

第三个步骤是，使用Hoeffding定理：

现在我们关注到对固定的hypothesis，两次sampling的差别。
考虑一个有2N个数据点的罐子，两次sample每次N个，可以认为是一次sample N个，留下剩下的N个，比较他们的差别；也可以认为是sample N个，比较它和所有的差别： \[ |E_{in}-E_{in}'| > \frac{\epsilon}{2} \Leftrightarrow |E_{in}-\frac{E_{in}+E_{in}'}{2}| > \frac{\epsilon}{4}\]

于是我们就可以用Hoeffding来衡量局部和整体的差别。这里与general的Hoeffding唯一的不同就是，这里的罐子更小，我们拿出来的弹珠不会再放回去，因此罐子中橘色/绿色弹珠的比例是在变的。这种不一样的Hoeffding叫做Hoeffding without replacement。

使用了这个Hoeffding without replacement之后，我们有：

总结来说，我们证明了机器学习中一个非常重要的定理VC bound(Vapnik-Chervonenkis bound)，其中V和C分别是机器学习领域两个非常重要的人物，他们推导出来了这个bound： \[P[|E_{in}(h) - E_{out}(h)| > \epsilon] \le 4m_H(2N)exp(-\frac{1}{8}\epsilon^2N)\]

推出VC bound的三个步骤是：

• 用\(E_{in}'\)来代替\(E_{out}\)（产生了bound右面，最前面的4）
• 把H中的hypothesis分门别类（产生了bound右面，\(m_{H}\)中的2N）
• 使用了Hoeffding without replacement（产生了bound右面，括号中的\(\frac{1}{8}\)）

于是，我们现在解决了2D perceptron的问题。我们知道它的break point是4，所以它的growth function增长地不会比\(N^3\)快。当N够大的时候，坏事发生的几率就很小，因此当A选择\(E_{in}\)最小的h作为g，那么它的\(E_{out}\)大概也是最小的。也就是说，数据够多时，2D perceptron是能够有学习的效果的。

本节的测验题是： 我们可以看到，即使是在有10000个训练数据的情况下，坏事发生的几率也不是特别小（0.289）。这是因为，我们在推VC bound的过程中，用了很多近似，导致这个bound不是很紧。那既然这样，我们为什么还要花这么多力气推导它呢？且看下回分解。

Summary

下节课我们会讨论，在实践中如何使用break point。