吴军·《数学之美》

从事科学研究，最重要的是掌握思维方法。
牛顿《自然哲学的数学原理》四条法则之法则1（简单性原则）：除那些真实而已足够说明其现象者外，不必去寻找自然事物的其他原因。

爱因斯坦：从希腊哲学到现代物理学的整个科学史中，不断有人力图把表面上极为复杂的自然现象归结为几个简单的基本概念和关系。

www的发明人蒂姆·伯纳斯·李 谈到设计原理时说：简单性和模块化是软件工程的基石；分布式和容错性是互联网的生命。

数学在西方的意思是，通过学习获得的知识。

01. 文字和语言 vs 数字和信息

文字和语言与数学，从产生起原本就有相通性。

语言和数学的产生都是为了同一个目的——记录和传播信息。

信息

信息（发出信息）->编码->信道（传递信息）->解码->接受信息

语言是怎么产生的？
随着人类的进步和文明化的进展，需要表达的信息也越来越多，不再是几种不同的声音就能完全覆盖了，于是就产生了语言。

文字和数字

文字的起源？
当语言和词汇多到一定程度，人类仅靠大脑已经记不住所有词汇的时候，高效记录信息的需求就产生了，这就是文字的起源。

随着信息量的增加，埃及的象形文字太不适合时，概念的第一次概括和归类就开始了。

文字按照意思来聚类，最终会带来一些歧义性，也就是说有时弄不清一个多义字在特定环境下它到底表示其中的哪个含义。

解决的歧义的办法是？
大多数情况下，依靠上下文。

不同文明之间的交流通信，翻译的需求就产生了。翻译这件事之所以能达成，是因为不同的文字系统在记录信息上的能力是等价的，不同的文明或许会用不同的文字记载同一件事，那么翻译就有了可能。文字是信息的载体，而非信息本身。

罗塞塔石碑破译的2点知道意义：

1. 信息的冗余是信息安全的保障。罗塞塔石碑上的内容是同一信息重复3次，因此只要有一份内容完好保留下来，原有的信息就不会丢失，这对信道编码有指导意义。
2. 语言的数据，即语料，尤其是双语或者多语的对照语料对翻译至关重要，它是机器翻译研究的基础。

当人们的财产多到需要数一数才搞得清楚的时候，数字的需求就产生了。

当数量太大无法用十指计量的时候，进位制的需求就产生了，这意味着人类开始懂得对数量进行编码了，不同的数字代表不同的量，进而出现大数的概念，出现加减乘除。

文字和数字的分离，是阿拉伯数字0-9的出现，这是古印度人发明的而非阿拉伯人。

文字和语言背后的数学

出于成本的考量，人们把文字简化成了拼音，从象形文字到拼音文字是一个飞跃，因为人类在描述物体的方式上，从物体的外表进化到了抽象的概念，同时不自觉地采用了对信息的编码。

信息科学原理，就是在通信时，如果信道较宽，信息补习压缩就可以直接传递；而如果信道很窄，信息在传递前需要尽可能地压缩，然后在接受端进行加压缩。

为避免《圣经》的抄写错误，他们用了类似于计算机和通信中校验码的方法，把每一个希伯来字母对应一个数字，这样每行文字加起来便得到一个特殊的数字，这个数字便成了这一行的校验码。

词可以被认为是有限而且封闭的集合，而语言则是无限和开放的集合。从数学上讲，对于前者可以有完备的编解码规则，而后者则不具备这个特性。

语言坚持从真实的语句文本（语料）出发，而语法则坚持从规则出发。自然语言的处理的成就最终宣布前者的获胜。

02. 自然语言处理——从规则到统计

语言的出现是为了人类之间的通信。字母（或者中文的笔画）、文字和数字实际上是信息编码的不同单位。任何一种语言都是一种编码的方式，而语言的语法规则是编码解码的算法。

我们把一个要表达的意思，通过某种语言的一句话表达出来，就是用这种语言的编码方式对头脑中的信息做了一次编码，编码的结果就是一串文字。而如果对方懂得这门语言，ta就可以用这门语言的解码方法获得说话人要表达的信息。这就是语言的数学本质。

一、计算机能否处理自然语言；二、如果能，那么它处理自然语言的方法是否和人类一样？yes.

机器智能

图灵测试：如果人无法判断自己交流的对象是人还是机器，就说明这个机器有智能了。

自然语言处理的2个阶段：
第一个阶段：用电脑模拟人脑，从20世纪50年代到20世纪70年代，这20多年的成果几乎为0。
第二个阶段：用数学模型和统计的方法来处理。

