不等式(二)-Hoeffding不等式

作者: _与谁同坐_ | 来源:发表于2019-07-05 21:05 被阅读0次

Hoeffding不等式简介
不等式(二)-Hoeffding不等式
Hoeffding 不等式
数学笔记：不等式
高中数学题型五十六《解不等式》
4. 泛化理论
8-Bias and Variance Tradeoff
柏舟日記｜辭舊迎新
【机器学习基础】理解为什么机器可以学习3——VC理论
【高等数学】不等式的解和解集

接着上一节的那些不等式们(一)-Markov与Chebyshev不等式
本节将学习Hoeffding不等式。

Hoeffding不等式

作用与Chebyshev不等式类似，但区间更紧致(增加了独立性约束)

Hoeffding不等式
设 $Y_1,...Y_n$ 相互独立，且 $E(Y_i) = 0$ ，且 $a_i \leq Y_i \leq b_i$ ，令 $\epsilon > 0$ ，则对任意 $t>0$ ，
$P(\sum_{i=1}^{n}Y_i \geq \epsilon) \leq e^{-t\epsilon} \prod_{i=1}^{n}e^{t^2(b_i-a_i)^2/8}$

证明过程如下：
$\begin{eqnarray} P \Bigg( \sum_{i=1}^{n}Y_i \geq \epsilon \Bigg) &=& P \Bigg( t \sum_{i=1}^{n}Y_i \geq t \epsilon \Bigg ) \\ &=& P \Bigg(e^{t \sum \limits_{i=1}^{n}Y_i} \geq e^{t \epsilon} \Bigg) \\ & \leq & e^{-t \epsilon} E\Bigg(e^{t \sum \limits_{i=1}^{n}Y_i} \Bigg) \qquad (Markov 不等式) \\ &=& e^{-t \epsilon} \prod_{i=1}^{n} E \Bigg( e^{t Y_i} \Bigg) \qquad (Y_1,...Y_n相互独立，期望的性质) \end{eqnarray}$

对于凸函数 $f(x) = e^x$ ，对于任意 $\alpha \in [0, 1]$ ，和 $x \in [a, b]$ 都满足
$f(x) \leq \alpha f(a) + (1 - \alpha)f(b)$
如图所示：

因为 $a_i \leq Y_i \leq b_i$ ，即 $Y_i \in [a_i, b_i]$ ，令 $\alpha = \frac{b_i-Y_i }{b_i - a_i} \in [0, 1]$ ，则

$e^{tY_i} \leq \frac{(b_i - Y_i)}{(b_i - a_i)} e^{ta_i} + \frac{(Y_i - a_i)}{(b_i - a_i)} e^{tb_i}$

又因为 $E(Y_i) = 0$ ，对两边同时取期望，

$E(e^{tY_i}) \leq \frac{b_i - E(Y_i)}{(b_i - a_i)} e^{ta_i} + \frac{E(Y_i) - a_i}{(b_i - a_i)} e^{tb_i} = \frac{b_i}{(b_i - a_i)} e^{ta_i} - \frac{a_i}{(b_i - a_i)} e^{tb_i}$
记 $u = t(b_i - a_i)$ ，和 $\gamma = -a_i/b_i - a_i$ ，可以将上式右边写作 $e^{ -\gamma u + log(1 - \gamma + \gamma e^u)}$

