VC维的来龙去脉

本文转自： VC维的来龙去脉

VC维在机器学习领域是一个很基础的概念，它给诸多机器学习方法的可学习性提供了坚实的理论基础，但有时候，特别是对我们工程师而言，SVM，LR，深度学习等可能都已经用到线上了，但却不理解VC维。

这里，在台湾大学 机器学习基石 课程的基础上，我们简单聊聊“VC维的来龙去脉”。我们将解决以下问题：为什么某机器学习方法是可学习的？为什么会有过拟合？拿什么来衡量机器学习模型的复杂度？深度学习与VC维的关系？

在讲VC维之前，我们不妨来说说VC维的历史。而说起VC维的历史，又不得不提起神经网络，一方面是因为神经网络与VC维的发明过程是交织在一起的，另一方面是由于神经网络乏善可陈的泛化控制方法，深度学习在理论基础上一直被怀疑，甚至神经网络和VC维的代表SVM还一起争风吃醋过好多年。

1943年，模拟神经网络由麦卡洛可（McCulloch）和皮茨（Pitts)提出，他们分析了理想化的人工神经元网络，并且指出了它们进行简单逻辑运算的机制。

1957年，康奈尔大学的实验心理学家弗兰克·罗森布拉特(Rosenblatt)在一台IBM–704计算机上模拟实现了一种他发明的叫作“感知机”（Perceptron）的神经网络模型。神经网络与支持向量机都源自于感知机（Perceptron）。

1962年，罗森布拉特著作：《神经动力学原理：感知机和大脑机制的理论》（Principles of Neurodynamics: Perceptrons and the Theory of Brain Mechanisms）。

1969年，明斯基和麻省理工学院的另一位教授佩普特合作著作：《感知机：计算几何学》（Perceptrons: An Introduction to Computational Geometry)。在书中，明斯基和佩普特证明单层神经网络不能解决XOR（异或）问题。

1971年，V. Vapnik and A. Chervonenkis在论文“On the uniform convergence of relative frequencies of events to their probabilities”中提出VC维的概念。

1974年，V. Vapnik提出了结构风险最小化原则。

1974年，沃波斯（Werbos）的博士论文证明了在神经网络多加一层，并且利用“后向传播”（Back-propagation）学习方法，可以解决XOR问题。那时正是神经网络研究的低谷，文章不合时宜。

1982年，在加州理工担任生物物理教授的霍普菲尔德，提出了一种新的神经网络，可以解决一大类模式识别问题，还可以给出一类组合优化问题的近似解。这种神经网络模型后被称为霍普菲尔德网络。

1986年，Rummelhart与McClelland发明了神经网络的学习算法Back Propagation。

1993年，Corinna Cortes和Vapnik等人提出了支持向量机(support vector machine)。神经网络是多层的非线性模型，支持向量机利用核技巧把非线性问题转换成线性问题。

1992~2005年，SVM与Neural network之争，但被互联网风潮掩盖住了。

2006年，Hinton提出神经网络的Deep Learning算法。Deep Learning假设神经网络是多层的，首先用Restricted Boltzmann Machine（非监督学习）学习网络的结构，然后再通过Back Propagation（监督学习）学习网络的权值。

现在，deep learning的应用越来越广泛，甚至已经有超越SVM的趋势。一方面以Hinton，Lecun为首的深度学习派坚信其有效实用性，另一方面Vapnik等统计机器学习理论专家又坚持着理论阵地，怀疑deep learning的泛化界。

Hoeffding不等式是关于一组随机变量均值的概率不等式。 如果X1,X2,u22ef,Xn为一组独立同分布的参数为p的伯努利分布随机变量，n为随机变量的个数。定义这组随机变量的均值为：

接下来，我们希望可以将机器学习关联到上一节讨论的hoeffding不等式。

一个基本的机器学习过程如下图所示。其中的概念定义为： f 表示理想的方案(可以是一个函数，也可以是一个分布)，H 是该机器学习方法的假设空间，g 表示我们求解的用来预测的假设，g属于H。

机器学习的过程就是：通过算法A，在假设空间H中，根据样本集D，选择最好的假设作为g。选择标准是 g 近似于 f。

Eout(h)，可以理解为在理想情况下(已知f)，总体(out-of-sample)的损失(这里是0–1 loss)的期望，称作expected loss。

