统计学习基本定理

等价链的正向部分说：有限 VC 维限制类在有限样本上能制造的标注模式，因此一份样本可以同时代表所有假设的总体风险；一旦这种同时代表成立，ERM 的经验比较就能安全搬到总体风险。逆向部分则说：若类能在任意大的点集上随意编码标签，有限样本总会留下大量未见点，学习器在那里没有任何分布无关的信息来源。

从有限 VC 维到不可知 PAC ​

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

其中若下确界不达到，可取 $R_D(h^{\ast })\le \underset{h\in H}{inf}{R}_D(h)+\eta$，最后令 $\eta \downarrow 0$。令 $\alpha =\epsilon /2$ 得到条件 3；存在一个这样的 ERM 给出条件 4，把分布限制到类内最优风险为零的可实现情形又得到条件 5。

从可实现 PAC 反推有限 VC 维 ​

关键逆向是条件 5 推出 VC 维有限。反设 $H$ 能打散任意大的有限集合。给定样本量 $m$，取一个被打散的 $2m$ 点集合，让 $D_X$ 在这些点上均匀，并从 $H$ 可实现的 $2^{2m}$ 种目标标注中等概率选一个。某个固定点未出现在样本中的概率为

条件于训练样本，未见点的目标标签仍是独立公平位；这对随机化、improper 学习器也成立。因此对目标、样本和算法随机性平均，总体错误至少为

错误率落在 $[0,1]$，所以它至少以 $1/7$ 的概率不小于 $1/8$；否则期望会小于 $1/8+(7/8)(1/7)=1/4$。再对随机目标取平均，至少存在一个固定的可实现目标，使学习器以概率至少 $1/7$ 留下错误 $1/8$。对任意 $m$ 都能构造这样的分布与目标，违背 $\epsilon =1/8,\delta <1/7$ 的分布无关 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 统计保证之外，要求样本处理、运行时间与输出评价均为多项式。。Proper/improper 是输出限制，efficient/inefficient 是计算限制，两条轴都独立于本定理的有限 VC 判据。定理也不把 Valiant 1984 年原始模型中的具体表示与计算约束偷渡进现代定义。

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

基本定理把二元分布无关学习的多个入口压到同一个结构参数上。要证明一个类可学，可以直接上界 VC 维并调用一致收敛；要证明不可学，可以构造任意大的被打散集合。两条路线分别把学习问题转成组合几何的上界和下界问题。

有限 VC 维还给出样本复杂度的数量级入口，但基本定理本身只负责等价性。要得到可实现与不可知设定中对 $d,\epsilon ,\delta$ 的精确依赖，需要继续使用 VC 样本复杂度上、下界；要判断算法是否能实际运行，则必须另外研究 ERM 的表示与计算复杂度。

因此，统计可学与高效可学应分层使用：有限 VC 维排除信息论障碍，却不提供多项式时间搜索。一个类可以满足本定理的全部统计条件，同时其最自然的 ERM 问题仍计算困难；这正是高效 PAC 学习需要额外处理的部分。