【数学基础笔记】什么是VC维?

定义

VC维(外文名 Vapnik-Chervonenkis Dimension)的概念是为了研究学习过程一致收敛的速度和推广性(Generalization performance),由统计学理论定义的有关函数集学习性能的一个重要指标.

简单来说,VC维是用来衡量研究对象(数据集与学习模型)可学习性的指标.

如何理解可学习性?

机器学习的学习过程

基本概念

\(\mathcal{A}\) 表示学习算法, 可以理解为包含损失函数的优化算法
\(f\) 表示学习的目标假设(可以是一个函数,也可以是一个分布)
\(\mathcal{H}\)表示假设空间
\(g\) 表示求解的用来预测的假设,\(g \in \mathcal{H}\)
机器学习算法: \(\mathcal{A} + \mathcal{H}\)

机器学习的过程就是:通过算法 \(\mathcal{A}\) 在假设空间 \(\mathcal{H}\) 中,根据训练样本集 \(\mathcal{D}\) 选择最好的假设作为 \(g\) 使 \(g\) 近似于 \(f\).

针对机器学习中需要关注的要素: 训练集, 测试集和学习算法

对于训练集来说,训练集要足够大,才能使结果收敛.
对于测试集来说,测试集要有足够的代表性,不能偏差太大.
对于学习算法来说,要足够复杂,以表达特征(X值)与学习目标(y值)之间的逻辑关系.

经过归纳为 \(E_{out}(g)\) 和 \(E_{in}(g)\) 是两个重要的概念:

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

机器学习的目标即为 \(E_{out}(g) \approx E_{in}(g) \approx 0\), 问题在于无法估计 \(E_{out}(g)\)

假设训练集和测试集是从同一个分布中取出的,这其实是PAC假设中的一条.PAC(Probably Approximately Correct)是一个学习框架,包含许多条假设.其中,训练集和测试集取自同一分布,训练集样本是独立同分布取出的,是最重要的两条假设.

结论: 模型的可学习型,只与数据量与模型复杂度有关.与具体的研究对象,输入数据(X)的分布都无关.

Hoeffding不等式

举例: 设瓶子里的橙色球占比为 \(\mu\)(可看做\(E_{out}(g)\)),从瓶子中随机抽取出 \(N\) 个样本,这N个样本中橙色球占比是 \(\upsilon\)(可看做\(E_{in}(g)\)).

这里也可以将 \(\mu\) 看为总体期望,而 \(\upsilon\) 为样本期望

直觉上如果 \(N\) 越大,样本期望与总体期望是愈发接近的,这里可以用Hoeffding不等式表示

\[ \mathbb{P}[|\nu - \mu| > \epsilon] \leq 2 \exp \left(-2 \epsilon^2 N \right) \tag{1.2.1} \]

由公式可知: 当样本 \(N\) 越大,大于误差 \(\epsilon\) 也就越发接近 0.即样本期望与总体期望近似相等.

可学习的条件

对于任意固定的假设 \(h\),当训练样本量 \(N\) 足够大,可以通过样本集上的经验误差 \(E_{in}(h)\) 推测总体的期望误差 \(E_{out}(h)\).基于hoeffding不等式, 可得

\[ \mathbb{P}[|E_{in}(h) - E_{out}(h)| > \epsilon] \leq 2 \exp(-2 \epsilon^2 N) \tag{1.3.1} \]

当 \(N\) 足够大时,\(E_{in}(h)\) 和 \(E_{out}(h)\) 将非常接近.

注意: 针对某一个特定的假设 \(h\).在我们的假设空间 \(\mathcal{H}\) 中,往往有很多个假设(甚至于无穷多个).那么对于假设空间 \(\mathcal{H}\) 中的任意的假设 \(h\),\(E_{in}(h)\) 和 \(E_{out}(h)\) 之差大于 \(\epsilon\) 的概率的上界会是什么?

这里在<机器学习基石>中存在一个例子即为一个人扔硬币五次正面朝上的概率为 \(\frac{1}{32}\), 而150个人各扔五次,存在一次正面朝上的概率为 \(1-(\frac{31}{32})^150 > 99\%\),说明对于总体而言独特的情况出现的概率是非常高的,而在此时获得5次正面朝上这个人的样本来推算整体均为硬币朝上,样本和总体的偏差就会非常大.

