Vapnik-Chervonenkis Dimension 简论

Vapnik-Chervonenkis Dimension 是统计学习理论中刻画假设类容量的核心概念。本文从打散与增长函数出发，完整推导 Sauer–Shelah 引理与一致收敛泛化界，再讨论它为何在深度网络上失效，以及间隔界、PAC-Bayes、稳定性等替代方案如何回应这一困境。

先看一个只有 1 个参数的分类器：

h_\theta(x)=\operatorname{sign}\bigl(\sin(\theta x)\bigr),\qquad \theta\in\mathbb R.

它只有一个参数。但它的 VC 维是无穷大：对任意多的点，只要把这些点取在 $2^{-1},2^{-2},\dots,2^{-m}$ 上，就总存在一个 $\theta$ ，把任意指定的 $0/1$ 标注实现出来。反过来，一个有 2500 万参数的 ResNet-50，VC 维虽然有限，却大到让所有经典泛化界都变成一句废话——界大于 1，等于什么都没说。

这两个事实放在一起，说明「参数个数」和「容量」是两件不同的事。VC 维（Vapnik–Chervonenkis dimension）就是 Vapnik 与 Chervonenkis 在 1971 年为了把后者说清楚而发明的量：它不数参数，不假设分布，只看一个假设类作为「函数集合」的组合结构有多丰富。

本文的路线是：第一至四节把定义、Sauer–Shelah 引理、一致收敛定理这条逻辑链完整搭起来；第五至七节讨论它在深度学习里的处境——为什么界会空、空界是否意味着理论失效、今天用什么替代它；第八节清理一批常见误解。

一、学习问题

1.1 设定

设输入空间为 $\mathcal X$ ，标签空间为 $\mathcal Y=\{0,1\}$ 。一个假设是函数 $h:\mathcal X\to\{0,1\}$ ，一个假设类 $\mathcal H$ 是若干假设的集合。数据 $(x,y)$ 服从未知分布 $\mathcal D$ ，训练集

S=\{(x_1,y_1),\dots,(x_m,y_m)\}\sim\mathcal D^m

独立同分布地抽自 $\mathcal D$ 。

假设 $h$ 的真实风险与经验风险分别是

L_{\mathcal D}(h)=\mathbb P_{(x,y)\sim\mathcal D}\bigl[h(x)\neq y\bigr], \qquad L_S(h)=\frac1m\sum_{i=1}^m \mathbf 1\bigl[h(x_i)\neq y_i\bigr].

前者是我们真正关心但看不见的量，后者是能算出来的量。经验风险最小化（ERM）只做一件事：

h_S\in\arg\min_{h\in\mathcal H}L_S(h).

1.2 误差分解

对任意 $h^*\in\mathcal H$ ，把 $L_{\mathcal D}(h_S)$ 拆开：

\begin{aligned} L_{\mathcal D}(h_S) &=\bigl[L_{\mathcal D}(h_S)-L_S(h_S)\bigr]+L_S(h_S)\\ &\le \bigl[L_{\mathcal D}(h_S)-L_S(h_S)\bigr]+L_S(h^*)\\ &=\bigl[L_{\mathcal D}(h_S)-L_S(h_S)\bigr]+\bigl[L_S(h^*)-L_{\mathcal D}(h^*)\bigr]+L_{\mathcal D}(h^*)\\ &\le L_{\mathcal D}(h^*)+2\sup_{h\in\mathcal H}\bigl|L_{\mathcal D}(h)-L_S(h)\bigr|. \end{aligned}

第一项 $L_{\mathcal D}(h^*)$ 是近似误差：假设类里最好的那个假设有多好。第二项是估计误差：经验风险对真实风险的均匀偏差。

这个分解是整篇文章的地图。VC 理论只关心第二项。它不问你的网络能不能逼近目标函数——那是逼近论的问题；它只问：当你在 $\mathcal H$ 里挑一个经验风险最小的假设时，经验风险与真实风险的差距能被控制到什么程度。

1.3 一致收敛

如果对任意分布 $\mathcal D$ 和任意 $\varepsilon>0$ ，当 $m\to\infty$ 时

\Pr\left[\sup_{h\in\mathcal H}\bigl|L_{\mathcal D}(h)-L_S(h)\bigr|>\varepsilon\right]\to 0,

就说 $\mathcal H$ 具有一致收敛性（uniform convergence）。

$\sup$ 在概率里面，这个顺序很关键：不是「对每个 $h$ 分别收敛」，而是「所有 $h$ 同时收敛」。前者由大数定律自动成立，后者才是学习所需要的——因为 $h_S$ 本身依赖数据，你不能先固定 $h$ 再用大数定律。

于是问题变成：什么样的 $\mathcal H$ 具有一致收敛性？答案由 VC 维给出。

二、打散与 VC 维

2.1 二分

固定一个有限的点集 $C=\{c_1,\dots,c_m\}\subseteq\mathcal X$ 。 $\mathcal H$ 在 $C$ 上的限制（restriction）是