鸟飞派，也就是看看鸟怎么飞的，就能模仿鸟造出飞机，而不需要了解空气动力学。同样的，把这种直觉用自爱机器翻译和语音识别上，他们认为，只有人类才能做的事情，就必须先让计算机理解自然语言，而做到这一点就必须让计算机拥有类似我们人类这样的智能。然而，怀特兄弟造出飞机靠的是空气动力学而不是仿生学。

在20世纪60年代，摆在科学家面前的问题是怎样才能理解自然语言？
解决这个问题的基础是，分析语句和获取语义，让计算机理解自然语言，从而应用到语音识别、机器翻译、自动问答、自动摘要上。

计算机高级程序语言都可以概括成上下文无关的文法，这是一个在算法上可以在多项时间内解决的问题。

基于文法规则的分析器有2大问题：

1. 通过语法覆盖20%真实语句，要编写的文法规则已经达几万条了，写起来非常复杂，同时想提高精确度，后期要写更多，而规则之间甚至还会出现矛盾，会带来的一系列处理问题，然而精确度却一直没什么成效。
2. 即使能够写出涵盖所有自然语言现象的语法规则集合，也很难用计算机来解析。如解决歧义问题就要理解上下文，而一旦遇到复杂的上下文，通过语法规则就解决不了了（看下文）。而程序语言是认为设计的、便于计算机解码的，并且是上下文无关的文法，因此能够用计算机来解码。

对于上下文无关文法，算法的复杂度基本上是语句长度的2次方，而对于上下文有关文法，计算机复杂度基本上是语句长度的6次方，随着语句长度的增加，计算时间太长，用今天的电脑，分析二三十个词的句子也需要一两分钟，而这是不具备使用价值的。

从规则到统计

自然语言处理的第二个阶段，使用语义来处理，它的麻烦更大。自然语言中词的多义性很难用规则来描述，而且严重依赖上下文，甚至是“世界的知识”和常识。而解决这个问题的转变，是使用了统计的方法。

统计的方法的核心模型是通信系统加隐含马尔可夫模型。

1. 这个系统的输入和输出都是一维的符号序列，而且保持原有的次序。
2. 而用语法分析的方法，输入的是一维的句子，输出的却是二维的分析树；在机器翻译中，虽然输出的依然是一维的句子（另一种语言的），但是次序会有很大的变化，因为语法分析不管用。

基于统计的方法，随着计算能力的提高和数据量的不断增加，精确度越来越高。

老科学家，就是老的科学家。因此，“我常想，我自己一定要在还不太糊涂和固执时就退休。”

基于统计的自然语言处理方法，在数学模型上和通信是想通的，甚至就是想同。因此，在数学意义上自然语言处理又和语言的初衷——通信联系在一起了。但是，科学家们用了几十年才认识到这个联系。
（因此，了解过去，有利于更好的了解未来。）

03. 统计语言模型

计算机处理自然语言，首先要为自然语言这种有着上下文相关的特性建立数学模型，即统计语言模型。

用数学的方法描述语言规律

给句子中每个词赋予一个概率，统计历史上讲过的话（数据量足够的大），得出这个词出现的概率和这个词跟前面若干个词的相关度，进而组成句子。

从第二个词开始，后面的计算太过庞大，所以出现了马儿可夫的方法。只用来感受一下这个数学模型：P(i | i + 1) -> P(i | i - 1)。

用数学的方法描述语言规律，有模型的训练、零概率问题、平滑方法、语料的选取等几个大块问题。

04. 谈谈分词

理解语言，从理解句子表达的意思开始，这就需要理解词的意思，词组的意思，句子的意思，上下文的意思。

中文分词方法的演变

中文词组没有分界线，处理方法有几种：

1. “查字典法”：把一个句子从左向右扫描一遍，遇到字典里有的词就标识出来，遇到复合词（比如“上海大学”）就找最长的词匹配，遇到不认识的字串就分割成单字词。这种方法处理不好遇到复杂句子，如：发展中国家，解析成发展-中国-家。
2. “查字典法”发展版：最少次数的分词理论，即一句话应该分成数量最少的词串。这个方法的毛病是，遇到多义词就失效了。（有两重理解意思的词，容易产生歧义）。
3. 现在用的是统计概率的方法，上面已经写过了。

关于分词：

1. 这个问题属于已经解决的问题，不是什么难题了。只要采用统计语言模型，加上一次技巧，就能得到很好的分词结果，不值得再投入大精力浪费时间。
2. 英语和主要西方语言没有分词问题，但在手写体识别上有用到。

05. 隐含马尔可夫模型

通信模型

通信的本质是一个编解码的和传输的过程。

所谓语音识别，就是听者去猜说话者要表达的意思。这其实就像通信中，接收端根据收到的信号去分析、理解、还原发送端传送过来的信息。

