这是我阅读《统计学习方法》的第一篇笔记。在书中 P25 1.6.2 泛化误差上界部分。书中的证明比较简略，本文将手把手、详细展开，包括 Hoeffding Inequality（书中版本）的证明。我搜到的中文相关文章，都证明得非常复杂，但其实没有很复杂的。
本文虽然没什么自己的感悟，只是把不同人零碎的证明进行整理（主要是英译中），并统一字母为《统计学习方法》书中字母。但是我相信，这是全世界最易懂的、最系统的（中文）霍夫丁不等式证明，高中水平即可理解。
1. Hoeffding Inequality
设 $X_1,X_2,…,X_N$ 是独立随机变量，且 $X_i \in [a_i,b_i], \; i=1,2,…,N$；均值 $\overline{X} = \frac{1}{N}\sum_{i=1}^NX_i$，则对 $\forall\; t > 0$ 有
$$ \begin{aligned} P \Big[ \overline { X } – E [ \overline { X } ] \geq t \Big] \leq \exp \Bigg( – \frac { 2 N^ { 2 }t ^ { 2 } } {\sum _ { i = 1 } ^ { n } ( b _ { i } – a _ { i } ) ^ { 2 }} \Bigg) \end{aligned} $$
$$ \begin{aligned} P \Big[ E [ \overline { X } ] – \overline { X } \leq t \Big] \leq \exp \Bigg( – \frac { 2 N^ { 2 }t ^ { 2 } } {\sum _ { i = 1 } ^ { n } ( b _ { i } – a _ { i } ) ^ { 2 }} \Bigg) \end{aligned} $$
要证 Hoeffding Inequality，需要先证明 Chernoff Bound 和 Hoeffding Lemma 这两个引理。而为了引出 Chernoff bound，我将从 Markov Inequality 和 Chebyshev Bound 说起。
ps：本文为了好看，所有求概率、求期望，均使用方括号。
1.1 Markov Inequality
若 $X$ 为非负随机变量，那么对于 $\forall \;\lambda>0$，有
$$P[X>\lambda] \le \frac{E[X]}{\lambda}$$
证明：
$$ \begin{aligned} E[X] =& \int_0^\infty xp(x)dx \ge \int_{\lambda}^\infty xp(x)dx\\ \ge& \lambda\int_{\lambda}^\infty p(x)dx = \lambda P[X\ge \lambda] \end{aligned} $$
即 $P[X>\lambda] \le \dfrac{E[X]}{\lambda}$，得证
注意，这里的 $X$ 可以代换成任意的 $f(X)$，即
$$P[f(X)>f(\lambda)] \le \frac{E[f(X)]}{f(\lambda)}$$
如果 $f$ 是一个单调不减的函数，更有：
$$P[X>\lambda] = P[f(X)>f(\lambda)] \le \frac{E[f(X)]}{f(\lambda)}$$
（这理论我是在 [4] 看到的，记得之前在方浩概率论的视频里也看到过，具体证明还 #TODO）
1.2 Chebyshev Bound
Chebyshev Bound 就是对上面定理的应用，我们令 $f(X) = (X-E[X])^2$，则
$$P[|X-E[X]|\ge\lambda] = P[(X-E[X])^2\ge \lambda^2] \le \frac{E[(X-E[X])^2]}{\lambda^2} = \frac{var(X)}{\lambda^2}$$
是不是很眼熟！对，这就是考研数学里面的切比雪夫不等式！好亲切 T_T
1.3 Chernoff Bound
若 $X$ 为非负随机变量，那么对于 $\forall \;\lambda,t>0$，有
$$P[X\ge E[X] + t] \le \mathop{\min_{\lambda \ge 0}} \dfrac{E[e^{\lambda (X-E[X])}]}{e^{\lambda t}}$$
$$P[X\le E[X] – t] \le \mathop{\min_{\lambda \ge 0}} \dfrac{E[e^{\lambda (E[X]-X)}]}{e^{\lambda t}}$$
对于 $\forall \; \lambda > 0$，如果 $X\ge E[X] + t$，那么必然有
$$e^{\lambda X} \ge e^{\lambda E[X] + \lambda t}$$ $$e^{\lambda (X-E[X])} \ge e^{\lambda t}$$
根据 Markov Inequality，我们有
$$P[X-E[X]\ge t] = P[e^{\lambda(X-E[X])}\ge e^{\lambda t}] \le \frac{E[e^{\lambda(X-E[X])}]}{e^{\lambda t}}$$
再把 $\dfrac{E[e^{\lambda (X-E[X])}]}{e^{\lambda t}}$ 看成关于 $\lambda$ 的函数，第一个式子显然得证。第二个对称的，同理。
1.4 Hoeffding Lemma
假设 $X$ 是一个随机变量，且满足 $X \in [a,b]$ 以及 $E(X) = 0$。那么对于 $\forall \;\lambda>0$，有
$$E(e^{\lambda X})\le \exp\Big(\dfrac{\lambda^2(b-a)^2}{8}\Big)$$
证明：
显然 $f(x) = e^{\lambda x}$ 是一个凸函数，所以对于 $\forall \alpha \in (0,1)$，有
$$f(x)\le \alpha f(a) + (1-\alpha)f(b)$$
令 $\alpha = \dfrac{b-x}{b-a}$，则对 $\forall \; x \in [a,b]$，有
$$e^{\lambda x} \le \frac{b-x}{b-a}e^{\lambda a} + \frac{x-a}{b-a}e^{\lambda b}$$
将 $x$ 看做取值于 $[a,b]$ 的随机变量 $X$，两边求期望，又 $E(X) = 0$，故有
$$E(e^{\lambda X}) \le \frac{b}{b-a}e^{\lambda a} – \frac{a}{b-a}e^{\lambda b}$$
接下来进行变量代换：令 $h = \lambda(b-a),\; p = \dfrac{-a}{b-a}, \; L(h) = – hp + \ln(1-p+pe^h)$（我也不知道怎么设计的），则有
$$ \begin{aligned} \exp\Big(L(h)\Big) =& \exp\Big(-hp+\ln(1-p+pe^h)\Big) \\ =& (1-p+pe^h)e^{-hp}\\ =& \frac{b}{b-a}e^{\lambda a} – \frac{a}{b-a} e^{\lambda b} \end{aligned} $$
由上面两式可得，$E(e^{\lambda X}) \le e^{L(h)}$，因此要证 Hoeffding lemma，只需证 $\exp\Big(L(h)\Big) < \exp\Big(\frac{\lambda^2(b-a)^2}{8}\Big)$，又 $\lambda^2(b-a)^2\ = h^2$，故只需证
$$g(h) = L(h) – \frac{h^2}{8} = -hp + \ln(1-p+pe^h) – \frac{h^2}{8} \le 0,\;(h>0)$$
显然，$g(0) = 0$，又
$$g'(h) = -p + \dfrac{pe^h}{1-p+pe^h} – \dfrac{h}{4}$$
显然，$g'(0) = 0$，又
$$g”(h) = \frac{(1-p)pe^h}{1-p+pe^h} – \frac{1}{4}$$
令 $m = 1-p,n = pe^h$，则有
$$g”(h) = \frac{mn}{(m+n)^2} – \frac{1}{4} = \dfrac{1}{\frac{n}{m} + \frac{m}{n} + 2} – \frac{1}{4} \le 0$$
因此 $g'(h)$ 单调递减，又 $g'(0) = 0$，故 $g(h)$ 单调递减，又 $g(0) = 0$，故 $g(h) \le 0$，得证。
1.5 Hoeffding Inequality 证明
文章写的太长了，为了不用往上翻，这里回忆一下刚刚得到的引理：
Chernoff Bound：$P\Big[X\ge E[X] + t\Big] \le \dfrac{E[e^{\lambda (X-E[X])}]}{e^{\lambda t}}$
Hoeffding Lemma：$E(e^{\lambda X})\le \exp\Big(\dfrac{\lambda^2(b-a)^2}{8}\Big)$
以及要证的 Hoeffding Inequality：$P \Big[ \overline { X } – E ( \overline { X } ) \geq t \Big] \leq \exp \Bigg( – \dfrac { 2 N^ { 2 }t ^ { 2 } } {\sum _ { i = 1 } ^ { n } ( b _ { i } – a _ { i } ) ^ { 2 }} \Bigg)$
接下来开始证明：
$$ \begin{aligned} P \Big[ \overline { X } – E ( \overline { X } ) \geq t \Big] =& P \Big[ \frac{1}{N}\sum_{i=1}^N (X_i – E[X_i]) \geq t \Big] \\ =& P \Big[ \sum_{i=1}^N (X_i – E[X_i]) \geq Nt \Big] \\ \le& E \Big[\exp\Big( \lambda\sum_{i=1}^N(X_i – E[X_i])\Big)\Big] e^{-\lambda Nt} \\ =& \Big( \prod_{i=1}^N E[e^{\lambda(X_i – E[X_i])}]\Big) e^{-\lambda Nt} \\ \le& \Big( \prod_{i=1}^N \frac{\lambda^2(b_i-a_i)^2}{8}\Big) e^{-\lambda Nt} \\ =& \exp \Big(\frac{\lambda^2\sum_{i=1}^N(b_i-a_i)^2}{8} – \lambda Nt\Big) \end{aligned} $$
所以
$$ P \Big[ \overline { X } – E ( \overline { X } ) \geq t \Big] \le \mathop{\min_{\lambda \ge 0}} \exp \Big(\frac{\lambda^2\sum_{i=1}^N(b_i-a_i)^2}{8} – \lambda Nt\Big) = \exp \Big( – \frac { 2 N^ { 2 }t ^ { 2 } } {\sum _ { i = 1 } ^ { n } ( b _ { i } – a _ { i } ) ^ { 2 }} \Big) $$
上面的答案是对函数直接求极值得到的。
以上就是 Hoeffding Inequality 的证明。
2. 泛化误差上界
先定义一些概念：
损失函数：$L(Y,f(X))$
期望风险：$R(f) = E_p[L(Y,f(X))]$
经验风险：$\hat{R}(f) = \dfrac{1}{N}\sum_{i=1}^N L(y_i,f(x_i))$
刚得到的 Hoeffding Inequality：（这次用的第二个）
$$P \Big[ E [ \overline { X }] – \overline { X } \geq t \Big] \leq \exp \Bigg( – \dfrac { 2 N^ { 2 }t ^ { 2 } } {\sum _ { i = 1 } ^ { n } ( b _ { i } – a _ { i } ) ^ { 2 }} \Bigg)$$
再把书里泛化误差上界的定理抄过来：
对二分类问题，当假设空间是有限个函数的集合 $\mathcal{F} = {f_a,f_2,…,f_d}$ 时，对 $\forall f \in \mathcal{F}$，至少以概率 $1-\delta, 0<\delta<1$，使以下不等式成立：
$$R(f)\le\hat{R}(f) + \varepsilon(d,N,\delta)$$
其中
$$\varepsilon(d,N,\delta) = \sqrt{\frac{1}{2N}(\log d + \log \frac{1}{\delta})}$$
证明：先把 Hoeffding Inequality 改写一下形式：
$$P \Big[ E [ S_N ] – S_N\geq N\varepsilon \Big] \leq \exp \Bigg( – \dfrac { 2(N\varepsilon) ^ { 2 } } {\sum _ { i = 1 } ^ { n } ( b _ { i } – a _ { i } ) ^ { 2 }} \Bigg)$$
看这个式子，第一眼一定以为是将 $t$ 直接代换成 $N\varepsilon$ 对吧？但是仔细一看，右边分子怎么少个 $N^2$？这里解释一下，$\overline { X } = \dfrac{S_N}{N}$，因此 $E[\overline { X }] = \dfrac{E[S_N]}{N}$，因此 $P \Big[ \overline { X } – E [ \overline { X } ] \geq \varepsilon \Big] = P \Big[ S_N- E [ S_N ] \geq N\varepsilon \Big]$，改写形式前后 $t$ 和 $\varepsilon$ 是一个东西，这个感觉是《统计学习方法》书里面没有自行统一。在同一页的公式都不把字母统一，实在过分！
继续。由于是二分类问题，因此 $X$ 不是一就是零，因此 $b-a = 1-0 = 1$，故有
$$P \Big[ E [ S_N ] – S_N \geq N\varepsilon \Big] \leq \exp ( – 2N\varepsilon^2 )$$
根据我们上面定义的期望风险和经验风险，这俩其实就是统计量，即 $R(f) = \dfrac{E [ S_N ]}{N},\;\hat{R}(f) = \dfrac{S_N}{N}$，即书中的式 1.36（这就是书上写的“不难得知”，草（一种植物））
$$P \Big[ R(f) – \hat{R}(f) \geq \varepsilon \Big] \leq \exp ( – 2N\varepsilon^2 )$$
$\mathcal{F} = {f_a,f_2,…,f_d}$ 是一个有限集合，上面的十字表明 $\mathcal{F}$ 中的任何一个函数 $f$ 作为模型时 的泛化误差的上限。如果要求 $\mathcal{F}$ 中存在某个 $f$ 满足这个式子，则由概率的加和规则可以得到，对于 $\forall f\in \mathcal{F}$，有
$$ \begin{aligned} & P \Big[\exists f \in \mathcal{F}: R(f) – \hat{R}(f)\geq \varepsilon \Big] \\ =& P \Big[ \bigcup_{f \in \mathcal{F}} { R(f) – \hat{R}(f)\geq \varepsilon } \Big] \\ \le&\sum_{f \in \mathcal{F}} P \Big[ R(f) – \hat{R}(f) \geq \varepsilon \Big]\\ \le&d \exp ( – 2N\varepsilon^2 ) \end{aligned} $$
等价的，有
$$ P \Big[R(f) – \hat{R}(f) < \varepsilon \Big] \ge 1- d \exp ( – 2N\varepsilon^2 ) $$
令 $\delta = d \exp ( – 2N\varepsilon^2 )$，则
$$ P \Big[R(f) < \hat{R}(f) + \varepsilon \Big] \ge 1- \delta $$
得证（那个 $\varepsilon$ 的表达式直接用 $\delta$ 的定义反推即可）
3. 本文的不足
- 关于 Markov Inequality 的证明还没有。
- [3] 中用杰森不等式证明 Hoeffding Lemma，虽然差个系数，但是也值得看一下
- 在我的文章里，Hoeffding Lemma 要求 $E[X] = 0$，但是在 1.5 忽视了这个问题。总之，还是 Hoeffding Lemma 证明还有缺陷。
4. 引用与延伸阅读
[1] CS229 Supplemental Lecture notes Hoeffding’s inequality 写得真是好，是本文主要抄袭来源，推荐阅读原文。
[2] Hoeffding不等式证明 前半部分挺好，就是最后推导的是 Hoeffding Inequality 的第一种形式。
[3] 关于Hoeffding不等式及泛化误差上界 我最反感这种拼凑的博客了，难以下咽，不过对我还是有一点帮助
[4] Chernoff bound 只看了前面一小部分，没太大用
[5] Hoeffding不等式的证明 这篇文章很多错，不过对我还是有一点帮助
[6] 泛化误差上界（证明详推）