\mathcal H|_C=\bigl\{(h(c_1),\dots,h(c_m)):h\in\mathcal H\bigr\}\subseteq\{0,1\}^m.

这个集合里的每个元素称为一个二分（dichotomy）。 $|\mathcal H|_C|$ 最多是 $2^m$ 。如果取到 $2^m$ ，说明对这 $m$ 个点的每一种 $0/1$ 标注， $\mathcal H$ 里都有一个假设恰好实现它。

定义 2.1（打散）

若 $|\mathcal H|_C|=2^m$ ，称 $\mathcal H$ 打散（shatter）了 $C$ 。

定义 2.2（VC 维）

假设类 $\mathcal H$ 的 VC 维是它能打散的最大有限集的大小：

\operatorname{VCdim}(\mathcal H)=\sup\bigl\{m:\exists C\subseteq\mathcal X,\ |C|=m,\ \lvert\mathcal H|_C\rvert=2^m\bigr\}.

若右侧无界，则记 $\operatorname{VCdim}(\mathcal H)=\infty$ 。

请把定义里的量词读三遍：存在一个点集 $C$ ，使得对所有 $2^m$ 种标注，都存在 $h$ 。不是「对所有 $C$ 」，也不是「对某一种标注」。

这个「存在」是 VC 维最容易被误读的地方，也是它作为最坏情况度量的根源：它问的是假设类在某个精心挑选的点集上最多能变出多少花样，而不是它在典型数据上会怎么做。

2.2 几个例子

例 1（半直线， $\operatorname{VCdim}=1$ ）

取 $\mathcal H=\{x\mapsto\mathbf 1[x\ge t]:t\in\mathbb R\}$ ， $\mathcal X=\mathbb R$ 。

一个点 $C=\{0\}$ 显然可以被打散： $t\le 0$ 输出 $1$ ， $t>0$ 输出 $0$ 。

两个点 $x_1<x_2$ 则不行：标注 $(1,0)$ 要求 $t\le x_1$ 且 $t>x_2$ ，与 $x_1<x_2$ 矛盾。所以 VC 维是 $1$ 。

这个例子说明，VC 维和「能拟合多少点」不是一回事：半直线可以把任意多个点拟合成「前面全是 $0$ 、后面全是 $1$ 」的形状，但它只能实现 $m+1$ 种二分，远少于 $2^m$ 。

例 2（区间， $\operatorname{VCdim}=2$ ）

取 $\mathcal H=\{x\mapsto\mathbf 1[a\le x\le b]:a\le b\}$ 。

两个点 $x_1<x_2$ 可以被打散： $(1,1)$ 取 $a\le x_1,\ b\ge x_2$ ； $(1,0)$ 取 $a\le x_1,\ b\in[x_1,x_2)$ ； $(0,1)$ 取 $a\in(x_1,x_2],\ b\ge x_2$ ； $(0,0)$ 取一个避开两点的区间。

三个点 $x_1<x_2<x_3$ 不行：标注 $(1,0,1)$ 要求区间同时包含 $x_1$ 与 $x_3$ ，而区间是凸的，必然包含中间的 $x_2$ ，与中间的 $0$ 矛盾。

例 3（仿射超平面， $\operatorname{VCdim}=d+1$ ）

取 $\mathcal X=\mathbb R^d$ ， $\mathcal H=\{x\mapsto\operatorname{sign}(w\cdot x+b)\}$ 。

下界：取 $C=\{0,e_1,\dots,e_d\}$ ，这是 $d+1$ 个仿射无关的点。对任意标注 $y\in\{\pm1\}^{d+1}$ ，方程组

w\cdot x_i+b=y_i,\qquad i=1,\dots,d+1

有唯一解，因为以 $(x_i,1)$ 为列的 $(d+1)\times(d+1)$ 矩阵可逆。于是每种标注都能被某个仿射函数实现， $C$ 被打散。

上界： $\mathbb R^d$ 中任意 $d+2$ 个点都仿射相关，因此可以用 Radon 定理处理。

定理（Radon，1921）

$\mathbb R^d$ 中任意 $d+2$ 个点都可以分成两个不相交的子集，使二者的凸包相交。

证明很短。把点写成齐次坐标 $(x_i,1)\in\mathbb R^{d+1}$ ， $d+2$ 个向量线性相关，故存在不全为零的系数 $\alpha_i$ ，使

\sum_i \alpha_i x_i=0,\qquad \sum_i\alpha_i=0.

令 $P=\{i:\alpha_i>0\}$ ， $N=\{i:\alpha_i<0\}$ 。两者都非空，且

\sum_{i\in P}\alpha_i x_i=\sum_{i\in N}(-\alpha_i)x_i.

两边系数之和相同，记为 $A>0$ 。除以 $A$ ，得到同一点的两个凸组合表示，于是 $\operatorname{conv}(P)\cap\operatorname{conv}(N)\neq\varnothing$ 。

