机器学习基石第七讲主要介绍了VC dimension，笔记整理在下面。

Definition of VC Dimension

上一讲我们找到了B(N,k)的上限，拿它和$N^{k-1}$做一个比较，发现当N够大时，前者比后者小得多。

上一讲我们提到了VC bound：在dataset上，H中任意一个hypothesis发生坏事情的概率不超过一个很小很小的定值。

这时可以说机器学习算法选择的g，其$E{in}$和$E{out}$相差很大的几率很小。

下面开始介绍VC Dimension，其是最大的non-break point的那个点，所以有$d_{vc}='minimum' -1$。那么当$N \leq d_{vc}$时，存在某个数据集可能会被某个hypothesis给shatter掉，当然不是一定；当$N > d_{vc}$时，数据集一定不会被H中的任一个hypothesis给shatter。

下面是四个例子的vc dimension。

前面我们说当break point露出一线曙光的时候有好的hypothesis，现在则变成了是有好的vc dimension的时候。

本小节测试：

VC Dimension of Perceptrons

现在回到课程开始时介绍的2D PLA算法。一方面，假设训练数据集线性可分，PLA算法就可以收敛，经过T次（足够大）迭代后就能够得到一个g有$E_{in}=0$。另一方面，数据集服从某一未知的分布P，存在一未知的目标f，此时的$d_{vc}=3$，那么当N足够大时，就有$E_{out}(g) \approx E_{in}(g)$。将这两条线融合在一起，我们就有了$E_{out}(g) \approx 0$，从而说明了学习是可行。

现在我们尝试解决多维度的问题。前面知道了1D perceptron的$d_{vc}=2$，2D perceptrons的$d_{vc}=3$，我们猜测d-D perceptrons的$d_{vc} \stackrel{?}{=} d+1$。要证明它只需要两步：第一步，证明$d_{vc} \geq d+1$；第二步，证明$d_{vc} \leq d+1$。

证明之前先来一个小测试：

先来证明$d_{vc} \geq d+1$，我们只需证明存在d+1组输入数据能被某一个hypothesis给shatter掉。首先我们找到d+1组输入数据，存在矩阵X中，矩阵的每一行是一组数据。另外，矩阵X是可逆的。shatter的意思是说，对于任意$y=(y_1,y_2,...,y^{d+1})^T$都能找到一个w使得$sign(Xw)=y$。
如何做到这一点呢，看下面：
$$(Xw=y) \Rightarrow sign(Xw) = y \Longleftrightarrow w=X^{-1}y$$
所以说这一组特殊的数据集可以被shatter，从而证明了$d_{vc} \geq d+1$

小测试：

现在来证明$d_{vc} \leq d+1$。举一个二维的例子，选择下图中的一组数据集，注意其中$x_4$可由$x_1$、$x_2$和$x_3$线性组合而来。前面我们说过下图中的那个问号不可能被标记为叉叉，同样$x_4$不可能被标记为叉叉，原因看下图的公式。

数据点之间的这种线性依赖关系限制了dichotomy的产生，这是一种特殊情况，但我们要证明的是所有的情况都不能被shatter。现在我们用一组d维的一般例子来解释。下图中的矩阵X包含d+2组数据，这d+2组数据肯定是线性相关的，然后重复前一张图的计算公式，我们同样也可以证明不能被shatter。这样我们就完成了对一般情况的证明。

最后是小测试：

Physical Intuition of VC Dimension

VC dimension的物理意义就是我的hypothesis在做二元分类的时候大概有多少的自由度，也告诉我们这个hypothesis能最多产生多少dichotomy。不同的VC dimension对应的好坏处见下图：

这时，选择合适的VC dimension就变得很重要，而不同的VC dimension对应着不同的模型，所以选择模型是一件很重要的事。

本小节测试：

Interpreting VC Dimension

前面我们用一个不等式表示坏事情发生的概率，通过对该不等式的处理，我们得到了一个不等式来表示好事情发生的概率。

这里我们用$\Omega(N,H,\delta)$来表示上图中不等式的右侧，它表示在一个很高的几率内，$E_{out}-E_{in}$的值会小于$\Omega(N,H,\delta)$（当然，如果差值为负更好，说明g在未知数据上的犯错率比在训练集上还低）。

观察下图中的图像，可以看到随着$d_{vc}$的不断增大，$E_{in}$不断降低，$E_{out}$先降低后增加，模型复杂度不断增大。最合适的$d_{vc}^{*}$往往是在中间的。未来会利用这个图来设计更好的机器学习算法。

另外，VC bound还可以说明样本的复杂度。假设已经给定了$\epsilon$、$\delta$、$d_{vc}$，问我们需要多大的训练集才可以得到这样的精度，请看下图。总结起来，理论上可能需要$N \approx 10,000d_{vc}$才能有一个好的精度，而实际上当$N \approx 10d_{vc}$时就已经足够了。

这也说明这个VC bound实际上是很宽松的，宽松的原因是在整个推理过程中多次放大标准（要求太严），具体看下面四点。

到这里，VC bound背后的一些数学意义和哲学意义就算介绍完了，虽然在以后的课程中涉及不太多，但大大加深了我们对机器学习的理解。

本节小测试：