信息论基础——熵

信息论基础——熵

一 、Jensen不等式
定理1 设ff 为区间II 上的凹函数，pi∈[0,1],i=1,2,⋯ ,np_{i} \in[0,1], i=1,2,\cdots,n,且∑i=1npi=1\sum_{i=1}^{n} p_{i}=1，则对任何xi∈Ix_{i} \in I，有f(∑i=1npixi)⩾∑i=1npif(xi)f\left(\sum_{i=1}^{n} p_{i} x_{i}\right) \geqslant \sum_{i=1}^{n} p_{i} f\left(x_{i}\right)

若 ff 严格凹，上式的等号只有在下列条件满足时才成立：若pi⋅pj≠0p_{i} \cdot p_{j} \neq 0，则必有xi=xjx_{i}=x_{j}
证明：略
对于对数函数f(x)=log⁡xf(x)=\log x在区间(0,+∞)(0,+\infty)是凹函数，有log⁡(∑i=1npixi)⩾∑i=1npilog⁡xi\log \left(\sum_{i=1}^{n} p_{i} x_{i}\right) \geqslant \sum_{i=1}^{n} p_{i} \log x_{i}，∀i,xi>0,pi⩾0\forall i, x_{i}>0, p_{i} \geqslant 0，且∑i=1npi=1\sum_{i=1}^{n} p_{i}=1。

二、熵
一个离散随机变量XX的熵H(X)H(X)的定义为H(X)=∑XP(X)log⁡1P(X)=−∑XP(X)log⁡P(X) H(X)=\sum_{X} P(X) \log \frac{1}{P(X)}=-\sum_{X} P(X) \log P(X) log⁡P(X)\log P(X)以为22底，熵的单位是比特，以ee为底，熵的单位是奈特
熵是对随机变量的不确定性的度量。随机变量XX的熵越大，说明它的不确定性越大。
熵的基本性质
(1)(1) H(X)⩾0H(X) \geqslant 0
(2)(2) H(X)⩽log⁡∣X∣H(X) \leqslant \log |X|,等号成立当且仅当对XX的所有取值xx有P(X=x)=1∣X∣P(X=x)=\frac{1}{|X|}

证明：(1)(1) 对XX的任意取值xx，总有−P(X=x)log⁡P(X=x)⩾0-P(X=x) \log P(X=x) \geqslant 0
(2)(2) H(X)=∑xP(X)log⁡1P(X)⩽log⁡∑XP(X)1P(X)=log⁡∣X∣命题得证，此性质经常被称为最大熵原理

三、联合熵、条件熵和互信息
联合熵 ：两个离散随机变量XX和YY的联合熵的定义为
H(X,Y)=∑X,YP(X,Y)log⁡1P(X,Y)=−∑X,YP(X,Y)log⁡P(X,Y)H(X, Y)=\sum_{X, Y} P(X, Y) \log \frac{1}{P(X, Y)}=-\sum_{X, Y} P(X, Y) \log P(X, Y)
条件熵 ：给定Y=xY=x时XX的条件熵为
H(X∣Y=y)=∑XP(X∣Y=y)log⁡1P(X∣Y=y)H(X | Y=y)=\sum_{X} P(X | Y=y) \log \frac{1}{P(X | Y=y)}
条件熵H(X∣Y=y)H(X | Y=y)度量的是已Y=yY=y知后，XX的不确定性
由于知道YY的概率分布，因此可以计算观测YY后XX的熵的期望值，即
H(X∣Y)=∑y∈ΩYP(Y=y)H(X∣Y=y)=∑y∈ΩYP(Y=y)∑XP(X∣Y=y)log⁡1P(X∣Y=y)=∑Y∑XP(Y)P(X∣Y)log⁡1P(X∣Y)=∑X,YP(X,Y)log⁡1P(X∣Y)H(X∣Y)H(X | Y)称为给定YY时XX的条件熵
注意：H(X∣Y)H(X | Y)与H(X∣Y=y)H(X | Y=y)有所不同，后者是在已知YY取某一特定值yy时XX的条件熵，是在已知Y=yY=y后，XX剩余的不确定性。而H(X∣Y)H(X | Y)则是在未知YY的取值时，对观测到YY的取值后XX剩余的不确定性的一个期望。
例 : 设联合分布P(X,Y)P(X,Y)及边缘分布P(X)P(X)和P(Y)P(Y)如下：

