统计学习理论与 PAC 学习

机器学习最基本的问题不是"怎么把训练数据拟合好"——那件事平凡到可以用一张查找表完成。真正的问题是：为什么在训练集上表现好的模型，在没见过的数据上也会表现好？

这个问题看起来像哲学（休谟的归纳问题），但从 1984 年起它有了一个数学答案的框架。莱斯利·瓦利安特那一年提出可能近似正确（Probably Approximately Correct，PAC）学习：不要求学到的假设完全正确，只要求它以高概率（probably）近似正确（approximately correct），并且要求达到这个目标所需的样本量与时间是可控的。

这个看似退让的定义，第一次让"学习"成为可以被证明与被否证的计算问题。

破除误解：泛化不是"数据够多就行"#

第一个误解是把泛化归因于数据量。 数据量当然重要，但决定性的量是样本量与假设空间复杂度的比值。一个能表达任意函数的模型，无论给多少数据都可以完美拟合训练集而对新数据一无所知；一个只能表达线性函数的模型，几十个样本就足以稳定。学习的可能性来自限制——你事先排除了多少种可能的解释。

第二个误解是把"训练误差低"当作学到了东西。 统计学习理论的全部张力在于分解：

$$\text{泛化误差} \le \text{训练误差} + \text{复杂度惩罚项}$$

前一项可以靠拟合压低，后一项只能靠限制假设空间或增加样本压低。任何声称同时改善两者的做法都值得怀疑——它通常意味着复杂度被藏在了别处（比如藏在数据预处理、超参数搜索或模型选择的过程里）。

第三个误解是把理论界当作实用预测。 经典泛化界给出的数值往往极其松弛——对现代深度网络，它们预测的误差上界经常大于 1（即"什么都没说"）。这不意味着理论错了，而意味着它刻画的是最坏情况下的保证，而实际数据与实际算法都远非最坏情况。理论的价值在于揭示哪些量在起作用，而不是替你预测测试集准确率。

核心一：PAC 框架说了什么#

设有一个未知的目标概念 $c$，以及一个未知但固定的数据分布 $D$。学习算法看到 $m$ 个从 $D$ 独立同分布抽取的样本及其标签，输出一个假设 $h$。

称一个概念类是 PAC 可学习的，若存在算法与多项式 $\mathrm{poly}(\cdot)$，使得对任意 $\epsilon,\delta \in (0,1)$，只要样本量

$$m \ge \mathrm{poly}\!\left(\frac{1}{\epsilon}, \frac{1}{\delta}, \text{问题规模}\right)$$

算法就能以至少 $1-\delta$ 的概率输出泛化误差不超过 $\epsilon$ 的假设。

三个设计选择值得注意。分布无关：保证对任意分布 $D$ 成立，代价是保证很保守。双重松弛：既允许误差（$\epsilon$），又允许失败（$\delta$）——只要求"大概率"学到"大致对"的东西。计算与统计并重：PAC 同时要求样本复杂度与时间复杂度是多项式的，这一点使它成为计算复杂性理论的一支，而非纯统计。

对有限假设空间 $\mathcal{H}$，一个漂亮的初等结果给出了样本量的充分条件：

$$m \ge \frac{1}{\epsilon}\left(\ln|\mathcal{H}| + \ln\frac{1}{\delta}\right)$$

注意 $\ln|\mathcal{H}|$ 这一项——它正是"描述一个假设需要多少比特"，与柯尔莫哥洛夫复杂度的直觉一脉相承：越难描述的解释，越需要更多证据支撑。

核心二：VC 维——无限假设空间怎么办#

现实中的假设空间几乎总是无限的（比如平面上所有直线），$\ln|\mathcal{H}|$ 直接失效。瓦普尼克与切尔沃年基斯在 1970 年代给出的替代品，是一个纯组合的量。

称假设空间 $\mathcal{H}$ 打散（shatter）一个点集，若对该点集的任意一种 0/1 标注方式，$\mathcal{H}$ 中都存在一个假设能实现它。VC 维就是 $\mathcal{H}$ 能打散的最大点集的大小。

