【机器学习基石笔记六】------Theory of Generalization（一般化理论---举一反三）
第五节主要讨论M的数值大小对机器学习的影响。如果M很大，那么就不能保证机器学习有很好的泛化能力，所以问题就转化为验证M有限，即最好按照多项式成长。然后通过引入了成长函数和dichotomy以及break point的概念。提出2D perceptrons的成长函数
是多项式级别的猜想。以下探讨这个多项式的形成。
Restriction of Break Point
之前介绍的四种成长函数与break point之间的关系为：
计算k=2的时候，不同的N值成长函数是多少？N=1时，
=2；当N=2时，由break point=2知任意两点都不能被shattered（即不能分解为
种dichotomies），
最大值只能是3；当N=3时，简单绘图分析可得
=4，即最多只有4种dichotomy。
可以发现，当N>k时，break point限制了值的大小，也就是说影响成长函数
的因素主要有两个：
- 抽样数据集N
- break point k（这个变量确定了假设的类型）
那么，给定N和k，就能够证明的最大值的上界是多项式的，则根据hoeffding不等式，使用
代替M，得到机器学习是可行的。因此，证明了
的上界是poly(N)，是我们的目标。
Bounding Function：Basic Cases
界限函数bounding function B(N,k)：当break point=k时可能的的最大值。
求解B(N,k)的过程为：
当k=1时，B(N,1)的值恒为1；
当N<k时，根据break point的定义，得到B(N,k)=；
当N=k时，此时N是第一个出现不能被shatter的值，所以最多只能有，则
；
Bounding Function：Inductive Cases
N>k时，计算bounding function比较复杂，其推导过程如下，以B(4,3)为例，首先试着查看能否构建B(4,3)与B(3,x)之间的关系。
首先，将B(4,3)的所有情况写下来，共有11组，将其分为两种数据橙色（成对部分）与紫色（单一部分）部分，橙色部分是有三个点相同，另一个点有两种可能（成对），紫色部分不满足橙色的条件。
可以将B(4,3)写作，B(4,3)表示4个点中任何三个点不能shatter，所以dichotomies on (
)也不能shatter，所以
。
下面我们去掉并只查看橙色的部分，即
的四种组合，发现其中任意两个点都不能shatter，以此说明
；
综合以上，得出B(4,3)的推导如下：
推广到B(N,k)的推导为：
根据得出的上限公式填入表中：
我们称B(N，k)是上限的上限，下面来证明一个不等式，这个不等式右边的最高次幂是k-1，即满足多项式poly(N)，这是我们想要得到的结果。
所以，我们现在有了使用上界和递推公式得到的简单的推导，对于固定的k，B(N，k)的上限为poly(N)所限，如果break point存在成长函数为poly(N)。
使用上限函数检测之前得出的成长函数值，发现都满足；所以，我们得出的结论是对于2D perceptrons，break point为k=4，的上界为
。推广一下，也就是如果能找到一个模型的break point，并且是有限大的，那么就可以推断出成长函数
有界。
A pictorial Proof
我们已经知道成长函数的上界是poly(N)，如果能将代替M代入到hoeffding不等式中，就能得到
的结论：
实际上并非简单的替换就可以，正确的表达式是：
其中加入了一些常数，证明分为三个步骤：
最终，通过引入成长函数，得到一个新不等式，成为Vapnik-Chervonenkis(VC) bound；
对于2D perceptrons，它的break point是4，那么成长函数，所以，我们可以说2D perceptrons是可以进行机器学习的，只要找到hypothesis 使得
，就能保证
。