从而得H(X)=−18log⁡18−78log⁡78=0.544H(X∣Y=y1)=−0log⁡0−1log⁡1=0H(X∣Y=y2)=−12log⁡12−12log⁡12=1H(X∣Y)=34H(X∣Y=y1)+14H(X∣Y=y2)=0.25
在观测到YY前，XX 的不确定性是H(X)H(X)，通过观测YY，我们的期望XX的不确定性会变为H(X∣Y)H(X|Y),因此H(X)H(X)与H(X∣Y)H(X|Y)之差I(X;Y)=H(X)−H(X∣Y)I(X ; Y)=H(X)-H(X | Y)就是对YY包含多少关于XX的信息的一个度量，称之为YY关于XX的信息，下面可以看到I(X;Y)=I(Y;X)I(X ; Y)=I(Y ; X)，因此它又称为和之间的互信息
定理2 对任意两个离散随机变量XX和YY，有I(X;Y)=∑X,YP(X,Y)log⁡P(X,Y)P(X)P(Y)(a)I(X;Y)=I(Y;X)(b)H(X,Y)=H(X)+H(Y∣X)=H(Y)+H(X∣Y)(c)I(X;Y)+H(X,Y)=H(X)+H(Y)(e) 其中式(c)(c)称为熵的链规则
证明：(1)(1)对式(a)(a) ，I(X;Y)=H(X)−H(X∣Y)=∑XP(X)log⁡1P(X)−∑X,YP(X,Y)log⁡1P(X∣Y)=∑X,YP(X,Y)log⁡1P(X)−∑X,YP(X,Y)log⁡1P(X∣Y)=∑X,YP(X,Y)log⁡P(X∣Y)P(X)=∑X,YP(X,Y)log⁡P(X,Y)P(X)P(Y) (2)(2) 对式(b)(b),由式(a)(a)的推导知显然成立
(3)(3) 对式(c)(c),H(X,Y)=−∑X,YP(X,Y)log⁡P(X,Y)=−∑XYXYP(X,Y)log⁡P(X)−∑XYP(X,Y)log⁡P(Y∣X)=−∑XP(X)log⁡P(X)−∑XYP(X,Y)log⁡P(Y∣X)=H(X)+H(Y∣X) 同理可证H(X,Y)=H(Y)+H(X∣Y)H(X, Y)=H(Y)+H(X | Y)
(4)(4)对式(d)(d)，有I(X;Y)+H(X,Y)=(H(X)−H(X∣Y))+(H(Y)+H(X∣Y))=H(X)+H(Y)
定理得证. 下图为联合熵、条件熵以及互信息之间的关系

四、相对熵
对定义于随机变量XX的状态空间ΩX\Omega_{X}上的两个概率分布P(X)P(X)和Q(X)Q(X)，可以用相对熵来度量它们之间的差异，即有KL(P,Q)=∑xP(X)log⁡P(X)Q(X)K L(P, Q)=\sum_{x} P(X) \log \frac{P(X)}{Q(X)}其中约定：log⁡0q=0;plog⁡p0=∞\log \frac{0}{q}=0 ; \quad p \log \frac{p}{0}=\infty
∀p>0.KL(P,Q)\forall p>0 . K L(P, Q)又被称为P(X)P(X)和Q(X)Q(X)之间的Kullback-Leibler \text { Kullback-Leibler }距离，但它不是一个真正意义上的距离，因为KL(P,Q)≠KL(Q,P)K L(P, Q) \neq K L(Q, P)
定理3 (信息不等式)
设P(X)P(X)和Q(X)Q(X)为定义在某个变量XX的状态空间ΩX\Omega_{X}的两个概率分布，则有KL(P,Q)⩾0K L(P, Q) \geqslant 0其中，当且仅当PP与QQ相同，即P(X=x)=Q(X=x),∀x∈ΩXP(X=x)=Q(X=x), \forall x \in \Omega X时等号成立
证明
∑XP(X)log⁡P(X)Q(X)=−∑XP(X)log⁡Q(X)P(X)⩾−log⁡∑XP(X)Q(X)P(X)(Jensen不等式)=−log⁡∑XQ(X)=−log⁡1=0\sum{X} P(X) \log \frac{P(X)}{Q(X)}=-\sum_{X} P(X) \log \frac{Q(X)}{P(X)}\ \geqslant-\log \sum_{{X}} P(X) \frac{Q(X)}{P(X)}(Jensen不等式)\ {=-\log \sum_{X} Q(X)} {=-\log 1=0} 定理得证
推论 对于满足∑Xf(X)>0\sum_{X} f(X)>0的非负函数f(X)f(X)，定义概率分布P∗(X)P^{}(X)为
P∗(X)=f(X)∑Xf(X)P^{}(X)=\frac{f(X)}{\sum_{X} f(X)} 那么对于任意其它的概率分布P(X)P(X)，则有∑Xf(X)log⁡P∗(X)⩾∑Xf(X)log⁡P(X)\sum_{X} f(X) \log P^{}(X) \geqslant \sum_{X} f(X) \log P(X)其中当且仅当P∗P^与PP相同时等号成立
证明 : 根据上述定理有KL(P∗,P)=∑XP∗(X)log⁡P∗(X)P(X)⩾0K L\left(P^{}, P\right)=\sum_{X} P^{}(X) \log \frac{P^{}(X)}{P(X)} \geqslant 0因此有∑XP∗(X)log⁡P∗(X)⩾∑XP∗(X)log⁡P(X)\sum_{X} P^{}(X) \log P^{}(X) \geqslant \sum_{X} P^{}(X) \log P(X)即∑Xf(X)∑Xf(X)log⁡P∗(X)⩾∑Xf(X)∑Xf(X)log⁡P(X)\sum_{X} \frac{f(X)}{\sum_{X} f(X)} \log P^{}(X) \geqslant \sum_{X} \frac{f(X)}{\sum_{X} f(X)} \log P(X)从而有∑Xf(X)log⁡P∗(X)⩾∑Xf(X)log⁡P(X)\sum_{X} f(X) \log P^{}(X) \geqslant \sum_{X} f(X) \log P(X)推论得证

