机器学习基石-The VC Dimension

The VC Dimension

前情摘要

前几节课中我们通过定义一系列的概念最终完成了机器学习可行性的证明，然后今天的课程我们将上节课的概念做一个深化，本节课的主要内容是VC Dimension。

Definition of VC Dimension

上一节课中，我们学到成长函数的上界函数是poly(N）并且最高次数是k-1的，其中K为break point。然后我们试着写出B(N,k)和N^(k-1)的表格形式，我们发现在N ≥ 2和k ≥ 3时，成长函数小于等于N^(k−1)，然后我们将上述结论代入我们前两节课得出的结论公式中得到下图的不等式。

这样的情况下，机器学习的可行性基本需要满足一下几个条件：1、我们需要有一个好的H，意思是其成长函数需要存在一个“漏出一线曙光”（mH(N)≠2^N)的点;2、我们需要有一个好的观测集D,即N要足够大；3、我们需要一个好的演算法进而帮助我们找到一个较小的Ein。最后，我们可能还需要一点点运气来帮助我们做到一个不错的结果。

言归正传，我们接下来给出VC Dimension的定义：最大的那个不是break point的点。VC Dimension是hypothesis set的一个性质，在VC Dimension上这个hypothesis可以shatter掉“某”N个点，不一定是所有的N个点。超过VC Dimension，就会出现不能shatter即break point的情形，所以他满足上图的公式。

以上是四个我们之前学过的成长函数，我们容易得到他们的

dVC值，我们之前说一个好的H，是漏出一线曙光的H，也即

dVC是finite的H。

一个finite的dVC能保证说Ein和Eout是比较接近的，并且这个结论与我们选择的演算法、资料的分布和目标函数均没有关系，因为我们推导过程中并没有用到上述假设。

VC Dimension of Perceptrons

我们回顾下我们之前学习的2D的perceptron，结合VC理论易知VC维度为3，结合上图我们知道2D情形下的PLA是可行的。然后我们看看多维情形下的perceptron的dVC值，我们通过总结猜想dVC=d+1，其中d为维数。

Physical Intuition of VC Dimension

我们接下来看看VC Dimension的物理意义：我们的hypothesis在做二元分类时“有效”的自由度，他的意思对应到H产生dichotomy的能力的强弱。然后我们通过低纬度的情形大致可以总结得出：VC Dimension大体上与我们可以自由调节的因素的个数一致。

然后我们将VC Dimension和lecture5中的M联系起来，对应的我们可以得到类似的结论，这块不作过多解释。

Interpreting VC Dimension

接下来我们进一步探索VC Dimension更深层次的数据，我们写出之前版本的Hoefffding公式，上面的公式的意思是坏事的发生概率很低，那么对应的好事情发生的概率是很高的，于是通过数学处理我们得到ε，然后进一步代入公式可以得到下面的公式。

然后我们来总结下VC message：1、首先，Ein小于等于Eout加上Ω（model complexity）；2、Ein随着VC Dimension的上升而降低，Ω随着VC Dimension的上升而上升；3、Eout的最佳值一般在中间值取得。

接下来我们看看机器学习对资料量的要求，我们主要根据VC bound理论，对上面一个场景进行计算，发现要满足实际规格的要求需要的资料量大概是VC Dimension的10000倍，这似乎和我们的实际生活有些许差异，实际场景中我们通过统计发现大概10倍VC Dimension的资料量就能有一个还不错的结果，也就是说我们的这个VC bound的里面是非常宽松的。导致这个结果的原因主要是我们在推导的过程中的条件是十分宽松的，这导致最后将VC bound放大了若干倍，主要的条件为以下四项。

课程小结

本节课我们主要介绍VC Dimension，我们首先给出了他的定义，然后证明了他在perceptron中的公式，接着介绍了他的物理意义，最后揭示了其与model complexity和sample complexity间的关系。