*大学林轩田《机器学习基石》学习笔记第6讲——Theory of Generalization

上一节课我们使用了dichotomy来替代hypothesis set的个数，引入了mH(N)的概念，同时也提出了growth function的break point来表征其增长速度。上一节课还预测了针对2D perceptron 的成长函数mH(N)是多项式的猜想，那么这一课就一起来验证一下。
一、Restriction of Break Point

• 这是上一节课提到的四种不同growth function的最小break point值；
• 我们关心的是当最小break point k出现之后，那么之后的k+1、k+2的情况会使怎样的？

• 这个例子设定某一个一般的growth function的break point为2，那么当N=2或者3或者更大的时候，mH(N)最大会是多少？
• 当N=1时，因为没到break point，所以这个点是能够被shatter的，这里的shatter是指能够找到2^N个dichotomy；
• 当N=2时，因为到了break point，因此最多只能找到<2^2（<4）个dichotomy，即最多三个；
• 当N=3时，通过上一条，任意两个点是没有办法被shatter的，即最多只能有3个dichotomy，经过推演，mH(3)=4；
• 这时候我们就发现了随着N的增加（即远远大于break point），mH(N)的增长会被大大地限制住。

二、Bounding Function: Basic Cases

• 这里引入一个新的概念Bonding Function B(N,k)，它的含义在于当break point=k时，mH(N)的最大的可能值，即上限；
• 那么问题就可以转化为B(N,k)是否是多项式形式了。

- 这里列出了不同最小break point k值所对应的B(N,k)的值；
- 当k=1时，所有B(N,1)=1；
- 当N小于k时，都是可以shatter的，即B(N,k)=2^N；
- 当N=k时，B(N,k)=2^N-1，即最大不能超过2^N；
- 当N>k时，请往后看。

三、Bounding Function: Inductive Cases
我们猜测B(N,k)在N>k时是多项式形式，那么如果能找到B(N,k)与B(x,y)等之间的关系，或许我们就可以得出一些一般性的结论。
接下来我们以B(4,3)为例，看看能否构建这样的一些关系。

1.首先，列举所有B(4,3)dichotomy的可能性，共11组：

• 同时对11组dichotomy分成两组：
• orange：x1,x2和x3成对出现，分别对应着x4的o/x；
• purple：x1,x2,x3都不成对出现，每组都只有自己一个可能；

2.去掉x4，单独分析x1、x2、x3。

• 令B(4,3)=2α+β，2α为orange组的的数量，β为purple组的数量；
• 由于B(4,3)不能被3 shatter，那么很显然(x1，x2，x3)也不能被3 shatter，即α+β≤B(3,3)；

3.单独研究α：

• 现在我们单独研究一下orange组：
• α首先因为不能被3 shatter，同时α和x4是成对存在的，那么从这里可以推论出α同时也不能被2 shatter；
• 因为如果α能被2 shatter，那么再加上x4的成对出现，可以推论出α同时也能被3 shatter，这与上面矛盾；
• 因此可以得出α≤B(3,2)；

4.归纳总结：


- 由推论我们得到B(4,3)与B(3,3)和B(3,2)的关系，并且进一步推广到B(N,k)如上；
- 这样我们就把图标中的其他空位以最大值形式填入；

四、Bounding Function: Inductive Cases
这部分确实理解不是很好，就暂时把结果放进来吧。经过推导证明得到：

五、总结

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