Information Theory, Inference and Learning Algorithms Lecture 3

课程主页：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$的香农信息量定义为

$$h(x)=\log _{2} \frac{1}{P(x)}$$

总体$X$的熵定义为香农信息量的期望

$$H(X) \equiv \sum_{x \in \mathscr{G}_{X}} P(x) \log \frac{1}{P(x)}$$

下面给出熵定义的直觉，考虑如下随机变量

$$P(x=\pm1)=\frac 1 2$$

所以$x$以等概率出现$\pm 1$，因此大约利用$1$比特即可描述该随机变量，另一方面，熵为

$$H(X)= \frac 1 2 +\frac 1 2 =1$$

这说明熵和我们的直觉符合，课本中还举例称重的例子，非常有意思，具体的可以参考课本。

数据压缩

如果可以将特定源数据压缩成$L$比特的文件，并且能够恢复数据，那么就称这个信源的平均信息量最多为每个符号$L$比特，例如信源数据属于集合$\mathscr H_X$，那么可以显然可以使用如下长度的比特存储数据：

$$\boldsymbol{H}_{0}(X)=\log _{2}\left|\mathscr{H}_{X}\right|$$

有损压缩

因为不同结果出现的概率不同，有损压缩的思想就是丢弃那些出现概率较低的结果，对剩余情形重新编码，从而达到压缩数据的功能。

最小$\delta$-充分子集

$S_\delta$是满足

$$P\left(x \in S_{\delta}\right) \geqslant 1-\delta$$

的最小$\mathscr H_X$子集（即元素数量最小）。构造方法如下，首先将$\mathscr H_X$中元素按照概率从大到小排列，初始化$ S_{\delta}= \varnothing$，然后依次加入集合$ S_{\delta}$直到上式成立即可。

$X$的基本比特内容定义为

$$H_{\delta}(X)=\log | S_{\delta}|$$

香农信源编码定理

记

$$X^N=\left(X_{1}, X_{2}, \cdots, X_{N}\right)$$

设$X$为熵$H(X)=H$比特的一个总体。若$\epsilon>0,0<\delta <1$，则存在一个正整数$N_0$，当$N>N_0$时，有

$$\left|\frac{1}{N} H_{\delta}\left(X^{N}\right)-H\right|<\varepsilon$$

典型性

为了解释上述定理，考虑如下例子：

考虑一个硬币$N$次翻转所得到的字符串$x=\left(x_{1}, x_{2}, \cdots, x_{N}\right)$，其中$x_n \in \{0,1\}$，其中$p_0=0.9,p_1=0.1$，记$r$为$1$出现的次数，那么随着$N$增加，根据大数定律$r$应该在一个较小的范围内，对应的$x$应该也落在一个较小的子集中，这个子集就称为典型集，下面给出正式定义。

典型集

典型集$T_{N\beta}$定义为如下集合：

$$T_{N \beta}=\left\{\boldsymbol{x} \in \mathscr{H}_{X}^{N}:\left|\frac{1}{N} \log _{2} \frac{1}{P(x)}-H(X)\right|<\beta\right\}$$

可以这样理解，典型集中的元素出现的概率约等于于$2^{-NH}$，元素数量大约有$2^{NH}$个。

“渐进均分”原理

对于$N$个独立同分布随机变量总体$X^N=\left(X_{1}, X_{2}, \cdots, X_{N}\right)$，当$N$充分大时，结果$x=\left(x_{1}, x_{2}, \cdots, x_{N}\right)$几乎肯定属于一个只有$2^{NH(X)}$个元素的子集，每个成员的概率都“接近”$2^{-NH(X)}$。

定理证明

弱大数定律

$N$个独立同分布随机变量$h_1,h_2,\ldots,h_N$，期望为$\bar h$，方差为$\sigma_h^2$，考虑$x= \frac 1 N\sum_{n=1}^N h_n$，那么

$$P\left((x-\bar{h})^{2} \geqslant \alpha\right) \leqslant \sigma_{h}^{2} / \alpha N$$

证明

考虑随机变量$\log \frac 1 {P(X)}$，那么其均值为$H(X)$，方差记为$\sigma^2= \operatorname{var}\left[\log _{2}\left(1 / P\left(x\right)\right)\right]$，现在考虑典型集（这里将$H(X)$简记为$H$）