语音识别是，根据声学信号来推测说话者的意思。
机器翻译是，利用计算机，根据接收到的英文信息，推测说话者的汉语意思。
自动纠错是，根据带有拼写错误的语句推测说话者想表达的正确意思。
总结起来就是，几乎所有的自然语言处理问题，都可以等价成通信的解码问题。

隐含马尔可夫模型

表示看不下去。

围绕着马儿可夫模型有3个基本问题：

1. 给定一个模型，如何计算某个特定的输出序列的概率；
2. 给定一个模型和某个特定的输出序列，如何找到最可能产生这个输出的状态序列；
3. 给定足够量的观测数据，如何估计隐含马儿可夫模型的参数。

隐含马尔可夫模型最初应用于通信领域，继而推广到语音和语言处理中，成为连接自然语言处理和通信的桥梁。它需要一个训练算法（鲍姆-韦尔奇算法）和使用时的解码算法（维特尔算法）。

06. 信息的度量和作用

如何解决信息的度量问题，如何量化信息？
信息熵。

信息熵

一条信息的信息量与其不确定性有着直接的关系。比如说，我们要搞清楚一件非常不确定的事，或是我们一无所知的事情，就需要了解大量的信息。相反，如果已对某件事了解较多，则不需要太多的信息就能把它搞清楚。所以，从这个角度来看，可以认为，信息量就等于不确定性的多少。

H = -(p1·log i1 + p2·log i2 + ··· + pn·log in)
p1, p2, p3 是概率，H 即使这个信息的信息熵。

信息的作用

汉语是最简洁的语言。

情报的作用，就是消除不确定性。

一个事物内部会存在有随机性，也就是不确定性，假定为U，而从外部消除这个不确定性唯一的办法是引入信息I，而需要引入的信息量取决于这个不确定性的大小，即I > U 才行。当 I < U 时，这些信息可以消除一部分不确定性，也就是说新的不确定性。反之，如果没有信息，任何公式或者数字的游戏都无法排除不确定性。

几乎所有的自然语言处理、信息与信号处理的应用都是一个消除不确定性的过程。网页搜索本质上也是利用信息消除不确定性的过程。

不正确的做法是，在搜索关键词上玩数字和公式的游戏，由于没有额外的信息引入，这种做法没有效果。
最糟糕的做法是引入认为的假设，这和“蒙”没有区别，其结果是似乎满足了个别用户的口味，但是对大部分用户来讲，搜索结果反而变得更糟。

信息的作用在于消除不确定性，自然语言处理的大量问题就是寻找相关的信息。

互信息

互信息，作为两个随机事件“相关性”的量化度量。解决了有两重理解意思的词，容易产生歧义的问题。

信息熵不仅是对信息的量化度量，而且是整个信息论的基础。它对于通信、数据压缩、自然语言处理都是有很大的指导意义。信息熵的物理含义，是对一个信息系统不确定性的度量。

07. 贾里尼克和现代语言处理

早年生活

美国人和欧洲人的思维方式比较直接，他们不会玩中国学者那种所谓的“既要···又要···”的逻辑，如果相信一种方法就坚持到底，如果这种方法遇到障碍了，他们就坚持解决问题，直到把这种方法完善起来。

对教育的几点看法：
首先，小学生和中学生其实没有必要花那么多时间读书，而他们的社会经验、生活能力以及那时树立起来的志向将帮助他们的一生。
第二，中学阶段花很多时间比同伴多读的课程，在大学以后用非常短的时间就可以读完，因为在大学阶段，人的理解力要强得多。
第三，学习（和教育）是一个人一辈子的过程，很多中学成绩好的亚裔学生进入名校后表现明显不如那些因为兴趣而读书的美国同学，因为前者不断读书的动力不足。
第四，书本的内容可以早学，也可以晚学，但是错过了成长阶段却是无法弥补回来的。

贾里尼克如何成为那么多著名科学家的精神领袖级人物的呢？
一，自我的动力，要改变自身命运的决心；二，博学和丰富的经历；三，年轻时受到世界级大师的指点；四，长期坚持。

“我一直认为，一个人想要在自己的领域做到世界一流，他的周围必须有非常多的一流人物。”

一位老人的奇迹

两三年讲老化的CLSP变成世界一流的研究中心？
贾里尼克做了2件大事，2件小事。

贾里尼克做的2件大事：

1. 从美国政府主管研究的部门那里申请到了很多研究经费。
2. 然后，每年夏天他用一部分经费，邀请世界上20-30名顶级的科学家和学生到CLSP一起工作，使得CLSP成为世界上语音和语言处理的中心之一。

贾里尼克做的2件小事：

