Lec 7-1 VC Dimension 的定义

break point 与成长函数的上限

如果mH(N) 的成长函数在某个点 k 的地方使 mH(N) <= 2^k 即 k 个点不能被shatter的话，这个成长函数会被某个上限函数给bound住，这个上限函数又会被某个多项式给bound住，这个多项式的次方是 k-1 次方。

所以我们可以把上限函数的表格和 N^(k1) 的表格列出来，但其实当N够大(也没有多大，只需要N大于等于2，k大于等于3)，N^(k-1) 其实比成长函数的上限函数 B(N, k) 大，

所以之前的推理在实例上也证明是合理的，成长函数的上限会被N^(k-1) bound住：

VC维

先前证明了，如果在hypothesis set里面，有任何一个hypothesis 发生坏事的几率很小很小：

所以不管我们的演算法在hypothesis set 中挑出了怎样的 h 来作为最终的 g，都是被这个不等式支配的：

而上式是我们用 ghost sample 的图示来证明的，如果把再之前的 mH(N) <= N^(k-1) 代入，则得到：

要满足上面的上限，需要有一些前提条件：

① 要有一个好的 Hypothesis set，这个 hypothesis set 成长函数在 k 个点时能够出现 break point。

② 要有好的data，即 N要足够大。

满足这两个前提条件，才能保证 Eout 与 Ein足够接近。

③ 另外，我们还需要好的演算法和一点点好的运气来找到能使Ein足够小的 h。

这样才能做到让机器能够学习。

VC Dimension 是什么

VC维其实是我们给之前讲的Break point 的一个正式的名称，不过还没又到达break point， VC维是break point 的前一个点，即 k-1。

VC维是一个hypothesis  set 的性质，它告诉我们说，在VC dimension上面，这个hypothesis set 可以shatter掉某N个点（不是所有的N个点，只是某N个点）；如果超过这个VC dimension的话，就开始出现不能shutter 的情况。

如果最小不能shatter的点minimum k 不存在的话，VC dimension就是无限大。

当资料量小于等于VC dimension时，表示资料有可能会被hypothesis set shatter，不是一定会被shatter，只是存在某个资料会被hypothesis set来shatter。

当资料量大于VC dimension时，我们非常确定它一定不能被shatter，之前我们使用的符号不是N，而是k，也就是H 的break point，因为 N 比VC dimension大时，其实它就是k。

所以当N够大，VC dimension也够大的时候，我们可以说我们的成长函数比N的VC dimension要小。也就是原来的k-1 被替换为了VC dimension。

案例回顾

VC dimension的好处

什么是好的hypothesis set——VC dimension 是有限大的hypothesis set 就是好的hypothesis set。

如果是一个好的hypothesis set 有什么好事? Eout 与 Ein 很接近。并且，它跟以下情况都没有关系：

① 它跟演算法 A 怎么选择g没有关系：

     即使选到了Ein很大的g，Eout与Ein还是很接近，只是不够小而已；

② 它跟资料的分布没有关系；

③ 它跟target function的样子没有关系；

那么我们就可以在上述情况都不知道的情况下，做到Eout 和 Ein 很接近，剩下的就只是通过好的演算法 A 来找到 Ein 很小的 g 了。

7-2 Perceptron 的VC dimension

在2D的PLA 中，如果资料是线性可分的，PLA才有可能会停下来，最终才能找到使Ein为0的g。

另一方面，资料是从某个分布出发的（我们不用知道具体分布），并且有一个目标函数target function，由于2D perceptron的VC dimension 是3，所以我们就可以确保，当资料量足够大（至少大于3），它的Eout 有很大的机会是和Ein很接近的。

结合这两方面，我们可以得出Eout是接近于0的，机器学到东西了。

PLA 推广到多维

1D 和 2D 的perceptron 都满足 dVC = d+1，那么大胆猜想多维的perceptron 也满足 dVC = d + 1， 要证明这个猜想，需要从两方面入手：

我们知道，VC dimension保证了，在小于等于VC dimension时，是没有break point的。回顾break point的定义，当出现break point，则资料无论如何也不能shatter。

要证明大于等于，即证明当资料数等于d+1时，这些资料可以被shatter，这说明break point 是大于d+1 的，那么 dvc =  k -1 则是大于等于 d+1 的