假定 \(\mathcal{H}\) 中有 \(M\) 个假设 \(h_1,h_2,\cdots,h_M\),则有如下推导:

\[ \begin{aligned} \mathbb{P}[\mathbf{E}(h_1)> \epsilon \cup \mathbf{E}(h_2)> \epsilon \space \cdots \cup \mathbf{E}(h_M)> \epsilon] &\leq \mathbb{P}[\mathbf{E}(h_1)> \epsilon] + \mathbb{P}[\mathbf{E}(h_2)> \epsilon] \space \cdots + \mathbb{P}[\mathbf{E}(h_M)> \epsilon] \\ &\leq 2M\exp(-2 \epsilon^2 N) \end{aligned} \tag{1.3.2} \]

其中: \(\mathbf{E}(h_i) = |E_{in}(h_i) - E_{out}(h_i)|\)

因此得到整体最为关键的公式

\[ \forall g \in \mathcal{H}, \mathbb{P}[|E_{in}(g) - E_{out}(g)| > \epsilon] \leq 2M \exp(-2 \epsilon^2 N) \tag{1.3.3} \]

结论: 在假设空间 \(\mathcal{H}\) 中,对于任意一个假设 \(g\),\(E_{in}(g)\) 和 \(E_{out}(g)\) 之差大于 \(\epsilon\) 的概率的上界是 \(2M \exp(-2 \epsilon^2 N)\).注意这个上界与训练样本数 \(N\) 和假设空间假设数 \(M\) 密切相关.

由此可得可学习性的核心条件:

学习算法 \(\mathcal{A}\) 能够从 \(\mathcal{H}\) 选出的假设 \(g\) 满足 \(E_{in}(g) \approx 0\).
假设空间 \(\mathcal{H}\) 中假设数 \(M\) 是有限的且训练样本数 \(N\) 足够大.保证学习算法 \(\mathcal{A}\) 从 \(\mathcal{H}\) 选出的任意假设 \(g\) 都满足 \(E_{in}(g) \approx E_{out}(g)\).

分析 \(M\) 的大小对于两个条件的满足情况:

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

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

VC维

有效假设数

针对一个二分类问题, 假定数据集二维数据点的数量为 \(N\)

\(N = 2\), 假设空间 \(\mathcal{H}\) 的无数条直线可将其分为 4 类
\(N = 3\), 假设空间 \(\mathcal{H}\) 的无数条直线可将其分为 8 类(三点为直线时仅为 6 类)
\(N = 4\), 假设空间 \(\mathcal{H}\) 的无数条直线可将其分为 14 类(而非 \(2^N\) )

结论: 可知虽然假设空间 \(\mathcal{H}\) 的 \(M\) 一般非常大, 但在特定样本集上,其有效假设数目是有限的

\[ \forall g \in \mathcal{H}, \mathbb{P}[|E_{in}(g) - E_{out}(g)| > \epsilon] \leq 2 \cdot effective(M) \cdot \exp(-2 \epsilon^2 N) \tag{2.1.1} \]

增长函数与对分

对分: \(\mathcal{H}\) 中的假设对 \(\mathcal{D}\) 中数据赋予标记的每种可能结果称为对数据集 \(\mathcal{D}\) 的一种对分.

针对假设空间 \(\mathcal{H} = \{h: \mathcal{X} \rightarrow \{+1, -1\}\}\), 当 \(N = 4\)并且数据为二维时

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

上述对分的数据中存在着对数据集 \(\mathcal{D}\) 的依赖,为了去除依赖,引入 增长函数(growth function)

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

\[ m_{\mathcal{H}}(N) = \underset{X_1,X2, \cdots ,X_N \in \mathcal{X}}{max} |\mathcal{H}(X_1, X_2, \cdots ,X_N)| \tag{2.2.1} \]

\(m_{\mathcal{H}}(N)\) 越大,\(\mathcal{H}\) 的表示能力越强.因此,增长函数描述了假设空间 \(\mathcal{H}\) 的表示能力,由此反映出假设空间的复杂度.