现在取标注「 $P$ 为正、 $N$ 为负」（系数为零的点任意归入一侧，它们不影响下面的凸组合）。任何包含 $P$ 的半空间都包含 $\operatorname{conv}(P)$ ；任何不包含 $N$ 的半空间，其补集是凸的，因而也不包含 $\operatorname{conv}(N)$ 。两者相交，矛盾。所以 $d+2$ 个点无法被打散， $\operatorname{VCdim}=d+1$ 。

这个证明值得记住：它把「线性分类器的容量」归结为「仿射无关点的最大数目」，而后者正是线性代数意义上的维数加一。VC 维里的「维」字，在这里有了具体的所指。

例 4（轴对齐矩形， $\operatorname{VCdim}=2d$ ）

$\mathcal H$ 是 $\mathbb R^d$ 中所有轴对齐矩形（即 $d$ 个区间的乘积）的指示函数。

上界：任取 $2d+1$ 个点。若存在一点 $p$ ，使它在每个坐标上都不是严格极值——即对每个坐标 $j$ ，都有别的点在 $p_j$ 的左边和右边——那么标注「 $p$ 为负、其余为正」无法实现：任何包含其余所有点的矩形，在每个坐标上的区间都必须覆盖 $p_j$ 两侧的值，因而必然包含 $p$ 。

这样的 $p$ 一定存在。否则每个点都在某个坐标上严格小于所有其他点、或严格大于所有其他点。把「坐标 $j$ 的最小值」和「坐标 $j$ 的最大值」看作 $2d$ 个位置，每个点占据其中一个；若两个点占据同一个位置，立刻矛盾（不可能同时严格小于对方）。 $2d+1$ 个点放进 $2d$ 个位置，必有一对冲突。所以上界成立。

下界是初等的但需要一点构造：确实存在 $2d$ 个点可以被矩形打散（ $d=2$ 时， $(1,2),(2,4),(3,1),(4,3)$ 这四个点就可以；注意不能取正方形的四个角）。于是 $\operatorname{VCdim}=2d$ 。

例 5（有限类， $\operatorname{VCdim}\le\log_2|\mathcal H|$ ）

若 $\mathcal H$ 有限且能打散 $C$ ，则 $2^{|C|}=|\mathcal H|_C|\le|\mathcal H|$ ，所以 $|C|\le\log_2|\mathcal H|$ 。

例 6（正弦类， $\operatorname{VCdim}=\infty$ ）

取 $\mathcal H=\{x\mapsto\operatorname{sign}(\sin(\theta x)):\theta>0\}$ ， $\mathcal X=\mathbb R$ 。对任意 $m$ ，取 $x_i=2^{-i}$ ，给定任意标注 $y\in\{\pm1\}^m$ ，令

\theta=\pi\left(\frac12+\sum_{i:\,y_i=-1}2^i\right).

对每个 $i$ ，把 $\theta x_i$ 对 $2\pi$ 取模。 $j>i$ 的项贡献 $2\pi$ 的整数倍，可以丢掉； $j=i$ 的项贡献 $\pi$ （当 $y_i=-1$ ）； $j<i$ 的项合并为 $\pi k_i/2^i$ ，其中 $0\le k_i\le 2^i-1$ 。于是

\theta x_i\equiv \pi\left(2^{-i-1}+\mathbf 1[y_i=-1]+\frac{k_i}{2^i}\right)\pmod{2\pi}.

当 $y_i=+1$ 时，括号内的值落在 $(0,1)$ ；当 $y_i=-1$ 时落在 $(1,2)$ 。所以 $\operatorname{sign}(\sin(\theta x_i))=y_i$ 。任意 $m$ 个点都能被打散，VC 维无穷。

一个参数，无穷容量。这就是「参数量不等于容量」最干净的反例。

例 7（最近邻， $\operatorname{VCdim}=\infty$ ）

1-NN 没有参数：给定训练集，它把测试点判为最近训练点的标签。给定任意有限点集 $C$ （点互不相同、没有距离并列）和任意标注，直接令训练集就是 $C$ 本身（标签按标注给）；对每个 $x_i$ ，最近邻是它自己，预测即标注。所以任意有限集都被打散，VC 维无穷。

这个例子说明，VC 维无穷并不妨碍一个算法在真实数据上表现良好；它只说明不存在一个对所有分布一致的泛化保证。

把上面几个例子汇总：

假设类	输入空间	VC 维
半直线	$\mathbb R$	$1$
区间	$\mathbb R$	$2$
仿射超平面	$\mathbb R^d$	$d+1$
轴对齐矩形	$\mathbb R^d$	$2d$
球	$\mathbb R^d$	$d+1$
有限类 $\mathcal H$	任意	$\le\log_2\lvert\mathcal H\rvert$
$\operatorname{sign}(\sin(\theta x))$	$\mathbb R$	$\infty$
1-NN	$\mathbb R^d$	$\infty$

