vcitym的个人博客分享 http://blog.sciencenet.cn/u/vcitym 中国地质大学(北京)教授

博文

[转载]香农:用一篇论文建立一个学科

已有 2216 次阅读 2021-2-17 08:15 |系统分类:教学心得|文章来源:转载


1948年,当香农终于整理好所有文字,发布他那惊天论文——A Mathematical Theory of Communication(一种通讯的数学理论)——的时候,不知道他是否会知道,自己会在一年后,会和瓦伦·韦弗(Warren Weaver)一道,将A改成The,完成用一篇论文建立一个学科的壮举。

我们身处信息时代,但在享受海量数据带来的便利时,克劳德·香农(Claude Shannon,1916-2001)——信息论的创始人,却鲜为人知。香农是近代最伟大的数学家之一,他毫无疑问是个天才,并且拥有符合所有人刻板印象的,只有天才才能拥有的离谱人生。毕竟只用一篇论文就能建立一个学科的,除了爱因斯坦,还有香农。

小说中才会有的天才

香农1916年出生于密歇根州的一个小镇,自幼崇拜托马斯·爱迪生,经常在家里制作模型飞机、遥控船还有无线电台。后来他才知道,原来爱迪生竟然是自己的远房亲戚。

1932年香农进入密歇根大学,就是在那里,他接触到了乔治·布尔(George Boole,英国数学家,布尔型、布尔代数均得名于他)的理论。大学毕业时,他获得了电子工程和数学两个学士学位,并进入麻省理工学院深造。在那里,他参与了万尼瓦尔·布什(Vannevar Bush)的微分分析机的相关工作。微分分析机是一种由轴承和齿轮构成的机械计算机,正是在那时,他发现布尔代数与这种机械、电路设计,有惊人的联系。于是他发表了自己的硕士论文,《继电器和开关电路的符号分析》(A Symbolic Analysis of Relay and Switching Circuits)。从此,电路设计从依靠灵光一闪的艺术,变成了可以依靠严谨逻辑一步步推导下来的工程。

“这可能是本世纪最重要、最著名的硕士学位论文。”哈佛大学的霍华德·加德纳(Howard Gardner)在后来这样评论这篇论文。不过,即使是这样的成就还远不能称为香农最高光的时刻。

香农在万尼瓦尔·布什的建议下,将他的理论应用于遗传学。当时沃森和克里克还没有弄清楚DNA的结构,但是既然遗传物质必然包含信息,概率一类的东西,为什么不尝试一下呢?在读了所有他能找到的有关遗传学的书后,香农撰写了《理论遗传学的代数》(An Algebra for Theoretical Genetics),用线性代数描述不同遗传性状在遗传中的可能性。以此,就能用线性代数来预测性状是如何代代相传的。不过,这种理论并没有被生物学家大规模使用。但至少,1940年香农以此得到了麻省理工学院的博士学位,和在普林斯顿高等研究院的工作。而在那里,他可以接触到那个时代最闪耀的一批人——阿尔伯特·爱因斯坦、库尔特·哥德尔、冯·诺依曼……

物理学圣地,普林斯顿高等研究院(图片来源:Hanno Rein,Wikipedia)

在这批人的光芒的掩盖之下,即使是当时的香农,也不过是一个初出茅庐的毛头小子。按照香农的说法:“我见过这些人,可是他们没有见过我。”那时信息论已经在他头脑中酝酿。但他失望地发现,在普林斯顿高等研究院中,所有人关心的都是一些量子力学、广义相对论的本质之类的问题,他那些更实用一些的数学问题并没有人关心。

无人关心,再加上二战的爆发,他只在高等研究院待了两个月,就加入了贝尔实验室,在军方的直接领导下研究火控系统和密码学。根据《香农传》(The Bit Player)中,对香农前妻、前女友和妻子三人的采访,可以知道香农是一个帅气且有情调的人。而正是在军方领导的贝尔实验室工作时,他甚至无法维持和第一任妻子的婚姻,可见这段经历让他有多消沉。

不过在贝尔实验室的工作也不是全是坏事,至少他接触到了艾伦·图灵(Alan Turing),并得知了他的“图灵机”。他对此很感兴趣,并经常约在下午茶时间见面,香农还为图灵机补充了一些自己的见解。