1. 招募了一批当时很有潜力的年轻学者。
2. 利用自己影响力，在暑假把他的学生排到世界上最好的公司去实习，通过这些学生的优异表现，树立起CLSP在培养人才方面的声誉。

贾里尼克一方面治学严谨，要求严格；另一方面为学生提供便利，承担学生的学费和生活费。

牛人能告诉你的，是什么方法不好。
跟巴菲特说的一样：“你们都非常聪明，不需要我告诉你们做什么，我只需要告诉你们不要去做什么（这样可以少犯很多错误）。”

08. 简单之美——布尔代数和搜索引擎

“我希望面对的是大众，而不仅仅是专业人员，而了解一件事有什么用对大众而言更重要。”

技术分为术和道两种，具体的做事方法是术，做事的原理和原则是道。而真正做好一件事没有捷径，离不开一万小时的专业训练和努力。总想是指望靠一个算法、一个模型就能毕其功于一役，这是不现实的。

建立一个搜索引擎重要的3步：下载、索引和排序（权重、概率、级别）：

1. 自动下载尽可能多的网页；
2. 建立快速有效的索引；
3. 根据相关性对网页进行公平准确的排序。

布尔代数 （0，1）

布尔代数只有2个数字：0和1。它可以表示逻辑的“是”与“非”。它把万物都量子化，从连续的变成一个个分离的，用0和1组合二进制、十进制等来表示，而万物远比其组合数量“google”（10的100次方）小得多。

索引

为什么搜索引擎能在0.0几秒内找到成千上万甚至上亿的搜索结果？
技巧是，建索引。如在图书馆找书，拿到索引号，对应书架上一下子就找到了想看的书；而不是一本本的找。

搜索引擎的索引是数据库，把搜索的关键字转换成布尔运算的算式，再到数据库查询。

索引的方法有很多，如位置（国家地区）、次数、类型、重要性（权重概率）、质量和访问频率、分级别等等。

数据（索引）存放在分布式的多台服务器上，在查询的时候，就可以分发到多台服务器上，并行（同时）搜索，并把结果送到主服务器进行合并处理，最后将结果返回给用户。

“（人们）发觉真理在形式上从来是简单的，而不是复杂和含混的。”——牛顿

09. 图论和网络爬虫

互联网搜索引擎在建立索引前需要用一个程序自动地将所有的网页下载到服务器上，这个程序称为网络爬虫，它的编写是基于离散数学中图论的原理。

图论

广度优先搜索算法：如
首先，访问权重最高的城市（北京），
接着，访问与之有直接联系的城市（上广深），以此类推直到尽头，
最后，访问零散的城市。

深度优先搜索算法：一条路走到黑，再走另一条路。

搜索期间，要记录已访问过的城市。

网络爬虫

网络爬虫运用的就是图论的方法，连接的方式就是网页超链接，记录的方式是“散列表”（哈希表）。

好的问题是大家都知道这个事实，但是它没有对和错的答案，但是有好和不好、可行和不可行的答案，而且可以不断地往深处问下去，如：如何构建一个网络爬虫？点击浏览器搜索发生了什么事情？

10. PageRank——Google的民主表决式算法

网页排名技术PageRank算法是早起Google的杀手锏，它背后的原理是图论和线性代数的矩阵运算。

搜索结果的排名取决于2点：

1. 关于网页的质量信息；
2. 这个查询与每个网页的相关性信息。

PageRank算法原理

PageRank算法原理的核心思想是：“民主表决”。
在互联网上，如果一个网页被很多其他网页所连接，说明它受到普遍的承认和信赖，那么它的排名就高。另外还有网页排名的权重影响。

计算搜索结果的网页排名过程中需要用到网页本身的排名，这就成了先有鸡还是先有蛋的问题？
布林把这个问题变成了一个二维矩阵相乘的问题，并用迭代的方法解决了问题。先假定所有网页的排名是相同的，并且根据这个初始值，算出各个网页的第一次迭代排名，然后再根据第一次迭代排名算出第二次的排名。而这种算法不需要任何人工干预。

解决计算一百亿亿数量级的方法是，稀疏矩阵计算技巧。

解决计算时间长的方法是，并行自动化计算。

而这种算法，决定搜索质量最有用的信息是用户的点击数据，而一项新技术为搜索质量带来的提升空间却非常有限，用户很难感觉到差别。

11. 如何确定网页和查询的相关性

确定网页和查询关键字的重要性有多高是关键，目前通用的方法是TF-IDF，原理是信息论。

技术和算法的重要性依然高于数据，因此确定网页和查询的相关性主要依靠算法。但今天商业搜索引擎拥有大量的用户点击数据，因此，对搜索相关性贡献最大的是根据用户对常见搜索点击网页的结果得到的概率模型。

影响搜索引擎的4类因素：

