前几节课着重介绍了机器能够学习的条件并做了详细的推导和解释。机器能够学习必须满足两个条件：
- 假设空间H的Size M是有限的，即当N足够大的时候，那么对于假设空间中任意一个假设g，Eout≈Ein。
- 利用算法A从假设空间H中，挑选一个g，使Ein(g)≈0，则Eout≈0。
这两个条件，正好对应着test和trian两个过程。train的目的是使损失期望Ein(g)≈0；test的目的是使将算法用到新的样本时的损失期望也尽可能小，即Eout≈0。
正因为如此，上次课引入了break point，并推导出只要break point存在，则M有上界，一定存在Eout≈Ein。
本次笔记主要介绍VC Dimension的概念。同时也是总结VC Dimension与Ein(g)≈0，Eout≈0，Model Complexity Penalty（下面会讲到）的关系。
一、Definition of VC Dimension
首先，我们知道如果一个假设空间H有break point k，那么它的成长函数是有界的，它的上界称为Bound function。根据数学归纳法，Bound function也是有界的，且上界为N的k-1次方。从下面的表格可以看出，N的k-1次方比B(N,k)松弛很多。
下面介绍一个新的名词：VC Dimension。VC Dimension就是某假设集H能够shatter的最多inputs的个数，即最大完全正确的分类能力。（注意，只要存在一种分布的inputs能够正确分类也满足）。
shatter的英文意思是“粉碎”，也就是说对于inputs的所有情况都能列举出来。例如对N个输入，如果能够将2的N次方种情况都列出来，则称该N个输入能够被假设集H shatter。
根据之前break point的定义：假设集不能被shatter任何分布类型的inputs的最少个数。则VC Dimension等于break point的个数减一。
二、VC Dimension of Perceptrons
三、Physical Intuition VC Dimension
上节公式中W又名features，即自由度。自由度是可以任意调节的，如同上图中的旋钮一样，可以调节。VC Dimension代表了假设空间的分类能力，即反映了H的自由度，产生dichotomy的数量，也就等于features的个数，但也不是绝对的。
四、Interpreting VC Dimension
下面，我们将更深入地探讨VC Dimension的意义。首先，把VC Bound重新写到这里：
所以，为了得到最小的Eout，不能一味地增大dvc以减小Ein，因为Ein太小的时候，模型复杂度会增加，造成Eout变大。也就是说，选择合适的dvc，选择的features个数要合适。
下面介绍一个概念：样本复杂度（Sample Complexity）。如果选定dvc，样本数据D选择多少合适呢？通过下面一个例子可以帮助我们理解：
通过计算得到N=29300，刚好满足δ=0.1的条件。N大约是dvc的10000倍。这个数值太大了，实际中往往不需要这么多的样本数量，大概只需要dvc的10倍就够了。N的理论值之所以这么大是因为VC Bound 过于宽松了，我们得到的是一个比实际大得多的上界。
值得一提的是，VC Bound是比较宽松的，而如何收紧它却不是那么容易，这也是机器学习的一大难题。但是，令人欣慰的一点是，VC Bound基本上对所有模型的宽松程度是基本一致的，所以，不同模型之间还是可以横向比较。从而，VC Bound宽松对机器学习的可行性还是没有太大影响。
五、总结
本节课主要介绍了VC Dimension的概念就是最大的non-break point。然后，我们得到了Perceptrons在d维度下的VC Dimension是d+1。接着，我们在物理意义上，将dvc与自由度联系起来。最终得出结论dvc不能过大也不能过小。选取合适的值，才能让Eout足够小，使假设空间H具有良好的泛化能力。
