第四百四十一章香农的信息熵

章节错误,点此举报(免注册),举报后维护人员会在两分钟内校正章节内容,请耐心等待,并刷新页面。

因为n很大很大，让我们先回顾一下大数定理的情怀：

老千掷出的硬币序列的平均值几乎总是很接近1/3。

根据俺之前对这句话不辞劳苦的解释，这句话也可以换一种说法，而且这种说法很重要（重要的事情说三遍！）

老千掷出的序列几乎可以肯定有差不多n/3个1和2n/3个0！

同学们再好好体会一下俺极其考究、极负责任、极具情怀的用词：“几乎可以肯定”和“差不多”。

这个重要结论很容易推广到掷硬币之外的任意随机变量：假设随机变量X是通过一个在集合S={1，2，…，M}上定义的概率分布函数P(x)描述的。那么当俺们产生n个相互独立的这样的随机变量的时候，如果n是个很大的数字而a是S中的任意一个数，那么：

产生的随机序列几乎可以肯定有差不多n*P(a)个a！

也就是说，虽然得到的序列本身是随机的，不确定的，但是当n很大的时候，这个序列的组成“几乎”是“差不多确定的”！而且可以想象，当n无穷大的时候，这里的“几乎”和“差不多”都可以删去！

在老千掷硬币这个例子里，如果一个硬币的序列有差不多n/3个1和2n/3个0，那么俺就管这种序列叫“典型序列”。在更普遍的意义上，相对于一个在S上定义的分布P(x)，一个由S里的数字组成的长度为n的序列俺也管它叫典型序列，如果S里的每个数a在这个序列中出现了差不多n*P(a)次。在典型序列定义中的“差不多”是差多少？呵呵，跟前面的逻辑一样，如果n很大，差不多就是差一丁点，如果n无穷大，差不多可以是“一点不差”！

那么上面重要的说了三遍的话用这个语言重新说，就是：

老千掷出的序列几乎可以肯定是典型的！

当n无穷大的时候，这句话里的“几乎”当然也是可以删掉的。也就是说，在n无穷大的时候，不典型的序列根本不会出现！那么，你问问题的时候岂不是只需要针对典型序列问问题就行了？

正是如此！

那咱们看看典型序列一共有多少个。把这个要算的数记作T。

首先注意一下每个典型序列有多大的概率被老千掷出来。因为每个典型序列“差不多”由n/3个1和2n/3个0组成，而这个序列中的所有随机变量又是相互独立的，那么，每个典型序列被掷出来的概率“差不多”就是(1/3)^(n/3)*(2/3)^(2n/3)。不知道同学们注意到没有，每个典型序列被掷出来的概率“差不多”都是这个数。同时注意到只有典型序列才可能被掷出来，也就是说，所有典型序列出现的概率之和“差不多”就是1。这样俺们就可以得出，典型序列的数目T“差不多”就是1除以每个典型序列出现的概率，也就是

1/((1/3)^(n/3)*(2/3)^(2n/3))=(1/3)^(-n/3)*(2/3)(-2n/3).

针对这T个序列问问题，就“差不多”等同于俺跟你玩一次这样的“二十个问题”游戏：俺从{1，2，…，T}里取一个数，而且这个数服从均匀分布；然后你问俺“是不是”问题来猜这个数。那么你最少需要多少问题呢？现在回头找到之前让你们用红笔圈出的结论：最优解是二分法；你最少需要的问题总数是logT！而且不管俺取的是哪个数，你都需要这么多问题！

认真的同学可能会叫板说，哎，这个T也未必是2的整数次方啊，二分法能用吗？！嗯，这个问题不错。但可以这样想，只要把n弄得足够大，总可以让T非常接近2的某个整数次方。而且，即使T真的不是2的整数次方，还可以换一个角度得到我们后面要得到的结论，比如，一定存在一个整数K使得T是在2^K和2^(K+1)之间......总之，当n无穷大的时候，凌乱的世界都变整齐了，这个问题不再是问题了。

这个最少问题数logT是用来问这个长度为n的硬币序列的。平均到每次掷硬币，平均需要的最少问题数就是（logT）/n。稍微整理一下这个表达式就应该可以看到，这个数字正好等于-(1/3)log(1/3)-(2/3)log(2/3)。

这也就是压缩这个“老千掷硬币”信息源所需要的最少比特数。

把这种推演用到任意信息源。如果一个信息源往外蹦的随机变量都独立而且服从同一个定义在S={1，2，…，M}上的分布P(x)，那么以下结论依次成立。

信息源里蹦出的随机序列几乎可以肯定是典型的！

每个典型序列出现的概率差不多就是P(1)^(nP(1))*P(2)^(nP(2))*…*P(M)^(nP(M))!

典型序列的个数T差不多就是P(1)^(-nP(1))*P(2)^(-nP(2))*…*P(M)^(-nP(M))!

压缩这个信息源蹦出的每个随机变量平均所需要的最少比特数就是(logT)/n！

这个数字(logT)/n就等于：-P(1)logP(1)-P(2)logP(2)-…-P(M)logP(M).

这个数字，就是熵。