1. 完备的索引。就是搜索的东西要在保存在数据库中。
2. 对网页质量的度量，比如PageRank。
3. 用户偏好。不同用户的喜欢、专业给出不同的搜索排名。
4. 确定一个网页和某个查询的相关性的方法。

搜索关键词权重的科学度量 TF-IDF

将关键字拆成分词，如“原子能的应用”，拆分成原子能，的，应用3个关键词，用关键词计算出词频的总和，就是表示了网页的相关性。

计算词频：根据网页的长度，用关键词出现的次数除以网页的总字数。

词频的度量因素权重：“原子能” > “应用” > “的”。“的”作为停止词权重为0。

网页的综合排名 = 相关性 X 网页排名的乘积。

12. 有限状态机和动态规划——地图与本地搜索的核心技术

地图和本地服务中，要用到有限状态机和动态规划技术。
这2项技术应用到：语音识别、拼写和语法纠错、拼音输入法、工业控制和生物的序列分析等。

智能手机的定位和导航功能3个关键技术：

1. 利用卫星定位；
2. 地址的识别；
3. 根据用户输入的起点和重点，在地图上规划最短路线或者最快路线。

地址分析和有限状态机

地址分析：判断一个地址的正确性，同时非常准确地提炼出相应的地理信息（省、市、区、街道、门牌号）。

使用有限状态机识别地址的2个关键问题：

1. 通过一些有效的地址建立状态机；
2. 给定一个有限状态机后，地址字串的匹配算法。

有了有限状态机后，就可以用它分析网页，找出网页中的地址部分，建立本地搜索的数据库。同样，也可以对用户输入的查询进行分析，挑出其中描述地址的部分，当然，剩下的关键词就是用户要找打内容。

全球导航和动态规划

全球导航的关键算法是，计算机科学图论中的动态规划的算法。

局部最短路线，到全程最短路线。

13. Google AK-47 的设计者——阿米特·辛格博士

AK-47冲锋枪的优点：从不卡壳，不易损坏，可在任何环境下使用，可靠性好，杀伤力大并且操作简单。
简单的哲学，简单有效的解决方案。

在工程上简单实用的方法最好。
一个好的算法，应该简单、有效、可靠性好而且容易读懂（或者说易操作），而不应该是故弄玄虚。

做事情的哲学，即先帮助用户解决80%的问题，再慢慢解决剩下的20%的问题，是在工业界成功的秘诀之一。
许多失败并不是因为人不优秀，而是做事情的方法不对，一开始追求大而全的解决方案，之后长时间不能完成，最后不了了之。

遵循简单原则，容易解释每一个步骤和方法背后的道理，这样不仅便于出了问题时查错，而且容易找到今后改进的目标。
在做细微改进的时候，必须很清楚“所以然”。说不清楚理由的改进，即使看上去有效也不会采用，因为这样将来可能是个隐患。

分析研究的价值，是掌握第一手的资料。

14. 余弦定理和新闻的分类

新闻的分类，由计算机整理、分类和聚合各个新闻网站的内容，一切都是自动生成的。这里面的关键技术就是新闻的自动分类。

计算机本质上只能做快速计算。用计算机解决问题的思路，就是把事物转化成计算机能够“算”。
把新闻变成一组可计算的数字，然而再设计一个算法来算出任意2篇新闻的相似性。
新闻的相似性（长得像不像）又名新闻的特征向量，概括来讲就是词出现的概率，根据概率分类。

余弦定理：一篇10000字的文本，各个维度的数值都比一篇500字的文本来得大，因此单纯比较各个维度的大小没有太大意义。如果2个向量的方向一致，说明相应的新闻用词的比例基本一致。因此，可以通过计算2个向量的夹角来判断对应的新闻主题的接近程度。

美国人总是倾向于用机器（计算机）代替人工来完成任务。虽然在短期内需要做一些额外的工作，但是从长远看可以节省更多时间和成本。

15. 矩阵运算和文本处理中的2个分类问题

无论是词汇的聚类还是文本的分类，都可以通过线性代数中矩阵的奇异值分解来进行。这样一来，自然语言处理的问题就变成了一个数学问题。
分类其实是一个聚类问题，关键是计算相似程度。

矩阵运算中的奇异值分解，一次就能把所有新闻相关性计算出来，不需要迭代，它适合处理超大规模文本的粗分类。
在实际应用中，可以先进行奇异值分解，得到粗分类结果，再利用计算向量余弦的方法，在粗分类结果的基础上，进行几次迭代，得到比较精确的结果。

16. 信息指纹及其应用

世间万物都有一个唯一标识的特征，信息也是如此。每一条信息都有它特定的指纹，通过这个指纹可以区别不同的信息。

