信息论

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

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

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

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

简述

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

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

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

信息的度量

信息熵

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

H(X)=\mathbb{E}_{X} [I(x)] =\sum_{x\in\mathcal{X}}^{}p(x)\log_2\left(\frac{1}{p(x)}\right)

其中 $\mathcal{X}$ 为有限个事件x的集合， $X$ 是定义在 $\mathcal{X}$ 上的随机变量。信息熵是随机事件不确定性的度量。

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

S(X)=k_BH(X)

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

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

例子

设有一个三个面的骰子，三面分别写有 $1, 2, 3$ ， $X$ 为掷得的数，掷得各面的概率为

{\displaystyle \begin{align}\mathbb P(X = 1) & =1/5, \\ \mathbb P(X = 2) & =2/5, \\ \mathbb P(X = 3) & = 2/5, \end{align} }

则

H(X)=\frac{1}{5}\log_2 (5)+\frac{2}{5}\log_2\left(\frac{5}{2}\right)+\frac{2}{5}\log_2\left(\frac{5}{2}\right) \approx 1.522 .

联合熵与条件熵

联合熵（Joint Entropy）由熵的定义出发，计算联合分布的熵：

H(X,Y)=\sum_{x\in\mathcal{X}}\sum_{y\in\mathcal{Y}}^{}p(x,y)\log\left(\frac{1}{p(x,y)}\right).

条件熵（Conditional Entropy），顾名思义，是以条件概率 $p(y|x)$ 计算：

H(Y|X)=\sum_{x\in\mathcal{X}}\sum_{y\in\mathcal{Y}}^{}p(x,y)\log\left(\frac{1}{p(y|x)}\right).

由贝叶斯理论，有 $p(x,y)=p(y|x)p(x)$ ，代入联合熵的定义，可以分离出条件熵，于是得到联合熵与条件熵的关系式:

H(X,Y)=H(X)+H(Y|X)=H(Y)+H(X|Y)=H(Y,X).

链式法则

可以再对联合熵与条件熵的关系做推广，假设现在有 $n$ 个随机变量 $X_i, i=1,2,...,n$ ，重复分离出条件熵，有：

{\displaystyle \begin{align} H(X_1,X_2,...,X_n)&=H(X_1)+H(X_2,...,X_n|X_1)\\ &=H(X_1)+H(X_2|X_1)+H(X_3,...,X_n|X_1,X_2)\\ &=H(X_1)+\sum_{i=2}^{n}H(X_i|X_1,...,X_{i-1})\end{align}.}

其直观意义如下：假如接收一段数列 $\{X_1,X_2,...,X_n\}$ ，且先收到 $X_1$ ，再来是 $X_2$ ，依此类推。那么收到 $X_1$ 后总信息量为 $H(X_1)$ ，收到 $X_2$ 后总信息量为 $H(X_1)+H(X_2|X_1)$ ，直到收到 $X_n$ 后，总信息量应为 $H(X_1,...,X_n)$ ，于是这个接收过程给出了链式法则。

互信息

互信息（Mutual Information）是另一有用的信息度量，它是指两个事件集合之间的相关性。两个事件 $X$ 和 $Y$ 的互信息定义为：

I(X;Y) = H(X)-H(X|Y)=H(X) + H(Y) - H(X, Y)=H(Y)-H(Y|X)=I(Y;X).

其意义为， $Y$ 包含 $X$ 的多少信息。在尚未得到 $Y$ 之前，对 $X$ 的不确定性是 $H(X)$ ，得到 $Y$ 后，不确定性是 $H(X|Y)$ 。所以一旦得到 $Y$ ，就消除了 $H(X)-H(X|Y)$ 的不确定量，这就是 $Y$ 对 $X$ 的信息量。

如果 $X,Y$ 互为独立，则 $H(X,Y)=H(X)+H(Y)$ ，于是 $I(X;Y)=0$ 。

又因为 $H(X|Y)\leq H(X)$ ，所以

I(X;Y)\leq \min(H(X),H(Y)),

其中等号成立条件为 $Y=g(X)$ ， $g$ 是一个双射函数。

互信息与G检验以及皮尔森卡方检验有着密切的联系。

应用

信息论被广泛应用在：

参考文献

↑ F. Rieke, D. Warland, R Ruyter van Steveninck, W Bialek. Spikes: Exploring the Neural Code. The MIT press. 1997. ISBN 978-0262681087.
↑ 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
↑ 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
↑ 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.
↑ Jaynes, E. T. (1957) Information Theory and Statistical Mechanics , Phys. Rev. 106:620
↑ Charles H. Bennett, Ming Li, and Bin Ma (2003) Chain Letters and Evolutionary Histories , Scientific American 288:6, 76-81
↑ 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].

外部链接

香农论文：通信的数学理论

[1] F. Rieke, D. Warland, R Ruyter van Steveninck, W Bialek. Spikes: Exploring the Neural Code. The MIT press. 1997. ISBN 978-0262681087.

[2] . 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].

[1]

[2]

[3]

[4]

[5]

[6]

[7]