6-Theory of Generalization

这节课的重点是证明growth function可以是polynomial的并且可以代替M

还是以lecture 5 的Puzzle为例子， 来证明在break point = k 的基础上， 对于N个point可以存在的pattern。

首先， 将数据点划分为[x1, x2, ... x_n-1]，[x_n]两个部分， 然后讨论x_n 只能为+1或者-1的情况S1， 或者x_n既可以为+1也可以为-1的情况S2.

首先， 在这个部分， 不需要考虑x_n 是多少， 仍然认为break point是k， 为什么不是=号呢， 因为我们不清楚这样划分就是maximum number， 只需要得到其上界即可。

第二个部分， S2+, S2-的前N-1个点是一样的， 所以单独考虑其中一个情况即可， 在这里， 因为x_n是+1, -1 都有， 所以前N-1的点的break point只能是k-1， 否则再考虑上x_n的话就违背了break point是k了。

总结起来。可见， 上个lecture的所有pattern是[000, 001, 010, 100]， B(N-1, k-1)可认为就是000或者001， B(N-1, k)就是另外的三种情况了。

bounded。 我们得到了growth function的上界， 并且在induction step中证明了它。 这个上界有个很好的性质， 就是它是polynomial， polynomial意味着hoeffding不等式的右边的值是极小的。

因此， 只要给定N个点， 并且指明模型的break point是多少， 我们就可以计算出这个模型可以判别的这N个点的模式是多少。如之前提到的三个example， 前两个我们知道具体的growth function的值， 但是第三个我们没有得到显式的表达， 通过以上的结论， 我们仍然可以推算出growth function的值。

OK, 现在回到Hoeffding 不等式， 我们希望用growth function取代本来的M， 详细的步骤可能比较冗长， 但主要的步骤总结如下。

图中的彩色区域指的是Error的区域。 对于一个假设h， Hoeffding的bound非常严格，只有一片； 引申到一个Hypothesis Set H， Union Bound假设它们造成的错误例子是no overlap的， 因此彩色区域几乎充满整个空间， 而VC bound考虑了overlap， 表现为一族， 使得Hoeffding 不等式有意义。 VC的idea是假设每个点可能被着色100次， 因此到最后显示的是着色深的点， 而其它点被忽略， 这与growth function来代替M的思路是一致的。

Putting all together，就得到了VC不等式(上边的式子是错的）