Computational Learning Theory - VC Dimension

Posted on   |   In   |     |   views

在计算学习理论里面，有一个比较重要的概念，那就是VC维（Vapnic-Chervonenkis Dimension）。它解释了机器学习算法为什么可以去学习，数据又为什么可以被学习。在机器学习领域，VC维可以说是一个非常基础的定量化概念，可用来刻画分类系统的性能，也因此给诸多机器学习方法的可学习性提供了坚实的理论基础。网上有许多讲解VC维的博文，自己在学习VC维的时候也搜到很多，数量多的同时质量难免也良莠不齐。所以在这里，强烈推荐一下pluskid写的关于VC theory 的系列文章，总结的确实非常深入。

由于pluskid的VC维系列比较深入，如果有一定的数学基础，那么学起来倒不难，但对初学者来说可能就比较困难。不过，不用担心，还有一份比较好的入门级学习教程，就是林轩田老师的《机器学习基石》，该课程前面几堂课讲的都是VC维，并且林老师讲解VC维时将理论与实例结合在一起，以讲故事的形式来阐述VC维，极力推荐一下，的确值得一听。有兴趣的同学可以去Google找找资料，这里推荐一个学者在听课过程中总结的笔记“《机器学习基石课程笔记》“。然而，虽然目前已经有很多前辈都透彻地阐述了VC维，但要想将知识转为己有，就必须自己反复地去琢磨，去回顾归纳并去总结。本文对于VC维而言可以说是冰山一角，想要更全面地理解VC维，还请读者前去查阅与VC维有关的paper。此外，本文主要以总结为主，理论上的证明将不会过多的涉及，内容则主要围绕下面几点展开：

  1. Hoeffding Inequality
  2. Probably Approximately Correct Learnable
  3. Vapnic-Chervonenkis Dimension
    • Growth function
    • Dichotomy
    • Shatter && Break point
    • VC dimension

最近，在总结VC维的时候，脑海中总会浮现以下几个问题，确切的说，这也是VC维能够解决的事情（当然，不同的人会有不同的想法，或者携带的问题会更多）：

  1. 为什么机器学习方法可以学习？
  2. 为什么会出现过拟合？
  3. 机器学习模型的复杂度如何衡量？

下面根据上文提到的几点，来对各个要点逐个展开。

Hoeffding Inequality

Hoeffding不等式是一个关于一组随机变量均值的概率不等式。

Hoeffding Inequality：设$X_1, X_2,\cdot, X_n$为一组独立同分布的随机变量，满足$X_i \epsilon [a, b], 0 \leq i \leq n $，$n$为随机变量的个数。记$n$个随机变量的经验期望 $\bar{X} = \frac{X_1 + X_2 + \cdots + X_n}{n}$，则对于任意的$0<\delta<1$, Hoeffding不等式可以表示为:

$$ P(\bar{X} - E(\bar{X}) \geq \epsilon ) \leq exp \left (\frac{-2 n \epsilon ^{2} }{(b-a)^{2}} \right ) \tag{1} \label{1}$$

在上述式子中，注意到$X_i$的取值范围是$[a, b]$，当分类误差为$0-1$损失时，$a$和$b$分别对应到$0$和$1$，此时，方程$\eqref{1}$简化为

$$ P(\bar{X} - E(\bar{X}) \geq \epsilon ) \leq exp\left(-2 n \epsilon ^{2} \right ) \tag{2}$$

或

$$ P( \left | \bar{X} - E(\bar{X}) \right | \geq \epsilon ) \leq 2 exp \left (-2 n \epsilon ^{2} \right ) \tag{3} \label{3}$$

如果单纯的从概率的角度来看，Hoeffding 不等式刻画的是某个随机事件的真实概率及其$n$个独立重复试验中观察到的频率之间的差异。换言之，它是$n$个不同伯努利（Bernoulli）试验的应用。那么现在的问题是：对于这样一个不等式，如何将其与机器学习联系在一起呢？

