统计学习理论之VC维究竟是什么

        学习机器学习不可避免的会接触到VC维，它在机器学习领域是一个很基础但很重要的概念，它给机器学习提供了坚实的理论基础。但直到在我写这篇博客之前，我对VC的理解还只停留在它能刻画假设空间的复杂度这样浅显的层次。本文就来理一理VC维(Vapnik–Chervonenkis dimension)的来龙去脉，搞清楚其本质。

二. 可学习的条件

        既然说VC维给机器学习提供了坚实的理论基础，那么就有必要来看看机器学习算法可学习的条件是什么。

2.1 学习的过程

        一个基本的机器学习过程如图1.1所示(本文图片若无特别说明即来自于台大机器学习基石课程课件，Coursera课程地址)。解释一下下图中的一些概念：表示学习算法， 表示学习的目标假设(可以是一个函数，也可以是一个分布)，  表示假设空间，  表示我们求解的用来预测的假设，  是属于   的。
机器学习的过程就是：通过算法 ，在假设空间   中，根据训练样本集  ，选择最好的假设作为    使近似于 。

 

图1.1中的   和  是两个重要的概念：

• ，学到的假设 g 在除了训练样本外的其他所有样本(out-of-sample)上的损失，称为期望误差，也称泛化误差。
• Ein(g)，学到的假设 g在训练样本(in-of-sample)上的损失，称为经验误差。

我们的目标是选择最好的假设作为 g 使 g 近似于 f，而 Eout(f)=0，也即我们的目标是使  。但我们是没法获得训练样本外的其他所有样本的，那也就没法计算 了，这该怎么办呢？

2.2 Hoeffding不等式

在回答1.1最后的问题之前，先来看看Hoeffding不等式。
来看图1.2所述的问题: 设瓶子里的橙色球占比为 μ ，从瓶子中随机抽取出N个样本，这N个样本中橙色球占比是 ν 。我们可以将 μ  看作1.1节中的Eout(g) ，将 ν  看作是 Ein(g) ，我们现在并不知道 μ  和 Eout(g) ，只知道 ν  和 Ein(g) ，我们可以从 ν  推断出关于 μ  的什么吗？

可以将 ν  看作是样本期望，μ  则是总体期望。

 

   

        直觉上，如果我们有更多的样本(抽出很多的球)，则 ν  应该越来越接近总体期望 μ 。事实上，这里可以用hoeffding不等式表示如下：

        从hoeffding不等式可以看出，当N越来越大时，ν  和 μ  之差大于 ϵ  的概率的上界越来越接近0，所以样本期望 ν  越来越接近总体期望 μ ，即 ν  和 μ  概率近似相等(probably approximately correct, PAC)了。

2.3 可学习的条件

        有了1.2节的铺垫，我们就可以来回答1.1节的问题了。

对于任意固定的假设 h ，当训练样本量N足够大，类比于1.2节的例子，可以通过样本集上的经验误差 Ein(h) 推测总体的期望误差 Eout(h) 。基于hoeffding不等式，我们得到下面式子：

根据上面不等式，我们可以推断，当N足够大时，Ein(h)  和 Eout(h)  将非常接近。

注意在上面推导中，我们是针对某一个特定的假设 hℎ。在我们的假设空间 H  中，往往有很多个假设(甚至于无穷多个)。那么对于假设空间 H  中的任意的假设 hℎ，Ein(h)  和 Eout(h)  之差大于 ϵ  的概率的上界会是什么呢？

发生概率很小的事件在很多次实验中发生概率就会变得很大。例如连续丢5次硬币，事件”五次都是正面朝上”的概率是 132132。但是如果100个人做这个实验，事件”五次都是正面朝上”的发生的概率就是 1−(3132)100>0.951−(3132)100>0.95。所以对于特定的假设 hℎ，Ein(h)  和 Eout(h)  很接近，但是对于 H 中任意的假设这就不一定了。

这里假定 H  中有 M  个假设 h1,h2,…hMℎ1,ℎ2,…ℎ ，则有如下推导:

其中 E(hi)=|Ein(hi)−Eout(hi)| 。

根据式 (1.3.2)   知