要证明小于等于，即证明即使当资料数等于d+2，任何一种情况都不能shatter，这说明已达到了break point ，即k <= d+2，那么dvc = k - 1 则是小于等于d+1 的。

证明 dvc >= d+1

假设有一组特别的资料，然后我们来证明可以在这组资料上做到shatter。这组特别的资料长什么样呢？它有d+1 笔，它的第一笔，我们把它设定成原点；第二笔设定成在所有维度的第一个维度上有一个分量，其他维度统统为0；第三笔资料在第二个维度上有一个分量，其他维度统统为0；以此类推。

因为有d个维度，再加上原点，所以总共有d+1笔资料。可以把这些资料排成一个矩阵如下：

在这个矩阵最左边有一些灰色的1，这就是我们偷偷塞进去的x0维度，代表threshold。

如果现在是2D，那么有d+1 = 2+1 = 3笔资料，就是原点、（1,0）,(0,1) 这三个点。在二维上能够很轻易地看到，这三个点是可以被shatter的。

我们要证明的是在d个维度的时候，d+1点也能够被shatter。

注意到，这个矩阵的逆矩阵是存在的且唯一的。很容易证明该矩阵式可逆：除了第一行之外的每一行都减去第一行得到一个对角矩阵，因此为满秩，可逆。这对于我们有什么意义呢？

首先我们要明确shatter的意思即完全二分，我们给它任何一个y的圈圈叉叉的排列组合，只要找出对应的权值向量w，能将上述输入样本集X映射到全部的二分情况下的 y 上就可以了，即能够使 Xw = y。而PLA可以用sign(Xw) = y 来表示，假如Xw 可以等于 y，那么取符号后也一定等于y（用threshold校正后，y为1 或 -1）。

由于X是可逆矩阵，输出向量y的任意一种二分类情况都可以被一个假设函数w划分，只要权值向量w满足w = X(逆)y 即可，即任何一种二分类情况都会有一个权向量w与之对应，因此dvc >= d+1得证。

证明 dvc <= d+1

要证明所有d+2 的情况都不能shatter 会困难一点。我们回到前面那个特殊的d+1 笔资料的例子，现在再加一笔资料进来变成d+2笔。

在三个点的基础上加一个点，如果出现下面这种对角线的情况，原点的点是×，第一维度和第二维度的点是⭕，那么新加的第三维度的点就不能是×，否则它就不能被二分。不能被二分的dichotomy情况不能被产生（后面将证明）。

数学上的理由是：

以x1为原点（0，0），x1 为x轴上的（1，0）， x2为y轴上的（0，1）的话，x4（1，1）等于 x2 + x3 - x1是成立的。

在此基础上，用任何一个W乘上这个向量等式的话，它也是成立的。如果这个权重矩阵W刚好在x2 和 x3处得到⚪，为正，在x1处得到X，为负，如果把这三项加起来，一定是正的（+1），那么x4就一定是⚪（2-1= +1），它不可能是X，这是由它的本质性质所决定的，即如果把x4表示成x1，x2，x3的 线性组合的话，它们之间的线性依赖关系限制了能产生的dichotomy的数量，导致x4无法成为X。

当然这是一个特殊的例子，我们还需要对所有d+2笔资料全都满足不能shatter才行。

把d+2笔资料列在一个矩阵里(转置过)，这个矩阵，行的数量是 d+2，列的数量是d+1。而线性代数告诉我们说，这个时候会有线性相依的产生，也就是可以把x(d+2)表示成其他向量的线性组合。这些a1、a2……的系数，有的是正的，有的是负的，有的是0，但不会全部是0。

那么如果有一组w，这组w在前面 d+1 个资料产生的情形刚好跟这些系数为正或为负一致，也就是如果a1是正的，w刚好在x1上产生一个⚪，a2是负的，w刚好在X2上产生一个x，以此类推。

假设存在Xd+2可以为 X 的情况，因为a1和 yT 的第i个分量同号（i=1,2,…,d+1），因此左项必然为正，所以我们产生不了x(d+2)为X的情况，x(d+2)只能为⚪，也就是不能shatter。

不管是什么资料，只要有这个线性依赖的关系，第d+2笔资料无论如何也不能为X，所以也就证明了N = d + 2 时，资料不能被shatter，break point k <= d+2, 所以dvc = k-1 <= d+1