机器能够学习必须满足两个条件：

假设空间H的Size M是有限的，即当N足够大的时候，那么对于假设空间中任意一个假设g， $E_{out} \approx E_{in}$。
利用算法A从假设空间H中，挑选一个g，使$E_{in} \approx 0$ ，则$E_{out} \approx 0$。

这两个条件，正好对应着test和trian两个过程。train的目的是使损失期望$E_{in}(g) \approx 0$；test的目的是使将算法用到新的样本时的损失期望也尽可能小，即$E_{out} \approx 0$。

正因为如此，上次课引入了break point，并推导出只要break point存在，则M有上界，一定存在$E_{out} \approx E_{in}$。

Definition of VC Dimension

首先，我们知道如果一个假设空间H有break point k，那么它的成长函数是有界的，它的上界称为Bound function。根据数学归纳法，Bound function也是有界的，且上界为$N^{k - 1}$。从下面的表格可以看出， $N(k - 1)$比B(N,k)松弛很多。

则根据上一节课的推导，VC bound就可以转换为：

这样，不等式只与k和N相关了，一般情况下样本N足够大，所以我们只考虑k值。有如下结论：

若假设空间H有break point k，且N足够大，则根据VC bound理论，算法有良好的泛化能力
在假设空间中选择一个g，使$E_{in} \approx 0$，则其在全集数据中的错误率会较低

VC Dimension就是某假设集H能够shatter的最多inputs的个数，即最大完全正确的分类能力。（注意，只要存在一种分布的inputs 能够正确分类也满足）。

shatter的英文意思是“粉碎”，也就是说对于inputs的所有情况都能列举出来。例如对N 个输入，如果能够将$2^N$种情况都列出来，则称该N个输入能够被假设集H shatter。

根据之前break point的定义：假设集不能被shatter任何分布类型的inputs的最少个数。则VC Dimension等于break point的个数减一。

现在，我们回顾一下之前介绍的四种例子，它们对应的VC Dimension是多少：

用$d_{vc}$代替k，那么VC bound的问题也就转换为与$d_{vc}$和N相关了。同时，如果一个假设集H的$d_{vc}$确定了，则就能满足机器能够学习的第一个条件$E_{out} \approx E_{in}$，与算法、样本数据分布和目标函数都没有关系。

VC Dimension of Perceptrons

回顾一下我们之前介绍的2D下的PLA算法，已知Perceptrons的k=4，即$d_{vc} = 3$。根据VC Bound理论，当N足够大的时候， $E_{out}(g) \approx E_{in}(g)$。如果找到一个g，使$E_{in}(g) \approx 0$，那么就能证明PLA是可以学习的。

这是在2D情况下，那如果是多维的Perceptron，它对应的$d_{vc}$又等于多少呢？

已知在1D Perceptron， $d_{vc} = 2$，在2D Perceptrons，$d_{vc} = 3$ ，那么我们有如下假设： $d_{vc} = d + 1$，其中d为维数。

要证明的话，只需分两步证明：

$d_{vc} \geq d + 1$
$d_{vc} \leq d + 1$

首先证明第一个不等式：$d_{vc} \geq d + 1$

在d维里，我们只要找到某一类的d+1个inputs可以被shatter的话，那么必然得到$d_{vc} \geq d + 1$。所以，我们有意构造一个d维的矩阵$X$能够被shatter就行。$X$是d维的，有d+1个inputs，每个inputs加上第零个维度的常数项1，得到的矩阵：

矩阵中，每一行代表一个inputs，每个inputs是d+1维的，共有d+1个inputs。这里构造的$X$很明显是可逆的。shatter的本质是假设空间H对$X$的所有情况的判断都是对的，即总能找到权重W，满足$X * W = y$，$W = X^{-1} * y$ 。由于这里我们构造的矩阵$X$的逆矩阵存在，那么d维的所有inputs都能被shatter，也就证明了第一个不等式。