VC 界

在该部分引入更多的概念

打散(shatter): 当假设空间 \(\mathcal{H}\) 作用于大小为 \(N\) 的样本集 \(\mathcal{D}\) 时,产生的对分数量等于 \(2^N\) 即 \(m_{\mathcal{H}}(N)=2^N\) 时,就称 \(\mathcal{D}\) 被 \(\mathcal{H}\) 打散了.
break point: 对于假设空间 \(\mathcal{H}\) 的增长函数 \(m_{\mathcal{H}}(N)\) ,从 \(N=1\) 出发逐渐增大,当增大到 \(k\) 时,出现 \(m_{\mathcal{H}}(N)<2^N\) 的情形,则 \(k\) 是该假设空间的 break point.

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

\[ m_{\mathcal{H}}(N) \le B(N,k) \le \sum_{i=0}^{k-1}{N \choose i} \le N^{k-1} \tag{2.3.1} \]

该公式可推断 break point 存在时增长函数上界是一个多项式,多项式的最高幂次项为 \(N^{k-1}\).

结论:如果 break point 存在,则增长函数 \(m_{\mathcal{H}}(N)\) 是多项式的.多项式的量级就比 \(2^N\) 小多了, 此时学习就可行!

此时给出 VC 界的概念和公式:

\[ \forall g \in \mathcal{H}, \mathbb{P}[|E_{in}(g) - E_{out}(g)| > \epsilon] \leq 4 m_{\mathcal{H}}(2N) \exp(-\frac18 \epsilon^2 N) \tag{2.3.2} \]

如果假设空间 \(\mathcal{H}\) 存在有限的 break point \(k\),即 \(m_{\mathcal{H}}(2N)\) 会被最高幂次为 \(k-1\) 的多项式上界给约束住,那么,随着 \(N\) 的逐渐增大,指数式 \(exp(\cdot)\) 的下降会比多项式 \(m_{\mathcal{H}}(2N)\) 的增长速度更快,所以此时可以推断出VC界是有界的.

结论: 当 \(N\) 足够大时,对于 \(\mathcal{H}\) 中的任意一个假设 \(g\) ,\(E_{in}(g)\) 都将接近于 \(E_{out}(g)\),即学习是可行的.

VC 维

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

\[ VC(\mathcal{H}) = \max \{ N: m_{\mathcal{H}}(N) = 2^N\} \]

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

注意: 并不意味着所有大小为 \(d\) 的数据集都能被 \(\mathcal{H}\) 打散.例如二维的三点共线,就不可以.事实上,VC维的定义与数据具体分布是无关的.

因为 \(VC(\mathcal{H}) = k - 1\), 当 \(N \geq 2\) 且 \(k \geq 2\) 时, 有

\[ m_{\mathcal{H}}(N) \le N^{VC(\mathcal{H})} \tag{2.4.1} \]

将上式代入式(2.3.2)可得

\[ \forall g \in \mathcal{H}, \mathbb{P}[|E_{in}(g) - E_{out}(g)| > \epsilon] \leq 4 (2N)^{VC(\mathcal{H})} \exp(-\frac18 \epsilon^2 N) \tag{2.4.2} \]

思考

\(E_{in}(g)\) 与 \(E_{out}(g)\) 的关系

令 式(2.4.2) 右边\(4 (2N)^{VC(\mathcal{H})} \exp(-\frac18 \epsilon^2 N) = \delta\),即坏事发生的概率

\[ \mathbb{P}[|E_{in}(g) - E_{out}(g)| > \epsilon] \leq \delta \tag{3.1.1} \]

则可反解出

\[ \epsilon = \sqrt{\frac 8 N \ln \left( \frac {4(2N)^{VC(\mathcal{H})}} \delta \right)} \tag{3.1.2} \]

由 式(3.1.1) 有 \(1-\delta\) 的概率好事情会发生,好事情即

\[ 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)} \tag{3.1.3} \]

结论: 模型越复杂,\(E_{in}(g)\) 与 \(E_{out}(g)\) 离得越远.