从熵的表达式看，熵是通过一个概率分布函数P(x)来定义的。因为概率分布函数P(x)都对应于它所描写的随机变量X，所以俺们也可以认为熵是对随机变量X的某种特性的度量，而把它记作H(X)。从压缩的角度讲，熵值H(X)是对产生随机变量X的信息源编码所需要的平均最小比特数，或随机变量X中固有的平均信息量。

如果随机变量X是在S={1，2，…，M}里取值，那么可以证明，熵值H(X)的取值必定在0和logM之间。当随机变量X在S上均匀分布的时候，H(X)取最大值logM；当X以百分之百的概率取S中的某个数值的时候，H(X)取最小值0。前者对应于“不确定性”最大的X，而后者对应于“不确定性”最小的（即完全可以确定的）X。所以，也可以把熵值H(X)理解为对随机变量X的“不确定性“（或“不可预测性”）的度量。

因此，随机变量所包含的“信息量”和它的“不确定性”其实是同一个概念。一个随机变量越难以确定，它所包含的信息量越多。这种认识对初次接触熵的人来说或许不够自然。但仔细体会一下，确实是有道理的。如果俺想告诉你的事你很容易猜到，或者说你不用问几个问题就能知道，那俺要说的话对你来说就没多少信息量。

在熵的定义里－logP(a)又是什么物理意义呢？当然这个数字可以理解为a编码所需要的比特数（在前面例子里，我们能看到以1/8概率出现的事件，需要用3个比特来编码）。换一个角度理解，－logP(a)可以理解为a的“惊奇度”。一个出现概率极低的事件a，比如世界末日，它一旦出现就会令人非常惊奇，所以对应的－logP(a)就会很大；而如果a出现的概率很大，它的出现就不会太令人吃惊，所以对应的－logP(a)就会很小。因此，熵值H(X)也可以理解为随机变量X的“平均惊奇度”。

用不确定性，信息量，或平均惊奇度来理解熵，都只是给它赋予一个直觉的解释。平均最小编码长度才是对熵的数学理解。但这种理解并不能体现出大数定理在熵的定义里所起的决定性作用以及“二十个问题”游戏必须攒着玩才能实现最短问题数等于熵值的深刻认识。在大数定理的情怀下，熵值H(X)还有另一个数学解释：H(X)是典型序列的总数随序列长度的“翻倍速率”。看，长度为n的典型序列总数T差不多是2^(nH(X))；也就是说，每当序列长度n增加1，T就增大2^(H(X))倍，或者说，翻倍翻了H(X)次。所以把熵理解为典型序列总数的翻倍速率才能真正体现熵的数学本质。当然，这样的理解就离韩剧更加遥远了。

熵，或英文里的entropy，本来源于物理中的热力学，用来描写系统的“混乱度”。香农在定义信息熵的时候借用了这个词。虽然俺经常夜观星象，也能在夜空没有雾霾的时候认出北斗星，但对宇宙、相对论，或是热力学，都一窍不通。所以俺就不试图解释物理熵和信息熵的联系了。

但在通信的范畴，熵是人类第一次对信息有了数学的认识。人类刚刚开始研究数字通信的时候基本就是瞎子摸象，直到1948年香农在贝尔实验室发表了那篇著名的文章，“通信的数学理论”。倚天剑一出，天下皆惊。香农一针见血地指出，通信的问题可以分解成两个的问题，即信源编码和信道编码。信源编码的目的是尽可能高效的表示信息源，即数据压缩；信道编码的目的则是尽可能高效的让数据可靠无误地通过信道。在他1948年的文章里，香农证明了信源编码的极限是信源的熵，而信道编码的极限则是个叫信道容量的东东，标注着信道可以支持的最大通信速率。（信道容量的概念是在熵的基础上的对信息论的进一步发展，故事更长，更精彩，不过俺还是不讲了吧。）香农说，只有当信源的熵低于信道的容量的时候，可靠的通信才可能实现；而且只要在这个条件下，可靠的通信就一定可以实现！香农的证明是存在性证明，就是说，他告诉俺们：反正这事儿一定可以实现，至于怎么实现，你们自己想办法吧。

信源编码的问题很快被香农的追随者和逐步解决。基于算术编码(arithmeticcoding)和LZ编码（Lampel-Zivcoding)的信源编码方法在上世纪七八十年代已经日渐成熟，实现了香农预测的压缩极限并在实践中被广泛采纳。而香农预测的信道编码的极限，信道容量，却花费了人类半个世纪挣扎。业外人士未必了解，对信道编码的研究结晶了人类最高的智慧和前赴后继的努力。然而香农预测的信道容量直到上世纪九十年代中叶才终于被实现。今天我们的手机里也终于承载了香农在1948年的预言！

熵的提出是信息论起点，也是人类对信息认知的开始，而香农在他1948年文章里提出的数学工具正是信息论的骨架。在我们今天生活的信息时代，香农和信息论存在于我们的手机，我们的电脑，我们的电视，我们的蓝光播放器，我们的internet，我们的facebook，我们的韩剧......

大约七十年前，当人们还在黑暗中摸索数字通信的时候，香农说，要有熵。于是，就开启了信息时代。

八哥电影

第四百四十一章 香农的信息熵

第四百四十一章香农的信息熵