香农说要有熵信息时代由此开启.docx
《香农说要有熵信息时代由此开启.docx》由会员分享,可在线阅读,更多相关《香农说要有熵信息时代由此开启.docx(16页珍藏版)》请在冰点文库上搜索。
香农说要有熵信息时代由此开启
香农说,要有熵。
信息时代由此开启……
作者:
月宝、晓桦
2016年四月三十日是克劳德·艾尔伍德·香农(ClaudeElwoodShannon)的一百周年诞辰。
虽然香农被学术届尊为信息时代之父,听说过这位科学巨人名字的想必比知道宋仲基的人少得多。
不过不管你们信不信,要是没有香农,到今天咱们应该还没有见过手机或Internet,也没有用过微信或Facebook,更不能在网上看韩剧。
香农是美国数学家、信息论的创始人。
1948年,香农发表了《通信的数学理论》文章,提出了信息熵的概念,并创建了信息论。
这篇文章奠定了香农“信息论之父”的地位。
后来,香农在1949年继续发表了《噪声下的通信》。
几十年来,人类科技在数字化、智能化、网络化等的推动下经历了一波又一波通信、信息革命。
数十年之后,在信息流、物质流的社会中,香农的论著依然闪烁着智慧之光,并将照耀人类社会今后的数个世纪。
在学术圈子里,人们往往对香农高山仰止。
南加州大学(UniversityofSouthernCalifornia)电子工程系教授巴特·嗑死磕(BartKosko)说:
爱因斯坦相对论之革命性在于它颠覆了之前的牛顿力学,而香农信息论之革命性在于它前无古人——香农对信息的认知开人类之先河,没有什么挡在前面需要被颠覆的;香农提出了全新的数学工具,就是所谓的信息论,并用这个工具回答了人类从未思考过的问题。
在这个意义上,香农的发现像牛顿的引力定律一样基本。
克劳德·艾尔伍德·香农(ClaudeElwoodShannon),1916年4月30日—2001年2月26日。
1948年,香农(ClaudeShannon)在贝尔实验室发表论文《通信的数学理论》。
文章中提出的数学工具构成了信息论的骨架。
香农证明了信源编码的极限是信源的熵,信道编码的极限则是信道容量。
倚天剑一出,天下皆惊。
而为达到香农预测的信道编码的极限——信道容量,人类却花费了半个世纪挣扎。
本篇文章试图用最少的数学科普一下信息论里最基础的概念——熵(entropy)。
“二十个问题”游戏
先从一个貌似不相干的西方曾经流行的游戏,“二十个问题”(thetwenty-questiongame)说起。
游戏是这样的。
俺心里想一样东西,你可以问俺二十个问题,然后猜俺心里想的东西。
你的问题必须是“是不是”这种形式的。
比如,这个东西是不是可以放进冰箱里?
这个东西是不是活的?
这个东西是不是能吃?
诸如此类。
对于你问的每一个问题,俺必须如实地回答“是”或者“不是”。
你在二十个问题之内猜到了我想的东西就算赢。
这个二十个问题的游戏曾经很受欢迎,还被做成过电子玩具。
这个游戏的关键是在于如何有效地问你的问题。
如果你问“明天是不是下雨”,那你肯定脑子进水了,可以不用往下看了。
如果你第一个问题问的是“这东西是不是iPhone6”,这样的问法显然也效率不高,因为俺一旦说“NO”,你只从大量的可能性中排除了一种可能,还是要面对剩下巨大的猜测空间。
这个游戏可以大致等价于这样一个数字游戏。
假设M是个大于1的正整数,俺俩在玩游戏之前就商议确定好。
俺在1到M之间任意想一个整数,你的任务是用最少的“是不是”形式的问题问出这个数是多少。
对于这个数字版的“二十个问题”游戏,聪明的宝宝都会发现类似这样的结论:
M的数值越大,需要的问题越多。
但爱钻研的同学可能会想到另一个问题:
对于一个给定的问问题策略,所需问题的“多”或“少”又是用什么来衡量的呢?
比方说,M=8,而你的问法是依次问如下问题:
“这个数是不是1”,“这个数是不是2”,“这个数是不是3”,一直到“这个数是不是7”(如果问完“这个数是不是7”你觉得还需要问“这个数是不是8”的话,那请你去看韩剧吧)。
在这种情况下,如果俺想的数字是1,你只需要一个问题就可以知道答案;而如果俺想的数字是8,你必须在问完7个问题之后才能知道答案。
换句话说,即使问问题的策略确定,因为俺心里那个神秘数字的不确定性,你所需要的问题数目也是不确定的。
因此我们需要把这个数字版“二十个问题”游戏更准确地描述出来,或者说,把在什么意义上“最少”定义出来。
随机变量
随机变量描述的是一个随机实验可能出现的结果以及每种可能结果的可能性,也就是概率。
先看一个例子。
例[老千掷硬币]假设某老千每次投掷硬币的结果有1/3可能性出正面,2/3的可能性出反面。
那么掷一次硬币就是一个随机实验,掷硬币的结果就是一个随机变量,我们这里记作大写的X。
如果把正面记作1,反面记作0,那么这个随机变量X可以通过一个函数P(x)来描述:
函数的变量(小写的)x的取值范围是集合{0,1},这个集合此后记作S;函数在0和1的取值分别为:
P
(1)=1/3,P(0)=2/3。
从这个例子可以看出,一个随机变量X无非是通过在某个集合S上定义的一个函数P(x)来描述的,而这个函数不能取负值,而且必须在对其变量x求和的时候结果为1(在老千掷硬币的例子中即:
P(0)+P
(1)=1)。
这个函数通常被称为随机变量X的概率分布。
当然,同样是掷硬币,可以定义出很多不同的随机变量(即不同的概率分布函数P(x))来。
普通人掷硬币对应的随机变量基本就是P(0)=P
(1)=1/2。
赌神掷硬币对应的随机变量可能是P(0)=1,P
(1)=0。
生活中的随机变量比比皆是。
比如,在掷骰子的时候,骰子掷出的结果这个随机变量对应于一个定义在S={1,2,...,6}上的概率分布函数P(x),通常认为P
(1)=P
(2)=...=P(6)=1/6。
再比如明天会不会下雨(天气预报不准的啦),会有几个人给俺这篇吐血之作点赞或转发(不晓得多少人更喜欢韩剧的啦)这些不确定的事情里都可以定义出随机变量来。
记得不知道哪一位伟人曾经说过,“随机变量是到处都有的。
对于我们的脑袋,不是缺少随机变量,而是缺少发现。
”在前面说的那个数字版“二十个问题”游戏中,俺心里想的神秘数字对你来说也是一个随机变量,它的概率分布P(x)是定义在S={1,2,...,M}上的函数。
如果我选数字是“完全随机的”,那么,这个函数就是P
(1)=P
(2)=...=P(M)=1/M。
这种分布通常被称为均匀分布。
当然,取决于俺按什么偏好选数字,这个函数也可以取其他形式:
如果俺就是喜欢2,也许俺会以更高的概率取2。
随机变量的均值假设有个随机变量X,它的取值范围S={1,2,…,M},它的概率分布函数是某个定义在S上的函数P(x)。
那么这个随机变量的均值(更文化点的说法叫数学期望值)就是这样一个东东:
1*P
(1)+2*P
(2)+3*P(3)+…+M*P(M).在上面老千掷硬币的例子中,随机变量X的均值就是1*(1/3)+0*(2/3)=1/3。
简单吧。
很多同学可能都有直觉的认识,能感觉到如果把产生这个随机变量X的随机实验做很多次,把得到的数字取平均,那么这个平均数差不多就是X的均值。
这个概念,叫做大数定理,跟俺要讲的熵有着本质的联系。
独立随机变量
很多时候俺们关心的不止一个随机变量,而是很多随机变量。
比如,俺们同时关心两个随机变量X和Y,X的取值范围是{1,2},Y的取值范围是{1,2,3}。
那么俺们可以把这两个随机变量看作一个随机变量对,写作(X,Y),而把它的取值范围理解为所有可能的(X,Y)取值的组合,也就是{(1,1),(1,2),(1,3),(2,1),(2,2),(2,3)}。
把这个集合叫作S,那么这对随机变量就是通过一个定义在S上的概率分布函数P(x,y)来描述的。
当这个随机变量对的分布满足P(x,y)=P(x)P(y)的时候,俺们就称这两个随机变量是相互独立的。
P(0,0)=P(0)P(0)=(2/3)(2/3)=4/9P(0,1)=P(0)P
(1)=(2/3)(1/3)=2/9P(1,0)=P
(1)P(0)=(1/3)(2/3)=2/9P(1,1)=P
(1)P
(1)=(1/3)(1/3)=1/9独立随机变量的概念当然可以推广到更多的随机变量上。
如果有n个随机变量,它们的取值无非就对应了一个长度为n的序列。
所有这样序列的集合就是这组随机变量的取值范围。
如果这些随机变量是相互独立的,那么每个序列出现的概率无非就是把这个序列中每个数出现的概率乘在一起。
比如,上面的老千连续掷了10次硬币,那么出现1101011110的概率就是(1/3)(1/3)(2/3)(1/3)(2/3)(1/3)(1/3)(1/3)(1/3)(2/3)=(1/3)^7*(2/3)^3均值和大数定理
大数定理的英文是thelawsoflargenumber,它的中文翻译通常是“大数定律”而不是大数定理。
定律或是英文里的law都是指不需要证明但可以被验证的理论假设。
比如牛顿的万有引力定律。
从数学上说,不需要证明就被接受的假设被认为是公理。
但是这个大数定理并非公理,它是被严格证明出来的(证明也不复杂,只要用马尔可夫不等式或切比晒夫不等式就行了),因此准确的数学语言应该叫它“定理”。
管他叫“定律”会让人以为这个东东就是假设出来的公理,从而产生歧义,当年也不知道谁这么没涵养管它叫“law”。
所以,不管你们服不服,俺都要管它叫大数定理。
大数定理大概说了这样一个意思。
假设有某个随机实验会产生一个随机变量X。
如果你重复做这个随机实验n次,你就会得到一个随机变量序列X1,X2,X3,…,Xn。
这里假定这些随机变量相互独立(即这些随机实验互不影响)而且n是个很大的数(比如,一万,十万,百万),那么把这n个数加起来除以n(即取平均),得到的数(即(X1+X2+…+Xn)/n)几乎总是很接近随机变量X的均值。
咱们用老千掷硬币的例子先看看大数定理到底说了些啥子嘛。
假设那个老千掷了n次硬币,那么他就得到了n个在{0,1}里取值的数。
因为这n个数都是随机的,这n个数的均值当然也是个随机变量,就是说也有一个概率分布函数,有一定的不确定性。
大数定理告诉俺们,当n很大的时候,这n个数的平均值“几乎总是很接近”1/3。
“几乎总是”和“很接近”是可以在数学上严格定义的,套一下切比晒夫不等式得出下面这些“至少有”的结论:
当n=1000时,至少有91.1%的概率这个平均值很接近1/3。
当n=10000时,至少有99.1%的概率这个平均值很接近1/3。
当n=100000时,至少有99.9%的概率这个平均值很接近1/3。
如果把“很接近1/3”理解为跟1/3相差不到0.02,那么:
当n=1000时,至少有44.4%的概率这个平均值很接近1/3。
当n=10000时,至少有94.4%的概率这个平均值很接近1/3。
当n=100000时,至少有99.4%的概率这个平均值很接近1/3。
当n=1000000时,至少有99.9%的概率这个平均值很接近1/3。
现在展开你想象的翅膀,你应该看到当n变成无穷大的时候,这个平均值就不再是“几乎总是很接近1/3”,而是“就是1/3”了!
老千掷出的序列当然是随机的、不确定的、没有规律的。
这个序列的平均数虽然也在1/3周围随机跳动,但却随着n的增大越发确定起来。
当n很小、她就在你跟前的时候,变化多端、捉摸不定的她让你无法看清;当n增大的时候,她渐行渐远,但她在风中颤动的身影却在你记忆的相机里慢慢聚焦,越来越清晰;直到她消逝在无限的远方,她竟定格成一幅永恒而又无比真切的画面……“二十个问题”游戏的准确规则及特例
用概率论武装一下之后,同学们应该已经认识到,在“二十个问题”游戏中俺心里想的神秘数字其实就是一个随机变量X。
我们可以假设它的取值范围S={1,2,…,M}和概率分布函数P(x)都已知。
当然在实际情况下我们未必真知道P(x),但往往可以大致估计这个函数。
如果对这个分布函数我们一无所知,我们不妨认为P(x)是个均匀分布。
对于任意一个给定的问问题策略,如果俺心里的神秘数字是x,我们把所需的问题个数记作L(x)。
比如M=8,而我们用前面提到的那个从1问到7的策略问问题,我们就会得到:
L
(1)=1,L
(2)=2,L(3)=3,L(4)=4,L(5)=5,L(6)=6,L(7)=7,L(8)=7。
(对,L(8)=7,俺没敲错。
)因为俺心里想的是个随机变量X,在这个策略下所需要的问题数目L(X)就也是个随机变量。
这个随机变量L(X)也有一个分布,在知道P(x)的前提下,如果想算也是可以算出来的。
但是俺懒得算它。
既然L(X)是个随机变量,一个最自然的方式定义这个策略所需要的问题个数就是用这个随机变量的均值,或者说用平均所需要的问题个数。
如果你的数字直觉好,应该可以看到,即使不求L(X)的分布,这个随机变量的均值其实就是L
(1)*P
(1)+L
(2)*P
(2)+…+L(M)*P(M).用L(X)的均值定义一个问问题策略所需要的问题个数除了“自然”,还有什么物理意义吗?
当然!
前面的大数定理告诉咱们,如果你用这个策略玩这个游戏很多次,你所用问题个数的平均值“几乎总是很接近”L(X)的均值。
而当你玩了这个游戏无数次之后,你平均每次用的问题数就正好是这个L(X)的均值。
由此可见,如果俺们准备玩这个游戏很多次,那么用L(X)的均值定义所需要问题的个数,用金星老师的话说就是一个动作两个字:
完美。
至此,已经确定这个“二十个问题”游戏的准确规则,即:
你要设计一种问问题的策略,当用这个策略跟俺玩很多次(更准确的说,无数次)这个游戏之后,平均每次用的问题个数要越少越好!
换句话说,我们希望寻找一个最好的问问题策略,同时确定最少需要多少个问题(平均意义上)。
其实在一些特殊的情况下,确定最优的问问题策略和最少需要的问题个数并不困难。
考虑这样一个特例:
俺心里的神秘数字X的取值范围是S={1,2,…,8},而且X的概率分布函数是个均匀分布。
那么最优的问问题方法就是所谓的“二分法”:
每问一个问题要把这个神秘数字的可能范围缩减一半。
比如这样的问法:
问题1:
把集合{1,2,…,8}分成左右两份,左边的是{1,2,3,4},右边的是{5,6,7,8}。
然后问:
你想的数是不是在左边啊?
问题2:
根据俺的答案,你可以确定这个神秘数字只剩下四种选择。
你再类似地把四种选择分成左右两份,然后问:
你想的数是不是在左边啊?
问题3:
根据俺的答案,你现在可以确定这个神秘数字只有两种选择,再把它们一个放左边,一个放右边。
你再问:
你想的数是不是在左边啊?
如此问完三个问题,你一定知道了俺的神秘数字。
相信你的直觉也应该告诉你,这就是最优问法!
那么在这个例子里,所需的最少问题个数就是3。
从咱们用每个问题把猜测空间一切两半的问法,同学们应该也已经认识到,这里得出的最少问题数3正是因为8=2^3,或者说,2=log8.(本文中所有的对数操作均以2为底数)。
在这个例子中有个现象也值得注意一下:
不管俺心里想的是个什么数字,使用二分法所需的问题数字都是3,一个完全确定,毫无随机性的数字。
这个特例显然可以推广:
如果神秘数字X的概率分布函数是在2^K种可能性上的均匀分布,那么“二十个问题”游戏的最优策略可以通过二分法实现;在这种策略下,不论神秘数字是什么,问出它所需要的问题数都是K,因此所需要的平均问题数也是K。
当然,这个二分法只适合于这样的特例,当神秘数字的可能性总数不是2的多少次方的时候,或者当神秘数字的分布不均匀的时候,这种问法显然不是最优的。
这个问题任意形式的最优解法曾让一个叫大卫.霍夫曼(DavidHuffman)的年轻学生在1951年一夜成名。
不过,那已经是在香农提出信息论三年之后了。
在香农独特的视角里,这个问题并不至关重要。
在想象中,当香农看到满屋子小朋友们叽叽喳喳地玩这个游戏的时候,他笑了笑,说:
你们慢慢玩吧。
然后他点起一支烟,凝视着窗外的远方。
在落霞与孤鹜齐飞的秋色里,他看到了这个游戏的另一种设计。
“二十个问题”游戏攒着玩和数据压缩
既然用L(X)的均值定义所需要问题的个数依赖于把这“二十个问题”游戏玩很多次,那么考虑一下这个游戏的一个变种,就是把这很多次游戏攒起来一起玩:
俺拿出一张很长很长的纸条,然后随机想n个相互独立的神秘数字,X1,X2,…,Xn(每个数字的分布都是同一个定义在S={1,2,…,M}上的概率分布函数,P(x))。
俺把这些数字一个一个地写到纸条上。
这里n很大很大,所以纸条很长很长。
然后你再来问俺“是不是”台或一百台电脑来。
你问俺的问题要是计算太复杂,俺也可以去搬电脑来算。
总之,咱们不用管计算有多复杂,俺俩都有无限的计算能力。
在这个攒着玩的“二十个问题”游戏中,怎样的问问题策略才最优呢?
最优的策略所需要的平均问题数目又是多少呢?
暂且先不讨论这个问题的答案,咱们先审视一下这个新的游戏设计的应用意义吧。
想象一下,俺写在纸条上的序列其实是俺刚写好的长篇小说(俺写下的每一个数其实对应于新华字典里的一个字),又或者俺写在纸条上的序列其实对应于俺长期夜观星象的结果,记录了不为人知的宇宙奥秘(俺写的每个数字都是对观测到的宇宙状态的描述)。
在你问俺问题的时候,俺的回答将是一个长长的由Yes/No组成的序列。
如果把Yes记作1,No记作0,俺的回答其实就是一个0/1组成的序列。
一个可以取0/1两个值的变量,或者一个可以储存0/1两种不同状态的存储单元,就是人们常说的比特(bit)。
所以俺的回答其实就是一个比特序列。
你希望用最少的问题就等同于要求这个比特序列最短,或者说要求用最少的比特数表示俺纸条上的内容。
这个问题其实就是通信中的数据压缩问题!
数据压缩,又叫“信源编码”,大约是干这样一件事。
假设有个信息源,就是一个能不停往外蹦信息的东西,比如一直在想神秘数字的俺,夜观星象的俺,写小说的俺,等等等等。
信息源产生的信息从数学上说就是一个随机变量序列(更有文化的说法叫随机过程)。
这个随机变量序列可以有很多种形式,最简单形式就是其中的随机变量都相互独立而且服从相同的分布。
对这个信息源进行数据压缩包括了两个环节,编码和解码。
编码就是把从信息源蹦出来的随机序列表示成比特序列,而且越短越好;解码就是从比特序列中还原出信息源蹦出来的随机序列。
数据压缩可以大幅度降低数据存储和通讯需要的资源,已经是现代通信技术的一个重要组成部分。
现在回到“二十个问题”游戏。
如果这个游戏一个一个分开玩,其实就是在数据压缩的时候,对信息源里蹦出的每个随机变量单独做压缩。
如果这个游戏攒n个一起玩,其实就是对随机序列中的n个随机变量同时进行压缩。
显然,对每个随机变量单独进行压缩一定不会比对整个随机序列同时做压缩效率更高(这里的效率是用平均每个随机变量压缩后的比特数来衡量的,比特数越低,效率越高)。
这里的道理是这样的:
比如俺俩攒n个“二十个问题”游戏一起玩,但你设计问题的时候,每个问题只是针对序列中的一个随机变量,而不是针对整个序列。
这样的问问题策略显然等同于把每个游戏分开玩。
也就是说,这个游戏一个一个分别玩可以认为是攒起来一起玩的一种特例。
因而分别玩能达到的效率,攒起来玩也可以达到。
因为同样的道理,如果这个游戏攒2n个一起玩,其效率也一定不比攒n个一起玩低。
也就是说,为了提高效率,n应该越大越好。
那么攒起来玩的效率到底最高可以达到多少呢?
或者说,对一个给定的信息源,平均每个蹦出来的随机变量最少需要多少个比特来表示呢?
这个数字通常跟序列的长度n相关,而且对于任意一个给定的n,即使俺们能够确定最优的压缩方法,精确地确定这个数字也是一件很棘手的事。
不过既然俺们已经认识到n越大越好,那不妨考虑n取无穷大吧。
当n取无穷大时,如果俺们能够计算出信息源里平均每个蹦出的随机变量最少需要多少比特来表示,这个数字不仅标记了最优的压缩效率,它同时还有着更深刻的物理意义:
它跟序列的长度n无关,也跟编码方法无关;换言之,这个比特数只取决于信息源本身(即随机变量X或其分布P(x))。
因为这个比特数是由最优编码/解码方法实现的,它同时说明了两件事:
1.只要解码端接收到的平均比特数不到这个数字(平均到每个随机变量上),不论用什么编码/解码方法都一定无法重建信息源里蹦出的随机序列。
2.只要解码端接收到的平均比特数超过这个数字,就一定有一种编码/解码方法可以使解码端重建这个序列。
这就是说,在平均意义上,你一定需要这么多比特来表达信息源里蹦出的每一个随机变量,而且只要这么多比特就够了!
因此,这个比特数实际上就标注了这个信息源在以什么样的“速率”释放“信息”,或者说标注了这个信息源里蹦出的每个随机变量平均包涵了多少“信息”!
下面俺们就来看看是否可以导出这个最小比特数。
最小比特数
还是二十个问题攒着玩吧。
不过这次俺也不去想什么随机数了。
俺就把之前例子里的那个老千找来,让他躲在俺身后不停地掷硬币。
俺就把他掷出的0/1结果写在纸条上。
等俺写完n个数的时候,就让你开始问问题。
前面说过,这无非就是把这个老千掷硬币的结果当作一个信息源,对这个信息源做压缩。
因为n很大很大,让我们先回顾一下大数定理的情怀:
老千掷出的硬币序列的平均值几乎总是很接近1/3。
根据俺之前对这句话不辞劳苦的解释,这句话也可以换一种说法,而且这种说法很重要(重要的事情说三遍!
)老千掷出的序列几乎可以肯定有差不多n/3个1和2n/3个0!
老千掷出的序列几乎可以肯定有差不多n/3个1和2n/3个0!
老千掷出的序列几乎可以肯定有差不多n/3个1和2n/3个0!
这个重要结论很容易推广到掷硬币之外的任意随机变量:
假设随机变量X是通过一个在集合S={1,2,…,M}上定义的概率分布函数P(x)描述的。
那么当俺们产生n个相互独立的这样的随机变量的时候,如果n是个很大的数字而a是S中的任意一个数,那么:
产生的随机序列几乎可以肯定有差不多n*P(a)个a!
产生的随机序列几乎可以肯定有差不多n*P(a)个a!
产生的随机序列几乎可以肯定有差不多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组成,而这个序列中的所有随机变量又是相互独立的,那么,每个典型序列被掷出来的概率“差不多”就是(