统计学习基本定理

定理的范围 ​

固定输入空间 $\mathcal{X}$ 与二元假设类 $H\subseteq \{0,1{\}}^{\mathcal{X}}$，使用 $0$–$1$ 损失。样本始终是 $S\sim D^m$，分布 $D$ 可在 $\mathcal{X}\times \{0,1\}$ 上任意选择；学习器允许输出 $H$ 中假设时称 proper，允许输出更大类时称 improper。

在 $H$ 可数，或满足使经验风险上确界与 ERM 可测的标准可分性条件时，下列命题等价：

1. $H$ 的 VC 维公理库VC 维Vapnik–Chervonenkis dimension · VC dimension二分类假设类能够完全打散的最大有限点集大小。有限；
2. $H$ 是一致 Glivenko–Cantelli 类，即对任意 $\epsilon ,\delta >0$，足够大的 $m$ 使$$\text{Pr}(\underset{h\in H}{sup}|R_D(h)-{\hat{R}}_S(h)|>\epsilon )\le \delta$$对所有 $D$ 同时成立；
3. 任意经验风险最小化器都是不可知 PAC 学习器；
4. $H$ 不可知 PAC 可学习；
5. $H$ 在可实现分布下 PAC 可学习。

不同教材会把第 5 项的 learner 类型或可测性假设写得略有差异。定理的语义中心不是一串常数，而是：二元类能否被分布无关地学习，恰由有限样本上能否打散任意大的点集决定。

为什么这些条件等价 ​

有限 VC 维首先通过 VC 一致收敛界公理库VC 一致收敛界VC inequality · VC uniform convergence bound二元假设类的总体错误与经验错误以 VC 维控制的速率同时接近，证明由对称化、标注计数和集中三步组成。推出条件 2。若所有经验风险都与总体风险相差至多 $\alpha$，ERM 输出 $\hat{h}$，则

$$R_D(\hat{h})\le {\hat{R}}_S(\hat{h})+\alpha \le {\hat{R}}_S(h^{\ast })+\alpha \le R_D(h^{\ast })+2\alpha ,$$

其中 $h^{\ast }$ 可取为类内近似最优假设。令 $\alpha =\epsilon /2$，得到条件 3，随后条件 3 显然推出 4；限制到存在零风险目标的分布，4 又推出 5。

关键逆向是 5 推出 VC 维有限。若 $H$ 能打散任意大的有限集合，就可在一个被打散的 $n$ 点集上随机选择目标标注，并让输入均匀分布。训练样本只揭示它见过的点的标签，对未见点的标签没有信息。取 $n$ 与 $m$ 同阶，仍有常数比例的概率质量落在未见点上；对随机目标平均后，任何学习器在那里至少有一半机会猜错。于是存在某个固定目标使学习器以常数概率留下常数错误，和分布无关 PAC 保证矛盾。

具体例子：阈值类与无穷维反例 ​

实线阈值类 $h_a(x)=\mathbf{1}[x\ge a]$ 能打散一个点，却不能打散两个点：若 $x_1<x_2$，标注 $(1,0)$ 无法由任何阈值实现。因此 $\mathrm{VCdim}(H)=1$，它满足上述全部条件。样本中离分界最近的正负点已经把未知阈值夹在一个区间里；随着样本增加，这个区间在分布质量意义下收缩。

相反，所有有限子集的指示函数类在无限 $\mathcal{X}$ 上能打散每个有限点集，VC 维无穷。训练集之外仍可任意翻转标签，任何只见有限样本的学习器都无法获得分布无关保证。问题不在优化算法慢，而在样本根本没有排除足够多的候选行为。

失败边界：定理没有承诺什么 ​

等价性只谈统计存在性。有限 VC 维不意味着 ERM 可在多项式时间求出，也不意味着存在高效的编码或搜索过程；这些问题属于 高效 PAC 学习公理库高效 PAC 学习Efficient PAC learning在 PAC 统计保证之外，要求样本处理、运行时间与输出评价均为多项式。。它也不把 Valiant 1984 年原始模型中的正例查询、无假阳性等具体结构偷渡进现代定义。

定理同样不宣称任意 ERM 都达到可实现 PAC 的最优常数和最优 $\epsilon$ 依赖。有限 VC 维给出可学习性的质性刻画，最优上、下界及 proper/improper 差异由 VC 类的样本复杂度界公理库VC 类的样本复杂度界VC sample complexity bounds · PAC optimal sample complexity区分二元 VC 类的教材式 ERM 上界、分布无关最优上界与配套下界，明确可实现和不可知情形的不同精度次数。单独整理。样本压缩能推出学习，但“每个 VC 维为 $d$ 的类都有大小 $O(d)$ 的压缩方案”不是本定理中可以无条件加入的已证等价项。

参考资料

• Anselm Blumer et al., “Learnability and the Vapnik–Chervonenkis Dimension,” JACM, 1989.
• Vladimir Vapnik and Alexey Chervonenkis, 1971.
• Shai Shalev-Shwartz and Shai Ben-David, Understanding Machine Learning, chapter 6.