对论文《A Mathematical Theory of Communication》的简要解读
作者 张洋 | 发布于 2017-05-31
信息论 香农

香农在1948年发表了一篇著名的论文A Mathematical Theory of Communication,作为现代信息论的奠基之作,不管是从理论角度还是对人类实际生活的贡献,再怎么强调这篇论文的重要性都不过分。虽然之前对信息论已经有所了解,但是为了向信息论鼻祖致敬,最近还是拜读了这篇论文。这篇论文自成体系,可以说是字字珠玑,读完后对整个信息论的来龙去脉有了更加深入的了解。其实这篇论文主要就是要解决如何用数学方式去度量信息的价值,虽然核心思想及方法非常简单明了,但是由于是一篇数学论文,其中对”价值“并没有进行直观描述,再加上掺杂了一些略微复杂的数学公式,所以有可能阅读起来会略有困难。我写这篇文章就是想通过一个直观的类比(通过一个猜硬币游戏),并把论文中抽象的“价值”直接具象化为“金钱”,以此帮助读者更容易理解论文要阐述的关键点,从而更好的阅读这篇论文。

1 衡量信息价值

1.1 猜硬币游戏

正文开篇需要再强调一遍,这篇论文的核心就是提出一种在数学上量化信息价值的方法,整个论文的内容基本都是为这个主题服务的,因此理解了这个度量方法,也就掌握了理解这篇论文的关键。而这也是这篇论文最开辟性的地方,在香农之前,没有人能明确使用数学方法量化信息这一概念。

为了直观理解这一方法,先看一个简单的猜硬币游戏:

猜硬币游戏规则:一枚硬币被连续掷出,每次掷硬币正反面概率各为1/2,每次掷硬币事件相互独立。玩家可以猜任意次结果,猜对赢得1元,猜错输掉1元。

很明显,如果没有其他附加信息,这个游戏是一个期望为0的游戏,即不管是猜多少次,总盈利的期望总是0。

1.2 单个符号的价值

现在考虑这样一种情况,有一个人可以偷窥到硬币掷完后的状态,并且每次看到时,可以向你传递信息,但是这个信息只能是一个有两种状态的符号,为了方便我们姑且认为这个符号可以是0或1,那么请问每一个这样的符号值多少钱?

很显然,我们可以和信息传递者约定,0表示正面,1表示反面,这样每一个符号可以稳定帮我们赚到1元钱,所以我们可以说每一个这样的符号价值是1元。

现在考虑另一种情况,如果现在允许每个符号有10种状态(姑且认为可以是阿拉伯数字0-9),那么同样一个符号,价值是多少钱?

此时为了最大发挥这个符号的价值,我们可以这样做:不再是掷一次硬币传递一个符号,而是掷N次后再传递一个符号,而这个符号必须能准确表示这N次投掷的状态。由于3次投掷有8种状态,而4次投掷有16种状态,所以这里的N最多只能是3。我们可以这样约定如何传输这个符号:

正正正 - 0,正正反 - 1,正反正 - 2,正反反 - 3,反正正 - 4,反正反 - 5, 反反正 - 6,反反反 - 7

还有两个状态8和9没用,先不管了,照这种方式,一个符号至少可以稳定帮我们赚3元。我们看到,同样是一个符号,10个状态比两个状态价值高很多,所以我们得到了第一个重要的结论:

定性结论1:在其它条件不变的情况下,单个信息符号可表示状态越多,价值越大。

这里我们先给出定性结论,如何用数学定量的方式度量这个符号的价值,后面再说。

1.3 不确定性与符号价值

上面我们知道,在这个游戏中,一个二状态信息符号值一元钱,现在我们变更以下游戏条件,硬币正反面不再是等概率,而是正面概率为$p$,反面概率为$1-p$,那么此时这个符号还值1元吗?我们首先考虑一个极端情况:$p=1$,此时硬币永远是正面,显然此时我们根本不需要这个符号,只要一直猜正面就能每次稳赚1元钱,所以此时可以说这个信息毫无价值;反之如果$p=0$也一样,我们一直猜反面就好了。

