信息熵

作者: M_lear | 来源:发表于2019-08-25 00:07 被阅读0次

信息论之父 C. E. Shannon 在 1948 年发表的论文“通信的数学理论（A Mathematical Theory of Communication）”中指出，绝大部分信息都存在冗余，冗余大小与信息中每个符号（数字、字母或单词）的出现概率或者说不确定性有关。

Shannon 借鉴了热力学的概念，把信息中排除了冗余后的平均信息量称为“信息熵”，并给出了计算信息熵的数学表达式。
假设信息中有 $n$ 种符号，每种符号出现的概率为 $p_i(\sum_{i=1}^np_i=1)$ ，则信息熵为： $\mathrm H(p)=\sum_{i=1}^np_i\log\frac{1}{p_i}$

刚看到这个公式时，我们的脑海中一定会有很多的疑问。比如，为什么是概率？为什么是概率的倒数？为什么是对数？等等这些问题。我们很难直观的理解这个公式是如何衡量信息量的大小的。

今天我们从编码的角度上，来直观地理解信息熵。
问题一：对于包含 [A, B, C, D, E, F, G, H] 8 个字符的字符集来说，至少需要多少二进制位来编码？

一位二进制位能编码两种字符，两位二进制位能编码四种字符。一般的， $m$ 位二进制位能编码 $2^m$ 种字符。那么对于 8 种字符至少需要多少二进制位编码的问题，是前面问题的逆问题，所以自然可以想到使用指数运算的逆运算对数运算来求解。所以 8 种字符至少需要 ${\log_2}^8=3$ 位二进制编码。一般的，编码 $N$ 种字符需要 $\lceil{\log_2}^N\rceil$ 位二进制编码。

我们可以使用编码一个字符集所需要的最少的二进制位数来衡量字符集的信息量，那么上面这个字符集的信息量就可以量化为 $8\times3=24\mathrm{bit}$ 。

问题二：那么对于字符集 [A, A, A, A, B, B, C, C]，即 {A:4, B:2, C:2} 来说，至少需要多少二进制位来编码呢？（对于学过哈夫曼编码的同学来说，这个问题是不是很熟悉，这不就是一个求哈夫曼树带权路径长度（WPL）的问题嘛。）

符号约定： $N$ 表示字符集的字符个数； $N_A$ 表示字符 A 的个数， $N_B,N_C$ 的含义同理。
以字符 A 为例，我们可以按照如下方式计算字符 A 至少需要的二进制编码位数：

$\mathrm I_A={\log_2}^N-{\log_2}^{N_A}$
这个式子可以理解为，首先假设字符集的 $N$ 个字符都是不同的，那么编码区分字符 A 就需要 ${\log_2}^N$ 位编码；但是现在 $N$ 个字符中有 $N_A$ 个 A 字符，也就是说 $N$ 个字符中有 $N_A$ 个字符不需要进行编码区分，那么就需要减去区分 $N_A$ 个字符的编码位数，得到的结果就是 A 字符至少需要编码位数。
下面我们可以分别计算 A，B，C 三种字符至少需要的编码位数，
A： ${\log_2}^8-{\log_2}^4=1$
B： ${\log_2}^8-{\log_2}^2=2$
C： ${\log_2}^8-{\log_2}^2=2$
那么这个字符集需要的最少二进制编码位数（字符集的信息量）为：
$N_A\times1+N_B\times2+N_C\times2=12\mathrm{bit}$
我们可以看到，同样是 8 个字符的字符集，第二个字符集所含的信息量要远小于第一个字符集。

注意，不要真正使用上面这个方法去计算哈夫曼树的带权路径长度，因为这种方法的计算结果可能出现小数。实际上，字符集的信息量是字符集最优编码长度的理论下界，哈夫曼编码也是最优编码的一种。

对于之前的 $\mathrm I_A$ ，利用对数函数的性质我们容易得到：
$\mathrm I_A={\log_2}^{\frac{N}{N_A}}$
又 $p_A=\frac{N_A}{N}$ ，所以上式可以写作：
$\mathrm I_A={\log_2}^{\frac{1}{p_A}}$
实际上，这个式子就是信息量的定义。对数函数不同的底对应信息量的不同单位，当对数的底为 2 时，信息量的单位是 bit；当底为 e 时，信息量的单位是 nat；而当底为10 时，信息量的单位是 Hart。