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

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

1. 可学习的条件

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

1.1 学习的过程

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

图1.1

图1.1中的 Eout(g)$E_{out}(g)$ 和 Ein(g)$E_{in}(g)$ 是两个重要的概念：

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

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

1.2 Hoeffding不等式

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

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

图1.2

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

P[|ν−μ|>ϵ]≤2exp(−2ϵ2N)(1.2.1)$$\begin{array}{}\text{(1.2.1)}& \mathbb{P}[|\nu -\mu |>ϵ]\le 2\exp \left(-2{ϵ}^{2}N\right)\end{array}$$

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

1.3 可学习的条件

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

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

P[|Ein(h)−Eout(h)|>ϵ]≤2exp(−2ϵ2N)(1.3.1)$$\begin{array}{}\text{(1.3.1)}& \mathbb{P}[|E_{in}(h)-E_{out}(h)|>ϵ]\le 2\exp (-2{ϵ}^{2}N)\end{array}$$

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

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

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

这里假定 H$\mathcal{H}$ 中有 M$M$ 个假设 h1,h2,…hM$h_1,h_2,\dots h_M$，则有如下推导:

P[E(h1)>ϵ∪E(h2)>ϵ …∪E(hM)>ϵ]≤P[E(h1)>ϵ]+P[E(h2)>ϵ] …+P[E(hM)>ϵ]≤2Mexp(−2ϵ2N)(1.3.2)$$\begin{gathered} \begin{array}{}\text{(1.3.2)}& \mathbb{P}[\mathbf{E}(h_1)>ϵ\cup \mathbf{E}(h_2)>ϵ\dots \cup \mathbf{E}(h_M)>ϵ] \\ \le \mathbb{P}[\mathbf{E}(h_1)>ϵ]+\mathbb{P}[\mathbf{E}(h_2)>ϵ]\dots +\mathbb{P}[\mathbf{E}(h_M)>ϵ] \\ \le 2M\exp (-2{ϵ}^{2}N)\end{array} \end{gathered}$$

其中 E(hi)=|Ein(hi)−Eout(hi)|$\mathbf{E}(h_i)=|E_{in}(h_i)-E_{out}(h_i)|$。

根据式 (1.3.2)$(\mathrm{1.3.2})$ 知

∀g∈H,P[|Ein(g)−Eout(g)|>ϵ]≤2Mexp(−2ϵ2N)(1.3.3)$$\begin{array}{}\text{(1.3.3)}& \mathrm{\forall }g\in \mathcal{H},\mathbb{P}[|E_{in}(g)-E_{out}(g)|>ϵ]\le 2M\exp (-2{ϵ}^{2}N)\end{array}$$

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

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

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

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

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

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

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

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

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

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

2. VC维

2.1 有效假设数

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

P(A1∪A2 …∪AM)≤∑i=1MP(Ai)(2.1.1)$$\begin{array}{}\text{(2.1.1)}& \mathbb{P}(A_1\cup A_2\dots \cup A_M)\le \sum _{i=1}^M\mathbb{P}(A_i)\end{array}$$

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

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

图2.1

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

图2.2

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

∀g∈H,P[|Ein(g)−Eout(g)|>ϵ]≤2⋅effective(M)exp(−2ϵ2N)(2.1.2)$$\begin{array}{}\text{(2.1.2)}& \mathrm{\forall }g\in \mathcal{H},\mathbb{P}[|E_{in}(g)-E_{out}(g)|>ϵ]\le 2\cdot \text{effective}(M)\exp (-2{ϵ}^{2}N)\end{array}$$

2.2 对分和增长函数

为了探究式(2.1.2)$(\mathrm{2.1.2})$中的 effective(M)$\text{effective}(M)$ ，先引入对分(dichotomy) 的概念:

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

h(X1,X2,…,XN)=(h(X1),h(X2),…,h(Xn))∈{+1,−1}N$$h(X_1,X_2,\dots ,X_N)=(h(X_1),h(X_2),\dots ,h(X_n))\in \{+1,-1{\}}^N$$

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

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

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

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

假设空间 H$\mathcal{H}$ 的增长函数 mH(N)$m_{\mathcal{H}}(N)$ 为

mH(N)=maxX1,X2,…,XN∈X|H(X1,X2,…,XN)|$$m_{\mathcal{H}}(N)=\underset{X_1,X2,\dots ,X_N\in \mathcal{X}}{max}|\mathcal{H}(X_1,X_2,\dots ,X_N)|$$

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

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

∀g∈H,P[|Ein(g)−Eout(g)|>ϵ]≤?2mH(N)exp(−2ϵ2N)(2.2.1)$$\begin{array}{}\text{(2.2.1)}& \mathrm{\forall }g\in \mathcal{H},\mathbb{P}[|E_{in}(g)-E_{out}(g)|>ϵ]\stackrel{?}{\le }2m_{\mathcal{H}}(N)\exp (-2{ϵ}^{2}N)\end{array}$$

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

