熵的内容总结

参考资料：https://www.fi.muni.cz/~xbouda1/teaching/current/IV111/prednasky/lecture5.pdf

在学习信息论过程中发现熵的内容少了一点，找到一个不错的课件加以补充，这里进行总结。

备注：后续讨论都在离散情形下进行。

不确定性和熵

熵的直觉

给定概率分布$\left\{p_{1}, p_{2}, \ldots, p_{n}\right\}$，现在要定义一个衡量不确定性的度量，记为$H\left(p_{1}, p_{2}, \ldots, p_{n}\right)$，我们希望该函数满足如下条件：

均匀分布给出最大的不确定性，即当$p_{1}=\cdots=p_{n}=1 / n$时，$H\left(p_{1}, \ldots p_{n}\right)$取最大值
不确定性和概率的顺序无关，即对于任意置换$\pi:\{1 \ldots n\} \rightarrow\{1 \ldots n\}$，我们有$H\left(p_{1}, p_{2}, \ldots, p_{n}\right)=H\left(p_{\pi(1)}, p_{\pi(2)} \ldots, p_{\pi(n)}\right)$
不确定性非负：$H\left(p_{1}, p_{2}, \ldots, p_{n}\right) \geq 0$，当且仅当存在某个$p_i=1$时取等号
如果增加一个概率为$0$的结果，那么不改变不确定性，$H\left(p_{1}, \ldots, p_{n}, 0\right)=H\left(p_{1}, \ldots, p_{n}\right)$
最大值的单调性：
$H(\overbrace{1 / n, \ldots, 1 / n}^{n \times}) \leq H(\overbrace{1 /(n+1), \ldots, 1 /(n+1)}^{(n+1) \times}$
连续性：$H(p_1,\ldots,p_n)$关于$p_i$连续
独立性：
$H(\overbrace{1 /(m n), \ldots, 1 /(m n)}^{m n \times})=H(\overbrace{1 / m, \ldots, 1 / m}^{m \times})+H(\overbrace{(1 / n, \ldots, 1 / n)}^{n \times}$
分解性：记$p=\sum_{i=1}^{m} p_{i},q=\sum_{i=m+1}^{m+n} p_{i}$，那么
$\begin{aligned} & H\left(p_{1}, \ldots, p_{m}, p_{m+1}, \ldots, p_{m+n}\right)=\\ =& H(p, q)+p H\left(\frac{p_{1}}{p}, \ldots, \frac{p_{m}}{p}\right)+q H\left(\frac{p_{m+1}}{q}, \ldots, \frac{p_{m+n}}{q}\right) \end{aligned}$

可以证明，满足上述条件的$H$形式如下：

$H\left(p_{1}, \ldots, p_{m}\right)=-\left(\log _{a} 2\right) \sum_{i=1}^{m} p_{i} \log _{2} p_{i}$

为了比例系数，我们通常取$a=2$，于是得到如下定义。

熵的定义

对于概率分布为$p(x)$的随机变量$X$，其香农熵定义为：

$H(X)=-\sum_{x \in \operatorname{Im}(X)} p(X=x) \log P(X=x)$

注：不加说明的情况下，没有下标表示底数为$2$。

不难发现

$H(X)=E\left[\log \frac{1}{p(X)}\right]\ge 0$

联合和条件熵

联合熵

给定联合概率分布$p(x,y)$，联合熵定义为

$H(X, Y)=-\sum_{X \in \operatorname{Im}(X)} \sum_{y \in \operatorname{Im}(Y)} p(x, y) \log p(x, y)$

同样可以将其改写为期望的形式：

$H(X, Y)=-E[\log p(X, Y)]=E\left[\frac{1}{\log p(X, Y)}\right]$

条件熵

定义

$H(X | Y=y)=-\sum_{X \in \operatorname{Im}(X)} P(X=x | Y=y) \log P(X=x | Y=y)$

条件熵定义为

$\begin{aligned} H(X | Y) &=\sum_{y \in \operatorname{lm}(Y)} p(y) H(X | Y=y)\\ &=-\sum_{y \in \operatorname{lm}(Y)} p(y) \sum_{x \in \operatorname{Im}(X)} p(x | y) \log p(x | y)\\ &=-\sum_{X \in \operatorname{Im}(X)} \sum_{y \in \operatorname{lm}(Y)} p(x, y) \log p(x | y) \\ &=E\left[\frac 1 {\log p(X | Y)} \right] \end{aligned}$

链式法则

利用条件概率恒等式：

$p(X,Y)=p(Y)p(X|Y)$

我们有

$\log \frac 1 {p(X, Y)}=\log\frac 1{ p(Y)}+\log \frac 1{p(X | Y)}$

所以

$\begin{aligned} H(X,Y) &=E\left[\frac 1 {\log p(X , Y)} \right]\\ &=E\left[\frac 1 {\log p( Y)} \right]+ E\left[\frac 1 {\log p(X | Y)} \right]\\ &=H(Y)+H(X|Y) \end{aligned}$

由对称性可得

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

推论：

$H(X, Y | Z)=H(Y | Z)+H(X | Y, Z)$

相对熵和互信息

相对熵（DL散度）

概率分布$p(x),q(x)$的相对熵（DL散度）定义为

$D(p \| q)=\sum_{x \in \operatorname{lm}(X)} p(x) \log \frac{p(x)}{q(x)}=E\left[\log \frac{p(X)}{q(X)}\right]$

互信息

互信息$I(X;Y)$定义为

$\begin{aligned} I(X ; Y) &=\sum_{X \in \operatorname{Im}(X)} \sum_{y \in \operatorname{Im}(Y)} p(x, y) \log \frac{p(x, y)}{p(x) p(y)} \\ &=D(p(x, y) \| p(x) p(y))\\ &=E\left[\log \frac{p(X, Y)}{p(X) p(Y)}\right] \end{aligned}$

互信息满足如下性质：

$I(X ; Y)=H(X)-H(X | Y)=H(Y)-H(Y|X) =H(X)+H(Y)-H(X, Y)$

证明：

$\begin{aligned} I(X ; Y) &=\sum_{x, y} p(x, y) \log \frac{p(x, y)}{p(x) p(y)}\\ &=\sum_{x, y} p(x, y) \log \frac{p(x | y)}{p(x)}\\ &=-\sum_{x, y} p(x, y) \log p(x)+\sum_{x, y} p(x, y) \log p(x | y)\\ &=-\sum_{x, y} p(x) \log p(x)-\left(-\sum_{x, y} p(x, y) \log p(x | y)\right)\\ &=H(X)-H(X | Y) \end{aligned}$

另一方面，利用恒等式

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

可得

$I(X ; Y)=H(X)-H(X | Y)=H(Y)-H(Y|X)$

注意到

$H(X|Y)=H(X,Y)-H(Y)$

所以

$\begin{aligned} I(X ; Y) &=H(X)-H(X | Y)\\ &=H(X)-\left(H(X,Y)-H(Y)\right)\\ &=H(X)+H(Y)-H(X, Y) \end{aligned}$

推论：

$I(X ; X)=H(X)$

证明：

$H(X,X)=-E[\log p(X, X)]=-E[\log p(X)] =H(X)$

所以

$\begin{aligned} I(X ; X) &=H(X)+H(X)-H(X,X)\\ &=H(X)+H(X)-H(X)\\ &=H(X) \end{aligned}$

互信息，熵，联合熵的关系可以由下图概括：

熵和互信息的性质

熵的链式法则

$H\left(X_{1}, X_{2}, \ldots, X_{n}\right)=\sum_{i=1}^{n} H\left(X_{i} | X_{i-1}, \ldots, X_{1}\right)$

利用条件概率的链式法则即可：

$p\left(X_{1}, X_{2}, \ldots, X_{n}\right)=\prod_{i=1}^{n}p\left(X_{i} | X_{i-1}, \ldots, X_{1}\right)$

所以

$\log \frac 1 {p\left(X_{1}, X_{2}, \ldots, X_{n}\right)}=\sum_{i=1}^{n} \frac 1{p\left(X_{i} | X_{i-1}, \ldots, X_{1}\right)}$

两边取期望即可得到结论。

同理由条件熵的链式法则：

$H\left(X_{1}, X_{2}, \ldots, X_{n}|Y\right)=\sum_{i=1}^{n} H\left(X_{i} | X_{i-1}, \ldots, X_{1},Y\right)$

条件互信息

条件互信息由下式定义：

$I(X ; Y | Z)=H(X | Z)-H(X | Y, Z)=E\left[\log \frac{p(X, Y | Z)}{p(X | Z) p(Y | Z)}\right] =D(p(x, y|z) \| p(x|z) p(y|z))$

利用条件互信息，可得互信息的链式法则：

$I\left(X_{1}, X_{2}, \ldots, X_{n} ; Y\right)=\sum_{i=1}^{n} I\left(X_{i} ; Y | X_{i-1}, \ldots, X_{1}\right)$

证明：

$I\left(X_{1}, X_{2}, \ldots, X_{n} ; Y\right) =H(X_{1}, X_{2}, \ldots, X_{n})-H(X_{1}, X_{2}, \ldots, X_{n} | Y)$

利用熵以及条件熵的链式法则可得

$\begin{aligned} H\left(X_{1}, X_{2}, \ldots, X_{n}\right)&=\sum_{i=1}^{n} H\left(X_{i} | X_{i-1}, \ldots, X_{1}\right)\\ H\left(X_{1}, X_{2}, \ldots, X_{n}|Y\right)&=\sum_{i=1}^{n} H\left(X_{i} | X_{i-1}, \ldots, X_{1},Y\right) \end{aligned}$

所以

$\begin{aligned} I\left(X_{1}, X_{2}, \ldots, X_{n} ; Y\right) &=H(X_{1}, X_{2}, \ldots, X_{n})-H(X_{1}, X_{2}, \ldots, X_{n} | Y)\\ &=\sum_{i=1}^{n} H\left(X_{i} | X_{i-1}, \ldots, X_{1}\right) -\sum_{i=1}^{n} H\left(X_{i} | X_{i-1}, \ldots, X_{1},Y\right)\\ &=\sum_{i=1}^{n} I\left(X_{i} ; Y | X_{i-1}, \ldots, X_{1}\right) \end{aligned}$

条件相对熵

条件相对熵定义为

$D(p(y | x) \| q(y | x))=\sum_{x} p(x) \sum_{y} p(y | x) \log \frac{p(y | x)}{q(y | x)} =E\left[\log \frac{p(Y | X)}{q(Y | X)}\right]$

条件相对熵也有链式法则：

$D(p(x, y) \| q(x, y))=D(p(x) \| q(x))+D(p(y | x) \| q(y | x))$

证明：

$\begin{aligned} D(p(x, y) \| q(x, y)) &=\sum_{x} \sum_{y} p(x, y) \log \frac{p(x, y)}{q(x, y)}\\ &=\sum_{x} \sum_{y} p(x, y) \log \frac{p(x) p(y | x)}{q(x) q(y | x)}\\ &=\sum_{x, y} p(x, y) \log \frac{p(x)}{q(x)}+\sum_{x, y} p(x, y) \log \frac{p(y | x)}{q(y | x)} \\ &=D(p(x) \| q(x))+D(p(y | x) \| q(y | x)) \end{aligned}$

信息不等式

相对熵（DL散度）不等式

$D(p \| q) \ge 0$

当且仅当$p(x) =q(x)$时等号成立。

令

$f(u)=\log \frac 1 u$

利用Jenson不等式，我们有

$E[f(u)]\ge f(E[u])$

取$u=\frac {q(x)}{p(x)}$，概率分布为$p(x)$，那么

$\begin{aligned} D(p \|q) &=\sum_{x} p(x) \log \frac{p(x)}{q(x)}\\ &=E\left[f\left(\frac {q(x)}{p(x)}\right) \right] \\ &\ge f\left(E\left[\frac {q(x)}{p(x)}\right]\right)\\ &= f(1)\\ &=0 \end{aligned}$

当且仅当$p(x) =q(x)$时等号成立。

互信息非负

$I(X ; Y) \geq 0$

当且仅当$p(x,y)=p(x)p(y)$时等号成立。

证明：

$I(X ; Y)=D(p(x, y) \| p(x) p(y)) \geq 0$

当且仅当$p(x, y)=p(x) p(y)$时等号成立。

条件相对熵（DL散度）不等式

$D(p(y | x) \| q(y | x)) \geq 0$

当且仅当$p(y | x)=q(y | x)$时等号成立。

证明：

$D(p(y | x) \| q(y | x))=\sum_{x} p(x) \sum_{y} p(y | x) \log \frac{p(y | x)}{q(y | x)}$

注意到

$\sum_{y} p(y | x) \log \frac{p(y | x)}{q(y | x)} \ge 0$

当且仅当$p(y | x)=q(y | x)$时等号成立。

所以

$D(p(y | x) \| q(y | x))=\sum_{x} p(x) \sum_{y} p(y | x) \log \frac{p(y | x)}{q(y | x)}\ge 0$

另证：直接使用相对熵的性质即可。

条件互信息非负

$I(X ; Y | Z) \geq 0$

当且仅当$p(x,y|z)=p(x|z)p(y|z)$时等号成立。

证明：

$I(X ; Y | Z)=D(p(x, y|z) \| p(x|z) p(y|z))\ge 0$

当且仅当$p(x,y|z)=p(x|z)p(y|z)$时等号成立。

熵的极大值

$H(X) \leq \log |\operatorname{lm}(X)|$

等号成立当且仅当$X$在$\text{lm}(X)$上是均匀分布。

证明：

取

$u(x)=1 /|\operatorname{lm}(X)|,x\in \operatorname{lm}(X)$

那么

$\begin{aligned} D(p \| u)& =\sum p(x) \log \frac{p(x)}{u(x)}\\ &=-\sum p(x) \log u(x)-\left(-\sum p(x) \log p(x)\right)\\ &=\log |\operatorname{lm}(X)|-H(X)\\ &\ge 0 \end{aligned}$

当且仅当$p(x)=u(x)$时取等号。

熵不等式

$H(X | Y) \leq H(X)$

当且仅当$p(x,y)=p(x)p(y)$时等号成立。

证明：

$I(X;Y)=H(X)-H(X | Y)\ge 0$

当且仅当$p(x,y)=p(x)p(y)$时等号成立。

联合熵的上界

$H\left(X_{1}, X_{2}, \ldots, X_{n}\right) \leq \sum_{i=1}^{n} H\left(X_{i}\right)$

证明：

利用下式

$H\left(X_{i} | X_{i-1}, \ldots, X_{1}\right) \le H(X_i)$

我们有可得

$H\left(X_{1}, X_{2}, \ldots, X_{n}\right)=\sum_{i=1}^{n} H\left(X_{i} | X_{i-1}, \ldots, X_{1}\right) \le \sum_{i=1}^{n} H\left(X_{i}\right)$