VC 维

增长函数记录每个样本规模上最多能出现多少种标注，VC 维则标出它最后一次达到全部 $2^m$ 种标注的位置。若 VC 维为 $d<\mathrm{\infty }$，所有 $m\le d$ 都能达到 $2^m$，因为打散集合的子集仍被打散；所有 $m>d$ 都不能达到 $2^m$，否则直接违背 $d$ 的定义。这个转折描述的是存在性量词，并非某次随机采样必然出现的模式数。

有限 VC 维并不要求假设类有限；它表达的是无限类投影到有限样本后，组合自由度会在某个尺度之后受到约束。

阈值与区间 ​

实线单阈值能分别标注一个点，却不能在两个有序点 $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 定理理路Radon 定理Radon theorem欧氏 d 维空间中的任意 d 加二个点都能划分为两个凸包相交的非空部分。把它们分成两个凸包相交的子集；若把一侧标为正、另一侧标为负，任何仿射超平面都无法严格分开这两个相交凸包。因此不存在被打散的 $d+2$ 点集。即使约定边界归正类也无法绕过此障碍：负侧所有点的仿射函数值必须严格小于零，其凸组合仍严格小于零；同一个交点作为正侧凸组合却必须非负，产生矛盾。过原点的齐次半空间少一个 bias 参数，不能把仿射结论不加说明地照搬。

维数与数据边界 ​

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

“存在一组点”尤其不能换成“任意一组点”。平面仿射半空间可打散三角形的三个顶点，但无法打散三个共线点：沿该直线，仿射函数只有一次符号切换，无法实现两端正而中间负。VC 维仍为 $3$，因为失败的共线配置不推翻成功的三角形见证。

它描述最有利点配置上的最坏组合能力，不保证实际分布把质量放在这些点上。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 维有限推出。

多类标签需要说明每个点可在哪两种标签之间自由选择，这导向Natarajan 维理路多类学习与 Natarajan 维Multiclass learning · Natarajan dimension · Natarajan 维用每点两个可区分标签的打散能力刻画多类假设类，并说明标签数如何进入泛化界。。标签只有两种时，其两标签见证退化为普通打散，所以 VC 维是该概念的二分类特例；这是推广方向，不是初学 VC 维必须先完成的前置内容。