Information Theory, Inference and Learning Algorithms Lecture 4

课程主页：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$ 的(二进制) 符号码 $C$ 是从 $x$ 的取值范围 $\mathscr{H}_{x}=\left\{a_{1}, a_{2}, \cdots, a_{I}\right\}$到$\{0,1\}^{+}$的一个映射。$c(x)$ 表示相对于 $x$ 的码字 $, l(x)$ 表示它的长度, 即 $l_{i}=l\left(a_{i}\right)$。

拓展码$\boldsymbol{C}^{+}$ 是从 $\mathscr{H}_{X}^{+}$ 到 $\{0,1\}^{+}$的一个映射，定义如下：

$$c^{+}\left(x_{1} x_{2} \cdots x_{N}\right)=c\left(x_{1}\right) c\left(x_{2}\right) \cdots c\left(x_{N}\right)$$

可唯一译码

这里我们要求码字$C(X)$可唯一译码，即

$$\forall x, y \in \mathscr{H}_{x}^{+}, x \neq y \Rightarrow c^{+}(x) \neq c^{+}(y)$$

易于译码

即方便解码，这里使用前缀码来解决这点。前缀码的任何一个码字不是另一个码字的前缀，不难看出前缀码满足唯一性。

压缩

对于总体$X$，符号码$C$的期望长度$L(C,X)$是

$$L(C, X)=\sum_{x \in \mathscr{H}_{X}} P(x) l(x)$$

可以把这个量写为

$$L(C, X)=\sum_{i=1}^{I} p_{i} l_{i}$$

其中$I=|\mathscr H_X|$

可唯一译码性的限制

Kraft不等式

对于任何定义在二元符号集$\{0,1\}$上的可唯一译码的码$C(X)$，其码长必须满足

$$\sum_{i=1}^{I} 2^{-l_{i}} \leqslant 1$$

其中$I=|\mathscr H_X|$。

证明：

定义

$$S=\sum_{i} 2^{-l_{i}}$$

考虑

$$S^{N}=\left[\sum_{i} 2^{-i_{i}}\right]^{N}=\sum_{i_{1}=1}^{I} \sum_{i_{2}=1}^{I} \cdots \sum_{i_{N}=1}^{I} 2^{-\left(l_{i_{1}}+l_{2_{2}}+\cdots+i_{i_{N}}\right)}$$

不难看出$\left(l_{i_{1}}+l_{i_{2}}+\cdots+l_{i_{N}}\right)$表示$\boldsymbol{x}=\boldsymbol{a}_{i_{1}} \boldsymbol{a}_{i_{2}} \cdots \boldsymbol{a}_{i_{n}}$的编码长度。

定义

$$l_{\min }=\min _{i} l_{i},l_{\max }=\max _{i} l_{i}$$

$A_l$表示编码长度为$l$的字符串$x$的数量，那么

$$S^{N}=\sum_{l=Nl_{\min} }^{Nl_{\max}} 2^{-l} A_{l}$$

由唯一性可得

$$|A_l|\le 2^l$$

所以

$$\begin{aligned} S^{N} &=\sum_{l=Nl_{\min} }^{Nl_{\max}} 2^{-l} A_{l}\\ &\le \sum_{l=Nl_{\min} }^{Nl_{\max}} 2^{-l} 2^l\\ &\le \sum_{l=Nl_{\min} }^{Nl_{\max}} 1\\ &\le Nl_{\max} \end{aligned}$$

如果$S>1$，那么上式对充分大的$N$必然不成立，所以

$$S\le 1$$

Kraft不等式和前缀码

已知一组码字长度满足Kraft不等式，那么就存在一个可唯一译码的前级码具有这样的码字长度。

证明：

考虑码字超市：

将码字长度长度从小到大排列，按此顺序选择码字，每次选择完之后将其右侧的码字删除即可得到前缀码。

完全性

如果一个可唯一译码的码，其Kraft不等式的等号成立，那么它叫做完全码。

最大压缩是多少？

我们希望最小化

$$L(C, X)=\sum p_{i} l_{i}$$

下面证明其范围。

期望长度的下界

可唯一译码的码之期望长度 $L(C, X)$ 的下界是 $H(X)$

证明：

定义

$$\begin{aligned} q_i&=\frac{2^{-l_i}}{z} \\ z&=\sum_{i}2^{-l_{i}} \end{aligned}$$

那么

$$l_i =\log \frac 1 {q_i}-\log z$$

回顾Gibbs不等式

$$\sum_{i} p_{i} \log \frac{1}{q_{i}} \geqslant \sum_{i} p_{i} \log \frac{1}{p_{i}}$$

以及可唯一译码的码字满足的条件

$$z=\sum_{i=1}^{I} 2^{-l_{i}} \leqslant 1$$

那么

$$\begin{aligned} L(C, X) &=\sum_{i} p_{i} l_{i}\\ &=\sum_{i} p_{i} \log \frac{1}{q_{i}}-\log z \\ &\ge \sum_{i} p_{i} \log \frac{1}{p_{i}}-\log z \\ & \ge H(X) \end{aligned}$$

最优信源码长

只有码长等于香农信息量

$$l_{i}=\log _{2}\left(\frac{1}{p_{i}}\right)$$

时，期望长度才能最小化，并且等于$H(X)$

由码长定义的隐式概率

码长$\{l_i\}$定义了隐式概率$\{q_i\}$

$$q_{i}=\frac{2^{-l_{i}}}{z}$$

期望长度的上界

存在前缀码$C$，使得

$$H(X) \leqslant L(C, X)<H(X)+1$$

证明：

令

$$l_i =\left\lceil\log _{2}\left(\frac{1}{p_{i}}\right)\right\rceil$$

首先验证Kraft不等式来保证可唯译码的存在性：

$$\sum 2^{-l_{i}}=\sum_{i} 2^{-\left\lceil\log _{2}\left(\frac{1}{p_{i}}\right)\right\rceil}\leqslant \sum 2^{-\log _{2}\left(\frac{1}{p_{i}}\right)}=\sum_{i} p_{i}=1$$

最后带入定义可得

$$\begin{aligned} L(C, X) &=\sum_{i} p_{i} l_{i}\\ &=\sum_{i} p_{i}\left\lceil\log \left(\frac{1}{p_{i}}\right)\right\rceil\\ &< \sum_{i} p_i \left(\log \left(\frac 1 {p_i}\right) + 1\right)\\ &=H(X)+1 \end{aligned}$$

符号码的信源编码定理

对于一个总体$X$，存在前缀码$C$，其期望长度满足

$$H(X) \leqslant L(C, X)<H(X)+1$$

最优的符号码信源编码：霍夫曼码

霍夫曼编码算法

1. 从符号集中选取两个具有最小概率的符号。对这两个符号分配最长的码字，二者长度相同，只有最后一位数字不同。
2. 将这两个符号合并成一个符号，并继续重复下去。

例子

考虑

$$\mathscr {H}_X=\{a, b, c, d, e\} , \mathscr{P}_{X}=\{0.25,0.25,0.2,0.15,0.15\}$$

算法过程如下：

最终得到码字

$$C=\{00,10,11,010,011 \}$$