首先，机器学习的目的是从合理数量的训练数据中，通过合理的计算量可靠的学习到知识。换句话说，就是从已有的数据中使用算法从假设空间$\mathcal{H}$中选择一个最好的$g$，虽然这个$g$很好，但它与样本真实的目标函数$f$存在一定的区别，从而导致训练时产生error。为了方便起见，我们将机器学习是在训练时会产生的训练误差叫做$E_{in}(g)$，当样本量为$n$时（从某个data set中有放回的抽取$n$次，最终未抽到的样本为out-of-sample），其表达式为：

$$ E_{in}(g) = \frac{1}{n} \sum_{i=1}^{n} l(g, X_i, y_i) \tag{4}$$

类似地，我们把out-of-sample的产生的误差叫做$E_{out}(g)$，表达式为

$$E_{out}(g) = \mathbb{E}_{P_{xy}} \left [ l(g, X, Y) \right ] \tag{5}$$

因此，可以将Hoeffding 不等式应用到$E_{in}$和$E_{out}$，公式$\eqref{3}$可化为式$\eqref{6}$

$$ P( \left | E_{in} - E_{out} \right | \geq \epsilon ) \leq 2 exp \left (-2 n \epsilon ^{2} \right ) \tag{6} \label{6}$$

公式$\eqref{6}$表达了算法学习到的$g$属于bad model的概率。换言之，当右边这个“upper bound”足够小时，我们可以说$g$在sample中的表现(错误率)与$g$在总体中的表现是差不多的。然而，对于假设空间$\mathcal{H}$中一个固定的$h$ 而言，$E_{in}(h)$会与$E_{out}(h)$很接近，这种情况能说是一种好的learning吗？答案当然是不能的，因为如果$E_{in}(h)$很大，则$E_{out}(h)$也大，这种学习得到的结果显然意义不大。

然而，不幸的是，在实际的采样过程中，我们可能会碰到bad sample（凡是由于抽样误差所造成样本分布与总体分布相差很大的样本，我们都可以称之为bad sample。）,从而造成训练时选择的$g$并非我们想要的。So，bad sample发生的概率有多大呢？当假设空间$\mathcal{H}$有$M$个可以学习的函数时，每个函数发生bad sample的概率为$\leq 2exp\left ( -2 \epsilon^2 n \right )$，如果每个$M$都出现了bad sample，则出现bad sample总概率为：

$$ \begin{aligned} \mathbb{P}_{\mathcal{D}}[BAD\ \mathcal{D}]
& = \mathbb{P}_{\mathcal{D}}[BAD\ \mathcal{D}\ for\ h_1\ or\ BAD\ \mathcal{D}\ for\ h_2\ or\ …\ or\ BAD\ \mathcal{D}\ for\ h_M]\\
\ & \leq \mathbb{P}_{\mathcal{D}}[BAD\ \mathcal{D}\ for\ h_1] + \mathbb{P}_{\mathcal{D}}[BAD\ \mathcal{D}\ for\ h_2]+…+\mathbb{P}_{\mathcal{D}}[BAD\ \mathcal{D}\ for\ h_M] \\
\ & \leq 2exp(-2\epsilon ^2n) + \leq 2exp(-2\epsilon ^2n) + … + \leq 2exp(-2\epsilon ^2n) \\
\ & = 2Mexp(-2\epsilon ^2n)
\end{aligned} \tag{7} \label{7}
$$

由公式$\eqref{7}$的推导可以看出，我们的算法learning得好不好，还与假设空间$\mathcal{H}$里决策函数的个数$M$有关。当$M$有限时，那么数据量$n$越大，发生bad sample的可能性越低。同理如果$M$太大，遇到bad sample的概率也会越大。

综上所述，从概率论的角度出发，根据Hoeffding不等式，可以证明当$E_{in}(h)$与$E_{out}(h)$很接近，同时$E_{in}(h)$与$E_{out}(h)$都比较小的时候，那么机器学习算法是可learning的。在learning的过程中，如果$E_{in}(h)$明显的小于$E_{out}(h)$，那么我们的模型便发生overfiting了；相反，如果$E_{in}(h)$本身就特别大，那么我们把这种情况称作underfitting。