根据上面不等式，我们可以推断，当N足够大时，expected loss和expirical loss将非常接近。

注意在上面推导中，我们是针对某一个特定的解h(x)。在我们的假设空间H中，往往有很多个假设函数(甚至于无穷多个)，这里我们先假定H中有M个假设函数。

上面式子的含义是：在假设空间H中，设定一个较小的u03f5值，任意一个假设h，它的Ein(h)与Eout(h)的差由该值2Mexp(u22122u03f52N)所约束住。注意这个bound值与 “样本数N和假设数M” 密切相关。

上面这两个核心条件，也正好对应着test和train这两个过程。train过程希望损失期望(即Ein(g) )尽可能小；test过程希望在真实环境中的损失期望也尽可能小，即Ein(g)接近于Eout(g)。

但往往我们更多在关心，如何基于模型的假设空间，利用最优化算法，找到Ein最小的解g。但容易忽视test这个过程，如果让学习可行，不仅仅是要在训练集表现好，在真实环境里也要表现好。

M太小，当N足够大时，Ein和Eout比较接近，但如果候选假设集太小，不容易在其中找到一个g，使得Ein(g)约等于0，第二项不能满足。

而如果M太大，这时候选集多了，相对容易在其中找到一个g，使得Ein(g)约等于0，但第一项就不能满足了。所以假设空间H的大小M很关键。

虽说假设空间很大，上述推导里，我们用到了P(h1 or h2 … hm) <= P(h1) + P(h2) + … + P(hm)。但事实上，多个h之间并不是完全独立的，他们是有很大的重叠的(这里重叠可理解为不同模型可能发生相同的错误，即这些错误重叠)，也就是在M个假设中，可能有一些假设可以归为同一类。

下面我们以二维假设空间为例，来解释一下该空间下各假设在确定的训练样本上的重叠性。

对于这个有效的假设函数值，我们尝试用一个数学定义来说明：

从H中任意选择一个方程h，让这个h对样本集合D进行二元分类，输出一个结果向量。例如在平面里用一条直线对2个点进行二元分类，输出可能为{1,–1}，{–1,1}，{1,1}，{–1,–1}，这样每个输出向量我们称为一个dichotomy。

下面是hypotheses与dichotomies的概念对比：

注意到，如果对平面上的4个点来分类，根据前面分析，输出的结果向量只有14种可能，即有14个dichotomies。

如果有N个样本数据，那么有效的假设个数定义为： effective(N) = H作用于样本集D“最多”能产生多少不同的dichotomy。

H作用于D“最多”能产生多少种不同的dichotomies？这个数量与假设空间H有关，跟数据量N也有关。将H作用于D“最多”能产生的dichotomies数量(即effective(N) )表示为数学符号：max_H(x1,x2,…,xN)

在进一步推导前，再看两个概念：shatter，break point。

Shatter的概念：当假设空间H作用于N个input的样本集时，产生的dichotomies数量等于这N个点总的组合数2^N是，就称：这N个inputs被H给shatter掉了。

对于给定的成长函数m_H(N)，从N=1出发，N慢慢变大，当增大到k时，出现mH(N)<2k的情形，则我们说k是该成长函数的break point。对于任何N > k个inputs而言，H都没有办法再shatter他们了。

举例来说，对于上面的positive ray的例子，因为m_H(N)=N+1，当N=2时，m_H(2)<2^2， 所以它的break point就是2。

说完break point的概念后，再回到成长函数。

我们将成长函数的上界，设为B(N,k)，意为：maximum possible m_H(N) when break point = k。

那么我们做一些简单的推导：

B(2,2)=3。因为break point=2，任意两个点都不能被shatter，m_H(2)肯定小于22，所以B(2,2)=3。

B(3,2)=4。因为任意两个点都不能被shatter，那么3个点产生的dichotomies不能超过4，所以B(3,2)=4。

B(N,1)=1。

B(N,k)=2N for N < k；B(N,k)=2N–1 for N=k；

B(4,3)=？去掉其中的一个数据点x4后，考虑到break point=3，余下数据(x1,x2,x3)的dichotomies数目不能超过B(3,3)。当扩展为(x1,x2,x3,x4)时，(x1,x2,x3)上的dichotomies只有部分被重复复制了，设被复制的dichotomies数量为a，未被复制的数量为b。于是有B(3,3) = a+b; B(4,3) = 2a + b。因为a被复制了，表示x4有两个取值，那么(x1,x2,x3)上的a应该小于等于B(3,2)。所以推导出B(4,3) = 2a + b <= B(3,3) + B(3,2)。

