VC 维理论是什么？衡量一类模型能“打散”多少个点

VC 维理论（VC Theory）是统计学习理论的核心组成部分，由苏联数学家弗拉基米尔·瓦普尼克和阿列克谢·切尔沃年基斯在 1971 年前后提出，“VC”就是两人姓氏的首字母。它用一个叫作“VC 维”的量来衡量一类模型的复杂程度，并在此基础上回答了机器学习中一个最根本的问题：在什么条件下，模型在训练数据上的表现能够推广到新的数据上。

什么是“打散”

理解 VC 维需要先理解“打散”这个概念。假设有一组样本点，每个点可以被标记为正类或负类，n 个点就有 2 的 n 次方种不同的标记方式。如果一类模型对于这 n 个点的每一种标记方式，都能找到其中的某个模型把它们完全正确地分开，就说这类模型能够“打散”这 n 个点。VC 维就是一类模型能够打散的最大点数。

一个经典的例子

以平面上的直线分类器为例：给定平面上任意位置合适的 3 个点（不在同一条直线上），无论怎样给它们标记正负类，总一共有 8 种标记方式，都能找到一条直线把正类和负类分开。所以直线分类器能打散 3 个点。但对于 4 个点，无论怎么摆放，总存在某种标记方式是一条直线分不开的，比如把四个点放在正方形的四个角上，对角的两个点为正类、另外两个对角为负类，这就是“异或”的情形，无法用一条直线分开。因此，平面上直线分类器的 VC 维是 3。更一般地，d 维空间中的线性分类器的 VC 维是 d 加 1。VC 维衡量的是模型的“表达能力”或“灵活程度”：VC 维越高，模型能够拟合的模式越复杂多样。

泛化误差的上界

VC 维理论最重要的成果，是给出了泛化误差的上界：以很高的概率，模型在新数据上的误差，不超过它在训练数据上的误差，加上一个与 VC 维和训练样本数量有关的项。这个额外的项随着 VC 维的增大而增大，随着样本数量的增大而减小，大致与“VC 维除以样本数量”的平方根有关。这个结论揭示了几个深刻的道理：对于一类 VC 维有限的模型，只要训练样本足够多，训练误差就能可靠地反映真实的泛化误差，也就是说学习是可能的；模型越复杂，VC 维越高，就需要越多的训练数据才能保证泛化；在样本数量一定的情况下，存在一个最佳的模型复杂度，太简单会使训练误差过大，太复杂会使额外的项过大。值得一提的是，这个上界不依赖于数据具体的分布，对任何分布都成立，这是它的优点，但也让它往往比较宽松。

结构风险最小化与支持向量机

基于 VC 维理论，瓦普尼克提出了结构风险最小化原则：在选择模型时，不仅要让训练误差小，还要控制模型的复杂度，让泛化误差的上界最小。支持向量机正是这一思想的产物：瓦普尼克等人证明，最大化分类的间隔可以有效地控制模型的有效复杂度，即使在维度非常高的特征空间中，只要间隔足够大，模型仍然能够很好地泛化。20 世纪 90 年代，支持向量机在多项任务上取得了出色的效果，让统计学习理论受到了广泛的重视。

局限与发展

对于现代的深度神经网络，VC 维理论遇到了困难：神经网络的参数量常常远远超过训练样本的数量，它的 VC 维极高，按照 VC 维理论给出的上界几乎毫无意义，但这些网络在实践中却往往泛化得很好。2017 年，张驰原等人的研究发现，深度网络甚至能够完美地拟合随机打乱的标签，这说明仅靠 VC 维这样只考虑模型类别的复杂度度量，无法解释深度学习的泛化能力。研究者因此转向了 Rademacher 复杂度、基于间隔的上界、PAC-Bayes 理论、算法稳定性，以及优化算法本身带来的隐式正则化等方向，试图建立新的泛化理论。尽管如此，VC 维理论仍然是理解机器学习基本原理的重要基石。