平面上的直线（线性分类器）VC 维是 3：任意三个不共线的点，八种标注全都能实现；四个点则存在无法实现的标注（异或型排布）。$d$ 维空间的线性分类器 VC 维是 $d+1$——它恰好等于参数个数，这个巧合让人误以为 VC 维就是参数量，但这是错的：单参数的正弦函数族 $\{\mathrm{sign}(\sin(\omega x))\}$ VC 维是无穷大。能表达多少种标注，与用多少个数描述，是两件不同的事。

VC 维的意义在于它直接给出样本复杂度：PAC 可学习当且仅当 VC 维有限，且所需样本量大致与 VC 维成正比。这是学习理论最深刻的定理之一——它把一个统计问题（需要多少数据）化归为一个纯组合问题（能打散多少点）。

核心三：偏差—方差与结构风险最小化#

同一件事有一个更常见的表述。总误差可分解为三部分：近似误差（假设空间本身够不够表达真实规律）、估计误差（有限样本导致的偏离）、以及不可约的噪声。前两者构成经典的偏差—方差权衡：模型越复杂，偏差越小、方差越大。

瓦普尼克据此提出结构风险最小化：把假设空间按复杂度排成嵌套序列 $\mathcal{H}_1 \subset \mathcal{H}_2 \subset \cdots$，在每一层内最小化训练误差，然后在层与层之间选择使"训练误差 + 复杂度惩罚"最小的那一层。正则化、模型选择与信息准则（AIC、BIC）都可以放进这个框架读。

支持向量机是这套理论最直接的产物：它最大化间隔，而理论表明间隔越大，有效 VC 维越小——这让"在高维空间里分类却不过拟合"有了解释，也让核方法在 1990 年代占据统治地位。

核心四：深度学习带来的理论危机#

2016 年之后，经典框架遇到了一个尴尬的事实。

现代深度网络的参数量远超样本量，VC 维大到理论界完全失效。更要命的是一个实验：把训练数据的标签完全随机打乱，同样的网络依然能把训练误差降到零——这说明它的表达能力足以记住任意标注，按经典理论应当无法泛化。可是在真实标签下，它偏偏泛化得很好。

随后被观察到的双下降现象进一步动摇了教科书图景：随着模型规模增大，测试误差先下降、在参数量约等于样本量的插值阈值处冲高，然后再次下降，在过参数化区域达到比经典最优点更低的水平。经典的 U 型偏差—方差曲线只是这条曲线的左半段。

目前的解释方向大致有三条，都未定论：

• 隐式正则化：真正限制假设空间的不是模型结构，而是优化算法。梯度下降在众多能拟合训练集的解中，系统性地偏好某一类（例如最小范数解或平坦极小值），这构成了一种没有写进目标函数的正则化。
• 依赖数据与算法的复杂度度量：用 PAC-Bayes 界、范数界或压缩界替代 VC 维，让复杂度反映训练出的那个具体网络，而不是整个假设空间。这类界有些已能给出非平凡（小于 1）的数值。
• 良性过拟合：在特定的高维统计结构下，插值噪声也不损害泛化——这已在线性回归等可解模型上被严格刻画，但能否推广到深度网络仍是开放的。

这是一个健康的理论危机：不是理论被推翻，而是发现原有的复杂度度量刻画错了对象。学习理论的重心因此正在从"假设空间有多大"转向"优化过程实际探索了假设空间的哪一部分"。

代价与争议#

分布无关的代价是保守。 PAC 要求对任意分布都成立，而真实数据分布远非任意——图像、语言与信号都有极强的结构。理论上的最坏情况保证与实践中的表现之间的巨大鸿沟，很大程度上源于此。分布相关的分析（如流形假设下的分析）更贴近实际，但失去了普适性。

独立同分布假设几乎从不成立。 PAC 的全部保证都建立在训练与测试数据来自同一分布。现实中分布漂移是常态——这正是模型上线后性能下降的主要原因，而经典理论对此完全沉默。分布外泛化、领域自适应与因果学习都是在补这个洞，且都还没有可比拟的完整理论。

