这是我阅读《统计学习方法》的第一篇笔记。在书中 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] 泛化误差上界(证明详推)