注（怎么算）

对线性分类器，固定点集 $C=\{x_1,\dots,x_k\}$ ，对每个标注 $y\in\{\pm1\}^k$ 解可行性问题：是否存在 $(w,b)$ 使 $y_i(w\cdot x_i+b)\ge 1$ 对所有 $i$ 成立。这是一个线性规划。若 $2^k$ 个标注全部可行， $C$ 就被打散；对所有 $C$ 取最大，就得到 VC 维。对一般的假设类，精确判定通常是组合优化问题，实践中只能靠随机采样加优化或可满足性求解来估计。

2.3 三个误区

第一，「存在」不是「所有」。 定义只要求存在一个点集被打散。所以 VC 维大，不意味着假设类在任意数据上都很灵活；VC 维小，也不意味着它在某些特殊点集上不灵活。

第二，打散不是「能拟合这组数据」。 给定一组带标签的数据，几乎任何足够灵活的类都能拟合。打散要求的是：把这组点的标签换着花样全部试一遍，每一种都能实现。前者是插值能力，后者是组合丰富度。

第三，VC 维与参数化方式无关。 同一个函数集合可以有一万种参数化，VC 维不变。反过来，同一个参数数目可以对应 VC 维为 $1$ 的类，也可以对应 VC 维为 $\infty$ 的类。参数只是描述函数的一种方式，容量是函数集合本身的性质。

还有一点值得提前说明：上面定义的是二值函数类的 VC 维。如果假设输出实数（回归、概率、间隔），就需要 pseudo-dimension 或 fat-shattering dimension，后文会再提。

三、增长函数与 Sauer–Shelah 引理

3.1 增长函数

逐个点集去数二分太麻烦。我们只关心最坏情况下能产生多少种二分：

\Pi_{\mathcal H}(m)=\max_{C\subseteq\mathcal X,\ |C|=m}\bigl|\mathcal H|_C\bigr|.

它称为 $\mathcal H$ 的增长函数（growth function）。显然 $\Pi_{\mathcal H}(m)\le 2^m$ ，且 $\Pi_{\mathcal H}$ 单调不减。

由定义， $\operatorname{VCdim}(\mathcal H)$ 就是使 $\Pi_{\mathcal H}(m)=2^m$ 成立的最大的 $m$ （若对所有 $m$ 都成立，则为 $\infty$ ）。注意这个性质是「向下封闭」的：若 $C$ 被打散， $C$ 的任何子集也被打散，所以一旦 $\Pi(m)=2^m$ ，对所有 $k\le m$ 都有 $\Pi(k)=2^k$ 。

3.2 Sauer–Shelah 引理

定理 3.1（Sauer–Shelah）

若 $\operatorname{VCdim}(\mathcal H)=d<\infty$ ，则对任意 $m$ ，

\Pi_{\mathcal H}(m)\le\sum_{i=0}^{d}\binom{m}{i}.

证明用归纳法，对 $m+d$ 归纳。取任意 $C=\{c_1,\dots,c_m\}$ ，记 $C'=C\setminus\{c_m\}$ 。把 $\mathcal H|_C$ 按最后一个坐标分成两类：

$A_0$ ：最后一个坐标为 $0$ 的二分；
$A_1$ ：最后一个坐标为 $1$ 的二分。

设 $A_0$ 与 $A_1$ 在 $C'$ 上的投影的交集大小为 $s$ ，则

|\mathcal H|_C|=|A_0|+|A_1|\le \Pi_{\mathcal H}(m-1)+s.

交集里的每个二分，都对应 $C'$ 上一种「最后一位可以任意翻转」的模式。把这些模式组成的集合记为 $\mathcal H''$ 。若 $\mathcal H''$ 打散了 $C'$ 的某个 $d$ 元子集，那么 $\mathcal H$ 就打散了该子集并上 $\{c_m\}$ ，共 $d+1$ 个点，矛盾。所以 $\operatorname{VCdim}(\mathcal H'')\le d-1$ ，从而 $s\le\Pi_{\mathcal H''}(m-1)\le\sum_{i=0}^{d-1}\binom{m-1}{i}$ 。

代回并用 Pascal 公式：

\Pi_{\mathcal H}(m)\le\sum_{i=0}^{d}\binom{m-1}{i}+\sum_{i=0}^{d-1}\binom{m-1}{i} =\sum_{i=0}^{d}\binom{m}{i}.

证毕。

3.3 多项式增长

当 $m\ge d$ 时，上述和式可以被一个更粗但更好用的界控制：

\sum_{i=0}^{d}\binom{m}{i}\le\left(\frac{em}{d}\right)^d.

推导只需一步：因为 $m/d\ge 1$ ，

