9

漫谈概率论与信息论中的不等式

 2 years ago
source link: https://allenwind.github.io/blog/6631/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

本文证明常用的概率或信息论相关的不等式，会持续更新~

k-σσ Rule

对于随机变量XX，如果满足正态分布N(μ,σ2)N(μ,σ2)，那么有

Pr(μ−1σ≤X≤μ+1σ)≈68.27%Pr(μ−2σ≤X≤μ+2σ)≈95.45%Pr(μ−3σ≤X≤μ+3σ)≈99.73%Pr(μ−1σ≤X≤μ+1σ)≈68.27%Pr(μ−2σ≤X≤μ+2σ)≈95.45%Pr(μ−3σ≤X≤μ+3σ)≈99.73%

它的证明使用累积分布函数即可，如对于2σ2σ区间来说，

Pr(μ−2σ≤X≤μ+2σ)=Pr(−2≤X−μσ≤2)=Φ(2)−Φ(−2)≈0.9772−(1−0.9772)≈95.45%Pr(μ−2σ≤X≤μ+2σ)=Pr(−2≤X−μσ≤2)=Φ(2)−Φ(−2)≈0.9772−(1−0.9772)≈95.45% Φ(x)=1√2π∫x−∞e−t2/2dtΦ(x)=12π∫−∞xe−t2/2dt

这个不等式可以用于异常处理，例如数据服从正态分布，或者通过一定的处理后服从正态分布，那么数据的取值落到区间[μ−3σ,μ+3σ][μ−3σ,μ+3σ]外的概率为1−99.73%1−99.73%，是极小概率，可以认为是异常值。

马尔可夫不等式

假设非负随机变量XX有概率密度函数 f(x)f(x)定义在ΩΩ上，根据连续概率分布的均值定义，有，

E[x]=∫Ωxf(x)dx=∫Uxf(x)dx+∫Ω−Uxf(x)dx≥∫Uxf(x)dx≥∫Uαf(x)dx=αP(x≥α)E[x]=∫Ωxf(x)dx=∫Uxf(x)dx+∫Ω−Uxf(x)dx≥∫Uxf(x)dx≥∫Uαf(x)dx=αP(x≥α)

这里U=[α,∞),Ω=[0,α)U=[α,∞),Ω=[0,α)有特例。

P(X⩾a)⩽E[X]aP(X⩾a)⩽E[X]a

这是一个很强的定理，不需要假设 f(x)f(x) 是具体的分布的概率密度函数。取E[X]=μ,α=5μE[X]=μ,α=5μ，有

P(X≥5μ)≤15P(X≥5μ)≤15

换成一个具体的语境来说是，不超过五分之一的人数收入超过平均水平的五倍。

不过马尔可夫不等式要求随机变量非负，这对于很多概率分布来说并不满足，如正态分布。那怎么办呢？一种技巧就是引入绝对值，这是一会提到的切比雪夫不等式的处理技巧，另外一种技巧是引入指数变换，因为指数变换总是非负的。以上要求x≥α>0x≥α>0，那么任给λ>0λ>0​有，

eλx≥eλα>0eλx≥eλα>0

代入到马尔可夫不等式中，有

P(x⩾a)=P(eλx⩾eλa)≤e−λaE[eλx]=minλe−λaE[eλx]P(x⩾a)=P(eλx⩾eλa)≤e−λaE[eλx]=minλe−λaE[eλx]

最后一部分是因为理论上只要λ>0λ>0即可，因此为了获得更高的近似估计精度，不等式右端应该取最小值。

马尔可夫不等式可以用来推导切比雪夫不等式。

切比雪夫不等式

对于随机变量XX，有均值和方差分别为μ,σ2μ,σ2，切比雪夫不等式为，

P(|X−μ|≥kσ)≤1k2P⁡(|X−μ|≥kσ)≤1k2

另外一种相似的形式，

P(|X−μ|≥ξ)≤σ2ξ2P(|X−μ|≥ξ)≤σ2ξ2 P(|X−μ|≥kσ)=E(I|X−μ|≥kσ)=E(I(x−μkσ)2≥1)≤E((X−μkσ)2)=1k2E((X−μ)2)σ2=1k2P⁡(|X−μ|≥kσ)=E(I|X−μ|≥kσ)=E(I(x−μkσ)2≥1)≤E((X−μkσ)2)=1k2E((X−μ)2)σ2=1k2

