VC 维数——决定可学习性的容量

父节点：learning-theory 前置知识：learning-theory——定义了 H（假设类）、h ∈ H（一条规则 X→{+,−}）、ε、m。

一个衡量假设类 H 原始"能力"的单一数字——而它恰好就是可学习与不可学习之间的分界线。

打散（Shattering）

固定一个类 H。一个有限集合 S = {x₁, …, xₙ} 被 H 打散，如果它的 2ⁿ 种标注方式全部都能实现：对每一个 (y₁,…,yₙ) ∈ {+,−}ⁿ，都存在某个 h ∈ H 使得对所有 i 都有 h(xᵢ) = yᵢ。

VC 维数

VCdim(H) 定义为：存在被 H 打散的 n 个点组成的集合，且 n 取最大值（若不存在最大值则为 ∞）。

量词的排列顺序——这是最容易让人绊倒的地方——是这样的：

VCdim(H) ≥ n ⟺ ∃ 点 x₁,…,xₙ 使得 ∀ 标注 ∃ h ∈ H 能实现它。

按顺序读这三个量词：你可以选择这 n 个点（∃，挑一个对自己最有利的摆法）；然后这个类必须应付它们的每一种标注（∀）；办法是每次都能找到某个假设（∃）。而 VCdim(H) = n 还额外要求：没有 n+1 个点能做到——任何一种 n+1 个点的摆法，都会在某种标注上失败。

实际计数的方法

• 要证明 VC ≥ n：找出某一组 n 个点，并实现全部 2ⁿ 种标注（把它们打散）；
• 要证明 VC = n：还要证明没有 n+1 个点能被打散——总有某种标注会失败。

你数的是能被打散的点数，不是直线数或参数数。所以"2 条直线"不等于"VC 2"——你必须真的跑一遍这个检验。

子节点

• examples ——一架用手数出来的容量阶梯：阈值（1）→ 区间（2）→ k 个区间的并（2k）→ 线性（3）→ 矩形（4）→ sin ωx（∞）。
• price-of-capacity ——提升 VC 从不是免费的：偏差—方差权衡与结构风险最小化。
• sauer-shelah ——驯服无限类的引理：在 n 个点上它只能实现 O(nᵈ) 种标注，而不是 2ⁿ。
• fundamental-theorem ——PAC 可学习 ⟺ VC 有限，附带两个方向的证明。

为什么叫"VC 维数"

• VC = Vapnik–Chervonenkis——弗拉基米尔·瓦普尼克（Vladimir Vapnik）与阿列克谢·切尔沃年基斯（Alexey Chervonenkis，1971 年），定义它的两位学者。这就是他们的名字（就像"欧拉数"一样），不是某个概念的缩写。
• 叫"维数"是因为它数的是这个类的自由度，是向量空间维数概念的推广：打散 n 个点 = 独立地选择全部 n 个标签 = n 个你能独立控制的"坐标"——这正是维数的定义：能找到的最大一组线性无关向量。打散就是学习理论版本的线性无关。
• 对于一个参数化的类，它甚至和参数个数吻合：ℝᵈ 中的线性分类器 VC = d+1。
• 但 VC 比数参数诚实得多：sin(ωx) 只有一个参数 ω，VC 却是 = ∞。数参数会在容量上撒谎；VC 量的是真实的灵活度——这正是为什么需要一个新的"维数"概念。

VC 维数 ≠ 数据空间的维数

这里容易混淆三种不同的"维数"——把它们分开：

类	输入空间（几何）	参数个数	VC
直线上的阈值	1 维	1（t）	1
直线上的区间	1 维	2（a,b）	2
平面上的直线	2 维	2	3
平面上的矩形	2 维	4	4

阈值和区间活在同一条 1 维直线上，VC 却是 1 对 2——所以VC 是规则类的属性，不是点所在空间的属性。 平面上一条用来切割的直线本身只是 1 维的切割，VC 却是 3——{输入=2，切割=1，VC=3} 三者互不一致。VC 与输入维数吻合，只发生在特殊的类上（线性分类器：ℝᵈ 中为 d+1），这也正是它们如此容易被混为一谈的原因。