Page cover

📓1. 熵和互信息

1.1 信息的介绍

信息论由克劳德·香农（Claude E. Shannon，1916-2001）通过《通信的数学理论》（A Mathematical Theory of Communication），发表于1948年《贝尔系统技术期刊》创立。

什么是信息？一些观察如下：

  1. 信息源自不确定性。

  2. 信息应与可能性的数量相关。

  3. 信息应具有“可加性”。

  4. 我们可以使用对数来缩小大量的可能性。

  5. 二进制排列用于表示所有的可能性。

  6. 信息的度量应考虑各种可能事件的概率。

因此，信息是：接收者未知的知识，是对不确定性的度量。

定义：给定消息 M1,M2,...,MqM_1, M_2, . . . , M_q，其发生的概率为 P1,P2,...,Pq(P1+P2+...+Pq=1)P_1, P_2, . . . , P_q(P_1+P_2+...+P_q=1)，则每条消息所携带的信息量的度量为

I(Mi)=log⁡xPi−1,i=1,2,...,qI(M_i)=\log_xP_i^{-1},\quad i=1,2,...,q

  1. x=2,:I(Mi)x=2,:I(M_i)单位是bitbit(比特)

  2. x=e,:I(Mi)x=e,:I(M_i)单位是natsnats(奈特)

  3. x=10,:I(Mi)x=10,:I(M_i)单位是HartleyHartley(哈特莱)

信息量的性质：

  1. 当 Pi→1P_i \to 1 时，I(Mi)→0I(M_i) \to 0；

  2. 当 0≤Pi≤10 \leq P_i \leq 1 时，I(Mi)≥0I(M_i) \geq 0；

  3. 如果 Pj>PiP_j > P_i，则 I(Mi)>I(Mj)I(M_i) > I(M_j)；

  4. 若 MiM_i 和 MjM_j 统计独立，则 I(Mi&Mj)=I(Mi)+I(Mj)I(M_i\&M_j)=I(M_i)+I(M_j)

1.2 熵

给定长度为 NN 的源向量。它有 UU 个可能的符号 S1,S2,...,SUS_1, S_2,...,S_U，每个符号出现的概率分别为 P1,P2,...,PUP_1,P_2,...,P_U。要表示该源向量，我们需要

I=∑i=1UNPilog⁡2Pi−1 bitsI=\sum_{i=1}^UNP_i\log_2P_i^{-1}\mathrm{~bits}

平均而言，

H=IN=∑i=1UPilog⁡2Pi−1 bits/symbolH=\frac IN=\sum_{i=1}^UP_i\log_2P_i^{-1}\text{ bits/symbol}

HH 称为源熵，表示每个源符号的平均信息量。它也可以理解为函数 log⁡2Pi−1\log_2P_i^{-1} 的期望值：

H=E[log⁡2Pi−1]bits/symbolH=\mathbb{E}\left[\log_2P_i^{-1}\right]\text{bits/symbol}

不同底数的熵可以通过以下方式互换：

Hb(x)=Ha(x)log⁡baH_b(x)=H_a(x)\log_ba

证明如下：

Ha(x)=E[−log⁡aP(x)]Ha(x)log⁡ba=lg⁡alg⁡bE[−lg⁡P(x)lg⁡a]=E[−lg⁡P(x)lg⁡b]=E[−log⁡bP(x)]=Hb(x)\begin{align*} H_a(x)&=\mathbb{E}[-\log_aP(x)] \\ H_a(x)\log_ba &=\frac{\lg a}{\lg b}\mathbb{E}\left[-\frac{\lg P(x)}{\lg a}\right] \\ &=\mathbb{E}\left[-\frac{\lg P(x)}{\lg b}\right] \\ &=\mathbb{E}[-\log_bP(x)] \\ &=H_b(x) \end{align*}

现在我们考虑两个随机变量 XX 和 YY 的熵，XX 和 YY 的取值分别为 xx 和 yy。XX和 YY 的分布分别为 P(x)P(x) 和 P(y)P(y)。因此我们有：

联合熵 H(X,Y)H(X,Y)：给定联合分布P(x,y)P(x,y)

H(X,Y)=−∑x∈X∑y∈YP(x,y)log2P(x,y)=−E[log⁡2P(x,y)]H(X,Y)=-\sum_{x\in X}\sum_{y\in Y}P(x,y)\mathrm{log}_2P(x,y) \\ =-\mathbb{E}[\log_2P(x,y)] \\

