Foundation of Machine Learning 笔记第三部分——Guarantees for Finite Hypothesis Sets in Inconsistent Case

本文主要是介绍Foundation of Machine Learning 笔记第三部分——Guarantees for Finite Hypothesis Sets in Inconsistent Case，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

前言

注意事项：

1. 这个系列的文章虽然题为书本《Foundation of Machine Learning》的读书笔记，但实际我是直接对书本的部分内容进行了个人翻译，如果这个行为有不妥当的地方，敬请告知。
2. 由于知识面限制，部分名词的翻译可能存在错误，部分难以翻译的名词保留英文原词。为了防止误导大家，在这里声明本文仅供参考。
3. 本文基本翻译自《Foundation of Machine Learning》的2.3节。

正文

在大多数情况下，假设集 $H$ 中往往没有与训练样本一致 (consistent) 的假设。实际上在实践中，由于学习问题可能比较困难，或者 concept class 比学习算法所使用的假设集更复杂，上述情况很典型。但虽然不一致却在训练集上错误较少的假设也可以很实用，我们接下来会证明它的错误率同样能得到一定的保证。这一部分中，我们会证明不一致且假设集有限情况下的学习保证。

为了从更加通用的背景中推导学习保证，我们将使用 Hoeffding 不等式进行证明。

定理 D.1 Hoeffding 不等式

$X_1,\dots,X_m$ 是相互独立的随机变量，且对于 $i \in [1,m]$ 所有的 $X_i$ 在区间 $[a_i,b_i]$ 中取值。那么给定任意 $\epsilon \gt 0$，下列不等式对于样本集 $S_m = \sum _{i=1}^mX_i$ 成立：

$${\rm Pr}\left[S_m-E[S_m]\ge \epsilon\right]\le e^{-2\epsilon^2/\sum_{i=1}^m(b_i-a_i)^2}\tag{D.4}$$ $${\rm Pr}\left[S_m-E[S_m]\le - \epsilon\right]\le e^{-2\epsilon^2/\sum_{i=1}^m(b_i-a_i)^2}.\tag{D.5}$$
证明 Hoeffding 不等式的证明偏离了这一章的中心，请详见该书附录。

推论 2.1

固定且使 $\epsilon \gt 0$，用 $S$ 指代一个大小为 $m$ 的独立同分布假设集。然后，对于任意假设 $h:X\to \{0,1\}$，下列不等式成立：

$${\rm Pr_{S\sim D^m}}\left[\hat R(h)-R(h)\ge\epsilon\right]\le e^{-2m\epsilon^2}\tag{2.14}$$ $${\rm Pr_{S\sim D^m}}\left[\hat R(h)-R(h)\le-\epsilon\right]\le e^{-2m\epsilon^2}.\tag{2.15}$$ 通过 union bound，这两个单边的限制可以合并成双边的限制： $${\rm Pr_{S\sim D^m}}\left[|\hat R(h)-R(h)|\ge\epsilon\right]\le 2e^{-2m\epsilon^2}.\tag{2.16}$$
证明 $(2.14)$ 和 $(2.15)$ 均由 这个系列的第一篇中的 $(2.3)$ 及 Hoeffding 不等式可得。Union bound 的本质是不等式：
$$\begin{align} {\rm Pr}\left[A \lor B\right] & ={\rm Pr} [A] + {\rm Pr}[B]-{\rm Pr}[A \land B]\\ &\le {\rm Pr} [A] + {\rm Pr}[B]. \end{align}$$
则推论得证。

使 $(2.16)$ 的右侧等于 $\delta$ 并求解 $\epsilon$ 就能马上得到对于单个假设的上限。

推论 2.2 泛化限制——单一假设

固定一个假设 $h:\mathcal{X}\to \{0,1\}$。那么对于任意 $\delta\gt 0$，下面的不等式至少有 $1-\delta$ 的概率成立：

