VC 一致收敛界

形式陈述 ​

设 $H\subseteq \{0,1{\}}^{\mathcal{X}}$，损失是二元误分类损失。样本 $S=(Z_1,\dots ,Z_m)\sim D^m$，其中 $Z_i=(X_i,Y_i)$；记

$$R_D(h)={\text{Pr}}_{(X,Y)\sim D}[h(X)\ne Y],{\hat{R}}_S(h)=\frac{1}{m}\sum _{i=1}^m\mathbf{1}[h(X_i)\ne Y_i].$$

若 $H$ 的 VC 维为 $d<\mathrm{\infty }$，并满足通常的可测性条件，则存在普适常数 $C>0$，使任意 $0<\delta <1$ 下，以至少 $1-\delta$ 的概率

$$\underset{h\in H}{sup}|R_D(h)-{\hat{R}}_S(h)|\le C\sqrt{\frac{d\log \left(2em/d\right)+\log \left(1/\delta \right)}{m}}$$

（当 $d>2m$ 时把增长函数直接以上界 $2^{2m}$ 处理）。这里常数与对数内的数字取决于采用单边还是双边不等式；不变的核心是 $\sqrt{(d\log \left(m/d\right)+\log \left(1/\delta \right))/m}$ 的量级。

证明链 ​

令 $S^{\prime }$ 是与 $S$ 独立、同分布的 ghost sample。对固定 $h$，总体风险是 $S^{\prime }$ 上经验风险的条件期望；对称化公理库对称化与 Ghost Samplesymmetrization · ghost sample用独立幽灵样本和随机符号，把未知总体均值偏差化为可分析的经验过程。把未知的 $R_D(h)$ 换成可比较的 ${\hat{R}}_{S^{\prime }}(h)$。一个标准版本给出

$$\text{Pr}(\underset{h}{sup}|R_D(h)-{\hat{R}}_S(h)|>\epsilon )\le 2\text{Pr}(\underset{h}{sup}|{\hat{R}}_{S^{\prime }}(h)-{\hat{R}}_S(h)|>\epsilon /2),$$

其中 $m{\epsilon }^2$ 足够大时成立；小样本区间可吸收到常数中。

条件于合并后的 $2m$ 个输入点，$H$ 虽可能无限，却只能产生至多 ${\mathrm{\Pi }}_H(2m)$ 种标注向量。对每一种向量，随机交换每对 $(Z_i,Z_i^{\prime })$ 等价于加入独立符号，Hoeffding 集中给出指数尾界；再对这些标注模式使用并集界公理库并集界Union bound · Boole 不等式多个坏事件中至少一个发生的概率，不超过各事件概率之和。，得到

$$\text{Pr}(\underset{h}{sup}|R_D(h)-{\hat{R}}_S(h)|>\epsilon )\le 4{\mathrm{\Pi }}_H(2m)e^{-m{\epsilon }^2/8}.$$

最后由 Sauer–Shelah 引理公理库Sauer–Shelah 引理Sauer's lemma · Sauer–Shelah–Perles lemma把有限 VC 维转化为假设类在有限样本上的多项式标注数上界。，当 $d\le 2m$ 时 ${\mathrm{\Pi }}_H(2m)\le (2em/d{)}^d$。取对数并令右侧不超过 $\delta$，便得到所述界。三步各有单一职责：ghost sample 消掉未知期望，增长函数把无限类压成有限模式，集中与并集界控制所有模式同时偏离。

概念图像与例子 ​

在 ${\mathbb{R}}^p$ 上，仿射半空间的 VC 维是 $p+1$。法向量与截距是任意精度的实数，候选分类器不可数；但在 $2m$ 个观测点上，它们能留下的二元切分只有多项式级别。于是泛化代价取决于 $p$ 与样本量，而不取决于参数写到多少位。这正是 VC 理论把“无限参数集合”换成“有限样本上的可区分行为”的意义。

如果 $\underset{h}{sup}|R_D(h)-{\hat{R}}_S(h)|\le \alpha$，不可知情形的 ERM 满足

$$R_D(\hat{h})\le \underset{h\in H}{inf}{R}_D(h)+2\alpha ,$$

所以要超额风险至多 $\epsilon$，朴素界通常需要 $m$ 为 $\tilde{O}(d/{\epsilon }^2)$。可实现情形利用“经验错误为零”的单边事件可得到 $1/\epsilon$ 依赖；若直接套本页双边平方根界，只会给出较松的 $1/{\epsilon }^2$。

边界与区分 ​

本页不是 VC 类最优样本复杂度公理库VC 类的样本复杂度界VC sample complexity bounds · PAC optimal sample complexity区分二元 VC 类的教材式 ERM 上界、分布无关最优上界与配套下界，明确可实现和不可知情形的不同精度次数。：它证明一种统一控制机制，不保证每个学习器都达到最优速率。固定 $h$ 的大数定律也不足以替代它，因为 ERM 的 $h$ 正由同一份数据选择。

可测性并非装饰。若 $\underset{h\in H}{sup}$ 对应的随机变量不可测，概率陈述需要外概率、可数稠密子类或其他可分性条件。数据依赖的随机假设类也不能原样代入：必须先条件化到能保持证明成立的信息，或改用稳定性、条件 Rademacher 复杂度等工具。

参考资料

• Vladimir Vapnik and Alexey Chervonenkis, “On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities,” 1971.
• Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, and Manfred Warmuth, “Learnability and the Vapnik–Chervonenkis Dimension,” 1989.
• Shai Shalev-Shwartz and Shai Ben-David, Understanding Machine Learning, chapters 6–7.