有限假设类泛化界

双边界及证明 ​

设 $\mathcal{H}$ 有限，损失在 $[0,1]$，样本 IID。对固定 $h$，Hoeffding 给坏事件概率至多 $2e^{-2m{\epsilon }^2}$。对全部 $h$ 的坏事件使用并集界：

$$\text{Pr}(\underset{h\in \mathcal{H}}{sup}|R(h)-\hat{R}(h)|>\epsilon )\le 2|\mathcal{H}|e^{-2m{\epsilon }^2}.$$

令右边为 $\delta$，以至少 $1-\delta$ 概率，

$$\mathrm{\forall }h\in \mathcal{H}:|R(h)-\hat{R}(h)|\le \sqrt{\frac{\log (2|\mathcal{H}|/\delta )}{2m}}.$$

因此 ERM 的类内超额风险至多上式右端的两倍。候选数以 $\log |\mathcal{H}|$ 而非 $|\mathcal{H}|$ 进入样本量。

可实现的一侧快界 ​

若存在零风险目标，任何错误率大于 $\epsilon$ 的 $h$ 在 $m$ 个样本上保持零错误的概率至多 $(1-\epsilon {)}^m\le e^{-m\epsilon }$。并集后，$m\ge (\log |\mathcal{H}|+\log \left(1/\delta \right))/\epsilon$ 足以排除所有坏的一致假设。这是 $1/\epsilon$，不能与一般双边估计的 $1/{\epsilon }^2$ 混淆。

类必须在看见样本前固定。连续或无限类的 $|\mathcal{H}|$ 可能无穷；需要增长函数、VC 或覆盖数替代全局计数，而不是把浮点参数精度随意当成类大小。

若 $|\mathcal{H}|=1000$、$m=5000$、$\delta =0.05$，双边偏差上界约为

$$\sqrt{\frac{\log \left(40000\right)}{10000}}\approx 0.0326.$$

因此 ERM 的类内超额风险由这条通用论证控制在约 $0.0652$。这是最坏情形保证；候选损失高度相关时，并集界可能很松，实际 gap 更小并不反驳定理。

数据依赖地生成候选类会破坏“预先固定”的证明。例如先在训练数据上搜索一百万个特征，再只把最好的十个称作 $\mathcal{H}$，不能把 $|\mathcal{H}|=10$ 代回上界；选择过程已经看过其余候选。可用独立样本完成筛选，或把整个搜索空间纳入复杂度控制。

参考资料

• Blumer et al., “Learnability and the VC Dimension,” 1989.
• Shalev-Shwartz, Ben-David, Understanding Machine Learning, Ch. 6.