熵、相对熵与互信息——初探信息论

1. 信息论与熵

1948年,美国数学家克劳德·香农发表论文《通信的数学理论》(A Mathematical Theory of Communication),奠定了信息论的基础。

今天,信息论在信号处理、数据压缩、自然语言等许多领域,起着关键作用。虽然,它的数学形式很复杂,但是核心思想非常简单。

举一个哈夫曼编码的例子:

A与B联系,只用四个词汇:狗,猫,鱼,鸟。

在互联网传递,需要用二进制编码表示,如下面这种:

  • 狗 00
  • 猫 01
  • 鱼 10
  • 鸟 11

所以一封信“狗猫鱼鸟”编码为00011011,另一封“鱼猫鸟狗”编码为10011100

而对于词频不均的一封信,如“狗狗狗狗猫猫鱼鸟”,编码为0000000001011011,似乎有点长,如何缩短编码?我们可以采用哈夫曼编码:

  • 狗 0
  • 猫 10
  • 鱼 110
  • 鸟 111

这样编码下,“狗狗狗狗猫猫鱼鸟”可以编码为00001010110111,从16个二进制位缩短到了14个。同时,我们注意到,这里狗编码为0,是不能改成1的,会造成歧义。(可以参考霍夫曼编码原理)

在上面例子中我们可以看到:概率越大,所需要的二进制位越少。(概率大->不确定程度小->信息/熵少)

香农给出了一个概率于二进制位的计算公式:

知道了每种概率对应的编码长度,就可以计算出一种概率分布的平均编码长度:

上面的$H$,就是该种概率分布的平均编码长度。理论上,这也是最优编码长度,不可能获得更短的编码。$H$也就是信息量的度量,称为“信息熵”。

由于信息量的多少与概率分布相关,所以在信息论里面,信息被定义成不确定性的相关概念:概率分布越分散,不确定性越高,信息量越高,信息量越大;繁殖,信息量越少。

总体来说,信息论是应用数学、电子学和计算机科学的一个分支,设计信息的量化、存储和通信等。信息传输和信息压缩是信息论研究中的两大领域。

2. 联合熵与条件熵

联合熵定义:

对于服从联合分布为$p(x,y)$的一堆离散随机变量$(X,Y)$,其联合熵$H(X,Y)$定义为:

上式也可以表示为:

条件熵定义:

若$(X,Y)~p(x,y)$,条件熵$H(Y|X)$定义为:

链式法则:

等价于(两边同时取数学期望):

性质:

可以通过移项证明。

3. 相对熵与互信息

相对熵定义:

两个概率密度函数为$p(x)$和$q(x)$之间的相对熵或Kullback-Leibler距离定义为

相对熵是两个随机分布之间距离的度量。在统计学中,它对应的是似然比的对数期望。

互信息定义:

考虑两个随机变量$X$和$Y$,他们的联合概率密度函数为$p(x,y)$,其编辑概率密度函数分别是$p(x)$和$p(y)$。互信息$I(X;Y)$为两盒分布$p(x,y)$和成绩分布$p(x)p(y)$之间的相对熵,即:

互信息是一个随机变量包含另一个随机变量信息量的度量。互信息也是在给定另一随机变量知识的条件下,原随机变量不确定度的缩减量。

熵和互信息的关系:

对称的。熵有时称为自信息。

参考资料

  1. 信息论入门教程
  2. 《信息论基础》 Cover著