一段文字所包含的信息，就是它的信息熵。如果对这段信息进行无损压缩编码，理论上编码后的最短长度就是它的信息熵。

所谓信息指纹，可以简单理解为将一段信息（文字、图片、音频、视频等）随机地映射到一个多维二进制空间中的一个点（一个二进制数字）。只要这个随机函数做得好，那么不同信息对应的这些点就不会重合，因此，这些二进制的数字几句成了原来的信息所具有的独一无二的指纹。
信息指纹的消重（消灭重复）作用，计算的复杂度不需要额外的空间，因此是最佳方法。

信息指纹的计算方法一般分2步：
首先，将这个字符串看成是一个特殊的、很长的整数。
接下来，就需要用到一个产生信息指纹的关键算法，伪随机数产生器算法，通过它将任意很长的整数转换成特定长度的伪随机数。

17. 由电视剧《暗算》所想到的——谈谈密码学的数学原理

密码学的根本是信息论和数学。没有信息论指导的密码是非常容易被破解的。只有在信息论被广泛应用与密码学后，密码才真正变得安全。

信息论时代的密码学

信息论的算法都有如下共同点：

1. 它们都有2个完全不同的样式，一个用于加密，一个用于解密。
2. 这2个看上去无关的钥匙，在数学上是关联的。

一个先进且最常用的密码系统设计方法：

1. 找2个很大的素数（质数）P和Q，越大越好，比如100位长的，然后计算它们的乘积N = P x Q, M = (P - 1) x (Q -1)
2. 找一个和M互素的整数E，也就是说M和E除了1以外没有公约数
3. 找一个整数D，使得E x D除以M余1，级E x M mod M = 1
   其中，E是公钥，谁都可以用来加密，公开密钥一次就来源于此，D是私钥用于解密，一定要自己保存好。联系公钥和密钥的乘积N是公开的。

用下面的公式对X加密，得到密码Y：X的E次方 mod N = Y
解密：Y的D次方 mod N = X

公开密钥的好处有：

1. 简答，就是一些乘除而已
2. 可靠。公开密钥方法保证产生的密文是统计独立而分布均匀的。也就是说，不论给出多少份明文和对应的密文，也无法根据已知的明文和密文的对应来破译下一份密文。更重要的是N、E可以公开给任何人加密用，但是只有掌握密钥D的人才可以解密，即使加密者自己也无法解密的。这样，即使加密者被抓住叛变了，整套密码系统仍然是安全的。
3. 灵活，可以产生很多的公开密钥E和私钥D的组合给不同的加密者。

利用信息可以消除一个系统的不确定性。而利用已经获得的信息情报来消除一个情报系统的不确定性就是解密。密码学的最高境界依然是无论地方获取多少密文，也无法消除己方情报系统的不确定性。为了达到这个目的，就不仅要做到密文之间相互无关，同时密文还是看似完全随机的序列。这个思想，则是学术研究的道。

18. 闪光的不一定是金子——谈谈搜索引擎反作弊问题和搜索结果的权威性问题

反作弊

做事情的方法有道和术2种境界。
遇到问题，要找到背后的动机和本质，从本质上解决问题。

搜索引擎作弊从本质上看就如同对（搜索）排序的信息加入噪音，因此反作弊的第一条是增强排序算法的抗噪音能力。其次是像在信号处理中去噪音那样，还原原来真是的排名。

如果在发动机很吵的汽车里用手机打电话，对方可能听不清；但是如果知道了汽车发动机的频率，可以加上一个与发动机噪音频率相同、振幅相反的信号，便很容易地消除发动机的噪音，这样，接听人可以完全听不到汽车的噪音。

权威性

计算权威度的步骤，得到一个针对不同主题，哪些信息源（网站）具有权威性的关联矩阵：

1. 对每一个网页正文（包括标题）中的每一句话进行句法分析，然后找出涉及到主题的短语（phrases，比如“吸烟的危害”），以及对信息源的描述（比如国基卫生组织、梅奥诊所等）。这样我们就获得了所谓的“提及”信息。
2. 利用互信息，找到主题短语和信息源的相关性。
3. 需要对主题短语进行聚合，虽然很多短语从字面上看不同，但是意思是相同的，比如
   “吸烟的危害”、“吸烟是否致癌”、“香烟的危害”、“煤焦油的危害”，等等，因此需要将这些短语聚类到一起得到搜索的主题。
4. 最后，我们需要对一个网站中的网页进行聚合，比如把一个网站下面的网页按照子域或者子目录进行聚类。为什么要做这一步呢？因为即使是一个权威的网站，它下面的一些子域却未必具有权威性。

19.谈谈数学模型的重要性

