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

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

前言

注意事项：

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

正文

假设集有限且满足一致性假设下的 PAC 保证

有某些学习任务中，算法总是可以保证其返回的假设 $h_S$ 在训练集 $S$ 下误差为0，我们称假设 $h_S$ 一致 ( consistent )，称这种问题符合一致性假设。在前一篇文章中我们提到过样本复杂度这个概念，它指的是学习算法要得到近似解所需的样本数。在这一部分中，我们为符合一致性假设且假设集的基数 $|H|$ 有限的学习问题提出一个通用的样本复杂度界限 ( sample complexity bound )，或称为泛化界 ( generalization bound )。由于我们只考虑一致的假设，我们进一步假定目标 concept $c$ 属于 $H$。

定理 2.1 learning bound —— 有限的 $H$，一致的情况下

设 $H$ 为一个由有限个从 $\mathcal{X}$ 映射到 $\mathcal{Y}$ 的函数构成的集合。 设 $\mathcal{A}$ 看作一个能从任意目标 concept $c \in H$ 和任意服从独立同分布的样本集 $S$ 中学习到至少一个一致假设 $h_S:\hat R\left(h_S\right)=0$ 的算法。那么对于任意的 $\epsilon,\delta\gt0$，如果有

$$m\ge\frac{1}{\epsilon}\left(\log{|H|} + \log{\frac{1}{\delta}}\right).\tag{2.8}$$ 不等式 ${\rm Pr}_{S\sim D^m}\left[R(h_S)\le\epsilon\right]\ge1-\delta$ 成立。$(2.8)$ 得到的是样本复杂度界限，它与下面的泛化界是等同的：对于任意 $\epsilon,\delta\gt0$，下式至少有 $1-\delta$ 的概率成立： $$R(h_S)\le\frac{1}{m}\left(\log{|H|}+\log{\frac{1}{\delta}}\right).\tag{2.9}$$
证明：固定 $\epsilon$。我们不知道哪一个一致假设 $h_S \in H$ 会被算法 $\mathcal{A}$ 选中，这取决于训练样本 $S$。因此，我们需要给出一个对所有一致假设都适用的界限，这样这个界限就必然适用于 $h_S$。于是，我们求出假设 $h \in H$ 一致并且泛化误差大于 $\epsilon$ 的概率界限 (我的理解：因为我们不知道哪一个假设集会被选中，所以只能希望所有一致的假设的泛化误差都小于等于 $\epsilon$，换句话说，只要存在一个一致且泛化误差大于 $\epsilon$ 的假设，我们就认为目标 concept 不能通过 $H$ PAC 学习，下面通过求解出现这样一个假设的概率上界，又因为我们已经假定了 $H$ 中起码有一个假设是一致的，最后反过来可以得到所有一致假设泛化误差都小于等于 $\epsilon$ 的概率下界)：
$$\begin{split} &{\rm Pr}\left[\exists h \in H:\hat R(h)=0 \land R(h)\gt\epsilon \right] \\ =&{\rm Pr}\left[ \left(h_1 \in H,\hat R(h_1)=0 \land R(h_1) \gt \epsilon\right) \lor \left(h_2 \in H,\hat R(h_2)=0 \land R(h_2) \gt \epsilon\right) \lor \cdots \right] \\ \le&\sum_{h \in H}{\rm Pr}\left[\hat R(h)=0 \land R(h) \gt \epsilon \right] \quad\text{(union bound)} \\ \le&\sum_{h \in H} {\rm Pr} \left[\hat R(h)=0|R(h)\lt\epsilon\right].\quad\text{(definition of conditional probability)} \end{split}$$
对于任意泛化误差大于 $\epsilon$ 的假设 $h \in H$，$h$ 在样本集 $S$ 上误差为0的概率的上界为： $${\rm Pr}\left[ \hat R(h)=0|R(h)\gt\epsilon\right]\le{(1-\epsilon)}^m.$$ 前面的不等式有： $${\rm Pr}\left[\exists h\in H:\hat R(h)\land R(h)\gt \epsilon\right]\le|H|{(1-\epsilon)}^m.$$ 进一步对右式进行放大，因为对于任意的 $x\ge0$ 有 $1-x\le e^{-x}$，则上式进一步化成： $${\rm Pr}\left[\exists h\in H:\hat R(h)\land R(h)\gt \epsilon\right]\le|H|e^{-m\epsilon}.$$ 故只要 $\delta \ge |H|e^{-m\epsilon}$成立，就有 $${\rm Pr}\left[\exists h\in H:\hat R(h)\land R(h)\gt \epsilon\right]\le\delta$$ 上式意味着存在一个一致且泛化误差大于 $\epsilon$ 的概率是小于 $\delta$ 的，那么我们反过来可以认为不存在这种假设的概率是大于等于 $1-\delta$ 的。也就是说只要算法 $\mathcal{A}$ 返回的是一个一致假设，我们就能保证它的泛化误差小于 $\epsilon$ 的概率大于 $\delta$。

我们可以把 $\delta \ge |H|e^{-m\epsilon}$ 化成

$$m\ge\frac{1}{\epsilon}\left(\log{|H|} + \log{\frac{1}{\delta}}\right).$$ 这样就证明了样本复杂度界限。只要对上式进行简单的转化，我们同样能得到泛化界的证明。证毕。

这个定理说明，当假设集 $H$ 大小有限时，任何一个一致的算法必然PAC可学习，因为 $(2.8)$ 给出的样本复杂度与 $1/\epsilon$ 和 $1/\delta$ 的一个多项式相关。$(2.9)$ 说明了，一致假设的泛化误差是被限制在一个随样本量 $m$ 增大而减少的数值之下的。这与我们对学习算法的经验是一致的：带标签的训练样本越多，学习算法效果越好。这个定理所保证的 $\mathcal{O}(1/m)$ 的下降率其实已经非常优秀了。

为了得到一致的假设，我们要付出的代价是需要更大的假设集，以使得假设集包含目标 concept。显然，$(2.9)$ 规定的上限是随着 $|H|$ 上升而上升的。但好事是这种上升只是对数级的。如果我们把 $\log {|H|}$ 这一项转换成 $\log_2{|H|}$ ——他们只有一个常数因子的差别，就能把这项理解为表示 $H$ 所需的二进制位数。因此该定理所提供的泛化保证是受位数 $log_2{H}$ 和样本量 m <script type="math/tex" id="MathJax-Element-67">m</script> 控制的。

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

---