那么,如果$p=0.8$,会怎么样?此时我们知道,即使没有这个符号信息,我们只要每次猜正面,猜对的概率也有80%,此时每一轮游戏期望收益为:$E(x)=0.8\times1+0.2\times(-1)=0.6$。

即是说,每一次猜正面,本身就可以有0.6元的收益,因此此时一个符号附加的价值是$1-0.6=0.4$。

由上分析,我们得到第二个定性结论:

定性结论2:在其它条件不变的情况下,单个符号所面对的情况越随机,价值越大。

或者换一种说法:

定性结论2*:一个信息符号的价值取决于其消除的不确定性,消除的不确定性越高,价值越大。

最后我们得出一个总的定性结论:

一个信息符号的价值取决于符号可表示状态数及可以消除的不确定性。

所以,如果要量化符号价值,只需量化“可表示状态数”及“不确定性”即可。

1.4 可表示状态数的量化

还是以上面二状态和十状态符号为例,上面看到后者的价值至少是前者的三倍,那么这个事情如何数学化呢。首先我们明显可以看到,在离散情况下,二状态符号是传递信息的最小单位,只有一个状态的符号不能传递信息。所以,我们可以规定二状态符号是信息传递的单位符号,价值记为1。

那么这个问题就变成了一个n状态符号(n > 2)所表示的状态需要几个二状态符号表示?由于m个二状态符号能表示$2^m$种状态,所以问题变成了求解$n=2^m$,得$m=log_2n$,因此我们得到第一个定量结果:

二状态符号是传递信息的最小单位,设为价值1,n状态符号的价值为$log_2n$。

由此可以知道,上文中十状态符号的价值是$log_210\approx3.32$,即3.32元(在正反概率皆为1/2时)。但是由于受到离散化限制,需要取个整,因此那个符号最大收益就是3元。

1.5 不确定性的量化

相比于可表示状态数,不确定性的量化稍微困难一些。具体来说,我们是要做这么一件事:对于一个有N种结果的随机变量X,在概率分布函数$P(X)$已知的情况下,寻找一个泛函$H(X)$(不要纠结于这个名词,这里可以简单理解为以函数为变量的函数),使得$H(X)$满足如下条件:

  1. 如果X是确定性事件(即X的结果是固定的),则$H(X)=0$
  2. $P(X)$越随机,$H(P)$越大
  3. $H(X)$最大为1,此时随机变量随机性最大

在论文中,香农给出了这样一个函数: $$ H(X)=-\sum_{i=1}^Np_i(X)log(p_i(X)) $$ 这就是大名鼎鼎的信息熵,今天普遍用来度量随机事件的不确定性。

回到上面的例子,可以看到$p=0$或$p=1$时,信息熵均为0,因此此时信息符号没有消除任何熵,所以没有价值。而当正反概率各位1/2时,信息熵为:$-2\times0.5\times log(0.5)=1.0$,因此一个二状态符号消除了1.0的熵(同时很容易证明,对应这个游戏,此时熵最大)。而对于$p=0.8$,信息熵为$-0.8log(0.8)-0.2log(0.2)\approx0.7219$,所以一个二状态符号消除了约0.72的不确定性,因此价值没有前者高。

综上,我们可以得到如下结论:

信息传递中,一个信息符号的价值,取决于可表示状态数及可以消除的系统不确定性。其中可表示状态数以二状态符号为单位1,n状态符号价值是二状态符号的$log_2n$倍,不确定性由信息熵度量,消除的不确定性越高则价值越高。

以上是这篇论文要传递的最核心的内容,其余部分基本都是基于这点展开的。下面利用上文总结的点,对论文的一些关键内容做一个简要的解读。

2 对论文关键点的解读

