跳转至

不确定性和熵

信息

信息

信息包含在问题和答案中. 信息是指一个变量(如答案, 信号, 测量值)减少我们对另一个变量的不确定性或者让我们感到惊讶的程度. 我们需要量化两个方面: 不确定性(熵, entropy)的程度和不确定性减少/让我们惊讶的程度(信息, information). 这些概念可以由香农(Claude Shannon)理论进行量化.

信息论

信息论是一种定量捕捉信息概念的方法. 在传统意义上, 信息论回答了两个问题:

  • 什么是数据的最终压缩: 也就是能将文件压缩到多小
  • 什么是最终的通信传输速率: 也就是最高的下载速度是多少

信息论在其他领域也有广泛的应用:

测量单位

信息通过比特为单位来测量. 1比特表示对一个等概率的是/否问题的不确定性的量度, 换句话说, 一个比特可以表示为一个二元决策中的不确定性, 比如一个抛硬币的问题(正面或者反面). 回答这个是/否问题会较少1比特的不确定性或者提供1比特的信息. 例如, 如果你知道一个硬币会是正面还是反面, 你就获得了1比特的信息, 因为你解决了一个二元问题的不确定性.

量化的基本概念

复习一下概率论中的内容, 详情可以参考这里.

  • 随机变量: \(X\)是一个随机变量, 这是一个取值受随机影响的变量. 例如, 一个答案/信号/测量值. 举例来说, 抛硬币的结果, 今天是否下雨的结果都是随机变量
  • 样本或结果: \(x\)是\(X\)的一个样本或结果, 从一个离散的字母表\(A_X=\{x_1, x_2, ...\}\). 对于二元随机变量\(X\), 字母表\(A_X=\{0, 1\}\); 对于抛硬币的结果, 字母表\(A_X=\{heads, tails\}\), 在"猜猜谁?"游戏中, 头发颜色的字母表可以是各种头发的颜色
  • 概率分布函数(Probability Distribution Function, PDF): 定义概率分布函数\(p(x)\), \(p(x)=P(X=x), x\in A_X\). 满足\(0\leq p(x)\leq 1\), \(\sum_{x\in A_X}p(x)=1, x\in A_X\)

香农信息量

香农信息量(Shannon Information Content)是一个信息论中的基本概念, 用来量化一个事件发生时所带来的信息量. 具体来说, 香农信息量描述的是某个特定事件发生时所减少的不确定性或者说, 描述的是某个特定事件发生时带来的惊喜程度.

对于一个离散随机变量\(X\), 假设它的一个可能的取值为\(x\), 其发生的概率为\(p(x)\), 则事件\(x\)的香农信息量\(h(x)\)定义为: \(h(x)=\log_2(\frac{1}{p(x)})=-\log_2(p(x))\). 可以看出:

  • 由于\(0\leq p(x)\leq 1\), 可得知\(h(x)\geq 0\)
  • 如果事件\(x\)一定发生的话, 即\(p(x)=1\), 则\(h(x)=0\), 没有惊喜
  • 当事件\(x\)的概率\(p(x)\)减小时, 惊喜也会增加

函数图像为:

例子

在"Guess Who"游戏中, 若询问的问题是"是不是Jason", 若总共有\(24\)个人, 如果回答"是", 那么该事件的香农信息量为\(\log_2 24\simeq 4.58\); 如果回答"不是", 那么该事件的香农信息量为\(\log_2 24/23\simeq 0.06\). 可见, 前者导致不确定性减少的程度远远大于后者.

香农熵

香农熵(Shannon Entropy)是一种衡量信息源不确定性的度量, 表示的是随机变量的平均信息量. 随机变量\(X\)的香农熵的定义如下: \(H(X)=\sum_{x\in A_x}p(x)\log_2 \frac{1}{p(x)}=-\sum_{x\in A_x}p(x)\log_2 p(x)\). 也就是说, 香农熵是香农信息量的期望, 可以看出:

  • 若所有的结果\(x\)的概率都为\(p(x)=\frac{1}{|A_X|}\), 那么香农熵\(H(X)=\log_2|A_X|\)
  • 对于随机变量\(X\), \(p(0) = 0.5\), \(p(1)=0.5\), 那么香农熵\(H(X)=1\)
  • 若存在一个结果\(x\)的概率\(p(x)=1\), 则其他所有结果的概率都为\(0\), 那么香农熵\(H(X)=0\)
Tip

当\(p\)趋近于\(0\)的时候, \(p\log p\)趋近于0.

例子

在"Guess Who"游戏中, 若询问的问题是"是不是Jason", 若总共有\(24\)个人, 如果回答"是", 那么该事件的香农信息量为\(\log_2 24\simeq 4.58\); 如果回答"不是", 那么该事件的香农信息量为\(\log_2 24/23\simeq 0.06\). 可以计算香农熵: \(H(X)=-\frac{1}{24}\log_2 \frac{1}{24}-\frac{23}{24}\log_2 \frac{23}{24}\simeq 0.25\). 所以你的回答("是"或"否")会导致不确定性程度平均减少约\(0.25\).

