CS229 Hoeffding不等式补充资料

课程视频地址:http://open.163.com/special/opencourse/machinelearning.html

课程主页:http://cs229.stanford.edu/

更具体的资料链接:https://www.jianshu.com/p/0a6ef31ff77a

笔记参考自中文翻译版:https://github.com/Kivy-CN/Stanford-CS-229-CN

这一部分主要回顾有关Hoeffding不等式的补充资料。

常用的概率不等式

关于随机变量,人们往往对如下概率感兴趣

Hoeffding不等式正是对这种概率的一个估计,在证明Hoeffding不等式之前,要介绍几个常用的命题。

命题 1 (马尔可夫不等式)

令$Z\ge 0$是一个非负随机变量,那么对任意$t\ge 0$,

证明:注意到$\mathbb P(Z\ge t) = \mathbb E [1\{Z\ge t\}]$,注意到当$Z\ge t$时,$\frac Z t \ge 1 =1\{Z\ge t\}$,当$Z<t$时,$\frac Z t\ge 0=1 \{Z\ge t\}]$,从而$\frac Z t\ge 1\{Z\ge t\}$成立,所以

关于马尔可夫不等式有如下推论:

推论 1

令$Z\ge 0$是一个非负随机变量,$f(x)$在$[0,+\infty)$单调递增,且$f(x)\ge 0$,那么对任意$t\ge 0$,

证明:由$f(x)$的单调性可知

将$f(Z)$视为随机变量,应用马尔可夫不等式可得

这个推论是非常有用的,取一些特殊的$f$可以得到很多很有用的不等式,例如切比雪夫不等式。

命题 2 (切比雪夫不等式)

令$Z$是任意满足$\text{Var}(Z) <\infty$的随机变量,那么

证明:注意到

将$|Z-\mathbb E[Z]|$视为随机变量(非负随机变量),取$f(x) =x^2$,应用推论1可得

矩母函数

这一部分简单介绍矩母函数。对于任意随机变量$Z$,定义其矩母函数为

关于矩母函数,有非常重要的Chernoff界:

命题 3 (Chernoff界)

令$Z$是任意随机变量,那么对于任意$t\ge 0$,

证明:只证第一个不等式,第二个不等式同理(只要对第一个不等式令$Z=-Z$即可)。

对于$\lambda \ge 0$,$e^{\lambda t}$单调,所以

对随机变量$e^{\lambda Z-\lambda \mathbb E[Z] }$应用马尔可夫不等式可得

上式对任意$\lambda \ge 0$都成立,所以

矩母函数的性质与例子

令$Z_i(i=1,…,n)$为$n$个独立随机变量,因为

所以

最后我们证明一个结论:

对于随机信号$S$,即$S\in \{-1, +1\}$,且$\mathbb P (S=+1)=\mathbb P (S=-1)=\frac 12 $,那么对任意$\lambda \in \mathbb R$,

首先利用泰勒展开$e^x =\sum_{k=0}^{+\infty}\frac {x^{k}}{k!}$,以及$\mathbb E[S^{2k}] =1,\mathbb E[S^{2k+1}] =1,k\in \mathbb N$可得

注意到

所以

从而结论成立。

现在令$Z =\sum_{i=1}^n S_i$,$S_i$为随机噪声,那么$\mathbb E[Z] =0$,利用Chernoff界可得

由于上式对任意$\lambda \ge 0 $都成立,所以

由二次函数的性质可知,当$\lambda = \frac t n$时,右边取最小值,从而

Hoeffding引理以及Hoeffding不等式

定理 4 (Hoeffding不等式)

$Z_1,…,Z_n$为$n$个独立有界随机变量,且对任意$i$,我们有$Z_i \in [a,b]$,其中$-\infty<a \le b <\infty $,那么

该不等式可以由Chernoff界以及如下Hoeffding引理得到

引理 5 (Hoeffding引理)

令$Z$是一个有界随机变量且$Z\in [a,b]$,那么对任意$\lambda \in \mathbb R$

证明:这里老师证明了如下相对较弱的结论:

但其实没有关系,指数上的系数不影响大局。

首先引入与$Z$独立同分布的随机变量$Z’$,那么$\mathbb E[Z] = \mathbb E[Z’]$,从而

接下来应用Jeson不等式,对于下凸函数$f$,我们有

由于$\exp(\lambda x)$为下凸函数,所以

注意到$Z-Z’$关于$0$对称,我们引入随机信号$S$,即$S\in \{-1, +1\}$,且$\mathbb P (S=+1)=\mathbb P (S=-1)=\frac 12 $,所以$Z-Z’$与$S(Z-Z’)$同分布,从而

我们对$\mathbb E_{S} [\exp(\lambda S(Z-Z’))|Z,Z’ ]$应用随机信号的Chernoff界可得

注意到$Z,Z’\in [a,b]$,所以$|Z-Z’| \le |b-a|$,从而

引理5得证。

接下来利用引理5证明定理4。

证明:首先利用Chernoff界

最后一个不等号利用了引理5,重写上述不等式可得

最后一个等号是由于二次函数的性质,所以$\lambda = \frac{4nt}{n(b-a)^2}$时取最小值,此时