按照香农的说法,在贝尔实验室密码学方向的工作,只是为自己提供一个职位,让自己能研究自己真正关心的,有关信息的数学。其实,1945年二战末期,他在贝尔实验室内部密码学相关的备忘录中,就已经有了信息论的雏形。至于为何要等到1948年才整理出完整的论文,他的回答只有一个字:“懒。”

一篇论文建立一个学科

1905年,26岁的爱因斯坦发了四篇论文,建立了三个学科——量子论、统计力学和狭义相对论。43年后的1948年,当年面对爱因斯坦插不上话的香农,在32岁时终于也完成了一篇论文建立一个学科的壮举——A Mathematical Theory of Communication(一种通讯的数学理论)横空出世,其完整性甚至到今天还能作信息论教材使用。一年后,用这篇论文再加上瓦伦·韦弗(Warren Weaver)的科普文章,把A改成The,两人出版了The Mathematical Theory of Communication(通讯的数学理论)。信息论就此诞生。

信息的数量与其内容好坏无关,毕竟所有信息编码转换成信号后,发送时的数量只与其长度有关,而这个长度可以用对数很方便的表示。受约翰·图基(John Tukey,快速傅里叶变化发明者)的启发,香农用信息转换成二进制数字后的二进制数位(binary digit)作为信息的单位,或者将其简称为比特(bit)。这是比特这一词首次公开出现,这个词在接下来大半个世纪的时间里,深刻地改变了整个世界。(以下出现的对数log均以2为底)

但仅仅找到信息的单位还远远不能让香农满足,他想要更深刻的解释。

用一种不太严谨的说法,在他看来,能从随机过程结果的不确定性结果中,让人确定唯一结果的东西才是信息。

比如说,抛出一枚硬币,落地时数字面和花面朝上概率相等。那么在不知道结果前,都不能十足的把握说硬币哪面朝上。但如果知道了硬币数字面朝上的信息,那么就可以确定抛硬币的结果是数字面朝上。如果抛出一枚两边都是数字面的硬币,那么就算不知道结果的信息,也可以确定硬币的数字面朝上。两种抛硬币的问题,前者在确定答案需要信息,而后者不需要。

再加上一些数学概率上的考虑,香农发现玻尔兹曼曾经研究过的物理学概念——熵,很适合用来描述这些。

其中pi是可能发生某种结果的概率,H就是信息学中的熵,或称香农熵(Shannon entropy),单位为比特。它和玻尔兹曼总结的热力学中物理上的熵只差了一个常系数kB·ln2,kB是玻尔兹曼常数,ln2而是因为信息论和物理学中对对数底数选择的不同导致的。

信息熵就是信息数量的度量,我们由此可以计算一个符号中包含的信息量了。

对于抛一枚硬币的问题,两面概率都是1/2,则其信息熵为H=-(0.5×log(0.5)+0.5×log(0.5))bit=1 bit。对于两面相同的硬币,则是H=-1×log(1) bit=0 bit。如果不考虑大小写区别,那么如果26个英文字母再加上空格,27个符号,发送信息时,如果每个符号出现的概率相等,并且相互独立,那么每个符号包含的信息将会是H=-log(1/27)bit≈4.75bit。

在这种情况下,再加上大写、标点、其他语言的符号,零零散散的其他符号凑到一起,可以将8比特定义为1个字节(Byte),不过那已经是后话了。

实际情况中,这27个符号出现的概率并不相等,并且符号之间也存在关系,即使不考虑大范围(8个英语符号以上)上字母、单词之间的联系,单个英文符号中的信息熵其实也不过是4.75bit的一半。剩下的50%,就是英文的冗余度。换句话说,在大多数情况下,即使英文中去掉了50%的字母,其实并不影响英语的理解。就像在速记时,经常省略元音字母,却不影响对英语的理解。

解释完信息,香农可以开始认真讲述他关于信息的传递,也就是通信的看法。

图片来源:C. E. SHANNON,A Mathematical Theory of Communication

