引入

上一小节中，“理解为什么机器可以学习——Hoeffding不等式”中，我们介绍了有限假设空间中的概率边界。在这篇文章中，我们将推广至无限假设空间中，进而引入VC理论。

面临待解决的问题

上一节，我们证明了PAC学习的样本复杂度随假设空间对数增长，但是以假设空间的个数|H|来刻画样本复制度存在缺点：

• 对于|H|很大的情形，会使一个很弱的边界，即出现错误的概率很大
• 对于无限假设空间的情形无法应用

所以，我们要考虑H的复杂度的另一种度量方式，称为H的Vapnik-Chervonenkis维度（简称VC维），我们用VC(H)代替|H|得到样本复杂度的边界。

打散(shatter)一个数据集合

VC维衡量假设空间复杂度的方法不是用不同假设的数量|H|，而是用给定X中能被H彻底区分的不同实例的数量（举个例子，比如2D空间有两个数据，如果是用感知机模型的话，可以将这两个数据分成两个正例、两个负例、一正一负或一负一正，我们知道在这种情况下，感知机的假设空间是无穷的，但是实际上导致最终分类的只有4中不同结果）。

Dichotomy，一分为二的划分

想象我们现在有一个假设集合，这个假设集合将N个点的数据分成正例和负例的不同组合（用圈和叉来表示），于是我们就将假设将数据分成不同正负例的组合称为Dichotomy。Hypotheses和Dichotomies的区别如下图所示，Dichotomies最多有2的N次方种可能。于是，我们就打算用Dichotomies的有效数量来取代有限假设空间的Hoeffding不等式中的M。

成长函数Growth Function

由于这里我们定义的Dichotomy是依赖具体的N个输入数据的，为了移除这里的影响，我们现定义成长函数mH(N)，用它来表示对于不同的数据集的Dichotomy的最大值。

以2D的Perceptron举例来说，针对不一样的输入点的个数N，可能有不同的有效分离平面，不一定是2的N次方种。

shatter

一数据集D被假设空间H打散（shatter），当且仅当对D的每个划分，存在H中的某假设与此划分一致（即当D的每种可能划分可由H中的某个假设来表达时，称H打散D）。
注意：
如果一个数据集合没有被假设空间打散，那么必然存在某种划分可被定义在数据集中，但不能由假设空间表示。
H的这种打散数据集合的能力是其在这些数据上定义目标函数的表示能力的度量。可以说被打散的X的子集越大，H的表示能力越强。

Break Point of H

基于上面的介绍我们可以回头看看Hoeffding不等式，我们想要用成长函数mH(N)来代替假设空间的数量|H|，而如果mH(N)和e的负幂次相乘，那么得到一个很小的数，这就对出错的概率作了一个限制；而如果mH(N)是一个幂指数的话，就无法限制错误率。

下面，我们定义一个新的概念——Break Point。如果数据集中的数据个数k是，假设空间H无法打散这个数据集，那么就说k是H的Break Point。比如，2D的Perceptron的情形，当N=4时，数据集应该可以有16种类别情形，而实际上，假设空间的有效个数只是14，那么4就是这个H的Break Point。

Bounding Function

上限函数Bounding Function B(N,k)是Break Point为k时，成长函数mH(N)的最大值，利用上限函数可以不去管假设空间里的具体细节，这样，只要上限函数是多项式的形式的话，就可以解决问题。
这里我们经过计算归纳，得到了上限函数的列表和规律：

经过一番努力，我们可以得到 成长函数mH(N)<= 上限函数B(N,k) <= 多项式函数poly(N)，只要成长函数有Break Point存在，那么该成长函数就是一个多项式。

VC Bound

这里给出VC bound的结论

这个结论通俗来讲就是，数据够多的时候，机器学习算法真的可以学到有用的知识。

小结

上面我们可以知道,要学到有用的东西需要下面几个条件：

• 好的假设空间，即mH(N)存在Break Point
• 好的数据，即数据足够多，使得训练误差和真实误差很接近
• 好的算法，即算法可以选出一个训练误差很小的假设
• 好的运气，因为之前说明的是一个概率问题，所以要有一点点运气，恶劣的情况才不会发生

VC维

定义

定义在输入空间X上的假设空间H的VC维，是可被H打散的X的最大有限子集的大小（数据量的大小）。如果X的任意有限大的子集可被H打散，则VC(H)为无穷大。
结合上面的介绍，我们知道VC维和Break Point的关系是：VC维 = ‘minimum k‘ - 1。通俗一点，比VC维大就是Break Point。
终于，我们可以得出结论，VC维是有限的假设就是好的假设。

VC维和学习的关系

• VC维和具体的学习算法A没有关系
• VC维和输入数据的概率分布P没有关系
• VC维和目标函数f没有关系

总结

我们终于一步一步地得到学习器能从数据中学习到有用的知识的限制条件，也明白了为什么机器能学习，其实就是从训练资料中选择一个错误率小的假设，该假设也能保证在更多的测试数据中存在较小的错误率。
在下一小节中，我要将VC维的内容收收尾，介绍一下VC维的物理意义，讨论一下PLA算法的VC维。

参考资料

机器学习， Tom M.Mitchell ，机械工业出版社
机器学习基石课程，林轩田，台湾大学

转载请注明作者Jason Ding及其出处
Github主页(http://jasonding1354.github.io/)
CSDN博客(http://blog.csdn.net/jasonding1354)
简书主页(http://www.jianshu.com/users/2bd9b48f6ea8/latest_articles)

【机器学习基础】理解为什么机器可以学习3——VC理论