VC 维 (VC Dimension)

定义

VC 维(Vapnik-Chervonenkis Dimension)由苏联数学家 Vladimir Vapnik 与 Alexey Chervonenkis 在 1970 年代前后建立的统计学习理论中提出,用于刻画一个假设空间(分类器族)的表达能力:它等于该假设空间能够"打散"(shatter,即实现所有可能二分类标注)的最大样本点数。

例子

二维平面上的线性分类器可以打散任意位置合适的 3 个点,却无法打散某些 4 点构型(如 XOR 布局),故其 VC 维为 3;一般地,d 维空间线性分类器的 VC 维为 d+1。

意义

VC 维出现在泛化误差上界中:假设空间 VC 维有限,则经验风险最小化的泛化误差随样本数增长而收敛,这为"有限容量的模型可以从有限数据中学习"提供了严格的理论保证,也是结构风险最小化和支持向量机的理论出发点。

局限

VC 界通常过于宽松,难以直接指导实践;Rademacher 复杂度等后续工具给出了更紧的分析。