$$T_{N \beta}=\left\{\boldsymbol{x} \in \mathscr{H}_{X}^{N}:\left|\frac{1}{N} \log \frac{1}{P(x)}-H\right|<\beta\right\}$$

那么由弱大数定律可得

$$P(x\in T_{N\beta})\ge 1-\frac {\sigma^2 }{\beta^2N}$$

说明当$N$趋于无穷时，$x$属与典型集$T_{N\beta}$的概率趋近于$1$。

为了证明香农信源编码定理，需要将典型集和$H_{\delta}(X)$联系起来，为了讨论方便，首先将原始定理的形式进行变形：

$$\left|\frac{1}{N} H_{\delta}\left(X^{N}\right)-H\right|<\varepsilon \Leftrightarrow \\ 2^{N(H-\epsilon)}<H_{\delta}\left(X^{N}\right) <2^{N(H+\epsilon)}$$

所以只要证明a

$$H_{\delta}\left(X^{N}\right)<2^{N(H+\epsilon)}$$

以及b

$$2^{N(H-\epsilon)}<H_{\delta}\left(X^{N}\right)$$

即可，下面分别证明。

a

取$\beta=\epsilon$，那么当$N$趋于正无穷时，必然可以使得

$$P(x\in T_{N\beta})\ge 1-\frac {\sigma^2 }{\beta^2N} \ge 1-\delta$$

这说明

$$H_{\delta} \le |T_{N\beta}|$$

如果能证明

$$|T_{N\beta}| < 2^{N(H+\epsilon)}$$

那么即可完成这一部分的证明。

由定义可得对于任意$x\in T_{N\beta}$：

$$\left|\frac{1}{N} \log \frac{1}{P(x)}-H\right|<\beta \\ H-\beta<\frac{1}{N} \log \frac{1}{P(x)} < H+\beta \\ -N(H+\beta)<\log {P(x)} < -N(H-\beta)\\ 2^{-N(H+\beta)}<P(x) < 2^{-N(H-\beta)}$$

所以

$$1=\sum_{x\in T_{N\beta}} P(x)>|T_{N\beta}| 2^{-N(H+\beta)}$$

即

$$|T_{N\beta}| < 2^{N(H+\beta)}$$

注意到这里$\beta =\varepsilon$，那么

$$H_{\delta} \le |T_{N\beta}| < 2^{N(H+\varepsilon)}$$

第一部分证毕。

b

反证法，若对于任意的$N$，我们有

$$H_{\delta}\left(X^{N}\right) \le 2^{N(H-\epsilon)}$$

假设对应的最小$\delta$充分子集为$S’$，如果能证明

$$P(x\in S') < 1-\delta$$

即可推翻该假设。

注意到我们有

$$P(x\in S')=P(x\in S' \cap T_{N\beta}) + P(x\in S' \cap \overline{T_{N\beta}})$$

对于第一部分，$\forall x \in T_{N\beta}$，我们有

$$P(x) < 2^{-N(H-\beta)}$$

而

$$|S'|=H_{\delta}\left(X^{N}\right) \le 2^{N(H-\epsilon)}$$

所以

$$P(x\in S' \cap T_{N\beta}) \le 2^{N(H-\epsilon)} 2^{-N(H-\beta)} =2^{N(\beta-\epsilon)}$$

对于第二部分，由大数定律可得

$$P(x\in S' \cap \overline{T_{N\beta}})\le P(x\in \overline{T_{N\beta}}) \le \frac {\sigma^2}{\beta^2 N}$$

所以

$$P(x\in S')=P(x\in S' \cap T_{N\beta}) + P(x\in S' \cap \overline{T_{N\beta}}) \le 2^{N(\beta-\epsilon)}+ \frac {\sigma^2}{\beta^2 N}$$

取$\beta =\frac \epsilon 2$，那么

$$P(x\in S')=P(x\in S' \cap T_{N\beta}) + P(x\in S' \cap \overline{T_{N\beta}}) \le 2^{N(-\frac \epsilon 2)}+ \frac {\sigma^2}{\beta^2 N}$$

令$N\to \infty$可得

$$P(x\in S') \le 2^{N(-\frac \epsilon 2)}+ \frac {\sigma^2}{\beta^2 N} \to 0 <1-\delta$$

显然原结论不成立，因此

$$2^{N(H-\epsilon)}<H_{\delta}\left(X^{N}\right)$$