2.3 对于有限假设集的不一致情况下的保证

• 在最一般的情况下，可能不存在与标记训练样本一致的 $\mathcal{H}$ 中的假设。
• 实际上，这在实践中是典型的情况，其中学习问题可能有些困难，或者概念类比学习算法使用的假设集更复杂。

鸭兔错觉 - Wikiwand articles

• 然而，在训练样本上错误数量较少的不一致假设可能是有用的，正如我们将看到的， 它们在某些假设下可以从有利的保证中受益。
• 本节将呈现了针对这种不一致情况和有限假设集的学习保证。

---

为了在这个更一般的设置中推导学习保证，我们将使用Hoeffding不等式（定理D.2）或以下推论，它将单个假设的泛化误差和经验误差联系起来。

推论 2.10

确定$ϵ>0$。那么，对于任何假设$h:\mathcal{X}\to \{0,1\}$，以下不等式成立：

$$\underset{S\sim {\mathcal{D}}^m}{\mathbb{P}}\left[{\hat{R}}_S\left(h\right)-R\left(h\right)\ge ϵ\right]\le \exp \left(-2m{ϵ}^2\right)\text{\hspace{1em}(2.14)}$$ $$\underset{S\sim {\mathcal{D}}^m}{\mathbb{P}}\left[{\hat{R}}_S\left(h\right)-R\left(h\right)\le -ϵ\right]\le \exp \left(-2m{ϵ}^2\right).\text{\hspace{1em}(2.15)}$$

通过并集界限，这暗示了以下双向不等式：

$$\underset{S\sim {\mathcal{D}}^m}{\mathbb{P}}\left[\left|{\hat{R}}_S\left(h\right)-R\left(h\right)\right|\ge ϵ\right]\le 2\exp \left(-2m{ϵ}^2\right).\text{\hspace{1em}(2.16)}$$

\begin{proof} 结果直接来自定理D.2。 \end{proof}

---

将 (2.16) 右侧设置为等于 $\delta$ 并求解 $ϵ$, 立即为单个假设得到以下界限。

推论 2.11（泛化边界 — 单个假设）

给定一个假设 $h:\mathcal{X}\to \{0,1\}$。 那么，对于任何 $\delta >0$， 以下不等式至少以 $1-\delta$ 的概率成立： R\left( h\right) \leq {\widehat{R}}_{S}\left( h\right) + \sqrt{\frac{\log \frac{2}{\delta }}{2m}} \tag{2.17}

---

示例 2.12 （抛硬币）说明了在简单情况下这个推论的应用。

由上述示例可见，与一致情况的证明一样，我们需要推导出一个均匀收敛边界，即对于所有假设 $h\in \mathcal{H}$ 都以高概率成立的一个边界: 定理2.13 学习界限 — 有限H 不一致情况。