\sum_{i=0}^{d}\binom{m}{i} \le\sum_{i=0}^{d}\binom{m}{i}\left(\frac{m}{d}\right)^{d-i} \\ =\left(\frac{m}{d}\right)^d\sum_{i=0}^{d}\binom{m}{i}\left(\frac{d}{m}\right)^{i} \le\left(\frac{m}{d}\right)^d\left(1+\frac{d}{m}\right)^m \le\left(\frac{em}{d}\right)^d.

这条引理是整个理论的枢纽：它把「组合上的有限性」翻译成「数量上的多项式增长」。VC 维有限的假设类，在 $m$ 个点上最多只有 $m^d$ 种行为，而不是 $2^m$ 种。当 $m$ 增大时，这两种增长速度的差距是压倒性的—— $m^d$ 取对数后只有 $d\log m$ ，而 $2^m$ 取对数后是 $m$ 。

换句话说，有限 VC 维等价于增长函数是多项式级的。这就是「容量」一词的数学来源：容量不是参数个数，而是假设类能产生的二分数量随样本量的增长速度。

四、一致收敛定理

4.1 对称化

增长函数是组合量，要把它变成泛化界，需要一步概率论证，称为对称化（symmetrization）。

设 $S'$ 是与 $S$ 独立同分布的另一组 $m$ 个样本。核心不等式是

\sup_{h\in\mathcal H}\bigl|L_{\mathcal D}(h)-L_S(h)\bigr| \;\lesssim\; \mathbb E_{S,S'}\sup_{h\in\mathcal H}\bigl|L_S(h)-L_{S'}(h)\bigr|,

意思是：真实风险与经验风险的偏差，本质上不会比两组经验风险之间的偏差更大。这一步用的是集中不等式（McDiarmid 不等式），代价是概率意义上的常数因子。

接着引入独立同分布的 Rademacher 变量 $\sigma_i\in\{\pm1\}$ 。由于 $\sigma_i$ 的对称性，

\mathbb E_{S,S'}\sup_{h}\left|\frac1m\sum_{i=1}^m\bigl(\ell_h(z_i)-\ell_h(z'_i)\bigr)\right| \;\le\; 2\,\mathbb E_{S,\sigma}\sup_{h}\left|\frac1m\sum_{i=1}^m\sigma_i\,\ell_h(z_i)\right|,

其中 $\ell_h(z)=\mathbf 1[h(x)\neq y]$ 。右侧就是 Rademacher 复杂度 $\mathfrak R_m(\mathcal H)$ ，它度量的是：给每个样本随机翻一个符号，假设类还能拟合得多好。随机符号是纯噪声，能拟合噪声就说明容量大。

对二值函数类，Rademacher 复杂度可以被增长函数控制：

\mathfrak R_m(\mathcal H)\le\sqrt{\frac{2\log\Pi_{\mathcal H}(m)}{m}}.

这一步用的是有限类的 Massart 引理：把 $\mathcal H$ 限制到样本上，最多只有 $\Pi_{\mathcal H}(m)$ 种不同的二分，再用 union bound 或鞅不等式。

4.2 泛化界

把上面的估计串起来，得到本文唯一需要记住的公式。当 $m\ge d$ 时，

L_{\mathcal D}(h)\;\le\;L_S(h)\;+\;C\sqrt{\frac{d\log(m/d)+\log(1/\delta)}{m}},

以至少 $1-\delta$ 的概率对所有 $h\in\mathcal H$ 同时成立，其中 $d=\operatorname{VCdim}(\mathcal H)$ ， $C$ 是某个绝对常数。

不同教材的常数和 $\log$ 里的具体形式略有出入（常见的一种写法是把 $d\log(m/d)$ 换成 $d\log(2em/d)$ ），但量级是一致的。重要的是它的结构：

分子里的 $d$ 是容量， $\log(1/\delta)$ 是置信度；
分母里的 $m$ 是样本量；
整个界以 $1/\sqrt m$ 的速度下降。在 agnostic 设定下，这个速度是最优的：存在匹配的下界，样本量再少就不可能保证同样的一致收敛。

把 $\Pi_{\mathcal H}(2m)$ 用 Sauer 界代入，就得到只依赖 VC 维的形式。再把它代回误差分解，就得到 ERM 的泛化保证。

4.3 基本定理

定理 4.1（统计学习基本定理）

对二分类、 $0$ - $1$ 损失、分布无关（distribution-free）的设定，以下四条等价：

$\operatorname{VCdim}(\mathcal H)<\infty$ ；
$\mathcal H$ 具有一致收敛性；
ERM 是 agnostic PAC 一致的；
$\mathcal H$ 是 agnostic PAC 可学习的。

在可实现（realizable）情形下，有限 VC 维同样等价于 PAC 可学习。这个定理把「组合上的有限性」和「统计上的可学习性」严格地焊在了一起：在分布无关的框架里，有限 VC 维不只是充分条件，而是充要条件。

4.4 样本复杂度

由上面的界解出 $m$ ，得到 agnostic 情形下的样本复杂度：