这里II值指示函数。

如果只考虑单边情况，有更一般化的形式，称为Cantelli’s inequality，

P(X−E[X]≥λ)=⎧⎪⎨⎪⎩≤σ2σ2+λ2if λ>0,≥1−σ2σ2+λ2if λ<0.P(X−E[X]≥λ)={≤σ2σ2+λ2if λ>0,≥1−σ2σ2+λ2if λ<0.

Gibbs 不等式

Gibbs 不等式，

DKL(q(z)|p(z|x))≥0DKL(q(z)|p(z|x))≥0

容易证明，

DKL(q(z)|p(z|x))=∑z∈Zq(z)logq(z)p(z|x)=−∑z∈Zq(z)logp(z|x)q(z)⩾log∑z∈Zq(z)p(z|x)q(z)=log∑z∈Zp(z|x)=0DKL(q(z)|p(z|x))=∑z∈Zq(z)log⁡q(z)p(z|x)=−∑z∈Zq(z)log⁡p(z|x)q(z)⩾log⁡∑z∈Zq(z)p(z|x)q(z)=log⁡∑z∈Zp(z|x)=0

这不就是 KL 散度大于等于 0 的证明！

Jensen 不等式

凸函数有一个直观的几何性质，即凸函数两点间的割线在该区间函数上方，可以用数学表示，

tf(x1)+(1−t)f(x2)≥f(tx1+(1−t)x2),0≤t≤1tf(x1)+(1−t)f(x2)≥f(tx1+(1−t)x2),0≤t≤1

这是实函数版本。其概率论版本如下，

φ(E(X))≤E(φ(X))φ(E(X))≤E(φ(X))

基于 Jensen 不等式还能导出很多有趣的不等式。EM算法的推导也涉及 Jensen 不等式。

Hoeffding 不等式

Hoeffding 不等式可以参考资料Hoeffding’s inequality。

P(H(x)≠f(x))=[T/2]∑i=0(Tk)(1−ε)kεT−k⩽exp(−12T(1−2ε)2)P(H(x)≠f(x))=∑i=0[T/2](Tk)(1−ε)kεT−k⩽exp⁡(−12T(1−2ε)2)

负熵不等式

负熵不等式，

H(λp1+(1−λ)p2)≥λH(p1)+(1−λ)H(p2)H(λp1+(1−λ)p2)≥λH(p1)+(1−λ)H(p2)

考虑到熵H(x)H(x)​的凹性，使用 Jensen 不等式容易证得。

有 Weak law，

limn→∞P(∣∣¯¯¯¯¯Xn−μ∣∣>ε)=0limn→∞P⁡(|X¯n−μ|>ε)=0

使用切比雪夫不等式易得，

Sn=X1+⋯+XnSn=X1+⋯+XnP(∣∣∣Snn−μ∣∣∣⩾r)⩽Var[Sn/n]ε2P(|Snn−μ|⩾r)⩽Var[Sn/n]ε2

另外，Strong law 如下，

P(limn→∞¯¯¯¯¯Xn=μ)=1P⁡(limn→∞X¯n=μ)=1

数据处理不等式

设有马尔可夫链，

p(x,y,z)=p(x)p(y|x)p(z|y)p(x,y,z)=p(x)p(y|x)p(z|y)

根据信息论，

I(X;Y)⩾I(X;Z)I(X;Y)⩾I(X;Z)

该不等式称为数据处理不等式。

在理论上说明，机器学习或深度学习任务中，data pipeline对信息的损失只增不减，这启发我们不要对数据过度处理。这正好印证匈牙利数学家科尼利厄斯·兰佐斯的一句话：任何数学技巧都不能弥补信息的缺失。

[1] https://en.wikipedia.org/wiki/Fano%27s_inequality

[2] https://en.wikipedia.org/wiki/Chernoff_bound

[3] Hoeffding’s inequality

[4]《信息论基础》

[5] https://en.wikipedia.org/wiki/Jensen%27s_inequality

转载请包括本文地址：https://allenwind.github.io/blog/6631
更多文章请参考：https://allenwind.github.io/blog/archives/


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK