6. Theory of Generalization

上一节课，主要探讨了 $M$M 的数值大小对机器学习的影响。如果 $M$M 很大，就不能保证机器学习有很好的泛化能力，所以问题转换为验证 $M$M 有限，即最好按照多项式成长。然后通过引入了成长函数和dichotomy以及break point的概念，提出2D perceptrons的成长函数是多项式级别的猜想。这就是本节课将要深入探讨和证明的内容。

6.1 Restriction of Break Point

突破点的限制。先回顾上一章中提到的两个概念。

成长函数（growth function） $m_H(N)$mH​(N) 的定义：假设空间在N个样本点上能产生的最大二分（dichotomy）数量，其中二分是样本点在二元分类情况下的排列组合。

突破点（break point）：不能满足完全分类情形的样本点个数。完全二分类（shattered）是可分出 $2^N$2N 种二分类（dichotomy）的情形。

四种成长函数与break point的关系：

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

假设N = 3，推导过程如下：

• 如图(a)表示在3个样本点时随意选择一种二分的情况，这种分类没有问题，不会违反任意两个样本点出现4种不同的二分类情况（因为突破点是2）；
• 如图(b)表示在(a)的基础上，添加不与之前重复的一种二分类，出现了2种不冲突的二分类，此时也没有问题，不会违反任意两个样本点出现4种不同的二分类情况；
• 如图©表示在(b)的基础上，再添加不与之前重复的一种二分类，出现了3种不冲突的二分类，此时也没有问题，不会违反任意两个样本点出现四种不同的二分类情况；
• 如图(d)表示在©的基础上，再添加不与之前重复的一种二分类，问题出现了，样本 $x_2,x_3$x2​,x3​ 出现了4种不同的二分情况，这与已知条件中k=2矛盾（最多只能出现3种二分类），因此将其删去。
• 如图(e)表示在©的基础上，再添加不与之前重复的一种二分类，此时也没有问题，不会违反任意两个样本点出现四种不同的二分类情况；
• 如图(f)表示在(e)的基础上，再添加不与之前重复的一种二分类，问题又出现了，样本 $x_1,x_3$x1​,x3​ 出现了4种不同的二分情况，这与已知条件中k=2矛盾（最多只能出现3种二分类），因此将其删去。

突破点 k = 2，样本点 N = 3 时，最多只能有4种二分类情况，而 $4 \ll 2^3$4≪23。

从上述情形，可以做一个猜想，成长函数 $m_H(N)\le$mH​(N)≤ 某个与突破点k有关的二次项，如果可以证明这一结论，即能寻找到一个可以取代无限大M的数值，同理即能公式 $P_D[BAD D]\le 2 \cdot M \cdot exp(-2\epsilon^2N)$PD​[BADD]≤2⋅M⋅exp(−2ϵ2N) 在假设空间为无限大时也是成立，即机器是可以学习的。

假设突破点 k = 1 ，在样本数为3时，最大的二分类个数是多少？答案是1，可以想象，在样本为1时，只有一种分类情形，假设这种情形是正，则以后所有样本也为正，才能满足上述条件，所以样本N不论为多少，其最大二分类数都是1。

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

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

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

6.2 Bounding Function- Basic Cases

上限函数的基本情形。

现在，引入一个新的函数：bounding function，$B(N,k)$B(N,k)。Bound Function：当最小突破点为k时，成长函数 $m_H(N)$mH​(N) 最大值的函数表示。也就是说B(N,k)是 $m_H(N)$mH​(N) 的上界，对应 $m_H(N)$mH​(N) 最多有多少种dichotomy。此函数将成长函数从各种假设空间的关系中解放出来，不用再去关心具体的假设，只需了解此假设的突破点，突破点相同的假设视为一类，抽象化成长函数与假设的关系。那么，新的目标就是证明：$B(N,k) \le poly(N)$B(N,k)≤poly(N)
这里值得一提的是，B(N,k)的引入不考虑是1D postive intrervals问题还是2D perceptrons问题，而只关心成长函数 $m_H(N)$mH​(N) 的上界是多少，从而简化了问题的复杂度。

二分类的个数或者称之为成长函数 $m_H(N)$mH​(N) 说白了就是二元（在图中表示为"×"或者"○"的符号）符号在长度为N的情况下的排列组合（每个不同的排列代表一个二分类，每种二分类可看做一个向量）个数。

提出上限函数的好处在于，可以不用关心到底使用的是何种假设空间，只需要知道突破点便可以得到一个上限函数来对成长函数做约束。

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

• 当k=1时，B(N,1)恒为1；

• 当N < k时，根据break point的定义，易知 $B(N,k) =2^N$B(N,k)=2N。

