VC 维

定义与量词 ​

$$\mathrm{VCdim}(\mathcal{H})=sup\{|S|:S\subseteq \mathcal{X}\text{ 被 }\mathcal{H}\text{ 打散}\}.$$

若任意有限大小都有可打散集合，则 VC 维为 $\mathrm{\infty }$。定义只要求“存在”一个大小为 $d$ 的点集被打散，不要求所有 $d$ 点配置都可打散；证明下界构造一组点，证明上界则要排除任意更大点集。

标准例子 ​

实线单阈值能分别标注一个点，却不能在两个有序点上产生 $1,0$，故 VC 维为 1。实线区间可打散两个点；三个有序点的标注 $1,0,1$ 不能由单区间实现，故维数为 2。${\mathbb{R}}^d$ 中仿射半空间的 VC 维是 $d+1$：一般位置的 $d+1$ 点可打散，而任意 $d+2$ 点的仿射依赖产生不可线性分离标注。

VC 维借用“维数”一词，却不是向量空间维数公理库维数Dimension of a vector space在基存在时，以基的基数度量向量空间的独立方向数。。无限假设类可有有限 VC 维，参数个数也只在特定正则参数化下与它相关。退化参数、离散约束和共享结构都可破坏简单等同。

有限 VC 维把无限类在有限样本上的标注数压低，是分布无关二分类可学性的组合核心；它不承诺 ERM 可在多项式时间求出，也不应从一份训练集大小直接“估计定义值”。

区间类的下界与上界可以逐步检验。取 $x_1<x_2$，空区间、只含 $x_1$、只含 $x_2$ 和同时包含两点的区间实现四种标注，所以 VC 维至少为 2。对任意 $x_1<x_2<x_3$，标注 $1,0,1$ 的正点集合不连续，单区间无法实现，故任何三点都不能被打散，VC 维至多为 2。

半空间的 $d+1$ 依赖“仿射”约定：过原点的齐次半空间与带 bias 的仿射半空间相差一个增广坐标。一般位置只用于构造可打散点集；上界必须覆盖退化配置。VC 维描述最坏存在配置，不保证实际分布把质量放在这些点上，分布依赖复杂度可能显著更小。

参考资料

• Vapnik, Chervonenkis, 1971.
• Blumer et al., “Learnability and the VC Dimension,” 1989.