1. 简介
在概率论中,霍夫丁不等式(Hoeffding’s Inequality)给出了有界独立随机变量之和偏离其均值超过一定数量的概率上界。霍夫不等式是切比雪夫界的推广,同时又是吾妻不等式和McDiarmid不等式(还没给出标准的中文翻译2333)。霍夫丁不等式是机器学习的基础理论。
2. 定义
假设 X1,X2,⋯,XN 是独立随机变量,且 Xi∈[ai,bi],i=1,2,⋯,N;Xˉ 是 X1,X2,⋯,XN 的经验均值,即 Xˉ=N1∑i=1NXi,则对任意 t>0,以下霍夫丁不等式成立:
P[Xˉ−E(Xˉ)≥t]≤exp(−∑i=1N(bi−ai)22N2t2)P[E(Xˉ)−Xˉ≥t]≤exp(−∑i=1N(bi−ai)22N2t2)
证明
由霍夫丁引理可得
E(es(X−E(X)))≤exp(81s2(bi−ai)2)(1≤i≤n)
令 Sn=X1+X2+⋯+Xn,对于 ∀s,t>0,可得
P(Sn−E(Sn)≥t)=P(es(Sn−E(Sn))≥est)
进一步根据马尔可夫不等式和 Xi 之间的独立性可得
P(es(Sn−E(Sn))≥est)≤e−stE(es(Sn−E(Sn)))=e−st∏i=1nE(es(Xi−E(Xi)))≤e−st∏i=1ne8s2(bi−ai)2=exp(−st+81s2∑i=1n(bi−ai)2)
令 g(s)=−st+8s2∑i=1n(bi−ai)2,则 g(s) 为关于 s 的二次函数,从而易得
s=∑i=1n(bi−ai)24t
为 g(s) 的最小值点。由于
P(es(Sn−E(Sn))≥est)≤exp(−st+81s2∑i=1n(bi−ai)2)
对 ∀s>0 都成立,因此当 s 取 g(s) 的最小值点时,得到 P(es(Sn−E(Sn))≥est) 的紧上界,即
P(es(Sn−E(Sn))≥est)≤exp(−∑i=1n(bi−ai)22t2)
最终简单变换后可得 P[Xˉ−E(Xˉ)≥t]≤exp(−∑i=1N(bi−ai)22N2t2)。另一个不等式 P[E(Xˉ)−Xˉ≥t]≤exp(−∑i=1N(bi−ai)22N2t2) 同理可证。
附录
参考资料: