霜降 | 制图师的三个工具：机器学习泛化与复杂度的演进

在机器学习的核心，存在一个根本性的挑战，我们可以将其比作一位古代制图师的困境。这位制图师的任务是绘制一整片未知大陆的精确地图，但这片大陆的真实地貌——即数据的真实分布——是无法完全观测的。他所拥有的，仅仅是在大陆上零星散布的几个勘测点，也就是我们所说的训练数据。他基于这些有限的勘测点绘制出的地图，便是学习到的模型。

制图师的几个复杂度工具示意图（基于 nano banana 作为工具绘制）

这个过程中的核心问题是：我们如何确保这张依据局部信息绘制的地图，在整片广袤的未知大陆上依然准确？地图在已知勘测点上的表现被称为经验风险，是我们能够直接测量和优化的指标；而它在整片大陆上的真实准确性，则被称为总体风险，是理论上的终极目标，却无法直接计算 。两者之间的差距，即泛化差距，决定了我们的模型是真正“学会”了规律，还是仅仅“记住”了特例。  

统计学习理论的核心任务，就是为这个差距提供一个可靠的界限。而这个界限的大小，本质上受制于制图师所使用工具的“复杂度”。一套简单的工具（如一把直尺）或许只能绘制出粗糙但可靠的地图；而一套极其灵活的工具（能画出任何曲线）虽然能完美连接所有已知勘测点，却可能在点与点之间的未知区域画出荒诞不经的线条，这种现象我们称之为过拟合。因此，理解泛化的故事，就是一场探索如何度量模型复杂度的智力远征^[1-3]。

对模型复杂度的首次系统性探索采取了一种宏大而普适的视角：暂时忽略地图绘制的具体地貌（数据分布），转而专注于制图工具本身固有的能力。这正是 Vapnik 与 Chervonkenis 的思想^[1]。他们认为，一个模型家族的复杂度，在于其划分不同事物的能力，无论这种划分在现实中多么任意。  

这一思想的核心是“打散”（Shattering）的概念。一个模型家族能够“打散”一个包含 n 个数据点的集合，是指对于这 n 个点所有可能的二元标签组合（共 2n 种），该模型家族中都存在一个模型能够完美地实现该标签组合 。这是一种对模型表达能力的终极度量。 

基于此，Vapnik-Chervonenkis 维度（VC dimension）^[4-5]被定义为模型家族能够打散的点的最大数量 。它是一个单一的、纯组合性质的数值，捕捉了模型家族的“自由度”，且完全独立于任何具体的数据分布。例如，在二维平面上的线性分类器，其 VC 维度是3，因为它能打散任意3个非共线的点，但任何4个点的某种布局都无法被一条直线完美划分。  

VC 维度的深刻意义在于，它直接给出了一个泛化差距的界限：只要一个模型家族的 VC 维度是有限的，那么随着样本量趋向于无穷大，经验风险必然会收敛于真实风险。这从数学上保证了“学习”是可能实现的 。然而，VC 维度的最大优点——其对数据分布的无关性——也正是其致命的弱点。为了对任何可能的数据分布都成立，它必须为最坏的情况做准备，因此在面对现实世界中那些相对“温和”的分布时，其界限往往会极大地高估真实的泛化差距，导致结论过于悲观。

VC 维度这把普适标尺的局限性，引导我们去寻求一种更具适应性的测量工具——一种能够根据我们正在绘制的具体地貌（数据分布）来评估复杂度的工具。这便是 Rademacher 复杂度的核心思想。我们不再问“这个模型在最坏情况下能做什么？”，而是问“对于这类特定的数据，这个模型有多大可能在其中发现虚假的随机模式？”

Rademacher 复杂度^[6-7]通过衡量一个模型家族与随机噪声的相关能力来捕捉其丰富程度 。其直觉如下：我们取训练数据点，但抛弃它们的真实标签，代之以一组完全随机的符号（+1或-1）。然后我们提问：在我们的模型家族中，表现最好的那个模型能在多大程度上使其预测结果与这组随机标签对齐？一个非常复杂的模型家族，由于其巨大的灵活性，总能找到某个函数与随机噪声产生强烈的相关性，这将导致很高的 Rademacher 复杂度 。  

Rademacher 复杂度的关键优势在于其分布依赖性。如果数据的真实分布是“友好的”，那么模型拟合随机噪声的能力就会受限，从而得到一个比悲观的 VC 界更紧致、更现实的泛化界 。然而正是这种精细的度量方式，揭示了现代神经网络的一个困境——研究表明，深度神经网络即使在训练数据的标签被完全随机化后，依然能够达到近乎为零的训练误差。这意味着它们拟合随机噪声的能力极强，其 Rademacher 复杂度也因此趋近于最大值，导致泛化界变得毫无意义。这个被设计出来用以替代 VC 维度的、更为精妙的工具，在面对过参数化模型的巨大容量时，同样失效了。

VC 维度和 Rademacher 复杂度的相继失效，迫使我们重新思考新的复杂度视角来解释泛化。或许，问题的根源不在于制图师拥有的地图库有多庞大，而在于他选择地图的过程本身。PAC-Bayes 框架将泛化的焦点从模型家族的固有属性，转移到了学习算法自身的行为上 。在这里，复杂度被重新诠释为：算法为了更新其“信念”，需要从数据中提取多少信息。 

PAC-Bayes 框架分析的是输出一个关于模型的概率分布（后验）的算法，而非单一模型。我们需要一个先验分布，它编码了我们在看到任何数据之前的初始信念（例如，我们可能先验地认为结构更简单的模型概率更高）。学习过程就是算法在观测到数据后，将先验更新为数据相关的后验的过程^[8-9]。

在 PAC-Bayes 的语境下，复杂度由后验与先验之间的 Kullback-Leibler（KL）散度来度量 。KL 散度的直观含义是“意外程度”或“信息增益”。它量化了从先验信念转变为后验信念所需要的信息量。如果数据迫使算法选择了一个与我们初始信念大相径庭的后验，那么 KL 散度就会很大，复杂度惩罚也随之增高。  

这种转变，为解释深度学习的泛化之谜提供了一条极具潜力的路径。我们可以提出这样一个假说：像随机梯度下降（SGD）这样的优化算法，拥有某种隐式偏置，其作用类似于一个先验。即便是在一个巨大的、过参数化的模型空间中，这种偏置也会引导算法找到那些在某种意义上“简单”的解（即 KL 散度较小的后验）。因此，泛化之谜的焦点从“为什么大型网络能够泛化？”转向了“为什么 SGD 能够找到可以泛化的解？”。这正是当前理论研究的最前沿。

我们从 VC 维度普适但悲观的组合学保证出发，途经 Rademacher 复杂度更为精细、依赖数据的视角，然后抵达了 PAC-Bayes 深刻的、以算法为核心的信息论框架。这一演进轨迹反映出对泛化问题的理解，从分析模型本身，深化到分析学习过程。

现代深度学习中“良性过拟合”^[10]和“双下降”^[11]等现象表明，当下的理论进展远非故事的终点 。泛化的故事远未结束，制图师的困境依然存在。我们的经典工具为我们提供了理解问题的基础语言，但要探索深度学习这片广袤的、过参数化的未知大陆，我们需要全新的地图。泛化理论的未来，在于深入理解优化算法的隐式偏置——在制图师拥有无限复杂度的工具时，依然能引导他走向简洁地图的无形罗盘。

参考文献：

[1] Vapnik, Vladimir. The nature of statistical learning theory. Springer science & business media, 2013.

[2] Mohri, Mehryar, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of machine learning. MIT press, 2018. 

[3] Bishop, Christopher M., and Nasser M. Nasrabadi. Pattern recognition and machine learning. Vol. 4, no. 4. New York: springer, 2006.

[4] Vapnik, Vladimir N., and A. Ya Chervonenkis. "On the uniform convergence of relative frequencies of events to their probabilities." In Measures of complexity: festschrift for alexey chervonenkis, pp. 11-30. Cham: Springer International Publishing, 2015. 

[5] Blumer, Anselm, Andrzej Ehrenfeucht, David Haussler, and Manfred K. Warmuth. "Learnability and the Vapnik-Chervonenkis dimension." Journal of the ACM (JACM) 36, no. 4 (1989): 929-965. 

[6] Bartlett, P. L., and Mendelson, S. "Rademacher and Gaussian Complexities: Risk Bounds and Structural Results." Journal of Machine Learning Research 3 (2002): 463-482.

[7] Koltchinskii, Vladimir. "Rademacher penalties and structural risk minimization." IEEE Transactions on Information Theory 47, no. 5 (2002): 1902-1914. 

[8] McAllester, David A. "Some pac-bayesian theorems." In Proceedings of the eleventh annual conference on Computational learning theory, pp. 230-234. 1998. 

[9] Germain, Pascal, Alexandre Lacasse, François Laviolette, and Mario Marchand. "PAC-Bayesian learning of linear classifiers." In Proceedings of the 26th Annual International Conference on Machine Learning, pp. 353-360. 2009. 

[10] Zhang, C., Bengio, S., Hardt, M., Recht, B., and Vinyals, O. "Understanding Deep Learning Requires Rethinking Generalization." International Conference on Learning Representations (ICLR), 2017. 

[11] Belkin, Mikhail, Daniel Hsu, Siyuan Ma, and Soumik Mandal. "Reconciling modern machine-learning practice and the classical bias–variance trade-off." Proceedings of the National Academy of Sciences 116, no. 32 (2019): 15849-15854.

文 | 初旭

图 | 钟方威