您正在使用IE低版浏览器,为了您的雷峰网账号安全和更好的产品体验,强烈建议使用更快更安全的浏览器
此为临时链接,仅用于文章预览,将在时失效
业界 正文
发私信给温晓桦
发送

8

香农诞辰百年纪念特辑 | 为什么说纪念香农如同纪念牛顿?

本文作者:温晓桦 2016-04-29 13:24
导语:百年后的今天,我们为什么还在纪念克劳德·艾尔伍德·香农?

香农诞辰百年纪念特辑 | 为什么说纪念香农如同纪念牛顿?

克劳德·艾尔伍德·香农(Claude Elwood Shannon ),1916年4月30日—2001年2月26日。

香农是美国数学家、信息论的创始人。1948年,香农发表了《通信的数学理论》文章,提出了信息熵的概念,并创建了信息论。这篇文章奠定了香农“信息论之父”的地位。后来,香农在1949年继续发表了《噪声下的通信》。

几十年来,人类科技在数字化、智能化、网络化等的推动下经历了一波又一波通信、信息革命。数十年之后,在信息流、物质流的社会中,香农的论著依然闪烁着智慧之光,并将照耀人类社会今后的数个世纪。对此,雷锋网咨询了相关专业人士。

“香农的现代信息论永不过时”

是否有人曾质疑过,随着科技的不断发展,香农的信息论有可能无法满足现实的要求?答案是否定的。根源上讲,信息流、物质流组成了世界。只要世界的根源还是信息与物质,香农揭示的依旧是一个公理。即便发展到人工智能的今天,信息依然是一切的基础。业界来说,《通信的数学理论》是一篇20世纪少有的、对人类发展产生深远影响的科学论著,可与牛顿力学相媲美。即便百年之后,我们依旧享用着这个理论来探索未知的世界。

基于香农信息论绵延至今的技术成果

奠定现代加密的理论基础

20世纪60年代末开始了通信与计算机相结合,通信网迅速发展,人类开始向信息化社会迈进。这就要求信息作业的标准化,加密算法当然也不能例外。标准化对于技术发展、降低成本、推广使用有重要意义。

我们都知道,美国FBI提出的数据加密标准DES,以及最新图灵奖得主斯坦福大学密码学和网络安全技术专家惠特菲尔德·迪菲(Whitfield Diffie)和马丁·赫尔曼(Martin Hellman)提出的公钥加密系统是现代密码学的标志,是现代通信的基础加密技术。不过,你也许不知道,这两种标准或体制都以香农的信息论为基本指导思想。 

1949年,香农公开发表《保密系统的通信理论》一文,开辟了用信息论来研究密码学的新思路。这篇文章基于的理论是香农在1945年为贝尔实验室所完成的一篇报告《A Mathematical Theory of Cryptography》。论文发表后,香农被美国政府聘为政府密码事务顾问。

DES

DES全称为Data Encryption Standard,即数据加密标准,是一种使用密钥加密的算法。DES设计中使用的两个分组密码设计原则:混淆(confusion)和扩散(diffusion),其目的是抗击敌手对密码系统的统计分析。这就很好地提现了香农1949年的论文中所提出的设计强密码思想:

  • 组合(Combine)概念:由简单易于实现的密码系统进行组合,构造较复杂的、密钥量较大的密码系统。Shannon曾给出两种组合方式,即加权和法和乘积法。

  • 扩散(Diffusion)概念:将每一位明文及密钥尽可能迅速地散布到较多位密文数字中去,以便隐蔽明文的统计特性。

  • 混淆(Confusion)概念:使明文和密文、密钥和密文之间的统计相关性极小化,使统计分析更为困难。

信息论是研究和评估保密和认证系统的安全的重要工具,同时熵和信息量也是研究和评估隐匿系统重要工具。

Shannon曾用揉面团来形象地比喻“扩散”和“混淆”的作用,密码算法设计中要巧妙地运用这两个概念。与揉面团不同的是,首先密码变换必须是可逆的,但并非任何“混淆”都是可逆的;二是密码变换和逆变换应当简单易于实现。分组密码的多次迭代就是一种前述的“乘积”组合,它有助于快速实现“扩散”和“混淆”。

可以说,分组密码设计中将输入分段处理、非线性变换,加上左、右交换和在密钥控制下的多次迭代,都在香农构造密码的思想下指导进行。

公钥加密系统