Probably Approximately Correct Learnable

为了简便起见，这里以分类场景为例。

假定$f$表示样本的真实“概念”，是从样本空间$X$到类别空间$Y$的映射，它决定了样本$x$的真实标记$y$，如果对于任意的样例$(x, y)$，都有$f(x)=y$成立，则称$f$为目标概念。在训练过程中，由于我们并不确定算法是否能够找到真正的$f$，因此将算法学到的概念称作“假设（hypotheses）”，那么算法考虑的所有可能的“hypotheses”便构成了假设空间（hypotheses space，记作$\mathcal{H}$）。理想的情况下，我们希望最终学习得到的模型$g (g \in \mathcal{H})$可以与$f$等价$(g \equiv f)$，以0误差完美的做出决策，但在现实中，这种情况很难发生，原因有三：

  • 有限的训练样本数决定了训练模型的上限；
  • 从分布$D$采样得到的数据具有一定的偶然性，因此不同大小的训练集，得到的结果也可能有所不同；
  • 训练数据中可能存在bad sample，导致训练时发生一定的误导性；

因此，为了尽可能达到预设上限的模型，我们需要弱化我们对学习器的要求，不要求学习器能够输出零错误率的假设，只要求错误率以置信度为$\delta$被限制在某个可以接受的常数$\varepsilon$范围内，并且$\varepsilon$越小越好。简而言之，我们只要求学习器可以以较大的概率（至少是1-$\delta$）学习到一个“近似正确（Approximately Correct）”的假设，这就是“Probably Approximately Correct”的由来，简称“PAC”。形象的描述

PAC Identify：给定$0 < \varepsilon,\delta <１$，对于所有的$f \in \mathcal{F}$ 和数据分布$D$，若学习算法的输出空间$g \in \mathcal{H}$满足

$$P(E(g) \leq \varepsilon) \geq 1 - \delta$$

则称学习算法能从假设空间$\mathcal{H}$中以较大的概率$(\geq 1 - \delta)$学习到目标概念$f$的近似假设（误差最多为$\varepsilon$），简称PAC Identify。

当有了上述条件，便可以得到PAC Learnable的定义：

PAC Learnable: 令$n$表示从分布$\mathcal{D}$中独立同分布采样得到的样本数，假设空间为$\mathcal{H}$，真实概念类为$\mathcal{F}$，且$0 < \varepsilon,\delta <１$，对于分布$\mathcal{D}$，若存在学习算法$\Psi $和多项式函数$poly(.,.,.,.)$，使得对于任意的$n \geq poly( \frac{1}{\varepsilon}, \frac{1}{\delta}, size(x), size(f))$，算法$\Psi$能够从假设空间$\mathcal{H}$中PAC Identify 真实概念类$\mathcal{F}$，则称概念类$\mathcal{F}$对假设空间$\mathcal{H}$而言是PAC可学习的。

从PAC可学习的定义可以看出，训练样本的数量与学习所需的计算资源密切相关。我们称满足PAC学习算法$\Psi$所需的$n \geq poly( \frac{1}{\varepsilon}, \frac{1}{\delta}, size(x), size(f))$中最小的$n$为学习算法$\mathcal{\Psi}$的样本复杂度。假定学习器对每个训练样本需要某个最小的处理时间，那么如果要使目标函数$g$是PAC可学习的，学习器就必须在多项式数量的训练样本中进行学习。

Vapnic-Chervonenkis Dimension

前面提到了假设空间$\mathcal{H}$，当假设空间比较多时，此时式$\eqref{6}$就变成了

$$\sum_{h \in \mathcal{H}} P(\left | E_{in}(h) - E_{out}(h) \right | \geq \epsilon) \leq 2 \color{red}{ \left | \mathcal{H} \right |} exp \left ( -2n \epsilon^2 \right ) \tag{8} \label{8}$$

