VC 维度（七）

这一章节非常重要，也是有点难度的

上节课我们知道，我们得到的一个结论是：

我们的假设函数的成长函数，它的break point 是K，那么成长函数是小于边界函数B（N，k）的，边界函数是，边界函数的最大值是N的k-1次方

那么我们把我们的B（N，K）的值和N的k-1次方的值列出来，会发现其实：

也就是说成长函数会被N的k-1次方所限定。

上节课我们还讲到说我们的任意一个假设函数发生坏的事情的概率很小：

由于我们的成长函数又被N的k-1次方所限定，所以：，这个上限需要N够大，K够大，由于N够大我们已经满足了，那就是还有多加了一个k够大。

总结一下：1.我们需要有一个好的成长函数，它break point K

    2.我们需要N够大，使得我们E（out）近似的等于E（in）

    3.我们还需要有一个好的演算法，使得能够找到最好的E(in)

    4.最后由于我们的上面的结论都是一个大概率事件，所以我们还需要有好一点的运气。

下面，我们开始说VC维度

VC维度的定义：最大的可以被shatter的点，也就是K-1，比如我们的K是3，那么我们的VC维度值就是2.

那么，我们可以得出以下结论：1.如果我们的样本集合数目小于等于VC维度值的话，那么可以得出存在假设函数集合分类使得我们的样本集合都被shatter，只是存在，不是一定。因为我们不知道我们的假设函数集有没有足够多的假设函数。

2.当我们的N大于VC维度的话，那么我们的样本集合一定不能全部被shatter。

那么N够大，vc维度够大，那么我们的成长函数比N的VC维度次方小。

同样我们可以得出：当VC维度是有限的值的话，我们的就可以说我们的E（out）≈E（in）

下面我们回到我们的PLA中。

如果我们的样本集合是线性可分的话，那么我们的PLA可以停止，并且找到一个E（in）（g）=0，然后由于其VC维度是3，是有限的，那么当N足够大的时候，我们的E（in）≈E（out），那么我们的E（out）（g）≈0

那么，当维度是多维的情况下呢？

我们知道，当是在一维的情况下：VC维度是2

在二维的情况下的perceptron：VC维度是3

那么我猜想是不是：VC维度=d+1？

下面我们进行证明：

我们只需要证明VC维度≥d+1，VC维度≤d+1

要证明前者，我们只需要找到d+1个样本集合，这d+1个样本集合可以被我们的假设函数集合shatter。

看下面这种特殊的情况:

我们把d+1个样本集合用一个矩阵表示出来

我们看到，当d=2的时候注意这个矩阵是，撇开第一列的常数项，看剩余的三个样本点是（0,0），（1,0），（0,1），这三个点在坐标中的分布式是这样的：，我们很轻易的得出这个是能够被shatter的。接下来我们要证明在d维的时候，这些d+1个点也是可以被shatter的。

注意以上的大的矩阵是存在逆矩阵的，存在逆矩阵有什么用呢？

先明白什么是shatter，其实就是给定任意的y的组个，我们可以找到w（其实代表的就是假设函数）

使得 ，那么如果我们XW=y的时候，XW的sign一定也是y。由于它的逆矩阵是存在的所以，我们可以令