VC 维

增长函数记录每个样本规模上最多能出现多少种标注，VC 维则标出它最后一次达到全部 $2^m$ 种标注的位置。有限 VC 维并不要求假设类有限；它表达的是无限类投影到有限样本后，组合自由度会在某个尺度之后受到约束。

VC 维只记录一个二元概念类能否实现所有标签模式；Rademacher 复杂度公理库Rademacher 复杂度Rademacher complexity · empirical Rademacher complexity用随机正负号衡量函数类在给定样本上拟合无结构噪声的能力。还读取给定样本上的实值预测幅度，并随样本变化。前者是组合容量参数，后者是可局部化的数据依赖复杂度。

阈值与区间 ​

实线单阈值能分别标注一个点，却不能在两个有序点 $x_1<x_2$ 上产生 $(1,0)$，故 VC 维为 $1$。

区间类的两个方向都可直接检查。对 $x_1<x_2$，空区间、只含 $x_1$、只含 $x_2$ 和同时包含两点的区间实现四种标注，所以维数至少为 $2$。对任意 $x_1<x_2<x_3$，标注 $(1,0,1)$ 的正点集合不连续，单区间无法实现，故任何三点都不能被打散，维数至多为 $2$。

仿射半空间的 $d+1$ ​

${\mathbb{R}}^d$ 中仿射半空间的 VC 维为 $d+1$。下界取 $d+1$ 个仿射无关点。对任意指定的 $\pm 1$ 标签，可解一个仿射函数 $g(x)=⟨w,x⟩+b$，使这些点上的值恰为相应标签；$\mathrm{sign}g$ 因而实现全部 $2^{d+1}$ 种标注。

上界取任意 $d+2$ 个点。Radon 定理把它们分成两个凸包相交的子集；若把一侧标为正、另一侧标为负，任何仿射超平面都无法严格分开这两个相交凸包。因此不存在被打散的 $d+2$ 点集。过原点的齐次半空间少一个 bias 参数，不能把仿射结论不加说明地照搬。

维数与数据边界 ​

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

它描述最有利点配置上的最坏组合能力，不保证实际分布把质量放在这些点上。Rademacher 复杂度公理库Rademacher 复杂度Rademacher complexity · empirical Rademacher complexity用随机正负号衡量函数类在给定样本上拟合无结构噪声的能力。还会读取具体样本和实值幅度；两者值得对照，却不是同一随机量。有限 VC 维也不承诺 ERM 可在多项式时间求出，不能从一份训练集大小直接“估计定义值”。

有限 VC 维直接限制可见标注模式，并不提供训练算法。Sauer–Shelah 引理公理库Sauer–Shelah 引理Sauer's lemma · Sauer–Shelah–Perles lemma把有限 VC 维转化为假设类在有限样本上的多项式标注数上界。把这种限制转成增长函数的多项式上界，PAC 可学习性公理库PAC 可学习性PAC learnability · Probably Approximately Correct learning在可实现设定中，以有限样本和高概率达到任意小总体错误的可学习性。再借集中论证把组合控制转成分布无关保证；具体的 $d,\epsilon ,\delta$ 依赖则在VC 类的样本复杂度界公理库VC 类的样本复杂度界VC sample complexity bounds · PAC optimal sample complexity区分二元 VC 类的教材式 ERM 上界、分布无关最优上界与配套下界，明确可实现和不可知情形的不同精度次数。中展开。计算可解性仍需另行证明，不能由 VC 维有限推出。