超额风险与误差分解

基准与恒等式 ​

固定分布、损失和类 $\mathcal{H}$，记 $R^{\ast }=\underset{h}{inf}R(h)$、$R_{\mathcal{H}}^{\ast }=\underset{h\in \mathcal{H}}{inf}R(h)$。则

$$R(\hat{h})-R^{\ast }=\underset{\mathrm{逼}\mathrm{近}\mathrm{误}\mathrm{差}}{\underbrace{R_{\mathcal{H}}^{\ast }-R^{\ast }}}+\underset{\mathrm{类}\mathrm{内}\mathrm{超}\mathrm{额}\mathrm{风}\mathrm{险}}{\underbrace{R(\hat{h})-R_{\mathcal{H}}^{\ast }}}.$$

下确界未必达到，故不应未经条件指定“类内最优参数”。

若 $\tilde{h}$ 是精确 ERM，实际输出的经验次优不超过 ${\epsilon }_{\mathrm{o}\mathrm{p}\mathrm{t}}$，且所有 $h$ 的经验—总体偏差不超过 ${\epsilon }_{\mathrm{g}\mathrm{e}\mathrm{n}}$，加减经验风险可得

$$R(\hat{h})-R_{\mathcal{H}}^{\ast }\le 2{\epsilon }_{\mathrm{g}\mathrm{e}\mathrm{n}}+{\epsilon }_{\mathrm{o}\mathrm{p}\mathrm{t}}.$$

泛化项出现两次，分别控制输出与比较规则；优化误差按目标值定义，参数距离或梯度范数需额外条件才能转换。

三种失败的图像 ​

真实边界是圆而 $\mathcal{H}$ 只有半空间时，即使无限数据和精确优化，逼近误差仍为正。类足够好但样本少，会留下估计误差；训练目标没求好，则留下优化误差。扩大类可能降低第一项，却提高后两项的难度。

训练—测试差只比较同一规则的两种风险，不是超额风险。非唯一最优时，参数相距很远也可能风险相同。正则化和代理损失会引入新的比较项，每次都应写清基准，不能把全部余量统称为“泛化误差”。

例如某任务的 Bayes 风险为 $0.08$，线性类内最优风险为 $0.13$，学习算法输出风险为 $0.17$。相对 Bayes 的超额风险 $0.09$ 精确分成逼近误差 $0.05$ 与类内超额风险 $0.04$。若训练优化只带来 $0.01$ 经验次优，剩余 $0.03$ 也不能不经论证都叫“估计误差”，因为统一偏差上界常是保守上界，而非可观测恒等分量。

分解还能指导改进顺序：当逼近项主导时，多采同分布数据不会突破类的天花板；当估计项主导时，盲目扩大类可能更糟；当优化项已远小于统计精度，再把训练目标多降十位小数通常不改变可保证的总体风险。这里的判断基于同一风险尺度，而不是把参数误差、运行时间和分类错误直接相加。

代理损失会增加一层转换。算法也许最小化 logistic 风险，但最终报告 0–1 风险；先分解代理风险的逼近、估计和优化项，再用校准函数把代理超额风险转换成分类超额风险。没有这条转换，代理目标下降不等于任务风险按同样数值下降。

若类或正则参数由同一数据选择，$\mathcal{H}$ 本身也变成随机对象，固定类的分解不能直接条件化后照搬。结构风险最小化会给各类分配复杂度罚项与失败预算，使模型选择代价显式进入估计项。

参考资料

• Devroye, Györfi, Lugosi, A Probabilistic Theory of Pattern Recognition, 1996.
• Shalev-Shwartz, Ben-David, Understanding Machine Learning, 2014.