经验风险与泛化间隙

固定规则的经验均值像一把事先放好的尺子；数据依赖选择却会在看见噪声后挑选最有利的尺子。每个候选单独都集中，不代表被挑中的极值仍服从同一个固定对象界。泛化理论需要额外控制这次选择所获得的自由度。

选择偏差可以用只有一条训练数据的实验精确算出。令 $Y$ 为公平二元标签，候选只有常数规则 $h_0\equiv 0$ 与 $h_1\equiv 1$。每个固定规则的总体错误都是 $1/2$，训练错误的期望也都是 $1/2$。ERM 看见唯一标签后选择 $h_Y$，于是训练错误恒为 $0$，独立新标签上的错误却仍为 $1/2$，gap 恒为 $1/2$。两条分别无偏的估计，经“挑较小者”后便不再无偏。

从百万个无信号特征中挑训练相关最大的一个，是同一机制的更大规模版本。大数律没有失效；算法把“先固定规则再抽样”改成了“看完样本再取极值”。反复查看测试集调参也会使最终预测器依赖测试数据。

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

具体地，设 $m=100$，固定分类器真实错误率为 $0.2$，训练中恰错了 15 个点，则 $\hat{R}=0.15$、有向 gap 为 $0.05$。这个数是本次样本的实现值，不是算法必然高估或低估的系统偏差。

对数据依赖输出，需要控制随机量 $R(A(S))-{\hat{R}}_S(A(S))$。若有限类有 $N$ 个候选，分别使用固定规则的 Hoeffding 界再求并，可得失败概率至多 $2N{e}^{-2m{\epsilon }^2}$。让它不超过 $\delta$，需 $m\ge \log \left(2N/\delta \right)/(2{\epsilon }^2)$；多出的 $\log N$ 正是在控制挑选自由度。无限类的一致收敛需要别的容量工具；算法稳定性则直接研究样本替换对所选规则损失的影响，未必要求整类都统一集中。

训练、验证和测试的角色也由依赖关系区分。验证集参与超参数选择后，最终预测器依赖它，不能再把验证误差当固定规则的无偏报告；真正封存的测试集仍可评价整个选择流程。交叉验证让多个划分共同参与评价，减少对某一次划分的依赖，但不保证在所有问题中都降低方差；各折估计相关，其置信分析也不能把样本量简单乘上折数。

一致收敛公理库经验风险的一致收敛Uniform convergence of empirical risks以高概率同时控制整个假设类的经验风险与总体风险偏差。在同一高概率事件上控制整类假设，因此能安全覆盖 ERM 的数据依赖输出；算法稳定性公理库算法稳定性algorithmic stability · uniform stability用训练集中单点替换对输出损失的影响，刻画学习算法的泛化敏感度。则绕过整类容量，直接限制替换一个样本时算法输出损失的变化。两条路线都在控制本页 gap，却依赖不同结构。

模型选择和测试复用把同一问题带到实践协议中。一次封存留出集可评价已经固定的训练流程；反复根据测试分数迭代时，评价对象重新依赖数据，需要嵌套交叉验证、自适应数据分析或新的独立样本来恢复可解释的样本外证据。