2.3 VC界

2.3.1 打散(shatter)

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

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

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

图2.3

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

图2.4

2.3.2 break point

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

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

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

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

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

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

mH(N)≤B(N,k)≤∑i=0k−1(Ni)≤Nk−1$$m_{\mathcal{H}}(N)\le B(N,k)\le \sum _{i=0}^{k-1}(\genfrac{}{}{0ex}{}{N}{i})\le N^{k-1}$$

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

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

2.3.3 VC界

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

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

∀g∈H,P[|Ein(g)−Eout(g)|>ϵ]≤4mH(2N)exp(−18ϵ2N)(2.3.1)$$\begin{array}{}\text{(2.3.1)}& \mathrm{\forall }g\in \mathcal{H},\mathbb{P}[|E_{in}(g)-E_{out}(g)|>ϵ]\le 4m_{\mathcal{H}}(2N)\exp (-\frac{1}{8}{ϵ}^{2}N)\end{array}$$

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

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

2.4 VC维

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

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

VC(H)=max{N:mH(N)=2N}$$VC(\mathcal{H})=max\{N:m_{\mathcal{H}}(N)=2^N\}$$

根据此定义，有 VC(H)=k−1$VC(\mathcal{H})=k-1$，其中 k$k$ 是 H$\mathcal{H}$ 的break point。

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

因为 VC(H)=k−1$VC(\mathcal{H})=k-1$，所以由2.3.2节可知当 N≥2$N\ge 2$ 且 k≥2$k\ge 2$ 时，有

mH(N)≤NVC(H)(2.4.1)$$\begin{array}{}\text{(2.4.1)}& m_{\mathcal{H}}(N)\le N^{VC(\mathcal{H})}\end{array}$$

将上式代入(2.3.1)$(\mathrm{2.3.1})$的右边VC界有

∀g∈H,P[|Ein(g)−Eout(g)|>ϵ]≤4(2N)VC(H)exp(−18ϵ2N)(2.4.2)$$\begin{array}{}\text{(2.4.2)}& \mathrm{\forall }g\in \mathcal{H},\mathbb{P}[|E_{in}(g)-E_{out}(g)|>ϵ]\le 4(2N{)}^{VC(\mathcal{H})}\exp (-\frac{1}{8}{ϵ}^{2}N)\end{array}$$

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

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

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

2.5 Ein(g)$E_{in}(g)$ 与 Eout(g)$E_{out}(g)$ 的关系

令式(2.4.2)$(\mathrm{2.4.2})$右边的 4(2N)VC(H)exp(−18ϵ2N)=δ$4(2N{)}^{VC(\mathcal{H})}\exp (-\frac{1}{8}{ϵ}^{2}N)=\delta$，即坏事发生的概率

P[|Ein(g)−Eout(g)|>ϵ]≤δ(2.5.1)$$\begin{array}{}\text{(2.5.1)}& \mathbb{P}[|E_{in}(g)-E_{out}(g)|>ϵ]\le \delta \end{array}$$

则可反解出

ϵ=8Nln(4(2N)VC(H)δ)−−−−−−−−−−−−−−−−√(2.5.2)$$\begin{array}{}\text{(2.5.2)}& ϵ=\sqrt{\frac{8}{N}\ln \left(\frac{4(2N{)}^{VC(\mathcal{H})}}{\delta }\right)}\end{array}$$

由(2.5.1)可得出，有 1−δ$1-\delta$ 的概率好事情会发生，好事情即

Ein(g)−8Nln(4(2N)VC(H)δ)−−−−−−−−−−−−−−−−√≤Eout(g)≤Ein(g)+8Nln(4(2N)VC(H)δ)−−−−−−−−−−−−−−−−√(2.5.3)$$\begin{array}{}\text{(2.5.3)}& E_{in}(g)-\sqrt{\frac{8}{N}\ln \left(\frac{4(2N{)}^{VC(\mathcal{H})}}{\delta }\right)}\le E_{out}(g)\le E_{in}(g)+\sqrt{\frac{8}{N}\ln \left(\frac{4(2N{)}^{VC(\mathcal{H})}}{\delta }\right)}\end{array}$$

上式就是 Ein(g)$E_{in}(g)$ 与 Eout(g)$E_{out}(g)$ 的关系。其中，根号部分也可以看做模型的复杂度 Ω$\mathrm{\Omega }$，模型越复杂，Ein(g)$E_{in}(g)$ 与 Eout(g)$E_{out}(g)$ 离得越远。如图2.5所示，当固定样本数 N$N$ 时，随着VC维的上升，Ein(g)$E_{in}(g)$ 会不断降低，而复杂度 Ω$\mathrm{\Omega }$ 会不断上升，其上升与下降的速度在每个阶段都有所不同，因此我们要寻找一个二者兼顾的比较合适的VC维使 Eout(g)$E_{out}(g)$ 最小。

图2.5

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

3. 总结

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

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

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

参考

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