[关闭]
@qqiseeu 2015-06-26T12:18:33.000000Z 字数 4417 阅读 3783

Chernoff-Hoeffding Bound

Mathematics 读书笔记 ConcentrationInequality


引文

中心不等式(Concentration Inequality)是分析随机算法的经典工具,在机器学习算法的理论分析中也用的特别多。为了
学习这方面的知识,刚开始我选择的是Massart和Lugosi所著的Concentration Inequalities,无奈数学水平不够,看了一章就实在看不下去了。后来换了本简单一些的Concentration of Measure for the Analysis of Randomized Algorithms,总算是能往后翻了。这个系列的文章作为该书的读书笔记,希望能够督促自己坚持读完。

Concentration of meature可简单地理解为随机变量在其期望处“聚集”的行为。概率论中已经提供了两个经典工具————大数定律及中心极限定理————来刻画这种现象,然而它们所给出的结果存在几点不足:

Chernoff Bound

Chernoff bounding technique指的是用moment-generating function来处理多个随机变量之和的期望的技巧。所谓moment-generating function被定义为随机变量X的指数函数的期望E[eλX]

先来看一个简单的例子:考虑独立同分布的Bernoulli随机变量XiBernoulli(p)及它们的和X=i[n]Xi,易见XBinomial(n,p)。现在要估计X偏离其期望一定距离的概率,即Pr[X>n(p+t)]. 先考虑一个一般性的情况:估计Pr[X>m]. 由Markov不等式易得

Pr[X>m]=Pr[eλX>eλm]E[eλX]eλm(401)(402)

根据Xi的独立性,上述式子中的moment-generating function可写成

E[eλX]=E[eλiXi]=E[ieλXi]=iE[eλXi]=(peλ+q)n(403)(404)(405)(406)

其中q=1p.再令m=(p+t)n,原不等式变为

Pr[X>m](peλ+qeλ(p+t))n

将上述不等式右边视为λ的函数,找一个λ>0使右边最小,由此我们得到基本的Chernoff bound:

Pr[X>(p+t)n]((pp+t)p+t(qqt)qt)n=[exp((p+t)lnp+tp(qt)lnqtq)]n=exp(nDKL(p+t||p))(407)(408)(409)

其中DKL(||)KL-Divergence.上述bound说明,当实际分布(的参数)是(p,q)时,观测到经验分布(p+t,qt)的概率随着样本大小n的增加指数下降,且下降速率与实际分布及经验分布的KL-Divergence密切相关。

Chernoff-Hoeffding bound

之前Chernoff bound的推导是在Xi为独立同分布的Bernoulli随机变量的假定下进行的,现在我们把上述bound推广到Xi任意[0,1]间的独立随机变量的情况。首先考虑Xi是独立但同分布的Bernoulli随机变量的情况。此时X的moment-generating function变为

E[eλX]=i(pieλ+qi)

根据Arithmetic-Geometric Mean Inequality易得

E[eλX]=i(pieλ+qi)(i(pieλ+qi)n)n=(peλ+q)n(410)(411)(412)

其中p=ipi/n,q=1p. 易见此时bound又变回了之前独立同分布时的形式,因此上一节得到的bound依然成立。

接下来考虑Xi[0,1]上任意(既可以是离散也可以是连续的)独立随机变量的情况,使用的技巧是由Hoeffding提出的,因此最后得到的bound也叫Chernoff-Hoeffding bound。这里要利用函数eλx的凸性:在区间[0,1]上,eλx的图像总在连接点(0,1)(1,eλ)的直线之下。该直线的方程为y=(eλ1)x+1,因此有

E[eλXi]E[(eλ1)Xi+1]=pieλ+qi

故有

E[eλX]iE[eλXi]i(pieλ+qi)

这与前述Xi是独立非同分布Bernoulli随机变量的情况一致,因此上一节得到的bound依然成立。

Variance bound

之前得到的bound都只利用了一阶矩(期望)的信息,作为Chernoff bounding technique的一个简单应用,我们考虑引入二阶矩(方差)的信息。这里的关键技巧是利用不等式ex1+x+x2,(0<|x|<1)为moment-generating function构造上界,从而引入二阶矩(x2)。设μi=E[Xi],μ=E[X],易知

Pr[X>μ+t]=Pr[i(Xiμi)>t]=Pr[eλi(Xiμi)>eλt]E[eλi(Xiμi)]/eλt(413)(414)(415)

利用之前提到的不等式及ex1+x,并假设i[n],max(μi,1μi)<1/λ,有

E[eλi(Xiμi)]=iE[eλ(Xiμi)]iE[1+λ(Xiμi)+λ2(Xiμi)2]=i(1+λ2σ2i)ieλ2σ2i=eλ2σ2(416)(417)(418)(419)(420)

其中σ2i,σ2分别是Xi,X的方差。综上,有

Pr[X>μ+t]eλ2σ2/eλt

针对λ<max(μi,1μi)最小化该上界,易知当λ=t/2σ2时有

Pr[X>μ+t]exp(t24σ2)

其中t<2σ2/(maxi max(μi,1μi))

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注