其中$\left | \mathcal{H} \right |$是假设空间的大小。根据式$\eqref{8}$可以看出，当$\left | \mathcal{H} \right |$比较大时，经验误差$E_{in}(h)$和泛化误差$E_{out}(h)$逼近的概率也就越大，然而与此同时，我们想要从hypotheses space中选择出一条很好的假设就比较困难；相反，如果$\left | \mathcal{H} \right |$比较小，经验误差$E_{in}(h)$和泛化误差$E_{out}(h)$逼近的概率也就越小了。所以，为了找到一个折衷的衡量经验误差与泛化误差逼近程度的表达式，我们需要对$\left | \mathcal{H} \right |$进行转化。因此，VC维便诞生了。

在进入VC维之前，先引入下面几个概念：

  • Dichotomy
  • Growth function
  • Shatter && Break point

Dichotomy

首先来看看dichotomy的定义：

Dichotomy： 给定hypotheses space$\mathcal{H}$和样本集$D = \lbrace x_1, x_2, \cdots, x_n \rbrace $， 假设从$\mathcal{H}$中任意选择一个方程$h$，并让$h$对$D$进行二元分类，最后输出一个结果向量，我们把这个输出向量称为一个Dichotomy。

例如，在$2\mathbb{D}$平面空间，用一条直线对$2$个点进行binary classification，输出可能的结果为$ \lbrace 1,–1 \rbrace $，$ \lbrace –1,1 \rbrace$，$ \lbrace 1,1 \rbrace $，$ \lbrace–1,–1 \rbrace$，每个结果对都是一个dichotomy。对于二分类而言，Dichotomy最多有$2^n$种可能。

虽然hypotheses space 中$\left | \mathcal{H} \right |$可以很大，但有效的假设$h$（即dichotomy）是有限的，于是，我们可以用dichotomy的有效数量来取代有限hypotheses space 的Hoeffding不等式中的$\left | \mathcal{H} \right |$，即

$$\sum_{h \in \mathcal{H}} P(\left | E_{in}(h) - E_{out}(h) \right | \geq \epsilon) \leq 2 \cdot \color{red}{effective(n)} \cdot exp \left ( -2n \epsilon^2 \right ) \tag{9} \label{9}$$

Growth function

由于dichotomy最多有$2^n$种可能，因此当样本量$n$增加时，dichotomy的可能结果数也会增加。对于所有的$n \in \mathbb{N}$, 假设空间$\mathcal{H}$的growth function $\mathbb{G}_{\mathcal{H}} (n)$为