条件熵 H(Y∣X)H(Y|X)：

H(Y∣X)=∑x∈XP(x)H(Y∣X=x)=−∑x∈X∑y∈YP(x)P(y∣x)log2P(y∣x)=−∑x∈X∑y∈YP(x,y)log2P(y∣x)=−E[log2P(y∣x)]\begin{align} H(Y|X)&=\sum_{x\in X}P(x)H(Y|X=x) \\ &=-\sum_{x\in X}\sum_{y\in Y}P(x)P(y|x)\mathrm{log}_2P(y|x) \\ &=-\sum_{x\in X}\sum_{y\in Y}P(x,y)\mathrm{log}_2P(y|x)=-\mathbb{E}[\mathrm{log}_2P(y|x)] \end{align}

链式法则（联合熵与条件熵的关系）：

H(X,Y)=H(X)+H(Y∣X)=H(Y)+H(X∣Y)\begin{aligned}H(X,Y)&=H(X)+H(Y|X)\\&=H(Y)+H(X|Y)\end{aligned}

证明如下：

H(X,Y)=−∑x∈X∑y∈YP(x,y)log2P(x,y)=−∑x∈X∑y∈YP(x,y)log2(P(y∣x)P(x))=−∑x∈X∑y∈YP(x,y)log2P(x)−∑x∈X∑y∈YP(x,y)log2P(y∣x)=−∑x∈XP(x)log⁡2P(x)−∑x∈X∑y∈YP(x,y)log2P(y∣x)=H(X)+H(Y∣X)\begin{aligned} H(X,Y)&=-\sum_{x\in X}\sum_{y\in Y}P(x,y)\mathrm{log}_2P(x,y)\\&=-\sum_{x\in X}\sum_{y\in Y}P(x,y)\mathrm{log}_2(P(y|x)P(x)) \\ &=-\sum_{x\in X}\sum_{y\in Y}P(x,y)\mathrm{log}_2P(x)-\sum_{x\in X}\sum_{y\in Y}P(x,y)\mathrm{log}_2P(y|x) \\ &=-\sum_{x\in X}P(x)\log_2P(x)-\sum_{x\in X}\sum_{y\in Y}P(x,y)\mathrm{log}_2P(y|x) \\ &=H(X)+H(Y|X) \end{aligned}

如果 XX 和 YY 独立：

H(X∣Y)=H(X)H(X|Y)=H(X)

因此

H(X,Y)=H(X)+H(Y)H(X,Y)=H(X)+H(Y)

该链式法则可以推广为：

(1) H(X,Y∣Z)=H(X∣Z)+H(Y∣X,Z)(2) H(X1,X2,...,XN)=∑i=1NH(Xi∣Xi−1,Xi−2,...,X1)\begin{aligned}&(1)~H(X,Y|Z)=H(X|Z)+H(Y|X,Z)\\&(2)~H(X_1,X_2,...,X_N)=\sum_{i=1}^NH(X_i|X_{i-1},X_{i-2},...,X_1)\end{aligned}

1.3 互信息

我们有两个随机变量 XX 和 YY，XX 和 YY 的取值分别为 xx 和 yy。XX 和 YY 的分布分别为 P(x)P(x) 和 P(y)P(y)。XX 和 YY 的联合分布为 P(x,y)P(x, y)。

互信息 I(X,Y)I(X,Y) 的定义为：

I(X,Y)=∑x∈X∑y∈YP(x,y)log2P(x∣y)P(x)=E[log⁡2P(x∣y)P(x)]\begin{aligned} I(X,Y)&=\sum_{x\in X}\sum_{y\in Y}P(x,y)\mathrm{log}_2\frac{P(x|y)}{P(x)}\\ &=\mathbb{E}\left[\log_2\frac{P(x|y)}{P(x)}\right] \end{aligned}

由以下关系可知：

P(x∣y)P(x)=P(x,y)P(x)P(y)\frac{P(x|y)}{P(x)}=\frac{P(x,y)}{P(x)P(y)}

因此：

I(X,Y)=∑x∈X∑y∈YP(x,y)log⁡2P(x,y)P(x)P(y)=E[log⁡2P(x,y)P(x)P(y)]I(X,Y)= \sum_{x\in X}\sum_{y\in Y}P(x,y)\log_2\frac{P(x,y)}{P(x)P(y)} =\mathbb{E}\left[\log_2\frac{P(x,y)}{P(x)P(y)}\right]