1. 一个正确的数学模型应当在形式上是简单的。
2. 一个正确的模型一开始可能还不如一个精雕细琢的错误模型来的准确，但是，如果我们认定大方向是对的，就应该坚持下去。（日心说一开始并没有地心说准确）。
3. 大量准确的数据对研发很重要。
4. 正确的模型而已可能受噪音干扰，而显得不准确；这时不应该用一种凑合的修正方法加以弥补，而是要找到噪音的根源，这也许能通往重大的发现。

20. 不要把鸡蛋放到一个篮子里——谈谈最大熵模型

最大熵原理，简单理解就是要保留全部的不确定性，将风险降到最小。
最大熵原理指出，对一个随机事件的概率分布进行预测时，我们的预测应当满足全部已知的条件，而对未知的情况不要做任何主观假设。当我们遇到不确定性时，就要保留各种可能性。

最大熵可以将各种信息整合到一个统一的模型中。它有很多良好的特性：从形式上看，它是最漂亮、最完美的统计模型；从效果上看，它是唯一一种既能满足各个信息源的限制条件，又能保证平滑性的模型。但是，最大熵模型计算量巨大，在工厂上实现方法的好坏决定了模型的实用与否。

21. 拼音输入法的数学模型

汉字的输入过程本身就是人和计算机之间的通信。好的输入法会自觉或不自觉地遵循通信的数学模型。当然要做出最有效的输入法，应当自觉使用信息论做指导。

输入法输入汉字的快慢取决于汉字编码的平均长度，通俗点讲，就是用击键次数乘寻找这个键所需时间。单纯地减少编码长度未必能提高输入速度，因为寻找一个键的时间可能变得较长。提高输入法的效率在于同时优化这2点，而这其中有着坚实的数学基础。

五笔输入法等一批发明人可以说是全军覆没。这一代输入法的问题在于减少了每个汉字击键的次数，而忽视了找到每个键的时间。

把语言和文字作为通信的编码手段，一个重要目的是帮助思维和记忆。如果一个输入法中断了人们的思维过程，就和人的自然行为不相符合。认知科学已经证明，人一心无二用。

拼音输入法有3个优点：

1. 它不需要专门学习
2. 输入自然，不会中断思维，也就是说找每个键的时间非常短
3. 因为编码长，有信息冗余量，容错性好。
   于是，拼音输入法要解决的问题只剩下排除一音多字的歧义性了。

香农第一定理指出：对于一个信息，任何编码的长度都不小于它的信息熵。

22. 自然语言处理的教父马库斯和他的优秀弟子们

放手让博士生研究自己感兴趣的课题，这是马库斯桃李满天下的原因。他一贯主张建立几个世界上最好的专业，而不是专业最齐全的系。

柯林斯：追求完美

他做文法分析器的出发点不是为了验证一个理论，而是要做一个世界上最好的分析器，他把每一个细节都研究得和你仔细，追求做到完美，大有其他科学家从此不必再做文法分析器的架势！

布莱尔：简单才美

下面是以拼音转汉字说明基于变换规则的机器学习方法：
第一步，把每个拼音对应的汉字中最常见的找出来作为第一遍变换的结果，当然结果有不少错误。比如，“常识”可能被转换成“长识”。
第二步，可以说是“去伪存真”，用计算机根据上下文，列举所有的同音字替换的规则，比如，如果chang被标识成“长”，但是后面的汉字是“识”，则将“长”改成“常”。
第三步，应该就是“去粗取精”，将所有的规则应用到事先标识好的语料中，挑出有用的，删掉无用的。然后重复二三步，知道找不出有用的为止。

在研究方面，布莱尔有时不一定能马上知道应该怎么做，但是能马上否定掉一种不可能的方案。这和他追求简单的研究方法有关，他能在短时间内大致摸清每种方法的好坏。

23. 布隆过滤器

日常生活中，经常要判断一个元素是否在一个集合中。布隆过滤器是计算机工程中解决这个问题最好的数学工具。

计算机中的集合是用散列表来储存的，优点是快速准确，缺点是耗费储存空间。但集合比较小的时，这个问题不明显，当集合规模巨大时，散列表储存效率低的问题就显现出来了。

散列表的储存效率一般只有50%，布隆过滤器是散列表的1/8 ~ 1/4的大小。
布隆过滤器的好处在于快速、省空间，但是有一定的误识别率。常见的补救办法是再建立一个小的白名单，储存那些可能被误判的邮件地址。

24. 马尔科夫链的扩展——贝叶斯网络

贝叶斯网络是一个加权的有向图，是马尔科夫链的扩展。而从认识论的层面看：贝叶斯网络克服了马儿可夫链那种机械的线性约束，它可以把任何有关联的时间统一到它的框架下面。它在生物统计、图像处理、决策支持系统和博弈论中都有广泛的使用。