• 当N = k时，此时N是第一次出现不能被shatter的值，所以最多只能有 $2^N -1$2N−1 个dichotomies，则 $B(N,k) =2^N - 1$B(N,k)=2N−1。原因是突破点代表不能完全二分类 $2^N$2N 的情况，因此在此情况下最大的二分类数可以是 $2^N - 1$2N−1。在这条斜线的右上角区域所有的点都满足完全二分类的，因此值为 $2^N$2N。
  
  对于最常见的N>k的情况比较复杂，推导过程下一小节再详细介绍。

6.3 Bounding Function- Inductive Cases

上限函数的归纳情形。

从已有的数据上可以看出一个似乎是正确的结论：每个值等于它正上方与左上方的值相加。公式为：$B(N,k)=B(N-1,k)+B(N-1,k-1)$B(N,k)=B(N−1,k)+B(N−1,k−1)。

N > k的情况较为复杂，下面给出推导过程：

以B(4,3)为例，首先想能否构建B(4,3)与B(3,x)之间的关系。

首先，把B(4,3)所有情况写下来，共有11组。也就是说再加一种dichotomy，任意三点都能被shattered，11是极限。

对这11种dichotomy分组，目前分成两组，分别是orange和purple，orange的特点是，$x_1,x_2$x1​,x2​和$x_3$x3​是一致的，$x_4$x4​ 是成对出现的，例如01和05，02和08等；purple则是单一的，$x_1,x_2,x_3$x1​,x2​,x3​都不同，如06,07,09三组。

注意 $k=3$k=3 ，意味着在样本点为3时，不能满足完全二分的情形。需要观察在样本数为3时，这11种分类会有何变化，不妨假设这三个样本是 $x_1,x_2,x_3$x1​,x2​,x3​ ，于是只剩下图中所示的7种二分类情形。

将原本两两成对出现的orange去掉 $x_4$x4​列后，去重得到4个不同的vector并成为 $\alpha$α，即有 $\alpha$α 对二分类， $2\alpha$2α种二分类，相应的purple为$\beta$β。那么 $B(4,3) = 2 \alpha + \beta$B(4,3)=2α+β，这个是直接转化。已知 $N=4,k=3$N=4,k=3 ，由定义，B(4,3)是不能允许任意三点shatter的，所以由$\alpha$α和$\beta$β构成的所有3点组合也不能 shattered（alpha经过去重），因此，一定满足式$\alpha + \beta \le B(3,3)$α+β≤B(3,3)。

另一方面，由于$\alpha$α中 $x_4$x4​ 是成对存在的，且是不能被任意三点shatter的，则能推导出$\alpha$α是不能被任意两点shatter的。这是因为，如果是不能被任意两点shatter，而 $x_4$x4​ 又是成对存在的，那么 $x_1、x_2、x_3、x_4$x1​、x2​、x3​、x4​ 组成的 $\alpha$α 必然能被三个点shatter。这就违背了条件的设定。这个地方的推导非常巧妙，也解释了为什么会这样分组。

使用反证法证明。假设$x_1、x_2、x_3$x1​、x2​、x3​三个样本在如下图所示的4种二分类情况下，满足任意两个样本都可完全二分类。将$x_1、x_2、x_3$x1​、x2​、x3​中任意两列取出，同之前被删除的$x_4$x4​ 列相结合，一定可得到一种三个样本都满足完全二分类的情形（因为不论是哪两列与$x_4$x4​相结合都会得到8种二分类，每一行二分类都对应两个不同标记的$x_4$x4​，因此为8种。且两列四行的二分类是全完二分的，在此基础上加上不同属性的列，应该也不会重复，因此一定也是全完二分的）。但是此结论和已知任意三个样本不能完全二分冲突了，因此假设不成立，即在下图中一定存在某两个样本点不能完全二分的情况，因此得到的结论是 $\alpha \le B(3,2)$α≤B(3,2)。

由此得出B(4,3)与B(3,x)的关系为：

最后，推导出一般公式为：

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

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

上述不等式的右边是最高阶为k-1的N多项式，也就是说成长函数的上界B(N,K)的上界满足多项式分布 $poly(N)$poly(N)，这就是想要得到的结果。

首先需要预先了解组合中的一个定理，$C_N^k = C_{N-1}^k + C_{N-1}^{k-1}$CNk​=CN−1k​+CN−1k−1​。很容易证明 $k=1$k=1的情况下，上图中公式 $B(N,k) \le \sum_{i=0}^{k}C_{N}^i$B(N,k)≤∑i=0k​CNi​ 成立。

假设$B(N-1,k) \le \sum_{i=0}^{k-1}C_{N-1}^i$B(N−1,k)≤∑i=0k−1​CN−1i​成立；则在 $k \ge 2$k≥2的情况下有：