注意：如果 XX 和 YY 独立，P(x)P(y)=P(x,y)P(x)P(y)=P(x,y)，则 I(X,Y)=0I(X,Y)=0。

互信息与熵的关系：

I(X,Y)=H(X)+H(Y)−H(X,Y)I(X,Y)=H(X)+H(Y)-H(X,Y)

证明如下：

I(X,Y)=∑x∈X∑y∈YP(x,y)log2P(x,y)P(x)P(y)=∑x∈X∑y∈YP(x,y)log2P(x,y)−∑x∈XP(x)log2P(x)−∑y∈YP(y)log2P(y)=H(X)+H(Y)−H(X,Y)\begin{aligned} I(X,Y)& =\sum_{x\in X}\sum_{y\in Y}P(x,y)\mathrm{log}_2\frac{P(x,y)}{P(x)P(y)} \\ &=\sum_{x\in X}\sum_{y\in Y}P(x,y)\mathrm{log}_2P(x,y)-\sum_{x\in X}P(x)\mathrm{log}_2P(x)-\sum_{y\in Y}P(y)\mathrm{log}_2P(y) \\ &=H(X)+H(Y)-H(X,Y) \end{aligned}

该证明还表明了互信息的对称性：

I(X,Y)=I(Y,X)I(X,Y)=I(Y,X)

该关系也可以通过维恩图可视化表示。

推论：

I(X,Y)=H(X)−H(X∣Y)=H(Y)−H(Y∣X)\begin{aligned}I(X,Y)&=H(X)-H(X|Y)\\&=H(Y)-H(Y|X)\end{aligned}

结论如下：

  1. 0≤I(X,Y)≤min⁡H(X),H(Y)0\leq I(X,Y)\leq\min{H(X),H(Y)}；

  2. 如果 H(X)⊂H(Y)H(X)\subset H(Y)，则 I(X,Y)=H(X)I(X,Y)=H(X)。类似地，如果 H(Y)⊂H(X)H(Y)\subset H(X)，则 I(X,Y)=H(Y)I(X,Y)=H(Y)；

  3. I(X,X)=H(X)−H(X∣X)=H(X)I(X,X)=H(X)-H(X|X)=H(X)，熵也称为自信息。

对于互信息，任意多个变量的链式法则如下：

I(X1,X2,...,XN;Y)=H(X1,X2,...,XN)−H(X1,X2,...,XN∣Y)=∑i=1NH(Xi∣X1,X2,...,Xi−1)−∑i=1NH(Xi∣X1,X2,...,Xi−1,Y)=∑i=1NH(Xi∣X1,X2,...,Xi−1)−H(Xi∣X1,X2,...,Xi−1,Y)=∑i=1NI(Xi;Y∣X1,X2,...,Xi−1)\begin{aligned} I(X_1,X_2,...,X_N;Y)& =H(X_1,X_2,...,X_N)-H(X_1,X_2,...,X_N|Y) \\ &=\sum_{i=1}^NH(X_i|X_1,X_2,...,X_{i-1})-\sum_{i=1}^NH(X_i|X_1,X_2,...,X_{i-1},Y) \\ &=\sum_{i=1}^NH(X_i|X_1,X_2,...,X_{i-1})-H(X_i|X_1,X_2,...,X_{i-1},Y) \\ &=\sum_{i=1}^NI(X_i;Y|X_1,X_2,...,X_{i-1}) \end{aligned}

假设 XX 是传输信号，YY 是接收信号。

互信息 I(X,Y)I(X, Y) 描述了一个变量 XX 包含关于另一个变量 YY 的信息量，或反过来为 I(Y,X)I(Y, X)。

1.4 信息论的进一步结果

相对熵：假设 XX 和 X^\widehat{X} 是两个随机变量，取值分别为 xx 和 x^\widehat{x}。它们旨在描述同一事件，其概率质量函数分别为 P(x)P(x) 和 P(x^)P(\hat{x})。它们的相对熵定义为：

