VC 一致收敛界

形式陈述 ​

本页给出经验风险一致收敛理路经验风险的一致收敛Uniform convergence of empirical risks以高概率同时控制整个假设类的经验风险与总体风险偏差。在二元 VC 类上的规范实现。设非空输入域上的非空类 $H\subseteq \{0,1{\}}^{\mathcal{X}}$，损失是二元误分类损失。样本 $S=(Z_1,\dots ,Z_m)\sim D^m$，其中 $Z_i=(X_i,Y_i)$；记

若 $H$ 的VC 维理路VC 维Vapnik–Chervonenkis dimension · VC dimension二分类假设类能够完全打散的最大有限点集大小。为 $d<\mathrm{\infty }$，并有固定可数决定子类，使下述偏差上确界保持不变，令 $G_d(2m)=\sum _{j=0}^{min(d,2m)}(\genfrac{}{}{0ex}{}{2m}{j})$。对任意整数 $m\ge 1$ 和 $0<\delta <1$，以至少 $1-\delta$ 的概率

当 $1\le d\le 2m$ 时，可以 $d\log \left(2em/d\right)$ 上界 $\log G_d(2m)$，恢复常见的平方根量级。$d=0$ 时 $G_0(2m)=1$，不出现除以零；$d>2m$ 时 $G_d(2m)=2^{2m}$。即使只有一个固定分类器，标签抽样仍会波动，所以零维也不能省去置信项。

证明链 ​

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

其中 $m{\epsilon }^2\ge 2$ 时成立，条件与证明见对称化页的有界类概率版本。

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

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