m=\Theta\left(\frac{d+\log(1/\delta)}{\varepsilon^2}\right),

可实现情形下则是

m=\Theta\left(\frac{d+\log(1/\delta)}{\varepsilon}\right).

这两个 $\Theta$ 是双向的：上界由 ERM 达到，下界则是信息论下界——存在一个分布，使任何算法都需要这么多样本。所以 VC 维不仅给出了一个可用的界，还在 minimax 意义下给出了最优的样本复杂度量级。

这一点很重要。很多人批评 VC 界「太松」，但在分布无关、最坏情况的设定里，它并不松：你不可能用更少的样本保证同样的一致收敛。问题不在于界本身，而在于这个设定是否匹配你关心的场景。

五、VC 维的含义

到这里，数学已经完整了。但公式正确不等于理解。这一节把 VC 维的语义拆成五句话。

第一，它是 min-max 的。 定义里的 $\sup_C$ 对应界里的 $\sup_{\mathcal D}$ 。VC 理论先让对手选一个最坏的分布，再让对手选一个最坏的点集，然后问：你还剩什么保证？所以它天生悲观。它给出的不是一个典型情形下的估计，而是一个任何情形下都不被打破的承诺。

第二，它是充要的。 在 $0$ - $1$ 损失、二分类、要求对所有分布一致的框架里，有限 VC 维精确刻画了可学习性。它不是「一个充分但过强的条件」；它就是那个条件。问题不在定理，而在框架。

第三，它是组合量，概率只出现在最后一步。 打散、增长函数、Sauer 引理都是纯组合的，与分布、与概率无关；对称化把组合量变成概率界。这也解释了为什么 VC 维对数据长什么样一无所知：它的输入只有假设类的集合结构。

第四，它衡量的是「能实现多少种二分」，不是「能拟合多复杂的函数」。 一个类可以 VC 维无穷却在某个分布上表现很好（1-NN），也可以 VC 维很小却拟合得很差（区间无法实现 $(1,0,1)$ 这种标注）。VC 维是容量，不是质量。

第五，它是上界，不是预测。 $L_{\mathcal D}\le L_S+\cdots$ 是一个保证（guarantee），不是一个估计（estimate）。当界大于 $1$ 时，它没有说「误差很大」，它只是没有信息。把泛化界当成测试误差的预测器，是误用的常见来源。

这五句话合起来，解释了为什么 VC 理论在深度学习时代显得「失灵」：它回答的是一个比深度学习实际面对的问题更难的问题。深度网络不是在一个任意的分布上学习，而是在图像、文本、语音这些有强结构的分布上学习；不是用任意算法，而是用 SGD 及其变体；不是在整个假设类里搜索，而是在一个由初始化、架构和训练动力学共同决定的子集里搜索。VC 维对这三件事都不敏感。

六、深度学习中的 VC 维

6.1 参数量估算

把上一节的界套到实际模型上，只需估算 $\sqrt{d/m}$ 的量级（暂时把 $d$ 低估成参数量 $W$ ，忽略 $\log$ 因子）：

模型	参数量 $W$	训练样本 $m$	$\sqrt{W/m}$
LeNet-5（MNIST）	$6\times10^4$	$6\times10^4$	$\approx 1$
ResNet-18（ImageNet）	$1.17\times10^7$	$1.28\times10^6$	$\approx 3.0$
ResNet-50（ImageNet）	$2.56\times10^7$	$1.28\times10^6$	$\approx 4.5$
ViT-L/16（ImageNet）	$3.07\times10^8$	$1.28\times10^6$	$\approx 15.5$

每一个都在 $1$ 附近或远大于 $1$ 。一个「错误率上界」一旦达到或超过 $1$ ，就等于什么都没说——它连「模型会犯错」这种同义反复都不如，因为它没有排除任何东西。而且这还是把 VC 维低估成参数量的结果；下一小节会看到，深度网络的 VC 维还要乘上 $\log$ 因子。

有人会说：那就把界改紧一点。但问题不是常数，是量级。ImageNet 有 128 万张训练图，ResNet-50 有 2560 万参数， $m$ 比 $d$ 小二十倍。任何以 $d$ 为主项的界，在这个区间里都只能给出与 $1$ 同阶或更大的量级。 这是样本量与容量之间的量级失配，不是分析技巧的问题。

6.2 深度网络的 VC 维

先确认一件事：深度网络的 VC 维是有限的。只要参数个数有限、激活函数是分段多项式（ReLU、Leaky ReLU、MaxOut 都是），VC 维就有限。深度网络并不是一个无限容量的对象。

那么它有多大？

阈值网络。 Baum 与 Haussler（1989）证明，由阈值门组成的多层网络，VC 维是 $O(W\log W)$ ，其中 $W$ 是权重个数。 $\log$ 因子来自网络内部的分段线性结构：不同的权重符号组合对应不同的线性区域，区域数量随 $W$ 组合增长。
ReLU 网络。 Bartlett、Harvey、Liaw 与 Mehrabian（2019）给出 $O(WL\log W)$ 的上界（ $L$ 为层数），并给出几乎匹配的下界 $\Omega(WL\log(W/L))$ ；伪维（pseudo-dimension）同阶。

