定理2.13 学习界限 — 有限H 不一致情况

定理2.13 （学习界限 — 有限 $\mathcal{H}$ ，不一致情况）

• 取 $\mathcal{H}$ 为一个有限的假设集。
• 那么，
  • 对于任何 $\delta >0$ ，
  • 在至少 $1-\delta$ 的概率下，
  • 以下不等式成立： $\forall h\in \mathcal{H},$ R \left( h\right) \leq {\widehat{R}}_{S}\left( h\right) + \sqrt{\frac{\log \left| \mathcal{H}\right| + \log \frac{2}{\delta }}{2m}}. \tag{2.20}

---

\begin{proof} 令 $h_1,\dots ,h_{|\mathcal{H}|}$ 为 $\mathcal{H}$ 的元素。使用并集界限并将 推论 2.11 应用于每个假设得到：

$$\begin{array}{rl}& \mathbb{P}\left[\exists h\in \mathcal{H}\left|{\hat{R}}_S\left(h\right)-R\left(h\right)\right|>ϵ\right]\\ =& \mathbb{P}[\left(\left|{\hat{R}}_S\left(h_1\right)-R\left(h_1\right)\right|>ϵ\right)\vee \\ & \dots \vee \left(\left|{\hat{R}}_S\left(h_{|\mathcal{H}|}\right)-R\left(h_{|\mathcal{H}|}\right)\right|>ϵ\right)]\\ \le & \sum _{h\in \mathcal{H}}\mathbb{P}\left[\left|{\hat{R}}_S\left(h\right)-R\left(h\right)\right|>ϵ\right]\\ \le & 2\left|\mathcal{H}\right|\exp \left(-2m{ϵ}^2\right)\end{array}$$

将右侧设置为等于 $\delta$ 完成证明。 \end{proof}

---

因此，对于有限的假设集 $\mathcal{H}$ ，

$$R\left(h\right)\le {\hat{R}}_S\left(h\right)+O\left(\sqrt{\frac{{\log }_2\left|\mathcal{H}\right|}{m}}\right).$$

Remark

• 如前所述，${\log }_2\left|\mathcal{H}\right|$ 可以解释为表示 $\mathcal{H}$ 所需的位数。
• 与一致情况下的泛化界限相关的其他几个类似评论也可以在这里提出：
  • 较大的样本大小 $m$ 保证更好的泛化，并且界限随 $\left|\mathcal{H}\right|$ 增加而增加，但仅以对数方式。
• 但是，在这里，界限是 $\frac{{\log }_2|\mathcal{H}|}{m}$ 的一个较不利的函数；
  • 它与这个项的 平方根 成比例变化。
  • 这不是一个小的代价：对于固定的 $\left|\mathcal{H}\right|$， 要达到一致情况下的相同保证，需要的标记样本数量是平方级的增加。

---

$$R\left(h\right)\le {\hat{R}}_S\left(h\right)+O\left(\sqrt{\frac{{\log }_2\left|\mathcal{H}\right|}{m}}\right).$$

奥卡姆剃刀原则 (Occam’s Razor principle)