经验风险与泛化间隙

两个风险 ​

对 $S=(Z_1,\dots ,Z_m)$，定义 ${\hat{R}}_S(h)=m^{-1}\sum _i\ell (h,Z_i)$。本文固定有向间隙

$${\mathrm{gap}}_S(h)=R_D(h)-{\hat{R}}_S(h),$$

绝对间隙则忽略偏高或偏低。正 gap 表示训练损失低估样本外损失；负 gap 只说明这份样本较难。

固定 $h$ 且损失在 $[0,1]$ 时，Hoeffding 给出

$$\text{Pr}(|R_D(h)-{\hat{R}}_S(h)|>\epsilon )\le 2e^{-2m{\epsilon }^2}.$$

“固定”是关键。若 $\hat{h}=A(S)$ 从同一数据的海量候选中选出，它与经验噪声相关，不能事后代入固定假设界。有限类用并集界公理库并集界Union bound · Boole 不等式多个坏事件中至少一个发生的概率，不超过各事件概率之和。同时控制；无限类需 VC、Rademacher 或稳定性结构。

选择偏差与边界 ​

从百万个无信号特征中挑训练相关最大的一个，最大值会系统性偏高，尽管每个预先指定特征都集中。这不是大数律失效，而是选择改变了量词。反复查看测试集调参也使最终预测器依赖测试数据，固定规则评价保证随之失效。

训练误差低只说明拟合样本；所有函数类可把训练错误降为零而任意预测未见点。泛化间隙也不等于超额风险：前者比较同一 $h$ 在两个分布上的风险，后者比较两个规则的总体风险。

具体地，设 $m=100$，固定分类器真实错误率为 $0.2$，训练中恰错了 15 个点，则 $\hat{R}=0.15$、有向 gap 为 $0.05$。这个数是本次样本的实现值，不是算法必然高估或低估的系统偏差。若在一万个独立候选中专挑错误最少者，即使每个候选都同样只有 $0.2$ 总体风险，被选者的训练错误也会因取最小值而偏低。

对数据依赖输出，真正要控制的是随机量 $R(A(S))-{\hat{R}}_S(A(S))$。一致收敛通过同时控制全部候选解决选择问题；算法稳定性则直接证明替换一个样本不会明显改变输出风险。这两条路线针对同一 gap，却使用不同结构，不能把“存在泛化界”自动解释为类上必有最朴素的一致收敛。

训练、验证和测试的角色也由依赖关系区分。验证集参与超参数选择后，最终预测器依赖它，不能再把验证误差当固定规则的无偏报告；真正封存的测试集仍可评价整个选择流程。交叉验证通过多次重用数据降低方差，但各折估计相关，其置信分析不是把样本量简单乘上折数。

Gap 的期望为零只对预先固定 $h$ 的无偏经验均值成立。对 ERM 输出，选择最小经验风险通常造成负的经验偏差，所以期望 gap 往往为正。这个“乐观训练误差”是数据复用的结果，不需要假设训练程序有意作弊。

参考资料

• Vapnik, Chervonenkis, “Uniform Convergence of Relative Frequencies,” 1971.
• Shalev-Shwartz, Ben-David, Understanding Machine Learning, Chs. 4–6.