可学习性与可计算性的裂缝。 存在概念类在信息论意义上样本复杂度很低，但计算上无法有效学习（如在密码学假设下学习某些布尔电路）。"数据够了"与"算得出来"是两个独立的门槛，PAC 之所以要求时间也是多项式的，正是为了不掩盖这道裂缝。

理论与实践的沟通失败是双向的。 实践者常因泛化界数值无用而整体忽视理论；理论者则时有把可解模型上的结论过度外推到深度网络。双下降是双方共同的教训——它先由实验发现，再迫使理论重建。

未知的边界#

• 隐式正则化能否被写成一个显式的、可计算的复杂度度量？
• 是否存在一套能对现代深度网络给出非平凡且紧致泛化界的框架？
• 双下降与良性过拟合在非线性、多层的设置下能否被严格证明？
• 分布漂移下有没有可能建立像 PAC 一样干净的保证，还是必须依赖因果结构等更强假设？
• 大规模预训练模型的"涌现能力"能否在学习理论框架内被刻画，还是需要新的概念？
• 从计算复杂性角度看，哪些学习任务是本质上困难的？这类下界结果远少于上界。

跨域连接#

• 计算复杂性理论：PAC 学习从设计之初就是计算复杂性的一支——它要求学习不仅统计上可行，计算上也必须可行。在密码学假设下，存在样本复杂度很低却无法多项式时间学习的概念类，这类结果把"学不会"从工程抱怨变成了定理。理解归约与困难性假设，才能理解学习理论中"不可学习"的确切含义。
• 机器学习概览：正则化、交叉验证、早停与模型选择这些日常操作，在理论上都是对复杂度惩罚项的不同近似。理论解释了为什么它们有效，也划出了它们失效的边界——例如当超参数搜索本身消耗了大量数据信息时，交叉验证的无偏性就不再成立，这是实践中最常被忽视的一类泄漏。
• 柯尔莫哥洛夫复杂度：有限假设空间的样本界里出现的 $\ln|\mathcal{H}|$，本质上是描述长度。最小描述长度原理把"最简解释最可能正确"从直觉变成了可计算的目标函数，与结构风险最小化在形式上高度平行。奥卡姆剃刀在这里第一次有了定量版本，代价是柯氏复杂度本身不可计算。
• 随机化算法：PAC 中的"以概率 $1-\delta$ 成立"与随机化算法的成功概率是同一套分析工具——集中不等式（Hoeffding、Chernoff、McDiarmid）是两个领域共同的技术核心。泛化界的推导，本质上是在证明经验均值以高概率接近期望，而这正是概率放大与去随机化研究的同一片数学地基。
• 可证伪性：波普尔主张科学理论的价值在于可被否证，学习理论给出了这个直觉的定量化身——VC 维衡量的正是一个假设空间"能被什么样的数据否证"。打散一个点集意味着对这些点的任何观测结果都无法排除该假设空间，也就意味着它在这些点上不可证伪、因而没有预测力。过拟合与不可证伪，在数学上是同一件事。

参考文献#

• Valiant, L. G. A Theory of the Learnable. Communications of the ACM 27(11), 1134–1142, 1984.
• Vapnik, V. N. & Chervonenkis, A. Ya. On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities. 1971.
• Shalev-Shwartz, S. & Ben-David, S. Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press, 2014.
• Zhang, C. et al. Understanding Deep Learning Requires Rethinking Generalization. ICLR 2017.
• Belkin, M. et al. Reconciling Modern Machine-Learning Practice and the Classical Bias–Variance Trade-off. PNAS 116(32), 2019.

延伸阅读#

• Kearns, M. & Vazirani, U. An Introduction to Computational Learning Theory. MIT Press, 1994.
• Vapnik, V. N. The Nature of Statistical Learning Theory. Springer, 2nd ed., 2000.
• Bartlett, P. L. et al. Benign Overfitting in Linear Regression. PNAS 117(48), 2020.
• Nagarajan, V. & Kolter, J. Z. Uniform Convergence May Be Unable to Explain Generalization in Deep Learning. NeurIPS 2019.