结论很清楚：深度网络的 VC 维随参数线性增长（乘一个 $\log$ ）。 「深度学习之所以泛化，是因为它的 VC 维很小」这个流行说法是错的。深度网络和线性模型一样，容量随参数增长；区别在于，深度网络的实际泛化误差可以远小于这个容量所暗示的上界。

另一个方向的反例是 1-NN：VC 维无穷，但在很多分布上表现并不差。这说明 VC 维无穷并不等于「不能用」；它只意味着不存在一个对所有分布一致的保证。

6.3 三条出路

既然「整个假设类的 VC 维」给不出有用的话，理论就往三个方向走。

（a）把容量做得更细：从假设类到算法输出

与其用整个 $\mathcal H$ 的 VC 维，不如用「训练解所在的那个小子类」的容量。

线性情形是最好的例子。若 $\lVert x\rVert\le R$ 、 $\lVert w\rVert\le B$ ，且分类间隔至少为 $\gamma$ ，则有效容量约为 $(RB/\gamma)^2$ ，与输入维度 $d$ 无关。这正是 SVM 的理论基础：在高维甚至无限维的特征空间里，只要间隔大，容量就小。

深度网络有类似的谱范数版本。把 $\lVert w\rVert$ 换成各层谱范数的乘积 $\prod_l\lVert W_l\rVert_\sigma$ ，再乘上深度和宽度带来的多项式因子、除以间隔，就得到 Bartlett–Foster–Telgarsky（2017）与 Neyshabur 等人（2018）的界。这类界的形式大致是「分子为谱范数乘积的平方，分母为间隔与样本量」；它们在经过特殊正则的小网络上可以非空，但在标准训练的 ImageNet 网络上仍然空泛。

覆盖数（covering number）是同一思想的度量几何版本：VC 维回答「能打散多少点」，覆盖数回答「用多少个半径为 $\varepsilon$ 的球能把假设类盖住」。二者通过 Dudley 熵积分相连。

PAC-Bayes 则把容量变成了「后验与先验的距离」。对任意后验分布 $Q$ （通常是训练后权重的分布），以 $1-\delta$ 的概率，

\mathbb E_{h\sim Q}\bigl[L_{\mathcal D}(h)\bigr] \;\le\; \mathbb E_{h\sim Q}\bigl[L_S(h)\bigr] \;+\;O\!\left(\sqrt{\frac{\mathrm{KL}(Q\Vert P)+\log(1/\delta)}{m}}\right).

这里的复杂度不再是假设类的 VC 维，而是「训练后的分布 $Q$ 离先验 $P$ 有多远」。Dziugaite 与 Roy（2017）用它在 MNIST 规模的网络上算出了非空的界，这是 PAC-Bayes 在深度网络上最早显示出实际内容的结果之一。

压缩是另一条路：若训练好的网络可以被压缩成 $k$ 比特而不改变其在训练集上的预测，则泛化误差约为 $\sqrt{k/m}$ 。Zhou 等人（2019）用剪枝加量化的压缩方案，在 ImageNet 规模上给出了非空（但仍然很松）的界。「非空」是里程碑，但离「解释」还很远。

稳定性 则把容量挂在算法上：若算法对替换一个样本不敏感，泛化误差就可以被稳定性系数控制（Bousquet–Elisseeff，2002）。Hardt、Recht 与 Singer（2016）把这一框架用到了 SGD 上。

这些界的共同点很重要：它们中的大多数不再是纯粹「假设类」的属性，而是「算法输出」或「数据」的属性。 容量从单一的 $\mathcal H$ 转移到了假设类、算法、数据三者共同决定的整体上。

（b）算法偏置：SGD 只在一个很小的子集里搜索

$\mathcal H$ 很大，但 SGD 不是均匀地在 $\mathcal H$ 里搜索。从初始化出发、沿着梯度的方向、在有限步内，它只能到达 $\mathcal H$ 的一个很小的子集。

线性可分的情形已经被严格刻画：梯度下降收敛到最大间隔解（Soudry 等，2018），即使假设类包含所有线性分类器。深度网络里也有大量关于隐式正则的工作，试图说明梯度方法偏向于某种「最小范数」或「最大间隔」的解。

神经正切核（NTK）提供了一个更清晰的图景：当网络宽度趋于无穷时，训练动力学等价于核回归，泛化由核的谱和 RKHS 范数控制。这把容量从参数空间搬到了函数空间：不是问「有多少个参数」，而是问「在核的度量下，解有多大的范数」。

但要小心：NTK 只描述「懒惰训练」（lazy regime），即特征几乎不变的情形。真实网络会学特征，这时 NTK 不再适用，隐式偏置的理论也远未完成。这是当前深度学习理论最核心的开放问题之一。