整篇《A Mathematical Theory of Communication》分为两大部分,前半部分是离散信号通信相关的数学理论,后半部分是连续信号通信的数学理论。其中连续信号是将信号看做离散信号的极限情况进行分析,用到了较多的数学技巧,所以相对艰涩,不过其目的可以看做是将离散信号的各种分析推广到连续的情况,因此这里只解读离散部分,理解了离散部分,连续信号部分可以类比理解。

2.1 无噪信道容量(capacity)的数学表示

论文的第一部分是对无噪信道容量的数学化。首先论文对通信的定义是接收端对发送端符号流的还原,所谓无噪信道就是接收端可以准确无误重现发送端符号流的信道,也称作理想信道。

对于无噪信道,信道容量即是单位时间内传输的符号流所能表示的状态数的上限的对数。这里我们以1秒为一个单位时间。

举个几个例子:

  • 一个信道一秒传输一个二状态符号,由于一个二状态符号只能表示两种状态,所以一秒传递的符号最多表示两个状态,$log2=1$(后面如果底数为2均省略),信道容量为1。
  • 一个信道一秒传输一个十状态符号,$log10\approx3.32$,信道容量为3.32。
  • 一个信道一秒传递十个二进制状态符号,十个二进制状态符号可以表示1024种状态,$log1024=10$,所以信道容量为10。

可以看到,这里信道容量的量化和上文中对可表示状态数的量化是一回事,只是把一个符号可表示状态数换成了单位时间内传输的符号可表示状态数。

信道容量定义了一个信道单位时间内所能传输的最大信息价值

注意我们上面的计算方式有一定局限,因为我们假设了符号在不同状态下所占用时间一致,但实际中可能并不是,例如摩尔斯电码中,“划”比“点”占用时间要长。论文中给出了计算信道容量的一个通用数学公式: $$ C=\lim_{T->\infty}\frac{logN(T)}{T} $$ 其中$T$是时间,$N(T)$表示在$T$时间内传输的符号流可以表示的最大状态数。

例如对上面例子中第一个,带入公式可得$C=\lim_{T->\infty}\frac{Tlog2}{T}=log2=1$ ,对第三个$C=\lim_{T->\infty}\frac{Tlog1024}{T}=10log2=10$。

当符号的不同状态占用时间不同时,需要求解一个递推方程。

假设我们一个符号有n种状态,占用时间分别为$t_1,t_2,...,t_n$,由定义可以得到如下递推式: $$ N(T)=N(T-t_1)+N(T-t_2)+...+N(T-t_n) $$ 根据数学知识可以知道这个式子的解是 $$ C=logX_0 $$ 其中$X_0$是特征方程$X^{-t_1}+X^{-t_2}+...+X^{-t_n}=1$的最大实根。

另外论文中还给出了一种通过把通信看成状态机的视角,然后求行列式方程求解信道容量的方法。由于目的一致,这里不再赘述。

2.2 信源的数学表示

上文的信道容量表示的是一个信道理论上能在单位时间内传输的最大信息价值,要达到这个上限,还需要信息编码本身价值最大化。香农接着用很大篇幅来对信息源及信息流编码的价值进行数学化。

回顾一下之前对熵的定义,可以知道熵可以评价一个随机分布函数的不确定性。而一段符号流,也可以看做背后服从一个联合概率分布,这个联合概率分布可以看做是信源的既有特征。因此熵可以用于评价信源的不确定性,论文告诉我们熵越大的信源信息价值越大。

且慢!上面明明说过,信息符号的价值取决于消除的不确定性,这和信源的不确定性有什么关系?背后的秘密在于,当所面对的情况不是完全随机,即熵不是1.0时,我们可以通过重新编码信源,提高符号价值,从而逼近信道最大价值

还是以上面掷硬币举例,假设正面概率0.8,反面概率0.2的情况。如果我们传输二状态符号,0表示正面,1表示反面,可以知道一个符号值1元。

那么我们有没有办法让符号更值钱?因为理论上一个二状态符号可以消除1.0的熵(在正反各0.5的情况下),但这里熵只有0.72,所以我们貌似亏了。有一种思路是这样的:我们不再一个一个编码,而是对两次掷硬币成组编码。因为正面出现概率远大于反面,所以两次掷硬币四种组合的概率也不同,我们用较短的编码表示较大概率出现的情况,用较长的编码表示较小概率的情况,感觉上可以提高每个符号的价值。

