霍夫丁不等式 和 泛化误差上界

这是我阅读《统计学习方法》的第一篇笔记。在书中 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. 本文的不足

  1. 关于 Markov Inequality 的证明还没有。
  2. [3] 中用杰森不等式证明 Hoeffding Lemma,虽然差个系数,但是也值得看一下
  3. 在我的文章里,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] 泛化误差上界(证明详推)

发表评论