如图3, 当固定样本数 \(N\) 时,随着VC维的上升,\(E_{in}(g)\) 会不断降低,而复杂度会不断上升,其上升与下降的速度在每个阶段都有所不同,因此要寻找一个二者兼顾的比较合适的VC维使 \(E_{out}(g)\) 最小.

注意: 样本数 \(N\) 也会影响 \(E_{out}(g)\).

例如,当前有一个 \(VC(\mathcal{H})=3\) 的假设空间,要使 \(\epsilon=0.1\) 且 \(\delta=0.1\),则要想满足 式(3.1.2),可计算出理论上样本数 \(N\) 需要达到 \(10000VC(\mathcal{H})\) 这个量级,但实际应用中发现 \(N\) 达到 \(10VC(\mathcal{H})\) 就够了.

因为VC界是一个极其宽松的上界,因为它需要对任何学习算法,对任何数据分布,对任何目标函数都要成立,所以实际应用中的上界要比VC界小很多.

公式推导

式(2,3,1) 证明

首先针对 \(B(N, K)\) 存在如下等式

\(B(N, 1) = 1\)
当 \(N < k\), \(B(N , k) = 2^N\)
当 \(N = k\), \(B(N , k) = 2^N - 1\), 因为 \(N\) 是第一个不能被打散的点

针对 \(N > k\) 的情况, 利用 \(B(4, 3)\) 举例

其中可以得出

\[ B(4, 3) = 2 \times \alpha + \beta \]

其中 \(\alpha\) 为后面 \(x_4\) 可成对的部分(橘色), \(\beta\) 为后面 \(x_4\) 不可成对部分(紫色).

由于定义, 可知 \(B(4, 3)\) 不能被任意三点打散,那么\(B(3, 3)\) 也应当是

\[ \alpha + \beta \leq B(3, 3) \]

由于 \(\alpha\) 部分, \(x_4\) 可成对即为打散, 那么

\[ \alpha \leq B(3, 2) \]

最终得出

\[ B(4, 3) = 2 \times \alpha + \beta \leq B(3, 3)+ B(3, 2) \]

由数学归纳法得

\[ B(N, k) = 2 \times \alpha + \beta \leq B(N - 1, k)+ B(N - 1, k - 1)\leq\sum_{i=0}^{k-1}{N \choose i} \le N^{k-1} \]

式(2,3,2) 证明

如果存在 \(E_{in}(h)\), 使得 \(|E_{in}(h) - E_{out}(h)| > \epsilon\)

在VC维中的证明为 VC维公式证明

替代无穷总体空间

假定存在一个与 \(E_{in}(h)\) 同大小的 \(E_{in}'(h)\) 数据(重新抽取的), 那么样本之间的误差与样本与总体之间的误差如下式

\[ \frac{1}{2} P(\exists h \in \mathcal{H}\; s.t.|E_{in}(h) - E_{out}(h)| > \epsilon) \leq P(\exists h \in \mathcal{H}\; s.t.|E_{in}(h) - E'_{in}(h)| > \frac{\epsilon}{2}) \]

最大泛化差距大于\(\epsilon\)的概率几乎是 \(\mathcal{D}\) 与 \(\mathcal{D}'\) 之间的经验风险差概率大于 \(\frac{\epsilon}{2}\)的两倍,这被称作对称引理.

分解假设空间的种类

\[ \begin{aligned} BAD &\leq 2 \times P(\exists h \in \mathcal{H}\; s.t.|E_{in}(h) - E'_{in}(h)| > \frac{\epsilon}{2}) \\ &\leq 2 m_{\mathcal{H}}(2N) \times P(fixed h \in \mathcal{H}\; s.t.|E_{in}(h) - E'_{in}(h)| > \frac{\epsilon}{2}) \end{aligned} \]

使用无取回的霍夫丁不等式

\[ \begin{aligned} BAD &\leq 2 m_{\mathcal{H}}(2N) \times P(fixed h \in \mathcal{H}\; s.t.|E_{in}(h) - E'_{in}(h)| > \frac{\epsilon}{2}) \\ &\leq 2 m_{\mathcal{H}} \times 2 \exp(-2(\frac{\epsilon}{4})^2N) \end{aligned} \]