具体我们可以这么做:

正正(0.64) - 0,正反(0.16) - 10,反正(0.16) - 110,反反(0.04) - 111

括号中为概率。注意,以上编码方式可以保证在解析信息流时不会出现歧义。可以算一下,这种编码方式,平均表示两次掷硬币所需的平均符号数量是$0.64\times1+0.16\times2+0.16\times3+0.04\times3=1.56$。因此我们可以平均用1.56个二状态符号赚2元,平均一个符号现在价值1.28元。我们通过重新编码把一个符号的价值提高了!

再来算一下这种编码下信源的熵,此时信源出现0的概率是$0.64+0.16\times0.5+0.16\times0.33=0.7728$,出现1的概率是$0.16\times0.5+0.16\times0.67+0.04=0.2272$,信源的熵$-0.7728log(0.7728)-0.2272log(0.2272)=0.773$,比原始信息的0.7219提高了。

所以我们得到了如下结论:如果所要传递的信息所服从的联合概率分布的熵不是最大,则有办法通过对信息重新编码,提高信源的熵,从而提高信息符号每个符号的价值,上限是编码使得信源中每个符号出现的概率相等,此时信源的熵为1.0,单个符号价值最大

换个角度看,我们上面用平均1.56个二状态符号准确重现了之前两个二状态符号(正反两种情况,所以一次掷硬币相当于一个二状态符号)的信息,等于把用于表示同等信息的符号流长度变短了,这就是数据压缩的原理。也就是说,如果一段符号的联合概率分布的熵不是最大(也称作存在冗余),则总有办法通过重新编码,使得用更短的符号流表示同等信息,此时单个符号价值变大,重新编码后的信息流熵也变大

2.3 自然语言熵的近似估计

上面两节可以说就是香农在论文中接下来一大部分所要传递的内容。不过论文中,香农还给出了自然语言中熵的近似估计方式,我们来看一下。

首先我们知道,如果能得到一种语言的联合概率分布,那么就可以直接算出熵,而对自然语言这是不可能的。所以我们只能以某种方式去逼近自然语言真实的联合概率分布。

以英文为例,为了简单我们假设英文只由26个小写英文字母组成,不考虑大写、分隔符及标点。那么,由弱及强可以有如下逼近方式:

  1. 每个位置都是独立的平均分布,即每个位置每个符号以1/26的等概率出现
  2. 每个位置都是独立的,但出现哪个字符的概率按照对真实英文的统计频率出现,例如e出现的概率大于x。
  3. 每个位置出现各个字符的概率,取决于前一个字符及其条件概率
  4. 每个位置出现各个字符的概率,取决于前两个字符及其条件概率
  5. ……

这个列表可以无限延伸下去,其中越后面的逼近方式越接近真实的联合概率分布。这种方式相当于把自然语言看成一个马尔科夫过程,这是随机过程和自然语言处理中一个非常重要的模型,香农的论文也使用了这个模型来表述,鉴于关于马尔科夫过程的资料非常丰富,这里不再赘述。

需要注意的是,不同近似模型下算出的熵可能非常不一样,例如01010101……这种语言,即0和1交替出现,如果用近似2,则算出熵为1.0,即完全随机,但如果用近似3,则熵为0,即完全没有信息量。因此如果近似过程如果不够强,可能得出非常荒谬的结论。

在经过一系列探讨后,香农给出并证明了一个非常重要的结论:

设一个语言有n个字符,每个字符出现的概率为$p_i$,N是一个正整数,令$p=p_1^{p_1N}p=p_2^{p_2N}...p=p_n^{p_nN}$,当N足够大时,$\frac{logp^{-1}}{N}$可以以任意精度逼近真实的熵。

原文使用了极限语言描述,更加严格,我这里给出的是更口语化的描述。