记为 $e^{g(u)}$ ，我们对 $g(u)$ 作泰勒展开
$g(u) = \frac{g(0)}{0!}(u-0)^0 + \frac{g^{'}(0)}{1!}(u-0)^1 + \frac{g^{''}(0)}{2!}(u-0)^2 + o(u^2)$

易得 $g(0) = g^{'}(0) = 0$ ，而
$g^{''}(u) = \frac{\gamma(1-\gamma)e^u}{(1- \gamma + \gamma e^u)^2}$

得到 $g^{''}(0) = \gamma(1-\gamma) \leq 1/4$ ，带入泰勒展开式，得到
$g(u) = \frac{g^{''}(0)}{2!}(u-0)^2 + o(u^2) \leq \frac{1/4}{2!}(u-0)^2 = \frac{u^2}{8} = \frac{1}{8}t^2(b_i - a_i)^{2}$

因此，
$E(e^{tY_i}) \leq e^{g(u)} \leq e^{t^2(b_i - a_i)^{2}/8}$
不等式得证。

Hoeffding不等式
设 $Y_1,...Y_n$ 相互独立，且 $E(Y_i) = 0$ ，且 $a_i \leq Y_i \leq b_i$ ，令 $\epsilon > 0$ ，则对任意 $t>0$ ，
$P(\sum_{i=1}^{n}Y_i \geq \epsilon) \leq e^{-t\epsilon} \prod_{i=1}^{n}e^{t^2(b_i-a_i)^2/8}$
令 $X_1,...X_n \backsim Bernoulli(p)$ ，则对任意 $\epsilon > 0$ ，有
$P(|\overline{X} - p| > \epsilon) \leq 2e^{-2n\epsilon^2} \qquad (2)$
其中 $\overline{X_n} = \frac{1}{n}\sum_{i=1}^{n}X_i$

对于(2)式证明如下：
令 $Y_i = \frac{1}{n}(X_i - p)$ ，有 $E(Y_i) = 0$ ，且有
$\sum_{i=1}^{n} Y_i = \frac{1}{n} \sum_{i=1}^{n} (X_i - p) = \frac{1}{n}\sum_{i=1}^{n} X_i - p = \overline{X_n} - p$

又有 $a \leq Y_i \leq b$ ，因为 $X_1,...X_n \backsim Bernoulli(p)$ ，所以 $X_i$ 的取值只能是 $0$ ， $1$ ，因此 $a = - p/n$ ， $b = (1-p)/n$ ，那么 $(b-a)^2 = 1/n^2$
$P(\overline{X} - p > \epsilon) = p(\sum_{i=1}^{n} Y_i > \epsilon) \leq e^{-t\epsilon}e^{t^2/(8n)} \qquad (t>0)$

取 $t = 4n\epsilon$ ，我们得到 $P(\overline{X} - p > \epsilon) \leq e^{-2n\epsilon^2}$
同理可得 $P(\overline{X} - p < -\epsilon) \leq e^{-2n\epsilon^2}$
因此
$P(|\overline{X} - p| > \epsilon) \leq 2e^{-2n\epsilon^2}$

不同于其他的不等式是在收敛的情况下等式成立，Hoeffding不等式对于任意n都成立。

Hoeffding不等式应用

Reference

《All of Statistics: A Concise Course in Statistical Inference》by Wasserman, Larry
不等式 by 中科院卿来云老师课件

Hoeffding不等式简介
1 Hoeffding不等式 Hoeffding不等式是非常有用的一个不等式，在机器学习、统计学等领域，都发挥着巨...
不等式(二)-Hoeffding不等式
接着上一节的那些不等式们(一)-Markov与Chebyshev不等式本节将学习Hoeffding不等式。 Hoe...
Hoeffding 不等式
基础准备 1.定比分点公式点为上一点，则设，则证明： 2.凸函数性质设，为凸函数，则 3.markov不等式...
数学笔记：不等式
三角不等式伯努利不等式二项不等式均值不等式调和平均数、集合平均数、算术平均数和二次平均数杨氏不等式施瓦...
高中数学题型五十六《解不等式》
我们通常遇到的解不等式有一元二次不等式、含绝对值不等式、分式不等式，这里解的不等式是利用导数求单调性，再结合函数的...
4. 泛化理论
证明mh(N) 是多项式证明mh(N) 可以在Hoeffding不等式中代替M 证明mh(N)为多项式为了证明...
8-Bias and Variance Tradeoff
在这之前整理一下之前的脉络。首先我们一直强调的是让Ein尽量靠近Eout，最开始用了Hoeffding不等式，...
柏舟日記｜辭舊迎新
2022年01月31日深夜“均值不等式，柯西不等式，权方和不等式，舒尔不等式，琴生不等式，贝努利不等式，契比雪夫...
【机器学习基础】理解为什么机器可以学习3——VC理论
引入上一小节中，“理解为什么机器可以学习——Hoeffding不等式”中，我们介绍了有限假设空间中的概率边界。在...
【高等数学】不等式的解和解集
不等式概念：式子中有解不等式：解不等式的过程称之为不等式，解不等式的值的取值范围成为解值，解不等式的未知数的值称...