（c）数据分布：最坏情况太坏

VC 界对每个分布都成立，因此必须按最坏的分布来定价。真实数据不是最坏的：图像有低维结构，类别之间有间隔，长尾分布有层次。

双下降（double descent）是一个典型现象：当模型容量、训练时间或样本量越过插值阈值时，测试误差可以出现第二次下降，而不是经典 U 形曲线预言的那样一路变差（Belkin 等，2019；Nakkiran 等，2020）。需要注意，经典理论从来没有证明过 U 形曲线——它只是小模型时代的经验总结；双下降也不「推翻」VC 理论，它只是说明在 $d$ 随 $m$ 变化的区域，偏差 - 方差分解的直觉不再适用。

良性过拟合（benign overfitting）则更反直觉：在高维线性回归中，最小范数插值器可以是一致的，只要数据协方差的谱衰减得足够快（Bartlett、Long、Lugosi、Tsigler，2020）。「插值」不等于「过拟合」——这是一个已经被严格证明的现象，而它的成立强烈依赖数据分布的具体性质。

这些结果都指向同一件事：泛化不是假设类单独的性质，而是假设类、算法、分布三者共同的性质。VC 维只看到了第一个。

6.4 一致收敛的局限

还有一条更根本的批评。Nagarajan 与 Kolter（2019）构造了一类学习问题，使得真实泛化误差可以很小，但任何基于一致收敛的界都必然很大。换句话说，「把 VC 界改紧」这条路存在原理性的上限。

这不是说他们的构造代表了真实网络，而是说：要解释深度学习，必须放弃「对所有假设一致」的要求，转而利用算法或分布的结构。一致收敛是一个充分条件，不是必要条件。

这里有一个容易被忽略的逻辑细节：对二分类 $0$ - $1$ 损失，有限 VC 维确实是 PAC 可学习的充要条件。所以如果深度网络在分布无关的意义下可学，它的 VC 维必须有限——而它确实有限。逻辑上没有矛盾；矛盾只在「界」与「实际」的巨大差距。VC 理论没有被证伪，它只是没有提供我们想要的那种解释。

七、容量度量谱系

在前面的讨论里，VC 维一直默认假设输出是二值的。对实值函数类（回归、概率输出、间隔），它不能直接使用。标准的替代有两种：把实值函数按阈值二值化后取 VC 维，得到 pseudo-dimension；或者要求在某个尺度 $\gamma$ 下仍能打散，得到 fat-shattering dimension。后者是间隔理论的正式语言：一个类完全可以在 VC 维意义下无穷，却在每个固定的 $\gamma$ 下只有有限的 fat-shattering 维数——这正是「间隔大则容量小」的精确表述。

把上面提到的各种度量放在一张表里，可以看到它们各自回答的是不同的问题。

度量	度量对象	核心思想	典型界	主要局限
VC 维	二值函数类	最大打散集	$\sqrt{(d+\log(1/\delta))/m}$	分布无关、最坏情况、只适用 $0$ - $1$ 损失
增长函数	二值函数类	限制类的最大规模	Sauer 多项式界	组合量，需要再转概率
Pseudo-dimension	实值函数类	阈值化后的 VC 维	与 VC 同阶	仍是最坏情况
Fat-shattering	实值函数类	尺度 $\gamma$ 下的打散	间隔界	依赖尺度选择
覆盖数	度量空间	用 $\varepsilon$ -球覆盖	Dudley 熵积分	计算困难
Rademacher 复杂度	数据相关	随机符号下的拟合能力	$2\mathfrak R+\sqrt{\log(1/\delta)/m}$	需要估计，通常偏松
PAC-Bayes	后验与先验	KL 复杂度	$\sqrt{(\mathrm{KL}+\log(1/\delta))/m}$	先验的选择
稳定性	算法	替换一个样本的影响	稳定性系数 $\beta$	对 SGD 难以验证
压缩	算法输出	描述长度	$\sqrt{k/m}$	需要构造压缩方案
NTK / RKHS 范数	核函数	函数空间中的范数	谱条件	只适用于懒惰训练

这张表想说明一件事：「容量」不是一个数，而是一个依设定而变的函数。 你选择哪种度量，等于选择了对「什么算简单」的回答。VC 维的回答是「组合上简单」，间隔界的回答是「几何上简单」，PAC-Bayes 的回答是「相对先验简单」，压缩的回答是「描述上简单」。它们不是互相替代的关系，而是从不同角度逼近同一个问题。

结语

回到开头那两个数字。一个只有 1 个参数的正弦分类器可以有无限 VC 维；一个 2500 万参数的 ResNet 却只能在 ImageNet 上得到一个大于 1 的界。这两件事并不矛盾，它们从两个方向说明了同一件事：容量不是参数的函数，而是假设类结构的函数；泛化不是容量的函数，而是容量、算法与分布三者共同的函数。