香农论文中第一幅图就将所有通讯系统模型化,可以用抽象的数学去描述所有通信系统。通讯的过程,就是将信源处的消息(文字、图片、声音等)经过发送器的处理(模拟调制、数字编码等)形成信号,信号在传输过程中受到噪声源的干扰后,变成接收器处接收到的信号,经过接收器的处理(解调、解码等),消息终于到达目的地信宿(人、手机、电脑等)。

香农提出的观点,就好像当年爱因斯坦给物体运动速度划定了光速的上限,他指出,信息传递的速率也是存在极限的,对于特定的信道,被称为信道容量C。如果信息源单位时间产生的熵H≤C,那么存在一个编码系统,使信息能完整传递;如果H>C,那就不能保证传输结果的完整性。这个定理被称为有噪信道编码定理,或香农定理

对于大多数情况下能用到的信道中,可以用一个公式计算信道的容量C。

W为带宽,S/N为信噪比。如果用常见的对话来类比,W就好比说话的速度,而S/N就是说话声音和环境噪音的比值。就像在嘈杂环境中小声对话效率很低,而在安静环境中大声说话能让对方辨别你声带的每一丝震动。最终对话的效率C就由这两者决定。

大航海时代

汉明码(hamming code)是一种具有自我纠错能力的编码方式,在这篇论文之前就已经被发明了。香农在论文“高效编码举例”这一部分列举了这种编码方式,并用信息论简洁明快却深刻的解释了它的原理。不过,显然这并不是最高效的编码方式。

横空出世的论文吸引了所有人的目光,而香农定理中H≤C那个小于等于号实在是令人想入非非,香农只是说明存在这样的编码方式,却没有说如何实现它。就好像《海贼王》中罗杰的最后一句话:“想要我的财宝吗,我把它都放在那了,想要就去那吧!”香农定理中那个可能存在的等号,给足了人们信心。而这篇论文中开创性的分析方法就像他10年前的那篇论文,将给编码方式的寻找提供了一些数学依据。自此,信息学寻找高效编码方式的“大航海时代”开始了。

而正是在这个过程中,从继电器到真空管,从晶体管到集成电路,计算机制造水平的飞速发展,让数学这个本来看上去离生活最遥远的学科,最深刻地改变了我们的现代生活。

今天我们使用的二维码,就算有部分损坏也不影响内容读取,这就是因为其编码方式具有冗余,可以让信息不易丢失。而其中编码方式,就是在 “大航海时代”中发明的里德-所罗门码(RS码)。这种1960年发明的编码方式,除了二维码,还应用在光盘、磁盘阵列RAID 6等场景下。

虽然有不少具有纠错功能的编码方式被发现,我们也能根据信息论用编码效率给它们论资排辈,但当初香农向大众许诺的“财宝”——接近,甚至达到香农极限的编码方式——始终没有出现。直到1991年法国教授克劳德·贝鲁(Claude Berrou)提出了turbo码。Turbo码是第一个接近香农极限的编码方案,并且作为数学理论,在信息时代的加成下,以前所未有的速度转进了实践应用。在仅仅十余年后的3G,4G中,turbo码就已经飞入了寻常百姓家。

2008年,极化码横空出世,这是首个能达到香农极限的编码方式。工程师埃尔达尔·阿里坎(Erdal Arikan)教授提出的极化码理论,几乎立即被工业界接受。2016年,在激烈辩论后,以华为为首的极化码阵营将极化码编码标准确定为5G信令信道编码方案。到今天,如果你的手机够新,那么已经能享受到5G带来的高速体验了。

从提出理论到进入实用,进入寻常百姓家,不过十年,科学成果到工业成果的转化从没有如此之快。不论是太阳系外探测器向我们传递信息时,还是深埋地下的实验装置探索基本粒子时,甚至只是我们随手翻翻手机时,都离不开信息论的支持。信息论的“大航海时代”快速且深刻地改变了我们生活的方方面面。如此看来,当年在普林斯顿高等研究所时,香农研究的纯数学问题,的确是要比爱因斯坦研究的物理问题要更实用一些。

不老顽童