$B(N-1,k-1) \le \sum_{i=0}^{k-2}C_{N-1}^i=\sum_{i=1}^{k-1}C_{N-1}^{i-1}$B(N−1,k−1)≤∑i=0k−2​CN−1i​=∑i=1k−1​CN−1i−1​；则有：

$B(N,k) \le B(N-1,k)+B(N-1,k-1)$B(N,k)≤B(N−1,k)+B(N−1,k−1)

$\le \sum_{i=0}^{k-1}C_{N-1}^i + \sum_{i=0}^{k-2}C_{N-1}^{i}$≤∑i=0k−1​CN−1i​+∑i=0k−2​CN−1i​

$= \sum_{i=0}^{k-1}C_{N-1}^i + \sum_{i=1}^{k-1}C_{N-1}^{i-1}$=∑i=0k−1​CN−1i​+∑i=1k−1​CN−1i−1​

$= C_{N-1}^0 + \sum_{i=1}^{k-1}(C_{N-1}^i +C_{N-1}^i)$=CN−10​+∑i=1k−1​(CN−1i​+CN−1i​)

$= 1 + \sum_{i=1}^{k-1}C_{N}^i$=1+∑i=1k−1​CNi​

$= C_N^0 + \sum_{i=1}^{k-1}C_{N-1}^i$=CN0​+∑i=1k−1​CN−1i​

$= \sum_{i=0}^{k-1}C_{N-1}^i$=∑i=0k−1​CN−1i​

这一结果意味着：成长函数 $m_H(N)$mH​(N) 的上限函数 $B(N,k)$B(N,k) 的上限为 $N^{k-1}$Nk−1。

得到了的上界B(N,K)的上界满足多项式分布 $poly(N)$poly(N)后，回过头来看之前介绍的几种类型的成长函数与break point的关系：

得到的结论是，对于2D perceptrons，break point为k=4， 成长函数的的上界是 $N^{k-1}$Nk−1。推广一下，也就是说，如果能找到一个模型的break point，且是有限大的，那么就能推断出其成长函数有界。

6.4 A Pictorial Proof

一种形象化的证明。

在这一小节之前，说明一下，面对这一小节时，因为林老师本身也没打算将这个证明的详细流程全部给出，我觉得原因有几个：一是难度很高，即使全部讲解能听懂的估计也没几个；二是思想更重要，只需要知道它用到了什么原理去证明这个问题，这比了解这枯燥的数学推导更重要；三是结论比求解过程更重要。

在讲述之前几章时，一直以为只需要证明出在假设函数为无限多的情况下，寻找成长函数$m_H(N)$mH​(N) 作为假设空间个数的上限，直接使用该上限去取代原本霍夫丁不等式中的M便可得出结论，即在$E_{in}(g)$Ein​(g) 接近0时，$E_{out}(g)$Eout​(g) 也接近0，也就是机器是可以学习的。实际与这一结果类似，但是稍有偏差，在霍夫丁不等式（如公式6-13所示）中多出一些常量。

比较两个公式，实际结论比猜想的公式，在不等式右侧三个不同位置多了三个常数。下面按照先后顺序，分三步简单说明这些变化的原因。可参考这位博主的证明：

第一步：$E_{in}(g)$Ein​(g) 取代 $E_{out}(g)$Eout​(g)



第三步：使用无取回的霍夫丁

还是用小球和罐子的那个例子解释，罐子中不再是无限多个小球，而是2N个小球，选择N个小球而留下另外N个，可以通过下图公式得出如下结论。

最终，通过引入成长函数，得到了一个在机器学习领域很著名的理论——V-C上界制（Vapnik-Chervonenkis bound）。

对于2D perceptrons，它的break point是4，那么成长函数 $m_H(N) \approx O(N^3)$mH​(N)≈O(N3)。可以使用这个VC bound来说明在样本N足够大时候，发生坏事的情况很少，即选择一个在样本中错误率很小的g，可以得出其在整个数据上错误率也很低的结论，说明机器学习是可能的。

Summary

本节课我们主要介绍了只要存在break point，那么其成长函数就满足$poly(N)$poly(N)。推导过程是先引入成长函数 $m_H(N)$mH​(N)的的上界 $B(N,k)$B(N,k)，$B(N,k)$B(N,k)的上界是N的k-1阶多项式，从而得到$m_H(N)$mH​(N)的上界就是N的k-1阶多项式。然后，通过简单的三步证明，将代入了Hoffding不等式中，推导出了Vapnik-Chervonenkis(VC)bound，最终证明了只要break point存在，那么机器学习就是可行的。

https://www.cnblogs.com/ymingjingr/p/4290983.html
https://github.com/RedstoneWill/HsuanTienLin_MachineLearning