对于任意N>k，类推可以得到，B(N,k) ≤ B(Nu22121,k)+B(Nu22121,ku22121)

所以我们得到结论：如果break point存在（有限的正整数），生长函数m(N) 是多项式的。

再重复一遍，H作用于数据量为N的样本集D，方程的数量看上去是无穷的，但真正有效(effective)的方程的数量却是有限的，这个数量为m_H(N)。H中每一个h作用于D都能算出一个Ein来，一共有m_H(N)个不同的Ein。

OK，到目前为止，关于m_H(N)的推导结束。回到growth function小节提出的问题，能否用m_H(N)直接替换M?

关于这个公式的数学推导，我们可以暂且不去深究。我们先看一下这个式子的意义，如果假设空间存在有限的break point，那么m_H(2N)会被最高幂次为k–1的多项式上界给约束住。随着N的逐渐增大，指数式的下降会比多项式的增长更快，所以此时VC Bound是有限的。更深的意义在于，N足够大时，对H中的任意一个假设h，Ein(h)都将接近于Eout(h)，这表示学习可行的第一个条件是有可能成立的。

说了这么多，VC维终于露出庐山真面目了。此概念由Vladimir Vapnik与Alexey Chervonenkis提出。

一个假设空间H的VC dimension，是这个H最多能够shatter掉的点的数量，记为dvc(H)。如果不管多少个点H都能shatter它们，则dvc(H)=无穷大。还可以理解为：vc-dim就是argmax_n {growth function=power(2,n)}。

根据定义，可以得到一个明显的结论：

k = d_vc(H) + 1

根据前面的推导，我们知道VC维的大小：与学习算法A无关，与输入变量X的分布也无关，与我们求解的目标函数f 无关。它只与模型和假设空间有关。

总结回顾一下，要想让机器学到东西，并且学得好，有2个条件：

从上图可以看出，当VC维很小时，条件1容易满足，但因为假设空间较小，可能不容易找到合适的g 使得Ein(g)约等于0。当VC维很大时，条件2容易满足，但条件1不容易满足，因为VC bound很大。

VC维反映了假设空间H 的强大程度(powerfulness)，VC 维越大，H也越强，因为它可以打散(shatter)更多的点。

注意在前述讨论中，理想的目标函数为f(x)，error measure用的是“0–1 loss”。如果在unknown target上引入噪声(+noise)，或者用不同的error measure方法，VC theory还有效吗？这里只给出结论，VC theory对于绝大部分假设空间(or 加入噪声)和error度量方法，都是有效的。

除此外，我们为了避免overfit，一般都会加正则项。那加了正则项后，新的假设空间会得到一些限制，此时新假设空间的VC维将变小，也就是同样训练数据条件下，Ein更有可能等于Eout，所以泛化能力更强。这里从VC维的角度解释了正则项的作用。

对于神经网络，其VC维的公式为：

举例来说，一个普通的三层全连接神经网络：input layer是1000维，hidden layer有1000个nodes，output layer为1个node，则它的VC维大约为O(1000 1000 1000)。

可以看到，神经网络的VC维相对较高，因而它的表达能力非常强，可以用来处理任何复杂的分类问题。根据上一节的结论，要充分训练该神经网络，所需样本量为10倍的VC维。如此大的训练数据量，是不可能达到的。所以在20世纪，复杂神经网络模型在out of sample的表现不是很好，容易overfit。

但现在为什么深度学习的表现越来越好。原因是多方面的，主要体现在：

但即便这样，深度学习的VC维和VC Bound依旧很大，其泛化控制方法依然没有强理论支撑。但是实践又一次次证明，深度学习是好用的。所以VC维对深度学习的指导意义，目前不好表述，有一种思想建议，深度学习应该抛弃对VC维之类概念的迷信，尝试从其他方面来解释其可学习型，例如使用泛函空间（如 Banach Space ）中的概率论。

上面仔细分析了VC维的来龙去脉，讲述了VC维在机器学习理论中的指导意义。考虑到VC维在机器学习领域虽是基础，却也是大坑，所以难免有理解不深或不当之处，敬请谅解。若希望获得更深理解，请参考下面的参考文献。