上面式子的含义就是：在假设空间 H  中，对于任意一个假设 g ，Ein(g)  和 Eout(g) 之差大于 ϵ  的概率的上界是 2Mexp(−2ϵ2N) 。注意这个上界与训练样本数 N  和假设空间假设数 M  密切相关。

本文的所有讨论都是围绕式(1.3.3)进行的!!!

所以，根据式 (1.3.3)(1.3.3)，我们就知道了可学习的两个核心条件是:

1. 学习算法 A  能够从 H  选出的假设 g  满足 Ein(g)≈0 。再结合条件2即达到了 Eout(g)≈0  的目标。
2. 假设空间 H  中假设数 M  是有限的且训练样本数 N  足够大。此时可保证式(1.3.3)右边上界趋于0，即学习算法 A  从 H  选出的任意假设 g  都满足 Ein(g)≈Eout(g) 。

上面这两个核心条件，也正好对应着train和test这两个过程:

1. train过程希望经验误差Ein(g) 尽可能小；
2. test过程希望在真实环境中的期望误差Eout(g) 也尽可能小，即Eout(g) )接近于Ein(g) 。

所以我们不应该只关心如何利用学习算法找到使 Ein(g)  很小的 g 。因为如果想让学习可行，也要保证Eout(g) 接近于Ein(g) 。

来分析一下 M  的大小对于两个条件的满足情况：

• 当 M  较小时，由式(1.3.3)(1.3.3)知条件2很容易满足，但是由于可选的 g  的数目 M  较小，所以条件1不容易满足；
• 当 M  较大时，由于可选的 g  的数目 M  较大，所以条件1很容易满足，但是条件2不容易满足。

        由此可见，假设数 M  在这两个核心条件中有着重要作用，应该合理选取。但是往往一个假设空间(如二维平面的所有直线)的假设数是很大的甚至是无穷的，此时式(1.3.3) 中的上界就成了无穷大没有任何约束意义，也即不满足条件2，学习变得不可行，这该怎么办呢？

三. VC维

3.1 有效假设数

在式(1.3.2)(1.3.2)的推导中，我们用到了这样一个概率不等式:

我们知道，当 Ai  相互独立时上式取等号。但事实上，假设空间里的 hi  之间并不是完全独立的，它们是有很大的重叠的，也就是在 M  个假设中，有很多假设都可以归为同一类。

下面用二维假设空间为例解释一下上述重叠性。我们知道二维假设空间的所有假设数(即直线条数)为 ∞∞，但是如图2.1所示，可以将这些假设分为两类，一类是把x1判断为正例，另一类是把x1判断为负例。

 

   

        那如果在平面上有两个不同的数据点x1,x2，这样的话，假设空间 H  中的无数条直线可以分为4类。那依次类推，3个数据点情况下，H  中最多有8类(当三个点在同一直线上时只有6类)。4个数据点时，H  中最多有14类(注意不是16类)，如下图所示。

 

   

从上面的分析可知，虽然假设空间假设数 M  一般非常大(甚至无穷)，但在特定的样本集上，有效的假设数目是有限的，也即式(1.3.3)(1.3.3)中的 M  是有限的，所以可以重写式(1.3.3)(1.3.3)如下:

3.2 对分和增长函数

为了探究式(2.1.2)中的 effective(M)  ，先引入对分(dichotomy) 的概念:

对于假设空间 H={h:X→{+1,−1}} ，我们称

h(X1,X2,…,XN)=(h(X1),h(X2),…,h(Xn))∈{+1,−1} 

为一个对分，即一个对分表示样本的一种标记结果，H(X1,X2,…,XN)  表示假设空间 H  在训练集 D  上的所有对分。

例如，若 N=4 且数据为二维时，参见图2.2，有如下表格:

	假设空间 H	H(X1,X2,X3,X4)
所有元素	平面上的所有直线	{+1,+1,+1,+1}, {+1,+1,+1,-1}…
元素个数	∞	最大为14 (不会超过 2N )

