Information Theory, Inference and Learning Algorithms Lecture 6

课程主页：http://www.inference.org.uk/mackay/itprnn/，http://www.inference.org.uk/itprnn_lectures/

课程视频：https://www.bilibili.com/video/BV14b411G7wn?from=search&seid=1786094286746981315，https://www.youtube.com/watch?v=BCiZc0n6COY&list=PLruBu5BI5n4aFpG32iMbdWoRVAA-Vcso6

课程书籍：https://book.douban.com/subject/1893050/

这次回顾第六讲，第六讲介绍了熵进一步的内容。

备注：笔记参考了中文书籍。

关于熵的更多内容

联合熵

$X,Y$的联合熵是

$$H(X, Y)=\sum_{x y \in \mathscr{H}_{X} {\mathscr H}_{Y}} P(x, y) \log \frac{1}{P(x, y)}$$

条件熵

已知$y=b_k$时$X$的条件熵是

$$H\left(X | y=b_{k}\right) \equiv \sum_{x \in \mathscr{H}_{X}} P\left(x | y=b_{k}\right) \log \frac{1}{P\left(x | y=b_{k}\right)}$$

已知$Y$时$X$的条件熵是

$$\begin{aligned} H(X | Y) & \equiv \sum_{y\in \mathscr H_Y} P(y)\left[\sum_{x \in \mathscr{H}_{X}} P(x | y) \log \frac{1}{P(x | y)}\right] \\ &=\sum_{x y \in \mathscr{H}_{X} {\mathscr H}_{Y}} P(x, y) \log \frac{1}{P(x | y)} \end{aligned}$$

链式法则

信息量的链式法则

利用条件概率恒等式

$$\log \frac{1}{P(x, y)}=\log \frac{1}{P(x)}+\log \frac{1}{P(y | x)}$$

可以得到信息量恒等式

$$h(x, y)=h(x)+h(y | x)$$

熵的链式法则

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

证明：

$$\begin{aligned} H(X, Y)&=\sum_{x y \in \mathscr{H}_{X} {\mathscr H}_{Y}} P(x, y) \log \frac{1}{P(x, y)}\\ &=\sum_{x y \in \mathscr{H}_{X} {\mathscr H}_{Y}} P(x, y) \left(\log \frac{1}{P(x)}+\log \frac{1}{P(y | x)}\right)\\ &= \sum_{x\in \mathscr{H}_{X} }\sum_{y\in \mathscr{H}_{Y} } P(x, y) \log \frac{1}{P(x)} +\sum_{x y \in \mathscr{H}_{X} {\mathscr H}_{Y}} P(x, y) \frac{1}{P(y | x)}\\ &=\sum_{x\in \mathscr{H}_{X} } P(x) \log \frac{1}{P(x)} +\sum_{x y \in \mathscr{H}_{X} {\mathscr H}_{Y}} P(x, y) \frac{1}{P(y | x)}\\ &=H(X)+H(Y|X) \end{aligned}$$

同理可得另一个部分的恒等式。

互信息

$X$和$Y$之间的互信息是

$$I(X ; Y) \equiv H(X)-H(X | Y)$$

互信息满足

$$I(X ; Y) =I(Y;X)\ge 0$$

证明：

利用恒等式

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

我们有

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

另一方面

$$\begin{aligned} I(X ; Y) &= H(X)-H(X | Y)\\ &=H(X)-(H(X,Y)-H(Y))\\ &=H(X)+H(Y)-H(X,Y)\\ &=\sum_{x \in \mathscr{H}_{X}} P(x) \log \frac{1}{P(x)}+ \sum_{y \in \mathscr{H}_{Y}} P(y) \log \frac{1}{P(y)} -\sum_{x y \in \mathscr{H}_{X} {\mathscr H}_{Y}} P(x, y) \log \frac{1}{P(x, y)}\\ &= \sum_{xy \in \mathscr{H}_{X} \mathscr H_Y} P(x,y) \log \frac{1}{P(x)}+ \sum_{xy \in \mathscr{H}_{X} \mathscr H_Y} P(x,y) \log \frac{1}{P(y)}- \sum_{x y \in \mathscr{H}_{X} {\mathscr H}_{Y}} P(x, y) \log \frac{1}{P(x, y)}\\ &= \sum_{xy \in \mathscr{H}_{X} \mathscr H_Y} P(x,y) \log \frac{P(x,y)}{P(x)P(y)}\\ &=D_{KL}(P(x,y)\| P(x)P(y))\\ &\ge 0 \end{aligned}$$

关于互信息，下图概括了几个重要量的关系：

利用互信息非负，我们可得

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

即

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

条件互信息

$z=c_k$时$X$和$Y$之间的条件互信息是在联合总体$P(x,y|z=c_k)$中随机变量$X$和$Y$的互信息

$$I\left(X ; Y | z=c_{k}\right)=H\left(X | z=c_{k}\right)-H\left(X | Y, z=c_{k}\right)$$

已知$Z$时$X$和$Y$的条件互信息是上述互信息在$z$上的平均值

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

熵距离

定义熵距离

$$D_{H}(X, Y) \equiv H(X, Y)-I(X ; Y)$$

那么$D_H$满足距离公理：

$$\begin{aligned} D_{H}(X, Y) &\ge 0\\ D_{H}(X, X)&=0\\ D_{H}(X, Y)&=D_{H}(Y, X)\\ D_{H}(X, Z) &\le D_{H}(X, Y)+D_{H}(Y, Z) \end{aligned}$$

证明：

1.

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

2.

注意到