$$R(h)\le\hat R(h)+\sqrt{\frac{\log{\frac{2}{\delta}}}{2m}}.\tag{2.17}$$
证明 根据 $(2.16)$ 得 $${\rm Pr_{S\sim D^m}}\left[|\hat R(h)-R(h)|\le\epsilon\right]\ge 1 - 2e^{-2m\epsilon^2}.$$ 使 $\delta = 2e^{-2m\epsilon^2}$，求解 $\delta = 2e^{-2m\epsilon^2}$ 得到： $$\epsilon= \sqrt{\frac{\log{\frac{2}{\delta}}}{2m}}.$$ 有： $$\begin{align} {\rm Pr_{S\sim D^m}}\left[R(h)-\hat R(h)\le\sqrt{\frac{\log{\frac{2}{\delta}}}{2m}}\right] &\ge {\rm Pr_{S\sim D^m}}\left[|\hat R(h)-R(h)|\le\sqrt{\frac{\log{\frac{2}{\delta}}}{2m}}\right] \\ &\ge 1-\delta. \end{align}$$ 证明完毕。

定理 2.2 Learning bound ——有限 $H$，不一致的情况

设$H$ 是一个有限的假设集，那么对于任意 $\delta \gt 0$，下面的不等式至少有 $1-\delta$ 的几率成立：

$$\forall h\in H,\quad R(h)\le\hat R(h)+\sqrt{\frac{\log{|H|}+\log{\frac{2}{\delta}}}{2m}}.\tag{2.20}$$
证明 设 $h_1,\dots,h_{|H|}$ 为 $H$ 的元素。使用 union bound 以及对每个假设使用推论 2.2，可得： $$\begin{align}&{\rm Pr}\left[\exists h \in H，\quad|\hat R(h)-R(h)|\gt\epsilon\right] \\ =\ &{\rm Pr}\left[\left(\left|\hat R(h_1)-R(h_1)\right|\gt\epsilon\right)\lor\dots\lor\left(\left|\hat R(h_{|H|})-R(h_{|H|})\right|\gt\epsilon\right)\right] \\ \le\ &\sum_{h \in H}{\rm Pr}\left[\left|\hat R(h)-R(h)\right|\gt\epsilon\right] \\ \le\ &2|H|e^{-2m\epsilon^2}. \end{align}$$ 使右侧等于 $\delta$ 并且解 $\epsilon$，证明完毕。

因此，对于一个有限的假设集 $H$，

$$R(h)\le \hat R(h) + \mathcal{O}\left(\sqrt{\frac{\log_2{|H|}}{m}}\right).$$ 就跟前面指出的一样， $\log_2{|H|}$ 可以解读为表示 $H$ 所需要的二进制位数。在上一节中一致且 有限的情况下，我们得到了一些结论：样本量越大泛化效果越好，泛化误差的上限随着 $|H|$ 升高而升高，但只是以对数级的关系上升。在这里，得到的误差上限是一个比 $\frac{\log_2{|H|}}{m}$ 要不利的函数——它随着这一项的开根变化而变化 (我的理解：因为 $\frac{\log_2{|H|}}{m}$ 比1要小，所以开根得到的值比原值要高，使得泛化性能变差)。如果我们固定 $|H|$，并且希望在一致和不一致的情况下获取相同的保证，那么在不一致的情况下我们需要二次于一致情况的带标签样本数。

要注意的是，这个上限告诉我们应该去权衡经验误差和假设集大小：一个大的假设集会被后者惩罚，但是也能够降低前者。但是当经验误差变化不大的时候，我们往往应该使用更小的假设集。这可以看做是所谓的奥卡姆剃刀原则 ( Ocaam’s Razor principle ) 的一个例子。

我的疑惑

定理2.2不能说明不一致的学习问题满足上一节中说到的 PAC 可学习的要求，事实上定理2.2说明的仅仅是：在样本量增多的情况下，任意一个假设的训练误差都会越来越逼近泛化误差。其实这种学习问题根本就不满足前面说到的 PAC 学习，那么它的泛化误差是否满足某种其他上限呢？答案是肯定的。

为了把 PAC 学习框架拓展到这类问题上，人们把 PAC 学习的要求放松了，定义了一种新的 PAC 学习框架：不可知 PAC 学习 ( Agnostic PAC-learning )。它的定义将在本书的下一部分被提出来，在下一篇博客中，我也会尝试去证明不一致情况学习问题满足不可知 PAC 学习。

这篇关于Foundation of Machine Learning 笔记第三部分——Guarantees for Finite Hypothesis Sets in Inconsistent Case的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---