若询问的问题是"是不是有一个眼睛", 如果回答"有", 那么该事件的香农信息量为\(-\log_2 \frac{5}{24}\simeq 2.26\); 如果回答"没有", 那么该事件的香农信息量为\(-\log_2 \frac{19}{24}\simeq 0.34\). 可以计算香农熵: \(H(X)=-\frac{5}{24}\log_2 \frac{5}{24}-\frac{19}{24}\log_2 \frac{19}{24}\simeq 0.74\), 所以你的回答("有"或"没有")会导致不确定性程度平均减少约\(0.74\).

从上面, 可以看出, 后面那个问题, 不管怎么回答, 平均不确定性程度减少的程度较大. 所以应该问后面那个问题.

熵的含义及传统应用

在编码/压缩中, 我们可以经常碰到熵的概念. 假设\(x\)是需要传递的信息, 每一个信息对应的概率为\(p(x)\). \(h(x)\)表示每个信息\(x\)的编码长度, 即为了传递\(x\)需要的比特数. 在一个最优的编码方案中, \(p(x)\)越小, 其对应的编码长度\(h(x)\)就越长(参考霍夫曼树). \(H(X)\)表示传递随机变量\(X\)所需要的理论最佳平均比特数, 它指的就是熵.

对于每个样本进行逐个编码的时候, 由于比特是数字系统的最小单位, 所以只能是整数个比特.

例子

假设有一个二进制随机变量\(X\), 概率为\(p(0)=0.9, p(1)=0.1\), 计算所得熵\(H(X)=-(0.9\log_2 0.9+0.1\log_2 0.1)\simeq 0.469\). 尽管熵是\(0.469\)比特, 我们仍然需要用整数比特来编码整个样本, 即\(1\)比特.

块编码

熵是理论熵的最低限度, 即在最优编码方案下传递信息所需的平均比特数. 任何实际编码方案的平均长度如果超过这个值, 就意味着存在冗余. 如果编码长度大于熵, 就存在多余的比特, 这些比特不携带有用的信息, 通过减少这些冗余, 可以更加高效的传递信息. 单个样本编码通常需要整数比特, 难以完全达到熵的值. 通过块编码(即将多个样本一起编码), 可以使得每个样本的平均编码长度更接近其熵值, 从而减少冗余, 增加爱编码效率.

联合熵

二维(多维)随机变量的熵, 称为联合熵, 联合熵的定义为\(H(X, Y)=\sum_{x\in A_x}\sum_{y\in A_y}p(x, y)\log_2\frac{1}{p(x, y)}=\sum_{x\in A_x}\sum_{y\in A_y}-p(x, y)\log_2p(x, y)\). 我们将\(H(X)\)或者\(H(Y)\)称为边际熵.

注意

\(H(X, Y)=H(X)+H(Y)\)仅当随机变量\(X\)和\(Y\)独立的时候才成立.

例子

仍然使用上面的例子. 现在我们考虑块编码, 即将两个样本组合进行编码. 样本对的可能取值以及它们的概率如下:

  • \(00\): \(0.9 * 0.9 = 0.81\)
  • \(01\): \(0.9 * 0.1 = 0.09\)
  • \(10\): \(0.1 * 0.9 = 0.09\)
  • \(11\): \(0.1 * 0.1 = 0.01\)

计算熵为\(1.163\)比特, 即对两个样本的块编码熵为\(1.163\)比特, 所以平均每个样本的熵为\(\frac{1.163}{2}\simeq 0.5815\)比特. 可以看到, 使用了块编码之后, 平均比特数, 即\(1\), 更加接近其熵, 即理论最佳平均比特数, 即\(0.5815\). 所以说, 使用块编码比使用单个编码更加高效.

条件熵

条件熵\(H(X|Y)\)表示当我们已经知道了\(Y\)的样本值\(y\)时, 对于\(X\)的样本值\(x\)的平均剩余惊讶. 条件信息量和条件熵的计算公式为:

  • \(h(x|y)=h(x, y)-h(y)\)
  • \(h(x|y)=-\log_2 p(x|y)\)
  • \(H(X|y)=\sum_{x\in A_x}p(x|y)\log_2\frac{1}{p(x|y)}\)
  • \(H(X|Y)=\sum_{y\in A_y}p(y)H(X|y)\)
  • \(H(X|Y)=\sum_{x\in A_x}\sum_{y\in A_y}p(x, y)\log_2 \frac{1}{p(x|y)}\)
  • \(H(X|Y)=H(X, Y)-H(Y)\)

条件熵的一些属性:

  • \(0\leq H(X|Y)\leq H(X)\)
  • 当\(X\)与\(Y\)独立的时候, \(H(X|Y)=H(X)\)
  • \(H(X|Y)=0\)意味着只要知道了\(Y\), 那么\(X\)没有任何惊讶
  • \(H(X, Y)=H(X)+H(Y|X)\)
  • \(H(X, Y)=H(Y)+H(X|Y)\)
  • \(H(X_1, X_2, ..., X_n) = \sum_{i=1}^{n}H(X_i|X_1, ..., X_{i-1})\)

文式图表示:

例子

假设我们正在编码一段英文文本, 且我们知道前一个字符是字母"q", 则我们可以高度确定下一个字符是"u". 因为在英文中"q"后面几乎总是跟随着"u", 这种情况下, 条件熵\(H(X|Y)\)会显著低于整体熵\(H(X)\), 因为知道前一个字符"q"大大减少了对下一个字符的惊讶. 这就是"马可夫链".

评论