$$\begin{aligned} H\left(X | x=a_{k}\right) &=\sum_{x \in \mathscr{H}_{X}} P\left(x | x=a_{k}\right) \log \frac{1}{P\left(x | x=a_{k}\right)}\\ &= P\left(x=a_k | x=a_{k}\right) \log \frac{1}{P\left(x=a_k | x=a_{k}\right)}\\ &=0 \end{aligned}$$

所以

$$H(X|X)=0$$

从而

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

3.

利用下式即可

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

4.

首先对$D_{H}(X, Y) $进行变形：

$$\begin{aligned} D_{H}(X, Y) &=H(X, Y)-I(X ; Y)\\ &=H(X,Y)-( H(X)-H(X | Y))\\ &= H(X,Y)-H(X)+H(X|Y)\\ &=\sum_{x y \in \mathscr{H}_{X} {\mathscr H}_{Y}} P(x, y) \log \frac{1}{P(x, y)} -\sum_{x \in \mathscr{H}_{X} } P(x) \log \frac{1}{P(x)} +\sum_{x y \in \mathscr{H}_{X} {\mathscr H}_{Y}} P(x, y) \log \frac{1}{P(x | y)}\\ &= \sum_{x y \in \mathscr{H}_{X} {\mathscr H}_{Y}} P(x, y) \log \frac{1}{P(x, y)} -\sum_{x y \in \mathscr{H}_{X} {\mathscr H}_{Y} } P(x,y) \log \frac{1}{P(x)} +\sum_{x y \in \mathscr{H}_{X} {\mathscr H}_{Y}} P(x, y) \log \frac{1}{P(x | y)}\\ &= \sum_{x y \in \mathscr{H}_{X} {\mathscr H}_{Y}} P(x, y) \log \frac{P(x)}{P(x,y)P(x|y)}\\ &= \sum_{x y \in \mathscr{H}_{X} {\mathscr H}_{Y}} P(x, y) \log \frac{P(x)P(y)}{P^2(x,y)}\\ &=\sum_{x y z\in \mathscr{H}_{X} {\mathscr H}_{Y}{\mathscr H}_{Z}} P(x, y,z) \log \frac{P(x)P(y)}{P^2(x,y)}\\ \end{aligned}$$

另一方面，我们有如下结论（类比$I(X ; Y)=D_{KL}(P(x,y)| P(x)P(y))$）

$$\begin{aligned} I(X ; Y | Z) &=E_z\left[D_{KL}(P(x,y|z),P(x|z)P(y|z))\right]\\ &= \sum_{ z\in {\mathscr H}_{Z}} P(z) \sum_{xy\in {\mathscr H}_{X}{\mathscr H}_{Y}} P(x,y|z)\log \frac{P(x, y | z)}{P(x | z) P(y | z)}\\ &=\sum_{x y z\in \mathscr{H}_{X} {\mathscr H}_{Y}{\mathscr H}_{Z}} P(x, y, z) \log \frac{P(z) P(x, y, z)}{P(x, z) P(y, z)}\\ &\ge 0 \end{aligned}$$

其中非负是因为

$$D_{KL}(P(x,y|z),P(x|z)P(y|z)) \ge 0$$

所以可以推出

$$E_z\left[D_{KL}(P(x,y|z),P(x|z)P(y|z))\right]\ge 0$$

现在对原不等式进行处理

$$\begin{aligned} D_{H}(X, Y)+D_{H}(Y, Z)-D_H(X,Z) &= \sum_{x y z\in \mathscr{H}_{X} {\mathscr H}_{Y}{\mathscr H}_{Z}} P(x, y,z) \left(\log \frac{P(x)P(y)}{P^2(x,y)} +\log \frac{P(y)P(z)}{P^2(y,z)} - \log \frac{P(x)P(z)}{P^2(x,z)} \right)\\ &=\sum_{x y z\in \mathscr{H}_{X} {\mathscr H}_{Y}{\mathscr H}_{Z}} P(x, y,z) \left(\log \frac{P(x)P(y)}{P^2(x,y)} +\log \frac{P(y)P(z)}{P^2(y,z)} - \log \frac{P(x)P(z)}{P^2(x,z)} \right)\\ &=\sum_{x y z\in \mathscr{H}_{X} {\mathscr H}_{Y}{\mathscr H}_{Z}} P(x, y,z) \log \frac{P(x)P^2(y)P(z)P^2(x,z)}{P^2(x,y)P^2(y,z)P(x)P(z)}\\ &=2\sum_{x y z\in \mathscr{H}_{X} {\mathscr H}_{Y}{\mathscr H}_{Z}} P(x, y,z) \log \frac{P(y)P(x,z)}{P(x,y)P(y,z)}\\ &=2\sum_{x y z\in \mathscr{H}_{X} {\mathscr H}_{Y}{\mathscr H}_{Z}} P(x, y,z) \log \frac{P(y)P(x,y,z)P(x,z)}{P(x,y)P(y,z)P(x,y,z)}\\ &=2\sum_{x y z\in \mathscr{H}_{X} {\mathscr H}_{Y}{\mathscr H}_{Z}} P(x, y,z) \left(\log \frac{P(y)P(x,y,z)}{P(x,y)P(y,z)} -\log\frac 1 {P(x,z)} +\log \frac{1}{P(x,y,z)} \right)\\ &=2 \left( I(X;Z|Y)-H(X,Z)+H(X,Y,Z) \right) \end{aligned}$$

利用之前的结论可得

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

此外显然有

$$H(X,Y,Z) - H(X,Z)\ge 0$$

所以

$$D_{H}(X, Y)+D_{H}(Y, Z)-D_H(X,Z) \ge 0$$