上面给出了一种近似计算自然语言熵的方式,但是并没有定量给出在精度确定下N需要多大。

2.4 有噪信道的数学表示

上面考虑的所有情况都假设信道是完全可靠的,即接收端完美复现发送端的符号流。但现实中信道往往都是会出错的,即是一个有噪信道。香农在离散信息数学表示的最后部分讨论了有噪信道下通信的数学表示。

回到掷硬币的例子,假设我们用二状态符号传递信息,正反面概率各位0.5,已经知道在使用无噪信道时,每个符号值1元。现在我们假设这个信道并不是完美的,传输每个符号时,都有1%的可能性出错,即0变成1或1变成0,此时每个符号值多少钱?显然,如果符号出错,则我们会赔掉1块钱。也就是从统计意义上说,平均每玩一次,收益期望变为$1\times0.99+(-1)\times0.01=0.98$,所以现在每个符号值0.98元。

可以看到,噪声的存在使得信息符号的价值变低了。那么如何量化这个种噪声导致的损失呢?

直觉上,当我们接收到一个字符时,对原始字符越不确定,这个损失越大。香农在论文中引入了条件熵来量化这个损失。条件熵定义如下:如果接收到字符Y,则原字符X的条件概率分布函数的熵即为X对Y的条件熵。即: $$ H_Y(X)=-\sum_{i,j} P(X=i,Y=j)log(P(X=i|Y=j)) $$ 在这个例子中,条件熵为$-0.5\times0.99\times log(0.99)-0.5\times0.01\times log(0.01)-0.5\times0.01\times log(0.99)-0.5\times0.01\times log(0.01)\approx 0.08$

,这就是上述有噪信道单个字符损失的量化。

于是,对于有噪信道,其容量上限是: $$ C=H(X)-H_Y(X) $$ 那么有噪信道既然存在传输错误,还能用吗?当然是可以的,毕竟我们现实中用的信道都是有噪信道。在接下来,香农在论文中证明了一个非常让人吃惊的反直觉结论:

如果不考虑传输速率,总可以找到一种编码方式使得有噪信道传输信息的错误概率任意小。

不过论文中只从数学上证明了存在这样的编码方式,但并没有给出如何构造这样的编码。但是现实中我们经常用到的如奇偶校验码就是用来对抗有噪信道错误的方式。当然,错误概率降的越低,传输速率也会越慢。

原文中在这里给出了离散信道容量的基本原理,这个原理非常重要:

设离散信道容量为C,信源每秒发送符号的熵为H,如果$H\le C$,则一定存在某种编码方式,使得以任意小的出错概率传递信息,如果$H\gt C$,则无法通过任何编码方式将出错概率缩减至任意小。

上面这个结论可以说奠定了现代通信理论的基础。

论文关于离散通信理论的讨论到此为止了,后面部分是将离散情况下各种讨论推广到连续信号条件下。整体上用到的数学技巧较多,但本质要表述的东西和上面是类似的,我这里就不再分析了,有兴趣的可以自行阅读。

3 总结

下面总结一下本文的重要结论:

  1. 信息传递中,一个信息符号的价值,取决于可表示状态数及可以消除的系统不确定性。其中可表示状态数以二状态符号为单位1,n状态符号价值是二状态符号的$log_2n$倍,不确定性由信息熵度量,消除的不确定性越高则价值越高
  2. 信道容量定义了一个信道单位时间内所能传输的最大信息价值
  3. 如果一段符号的联合概率分布的熵不是最大(也称作存在冗余),则总有办法通过重新编码,使得用更短的符号流表示同等信息,此时单个符号价值变大,重新编码后的信息流熵也变大
  4. 如果不考虑传输速率,总可以找到一种编码方式使得有噪信道传输信息的错误概率任意小
  5. 设离散信道容量为C,信源每秒发送符号的熵为H,如果$H\le C$,则一定存在某种编码方式,使得以任意小的出错概率传递信息,如果$H\gt C$,则无法通过任何编码方式将出错概率缩减至任意小