Vapnik-Chervonenkis Dimension 简论

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

它只有一个参数。但它的 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$，训练集

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

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

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

1.2 误差分解

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

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

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

1.3 一致收敛

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

就说 $\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）是

这个集合里的每个元素称为一个二分（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}$，方程组

有唯一解，因为以 $(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$，使

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

两边系数之和相同，记为 $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$，令

对每个 $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$。于是

当 $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 维无穷并不妨碍一个算法在真实数据上表现良好；它只说明不存在一个对所有分布一致的泛化保证。

把上面几个例子汇总：

注（怎么算） 对线性分类器，固定点集 $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 增长函数

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

它称为 $\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$，则

交集里的每个二分，都对应 $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 公式：

证毕。

3.3 多项式增长

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

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

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

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

四、一致收敛定理

4.1 对称化

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

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

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

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

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

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

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

4.2 泛化界

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

以至少 $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）的设定，以下四条等价：

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

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

4.4 样本复杂度

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

可实现情形下则是

这两个 $\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$ 因子）：

每一个都在 $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$ 的概率，

这里的复杂度不再是假设类的 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 维的回答是「组合上简单」，间隔界的回答是「几何上简单」，PAC-Bayes 的回答是「相对先验简单」，压缩的回答是「描述上简单」。它们不是互相替代的关系，而是从不同角度逼近同一个问题。

结语

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