D(P(x),P(x^))=∑x∈supp⁡P(x)P(x)log2P(x)P(x^)=E[log⁡2P(x)P(x^)]\begin{aligned}D\big(P(x),P(\hat{x})\big)&=\sum_{x\in\operatorname{supp}P(x)}P(x)\mathrm{log}_2\frac{P(x)}{P(\hat{x})}\\&=\mathbb{E}\left[\log_2\frac{P(x)}{P(\hat{x})}\right]\\\end{aligned}

  • 相对熵通常称为两个分布 P(x)P(x) 和 P(x^)P(\widehat{x}) 之间的 Kullback-Leibler（KL 距离）。

    当假设分布为 P(x^)P(\hat{x}) 而真实分布为 P(x)P(x) 时，它是一种低效性的度量。例如，事件可以用平均长度为 H(P(x))H(P(x)) 位描述。然而，如果我们假设其分布为 P(x^)P(\widehat{x})，我们需要平均长度为 H(P(x))+D(P(x),P(x^))H( P( x) ) + D\left ( P( x) , P( \hat{x} ) \right ) 位来描述它。

    它不是对称的，即 D(P(x),P(x^))≠D(P(x^),P(x))D(P(x),P(\hat{x}))\neq D\left(P(\hat{x}),P(x)\right)。

推论 1：

When P(x)=P(x^),D(P(x),P(x^))=0.\text{When }P(x)=P(\hat{x}),D\Big(P(x),P(\hat{x})\Big)=0.

推论 2：

D(P(x),P(x^))≥0D\big(P(x),P(\hat{x})\big) \ge 0

证明如下：

−D(P(x),P(x^))=∑x∈supp⁡P(x)P(x)log⁡2P(x^)P(x)≤∑x∈supp⁡P(x)P(x)(P(x^)P(x)−1)log⁡2e=(∑x∈supp⁡P(x)P(x^)−∑x∈supp⁡P(x)P(x))log⁡2e≤(1−1)log2e=0\begin{aligned} -D\big(P(x),P(\hat{x})\big)& =\sum_{x\in\operatorname{supp}P(x)}P(x)\log_2\frac{P(\hat{x})}{P(x)} \\ &\leq\sum_{x\in\operatorname{supp}P(x)}P(x)\left(\frac{P(\hat{x})}{P(x)}-1\right)\log_2e \\ &=\left(\sum_{x\in\operatorname{supp}P(x)}P(\hat{x})-\sum_{x\in\operatorname{supp}P(x)}P(x)\right)\log_2e \\ &\leq(1-1)\mathrm{log}_2e \\ &=0 \end{aligned}

凸函数：若函数 f(x)f(x) 在区间 (a,b)(a,b) 上是凸的，即对于 x1,x2∈(a,b)x_{1},x_{2}\in(a,b) 且 0≤λ≤10\leq\lambda\leq1，有：

f(λx1+(1−λ)x2)≤λf(x1)+(1−λ)f(x2)f(\lambda x_{1}+(1-\lambda)x_{2})\leq\lambda f(x_{1})+(1-\lambda)f(x_{2})

当且仅当 λ=0\lambda=0 或 λ=1\lambda=1 时，等号成立，则该函数为严格凸函数。

如果 f(x)f(x) 是凸函数，则 −f(x)-f(x) 是凹函数。

詹森不等式：如果函数 f(x)f(x) 是凸的，则有：

f(E[x])≤E[f(x)]f(\mathbb{E}[x])\leq\mathbb{E}[f(x)]

詹森不等式可以用于证明一些关于熵的性质。

推论 2: D(P(x),P(x^))≥0D\big(P(x),P(\hat{x})\big) \ge 0

−D(P(x),P(x^))=∑x∈supp⁡P(x)P(x)log⁡2P(x^)P(x)≤log⁡2∑x∈supp⁡P(x)P(x^)≤log⁡21=0\begin{aligned}-D\big(P(x),P(\hat{x})\big)&=\sum_{x\in\operatorname{supp}P(x)}P(x)\log_2\frac{P(\hat{x})}{P(x)}\\&\leq\log_2\sum_{x\in\operatorname{supp}P(x)}P(\hat{x})\\&\leq\log_21=0\end{aligned}

推论 3: I(X,Y)≥0I( X, Y) \geq 0

I(X,Y)=∑x∈X∑y∈YP(x,y)log2P(x,y)P(x)P(y)=D(P(x,y),P(x)P(y))≥0\begin{aligned}I(X,Y)&=\sum_{x\in X}\sum_{y\in Y}P(x,y)\mathrm{log}_2\frac{P(x,y)}{P(x)P(y)}\\&=D(P(x,y),P(x)P(y))\geq0\end{aligned}

仅当 P(x,y)=P(x)P(y)P(x,y)=P(x)P(y) 时，I(X,Y)=0I(X,Y)=0，即 XX 和 YY 独立。

推论 4（最大熵分布）：

给定变量 X∈x1,x2,...,xUX\in{x_1,x_2,...,x_U}，其分布为 P1,P2,...,PUP_1,P_2,...,P_U。我们有：