不过香农本人并没有很多参与这个“大航海时代”。在提出信息论前后,他在密码学上还证明了一次性密钥是无法破译的,(这也是近期潘建伟团队量子密钥分发加密通信网络的数学理论基础)但是信息论的成就还是太过耀眼。MIT邀请他去做教授,期待他能带领MIT在信息论中实现更大突破。他的确在信息论上做了一些基础性工作。但给人印象更多的,是他终于回归到自己真正的样子——爱玩的老男孩。

想象一下,在教学楼里撞到某个教授踩着独轮车杂耍的场景,你就知道香农有多爱玩了。这个老男孩也曾像小时候一样,敲敲打打做了很多有趣的小玩意儿。直到老年时,他的工作室里还摆满了各种各样小玩具,有能喷火的小号,能在将其打开时自动关上的箱子,能杂耍的机器玩偶……他还有一个两面一样的硬币,这样,他抛硬币时总能猜对结果了。毕竟,这个问题对于他来说信息熵为0。

纪录片《香农传》中还原的香农的“终极机器”,是一个带按钮的木盒子,拨动摇杆打开盒子后会有一个小手伸出来将摇杆拨下去,关上盒子(图片来源:《香农传》)

“有用是最不重要的事情。”香农这样评论他工作室中的各种小玩意儿。

他是骗人的,他的确尝试了一些非常“有用”的东西。他发现俄罗斯轮盘放置时不可避免有一定倾斜,导致其偏向某个方向的概率更大,但为了分析这个概率需要一定量的计算。为此,他还和爱德华·索普(Edward Thorp)一起设计了历史上第一台可穿戴计算机,并一起到拉斯维加斯赌场检验他们的理论。他们将计算机隐藏在衣物之下,但由于计算机设计有些简陋,他们还不得不时刻忍受轻微的电击。当附带的耳机从耳朵里掉落出来时,旁边的赌客还都被他吓了一跳。不过至于他们有没有以此赚到钱,笔者并没有查证。

他还做过一个能自动寻路的机械小鼠,名为特修斯(Theseus)。小鼠位于一个定制平台的迷宫里,通过平台下方的继电器电路可以控制小鼠的移动,其目标是在迷宫中找到一个“奶酪”目标。小鼠会探索迷宫,并在找到目标之后,记住目标的位置,之后可以更快的找到目标。或者在迷宫形态、目标位置改变后重新学习,规划新的路线。这个小玩具可能是第一个此类人工智能设备。

香农和特修斯平台(图片来源:麻省理工学院博物馆)

他为了玩游戏甚至发过论文。他在1950年发表的一篇论文里描述了如何让计算机下国际象棋。他给出了国际象棋的复杂度,大约是1012⁰量级,这样的量级不可能暴力破解,不过通过他在论文中给出的较为明智的算法,可以大幅简化计算——1997年,由这篇论文演化出来的算法,在“深蓝”中运行,成功击败了卡斯帕罗夫(Каспаров)。

被问及有没有想过要把他这些“小玩意儿”商业化时,香农直截了当的回答没有。按他自己的说法,自己是一个没什么好胜心的人,要去商业化的话,一定会亏钱。

信息时代的功劳肯定不能全归功于香农一人,但他在其中肯定占有举足轻重的位置。在被繁杂信息浪花包围的我们中,这名天才的知名度并不高。不过,带入他的性格,可能他也并不在意。毕竟作为一个老顽童,在自己各种小玩意儿的包围下,亲眼见证了建立在自己理论上的信息时代如何改变人们的生活,对于一个数学家、工程师来说,这可能是能想象到的最幸福的事了。

参考链接:

http://people.math.harvard.edu/~ctm/home/text/others/shannon/entropy/entropy.pdf

https://www.bilibili.com/bangumi/play/ss34520

https://www.quantamagazine.org/how-claude-shannons-information-theory-invented-the-future-20201222/

https://en.wikipedia.org/wiki/Claude_Shannon

http://nautil.us/issue/50/emergence/claude-shannon-the-las-vegas-cheat

——————

转自:https://new.qq.com/rain/a/20210112a0e2cu00 



http://blog.sciencenet.cn/blog-43347-1272510.html

上一篇:对代表作机制设计的思考
下一篇:[转载]20世纪对西方占星术的科学检验

1 罗娜

该博文允许注册用户评论 请点击登录 评论 (0 个评论)

数据加载中...

Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2021-4-13 19:27

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部