五、互信息与变量独立
定理4 对任意两个离散随机变量XX和YY，有
(1)(1) I(X;Y)⩾0I(X ; Y) \geqslant 0
(2)(2) H(X∣Y)⩽H(X)H(X | Y) \leqslant H(X)
上面两式当且仅当XX和YY相互独立时等号成立。
证明:由定理2中式 I(X;Y)=∑X,YP(X,Y)log⁡P(X,Y)P(X)P(Y)I(X ; Y)=\sum_{X, Y} P(X, Y) \log \frac{P(X, Y)}{P(X) P(Y)}可得I(X;Y)=KL(P(X,Y),P(X)P(Y))I(X ; Y)=K L(P(X, Y), P(X) P(Y))即I(X;Y)I(X ; Y)是分布于P(X,Y)P(X, Y)和P(X)P(Y)P(X) P(Y)之间的相对熵,根据信息不等式，I(X;Y)⩾0I(X ; Y) \geqslant 0当且仅当
P(X,Y)=P(X)P(Y)P(X, Y)=P(X) P(Y)时等号成立。亦即I(X;Y)=0I(X ; Y)=0，当且仅当XX和YY相互独立。由于I(X;Y)=H(X)−H(X∣Y)I(X ; Y)=H(X)-H(X | Y)，所以H(X∣Y)⩽H(X)H(X | Y) \leqslant H(X),且H(X∣Y)=H(X)H(X | Y)=H(X)且仅当XX和YY相互独立，定理得证。
定理4 从信息论角度为边缘独立这一概念提供了一个直观解释，即两个随机变量相互独立当且仅当它们之间的互信息为零。
条件熵H(X∣Z)H(X|Z)表示给定ZZ时XX剩余的不确定性
再进一步给定YY，H(X∣Z,Y)H(X | Z, Y)为XX剩余的不确定性
两者之差为给定ZZ时观测YY取值会带来的关于XX的信息量，即I(X;Y∣Z)=H(X∣Z)−H(X∣Z,Y)I(X ; Y | Z)=H(X | Z)-H(X | Z, Y)称为给定ZZ时YY关于XX的信息。易证I(X;Y∣Z)=I(Y;X∣Z)I(X ; Y | Z)=I(Y ; X | Z)，因此I(X;Y∣Z)I(X ; Y | Z)也称为给定ZZ时XX和YY的条件互信息

定理5 对任意3个离散随机变量X,YX,Y和ZZ，有
(1)(1) I(X;Y∣Z)⩾0I(X ; Y | Z) \geqslant 0
(2)(2) H(X∣Y,Z)⩽H(X∣Z)H(X | Y, Z) \leqslant H(X | Z)
上式两式当且仅当X⊥Y∣ZX \perp Y|Z时等号成立
证明：I(X;Y∣Z)=H(X∣Z)−H(X∣Y,Z)=∑X,ZP(X,Z)log⁡1P(X∣Z)−∑X,Y,ZP(X,Y,Z)log⁡1P(X∣Y,Z)=∑X,Y,ZP(X,Y,Z)log⁡1P(X∣Z)−∑X,Y,ZP(X,Y,Z)log⁡1P(X∣Y,Z)=∑X,Y,ZP(X,Y,Z)log⁡P(X∣Y,Z)P(X∣Z)=∑ZP(Z)∑X,YP(X,Y∣Z)log⁡P(X,Y∣Z)P(X∣Z)P(Y∣Z)=∑ZP(Z)KL(P(X,Y∣Z),P(X∣Z)P(Y∣Z))⩾0 当且仅当(P(X,Y∣Z)=P(X∣Z)P(Y∣Z)(P(X, Y | Z)=P(X | Z) P(Y | Z),即X⊥Y∣ZX \perp Y|Z时等号成立
直观解释给定ZZ，两个随机变量XX和YY相互条件独立，当且仅当它们的条件互信息为零。