H(X)≤log⁡2UH(X)\leq\log_2U

证明：

由于 log⁡2(⋅)\log_2(\cdot) 是一个凹函数，基于詹森不等式，我们有：

H(X)≤log⁡2(∑i=1UPiPi−1)=log⁡2U\begin{aligned}H(X)&\leq\log_2\left(\sum_{i=1}^UP_iP_i^{-1}\right)\\&=\log_2U\end{aligned}

注意：如果 XX 在 x1,x2,...,xUx_1, x_2, . . . , x_U 上均匀分布，即 P1=P2=⋯=PU=1UP_1= P_2= \cdots = P_U= \frac 1U，则有：

H(X)=log⁡2UH(X)=\log_2U

费诺不等式：设 XX 和 YY 是两个随机变量，其取值来自 x1,x2,...xk{x_1,x_2,...x_k}。设 Pe=Pr⁡[X≠Y]P_e=\Pr[X\neq Y]，则有：

H(X∣Y)≤H(Pe)+Pelog⁡2(k−1).H(X|Y)\leq H(P_e)+P_e\log_2(k-1).

证明：我们构造一个二元变量 ZZ得：

Z=0,if⁡X=YZ=1,if⁡X≠Y\begin{aligned} &Z=0,\operatorname{if}X=Y \\&Z=1,\operatorname{if}X\neq Y \end{aligned}

因此

Pr⁡(Z=0)=1−PePr⁡(Z=1)=Pe\begin{aligned}&\Pr(Z=0)=1-P_e\\&\Pr(Z=1)=P_e\end{aligned}

因此，H(Z)=H(Pe)H(Z)=H(P_e)。基于熵的链式法则：

H(XZ∣Y)=H(X∣Y)+H(Z∣XY)=H(X∣Y)H(XZ|Y)=H(X|Y)+H(Z|XY)=H(X|Y)

注意，已知 XX 和 YY 时，ZZ 是确定的，且 H(Z∣XY)=0H(Z|XY)=0。同样基于链式法则：

H(XZ∣Y)=H(Z∣Y)+H(X∣YZ)≤H(Z)+H(X∣YZ)\begin{align} H(XZ|Y)&=H(Z|Y)+H(X|YZ)\\ &\leq H(Z)+H(X|YZ) \end{align}

因此

H(X∣YZ)=Pr⁡(Z=0)H(X∣Y,Z=0)+Pr⁡(Z=1)H(X∣Y,Z=1).=(1−Pe)⋅0+Pelog⁡2(k−1)=Pelog⁡2(k−1)\begin{aligned} H(X|YZ)& =\Pr(Z=0) H(X|Y,Z=0)+\Pr(Z=1) H(X|Y,Z=1). \\ &=(1-P_e)\cdot0+P_e\log_2(k-1) \\ &=P_e\log_2(k-1) \end{aligned}

注意：H(Pe)H(P_e) 是在 X=YX=Y 时描述 XX 所需的比特数；log⁡2(k−1)\log_2(k-1) 是在 X≠YX\neq Y 时描述 XX 所需的比特数。当 XX 在所有 k−1k-1 个值上均匀分布时，等号成立。

信息处理不等式：给定一个串联的数据处理系统：

马尔可夫链 X→Y→ZX\to Y\to Z 表示在给定 YY 的情况下，XX 和 ZZ 条件独立，因此有以下关系：

P(z∣x,y)=P(z∣y)P(x∣y,z)=P(x∣y)P(z|x,y)=P(z|y)\\ P(x|y,z)=P(x|y)

因此我们有

P(x,y,z)=P(x,y)⋅P(z∣y)=P(x)P(y∣x)P(z∣y)P(x,y,z)=P(x,y)\cdot P(z|y)=P(x)P(y|x)P(z|y)

得

I(X,Z)≤{I(X,Y)I(Y,Z)I(X,Z)\leq\begin{cases}&I(X,Y)\\&I(Y,Z)\end{cases}

证明：

I(X,Z)=H(X)−H(X∣Z)≤H(X)−H(X∣ZY)=H(X)−H(X∣Y)=I(X,Y)\begin{aligned} I(X,{Z})& =H(X)-H(X|Z) \\ &\leq H(X)-H(X|ZY) \\ &=H(X)-H(X|Y) \\ &=I(X,Y) \end{aligned}

数据处理无法增加信息。

Previous信息论与编码Next2. 信道容量

Last updated