信息论

數學理論,來自於機率論和統計學領域

信息论(英语:information theory)是应用数学电子学电脑科学的一个分支,涉及信息的量化、存储和通讯等。信息论是由克劳德·香农发展,用来找出信号处理通讯操作的基本限制,如数据压缩、可靠的存储和数据传输等。自创立以来,它已拓展应用到许多其他领域,包括统计推断、自然语言处理密码学神经生物学[1]、进化论[2]和分子编码的功能[3]生态学的模式选择[4]、热物理[5]量子计算语言学、剽窃检测[6]模式识别异常检测和其他形式的数据分析[7]

是信息的一个关键度量,通常用一条消息中需要存储或传输一个符号英语Symbol rate的平均位元数来表示。熵衡量了预测随机变量的值时涉及到的不确定度的量。例如,指定掷硬币的结果(两个等可能的结果)比指定掷骰子的结果(六个等可能的结果)所提供的信息量更少(熵更少)。

信息论将信息的传递作为一种统计现象来考虑,给出了估算通讯信道容量的方法。信息传输和信息压缩是信息论研究中的两大领域。这两个方面又由信道编码定理信源-信道隔离定理相互联络。

信息论的基本内容的应用包括无损数据压缩(如ZIP文件)、有损数据压缩(如MP3JPEG)、信道编码(如数码用户线路DSL))。这个领域处在数学统计学电脑科学物理学神经科学电机工程学的交叉点上。信息论对航海家深空探测任务的成败、光碟的发明、手机的可行性、互联网的发展、语言学和人类感知的研究、对黑洞的了解,以及许多其他领域都影响深远。信息论的重要子领域有信源编码信道编码算法复杂性理论算法信息论信息论安全性信息度量等。

简述

信息论的主要内容可以类比人类最广泛的交流手段——语言来阐述。

一种简洁的语言(以英语为例)通常有两个重要特点: 首先,最常用的词(比如"a"、"the"、"I")应该比不太常用的词(比如"benefit"、"generation"、"mediocre")要短一些;其次,如果句子的某一部分被漏听或者由于杂讯干扰(比如一辆车辆疾驰而过)而被误听,听者应该仍然可以抓住句子的大概意思。而如果把电子通讯系统比作一种语言的话,这种健壮性robustness)是不可或缺的。将健壮性引入通讯是通过信道编码完成的。信源编码和信道编码是信息论的基本研究课题。

注意这些内容同消息的重要性之间是毫不相干的。例如,像“多谢;常来”这样的客套话与像“救命”这样的紧急请求在说起来、或者写起来所花的时间是差不多的,然而明显后者更重要,也更有实在意义。信息论却不考虑一段消息的重要性或内在意义,因为这些是数据的质量的问题而不是数据量(数据的长度)和可读性方面上的问题,后者只是由概率这一因素单独决定的。

信息的度量

信息熵

美国数学家克劳德·香农被称为“信息论之父”。人们通常将香农于1948年10月发表于《贝尔系统技术学报英语Bell System Technical Journal》上的论文《通讯的数学理论英语A Mathematical Theory of Communication》作为现代信息论研究的开端。这一文章部分基于哈里·奈奎斯特拉尔夫·哈特利英语Ralph Hartley于1920年代先后发表的研究成果。在该文中,香农给出了信息熵的定义:

 

其中 为有限个事件x的集合, 是定义在 上的随机变量。信息熵是随机事件不确定性的度量。

信息熵与物理学中的热力学熵有着紧密的联络:

 

其中S(X)为热力学熵,H(X)为信息熵, 波兹曼常数。 事实上这个关系也就是广义的波兹曼熵公式,或是在正则系综内的热力学熵表示式。如此可知,玻尔兹曼吉布斯在统计物理学中对熵的工作,启发了信息论的熵。

信息熵是信源编码定理中,压缩率的下限。若编码所用的信息量少于信息熵,则一定有信息的损失。香农在大数定律渐进均分性英语Asymptotic equipartition property的基础上定义了典型集英语Typical set和典型序列。典型集是典型序列的集合。因为一个独立同分布的 序列属于由 定义的典型集的概率大约为1,所以只需要将属于典型集的无记忆 信源序列编为唯一可译码,其他序列随意编码,就可以达到几乎无损失的压缩。

例子

设有一个三个面的骰子,三面分别写有  为掷得的数,掷得各面的概率为

 

 

联合熵与条件熵

联合熵Joint Entropy)由熵的定义出发,计算联合分布的熵:

 

条件熵Conditional Entropy),顾名思义,是以条件概率 计算:

 

贝叶斯理论,有 ,代入联合熵的定义,可以分离出条件熵,于是得到联合熵与条件熵的关系式:

 

链式法则

可以再对联合熵与条件熵的关系做推广,假设现在有 个随机变量 ,重复分离出条件熵,有:

 

其直观意义如下:假如接收一段数列 ,且先收到 ,再来是 ,依此类推。那么收到 后总消息量为 ,收到 后总消息量为 ,直到收到 后,总消息量应为 ,于是这个接收过程给出了链式法则。

互信息

互信息Mutual Information)是另一有用的信息度量,它是指两个事件集合之间的相关性。两个事件  的互信息定义为:

 

其意义为, 包含 的多少信息。在尚未得到 之前,对 的不确定性是 ,得到 后,不确定性是 。所以一旦得到 ,就消除了 的不确定量,这就是  的信息量。

如果 互为独立,则 ,于是 

又因为 ,所以

 

其中等号成立条件为  是一个双射函数。

互信息与G检验英语G-test以及皮尔森卡方检验有着密切的联络。

应用

信息论被广泛应用在:

参考文献

  1. ^ F. Rieke, D. Warland, R Ruyter van Steveninck, W Bialek. Spikes: Exploring the Neural Code. The MIT press. 1997. ISBN 978-0262681087. 
  2. ^ cf. Huelsenbeck, J. P., F. Ronquist, R. Nielsen and J. P. Bollback (2001) Bayesian inference of phylogeny and its impact on evolutionary biology, Science 294:2310-2314
  3. ^ Rando Allikmets, Wyeth W. Wasserman, Amy Hutchinson, Philip Smallwood, Jeremy Nathans, Peter K. Rogan, Thomas D. Schneider页面存档备份,存于互联网档案馆), Michael Dean (1998) Organization of the ABCR gene: analysis of promoter and splice junction sequences, Gene 215:1, 111-122
  4. ^ Burnham, K. P. and Anderson D. R. (2002) Model Selection and Multimodel Inference: A Practical Information-Theoretic Approach, Second Edition (Springer Science, New York) ISBN 978-0-387-95364-9.
  5. ^ Jaynes, E. T. (1957) Information Theory and Statistical Mechanics页面存档备份,存于互联网档案馆), Phys. Rev. 106:620
  6. ^ Charles H. Bennett, Ming Li, and Bin Ma (2003) Chain Letters and Evolutionary Histories页面存档备份,存于互联网档案馆), Scientific American 288:6, 76-81
  7. ^ David R. Anderson. Some background on why people in the empirical sciences may want to better understand the information-theoretic methods (PDF). November 1, 2003 [2010-06-23]. (原始内容 (pdf)存档于2011-07-23). 

外部链接