Tips：所有没有进行解释说明的符号含义均参照之前的章节Lec～
上一节介绍了级联上限存在过分估计的问题，我们欲寻求一个多项式mH（N）取代M，并给出了成长函数、break point的定义，这节将证明如果存在break point ，成长函数会是多项式型的。
Lec 6：Theory of Generalization
先回顾一下四种成长函数，成长函数mH（N）代表dichotomies最大数量：
1、Restrict of Break Point
先通过一个小栗子感受一下break point会对dichotomies的数量有怎么样的限制？
在k=2的情况下：
N = 1：显然mH（N）=2；
N = 2：mH（N）＜4，所以最多有3个dichotomies；
N = 3：k = 2代表不能shatter任意两个data，我们分步骤来看，
1）显然，只有1个dichotomy时，或有2个dichotomies时，，或有3个dichotomies时，一定不会shatter任意两个data：
2）但是，当有4个dichotomies时，就可能会shatter两个data，如下图中x2和x3 shattered（可以这样理解，shatter就是x2和x3所有可能的二元组合都能出现）
不过也会存在4个dichotomies时不shatter两个data的情况，如：
3）接着上面4个dichotomies不shatter的情况，继续加入dichotomy，看5个dichotomies时会怎样？x1、x2、x3一共有8种二元组合，所以此时5个dichotomies存在3种情况，发现分别都会shatter：
所以，在N=3，k=2时，最多会有4个dichotomies.
N = 2时，最多有3个，比4小一点；N = 3时，最多有4个，比8小的多一点！
似乎当N＞k时，break point k 会限制mH（N）最大值的大小！
所以如果证明存在k限制的mH（N）最大值≤poly（N）就可以说明mH（N）是多项式型的。
2、Bounding Function：basic cases
定义一个新的函数B（N，K），maximum possible mH（N）when break point = k.
bounding function 与 H 的细节无关，只需要知道k.（个人是这样理解的，dichotomies的数量其实就是二元组合的种类，h不同时，可能得到的dichotomies会有所不同，但是这里我们是表示最大的mH（N），所以可以抛开H的细节，专注于二元组合的最大值，即只需要知道k）例如B（N，3）可以bound住positive intervals（k=3），也可以bound住1D perceptron（k = 3）。
所以我们的new goal 是证明 B（N，k）≤ poly（N）？
先列出我们已经知道的B（N，k）的值。首先由上节已知（2,2）=3，（3,2）=4；
然后 k＞N时，会shatter，则B（N，k）= 2的N次方；
还有就是对角线上面的值，N=k时，（2，2）取3时是选了一个比2的N次方小1的值（一定比2的N次方小，我们挑了一个比2的N次方小的数中最大的一个），其他对角值也如此取；
最后是第一列的值，一定都是1.至此，我们得到了B（N，k）表上一多半的值！其他值继续看下一节。
3、Bounding Function：inductive cases
我们要补全上一节的表。
先考虑B（4,3）这一格。猜测：B（4，3）只是比B（3，3）多了一个点，也许它们之间有着什么联系？！
先给出B（4,3）的结果（这个结果完全可以用代码全遍历一遍得出），结果是11：
下面看如何把B（4,3）reduce成B（3,3）？
先重新排列B（4,3）的dichotomies，如下图所示。可以看出橘色部分的x1、x2、x3是“成双成对”存在的，紫色部分是形单影只的。可以表示B（4,3） = 11 = 2 α + β .
下面就是见证奇迹的时刻！
遮掉x4，只剩下x1、x2、x3，在(x1,x2,x3)上会有α + β个dichotomies，B（4,3）任意3个点都不会shatter，那么α + β个dichotomies也就不会shatter x1、x2、x3，所以 α + β ≤ B（3,3）
只看x1 x2 x3的橘色部分，应该任意两个点不能shatter，why？假设此时 x1 x2 shatter，那么x1 x2 与 x4组合起来就会存在3个点shatter，就不满足B（4,3），所以α不能shatter橘色部分的任意两个点，可以得出 α ≤ B（3,2）
综合上述两个结论，可以得出 B（4,3）= 2α + β = （α + β）+ α ≤ B（3,3）+ B（3,2），这样我们就得到了Bounding Function的upper bound ！（回想一下：从成长函数，到成长函数的上限，再到上限的上限，哈哈哈哈~~~）
给出一个结论：
B（N，k）的最高次项是k-1次的，这个结论可以通过数学归纳法inductive证明。实际上≤可以是=，这需要更复杂的数学证明，这里不给出，我们只需要明白B（N，k）会被poly（N）bound住 if break point exist :)
4、VC bound
已经证明了mH（N）的上限是多项式，那我们是不是就可以替换M了呢？
并没有这么简单，实际上会是下图这样的，多了一些常数：
这个的证明很有技巧性，我们不深入探究，只介绍这几个常数的含义。（首先承认这部分笔者看的也不是很懂，希望得到大家指点~互相学习）
step 1：replace Eout by Ein '
有了上节的bound可以知道Ein（h）是有限多个，但是Eout（h）是无限多的。怎么办？之前提过采样一个大小为Ｎ的verification set D ' 去估计Eout，称为Ein ' 。
由上图分布可以得出，Ein ' 和Ein 离得远的概率是 Ein和Eout离得远的概率的一半多，因此得到下式，右侧式子的ε/2的1/2是数学上更强的约束。
step 2：decompose H by kind
上面的式子是在一个h上的结论，现在换成kind得到在H上的结论：
插播一条旧结论：
这里有一组很形象的图展示了union bound on hypothesis 和 union bound on kind的差别，第一张图是霍夫丁不等式说明对一个固定的h来说bad data的概率很小，对H中的每一个h使用union bound 会得到第二张图，花花绿绿的很多圈就代表了bad data没有重叠，我们后来进行了分类kind，再对kind进行union bound就得到第三张图！值得体悟一下~
step 3：use hoeffding without replacement
现在不是无限多的小球 in bin，而是2N个小球，这是不放回的霍夫丁，但是结论和原来的霍夫丁还是一样的。这时计算的不是Ein和Eout的差，而是Ein和均值的差，均值即（Ein + Ein '）/2，由|Ein - Ein'|＞ε/2可以得到
至此，得到：
其实这就是著名的Vapnik-Chervonenkis(VC) bound！！
所以现在就可以真正说learning with 2D perceptrons（break point is 4，mH（N）的最高次是3） is feasible！
有木有长舒一口气的感觉呢？！下一章告诉你力气不会白费！