25. 条件随机场、文法分析及其他

条件随机场，是计算联合概率分布的有效模型，而句法分析似乎是英文课上英语老师教的东西，这2者有什么联系呢？

26. 维特比和他的维特比算法

维特比算法是现代数字通信中使用最频繁的算法，同时也是很多自然语言处理的解码算法。

维特比算法是动态规划算法，可以解决任何一个途中的最短路径问题。凡是使用隐含马尔可夫模型描述的问题都可以用它来解码。

能够提供关键性的发明，而且为了保障其效益在全社会得到最大化，他还解决了所有配套的技术。

27. 上帝的算法——期望最大化算法

只要有一些训练数据，再定义一个最大化函数，采用EM算法，利用计算机经过若干次迭代，就可以得到所需要的模型。

1. 给出一个收益函数，它代表我们的利益。
2. 在每个时刻计算出能够最大化收益的期望值的方向，之后沿着这个方向走一小步。接下来， 再从新的起点出发重复这个过程。

一个人交朋友，开始可能有比较大的随意性，但是他内心有一个衡量标准（收益函数），就是最大化自己的“收益”，久而久之，那些对他好的人、能让他分泌多巴胺等激素的人，以及物理距离近有便于互相帮助的人，就成了他的朋友，其他人就渐渐淡出了他的生活圈。

1. 谷歌工程师文化——给单元测试写得好的员工奖励，同时给代码经常出错的员工一些小的惩戒，于是重视工程质量的风气就形成了。
2. Facebook一开始就强调产品迭代速度，因此它就成为一个以产品（而非技术）驱动的公司。

28. 逻辑回归和搜索广告

逻辑回归模型，是一种将影响概率的不同因素结合在一起的指数模型，它不仅在搜索广告中起着重要的作用，而且被广泛应用于信息处理和生物统计中。

29. 各个击破算法和Google云计算的基础

“各个击破算法”的原理——将复杂的大问题分解成小很多小问题分别求解，然后再把小问题的解合并成原始问题的解。由此可见，在生活中大量用到的、真正有用的方法常常是简单朴实的。

30. Google大脑和人工神经网络

人工神经网络是一个形式上非常简单但分类功能强大的机器学习工具。
Google大脑并不是一个什么都能思考的大脑，而是一个很能计算的人工神经网络。因此，与其说Google大脑很聪明，不如说它很能算。

随着计算能力的不断提高，计算量大但简单的数学方法有时能够解决很复杂的问题。

在现实生活中，真正能够通用的工具在形式上必定是简单的。

31. 大数据的能力——谈谈数据的重要性

如果说在过去的40年里，主导全球IT产业发展的是摩尔定律，那么在今后的20年里，主导IT行业继续发展的动力则将来自于数据。

计算复杂度

将解决实际问题的方法变成计算机可以运行的程序，中间的桥梁就是计算机的算法。一个优秀的计算机科学家或者工程师与平庸的程序员的差别就在于：前者总是不断寻找并且有能力找到好的算法，而后者仅满足于勉强解决问题。而在所有的“好”算法中，显然存在一个最优的算——找到它们是从事计算机科学的人应该努力的目标。

对于计算机算法来说，虽然衡量其好坏的标准非常多，比如运算速度、对储存量的需求、是否容易理解、是否容易实现等等，但是为了便于公平地比较，我们需要一个客观的标准。这个标准就是算法的复杂程度。

数学在计算机科学中的一个重要作用，就是找到计算复杂度尽可能低的解。同时找到复杂问题的近似解。

第二版后记

大部分软件工程师在一个未知领域都是从直观感觉触发，用“凑”的方法来解决问题，在中国尤其如此。这样的做法说得不好听，就是山寨。

（无意中）采用错误的模型，在特定的场合或许勉强有效，就比如我们介绍的地心说一样，毕竟也使用了几千年。但是，错误的模型终究是原理真理的，其负面影响会渐渐表现出来。最终是不仅远离了正确的结果，而且常常把原本简单的事情弄得很复杂，以至于濒临崩溃（地心说对于日心说就是如此）。

人们要认识到正确的理论和方法，总有一个渐进的过程。任何事物都有它的发展规律，而这些规律都是可以认识的，在信息科学领域也不例外。当我们认识了规律后，就应该自觉地在工作中遵循而非违背规律。

能用很简单的比喻将所在领域内最深奥的道理介绍清楚，让大众理解。这也许就是他们成为世界顶级科学家的原因。他们一方面对自己的领域非常精通，同时他们能用大白话把道理讲清楚。世界上好的学者总是有办法深入浅出地把大道理讲给外行听，而不是故弄玄虚地把简单的问题复杂化。