我们知道， H(X1,X2,…,XN)  的元素个数(即 |H(X1,X2,…,XN)| 是取决于具体的数据集 D  的，例如当 N=3 时且三个点不在一条直线时对分数为8，而在一条直线时对分数是6。为了去掉对具体 D  的依赖性，我们引入 增长函数(growth function):

假设空间 H  的增长函数 mH(N) 为

mH(N)=maxX1,X2,…,XN∈X|H(X1,X2,…,XN)| 

增长函数 mH(N)  表示假设空间 H  对个任意 N  个样本所能赋予标记的的最大可能结果数，其上界为 2N  。

显然，mH(N)  越大，H  的表示能力越强。因此，增长函数描述了假设空间 H  的表示能力，由此反映出假设空间的复杂度。既然如此，那我们可不可以用 mH(N) 直接替换掉式(2.1.2)  中的 effective(M) 呢，即

我们将在在2.3节回答这个问题。

3.3 VC界

3.3.1 打散(shatter)

在介绍VC维界(VC bound)之前，先引入打散(shatter)的概念,

当假设空间 H  作用于大小为 N  的样本集 D  时，产生的对分数量等于 2N  即 mH(N)=2N  时，就称 D  被 H  打散了。

shatter的原意是打碎，在此指 N   个点的所有(碎片般的)可能情形都被 H  产生了。

 

   

如上图所示，二维空间上的的三个点(不在一条直线上)可以被平面上所有直线这个假设空间打碎,此时 mH(3)=8=23 。但如下图所示的四个点就不能被这个假设空间打碎了，可知此时 mH(4)=14≠24 。

 

   

3.3.2 break point

尽管增长函数把假设数从无穷缩小到 2N ，但是这个量级还是太大了，很难保证式(1.3.3)(1.3.3)右边这个上界趋于0，所以能不能把量级再缩小一点?

为了回答这个问题，先给出break point的定义:

对于假设空间 H  的增长函数 mH(N)  ，从 N=1  出发逐渐增大，当增大到 k  时，出现 mH(N)<2N  的情形，则我们说 k  是该假设空间的break point。换句话说，对于任何大小为 N(N≥k)  的数据集， H  都没有办法打碎它。

举例来讲，由2.3.1节知，当假设空间 H  定义为平面上所有直线时，其break point就为4。

有了break point的概念，再经过一系列归纳证明(详见台大机器学习课程lecture6)，我们有这样一个结论:

设break point存在且为 k  的假设空间的增长函数上界为 B(N,k) ，则 B(N,k)  满足

mH(N)≤B(N,k)≤∑i=0k−1(Ni)≤Nk−1 

注: 上式的证明可见这个知乎回答，另外最后一个不等号仅在 N≥2  且 k≥2  时成立。
即break point存在时增长函数上界是一个多项式，多项式的最高幂次项为 Nk–1 。

所以我们得到结论：如果break point存在，则增长函数 mH(N)  是多项式的。多项式的量级就比 2N  小多了，这就很容易保证式(1.3.3) 右边这个上界很小，学习就可行了!

3.3.3 VC界

上一小节提到如果break point存在，学习是可行的。既然如此，我们来回答一下2.2节最后提出的问题: 可不可以用 mH(N) 直接替换掉式(2.1.2)(2.1.2) 中的 effective(M)  呢，即式(2.2.1) 是否成立。

答案是不能直接替换,正确的不等式是

上式其实和式 (2.2.1) 差不多，其证明略显复杂我们暂不去探究，可参考此处。

式(2.3.1)(2.3.1)就是VC界，这个公式的意义在于：如果假设空间 H  存在有限的break point k ，即 mH(2N)  会被最高幂次为 k–1  的多项式上界给约束住，那么，随着 N  的逐渐增大，指数式 exp(⋅) 的下降会比多项式 mH(2N)  的增长速度更快，所以此时可以推断出VC界是有界的。更进一步，当 N  足够大时，对于 H  中的任意一个假设 g  ，Ein(g) 都将接近于 Eout(g) ，即学习是可行的。

3.4 VC维

现在，我们终于可以定义VC维了:

假设空间 H 的VC维是能被 H  打散的最大数据集的大小，即

VC(H)=max{N:mH(N)=2N} 

根据此定义，有 VC(H)=k−1 ，其中 k  是 H  的break point。

VC(H)=d  表明存在大小为 d  的数据集能被假设空间 H  打散，需要注意的是这并不意味着所有大小为 d  的数据集都能被 H  打散，例如二维平面上的所有直线构成的假设空间 H  的VC维为3，但是它并不能打散位于同一条直线上的三个点。事实上，VC维的定义与数据具体分布是无关的。

因为 VC(H)=k−1 ，所以由2.3.2节可知当 N≥2  且 k≥2  时，有

将上式代入(2.3.1) 的右边VC界有

所以，1.3节的可学习的两个核心条件等价于:

1. 学习算法 A  能够从 H  选出的假设 g  满足 Ein(g)≈0 。再结合条件2即达到了 Eout(g)≈0  的目标。
2. 假设空间 H  的VC维 VC(H)  是有限的且训练样本数 N  足够大。此时可保证式(2.4.2)右边上界趋于0，即学习算法 A  从 H  选出的任意假设 g  都满足 Ein(g)≈Eout(g) 。

VC维反映了函数集的学习能力，VC维越大，能学到的模型越复杂。根据前面的推导，我们知道VC维的大小与学习算法无关，与数据集的具体分布无关，与我们求解的目标函数也无关，只与模型和假设空间有关。另外，实践中有这样一个规律：一般情况下，假设空间的VC维约等于假设自由变量的数目。

3.5 Ein(g)  与 Eout(g) 的关系

令式(2.4.2) 右边的 4(2N)VC(H)exp(−18ϵ2N)=δ ，即坏事发生的概率

则可反解出
由(2.5.1)可得出，有 1−δ  的概率好事情会发生，好事情即
上式就是 Ein(g) 与 Eout(g)  的关系。其中，根号部分也可以看做模型的复杂度 ΩΩ，模型越复杂，Ein(g)  与 Eout(g)  离得越远。如图2.5所示，当固定样本数 N  时，随着VC维的上升，Ein(g)  会不断降低，而复杂度 ΩΩ 会不断上升，其上升与下降的速度在每个阶段都有所不同，因此我们要寻找一个二者兼顾的比较合适的VC维使 Eout(g)  最小。

 

   

此外，由上面的分析易知，样本数 N  也会影响 Eout(g) 。例如，当前有一个 VC(H)=3  的假设空间，要使 ϵ=0.1  且 δ=0.1 ，则要想满足式(2.5.2) ，可计算出理论上样本数 N  需要达到 10000VC(H) 这个量级，但实际应用中我们发现 N  达到 10VC(H)  就够了。这是因为，VC界是一个及其宽松的上界，因为它需要对任何学习算法，对任何数据分布，对任何目标函数都要成立,所以实际应用中的上界要比VC界小很多。

四、总结

总结一下本文的行文思路，

1. 先用Hoeffding不等式说明了可学习的两个条件:
   (1) 学习算法 A  能够从 H  选出的假设 g  满足 Ein(g)≈0 。
   (2) 假设空间 H  中假设数 M  是有限的且训练样本数 N  足够大。
2. 但假设空间 H  中假设数 M  往往是无穷大的。幸运的是，在推导出条件(2)时，我们要求假设空间的所有假设都是独立的，而假设空间 H  中独立假设数 effective(M) 却是有限的，增长函数告诉我们 effective(M)  的上界为 2N  。
3. 2N  这个上界还是太大了，学习还是很难可行。所以我们又引入了break point的概念，使 2N  的量级降为 Nk−1 , 由此得到了VC界。
4. 然后我们给出了VC维的定义，可学习的两个条件转变为:
   (1) 学习算法 A  能够从 H  选出的假设 g  满足 Ein(g)≈0 。
   (2) 假设空间 H  的VC维 VC(H)  是有限的且训练样本数 N 足够大。
5. 最后我们讨论了 Ein(g)  与 Eout(g)  的关系，发现为了使学习器更好(Eout(g) 更小)，要选择合适的VC维，不能太大也不能太小。

        因笔者自身水平实在有限，如果文章有任何的不妥，还请读者告之。此外，VC维可以说是机器学习中的一大核心，并非一篇博客就可以讲解透彻，所以本文也省略了一些复杂的证明，如果想深入理解可以去查阅相关书籍或论文。

参考

统计学习理论之VC维究竟是什么 | TangShusen

• 周志华《机器学习》第12章.计算学习理论
• 台大机器学习基石课程
• ECE 901 Lecture 19: The Proof of the Vapnik-Chervonenkis (VC) Inequality
• Computational Learning Theory - VC Dimension
• [陆勤学习]解读机器学习基础概念：VC维的来龙去脉