香农在1949年指出:“好密码的设计问题,本质上是寻求一个困难问题的解,相对于某种其它条件,我们可以构造密码,使其在过程中的某点上等价于解某个已知数学难题。”在此影响下,迪菲和赫尔曼提出了公钥加密系统。

  • 迪菲和赫尔曼提出的公钥加密系统,其中的RSA、Rabin、背包、ElGamal、ECC、NTRU、多变量公钥等所有公钥算法都是基于某个数学问题求解的困难性。

  • 迪菲和赫尔曼的可证明安全理论就是在于证明是否可以将所设计的密码算法归约为求解某个已知数学难题。

  • 破译密码的困难性,所需的工作量,即时间复杂性和空间复杂性,与数学问题求解的困难性密切相关。计算机科学的一个新分支——计算复杂性理论与密码需的研究密切关联起来了。

扩频通信与调制解调

网络化社会的今天,我们必定离不开电子计算机和通信。下面我们用通俗易懂的方式来讲一下,我们今天孜孜以求的带宽、WiFi、蓝牙、GPS等与香农的关系吧:

根据香农(C.E.Shannon)在信息论研究中总结出的信道容量公式,即香农公式:

C=W×Log2(1+S/N)

式中:C——信息的传输速率,S——有用信号功率,W——频带宽度,N——噪声功率,也就是说:

为了提高信息的传输速率C,可以从两种途径实现,既加大带宽W或提高信噪比S/N。换句话说,当信号的传输速率C一定时,信号带宽W和信噪比S/N是可以互换的,即增加信号带宽可以降低对信噪比的要求,当带宽增加到一定程度,允许信噪比进一步降低,有用信号功率接近噪声功率甚至淹没在噪声之下也是可能的。扩频通信就是用宽带传输技术来换取信噪比上的好处。

扩频的出发点是加密,后来主要是用来减低干扰,同样是香农公式里面提到的另一个因子信噪比,也可以得到高带宽。简单来说,所谓降噪就是,带宽越宽,抗干扰能力越强。但是,带宽扩展上去了,信号功率就降低了,不符合市场经济。所以现代通信不是要无限扩大带宽,而是要找平衡点。基于这个思想,我们还在寻找这个平衡点。

信息论与机器学习

如果前面说的还是过去和当下的影响,那么接下来就不得不佩服香农的未来预示能力了。

香农是最早提出信息智能化的学者之一。信息论与人工智能之机器学习同为涉及计算机科学和应用数学等学科的分支领域,这两门交叉学科在起源和应用上有很多相似之处。不过,看起来神乎其神的机器学习,主要还是借用信息论的方法以此拓展理论研究和应用场景,比如关于分类计算上,借鉴于信息理论来创造和改进学习算法。

信息论中的一些度量也可以作为学习算法的度量。“学习就是一个熵减的过程”,学习的过程也就是使信息的干扰度下降的过程。比起传统的经验公式为基础的机器学习,以信息理论为基础的机器学习也拥有无可比拟的优势。

好吧来个具体一点的例子。上个月人机大战中的AlphaGo,其决策树算法是战胜人类的重要武器。那么,据来自于NSF博士论文《 Information Theory and its Relation to Machine Learning》所阐述,以互信息作为学习准则,例如以应用信息增益(归一化的互信息)构造最简结构决策树就是其中一种应用。这种基于信息理论为学习准则的原理就是将无序数据转变为有序数据,以信息熵差值作为测量尺度来评价转换效果。

如今也有不少研究者猜想,在机器学习中,所有学习目标的计算表征都是可以用熵函数的优化来描述或者解释的。这个猜想给了机器学习界一个很好的研究着力方向。

后记

我们纪念过那么多伟大的人物,不只在于膜拜。纪念不是扫墓,我们需要的是继往开来,或者说利用前人的成果,探索更多的未知世界。香农给了我们测量信息的方式,并未代替我们如何理解信息。把地球比作一只兔子,信息比作兔毛,我们还要努力爬到兔毛的顶端。雷锋网雷锋网雷锋网

雷峰网原创文章,未经授权禁止转载。详情见转载须知

分享:
相关文章
最新文章
请填写申请人资料
姓名
电话
邮箱
微信号
作品链接
个人简介
为了您的账户安全,请验证邮箱
您的邮箱还未验证,完成可获20积分哟!
请验证您的邮箱
立即验证
完善账号信息
您的账号已经绑定,现在您可以设置密码以方便用邮箱登录
立即设置 以后再说