$$\mathbb{G}_{\mathcal{H}} (n) =\underset{\lbrace x_1, x_2, \cdots, x_n \rbrace \subseteq X }{ max} \left | \lbrace (h(x_1), h(x_2), \cdots, h(x_n) | h \epsilon \mathcal{H} \rbrace \right | \tag{10} \label{10}$$

对于式子$\eqref{10}$，$\mathbb{G}_{\mathcal{H}} (n) $的upper bound是$2^n$。更严格一点为下式

$$
\begin{aligned}
\mathbb{G}_{\mathcal{H}}(n)\leq \sum_{i=0}^{d_{vc}}\binom {n}{i}\leq n^{d_{vc}} ,
\textit{( for }n\geq 2, d_{vc}\geq 2\textit{ )}
\end{aligned}
\tag{11} \label{11}$$

当Growth function表示假设空间$\mathcal{H}$对$n$个示例所能赋予标记的最大可能的结果数。显然，结果数越多，$\mathcal{H}$的表达能力越强。由此可见，growth function描述的是假设空间$\mathcal{H}$的表达能力，尽管$\mathcal{H}$可能包含无穷多个假设，但其对$D$中示例赋予标记的可能结果数是有限的。

Shatter && Break point

有了Growth function和Dichotomy的概念之后，下面我们来定义Shatter：

当假设空间$\mathcal{H}$作用于$n$个输入样本集时， 产生的dichotomy的数量等于这$n$个点总的组合数$2^n$，也就是Growth function的取值为$2^n$，即$\mathbb{G}_{\mathcal{H}} (n) = 2^n$，此时我们就称这$n$个输入被hypotheses space $\mathcal{H}$“Shatter”。

在一些资料中，“shatter”被翻译为“打散”。对于break point这个概念，使用下面这个例子来说明，会更加直观。

假定在某个枪击游戏中，你有一把散弹枪，每个关卡里面都只装有$6$颗子弹，而敌人的数量会随着关卡的不同而不同，具体数量为$2^i$，$i$为关卡号。现在，进入第一关时，敌人的数量为$2^1 = 2$个，很明显你可以shatter掉所有敌人并可以轻松过关；当进入第二关时，敌人数量为$2^2 = 4$，你也可以勉强过关；但是当你进入第三关时，敌人数量为$2^3 = 8$个，而你的子弹数只有$6$颗，此时你就无法通过散弹枪顺利过关了。我们把这个关卡$3$就叫做break point。

VC dimension

了解了growth function、dichotomy、shatter、break point这些概念之后，这时，我们也可以使用growth function来估计$E_{in}$和$E_{out}$的关系，式$\eqref{9}$变为下式：

$$\sum_{h \in \mathcal{H}} P(\left | E_{in}(h) - E_{out}(h) \right | \geq \epsilon) \leq \color{red}{4 \cdot \mathbb{G}_{\mathcal{H}} (2n) } \cdot exp \left ( - \color{red}{\frac{1}{8}}n \epsilon^2 \right ) \tag{12} \label{12}$$

式$\eqref{11}$就是我们的VC bound。这个公式的意义在于：如果假设空间$\mathcal{H}$存在有限的break point $k$，那么$\mathbb{G}_{\mathcal{H}} (2n) $会被最高幂次为$k–1$的多项式上界给约束住。随着$n$的逐渐增大，指数式$exp(*)$的下降会比多项式$\mathbb{G}$的增长速度更快，所以此时可以推断出VC Bound是有界的。更进一步，当$n$足够大时，对于$\mathcal{H}$中的任意一个假设$h$，$E_{in}(h)$都将接近于$E_{out}(h)$，表示学习是可行的。

现在，我们现在可以定义VC维了，此概念由Vladimir Vapnik与Alexey Chervonenkis提出。

VC Dimension：给定假设空间$\mathcal{H}$，它的VC维是能被$\mathcal{H}$ shatter的最大实例集大小$n$，
$$VC(\mathcal{H}) = max \lbrace n: \mathcal{G}_{\mathcal{H}}(n) = 2^n \rbrace $$

简而言之，若存在大小为$n$的示例集能被假设空间$\mathcal{H}$打散，但不存在任何大小为$n+1$的示例集能被$\mathcal{H}$打散，则假设空间$\mathcal{H}$的VC维是$n$。此时，break point为$n+1$。若对于任意数目的样本都有$2^n$个函数能将它们打散，则函数集的VC维是无穷大。

由于寻找所有hypothesis space的growth function是困难的，因此我们使用$n^{d_{vc}}$作为hypothesis space中所有$VC(\mathcal{H})=d_{vc}$的growth function的上界。So，对于hypothesis space $\mathcal{H}$的任意一个$g$来说，都有：

$$
\begin{aligned};;;,
\mathbb{P}[|E_{in}(g) - E_{out}(g) \ge \epsilon|]
&\leq \mathbb{P}[BAD] \\
&= \mathbb{P}[\exists h \in \mathcal{H}\text{ s.t. } |E_{in}(h)-E_{out}(h)|\ge \epsilon] \\
&\leq 4\mathbb{G}_{\mathcal{H}}(2n) exp \left ( - \frac{1}{8} n\epsilon^2 \right ) \\
&\leq 4(2n)^{d_{vc}}exp \left (- \frac{1}{8} n\epsilon^2 \right ) , (\textit{ if }d_{vc}\textit{ is finite })
\end{aligned}
\tag{13} \label{13}$$

因此，如果想要让机器学到东西，并且学习得到的结果比较好，就得满足三个条件：

  1. Good $\mathcal{H}$：假设空间$\mathcal{H}$的VC维$d_{vc}$是有限的;
  2. Good $D$：适中的样本量$n$，这样才能确保vc bound的不会太大；
  3. Good $\Psi$：一个好的算法，确保能够从假设空间$\mathcal{H}$中挑选出一个能使$E_{in}$最小的函数$g$。

VC维反映了函数集的学习能力，VC维越大，学习机器越复杂。根据前面的推导，我们知道VC维的大小：与学习算法$\Psi$无关，与输入变量$X$的分布也无关，与我们求解的目标函数$g$无关，只与模型和假设空间$\mathcal{H}$有关。实践中有这样一个规律：假设空间 $\mathcal{H}$的VC 维与假设参数$w$的自由变量数目大约相等。即$VC(\mathcal{H}) = free \ parameters$。

最后，令之前得到的VC Bound为$\delta$，则坏事情发生的概率$P[|E_{in}(g)−E_{out}(g)|>\epsilon] \le \delta$，好事情发生的概率$P[|E_{in}(g)−E_{out}(g)|≤\epsilon] \ge 1−\delta$，从而可以推导出$\epsilon$：

$$
\begin{aligned}
&P[|E_{in}(g)-E_{out}(g)|\ge \epsilon] \le \delta \\
\Rightarrow
&P[|E_{in}(g)-E_{out}(g)|\leq \epsilon] \ge 1 - \delta \\
&\text{set};;;;
\delta = 4(2n)^{d_{vc}}exp(-\frac{1}{8}n\epsilon^2)\\
\Rightarrow
& \epsilon = \sqrt{\frac{8}{n}ln(\frac{4(2n)^{d_{vc}}}{\delta})}
\end{aligned}
\tag{14} \label{14}$$

根据$\eqref{14}$的结果，进而可以推导出$E_{in}$与$E_{out}$的关系：

$$
E_{in}(g)-\sqrt{\frac{8}{n}ln(\frac{4(2n)^{d_{vc}}}{\delta})} \leq E_{out}(g) \leq E_{in}(g)+ \color{red}{ \underset{\Omega }{\underbrace{\sqrt{\frac{8}{n}ln(\frac{4(2n)^{d_{vc}}}{\delta})}}}}
\tag{15} \label{15}$$

当然，我们比较关心的还是$E_{out}$的上界，式$\eqref{15}$红色部分为模型的复杂度$\Omega$，模型越复杂，$E_{in}$与$E_{out}$的逼近程度越远。随着VC维的上升，$E_{in}$会不断降低，而$\Omega$项会不断上升，其上升与下降的速度在每个阶段都有所不同，因此我们能够寻找一个二者兼顾的，比较合适的$d_{vc}$，用来决定应该使用多复杂的模型。反过来，如果我们需要使用$d_{vc}=3$这种复杂度的模型，并且想保证$\epsilon=0.1$，置信度$1−\delta=0.9$，我们也可以通过VC Bound来求得大致需要的数据量$n$。通过简单的计算可以得到，理论上我们需要$n \approx 10,000d_{vc}$大小的数据量，但VC Bound事实上是一个极为宽松的bound，因为它对于任何演算法$\Psi$，任何分布的数据$D$，以及任何目标函数$g$都成立，所以经验上，常常认为$n \approx 10d_{vc}$就可以有不错的结果。

另外，还可以从VC维的角度解释正则项的作用。在训练的时候，我们是从假设空间$\mathcal{H}$中寻找最佳的$g$时，然而为了避免overfiting，通常会加上正则项。当正则项加入之后，新的hypotheses space会加入一些新的bound，这时新假设空间的VC维也将变小。换言之，对于同样的训练数据，$E_{in}$更有可能等于$E_{out}$，从而泛化能力变得更强。

Conclusion

虽然本文大致的叙述了VC维，但因笔者自身水平有限，很多东西仅仅只是一隅之见，理解的并不到位，如果有措辞上的不妥，还请读者告之。此外，VC维可以说是机器学习中的一大核心，并非一篇文章就可以讲解透彻，本文相对于VC维而言，仅仅是冰山一角，如果想深入理解的，还请前去查阅相关paper。

References