概论

前言

本书确实是本好书，书中还提到了「买指数基金」比如

因此，如果一个散户投资人能真正做到“用数据说话”，只需奉行一条投资决策，那就是买指数基金。这当然不是我的发明，而是投资领域著名的经济学家威廉·夏普（William F. Sharpe）和伯顿·麦基尔（Burton G. Malkiel）等人一直倡导的。

作者对人工智能边界的思考值得深究，这和辛顿的担忧有很大的区别。

今天，当计算机解决了越来越多的智能问题之后，人们对人工智能的态度从怀疑渐渐走向迷信。不了解人工智能背后技术的人开始凭着幻想猜测计算机的能力，即便是一些从业者也是糊里糊涂，完全忘却了计算机的能力有数学上的边界。这一边界，就如同物理学上无法超越的光速极限或绝对零度的极限一样，在最根本的层面上限制了人工智能的能力，这一边界与技术无关，仅取决于数学本身的限制。具体到今天大家使用的计算机，它有着两条不可逾越的边界，分别是由图灵和希尔伯特划定的。

……

对于机器智能也是如此，今天之所以机器智能显得极为强大，靠的是人们找到了让机器拥有智能的正确方法，即大数据、摩尔定律和数学模型这三个支柱。我们在前面各个章节中所介绍的内容，其实依然只是一部分数学模型而已。这些数学模型将各种形形色色的实际问题变成了计算问题，当然，这里面有一个前提，就是那些问题本质上就是数学问题，而且是可以用计算机计算的数学问题。但是，当计算机科学家们揭开了一个又一个这样的问题的数学本质之后，人们自然就不免会贪心地以为这样的进步是没有极限的，以致浪费时间去解决根本解决不了、可能也没有必要解决的问题。而那些行业之外的人若是有了这种想法，则难免会担心出现机器控制住人的事情。外行产生这样的想法情有可原，因为缺乏专业知识，但是如果不少从业者也想不清楚这个道理，那就是思维方式的问题了。大部分人的思维方式都是所谓的脚步累加，一点点进步，很难看清大的格局。

……

对人工智能领域而言，如今尚未解决的问题还非常多，无论是使用者还是从业者，都应该设法解决各种人工智能问题，而不是杞人忧天，担心人工智能这一工具太强大了。对非计算机行业的人来讲，世界上还有很多需要由人来解决的问题，如何利用好人工智能工具，更有效地解决属于人的问题，才是应该给予更多关注的。

杨立昆虽然不认同「大力出奇迹」的大语言模型，而是尝试实现世界模型。但这种方式真的可行吗？

书中还有一些瑕疵，比如反复出现的「涉及到」就是一种语病；还有多处不使用通用翻译，需要想一下才知道是谁，比如作者把Urbain LeVerrier的姓氏翻译成维内尔，而不是通用的勒维耶。

书中介绍了三位大师——贾里尼克、马库斯和辛格的故事，让我对自然语言处理领域的发展过程有了比较清晰的理解。贾里尼克、马库斯不同的管理风格值得中国的大学和研究机构借鉴，辛格的决策方式也值得技术管理员学习。

书籍简介

作者: 吴军

出版社: 人民邮电出版社

出品方: Just-pub

出版年: 2020-4

页数: 364

定价: 69.00元

装帧: 平装

ISBN: 9787115537973

内容简介

八年前，“数学之美”系列文章原刊载于谷歌黑板报，获得上百万次点击，得到读者高度评价。读者说，读了“数学之美”，才发现大学时学的数学知识，比如马尔可夫链、矩阵计算，甚至余弦函数原来都如此亲切，并且栩栩如生，才发现自然语言和信息处理这么有趣。

在纸本书的创作中，作者几乎把所有文章都重写了一遍，为的是把高深的数学原理讲得更加通俗易懂，让非专业读者也能领略数学的魅力。读者通过具体的例子学到的是思考问题的方式——如何化繁为简，如何用数学去解决工程问题，如何跳出固有思维不断去思考创新。

本书第一版荣获国家图书馆第八届文津图书奖。第二版增加了针对大数据和机器学习的内容。第三版增加了三章新内容，分别介绍当今非常热门的三个主题：区块链的数学基础，量子通信的原理，以及人工智能的数学极限。

作者简介

吴军，学者，投资人，人工智能、语音识别和互联网搜索专家。毕业于清华大学和美国约翰·霍普金斯大学，现任丰元资本创始合伙人、上海交通大学客座教授、约翰·霍普金斯大学工学院董事等职。

吴军博士曾作为资深研究员和副总裁分别任职于Google公司和腾讯公司。在Google公司，他和同事一同开创了搜索反作弊研究领域，成立了中、日、韩文产品部门，设计了Google中、日、韩文搜索算法，领导了Google自然语言处理和自动问答等研究型项目，拥有近20项美国发明专利。在腾讯公司，他负责了搜索、搜索广告和街景地图等项目。作为风险投资人，他成功地投资了150家硅谷和中国的高科技企业。吴军博士对科技产业有深入的研究，是当今硅谷地区解读IT产业最权威的专家。

吴军博士著有《浪潮之巅》《数学之美》《大学之路》《文明之光》《智能时代》《见识》《态度》和《全球科技通史》等多部畅销书，并多次获得包括文津奖、中国好书奖、中华优秀出版物在内的图书大奖。

正文摘录

第二版序言

第一版序言

第三版前言

第1章　文字和语言 vs 数字和信息

文字和语言与数学，从产生起原本就有相通性，虽然它们的发展一度分道扬镳，但是最终还是能走到一起。

数字、文字和自然语言一样，都是信息的载体，它们之间原本有着天然的联系。语言和数学的产生都是为了同一个目的一记录和传播信息。但是，直到半个多世纪前香农博士提出信息论，人们才开始把数学和信息系统自觉地联系起来。在此之前，数学的发展主要跟人类对自然的认识以及生产活动联系在一起，包括天文学、几何和工程学、经济学、力学、物理学甚至生物学等，而数学和语言学几乎是没有交集的。我们见到很多数学家同时是物理学家或者天文学家，但是过去很少有数学家同时是语言学家。

本书几乎全部的章节讲的都是近半个多世纪的事情，但是在这一章里，我们将先通过时间隧道回到远古，回到语言、文字和数字产生的年代。

1　信息

2　文字和数字

3　文字和语言背后的数学

我们在这一章中讲述了文字、数字和语言的历史，目的是帮助读者感受语言和数学天然的、内在的联系。这里提到的一些概念和主题，是我们在后面的章节中讨论的重点，包括：

• 通信的原理和信息传播的模型
• （信源）编码和最短编码
• 解码的规则，语法
• 聚类
• 校验位
• 双语对照文本，语料库和机器翻译
• 多义性和利用上下文消除歧义性

这些今天自然语言处理学者们研究的问题，我们的祖先在设计语言之初其实已经遇到了，并且用类似今天的方法解决了，虽然他们的认识大多是自发的，而不是自觉的。他们过去遵循的法则和我们今天探求的研究方法背后有着共同的东西，这就是数学规律。

第2章　自然语言处理——从规则到统计

人类对机器理解自然语言的认识走了一条大弯路。早期的研究集中采用基于规则的方法，虽然解决了一些简单的问题，但是无法从根本上将自然语言理解实用化。直到20多年后，人们开始尝试用基于统计的方法进行自然语言处理，才有了突破性进展和实用的产品。

上一章讲到，语言的出现是为了人类之间的通信。字母（或者中文的笔画）、文字和数字实际上是信息编码的不同单位。任何一种语言都是一种编码的方式，而语言的语法规则是编解码的算法。我们把一个要表达的意思，通过某种语言的一句话表达出来，就是用这种语言的编码方式对头脑中的信息做了一次编码，编码的结果就是一串文字。而如果对方懂得这门语言，他或者她就可以用这门语言的解码方法获得说话人要表达的信息。这就是语言的数学本质。虽然动物也能做到传递信息，但是利用语言来传递信息是人类的特质。

1946年，现代电子计算机出现以后，计算机在很多事情上做得比人还好。既然如此，机器能不能懂得自然语言呢？事实上计算机一出现，人们就开始琢磨这件事。这里面涉及两个认知方面的问题：第一，计算机能否处理自然语言；第二，如果能，那么它处理自然语言的方法是否和人类一样。这也是本书要回答的两个问题。这里先给出简洁版的答案：对这两个问题的回答都是肯定的，Yes！

1　机器智能

当时，学术界对人工智能和自然语言理解的普遍认为：要让机器完成翻译或者语音识别等只有人类才能做的事情，就必须先让计算机理解自然语言，而做到这一点就必须让计算机拥有类似我们人类这样的智能。（今天几乎所有的科学家都不再坚持这一点，而很多门外汉还误以为计算机是靠类似我们人类的这种智能解决了上述问题。）为什么会有这样的认识？是因为人类就是这么做的，道理就这么简单。对于人类来讲，一个能把英语翻译成汉语的人，必定能很好地理解这两种语言。这就是直觉的作用。在人工智能领域，包括自然语言处理领域，后来把这样的方法论称作“鸟飞派”，也就是看看鸟是怎样飞的，就能模仿鸟造出飞机，而不需要了解空气动力学。事实上我们知道，怀特兄弟发明飞机靠的是空气动力学而不是仿生学。在这里，我们不要笑话我们前辈来自于直觉的天真想法，这是人类认识的普遍规律。今天，机器翻译和语音识别已经做得不错，并且有上亿人使用过，但是这个领域之外的大部分人依然错误地以为这两种应用是靠计算机理解了自然语言才实现的。事实上，它们全都靠得是数学，更准确地说是靠统计。

……

这里面至少有两个越不过去的坎儿。首先，要想通过文法规则覆盖哪怕 20% 的真实语句，文法规则的数量（不包括词性标注的规则）也至少是几万条。语言学家几乎已经是来不及写了，而且这些文法规则写到后来甚至会出现矛盾，为了解决这些矛盾，还要说明各个规则特定的使用环境。如果想要覆盖50%以上的语句，文法规则的数量最后会多到每增加一个新句子，就要加人一些新的文法。这种现象不仅出现在计算机处理语言上，而且出现在人类学习和自已母语不同语系的外语时。今天30岁以上的人都应该会有这种体会：无论在中学和大学英语考试成绩多么好，也未必能考好 GRE，更谈不上看懂英文的电影。原因就是我们即使学了10年的英语语法，也不能涵盖全部的英语。

其次，即使能够写出涵盖所有自然语言现象的语法规则集合，也很难用计算机来解析。描述自然语言的文法和计算机高级程序语言的文法不同。自然语言在演变过程中，产生了词义和上下文相关的特性。因此，它的文法是比较复杂的上下文有关文法（Context Dependent Grammar），而程序语言是我们人为设计的、便于计算机解码的上下文无关文法（Context Independent Grammar），相比自然语言简单得多。理解两者的计算量不可同日而语。

在计算机科学中，图灵奖得主高德纳（Donald Knuth）提出了用计算复杂度（Computational Complexity，请见附录）来衡量算法的耗时。对于上下文无关文法，算法的复杂度基本上是语句长度的二次方，而对于上下文有关文法，计算复杂度基本上是语句长度的六次方。也就是说，长度同为10的程序语言的语句和自然语言的语句，计算机对它们进行句法分析（Syntactic Parsing）的计算量，后者是前者的一万倍。而且随着句子长度的增长，二者计算时间的差异会以非常快的速度扩大。即使今天，有了很快的计算机（英特尔i7四核处理器），分析上面这个二三十个词的句子也需要一两分钟的时间。因此，在20世纪70年代，即使是制造大型机的IBM公司，也不可能采用规则的方法分析一些真实的语句。

2　从规则到统计

在上个世纪70年代，基于规则的句法分析很快就走到了尽头，而对于语义的处理则遇到了更大的麻烦。首先，自然语言中词的多义性很难用规则来描述，而是严重依赖于上下文，甚至是“世界的知识”（World Knowledge）或者常识。1966年，著名人工智能专家明斯基（上面提到的达特茅斯会议的发起者之一）举了一个简单的反例来说明计算机处理语言的难处，“The pen is in the box.”和“The box is in the pen.”中两个pen的区别。第一句话很好理解，学过半年英语的学生都懂。但是第二句话则会让外国人很困惑，为什么盒子可以装到钢笔里？其实，第二句话对于英语是母语的人来讲很简单，因为这里pen是围栏的意思。整句话翻译成中文就是“盒子在围栏里”。这里面pen是指钢笔还是围栏，通过上下文已经不能解决，需要借助于常识，具体来说就是“钢笔可以放到盒子里，但是盒子比钢笔大，所以不能放到钢笔里”。这是一个很简单的例子，但清晰地说明了当时自然语言处理研究方法上存在的问题。1966年的明斯基已经不是十年前那个默默无名的年轻人了，而是当时世界上数一数二的人工智能专家。他的意见对美国政府的科技决策部门产生了重大影响，自然科学基金会等部门对传统的自然语言处理研究非常失望，以至于在较长时间里对这方面的研究资助大大减少。可以说，利用计算机处理自然语言的努力直到20世纪70年代初是相当失败的。1970年以后统计语言学的出现使得自然语言处理重获新生，并取得了今天的非凡成就。推动这个技术路线转变的关键人物是弗里德里克·贾里尼克（Frederick Jelinek）和他领导的IBM华生实验室（T.J. Watson）。最初，他们也没有想解决整个自然语言处理的各种问题，而只是希望解决语音识别的问题。采用基于统计的方法，IBM将当时的语音识别率从70%提升到90%，同时语音识别的规模从几百单词上升到几万单词，这样语音识别就有了从实验室走向实际应用的可能。关于这段历史，后面在贾里尼克的故事里会介绍。

……

在从20世纪80年代末至今的25年里，随着计算能力的提高和数据量的不断增加，过去看似不可能通过统计模型完成的任务，渐渐都变得可能了，包括很复杂的句法分析。到了20世纪90年代末期，大家发现通过统计得到的句法规则甚至比语言学家总结的更有说服力。2005年以后，随着 Google基于统计方法的翻译系统全面超过基于规则方法的 SysTran 翻译系统，基于规则方法学派固守的最后一个堡垒被拔掉了。这才使得我们在这本书里，可以且只需用数学的方法给出现今所有自然语言处理相关问题的全部答案。

……

基于统计的自然语言处理方法，在数学模型上和通信是相通的，甚至就是相同的。因此，在数学意义上自然语言处理又和语言的初衷一通信联系在一起了。但是，科学家们用了几十年才认识到这个联系。

第3章　统计语言模型

统计语言模型是自然语言处理的基础，并且被广泛应用于机器翻译、语音识别、印刷体或手写体识别、拼写纠错、汉字输入和文献查询。

我们在前面的章节一直强调，自然语言从它产生开始，逐渐演变成一种上下文相关的信息表达和传递的方式，因此让计算机处理自然语言，一个基本的问题就是为自然语言这种上下文相关的特性建立数学模型。这个数学模型就是在自然语言处理中常说的统计语言模型（Statistical Language Model），它是今天所有自然语言处理的基础，并且广泛应用于机器翻译、语音识别、印刷体或手写体识别、拼写纠错、汉字输入和文献查询。

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

2　延伸阅读：统计语言模型的工程诀窍

2.1高阶语言模型

上一节中公式（3.3）模型的假设前提是，句子中的每个词只和前面一个词有关，而和更前面的词就无关了，这似乎太简化了，或者说近似得过头了。确实是这样，读者很容易找到一些例子：某个词和前面第二个词有关，比如说“美丽的花朵”，花朵其实和美丽有关。因此，更普遍的假设是某个词和前面若干个词有关。

……

最后还有一个问题，三元或四元甚至更高阶的模型是不是就能覆盖所有的语言现象呢？答案显然是否定的。在自然语言中，上下文之间的相关性可能跨度非常大，甚至可以从一个段落跨到另一个段落。因此，即便再怎么提高模型的阶数，对这种情况也无可奈何，这就是马尔可夫假设的局限性，这时就要采用其他一些长程的依赖性（Long Distance Dependency）来解决这个问题了，在以后的章节还会对此有介绍。

2.2模型的训练、零概率问题和平滑方法

使用语言模型需要知道模型中所有的条件概率，我们称之为模型的参数。通过对语料的统计，得到这些参数的过程称作模型的训练。……

……

这是生活中的常识。但是在估计语言模型的概率时，很多人恰恰忘了这个道理，因此训练出来的语言模型“不管用”，然后回过头来怀疑这个方法是否有效。其实这个方法屡试不爽，今天的数字通信很大程度就建立在这个基础上，问题在于如何使用。那么如何正确地训练一个语言模型呢？

……

训练统计语言模型的艺术就在于解决好统计样本不足时的概率估计问题。 1953年古德（I.J.Good）在他老板图灵（Alan Turing）（就是计算机科学史上的图灵）的指导下，提出了在统计中相信可靠的统计数据，而对不可信的统计数据打折扣的一种概率估计方法，同时将折扣出来的那一小部分概率给予未看见的事件（Unseen Events）。古德和图灵还给出了一个很漂亮的重新估算概率的公式，这个公式后来被称为古德一图灵估计（Good-Turing Estimate）。

古德一图灵估计的原理是这样的：对于没有看见的事件，我们不能认为它发生的概率就是零，因此我们从概率的总量（Probability Mass）中，分配一个很小的比例给这些没有看见的事件（见图3.1）。这样一来，看见的那些事件的概率总和就要小于1了，因此，需要将所有看见的事件概率调小一点。至于小多少，要根据“越是不可信的统计折扣越多”的方法进行。

2.3语料的选取问题

模型训练中另一个重要的问题就是训练数据，或者说语料库的选取。如果训练语料和模型应用的领域相脱节，那么模型的效果往往会大打折扣。比如，某个语言模型的应用是网页搜索，则该模型的训练数据就应该是杂乱的网页数据和用户输入的搜索串，而不是传统的、规范的新闻稿，即使前者夹杂着噪声和错误。

这里有一个很好的例子，来自腾讯搜索部门。最早的语言模型是使用《人民日报》的语料训练的，因为开发者认为这些语料干净、无噪声。但是实际的效果比较差，经常出现搜索串和网页不匹配的例子。后来改用网页的数据，尽管它们有很多的噪音，但是因为训练数据和应用一致，搜索质量反而好。

训练数据通常是越多越好。虽然通过上节介绍的平滑过渡的方法可以解决零概率和很小概率的问题，但是毕竟在数据量很大时概率模型的参数可以估计得比较准确。高阶的模型因为参数多，需要的训练数据也相应会多很多。遗憾的是，并非所有的应用都能得到足够多的训练数据，比如说机器翻译的双语语料就非常少，在这种情况下片面追求高阶的大模型就没什么意义。

在训练数据和应用数据一致并且训练量足够大的情况下，训练语料的噪音高低也会对模型的效果产生一定的影响，因此，在训练之前有时需要对训练数据进行预处理。一般情况下，少量的（没有模式的）随机噪音清除起来成本非常高，通常就不做处理了。但是对于能找到模式（Pattern）的、量比较大的噪音还是有必要过滤的，而且它们也比较容易处理，比如网页文本中存在的大量制表符。因此，在成本不高的情况下，有必要对训练数据进行过滤。对于数据的重要性，我们会在后面 的章节里专门介绍。

小结

统计语言模型在形式上非常简单，也很容易理解。但是里头的学问却很深，一个专家可以在这方面研究很多年，比如我们在延伸阅读中提到的那些问题。数学的魅力就在于将复杂的问题简单化。

第4章　谈谈分词

中文分词是中文信息处理的基础，它同样走过了一段弯路，目前依靠统计语言模型已经基本解决了这个问题。

在本书的第一版中，这一章的题目是“谈谈中文分词”，在这一版中，我将标题改为“谈谈分词”，因为分词问题不仅中文有，很多亚洲语言比如日语、韩语和泰国语同样存在，甚至在拼音语言（英语、法语等）中，也有类似的问题，比如在英语句法分析时找词组和中文分词是一码事。不过它们使用的方法都是相同的，因此本章仍以中文分词为例来说明这个问题。

1　中文分词方法的演变

郭进是中国大陆地区自觉运用统计语言模型方法进行自然语言处理的第一人，并且获得了成功。这里面除了他比较努力以外，他特殊的经历也起了很大作用。他和我一样，虽然是计算机专业的博士，却在以通信为主的科系工作，他周围都是长期从事通信研究的同事，可以说是贾里尼克的同行，因此，他在方法论上接受通信模型非常直接。

……

在不少人看来，分词技术只是针对亚洲语言的，而罗马体系的拼音语言没有这个问题，其实不然。也许大家想不到，中文分词的方法也被应用到英语处理，主要是手写体识别中。因为在识别手写体时，单词之间的空格就不很清楚了。中文分词方法可以帮助判别英语单词的边界。

其实，自然语言处理的许多数学方法是通用的，与具体的语言无关。在 Google 内部，我们在设计语言处理的算法时，都会考虑它是否能很容易地适用于各种自然语言。这样才能有效地支持上百种语言的搜索。

需要指出的是任何方法都有它的局限性，虽然利用统计语言模型进行分词，可以取得比人工更好的结果，但是也不可能做到百分之百准确。因为统计语言模型很大程度上是依照“大众的想法”，或者“多数句子的用法”，而在特定情况下可能是错的。另外，有些人为创造出的“两难” 的句子，比如对联“此地安能居住，其人好不悲伤”，用什么方法都无法消除二义性。好在真实文本中，这些情况几乎不会发生。

最后，关于分词还有两点需要说明。首先，这个问题属于已经解决的问题，不是什么难题了。在工业界，只要采用基本的统计语言模型，加上一些业界熟知的技巧就能得到很好的分词结果，不值得再去花很大的精力去做研究，因为即使能够进一步提高准确率，提升的空间也很有限。第二，英语和主要西方语言原本是没有分词问题的，除了要做文法分析找词组。不过随着平板电脑和智能手机的普及，手写体识别输入法也被很多人使用，很多手写体识别软件需要使用分词，因为大家在书写英语时，词与词之间常常是没有停顿的，这就如同我们写汉字没有空格一样，因此原本用来对中文进行分词的技术，也在英语的手写体识别中派上了用场。

2　延伸阅读：如何衡量分词的结果

2.1分词的一致性

如何衡量分词结果的对与错和好与坏，看似容易，其实并不是那么简单。说它看似容易，是因为只要对计算机分词的结果和人工分词的结果进行比较就可以了。说它不是那么简单，是因为不同的人对同一个句子可能有不同的分词方法。比如有的人认为“清华大学”应该是一个词，有的人却认为“清华大学”是一个复合词，应该分成“清华-大学”两个词。应该讲，这两种分法都有道理，虽然语言学家可能比较坚持某一种是正确的。在不同的应用中，经常是一种词的切分比另一种更有效。

不同的人对词的切分看法上的差异性远比我们想象的要大得多。1994年，我和IBM的研究人员合作，对此进行了研究。IBM提供了100个有代表性的中文整句，我组织30名清华大学二年级的本科生独立对它们进行分词。实验前，为了保证大家对词的看法基本一致，我们对30名学生进行了半个小时的培训。实验结果表明，这30名教育水平相当的大学生分词的一致性只有85%——90%。

在将统计语言模型用于分词以前，分词的准确率通常较低，可以提升的空间非常大。不同的人切分的差异虽然会影响分词评测的准确性，但是好的方法和坏的方法还是可以根据分词结果与人工切分的比较来衡量的。

当统计语言模型被广泛应用后，不同的分词器产生的结果的差异要远远小于不同人之间看法的差异，这时简单依靠与人工分词的结果比较来衡量分词器的准确性就很难，甚至是毫无意义的了。很难讲一个准确率在 97%的分词器就一定比另一个准确率为95%的要好，因为这要看它们选用的所谓正确的人工分词的数据是如何得来的。我们甚至只能讲某个分词器和另一个分词器相比，与人工分词结果的吻合度稍微高一点而已。所幸的是，现在中文分词是一个已经解决了的问题，提高的空间微乎其微了。只要采用统计语言模型，效果都差不到哪里去。

2.2词的颗粒度和层次

人工分词产生不一致性的原因主要在于人们对词的颗粒度的认识问题。在汉语里，词是表达意思最基本的单位，再小意思就变了。这就如同在化学里分子是保持化学性质的最小单位一样。再往下分到原子，化学的特性就变了。在这一点上所有的语言学家都没有异议。因此，对于“贾里尼克”这个词，所有的语言学家都会认为它不可拆分，如果拆成四个字，和原来的人名就没有联系了。但是对于“清华大学”，大家的看法就不同了，有些人认为它是一个整体，表示北京西郊一所特定的大学，也有人认为它是一个词组，或者说是一个名词短语，“清华”是修饰“大学”的定语，因此需要拆开，不拆开就无法体现它里面的修饰关系。这就涉及对词的颗粒度的理解了。

在这里不去强调谁的观点对，而是要指出在不同的应用中，会有一种颗粒度比另一种更好的情况。比如在机器翻译中，一般来讲，颗粒度大翻译效果好。比如“联想公司”作为一个整体，很容易找到它对应的英语翻译 Lenovo ，如果分词时将它们分开，就很有可能翻译失败，因为在汉语中，“联想”一词首先是“根据相关联的场景想象”的意思。但是在另外一些应用，比如网页搜索中，小的颗粒度比大的颗粒度要好。比如“清华大学”这四个字如果作为一个词，在对网页分词后，它是一个整体了，当用户查询“清华”时，是找不到清华大学的，这绝对是有问题的。

针对不同的应用，我们可以构造不同的分词器，但是这样做不仅非常浪费，而且也没必要。更好的做法是让一个分词器同时支持不同层次的词的切分。也就是说，上面的“清华大学”既可以被看成一个整体，也可以被切分开，然后由不同的应用自行决定切分的颗粒度。这在原理和实现上并不是很麻烦，简单介绍如下。

……

介绍了分词的层次概念后，我们可以更进一步讨论分词器准确性的问题了。分词的不一致性可以分为错误和颗粒度不一致两种，错误又分成两类，一类是越界型错误，比如把“北京大学生”分成“北京大学-生”。另一类是覆盖型错误，比如把“贾里尼克”拆成了四个字。这些是明显的错误，是改进分词器时要尽可能消除的。接下来是颗粒度的不一致性，人工分词的不一致性大多属于此类。这一类不一致性在衡量分词器的好坏时，可以不作为错误，以免不同人的看法的不同左右了对分词器的度量。对于某些应用，需要尽可能地找到各种复合词，而不是将其切分。总之，要继续做数据挖掘，不断完善复合词的词典（它的增长速度较快），这也是近年来中文分词工作的重点。

小结

中文分词以统计语言模型为基础，经过几十年的发展和完善，今天基本上可以看做是一个已经解决的问题。当然不同的人做的分词器有好有坏，这里面的差别主要在于数据的使用和工程实现的精度。

第5章　隐马尔可夫模型

隐马尔可夫模型最初应用于通信领域，继而推广到语音和语言处理中，成为连接自然语言处理和通信的桥梁。同时，隐马尔可夫模型也是机器学习的主要工具之一。

隐马尔可夫模型是一个并不复杂的数学模型，到目前为止，它一直被认为是解决大多数自然语言处理问题最为快速、有效的方法。它成功地解决了复杂的语音识别、机器翻译等问题。看完这些复杂的问题是如何通过简单的模型得到描述和解决，我们会由衷地感叹数学模型之妙。

1　通信模型

2　隐马尔可夫模型

隐马尔可夫模型（Hidden Markov Model）其实并不是19世纪俄罗斯数学家马尔可夫（Andrey Markov）发明的（见图5.2），而是美国数学家鲍姆（Leonard E.Baum）等人在20世纪六七十年代发表的一系列论文中提出的，隐马尔可夫模型的训练方法（鲍姆－韦尔奇算法）也是以他的名字命名的。

3　延伸阅读：隐马尔可夫模型的训练

围绕着隐马尔可夫模型有三个基本问题：

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

第一个问题相对简单，对应的算法是Forward-Backward算法，在此略过，有兴趣的读者可以参看弗里德里克·贾里尼克（Frederick Jelinek）的Statistical Methods for Speech Recognition(Language,Speech,and Communication)—书第二个问题可以用著名的维特比算法解决，我们在以后的章节中会介绍。第三个问题就是我们这一节要讨论的模型训练问题。

……

鲍姆－韦尔奇算法的每一次选代都是不断地估计（Expectation）新的模型参数，使得输出的概率（我们的目标函数）达到最大化（Maximization），因此这个过程被称为期望值最大化（Expectation-Maximization），简称 EM过程。EM过程保证算法一定能收敛到一个局部最优点，很遗憾它一般不能保证找到全局最优点。因此，在一些自然语言处理的应用，比如词性标注中，这种无监督的鲍姆-韦尔奇算法训练出的模型比有监督的训练得到的模型效果略差，因为前者未必能收敛到全局最优点。但是如果目标函数是凸函数（比如信息），则只有一个最优点，在这种情况下EM过程可以找到最佳值。在第27章“上帝的算法一期望最大化算法”里，我们还会对EM过程进行更详细的介绍。

小结

隐马尔可夫模型最初应用于通信领域，继而推广到语音和语言处理中，成为连接自然语言处理和通信的桥梁。同时，隐马尔可夫模型也是机器学习的主要工具之一。和几乎所有的机器学习的模型工具一样，它需要一个训练算法（鲍姆-韦尔奇算法）和使用时的解码算法（维特比算法），掌握了这两类算法，就基本上可以使用隐马尔可夫模型这个工具了。

第6章　信息的度量和作用

信息是可以量化度量的。信息熵不仅是对信息的量化度量，也是整个信息论的基础。它对于通信、数据压缩、自然语言处理都有很强的指导意义。

到目前为止，虽然我们一直在谈论信息，但是信息这个概念依然有些抽象。我们常常说信息很多，或者信息较少，但却很难说清楚信息到底有多少。比如，一本50多万字的中文书《史记》到底有多少信息量，或者一套莎士比亚全集有多少信息量。我们也常说信息有用，那么它的作用是如何客观、定量地体现出来的呢？信息用途的背后是否有理论基础呢？对于这两个问题，几千年来都没有人给出很好的解答。直到1948年，香农（Claude Shannon）在他著名的论文“通信的数学原理”（A Mathematic Theory of Communication）中提出了“信息熵”（读shang）的概念，才解决了信息的度量问题，并且量化出信息的作用。

1　信息熵

不同语言的冗余度差别很大，而汉语在所有语言中冗余度是相对小的。大家可能都有这个经验，一本英文书，翻译成汉语，如果字体大小相同，那么中译本一般都会薄很多。这和人们普遍的认识一汉语是最简洁的语言一是一致的。对中文信息有兴趣的读者可以读我和王作英教授在《电子学报》上合写的一篇文章“汉语信息熵和语言模型的复杂度”。

2　信息的作用

信息是消除系统不确定性的唯一办法（在没有获得任何信息前，一个系统就像是一个黑盒子，引入信息，就可以了解黑盒子系统的内部结构）。

……

知道的信息越多，随机事件的不确定性就越小。这些信息，可以是直接针对我们要了解的随机事件，比如上面提到的日本内阁的战略决定；也可以是和我们关心的随机事件相关的其他（事件）的信息一通过获取这些相关信息也能帮助我们了解所关注的对象。比如在前面几章提到的自然语言的统计模型，其中的一元模型就是通过某个词本身的概率分布，来消除不确定因素；而二元及更高阶的语言模型则还使用了上下文的信息，那就能准确预测一个句子中当前的词汇了。在数学上可以严格地证明为什么这些“相关的”信息也能够消除不确定性。为此，需要引入一个条件熵（Conditional Entropy）的概念。

……

用一句话概括这一节：信息的作用在于消除不确定性，自然语言处理的大量问题就是寻找相关的信息。

3　互信息

4　延伸阅读：相对熵

同样，大家不必关心公式本身，只要记住下面三条结论就好：

1. 对于两个完全相同的函数，它们的相对熵等于零。
2. 相对熵越大，两个函数差异越大；反之，相对熵越小，两个函数差异越小。
3. 对于概率分布或者概率密度函数，如果取值均大于零，相对熵可以度量两个随机分布的差异性。

相对熵最早是用在信号处理上。如果两个随机信号，它们的相对熵越小，说明这两个信号越接近，否则信号的差异越大。后来研究信息处理的学者们也用它来衡量两段信息的相似程度，比如说如果一篇文章是照抄或者改写另一篇，那么这两篇文章中词频分布的相对熵就非常小，接近于零。在 Google的自动问答系统中，我们采用了上面的詹森——香农度量来衡量两个答案的相似性。

相对熵在自然语言处理中还有很多应用，比如用来衡量两个常用词（在语法和语义上）在不同文本中的概率分布，看它们是否同义。另外，利用相对，还可以得到信息检索中最重要的一个概念：词频率一逆向文档频率（TF-IDF），后面会在网页搜索相关性和新闻分类中进一步介绍TF-IDF 的概念。

小结

熵、条件熵和相对熵这三个概念与语言模型的关系非常密切。我们在第 2 章中谈到语言模型时，没有讲如何定量地衡量一个语言模型的好坏，因为当时还没有介绍这三个概念。当然，读者会很自然地想到，既然语言模型能减少语音识别和机器翻译的错误，那么就拿一个语音识别系统或者机器翻译软件来试试，好的语言模型必然导致错误率较低。这种想法是对的，而且今天的语音识别和机器翻译也是这么做的。但这种测试方法对于语言模型的研究人员来讲，既不直接，又不方便，而且很难从错误率反过来定量度量语言模型。事实上，在贾里尼克等人研究语言模型时，世界上既没有像样的语音识别系统，更没有机器翻译。我们知道，语言模型是为了用上下文预测当前的文字。模型越好，预测得越准，那么当前文字的不确定性就越小。

信息熵正是对不确定性的衡量，因此可以想象信息熵能直接用于衡量统计语言模型的好坏。当然，因为有了上下文的条件，所以对高阶的语言模型，应该用条件熵。如果再考虑到从训练语料和真实应用的文本中得到的概率函数有偏差，就需要再引人相对熵的概念。贾里尼克从条件熵和相对熵出发，定义了一个称为语言模型复杂度（Perplexity）的概念，直接衡量语言模型的好坏。复杂度有很清晰的物理含义，它是在给定上下文的条件下，句子中每个位置平均可以选择的单词数量。一个模型的复杂度越小，每个位置的词就越确定，模型越好。

李开复博士在介绍他发明的Sphinx语音识别系统的论文里谈到，如果不用任何语言模型（即零元语言模型），（模型的）复杂度为997，也就是说句子中每个位置有997个可能的单词可以填入。如果（二元）语言模型只考虑前后词的搭配，不考虑搭配的概率，复杂度为60。虽然它比不用语言模型好很多，但与考虑搭配概率的二元语言模型相比要差很多，因为后者的复杂度只有20。

对信息论有兴趣又有一定数学基础的读者，可以阅读斯坦福大学托马斯·科弗（Thomas Cover）教授的专著《信息论基础》（Elementsof Information Theory）。科弗教授是当今最权威的信息论专家。

现在，让我们来概括一下本章的内容。信息不仅是对信息的量化度量，而且是整个信息论的基础。它对于通信、数据压缩、自然语言处理都有很大的指导意义。信息的物理含义是对一个信息系统不确定性的度量，在这一点上，它和热力学中熵的概念有相似之处，因为后者就是一个系统无序的度量，从另一个角度讲也是对一种不确定性的度量。这说明科学上很多看似不同的学科之间也会有很强的相似性。

第7章　贾里尼克和现代语言处理

作为现代自然语言处理的奠基者，贾里尼克教授成功地将数学原理应用于自然语言处理领域中，他的一生富于传奇色彩。

1　早年生活

每当弗莱德和我谈起各自少年时的教育，我们都同意这样几个观点。首先，小学生和中学生其实没有必要花那么多时间读书，而他们的社会经验、生活能力以及在那时树立起的志向将帮助他们的一生。第二，中学阶段花很多时间比同伴多读的课程，上大学以后用很短时间就能读完，因为在大学阶段，人的理解力要强得多。举个例子，在中学需要花500小时才能学会的内容，在大学可能花100小时就够了。因此，一个学生在中小学阶段建立的那一点点优势在大学很快就会丧失殆尽。第三，学习（和教育）是持续一辈子的过程，很多中学成绩优异的亚裔学生进人名校后表现明显不如那些出于兴趣而读书的美国同伴，因为前者持续学习的动力不足。第四，书本的内容可以早学，也可以晚学，但是错过了成长阶段却是无法补回来的。（因此，少年班的做法不足取。）现在中国的好学校里，恐怕百分之九十九的孩子在读书上花的时间都比我当时要多，更比贾里尼克要多得多，但是这些孩子今天可能有百分之九十九在学术上的建树不如我，更不如贾里尼克。这实在是教育的误区。

2　从水门事件到莫妮卡·莱温斯基

贾里尼克和波尔、库克以及拉维夫的另一大贡献是BCJR算法，这是今天数字通信中应用最广的两个算法之一（另一个是维特比算法）。有趣的是，这个算法发明了20年后，才得以广泛应用。于是IBM把它列为IBM有史以来对人类的最大贡献之一，并贴在加州阿莫顿实验室（Amaden Research Labs）的墙上。遗憾的是BCJR四个人已经全部离开IBM，有一次IBM的通信部门需要用这个算法，还得从斯坦福大学请一位专家去讲解，这位专家看到IBM橱窗里的成就榜，感慨万分。

3　一位老人的奇迹

在贾里尼克到约翰·霍普金斯大学以前，这所以医学院闻名于世的大学在工程领域学科趋于老化，早已经没有了第二次世界大战前堪与麻省理工学院或者加州理工学院比肩的可能，也完全没有语音识别和自然语言处理这样的新兴学科。贾里尼克从头开始，在短短两三年内就将CLSP 变成世界一流的研究中心。他主要做了两件大事，两件小事。两件大事是，首先，从美国政府主管研究的部门那里申请到了很多研究经费，然后，每年夏天，他用一部分经费，邀请世界上20一30名顶级的科学家和学生到CLSP一起工作，使得CLSP成为世界上语音和语言处理的中心之一。两件小事是，首先，他招募了一批当时很有潜力的年轻学者，比如今天在自然语言处理方面颇负盛名的雅让斯基和今天eBay主管研究的副总裁布莱尔。第二，他利用自己的影响力，在暑期把他的学生派到世界上最好的公司去实习，通过这些学生的优异表现，树立起CLSP在培养人才方面的声誉。10多年后，由于国家安全的需要，美国政府决定在一所一流大学里建立一个信息处理的国家级研究中心（Center of Excellence），贾里尼克领导的约翰·霍普金斯大学的科学家们，在竞标中击败他们在学术界的老对手麻省理工学院和卡内基一梅隆大学，将这个中心落户到约翰·霍普金斯大学，确立了他在这个学术领域的世界级领导地位。

贾里尼克治学极为严谨，对学生要求也极严。他淘汰学生的比例极高，即使留下来的，毕业时间也极长。但是，另一方面，贾里尼克也千方百计利用自己的影响力为学生的学习和事业提供便利。贾里尼克为组里的每一位学生提供从进组第一天到离开前最后一天全部的学费和生活费。他还为每一位学生联系实习机会，并保证每位学生在博士生阶段至少在大公司实习一次。从他那里拿到博士学位的学生，全部任职于著名实验室，比如IBM、微软、AT&T和Google的实验室。为了提高外籍学生的英语水平，贾里尼克自己出资为他们请私人英语教师。

贾里尼克教授桃李满天下，这里面包括他的学生、过去的下属以及在学术界众多沿袭他的研究方法的晚辈，比如Google研究院的院长诺威格（Peter Norvig）和费尔南多·皮耶尔（Fernando Pereira），这些人分布在世界上主要的大学和公司的研究所，逐渐形成了一个学派。而贾里尼克是这个学派的精神领袖。

贾里尼克教授在学术上给我最大的帮助就是提高了我在学术上的境界。他告诉我最多的是：什么方法不好。在这一点上与股神巴菲特给和他吃饭的投资人的建议有异曲同工之处。巴菲特和那些投资人讲，你们都非常聪明，不需要我告诉你们做什么，我只需要告诉你们不要去做什么（这样可以少犯很多错误），这些不要做的事情，是巴菲特从一生的经验教训中得到的。贾里尼克会在第一时间告诉我什么方法不好，因为在IBM 时他和他的同事吃过这方面的亏。至于什么方法好，他相信我比他强，自己能找到。所以他节省了我很多可能做无用功的时间。同时，他考虑问题的方法让我终身受益。

第8章　简单之美——布尔代数和搜索引擎

布尔代数虽然非常简单，却是计算机科学的基础，它不仅把逻辑和数学合二为一，而且给了我们一个全新的视角看待世界，开创了数字化时代。

在接下来的几章里，我们会介绍与搜索有关的技术。几年前，当这个系列在谷歌黑板报上登出时，很多读者都很想通过它知道Google的独门搜索技术，对我只讲述简单的原理感到很失望。这次，我可能还是要让一些读者失望了，因为我依然不会讲得很深。主要有这样几个原因，首先我希望这本书的读者是大众，而不仅仅是搜索引擎公司的工程师。对于前者，帮助他们了解数学在工程中的作用，远比了解与他们的工作无关的算法要有意义得多。第二，技术分为术和道两种，具体的做事方法是术，做事的原理和原则是道。这本书的目的是讲道而不是术。很多具体的搜索技术很快会从独门绝技到普及，再到落伍，追求术的人一辈子工作很辛苦。只有掌握了搜索的本质和精髓才能永远游刃有余。第三，很多希望我介绍“术”的人是想走捷径。但是真正做好一件事没有捷径，离不开一万小时的专业训练和努力。做好搜索，最基本的要求是每天分析 10一20 个不好的搜索结果，累积一段时间才会有感觉。我在Google改进搜索质量的时候每天分析的搜索数量远不止这个，Google的搜索质量第一技术负责人阿米特·辛格（Amit Singhal）至今依然经常分析那些不好的搜索结果。但是，很多做搜索的工程师（美国的、中国的都有）都做不到这一点，他们总是指望靠一个算法、一个模型就能毕其功于一役，而这是不现实的。

现在我们回到搜索引擎这个话题。搜索引擎的原理其实非常简单，建立一个搜索引擎大致需要做这样几件事：自动下载尽可能多的网页；建立快速有效的索引；根据相关性对网页进行公平准确的排序。所以我到了腾讯以后，就把搜搜所有的搜索产品都提炼成下载、索引和排序这三种基本服务。这就是搜索的“道”。所有的搜索服务都可以在这三个基本服务的基础上很快实现，这就是搜索的“术”。 在腾讯内部升级搜索引擎时，首先要改进和统一的就是所有搜索业务的索引，否则提高搜索质量就如同浮沙建塔一样不稳固。同样，我们在这本书中介绍搜索，也是从索引出发，因为它最基础，也最重要。

1　布尔代数

读者也许会问，这么简单的理论能解决什么实际问题。和布尔同时代的数学家们也有同样的疑问。事实上，在布尔代数提出后80多年里，它确实没有什么像样的应用，直到1938年香农在他的硕士论文中指出用布尔代数来实现开关电路，才使得布尔代数成为数字电路的基础。所有的数学和逻辑运算，加、减、乘、除、乘方、开方，等等，全都能转换成二值的布尔运算。正是依靠这一点，人类用一个个开关电路最终“搭出” 电子计算机。我们在第一章讲到，数学的发展实际上是不断地抽象和概括的过程，这些抽象了的方法看似离生活越来越远，但是它们最终能找到适用的地方，布尔代数便是如此。

……

布尔代数对于数学的意义等同于量子力学对于物理学的意义，它们将我们对世界的认识从连续状态扩展到离散状态。在布尔代数的“世界”里，万物都是可以量子化的，从连续的变成一个个分离的，它们的运算“与、或、非”也就和传统的代数运算完全不同了。现代物理的研究成果表明，我们的世界实实在在是量子化的而不是连续的。我们的宇宙的基本粒子数目是有限的，而且远比古高尔（googol）要小得多。

2　索引

大部分使用搜索引擎的人都会吃惊为什么它能在零点零几秒内找到成千上万甚至上亿的搜索结果。显然，如果是扫描所有的文本，计算机扫描的速度再快也不可能做到这一点，这里面一定暗藏技巧。这个技巧就是建索引。这就如同我们科技读物末尾的索引，或者图书馆的索引。 Google有一道面试产品经理的考题，就是“如何向你的奶奶解释搜索引擎”。大部分候选人都是试图从互联网、搜索等产品的技术层面给出解释，如此，这道题基本通不过。好的回答是拿图书馆的索引卡片做类比。每个网站就像图书馆里的一本书，我们不可能在图书馆书架上一本本地找，而是要通过搜索卡片找到它的位置，然后直接去书架上拿。

……

随着互联网上内容的增加，尤其是互联网2.0时代，用户产生的内容越来越多，即使是Google这样的服务器数量近乎无限的公司，也感到了数据增加带来的压力。因此，需要根据网页的重要性、质量和访问的频率建立常用和非常用等不同级别的索引。常用的索引需要访问速度快，附加信息多，更新也要快；而非常用的要求就低多了。但是不论搜索引擎的索引在工程上如何复杂，原理上依然非常简单，即等价于布尔运算。

小结

布尔代数非常简单，但是对数学和计算机发展的意义重大，它不仅把逻辑和数学合二为一，而且给了我们一个看待世界的全新视角，开创了今天数字化的时代。在此，借用伟大的科学家牛顿的一句话来结束这一章，“（人们）发觉真理在形式上从来是简单的，而不是复杂和含混的。”（Truth is ever to be found in simplicity, and not in the multiplicity and confusion of things.)

第9章　图论和网络爬虫

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

离散数学是当代数学的一个重要分支，也是计算机科学的数学基础。它包括数理逻辑、集合论、图论和近世代数四个分支。数理逻辑基于布尔运算，前面已经介绍过了。这里介绍图论和互联网自动下载工具网络爬虫之间的关系。顺便提一句，用Google Trends来搜索一下“离散数学”这个词，可以发现不少有趣的现象。比如，武汉、西安、合肥、南昌、南京、长沙和北京这些城市对这一数学主题最有兴趣，除了南昌，其他城市恰好是中国在校大学生人数较多的一些城市。

第8章谈到了如何建立搜索引擎的索引，那么如何自动下载互联网所有的网页呢？这需要用到图论中的遍历（Traverse）算法。

1　图论

2　网络爬虫

现在看看图论的遍历算法和搜索引擎的关系。互联网虽然很复杂，但是说穿了其实就是一张大图而已一可以把每一个网页当作一个节点，把那些超链接（Hyperlinks）当作连接网页的弧。很多读者可能已经注意到，网页中那些带下划线的蓝色文字背后其实藏着对应的网址，当你点击时，浏览器通过这些隐含的网址跳转到相应的网页。这些隐含在文字背后的网址称为“超链接”。有了超链接，我们可以从任何一个网页出发，用图的遍历算法，自动地访问到每一个网页并把它们存起来。完成这个功能的程序叫作网络爬虫（Web Crawlers），有些文献也称之为“机器人”（Robot）。世界上第一个网络爬虫是由麻省理工学院的学生马休·格雷（Matthew Gray）在1993年写成的。他给自己的程序起了个名字叫“互联网漫游者”（WWW Wanderer）。以后的网络爬虫尽管越写越复杂，但原理是一样的。

我们来看看网络爬虫如何下载整个互联网。假定从一家门户网站的首页出发，先下载这个网页，然后通过分析这个网页，可以找到页面里的所有超链接，也就等于知道了这家门户网站首页所直接链接的全部网页，诸如腾讯邮件、腾讯财经、腾讯新闻等。接下来访问、下载并分析这家门户网站的邮件等网页，又能找到其他相连的网页。让计算机不停地做下去，就能下载整个的互联网。当然，也要记载哪个网页下载过了，以免重复。在网络爬虫中，人们使用一种“哈希表”（Hash Table，也叫“散列表”）而不是一个记事本记录网页是否下载过的信息。

现在的互联网非常庞大，不可能通过一台或几台计算机服务器就能完成下载任务。比如Google在2013年时整个索引大约有10000亿个网页，即使更新最频繁的基础索引也有100亿个网页，假如下载一个网页需要一秒钟，那么下载这100亿个网页则需要317年，如果下载10000亿个网页则需要32000年左右，是我们人类有文字记载历史的6倍时间。因此，一个商业的网络爬虫需要有成千上万个服务器，并且通过高速网络连接起来。如何建立起这样复杂的网络系统，如何协调这些服务器的任务，就是网络设计和程序设计的艺术了。

3　延伸阅读：图论的两点补充说明

3.2构建网络爬虫的工程要点

“如何构建一个网络爬虫”是我在Google最常用的一道面试题。因为我经常使用，一些面试者其实知道这个事实。但我还是继续使用，而且仍能有效地考察出一个候选人的计算机科学理论基础、算法能力及工程素养。这道题的妙处在于它没有完全对和错的答案，但是有好和不好、可行和不可行的答案，而且可以不断地往深处问下去。一个好的候选人不需要做过网络爬虫也能很好地回答这道题，而那些仅仅有执行能力的三流工程师，即使在做网络爬虫的工作，对里面的很多地方也不会考虑周全。

网络爬虫在工程实现上要考虑的细节非常多，其中大的方面有这样几点。

首先，用BFS还是DFS？

虽然从理论上讲，这两个算法（在不考虑时间因素的前提下）都能够在大致相同的时间里“爬下”整个“静态”互联网上的内容，但是工程上的两个假设一不考虑时间因素，互联网静态不变，都是现实中做不到的。搜索引擎的网络爬虫问题更应该定义成“如何在有限时间里最多地爬下最重要的网页”。显然各个网站最重要的网页应该是它的首页。在最极端的情况下，如果爬虫非常小，只能下载非常有限的网页，那么应该下载的是所有网站的首页，如果把爬虫再扩大些，应该爬下从首页直接链接的网页（就如同和北京直接相连的城市），因为这些网页是网站设计者自认为相当重要的网页。在这个前提下，显然BFS明显优于DFS。事实上在搜索引擎的爬虫里，虽然不是简单地采用BFS，但是先爬哪个网页，后爬哪个网页的调度程序，原理上基本上是BFS。

那么是否DFS就不使用了呢？也不是这样的。这跟爬虫的分布式结构以及网络通信的握手成本有关。所谓“握手”就是指下载服务器和网站的服务器建立通信的过程。这个过程需要额外的时间（Overhead Time），如果握手的次数太多，下载的效率就降低了。实际的网络爬虫都是一个由成百上千甚至成千上万台服务器组成的分布式系统。对于某个网站，一般是由特定的一台或者几台服务器专门下载。这些服务器下载完一个网站，然后再进人下一个网站，而不是每个网站先轮流下载5%，然后再回过头来下载第二批，这样可以避免握手的次数太多。要是下载完第一个网站再下载第二个，那么这又有点像DFS，虽然下载同一个网站（或者子网站）时，还是需要用BFS的。

总结起来，网络爬虫对网页遍历的次序不是简单的BFS或者DFS，而是有一个相对复杂的下载优先级排序的方法。管理这个优先级排序的子系统一般称为调度系统（Scheduler），由它来决定当一个网页下载完成后，接下来下载哪一个。当然在调度系统里需要存储那些已经发现但是尚未下载的网页的URL，它们一般存在一个优先级队列（Priority Queue）里。而用这种方式遍历整个互联网，在工程上和BFS更相似。因此，在爬虫中， BFS的成分多一些。

第二，页面的分析和URL的提取。

在上一节中提到，当一个网页下载完成后，需要从这个网页中提取其中的URL，把它们加人到下载的队列中。这个工作在互联网的早期不难，因为那时的网页都是直接用HTML语言书写的。那些URL都以文本的形式放在网页中，前后都有明显的标识，很容易提取出来。但是现在很多URL的提取就不那么直接了，因为很多网页如今是用一些脚本语言（比如JavaScript）生成的。打开网页的源代码，URL不是直接可见的文本，而是运行这一段脚本后才能得到的结果。因此，网络爬虫的页面分析就变得复杂很多，它要模拟浏览器运行一个网页，才能得到里面隐含的URL。有些网页的脚本写得非常不规范，以至于解析起来非常困难。可是，这些网页还是可以在浏览器中打开，说明浏览器可以解析。因此，需要做浏览器内核的工程师来写网络爬虫中的解析程序，可惜出色的浏览器内核工程师在全世界数量并不多。因此，若你发现一些网页明明存在，但搜索引擎就是没有收录，一个可能的原因是网络爬虫中的解析程序没能成功解析网页中不规范的脚本程序。

第三，记录哪些网页已经下载过的小本本——URL表。

在互联网上，一个网页可能被多个网页中的超链接所指向，即在互联网这张大图上，有很多弧（链接）可以走到这个节点（网页）。这样在遍历互联网这张图时，这个网页可能被多次访问到。为了防止一个网页被下载多次，我们可以用一个哈希表记录哪些网页已经下载过。再遇到这个网页时，我们就可以跳过它。采用哈希表的好处是，判断一个网页的 URL是否在表中，平均只需一次（或者略多的）查找。当然，如果遇到还未下载的网页，除了下载该网页，还要适时将这个网页的URL存人哈希表中，这个操作对哈希表来讲也非常简单。在一台下载服务器上建立和维护一张哈希表并不是难事。但是如果同时有上千台服务器一起下载网页，维护一张统一的哈希表就不那么简单了。首先，这张哈希表会大到一台服务器存储不下。其次，由于每个下载服务器在开始下载前和完成下载后都要访问和维护这张表，以免不同的服务器做重复的工作，这个存储哈希表的服务器的通信就成了整个爬虫系统的瓶颈。如何消除这个瓶颈是我经常考应聘者的试题。

这里有各种解决办法，没有绝对正确的，但是却也有好坏之分。好的方法一般都采用了这样两个技术：首先明确每台下载服务器的分工，也就是说在调度时一看到某个URL就知道要交给哪台服务器去下载，以免很多服务器都要重复判断某个URL是否需要下载。然后，在明确分工的基础上，判断URL是否下载就可以批处理了，比如每次向哈希表（一组独立的服务器）发送一大批询问，或者每次更新一大批哈希表的内容。这样通信的次数就大大减少了。

小结

在图论出现后的很长时间里，现实世界中图的规模都是在几千个节点以内（比如公路图、铁路图等）。那时候，图的遍历比较简单，因此在工业界没有多少人专门研究这个问题。过去，即使是计算机专业的学生，大部分人也体会不到这个领域的研究有什么实际用处，因为大家在工作中可能永远用不上。但是随着互联网的出现，图的遍历方法一下子有了用武之地。很多数学方法就是这样，看上去没有什么实际用途，但是随着时间的推移会突然派上大用场。这恐怕是世界上还有很多人毕生研究数学的原因。

第10章　PageRank——Google的民主表决式网页排名技术

网页排名技术PageRank是早期Google的杀手锏，它的出现使得网页搜索的质量上了一个大的台阶。它背后的原理是图论和线性代数的矩阵运算。

对于大部分用户的查询，今天的搜索引擎，都会返回成千上万条结果，那么应该如何排序，把用户最想看到的结果排在前面呢？这个问题很大程度上决定了搜索引擎的质量。我们在这一章和下一章将回答这个问题。总的来讲，对于一个特定的查询，搜索结果的排名取决于两组信息：关于网页的质量信息（Quality），以及这个查询与每个网页的相关性信息（Relevance）。这一章介绍衡量网页质量的方法，下一章介绍度量搜索关键词和网页相关性的方法。

1　PageRank算法的原理

在互联网上，如果一个网页被很多其他网页所链接，说明它受到普遍的承认和信赖，那么它的排名就高。这就是PageRank的核心思想。当然 Google的PageRank算法实际上要复杂得多。比如说，对来自不同网页的链接区别对待，因为那些排名高的网页的链接更可靠，于是要给这些链接以较大的权重。这就好比在现实世界中股东大会里的表决，要考虑每个股东的表决权（Voting Power），拥有20%表决权的股东和拥有1%表决权的股东，对最后的表决结果的影响力明显不同。PageRank算法考虑了这个因素，即网页排名高的网站贡献的链接权重大。

……

虽然佩奇和布林不强调这个算法中谁都贡献了什么思想，但是据我了解，上述想法应该来自于佩奇。接下来的问题是X1、X2、X3、X4的权重分别是多少，如何度量。佩奇认为，应该是这些网页本身的网页排名。现在麻烦来了，计算搜索结果的网页排名过程中需要用到网页本身的排名，这不成了“先有鸡还是先有蛋”的问题了吗？

破解这个怪圈的应该是布林。他把这个问题变成了一个二维矩阵相乘的问题，并用选代的方法解决了这个问题。他们先假定所有网页的排名是相同的，并且根据这个初始值，算出各个网页的第一次选代排名，然后再根据第一次选代排名算出第二次的排名。他们两个人从理论上证明了不论初始值如何选取，这种算法都能保证网页排名的估计值能收敛到排名的真实值。值得一提的事，这种算法不需要任何人工干预。

理论问题解决了，又遇到实际问题。因为互联网上网页的数量是巨大的，上面提到的二维矩阵从理论上讲有网页数量的二次方这么多个元素。假定有十亿个网页，那么这个矩阵就有一百亿亿个元素。这么大的矩阵相乘，计算量是非常大的。佩奇和布林两个人利用稀疏矩阵计算的技巧，大大简化了计算量，并实现了这个网页排名算法。

随着互联网网页数量的增长，PageRank的计算量越来越大，必须利用多台服务器才能完成。Google早期时，PageRank计算的并行化是半手工、半自动的，这样更新一遍所有网页的PageRank的周期很长。2003年， Google的工程师迪恩（Jeffrey Dean）和格麦瓦特（Sanjay Ghemawat）发明了并行计算工具MapReduce，PageRank的并行计算完全自动化了，这就大大缩短了计算时间，使网页排名的更新周期比以前短了许多。

我到Google后，佩奇和我们几个新员工座谈时，讲起他当年和布林是怎么想到网页排名算法的。他说：“当时我们觉得整个互联网就像一张大的图，每个网站就像一个节点，而每个网页的链接就像一个弧。我想，互联网可以用一个图或者矩阵描述，我也许可以用这个发现做篇博士论文。”他和布林就这样发明了PageRank算法。PageRank中的Page一词在英文里既有网页、书页等意思，也是佩奇的姓氏。我们开玩笑讲，为什么这个算法叫“佩奇”算法不叫“布林”算法？

网页排名算法的高明之处在于它把整个互联网当作一个整体来对待。这无意中符合了系统论的观点。相比之下，以前的信息检索大多把每一个网页当作独立的个体对待，大部分人当初只注意了网页内容和查询语句的相关性，忽略了网页之间的关系。虽然在佩奇和布林同时代也有一些人在思考如何利用网页之间的联系来衡量网页的质量，但只是摸到一些皮毛，找到一些拼凑的办法，都没有从根本上解决问题。

2　延伸阅读：PageRank的计算方法

网页排名的计算主要是矩阵相乘，这种计算很容易分解成许多小任务，在多台计算机上并行处理。矩阵相乘具体的并行化方法会在第29章介绍Google并行计算工具MapReduce时再作讨论。

小结

今天，Google搜索引擎比最初复杂、完善了许多。但是PageRank在 Google所有算法中依然是至关重要的。在学术界，这个算法被公认为是文献检索中最大的贡献之一，并且被很多大学列为信息检索课程（Information Retrieval）的内容。佩奇也因为这个算法在30岁时当选为美国工程院院士，是继乔布斯和盖茨之后又一位当选院士的缀学生。由于PageRank算法受到专利保护，它带来了两个结果。首先，其他搜索引擎开始时都比较遵守游戏规则，不去侵犯它，这对当时还很弱小的 Google是一个很好的保护。第二，它使得斯坦福大学拥有了超过1%的 Google股票，收益超过10亿美元。

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

确定网页和查询的相关性是网页搜索的根本问题，其中确定查询中每个关键词的重要性有多高是关键。TF-IDF是目前通用的关键词重要性的度量，其背后的原理是信息论。

我们在前面几章里介绍了如何自动下载网页、建立索引和度量网页的质量（PageRank）。接下来我们来讨论针对某个查询，如何找到最相关的网页。了解了这三个方面的知识，有一定编程基础的读者就可以写出一个简单的搜索引擎了，比如为自己所在的学校或院系搭建一个小型搜索引擎。

2007年我为Google黑板报写这一节时，技术和算法的重要性依然高于数据，因此确定网页和查询的相关性主要依靠算法。但是今天，由于商业搜索引擎已经有了大量的用户点击数据，因此，对搜索相关性贡献最大的是根据用户对常见搜索点击网页的结果得到的概率模型。如今，影响搜索引擎质量的诸多因素，除了用户的点击数据之外，都可以归纳成下面四大类。

1. 完备的索引。俗话说巧妇难为无米之炊，如果一个网页不在索引中，那么再好的算法也找不到。
2. 对网页质量的度量，比如PageRank。当然，正如在前面一章中介绍的那样，现在来看，PageRank的作用比10年前已经小了很多。今天，对网页质量的衡量是全方位的，比如对网页内容权威性的衡量，一些八卦网站的PageRank可能很高，但是它们的内容权威性很低。
3. 用户偏好。这一点也很容易理解，因为不同用户的喜好不同，因此一个好的搜索引擎会针对不同用户，对相同的搜索给出不同的排名。
4. 确定一个网页和某个查询的相关性的方法。这就是我们这一章要谈论的内容。

我们还是看看前面章节中介绍过的例子，比如查找关于“原子能的应用” 的网页。第一步是在索引中找到包含这三个词的网页（详见第8章关于布尔运算的内容）。现在任何一个搜索引擎能提供几十万甚至是上百万个与这个查询词组多少有点关系的网页，比如Google返回了大约一千万个结果。那么哪个应该排在前面呢？显然应该把网页本身质量好，且与查询关键词“原子能的应用”相关性高的网页排在前面。第10章已经介绍了如何度量网页的质量。这里介绍另外一个关键技术：如何度量网页和查询的相关性。

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

TF-IDF（Term Frequency / Inverse Document Frequency）的概念被公认为信息检索中最重要的发明。在搜索、文献分类和其他相关领域有着广泛的应用。讲起TF-IDF的历史蛮有意思。IDF的概念最早是剑桥大学的斯巴克·琼斯（Karen Sparck Jones）提出来的。1972年，斯巴克· 琼斯在一篇题为“关键词特殊性的统计解释和它在文献检索中的应用” 的论文中提出IDF的概念。……

……

学者们已经发现并指出，所谓IDF的概念就是一个特定条件下关键词的概率分布的交叉熵（Kullback-Leibler Divergence）（详见本书第6章“信息的度量和作用”）。这样，关于信息检索相关性的度量，又回到了信息论。

现在的搜索引擎对TF-IDF进行了不少细微的优化，使得相关性的度量更加准确了。当然，对有兴趣写一个搜索引擎的爱好者来讲，使用TF-IDF 就足够了。如果结合网页排名（PageRank）算法，那么给定一个查询，有关网页的综合排名大致由相关性和网页排名的乘积决定。

2　延伸阅读：TF-IDF的信息论依据

小结

TF-IDF是对搜索关键词的重要性的度量，并且具备很强的理论根据。因此，即使是对搜索不是很精通的人，直接采用TF-IDF，效果也不会太差。现在各家搜索引擎对关键词重要性的度量，都在TF-IDF的基础上做了一定的改进和微调。但是，在原理上与TF-IDF相差不远。

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

地图与本地搜索中要用到有限状态机和动态规划技术。这两项技术是机器智能和机器学习的工具，它们的应用非常广泛，还包括语音识别、拼写和语法纠错、拼音输入法、工业控制和生物的序列分析等。

2007年，第一次在谷歌黑板报上写“数学之美”系列时，本地搜索和服务还不是很普及，智能手机不仅数量有限，而且完全没有结合本地信息。地图服务的流量与网页搜索相比，只是众多垂直搜索的一部分。今天，本地生活服务变得越来越重要，而确认地点、查看地图、查找路线等依然是本地生活服务的基础。这里为了减少章节的数量，我将有限状态机这个系列和动态规划的一部分合并，组成围绕地图和本地生活搜索的一章。

……

智能手机的定位和导航功能，其实只有三项关键技术：第一，利用卫星定位，这一点传统的导航仪都能做到，不做介绍；第二，地址的识别，在本章第一节中介绍；第三，根据用户输入的起点和终点，在地图上规划最短路线或者最快路线，在本章第二节中介绍。

1　地址分析和有限状态机

所幸的是，地址的文法是上下文有关文法中相对简单的一种，因此有许多识别和分析的方法，但最有效的是有限状态机。

有限状态机是一个特殊的有向图（参见本书第9章中与图论相关的内容），它包括一些状态（节点）和连接这些状态的有向弧。图12.1所示的是一个识别中国地址的有限状态机的简单例子。

使用有限状态机识别地址，关键要解决两个问题，即通过一些有效的地址建立状态机，以及给定一个有限状态机后，地址字串的匹配算法。好在这两个问题都有现成的算法。有了关于地址的有限状态机后，就可以用它分析网页，找出网页中的地址部分，建立本地搜索的数据库。同样，也可以对用户输入的查询进行分析，挑出其中描述地址的部分，当然，剩下的关键词就是用户要找的内容。比如，对于用户输入的“北京市双清路附近的酒家”，Google本地会自动识别出地址“北京市双清路”和要找的对象“酒家”。

上述基于有限状态机的地址识别方法在实用中会有一些问题：当用户输入的地址不太标准或者有错别字时，有限状态机会束手无策，因为它只能进行严格匹配。（其实，有限状态机在计算机科学中早期的成功应用是在程序语言编译器的设计中。一个能运行的程序在语法上必须是没有错的，所以不需要模糊匹配。而自然语言则很随意，无法用简单的语法描述。）

为了解决这个问题，我们希望看到可以进行模糊匹配，并给出一个字串为正确地址的可能性。为了实现这一目的，科学家们提出了基于概率的有限状态机。这种基于概率的有限状态机和离散的马尔可夫链（详见前面关于马尔可夫模型的章节）基本上等效。

在上个世纪80年代以前，尽管有不少人使用基于概率的有限状态机，但都是为自己的应用设计专用的有限状态机的程序。上个世纪90年代以后，随着有限状态机在自然语言处理上的广泛应用，不少科学家致力于编写通用的有限状态机程序库。其中，最成功的是前AT&T实验室的三位科学家，莫瑞（Mehryar Mohri）、皮耶尔（Fernando Pereira）和瑞利（Michael Riley）。他们三人花了很多年时间，编写成一个通用的基于概率的有限状态机C语言工具库。由于AT&T有对学术界免费提供各种编程工具的好传统，他们三人也把自已多年的心血拿出来和同行们共享。可惜好景不长，AT&T实验室风光不再，这三个人都离开了AT&T，莫瑞成了纽约大学的教授；皮耶尔先当了宾夕法尼亚大学的计算机系主任，而后成为Google的研究总监；而瑞利直接成为Google的研究员。有一段时间， AT&T实验室的新东家不再免费提供有限状态机C语言工具库。虽然此前莫瑞等人公布了他们的详细算法”，但是省略了实现的细节。因此，在学术界，不少科学家能够重写同样功能的工具库，但是很难达到AT&T 工具库的效率（即运算速度），这一度是一件令人遗憾的事。但是近年来，随着开源软件在世界上的影响力越来越大，AT&T又重新开放了这个工具的源代码。有限状态机的程序不是很好写，它要求编程者既懂得里面的原理和技术细节，又要有很强的编程能力，因此建议大家直接采用开源的代码就好。

值得一提的是，有限状态机的用途远不止于对地址这样的状态序列进行分析，而是非常广泛的。在Google新一代的产品中，有限状态机的一个典型的应用是Google Now一一个在智能手机上的基于个人信息的服务软件。Google Now背后的核心是一个有限状态机，它会根据个人的地理位置信息、日历和一些其他信息（对应于有限状态机里面的状态），以及用户当前语音或者文字输入，回答个人的问题，提供用户所查找的信息，或者提供相应的服务（比如打开地图进行导航，拨打电话等）。Google Now的引擎和AT&T的有限状态机工具库从功能上讲完全等价。

2　全球导航和动态规划

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

……

所有的导航系统都采用了动态规划（Dynamic Programming，DP）的办法，这里面的Programming一词在数学上的含义是“规划”，不是计算机里的“编程”。动态规划的原理其实很简单。

……

正确的数学模型可以将一个计算量看似很大的问题的计算复杂度大大降低。这便是数学的妙用。

3　延伸阅读：有限状态传感器

有限状态机的应用远不止地址的识别，今天的语音识别解码器基本上是基于有限状态机的原理。另外，它在编译原理、数字电路设计上有着非常重要的应用，因此在这里给出有限状态机严格的数学模型。

……

有限状态机在语音识别和自然语言理解中起着非常重要的作用，不过这些领域使用的是一种特殊的有限状态机一加权的有限状态传感器（Weighted Finite State Transducer，简称WFST）。下面介绍WFST及其构造和用法。

小结

有限状态机和动态规划的应用非常广泛，远远不止识别地址、导航等地图服务相关领域。它们在语音识别、拼写和语法纠错、拼音输入法、工业控制和生物的序列分析等领域都有着极其重要的应用。其中在拼音输入法中的应用后面还要再介绍。

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

在所有轻武器中最有名的是AK-47冲锋枪，因为它从不卡壳，不易损坏，可在任何环境下使用，可靠性好，杀伤力大并且操作简单。Google的产品就是按照上述原则设计的。

我认为，在计算机科学领域，一个好的算法应该像AK-47冲锋枪那样：简单、有效、可靠性好而且容易读懂（或者说易操作），而不应该是故弄玄虚。Google Fellow、美国工程院院士阿米特·辛格博士（Amit Singhal）就是GoogleAK-47的设计者，Goolge内部的排序算法 Ascorer 里面的A便是他的名字首字母。

……

在Google，辛格一直坚持寻找简单有效的解决方案，因为他奉行简单的哲学。但是这种做法在Google这个人才济济的公司里常常招人反对，因为很多资深的工程师倾向于低估简单方法的有效性。2003一2004年， Google从世界上很多知名实验室和大学，比如MITRE、AT&T实验室和IBM实验室，招揽了不少自然语言处理的科学家。不少人试图用精确而复杂的办法对辛格设计的各种“AK-47”加以改进，后来发现几乎任何时候，辛格的简单方法都接近最优解决方案，而且还快得多。这些“徒劳者” 中包括一些世界级的人物，比如乌迪·曼波（Udi Manber）等人。

……

当然，辛格之所以总是能找到那些简单有效的方法，不是靠直觉，更不是撞大运，这首先是靠他丰富的研究经验。辛格早年师从于搜索大师萨尔顿（Salton）教授，毕业后就职于AT&T实验室。在那里，他和两个同事半年就搭建了一个中等规模的搜索引擎，这个引擎索引的网页数量虽然无法和商用引擎相比，但是准确性却非常好。早在AT&T，辛格就对搜索问题的各个细节进行了仔细的研究，他的那些简单而有效的解决方案，常常是深思熟虑去伪存真的结果。其次，辛格坚持每天要分析一些搜索结果不好的例子，以掌握第一手的资料，即使在他成为Google Fellow以后，依旧如此。这一点，非常值得从事搜索研究的年轻工程师学习。事实上，我发现中国大部分做搜索的工程师在分析不好的结果上花的时间远比功成名就的辛格要少。

辛格非常鼓励年轻人要不怕失败，大胆尝试。有一次，一位刚毕业不久的工程师因为把带有错误的程序推出到Google的服务器上而惶惶不可终日。辛格安慰她说，你知道，我在Google犯的最大一次错误是曾经将所有网页的相关性得分全部变成了零，于是所有搜索的结果全部都是随机的了。后来，这位出过错的工程师为Google开发出了很多好产品。

第14章　余弦定理和新闻的分类

计算机虽然读不懂新闻，却可以准确地对新闻进行分类。其数学工具是看似毫不相干的余弦定理。

世界上有些事情常常超乎人们的想象。余弦定理和新闻的分类看似八竿子打不着，却有着紧密的联系。具体来说，新闻的分类很大程度上依靠的是余弦定理。

2002年夏天，Google推出了自己的“新闻”服务。和传统媒体的做法不同，这些新闻不是记者写的，也不是人工编辑的，而是由计算机整理、分类和聚合各个新闻网站的内容，一切都是自动生成的。这里面的关键技术就是新闻的自动分类。

1　新闻的特征向量

2　向量距离的度量

现在把一篇篇文字的新闻变成了按词典顺序组织起来的数字（特征向量），又有了计算相似性的公式，就可以在此基础上讨论新闻分类的算法了。具体的算法分为两种情形。第一种比较简单，假定我们已知一些新闻类别的特征向量$x_1, x_2,\cdots, x_k$，那么对于任何一个要被分类的新闻$Y$，很容易计算出它和各类新闻特征向量的余弦相似性（距离），并将其归人它该去的那一类中。至于这些新闻类别的特征向量，既可以手工建立（工作量非常大而且不准确），也可以自动建立（以后会介绍）。第二种情形就比较麻烦了，即如果事先没有这些新闻类别的特征向量怎么办。我在约翰·霍普金斯大学的同学弗洛里安（Radu Florian）3和教授雅让斯基给出了一个自底向上不断合并的办法，大致思想如下。

3　延伸阅读：计算向量余弦的技巧

3.1 大数据量时的余弦计算

1. 存储中间结果
2. 计算只考虑非零元素
3. 去除虚词等无关项

3.2 位置的加权

和计算搜索相关性一样，出现在文本不同位置的词在分类时的重要性也不相同。显然，出现在标题中的词对主题的贡献远比出现在新闻正文中的重要。而即使在正文中，出现在文章开头和结尾的词也比出现在中间的词重要。在中学学习语文和大学学习英语文学时，老师都会强调这一点——阅读时要特别关注第一段和最后一段，以及每个段落的第一个句子。在自然语言处理中这个规律依然有用。因此，要对标题和重要位置的词进行额外的加权，以提高文本分类的准确性。

小结

本章介绍的这种新闻归类的方法，准确性很好，适用于被分类的文本集合在百万数量级。如果大到亿这个数量级，那么计算时间还是比较长的。对于更大规模的文本处理，我们将在下一章中介绍一种更快速但相对粗糙的方法。

第15章　矩阵运算和文本处理中的两个分类问题

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

1　文本和词汇的矩阵

在自然语言处理中，最常见的两个分类问题分别是，将文本按主题归类（比如将所有介绍奥运会的新闻归到体育类）和将词汇表中的字词按意思归类（比如将各种运动的项目名称都归成体育一类）。这两个分类问题都可以通过矩阵运算来圆满地、一次性地解决。为了说明如何用矩阵这个工具来解决这两个问题，让我们来看一看前一章中介绍的余弦定理和新闻分类的本质。

新闻分类乃至各种分类其实是一个聚类问题，关键是计算两篇新闻的相似程度。为了完成这个过程，我们要将新闻变成代表它们内容的实词，然后再变成一组数，具体说是向量，最后求这两个向量的夹角。当这两个向量的夹角很小时，新闻就相关；当两者垂直或者说正交时，新闻则无关。从理论上讲，这种算法非常漂亮。但是因为要对所有新闻做两两计算，而且要进行很多次迭代，耗时会特别长，尤其是当新闻的数量很大且词表也很大的时候。我们希望有一个办法，一次就能把所有新闻相关性计算出来。这个一步到位的办法利用的是矩阵运算中的奇异值分解（Singular Value Decomposition，简称SVD）。

……

现在剩下的唯一问题，就是如何用计算机进行奇异值分解。这时，线性代数中的许多概念，比如矩阵的特征值，以及数值分析的各种算法等就统统派上用场了。对于不大的矩阵，比如几万乘几万的矩阵，用计算机上的数学工具MATLAB就可以计算。但是更大的矩阵，比如上百万乘上百万，奇异值分解的计算量非常大，就需要很多台计算机并行处理了。虽然Google早就有了MapReduce等并行计算的工具，但是由于奇异值分解很难拆成不相关子运算，即使在Google内部以前也无法利用并行计算的优势来分解矩阵。直到2007年，Google中国（谷歌）的张智威博士带领几个中国的工程师及实习生实现了奇异值分解的并行算法，这是 Google中国对世界的一个贡献。

2　延伸阅读：奇异值分解的方法和应用场景

在文本分类中，M对应文本的数量，N对应词典大小。如果比较奇异值分解的计算复杂度和利用余弦定理计算文本相似度（一次选代）的时间，它们处于同一个数量级，但是前者不需要多次选代，因此计算时间短不少。奇异值分解的另一个大问题是存储量较大，因为整个矩阵都需要存在内 存里，而利用余弦定理的聚类则不需要。

小结

相比上一章介绍的利用文本特征向量余弦的距离自底向上的分类方法，奇异值分解的优点是能较快地得到结果（在实际应用中），因为它不需要一次次地迭代。但是用这种方法得到的分类结果略显粗糙，因此，它适合处理超大规模文本的粗分类。在实际应用中，可以先进行奇异值分解，得到粗分类结果，再利用计算向量余弦的方法，在粗分类结果的基础上，进行几次迭代，得到比较精确的结果。这样，这两个方法一先一后结合使用，可以充分利用两者的优势，既节省时间，又能获得很好的准确性。

第16章　信息指纹及其应用

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

1　信息指纹

在前面的章节中，我们讲到，一段文字所包含的信息，就是它的信息。如果对这段信息进行无损压缩编码，理论上编码后的最短长度就是它的信息。当然，实际编码长度总是要略长于它的信息熵的比特数。但是，如果仅仅要区分两段文字或者图片，则远不需要那么长的编码。任何一段信息（包括文字、语音、视频、图片等），都可以对应一个不太长的随机数，作为区别这段信息和其他信息的指纹（Fingerprint）。只要算法设计得好，任意两段信息的指纹都很难重复，就如同人类的指纹一样。信息指纹在加密、信息压缩和处理中有着广泛的应用。

……

上面那个百度网址（字符串）的信息指纹的计算方法一般分为两步。首先，将这个字符串看成是一个特殊的、很长的整数。这一步非常容易，因为所有的字符在计算机里都是按照整数来存储的。接下来就需要用到一个产生信息指纹的关键算法：伪随机数产生器算法（Pseudo-Random Number Generator，简称PRNG），通过它将任意很长的整数转换成特定长度的伪随机数。最早的PRNG算法是由计算机之父冯·诺依曼提出来的。他的办法非常简单，就是将一个数的平方掐头去尾，取中间的几位数。比如一个四位的二进制数1001（相当于十进制的9），其平方为01010001（十进制的81），掐头去尾，剩下中间的4位0100。当然这种方法产生的数字并不很随机，也就是说，两个不同的信息很可能有同一指纹，比如0100（十进制的4），它按照这个方法产生的指纹也是0100。现在常用的梅森旋转算法（Mersenne Twister）则要好得多。

信息指纹的用途远不止网址的消重，它的孪生兄弟是密码。信息指纹的一个特征是其不可逆性，也就是说，无法根据信息指纹推出原有信息。这种性质，正是网络加密传输所需要的。比如说，一个网站可以根据用户本地客户端的cookie识别不同用户，这个cookie就是一种信息指纹。但是网站无法根据信息指纹了解用户的身份，这样就可以保护用户的隐私。但是 cookie本身并没有加密，因此通过分析cookie还是能知道某台计算机访问了哪些网站。为了保障信息安全，一些网站（比如银行的）采用加密的 HTTPS，用户访问这些网站留下的cookie本身也需要加密。加密的可靠性，取决于是否很难人为地找到具有同一指纹的信息，比如一个黑客能否产生出某位用户的cookie。从加密的角度来讲，梅森旋转算法还不够好，因为它产生的随机数还有一定的相关性，破解一个就等于破解了一大批。

在互联网上加密要使用基于加密的伪随机数产生器（Cryptographically Secure Pseudo-Random Number Generator，CSPRNG）。常用的算法有 MD5或者SHA-1等标准，它们可以将不定长的信息变成定长的128位或者160位二进制随机数。值得一提的是，SHA-1以前被认为是没有漏洞的，现在已经被中国的王小云教授证明存在漏洞。但是大家不必恐慌，因为这和黑客能真正攻破你的注册信息还是两回事。

2　信息指纹的用途

上面一节讲述了在网络爬虫中利用信息指纹可以快速而经济（节省服务器）地判断一个网页是否已下载过。信息指纹在互联网和自然语言处理中还有非常多的应用，这里不可能（也不必要）一一列举，只是找几个有代表性的例子。

2.1集合相同的判定

利用信息指纹的方法计算的复杂度不需要额外的空间，因此是最佳方法。

类似的应用还有很多，如检测网络上的某首歌曲是否盗版别人的，只要算一算这两个音频文件的信息指纹即可。

2.2判定集合基本相同

爱思考的读者可能会挑战我：发垃圾邮件的人哪有这么傻，从两个账号发出的垃圾邮件收信人都相同？如果稍微变上一两个，上面的方法不就不起作用了吗？解决这个问题需要我们能够快速判断两个集合是否基本相同，其实只要将上面的方法稍作改动即可。

可以分别从两个账号群发的接收电子邮件地址清单（E-mail Address List）中按照同样的规则随机挑选几个电子邮件的地址，比如尾数为24的。如果它们的指纹相同，那么很有可能接收这两个账号群发邮件的电子邮件地址清单基本相同。由于挑选的数量有限，通常是个位数，因此也很容易判断是否是80%，或者90%重复。

上述判断集合基本相同的算法有很多实际的应用，比如在网页搜索中，判断两个网页是否是重复的。如果把两个网页（的正文）从头比到尾，计算时间太长，也没有必要。我们只需对每个网页挑出几个词，这些词构成网页的特征词集合，然后计算和比较这些特征集合的信息指纹即可。在两个被比较的网页中，常见的词一般都会出现，不能作为这两篇文章的特征。只出现一次的词，很可能是噪声，也不能考虑。在剩下的词中，我们知道IDF大的词鉴别能力强，因此只需找出每个网页中IDF最大的几个词，并且算出它们的信息指纹即可。如果两个网页这么计算出来的信息指纹相同，则它们基本上是相同的网页。为了充许有一定的容错能力，Google采用了一种特定的信息指纹——相似哈希（Simhash）。相似哈希的原理会在延伸阅读中介绍。

上面的算法稍作改进后还可以判断一篇文章是否抄袭了另一篇文章。具体的做法是，将每一篇文章切成小的片段，然后用上述方法挑选这些片段的特征词集合，并计算它们的指纹。只要比较这些指纹，就能找出大段相同的文字，最后根据时间先后，找到原创的和抄袭的。Google实验室利用这个原理做了一个名为CopyCat的项目，可以准确找出原文和转载（拷贝）的文章。

2.3YouTube的反盗版

Google旗下的YouTube是全球最大的视频网站，和国内的视频网站不同， YouTube自身不提供和上传任何内容，而完全由用户自己提供。这里的用户既包括专业的媒体公司，比如NBC和迪士尼，也包括个人用户。由于对后者没有太多上传视频的限制，一些人会上传专业媒体公司的内容。这件事若不解决就会动摇YouTube的生存基础。

从上百万视频中找出一个视频是否为另一个视频的盗版，并非易事。一段几分钟的视频，文件大小从几兆到几十兆，而且还是压缩的，如果恢复到每秒30帧的图像，数据量就会大得不得了。因此，没有人会直接比较两段视频来确定它们是否相似。

视频的匹配有两个核心技术，关键帧的提取和特征的提取。MPEG视频（在 NTSC制的显示器上播放）虽然每秒有30帧图像，但是每一帧之间的差异不大。（否则我们看起来就不连贯了。）一般来说，每一秒或若干秒才有一帧是完整的图像，这些帧称为关键帧。其余帧存储的只是和关键帧相比的差异值。关键帧对于视频的重要性，就如同主题词对于新闻的重要性一样。因此，处理视频图像首先是找到关键帧，接下来就是要用一组信息指纹来表示这些关键帧了。

有了这些信息指纹后，检测是否盗版就类似于比较两个集合元素是否相同了。Google收购YouTube后，由Google研究院研究图像处理的科学家们开发出的反盗版系统，效果非常好。由于可以找出相同的视频的原创和拷贝，Google制定了一个很有意思的广告分成策略：虽然所有的视频都可以插人广告，但是广告的收益全部提供给原创的视频，即使广告是插人在拷贝的视频中。这样一来，所有拷贝和上传别人的视频的网站就不可能获得收入。没有了经济利益，也就少了很多盗版和拷贝。

3　延伸阅读：信息指纹的重复性和相似哈希

3.1信息指纹重复的可能性

信息指纹是通过伪随机数产生的。既然是伪随机数，两个不同的信息就有可能产生同样的指纹。这种可能性从理论上讲确实存在，但是非常小。至于有多小，我们就在这一节中分析。

3.2 相似哈希

相似哈希是一种特殊的信息指纹，是Moses Charikar在2002年提出的，但真正得到重视是当Google在网页爬虫中使用它，并且把结果发表在 WWW会议上以后3。Charikar的论文写得比较晦涩，但相似哈希的原理其实并不复杂。下面用一个Google在下载网页时排查重复网页的例子来说明。

……

相似哈希的特点是，如果两个网页的相似哈希相差越小，这两个网页的相似性就越高。如果两个网页相同，它们的相似哈希必定相同。如果它们只有少数权重小的词不相同，其余的都相同，几乎可以肯定它们的相似哈希也会相同。值得一提的是，如果两个网页的相似哈希不同，但是相差很小，则对应的网页也非常相似。用64位的相似哈希做对比时，如果只相差一两位，那么对应网页内容重复的可能性大于80%。这样，通过记录每个网页的相似哈希，然后判断一个新网页的相似哈希是否已经出现过，可以找到内容重复的网页，就不必重复建索引浪费计算机资源了。

信息指纹的原理简单，使用方便，因此用途非常广泛，是当今处理海量数据必不可少的工具。

小结

所谓信息指纹，可以简单理解为将一段信息（文字、图片、音频、视频等）随机地映射到一个多维二进制空间中的一个点（一个二进制数字）。只要这个随机函数做得好，那么不同信息对应的这些点就不会重合，因此，这些二进制的数字就成了原来的信息所具有的独一无二的指纹。

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

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

1　密码学的自发时代

已故的美国情报专家雅德利（Herbert Osborne Yardley，1889—1958）二战时曾经在重庆帮助中国政府破解日本的密码。他在重庆的两年里做得最成功的一件事，就是破解了日军和重庆间谍的通信密码，由此破译了几千份日军和间谍之间通信的电文，从而破获了国民党内奸“独臂海盗”为日军提供重庆气象信息的间谍案。雅德利（及一位中国女子徐贞）的工作，大大减轻了日军对重庆轰炸造成的伤害。回到美国后，雅德利写了一本书《中国黑室》（The Chinese Black Chamber）介绍这段经历，但是该书直到1983年才被获准解密并出版。从书中的内容可以了解到，当时日本在密码设计上存在严重的缺陷。日军和重庆间谍约定的密码本就是美国著名作家赛珍珠（Pearl S. Buck）获得1938年诺贝尔文学奖的《大地》（The Good Earth）一书。这本书很容易找到，接到密码电报的人只要拿着这本书就能解开密码。密码所在的页数就是一个非常简单的公式：发报日期的月数加上天数，再加上10。比如3月11日发报，密码就在第24（3+11+10）页。这样的密码设计违背了我们前面介绍的“加密函数不应该通过几个自变量和函数值就能推出函数本身”这个原则，对于这样的密码，破译一篇密文就可能破译以后全部的密文。

《中国黑室》一书还提到日军对保密的技术原理所知甚少。有一次日本在菲律宾马尼拉的使馆向外发报时，发到一半机器卡死，然后居然就照单重发一遍了事，这种同文密电在密码学上是大忌（和我们现在VPN登录用的安全密钥一样，密码机加密时，每次应该自动转一轮，以防同一密钥重复使用，因此即使是同一电文，两次发送的密文也应该是不一样的）。另外，日本外交部在更换新一代密码机时，有些距离本土较远的日本使馆因为新机器到位较晚，居然还使用老机器发送。这样就出现新老机器混用的情况，同样的内容美国会收到新老两套密文，由于日本旧的密码很多已被破解，结果新的密码一出台就毫无机密可言。总的来讲，在第二次世界大战中日本的情报经常被美国人破译，他们的海军名将山本五十六（出生时他父亲56岁，故取名五十六）也因此丧命”。我们常讲落后是要挨打的，其实不会使用数学也是要挨打的。

2　信息论时代的密码学

在第二次世界大战中，很多顶尖的科学家都开始为军方和情报部门工作。比如维纳和爱因斯坦为美军改进火炮，香农和图灵都在研究加密和解密。香农被分配到的工作是，研究如何为英国首相丘吉尔和美国的通话加密，即便通话遭德国人窃听，对方也无法得知具体内容。而图灵的任务则相反，他在研究如何解密德国人的密码机。那时，香农和图灵经常在贝尔实验室一起喝咖啡，但是出于保密需要，他们从来不谈工作，否则这两个当时最聪明的头脑一定能产生更伟大的思想。在研究加密和解密的过程中，香农提出了信息论，因此信息论可以说是情报学的直接产物。

信息论的提出为密码学的发展带来了新气象。根据信息论，密码的最高境界是敌方在截获密码后，对我方的所知没有任何增加，用信息论的专业术语讲，就是信息量没有增加。一般来讲，当密码之间分布均匀并且统计独立时，提供的信息最少。均匀分布使得敌方无从统计，而统计独立可保证敌人即使知道了加密算法，并且看到一段密码和明码后，也无法破译另一段密码。按照我的理解，这也是《暗算》里传统的破译员老陈破译了一份密报但无法推广的原因，而数学家黄依依预见到了这个结果，因为她知道敌人新的密码系统编出的密文是统计独立的。

有了信息论，密码的设计就有了理论基础，现在通用的公开密钥（即非对称加密）的方法，《暗算》里的“光复一号”密码，应该就是基于这个理论。

Diffie和Hellman在1976年的开创性论文“密码学的新方向”（New Directions in Cryptography），介绍了公钥和电子签名的方法，这是今天大多数互联网安全协议的基础。

虽然公开密钥下面有许多不同的具体加密方法，比如早期的RSA算法、 Rabin算法和后来的ElGamal算法、椭圆曲线算法（Elliptic curve），它们的基本原理非常一致，且并不复杂。这些算法都有如下共同点。

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

最后让我们看看破解这种密码的难度。首先要声明，世界上没有永远破不了的密码，关键是它能有多长时间的有效期。要破解公开密钥的加密方式，至今的研究结果表明最彻底的办法还是对大数N进行因数分解，即通过N反过来找到P和Q，这样密码就被破解了。而找P和Q目前只有一个笨办法，就是用计算机把所有可能的数字试一遍。（注意，即使是“试”，也有聪明和愚笨之分。即便是聪明的试法，也要试大量的数字。）这实际上是在拼计算机的速度，这也就是为什么P和Q都需要非常大。一种加密方法只要保证50年内计算机破解不了，也就算是满意了。前几年破解的RSA-158密码是这样被因数分解的： 39505874583265144526419767800614481996020776460304936 4541393760515793556265294506836097278424682195350935 44305870490251995655335710209799226484977949442955603 =33884958374667213943683932046721815228158303686049930 48084925840555281177×11658823406671259903148376558383 270818131012258146392600439520994131344334162924536139

公开密钥的其他算法，尤其是Rabin算法，原理上和RSA算法有很多的相似性。但是因为它们毕竞不同，破解的方法也不同。公开密钥的任何一个具体算法，彻底破解是非常难的。遗憾的是，虽然公开密钥在原理上非常可靠，但是很多加密系统在工程实现上却留下了不少漏洞。因此，很多攻击者从攻击算法转而攻击实现方法。“20年对RSA的攻击”一文分析了这种情况。

现在，让我们回到《暗算》中，黄依依第一次找的结果经过一系列计算发现无法归零，也就是说除不尽。虽然在20世纪60年代还没有公开密钥加密计算，但是编导应该是借鉴了后来密码破译的通用方法，她可能试图对一个大数N做分解，没成功。第二次计算的结果是归零了，说明她找到了N=P×Q的分解方法。当然，这件事恐怕是不能用算盘完成的，所以我觉得编导在这一点上有些夸张。另外，该电视剧还有一个讲得不清不楚的地方，就是里面提到的“光复一号”密码的误差问题。一个密码是不能有误差的，否则就是有了密钥也无法解码了。我想编导可能是指在构造密码时有些实现的漏洞，这时密码的保密性就差了很多。在前面引I用的“20年对RSA的攻击”一文中作者给出了一些在密码系统中原理严密、实现却有漏洞的例子。再有，该电视剧提到冯·诺依曼，说他是现代密码学的祖宗，这是完全弄错了，应该是香农。冯·诺依曼的贡献在于发明现代电子计算机和提出博弈论（Game Theory），和密码无关。

不管怎么样，我们今天用的所谓最可靠的加密方法，背后的数学原理其实就这么简单，一点也不神秘。无论是RSA算法、Rabin算法还是后来的ElGamal算法，无非是找几个大素数做一些乘除和乘方运算。至于今天比较热门的椭圆曲线加密，其数学原理也并不复杂，我们在后面第 31 章介绍比特币和区块链协议时会专门予以介绍。总之，就是靠着这么简单的数学原理，保证了二战后的密码几乎无法被破解。冷战时期美苏双方都投入了前所未有的精力去获得对方的情报，但是没有发生过因密码被破解而泄密的重大事件。

小结

我们在介绍信息论中谈到，利用信息可以消除一个系统的不确定性。而利用已经获得的信息情报来消除一个情报系统的不确定性就是解密。密码系统具体的设计方法属于术的范畴，可以有很多，今后还会不断发展。但是，密码学的最高境界依然是无论敌方获取多少密文，也无法消除已方情报系统的不确定性。为了达到这个目的，就不仅要做到密文之间相互无关，同时密文还是看似完全随机的序列。这个思想，则是学术研究的道。在信息论诞生后，科学家们沿着这个思路设计出很好的密码系统，而公开密钥是目前最常用的加密办法。

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

闪光的不一定是金子，搜索引擎中排名靠前的网页也未必是有用的网页。消除这些作弊网页的原理和通信中过滤噪声的原理相同。这说明信息处理和通信的很多原理是相通的。

使用搜索引擎时，大家都希望得到有用而具有权威性的信息，而不是那些仅从字面上看相关的网页。遗憾的是，任何搜索引擎给出的结果都不完美，多少都会有点噪声。有些噪声是人为造成的，其中最主要的噪声是针对搜索引擎网页排名的作弊（SPAM）；另一些噪声则是用户在互联网上的活动产生的，比如用户和不严肃的编辑创作的大量不准确的信息。虽然这些噪声无法百分百地避免，但是任何好的搜索引擎都应该尽可能地清除这些噪声，给用户提供相关而准确的搜索结果。

1　搜索引擎的反作弊

做事情的方法有道和术两种境界，搜索反作弊也是如此。在“术”这个层面的方法大多是看到作弊的例子，分析并清除之，这种方法能解决问题，而且不需要太动脑筋，但是工作量较大，难以从个别现象上升到普遍规律。很多崇尚“人工”的搜索引擎公司喜欢这样的方法。而在“道”这个层面解决反作弊问题，就要透过具体的作弊例子，找到作的动机和本质。进而从本质上解决问题。

我们发现，通信模型对于搜索反作依然适用。在通信中解决噪声干扰问题的基本思路有两条。

1. 从信息源出发，加强通信（编码）自身的抗干扰能力。
2. 从传输来看，过滤掉噪声，还原信息。

搜索引擎作弊从本质上看就如同对（搜索）排序的信息加入噪声，因此反作弊的第一条是要增强排序算法的抗噪声能力。其次是像在信号处理中去噪声那样，还原原来真实的排名。学过信息论和有信号处理经验的读者可能知道这么一个事实：如果在发动机很吵的汽车里用手机打电话，对方可能听不清；但是如果知道了汽车发动机的频率，可以加上一个与发动机噪声频率相同、振幅相反的信号，便很容易地消除发动机的噪声，这样，接听人可以完全听不到汽车的噪声。事实上，现在一些高端手机已经有了这种检测和消除噪声的功能。消除噪声的流程可以概括如下。

2　搜索结果的权威性

用户使用搜索引擎一般有两个目的，其一是导航，即通过搜索引擎找到想要访问的网站，这个问题今天已经解决得很好了；其二是查找信息。今天的搜索引擎对几乎所有的查询都能给出非常多的信息，但问题是这些信息是否完全可信，尤其是当用户问的是一些需要专业人士认真作答的问题，比如医疗方面的问题。随着互联网的规模越来越大，各种不准确的信息也在不断增加，那么如何才能从众多信息源中找到最权威的信息，就成了近年来搜索引擎公司面对的难题。这也是我在2012年第二次加人Google后尝试解决的一个问题。

……

那么权威性是如何度量的呢？为了说明这一点，我们先要引人一个概念——“提及”（Mention）。比如某一篇新闻有这样的描述：

根据国际卫生组织的研究发现，吸烟对人体有害。或者约翰·霍普金斯大学的教授指出，二手烟对人同样有危害。

那么我们就说在谈论“吸烟危害”这个主题时，“提及”了“世界卫生组织”和“约翰·霍普金斯大学”。如果在各种新闻、学术论文或者其他网络信息页中，讨论到“吸烟危害”的主题时，这两个组织作为信息源多次被“提及”，那么我们就有理由相信这两个组织是谈论“吸烟危害” 这个主题的权威机构。

需要指出的是，“提及”这种信息不像网页之间的超链接那样一目了然，可以直接得到，它隐含在文章的自然语句中，需要通过自然语言处理方式分析出来，即使有了好的算法，计算量也是非常大的。

计算网站或者网页权威性的另一个难点在于，权威度与一般的网页质量（比如PageRank）不同，它和要搜索的主题是相关的。比如上面提到的世界卫生组织、梅奥诊所、美国癌症协会对于医学方面的论述具有相当的权威性，但是在金融领域，这些网站则未必如此。相反，CNN在医学方面未必有权威性，但是在民意看法、政治观点和新闻综述等方面则可能比较权威。权威性的这个特点，即与搜索关键词的相关性，使得它的存储量非常大，比如我们有M个网页，N个搜索关键词，那么我们要计算和存储O（M·N）个结果。而计算一般的网页质量则容易得多，只要计算和存储M个结果即可。因此，只有在今天有了云计算和大数据技术的情况下，计算权威性才成为可能。计算权威度的步骤可以概括如下。

1. 对每一个网页正文（包括标题）中的每一句话进行句法分析（关于句法分析的方法我们后面会有详细介绍），然后找出涉及到主题的短语（Phrases，比如“吸烟的危害”），以及对信息源的描述（比如国际卫生组织、梅奥诊所等）。这样我们就获得了所谓的“提及” 信息。需要指出的是，对几十亿个网页中的每一句话进行分析的计算量是极大的，好在现在皮耶尔领导开发的Google句法分析器足够快，而且有大量的服务器可供使用，这件事才成为可能。
2. 利用互信息，找到主题短语和信息源的相关性，这个方法我们在前面已经提到。
3. 需要对主题短语进行聚合，虽然很多短语从字面上看不同，但是意思是相同的，比如“吸烟的危害”“吸烟是否致癌”“香烟的危害”“煤焦油的危害”，等等，因此需要将这些短语聚类到一起。对这些短语进行聚类之后，我们就得到了一些搜索的主题。至于聚类的方法，可以采用我们前面提到的矩阵运算的方法。
4. 最后，我们需要对一个网站中的网页进行聚合，比如把一个网站下面的网页按照子域（Subdomain）或者子目录（Subdirectory）进行聚类。为什么要做这一步呢？因为即使是一个权威的网站，它下面的一些子域却未必具有权威性。比如约翰·霍普金斯大学的网站，它下面可能有很多子域的内容与医学无关，诸如涉及到医学院学生课外活动的子域就属于这种情况。因此，权威性的度量只能建立在子域或者子目录这一级。

完成了上述四步工作后，我们就可以得到一个针对不同主题，哪些信息源（网站）具有权威性的关联矩阵。当然，在计算这个关联矩阵时，也可以像计算PageRank那样，对权威度高的网站给出“提及”关系更高的权重，并且通过迭代算法，得到收敛后的权威度关联矩阵。有了权威度的关联矩阵，便可在搜索结果中提升那些来自于权威信息源的结果，使得用户对搜索结果更加放心。

在计算权威度时，我们采用了本书中另外三章的方法，包括句法分析、互信息和短语（词组）的聚类，而它们的背后都是数学。因此可以说，对搜索结果权威性的度量，完全是建立在各种数学模型基础之上的。

小结

噪声存在于任何通信系统，而好的通信系统需要能过滤掉噪声，还原真实的信号。搜索引擎是一个特殊的通信系统，免不了会有噪声，反作和确定权威性就是去噪声的过程。而这一系列过程的背后，依靠的是数学的方法。

第19章　谈谈数学模型的重要性

正确的数学模型在科学和工程中至关重要，而发现正确模型的途径常常是曲折的。正确的模型在形式上通常是简单的。

当然，他最大最有争议的贡献是对地心说模型的完善。虽然我们知道地球是围绕太阳运动的，但是在当时，从人们的观测出发，很容易得到地球是宇宙中心的结论。中国古代著名天文学家张衡提出的浑天说，其实就是地心说，但是张衡并未进行定量的描述。从图19.4、图19.5中可以看出两者非常相似。只不过因为张衡是中国人的骄傲，在历史书中从来是正面宣传，而托勒密在中国却成了唯心主义的代表。其实，托勒密在天文学上的地位堪比欧几里得之于几何学，牛顿之于物理学。

……

讲座结束时，我给Google中国和腾讯的工程师们总结过以下几点结论。

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

在网络搜索的研发中，我们在前面提到的单文本词频/逆文本频率指数（TF-IDF）和网页排名（PageRank）可以看作是网络搜索中的“椭圆模型”，它们都很简单易懂。

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

最大熵模型是一个完美的数学模型。它可以将各种信息整合到一个统一的模型中，在信息处理和机器学习中有着广泛的应用。它在形式上非常简单、优美，而在实现时需要有精深的数学基础和高超的技巧。

论及投资，人们常说不要把所有的鸡蛋放在一个篮子里，这样可以降低风险。在信息处理中，这个原理同样适用。在数学上，这个原理称为最大熵原理（The Maximum Entropy Principle）。这个题目很有意思，但也比较深奥，因此只能大致介绍它的原理。

在网络搜索排名中用到的信息有上百种，在腾讯时，工程师经常问我如何能把它们结合在一起用好。更普遍地讲，在信息处理中，我们常常知道各种各样但又不完全确定的信息，我们需要用一个统一的模型将这些信息综合起来。如何综合得好，是一门很大的学问。

1　最大熵原理和最大熵模型

数学上解决上述问题最漂亮的方法是最大熵（Maximum Entropy）模型，它相当于行星运动的椭圆模型。“最大熵”这个名词听起来很深奥，但它的原理很简单，我们每天都在用。说白了，就是要保留全部的不确定性，将风险降到最小。下面来看一个实际的例子。

……

最大熵原理指出，对一个随机事件的概率分布进行预测时，我们的预测应当满足全部已知的条件，而对未知的情况不要做任何主观假设。（不做主观假设这点很重要。）在这种情况下，概率分布最均匀，预测的风险最小。因为这时概率分布的信息最大，所以人们把这种模型叫作“最大熵模型”。我们常说，不要把所有的鸡蛋放在一个篮子里，其实就是最大熵原理的一个朴素的说法，因为当我们遇到不确定性时，就要保留各种可能性。

……

最大熵模型在形式上是最漂亮、最完美的统计模型，在自然语言处理和金融方面有很多有趣的应用。早期，由于最大熵模型计算量大，科学家们一般采用一些类似最大熵模型的近似模型。谁知这一近似，最大熵模型就从完美变得不完美了。结果可想而知，比打补丁的凑合的方法也好不了多少。于是，不少原来热衷于此的学者又放弃了这种方法。第一个在实际信息处理应用中验证了最大熵模型的优势的是宾夕法尼亚大学马库斯教授的高徒拉纳帕提（Adwait Ratnaparkhi），原IBM和微软的研究员、现任Naunce的科学家。拉纳帕提的聪明之处在于他没有对最大熵模型进行近似处理，而是找到了几个最适合用最大熵模型而计算量相对不太大的自然语言处理问题，比如词性标注和句法分析。拉纳帕提成功地将上下文信息、词性（名词、动词和形容词）以及主谓宾等句子成分，通过最大熵模型结合起来，做出了当时世界上最好的词性标识系统和句法分析器。拉纳帕提的论文让人们耳目一新。拉纳帕提的词性标注系统，至今仍然是使用单一方法的系统中效果最好的。从拉纳帕提的成果中，科学家们又看到了用最大熵模型解决复杂的文字信息处理问题的希望。

在2000年前后，由于计算机速度的提升以及训练算法的改进，很多复杂的问题，包括句法分析、语言模型和机器翻译都可以采用最大熵模型了。最大熵模型和一些简单组合了特征的模型相比，效果可以提升几个百分点。对于那些不是很看重产品质量的人和公司来讲，这几个百分点或许不足以给使用者带来明显的感受，但是如果投资的收益能增长哪怕百分之一，获得的利润也是数以亿计的。因此，华尔街向来最喜欢使用新技术来提高他们交易的收益。而证券（股票、债券等）的交易需要考虑非常多的复杂因素，因此，很多对冲基金开始使用最大熵模型，并且取得了很好的效果。

2　延伸阅读：最大熵模型的训练

最原始的最大熵模型的训练方法是一种称为通用选代算法GIS（Generalized Iterative Scaling）的迭代算法。GIS的原理并不复杂，大致可以概括为以下几个步骤。

1.假定第零次选代的初始模型为等概率的均匀分布。 2.用第N次选代的模型来估算每种信息特征在训练数据中的分布。如果超过了实际的，就把相应的模型参数变小。否则，将它们变大。 3.重复步骤2，直到收敛。

GIS最早是由达诺奇（J. N. Darroch）和拉特克利夫（D. Ratcliff）在上个世纪70年代提出的，它是一个典型的期望值最大化算法（Expectation Maximization，简称EM）。但是，这两人没能对这种算法的物理含义做出很好的解释。后来是由数学家希萨解释清楚的。因此，人们在谈到这个算法时，总是同时引用达诺奇和拉特克利夫以及希萨的两篇论文。GIS 算法每次迭代的时间都很长，需要迭代很多次才能收敛，而且不太稳定，即使在64位计算机上都会出现溢出。在实际应用中很少有人真正使用 GIS，大家只是通过它来了解最大熵模型的算法。

上个世纪80年代，天赋异禀的达拉·皮垂孪生兄弟（Della Pietra）在 IBM对GIS算法做了两方面改进，提出了改进选代算法IIS（Improved Iterative Scaling）。这使得最大熵模型的训练时间缩短了一到两个数量级。这样，最大熵模型才有可能变得实用。即使如此，在当时也只有IBM有条件使用最大熵模型。

……

讲到这里，读者也许会问，当年最早改进最大熵模型算法的达拉·皮垂兄弟这些年难道没有做任何事吗？在上个世纪90年代初贾里尼克离开 IBM后，他们也退出了学术界，到金融界大显身手。他们两个人和很多 IBM做语音识别的同事一同到了一家当时还不大，但现在是世界上最成功的对冲基金（Hedge Fund）公司一文艺复兴技术公司（Renaissance Technologies）。我们知道，决定股票涨跌的因素可能有几十甚至上百种，而最大方法恰恰能找到一个同时满足成千上万种不同条件的模型。在那里，达拉·皮垂兄弟等科学家用最大熵模型和其他一些先进的数学工具对股票进行预测，获得了巨大的成功。从1988年创立至今，该基金的净回报率高达平均每年34%。也就是说，如果1988年你在该基金投入一块钱，20年后的2008年你能得到200多元钱。这个业绩，远远超过股神巴菲特的旗舰公司伯克希尔·哈撒韦（Berkshire Hathaway）。同期，伯克希尔·哈撒韦的总回报是16倍。而在出现金融危机的2008年，全球股市暴跌，文艺复兴技术公司的回报率却高达80%，可见数学模型的厉害。

小结

最大熵模型可以将各种信息整合到一个统一的模型中。它有很多良好的特性：从形式上看，它非常简单，非常优美；从效果上看，它是唯一一种既能满足各个信息源的限制条件，又能保证平滑性（Smooth）的模型。由于最大熵模型具有这些良好的特性，因此应用范围十分广泛。但是，最大熵模型计算量巨大，在工程上实现方法的好坏决定了模型的实用与否。

第21章　拼音输入法的数学原理

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

亚洲语言及所有非罗马拼音式的语言（Non-Roman Language）的输入原本是个问题，但是近20年来，以中国为代表的亚洲国家在输入法方面有了长足的进步，现在这已经不是人们使用计算机的障碍了。以中文输入为例，过去的25年里，输入法基本上经历了以自然音节编码输入，到偏旁笔画拆字输入，再回归自然音节输入的过程。和任何事物的发展一样，这个螺旋式的回归不是简单的重复，而是一种升华。

输入法输入汉字的快慢取决于汉字编码的平均长度，通俗点儿讲，就是用击键次数乘以寻找这个键所需时间。单纯地编短编码长度未必能提高输入速度，因为寻找一个键的时间可能变得较长。提高输入法的效率在于同时优化这两点，而这其中有着坚实的数学基础。我们可以通过数学的方法说明平均输入一个汉字需要多少次击键，如何设计输入法的编码才能使输入汉字的平均击键次数接近理论上的最小值，同时寻找一个键的时间又不至于过长。

1　输入法与编码

这里面，对汉字的编码分为两部分：对拼音的编码（参照汉语拼音标准即可）和消除歧义性的编码。对一个汉字编码的长度取决于这两方面，只有当这两个编码都缩短时，汉字的输入才能够变快。早期的输入法常常只注重第一部分而忽视第二部分。

……

这一代输入法的问题在于减少了每个汉字击键的次数，而忽视了找到每个键的时间。要求普通用户背下这些输入方法里所有汉字的编码是不现实的，这比背6000个GRE单词还难。因此，他们在使用这些输入方法时都要按照规则即时“拆字”，即找到一个字的编码组合，这个时间不仅长，而且在脱稿打字时会严重中断思维。本书一开头就强调把语言和文字作为通信的编码手段，一个重要目的是帮助思维和记忆。如果一个输入法中断了人们的思维过程，就和人的自然行为不相符合。认知科学已经证明，人一心无二用。过去我们在研究语音识别时做过很多用户测试，发现使用各种复杂编码输入法的人在脱稿打字时，速度只有他在看稿打字时的一半到四分之一。因此，虽然每个字的平均击键次数少，但是敲键盘的速度也慢了很多，总的来看并不快。所以，广大中国计算机用户对这一类输入法的认可度极低，这是自然选择的结果。

最终，用户还是选择了拼音输入法，而且是每个汉字编码较长的全拼输入法。虽然看上去这种方法输入每个汉字需要多敲几个字，但是有三个优点让它的输入速度并不慢。第一，它不需要专门学习。第二，输入自然，不会中断思维，也就是说找每个键的时间非常短。第三，因为编码长，有信息余量，容错性好。比如对分不清非前鼻音an、en、in和后鼻音 ang、eng、ing的人来讲，输入zhan（占）这个字，即使他以为拼音是后鼻音zhang，当输入一半的时候，已经看到自己要找的字了，就会停下来，避免了双拼的那种不容错的问题。于是，拼音输入法要解决的问题只剩下排除一音多字的歧义性了，只要这个问题解决了，拼音输入法照样能做到击键次数和那些拆字的方法差不多，这也是目前各种拼音输入法做的主要工作。接下来我们就分析平均输入一个汉字可以做到最少几次击键。

2　输入一个汉字需要敲多少个键——谈谈香农第一定理

香农第一定理指出：对于一个信息，任何编码的长度都不小于它的信息熵。因此，上面平均编码长度的最小值就是汉字的信息熵，任何输入法都不可能突破信息给定的极限。这里需要指出的是，如果将输入法的字库从国标GB2312扩展到更大的字库GBK，由于后者非常见字的频率非常低，平均编码长度相比GB2312的大不了多少，因此本书中就以GB2312 字符集为准。

……

而利用上下文最好的办法是借助语言模型。只要承认概率论，就无法否认语言模型可以保证拼音转汉字（解决一音多字问题）的效果最好。假定有大小不受限制的语言模型，是可以达到信息论给出的极限输入速度的。但是在产品中，不可能占用用户太多的内存空间，因此各种输入法只能提供给用户一个压缩得很厉害的语言模型。而有的输入法为了减小内存占用，或者没有完全掌握拼音转汉字的解码技巧，根本就没有语言模型。这样一来，当今的输入法和极限输入速度相比还有不少可提升的空间。目前，各家拼音输入法（Google的、腾讯的和搜狗的）基本处在同一个量级，将来技术上进一步提升的关键就在于看谁能准确而有效地建立语言模型。当然，利用语言模型将拼音串自动转成汉字，要有合适的算法，这就是下一节要讨论的问题。

3　拼音转汉字的算法

这个拼音输入法的例子和前面第12章中提到的导航系统看似没什么关系，背后的数学模型却完全一样。数学的妙处在于它的每一个工具都具有相当的普遍性，在不同的应用中都可以发挥很大的作用。

4　延伸阅读：个性化的语言模型

现有的汉字拼音输入法距离信息论给的极限还有很大的差距，可提升的空间很大，会有越来越好用的输入方法不断涌现。当然，速度只是输入法的一个而不是唯一的衡量标准——当输入速度超过一定阈值后，用户的体验可能更重要。

从理论上讲，只要语言模型足够大，拼音输入法的平均击键次数就可以接近信息论给的极限值。如果把输入法放在云计算上，这是完全可以实现的，而在客户端上（比如个人电脑上）这样做不现实。好在客户端有客户端的优势，比如可以建立个性化的语言模型。

个性化的出发点是不同人平时写的东西主题不同，由于文化程度的差异，用词习惯不同，说话和写作的水平也不同，因此，他们各自应该有各自的语言模型。

我们在Google统计发现，这个假设是对的，且不说表达主题意义的实词会因人而异，就是不同的地方、不同的文化背景和受教育程度的人使用的虚词都有明显的不同。因此，如果每个人有各自的语言模型，用拼音输入时，候选词次序的排列一定比通用的输入法排得好。

接下来有两个问题需要解决。首先是如何训练一个个性化的语言模型，其次是怎样处理好它和通用语言模型的关系。

为每个人训练一个特定的语言模型，最好是收集足够多这个人自己写的文字，但是一个人一辈子写的东西不足以训练一个语言模型。训练一个词汇量在几万的二元模型，需要几千万词的语料，即使是职业作家或者记者，一辈子都不可能写这么多的文章。没有足够多的训练数据，训练出的（高阶）语言模型基本上没有用。当然训练一个一元模型不需要太多数据，一些输入法（自发地）找到了一种经验做法：用户词典，这实际上是一个小规模的一元模型加上非常小量的元组（比如一个用户定义的词ABC，实际是一个三元组）。

更好的办法是找到大量符合用户经常输入的内容和用语习惯的语料，训练一个用户特定的语言模型。这里面的关键显然是如何找到这些符合条件的语料。这次又要用到余弦定理和文本分类的技术了。训练用户特定的语言模型的整个步骤如下。

……

我们在最大熵模型中介绍过，把各种特征综合在一起最好的方法是采用最大熵模型。当然，这个模型比较复杂，训练时间较长，如果为每一个人都建立这样一个模型，成本较高。因此可以采用一个简化的模型：线性插值的模型。

……

这种线性插值的模型比最大熵模型效果略差，但是能得到大约80%的收益。（如果最大熵模型比原来的通用模型的改进收益是100%的话。）顺便说一句，Google拼音输入法的个性化语言模型就是这么实现的。

小结

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

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

将自然语言处理从基于规则的研究方法转到基于统计的研究方法上，宾夕法尼亚大学的教授米奇·马库斯功不可没。他创立了今天在学术界广泛使用的LCD语料库，同时培养了一大批精英人物。

1　教父马库斯

将自然语言处理从基于规则的研究方法转到基于统计的研究方法上，贡献最大的有两个人，一个是我们前面介绍过的贾里尼克，他是一位开创性人物，另一个是将这个研究方法进一步发扬光大的米奇·马库斯（Mitch Marcus）。和贾里尼克不同，马库斯（见图22.1）对这个领域的贡献不是直接的发明，而是通过他造福于全世界研究者的宾夕法尼亚大学LDC 语料库以及他的众多优秀弟子。这些优秀弟子，包括前面章节中介绍的一大批年轻有为的科学家，迈克尔·柯林斯（Michael Collins），艾里克· 布莱尔（Eric Brill），大卫·雅让斯基（David Yarowsky），拉纳帕提（Adwait Ratnaparkhi），以及很多在麻省理工学院和约翰·霍普金斯大学等世界一流大学和IBM等公司的研究所担任终身教职和研究员的科学家。就像许多武侠小说中描写的那样，弟子都成了各派的掌门，师傅一定了不得。的确，马库斯虽然作为第一作者发表的论文并不多，但是从很多角度上讲，他可以说是自然语言处理领域的教父。

和贾里尼克一样，马库斯也毕业于麻省理工学院，同样，他也经历了从工业界（AT&T贝尔实验室）到学术界（宾夕法尼亚大学）的转行。刚到宾夕法尼亚大学时，马库斯在利用统计的方法进行句子分析上做出了不少成绩。而这一方面恰恰是贾里尼克和IBM的科学家没有做过的。在马库斯以前，基于统计的自然语言处理为语言学术界所诟病的一个原因是采用统计的方法很难进行“深人的”分析，马库斯的工作证明统计的方法比规则的方法更适合对自然语言做深人的分析。但是，随着工作的深人以及研究的不断推进，马库斯发现存在两大难题：首先，可以用于研究的统计数据明显不够；其次，各国科学家因为使用的数据不同，论文里发表的结果无法互相比较。

马库斯比很多同行更早地发现了建立标准语料库在自然语言处理研究中的重要性。于是，马库斯利用自己的影响力，推动美国自然科学基金会（National Science Foundation，NSF）和DARPA出资立项，联络了多所大学和研究机构，建立了数百个标准的语料库组织（Linguistic Data Consortium，LDC）。其中最著名的语料库是Penn Tree Bank。起初这个语料库收集了一些真实的书面英语（《华尔街日报》）语句，人工进行词性标注和语法树构建等，作为全世界自然语言处理学者研究和实验的统一语料库。后来，由于得到广泛的认可，美国自然科学基金会不断追加投入，建立起了覆盖多种语言（包括中文）的语料库。对每一种语言，它有几十万到几百万字的有代表性的句子，每个句子都有词性标注、语法分析树等。LDC后来又建立了语音、机器翻译等很多数据库，为全世界自然语言处理科学家共享。如今，在自然语言处理方面发表论文，几乎都要提供基于LDC语料库的测试结果。

过去20年里，在机器学习和自然语言处理领域，80%的成果来自于数据量的增加。马库斯对这些领域数据的贡献可以说是独一无二的。当然，凭借对数据的贡献，还不足以让马库斯获得教父的地位。马库斯有点像日本围棋领域的木谷实”，他的影响力很大程度上是靠他的弟子传播出去的。

放手让博士生研究自已感兴趣的课题，这是他之所以桃李满天下的原因。马库斯的博士生研究的题目覆盖了自然语言处理的很多领域，而且题目之间几乎没有相关性，因为这些题目大多是博士生自己找的，而不是马库斯指定的。他的做法和中国大部分博士生导师完全不同。马库斯对几乎所有的自然语言处理领域都有独到的见解，他让博士生提出自己感兴趣的课题，或者用现有的经费支持学生，或者去为他们的项目申请经费。马库斯高屋建瓴，能够很快地判断一个研究方向是否正确，省去了博士生很多做无谓尝试（Try-And-Error）的时间。因此他的博士毕业生质量非常高，而且有些很快就拿到了博士学位。

由于马库斯宽松的管理方式，他培养的博士生在研究和生活上都是个性迥异。有些人善于找到间接快速的方法和容易做出成绩的题目，有的人习惯啃硬骨头；有些人三四年就拿到博士去当教授了，而有些人“赖在” 学校里七八年不走，最后出一篇高质量的博士论文。这些各有特点的年轻学者，后来分别能适应文化迥异的各个大学和公司。

2　从宾夕法尼亚大学走出的精英们

当今自然语言处理领域年轻一代的世界级专家，相当大一部分来自宾夕法尼亚大学马库斯的实验室。他们为人做事风格迥异，共同的特点是年轻有为。这里介绍其中两人，迈克尔·柯林斯和艾里克·布莱尔，因为他们代表两种截然不同的风格。

第23章　布隆过滤器

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

1　布隆过滤器的原理

在日常生活或工作中，包括开发软件时，经常要判断一个元素是否在一个集合中。比如，在字处理软件中，需要检查一个英语单词是否拼写正确（也就是要判断它是否在已知的字典中）；在FBI，需要核实一个嫌疑人的名字是否已经在嫌疑名单上；在网络爬虫里，需要确认一个网址是否已访问过，等等。最直接的方法就是将集合中全部的元素存在计算机中，遇到一个新元素时，将它和集合中的元素直接比较即可。一般来讲，计算机中的集合是用哈希表（Hash Table）来存储的，优点是快速准确，缺点是耗费存储空间。当集合比较小时，这个问题不明显，当集合规模巨大时，哈希表存储效率低的问题就显现出来了。比如，像Yahoo、 Hotmail和Gmail那样的公众电子邮件（Email）提供商，必须设法过滤来自发送垃圾邮件的人（Spamer）的垃圾邮件。一种做法就是记录下那些发垃圾邮件的电子邮件地址。由于那些发送者会不断注册新的地址，全世界少说也有几十亿个发垃圾邮件的地址，将这些地址都存起来，需要大量的网络服务器。采用哈希表，每存储一亿个电子邮件地址，就需要1.6GB的内存。（用哈希表实现的具体办法是将每一个电子邮件地址对应成一个8字节的信息指纹，然后将这些信息指纹存入哈希表，由于哈希表的存储效率一般只有50%，因此一个电子邮件地址需要占用16字节。一亿个地址大约要1.6GB，即16亿字节的内存。）因此，存储几十亿个邮件地址可能需要上百GB的内存。除非是超级计算机，一般服务器是存不下的。

今天，我们介绍一种称作布隆过滤器的数学工具，它只需要哈希表1/8 到1/4的大小就能解决同样的问题。

布隆过滤器（Bloom Filter）是由伯顿·布隆（Burton Bloom）于1970 年提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。接下来用上面的例子来说明其工作原理。

……

布隆过滤器决不会漏掉黑名单中的任何一个可疑地址。但是，它也有一个不足之处。也就是它有极小的可能将一个不在黑名单中的电子邮件地址也判定为在黑名单中，因为有可能某个好的邮件地址在布隆过滤器中对应的8个位置“恰巧”被（其他地址）设置成1。好在这种可能性很小。我们把它称为误识别率。在上面的例子中，误识别率在万分之一以下。误识别的理论分析会在延伸阅读中介绍。

布隆过滤器的好处在于快速、省空间，但是有一定的误识别率。常见的补救办法是再建立一个小的白名单，存储那些可能被误判的邮件地址。

2　延伸阅读：布隆过滤器的误识别问题

上一节中提到，布隆过滤器的一个不足之处就是它可能把不在集合中的元素错判成集合中的元素，这在检验上被称为“假阳性”。这个概率很小，但是究竟有多小，是否可以忽略？

小结

布隆过滤器背后的数学原理在于两个完全随机的数字相冲突的概率很小，因此，可以在很小的误识别率条件下，用很少的空间存储大量信息。补救误识别的常见办法是再建立一个小的白名单，存储那些可能被别误判的信息。布隆过滤器中只有简单的算术运算，因此速度很快，使用方便。

第24章　马尔可夫链的扩展——贝叶斯网络

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

1　贝叶斯网络

前面的章节中多次提到马尔可夫链（Markov Chain），它描述了一种状态序列，其每个状态值取决于前面有限个状态。对很多实际问题而言，这种模型是一种很粗略的简化。在现实生活中，很多事物相互的关系并不能用一条链来串起来，很可能是交叉的、错综复杂的。比如在图24.1 中可以看到，心血管疾病和成因之间的关系错综复杂，显然无法用一个链来表示。

上述有向图可以看作是一个网络，其中每个圆圈表示一个状态。状态之间的连线表示它们的因果关系。比如从心血管疾病出发到吸烟的弧线表示心血管疾病可能与吸烟有关。假定在这个图中马尔可夫假设成立，即每一个状态只跟与其直接相连的状态有关，而跟与它间接相连的状态没有直接关系，那么它就是贝叶斯网络。不过要注意，两个状态A和B之间没有直接的有向弧链接，只说明它们之间没有直接的因果关系，但这并不表明状态A不会通过其他状态间接地影响状态B，只要在图中有一条从A到B的路径，这两个状态就还是有间接的相关性的。所有这些（因果）关系，都可以有一个量化的可信度（belief），即用一个概率描述。也就是说，贝叶斯网络的弧上可以有附加的权重。马尔可夫假设保证了贝叶斯网络便于计算。我们可以通过这样一张网络估算出一个人患心血管疾病的可能性。

在网络中，每个节点的概率，都可以用贝叶斯公式来计算，贝叶斯网络因此而得名。由于网络的每个弧都有一个可信度，贝叶斯网络也被称作信念网络（Belief Networks）。……

……

我们在计算上面的贝叶斯网络中每个状态的取值时，只考虑了前面一个状态，这一点和马尔可夫链相同。但是，贝叶斯网络的拓扑结构比马尔可夫链灵活，它不受马尔可夫链的链状结构的约束，因此可以更准确地描述事件之间的相关性。可以讲，马尔可夫链是贝叶斯网络的特例，而贝叶斯网络是马尔可夫链的推广。

使用贝叶斯网络必须先确定这个网络的拓扑结构，然后还要知道各个状态之间相关的概率，也就是图24.2中的那些表。得到拓扑结构和这些参数的过程分别叫作结构训练和参数训练，统称训练。和训练马尔可夫模型一样，训练贝叶斯网络要用一些已知的数据。比如训练上面的网络，需要知道一些心血管疾病和吸烟、家族病史等有关的情况。相比马尔可夫链，贝叶斯网络的训练比较复杂，从理论上讲，它是一个NP完全问题（NP-Complete Problem），也就是说，对于现在的计算机是不可计算的。但是，对于某些应用，这个训练过程可以简化，并在计算机上实现。

值得一提的是IBM华生实验室的茨威格博士（Geoffrey Zweig）和西雅图华盛顿大学的比尔默教授（Jeff Bilmer）完成了一个通用的贝叶斯网络的工具包，提供给对贝叶斯网络有兴趣的研究者免费使用。

贝叶斯网络在图像处理、文字处理、支持决策等方面有很多应用。在文字处理方面，语义相近的词之间的关系可以用一个贝叶斯网络来描述。

我们利用贝叶斯网络，可以找出近义词和相关的词，因而在Google搜索和Google广告中都有直接的应用。

2　贝叶斯网络在词分类中的应用

可以用基于统计的模型分析文本，从中抽取概念，分析主题。不妨把这样的模型称为主题模型（Topic Model）。前面章节中提到的从一篇文章里得到它的特征向量，然后把这个特征向量通过余弦相似性（距离）对应到一个主题的特征向量，便是统计主题模型的一种。这里介绍通过贝叶斯网络建立的另一种模型一Google的Rephil，个中细节不便透露太多，因此这里改用我自己的语言介绍其原理，听过这个主题报告或者读过报告幻灯片的读者可能会发现我的讲法略有不同，但原理是相同的。

……

2002年，Google的工程师们利用贝叶斯网络，建立了文章、概念和关键词的联系，将上百万关键词聚合成若干概念的聚类，称为Phil Cluster。这项工作最初甚至没有考虑应用背景，只是觉得概念的提取将来对信息处理会有帮助。而最早的应用是广告的扩展匹配，这是Phil Cluster完成后几个月里的事情。由于早期只考虑了关键词和文本的关系，对关键词上下文关系考虑较少，因此这个概念的聚类过于广泛，比如计算机和股票可能被聚在一类中，汽车和美国总统的名字聚在一起。这严重影响了 Google各个项目组对Phil Cluster的接受程度。2004年，Google开始重构Phil Cluster，这次采用了比原先多几百倍的数据，考虑的关键词的相似性也从原来的在文本中同现扩展为在上下文中同现，同时支持不同颗粒的概念。因为是重构，所以项目的名称改为Rephil。Rephil聚合了大约1200万个词，将它们聚合到上百万的概念中。一个概念一般有十几个到上百个词。由于Rephil的质量比以前有很大提高，因此从广告到搜索都用到了它的成果。久而久之，就没有多少人知道Phil了。Rephil的网络结构比原先的Phil复杂很多，但是原理类似。

3　延伸阅读：贝叶斯网络的训练

使用贝叶斯网络首先要确定它的结构。对于简单的问题，比如上面那个心血管疾病的例子，由专家直接给出它的结构即可。但是，稍微复杂一点的问题已经无法人工给出结构了，需要通过机器学习得到。

优化的贝叶斯网络结构要保证它产生的序列（比如“家族病史一>高血脂一>心血管疾病”就是一个序列）从头走到尾的可能性最大，如果是使用概率做度量，那就是后验概率最大。当然，产生一个序列可以有多条路径，从理论上讲，需要完备的穷举搜索（Exhaustive Search），即考虑每一条路径，才能得到全局最优。但是这样的计算复杂度是NP困难的（详见附录），因此一般采用贪心算法（Greedy Algorithm），也就是在每一步时，沿着箭头的方向寻找有限步。当然这样会导致陷入局部最优，并且最终远离全局最优解。一个防止陷入局部最优的方法，就是采用蒙特卡罗（Monte Carlo）的方法，用许多随机数在贝叶斯网络中试一试，看看是否陷人局部最优。这个方法的计算量比较大。最近，新的方法是利用信息论，计算节点之间两两的互信息，只保留互信息较大的节点直接的连接，然后再对简化了的网络进行完备的搜索，找到全局优化的结构。

确定贝叶斯网络的结构后，就要确定这些节点之间的弧的权重了。假定这些权重用条件概率来度量，为此，需要一些训练数据，我们只需优化贝叶斯网络的参数，使得观察到的这些数据的概率（即后验概率） $P(D|\theta)$达到最大。这个过程就是前面介绍过的EM过程（Expectation-Maximization Process）。

在计算后验概率时，计算的是条件X和Y结果之间的联合概率P(X,Y)。我们的训练数据会提供一些P（X，Y)之间的限制条件，而训练出来的模型要满足这些限制条件。回顾我们在第20章“不要把鸡蛋放到一个篮子里一谈谈最大熵模型”中介绍的内容，这个模型应该是满足给定条件的最大熵模型。因此，涉及最大熵模型的训练方法在这里都可以使用。

最后，需要指明结构的训练和参数的训练通常是交替进行的。也就是先优化参数，再优化结构，然后再次优化参数，直至得到收敛或者误差足够小的模型。

对贝叶斯网络有特别兴趣的读者，可以阅读比尔默和茨威格共同发表的论文：

https://people.ece.uw.edu/bilmes/pgs/sort_date.html

如果想更系统地了解这方面的知识，可阅读斯坦福大学科勒（Daphne Koller）教授写的巨著Probabilistic Graphical Models: Principles and Techniques，这本书有一千多页，而且价格不菲，因此只适合于专业人士。

读者还可以从“数学之美番外篇：平凡而又神奇的贝叶斯方法”一文中找到更多的贝叶斯网络的应用。

小结

从数学的层面来讲，贝叶斯网络是一个加权的有向图，是马尔可夫链的扩展。而从认识论的层面看，贝叶斯网络克服了马尔可夫链那种机械的线性的约束，它可以把任何有关联的事件统一到它的框架下面。因此，贝叶斯网络有很多应用，除了前面介绍的文本分类和概念抽取外，在生物统计、图像处理、决策支持系统和博弈论中都有广泛应用。贝叶斯网络的描述简单易懂，但导出的模型却非常复杂。

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

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

1　文法分析——计算机算法的演变

所幸在很多自然语言处理的应用中，并不需要对语句做深入的分析，只要做浅层的分析（Shallow Parsing），比如找出句子中主要的词组以及它们之间的关系即可。于是科学家们把研究的重点从语句的深层分析转到对语句的浅层分析上。到20世纪90年代以后，随着计算机计算能力的增强，科学家们采用了一种新的数学模型工具一条件随机场，大大提高了句子浅层分析的正确率，正确率可达95%，使文法分析得以应用到很多产品，比如机器翻译上。

2　条件随机场

条件随机场是隐马尔可夫模型的一种扩展，它保留了隐马尔可夫模型的一些特性，比如在图中的y1，y2，等状态的序列还是一个马尔可夫链。更广义地讲，条件随机场是一种特殊的概率图模型（Probabilistic Graph Model）。在图25.2中，顶点代表一个个随机变量，比如x1和y1，顶点之间的弧代表它们相互的依赖关系，通常采用一种概率分布，比如P（x|y）来描述。它的特殊性在于，变量之间要遵守马尔可夫假设，即每个状态的转移概率只取决于相邻的状态，这一点，它和我们前面介绍的另一种概率图模型——贝叶斯网络相同。而它们的不同之处在于，条件随机场是无向图，而贝叶斯网络是有向图。

……

最早采用条件随机场对句子进行浅层分析的是宾夕法尼亚大学的博士生沙飞（FeiSha）和他的导师（之一）皮耶尔。他们继承了拉纳帕提的方法，只做了句子分析的第一层，即从词到词组的自动组合。由于改进了统计模型，因此句子浅层分析的正确率高达94%左右，在自然语言处理中，这是很高的水平了。

3　条件随机场在其他领域的应用

条件随机场的应用当然不限于自然语言处理领域，即使在很多非常传统的行业里，它的应用也会带来惊喜。

在美国大城市里，犯罪是让市民和警方都挠头的大问题，解决这个问题最好的办法不是在犯罪发生后去破案，而是提前制止犯罪行为。当然，做起来并不容易，毕竟城市这么大，人口这么多，而且还处在随时发生各种突发性事件的状态，谁知道下一次犯罪行为会发生在哪里。过去，警察只能沿着街巡视，凑巧赶上有罪犯在行凶犯罪，当然可以制止，但是这种“碰巧”的情况占少数，有点像是瞎猫碰到了死耗子。不过，现在通过数学模型对大数据进行分析，警察就能有效地预测在城市的什么地方、什么时间可能会出现什么样的犯罪，从而有针对性地进行巡视，达到制止犯罪的目的。

小结

条件随机场是一个非常灵活的用于预测的统计模型。本章强调了它在自然语言处理，特别是在句子分析中的应用，其实它的应用领域远远不止这些。条件随机场在模式识别、机器学习、生物统计，甚至预防犯罪等方面都有很成功的应用。

和最大熵模型一样，条件随机场形式简单，但是实现复杂，所幸现在有不少开源的软件可供选用，对于一般的工程人员来讲应该是足够了。

第26章　维特比和他的维特比算法

维特比算法是现代数字通信中使用最频繁的算法，也是很多自然语言处理采用的解码算法。可以毫不夸张地讲，维特比是对我们今天的生活影响力最大的科学家之一，因为基于CDMA的3G移动通信标准主要就是他和厄文·雅各布创办的高通公司制定的。

说起安德鲁·维特比（Andrew Viterbi），通信行业之外的人可能知道他的并不多，不过通信行业的从业者大多知道以他的名字命名的维特比算法（Viterbi Algorithm）。维特比算法是现代数字通信中最常用的算法，也是很多自然语言处理采用的解码算法。可以毫不夸张地讲，维特比是对我们今天的生活影响力最大的科学家之一，因为基于CDMA的3G移动通信标准主要就是他和厄文·雅各布（Irwin Mark Jacobs）创办的高通公司（Qualcomm）制定的，并且高通公司在4G时代依然引领移动通信的发展。

1　维特比算法

言归正传，现在让我们看看作为科学家的维特比得以成名的算法。维特比算法是一个特殊但应用最广的动态规划算法（见前面相应的章节）。利用动态规划，可以解决任何一个图中的最短路径问题。而维特比算法是针对一个特殊的图——篱笆网络（Lattice）的有向图最短路径问题而提出的。它之所以重要，是因为凡是使用隐马尔可夫模型描述的问题都可以用它来解码，包括今天的数字通信、语音识别、机器翻译、拼音转汉字、分词等。下面还是拿大家用得最多的输入法拼音转汉字来说明。

……

更重要的是，维特比算法是和长度成正比的。无论是在通信中，还是在语音识别、打字中，输入都是按照流（Stream）的方式进行的，只要处理每个状态的时间比讲话或者打字速度快（这点很容易做到），那么不论输入有多长，解码过程永远是实时的。这便是数学漂亮的地方！

虽然数字通信和自然语言处理的基础算法的原理就是这么简单，每个通信或者计算机专业的学生两个小时就能学会，但是在20世纪60年代能够想出这个快速算法是非常了不起的。凭借这个算法，维特比奠定了他在数字通信中不可替代的地位。但是，维特比并不满足于停留在算法本身，而是努力将它推广出去。为此，维特比做了两件事：首先，他放弃了这个算法的专利；第二，他和雅各布博士一起在1968年创办了Linkabit公司，将这个算法做成芯片，卖给其他通信公司。

到这一步维特比已经比一般的科学家走得远很多了。但是，这仅仅是维特比辉煌人生的第一步。20世纪80年代，维特比致力于将CDMA技术应用于无线通信。

2　CDMA技术——3G移动通信的基础

自从苹果公司推出iPhone，3G手机和移动互联网就成为科技界和工业界的热点话题。这里面最关键的通信技术就是码分多址（CDMA）技术。对CDMA技术的发明和普及贡献最大的有两个人一奥匈帝国出生、美籍犹太裔的海蒂·拉玛尔（Hedy Lamarr）和维特比。

……

虽然扩频技术和调频技术早在20世纪60年代就应用于军事，但是转为民用则是20世纪80年代以后的事情。这首先要归功于移动通信的需求。上个世纪80年代，移动通信开始快速发展，很快大家便发现空中的频带不够用了，需要采用新的通信技术。其次，具体到CDMA本身，很大程度上归功于维特比的贡献。

……

当然，读者可能会有个问题：如果一个发送者占用了很多频带，那么有多个发送者同时发射岂不打架了？没关系，每个发送者有不同的密码，接收者在接到不同信号时，通过密码过滤掉自己无法解码的信号，留下和自已密码对应的信号即可。由于这种方法是根据不同的密码区分发送的，因此称为码分多址。

将CDMA技术用于移动通信的是高通公司。从1985年到1995年，高通公司制定和完善了CDMA的通信标准CDMA1，并于2000年发布了世界上第一个主导行业的3G通信标准CDMA2000，后来文和欧洲、日本的通信公司一同制定了世界上第二个3G标准WCDMA。2007年，维特比作为数学家和计算机科学家，被授予美国科技界最高成就奖一国家科学奖（见图26.7）。

小结

世界上绝大多数科学家最大的满足就是自已的研究成果得到同行的认可，如果能有应用就更是喜出望外了。而能够亲自将这些成就应用到实际中的人少之又少，因为做到这一点对科学家来讲很不容易。这样的科学家包括RISC的发明人亨利西和DSL之父查菲等人。这些人已经非常了不起了，但也只是做了一个行业中他们擅长的部分，而不是从头到尾完成一次革命。而维特比所做的远远超出了这一点，他不仅提供了关键性的发明，而且为了保障其效益在全社会得到最大化，他解决了所有配套的技术。所有试图另辟径的公司都发现，高通公司的标准怎么也绕不开，因为高通已经把能想到的事情都想到了。

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

只要有一些训练数据，再定义一个最大化函数，采用EM算法，利用计算机经过若干次迭代，就可以得到所需要的模型。这实在是太美妙了，这也许是造物主刻意安排的，所以我把它称作上帝的算法。

前面的章节已经多次讨论到文本自动分类问题，一方面是因为今天互联网的各种产品和应用都需要用到这个技术；另一方面，这个技术可以应用到几乎所有分类中，比如用户的分类、词的分类、商品的分类，甚至生物特征和基因的分类，等等。这一章再介绍一些文本自动分类的技术，并借此说明在机器学习中最重要的一个方法——期望最大化算法（Expectation Maximization Algorithm）。这个算法，我称之为上帝的算法。

1　文本的自收敛分类

我们在前面的章节里已经介绍了两种文本分类算法，即利用事先设定好的类别对新的文本进行分类，以及自底向上地将文本两两比较进行聚类的方法。这两种方法，多少都有一些局限性，比如前一种方法需要有事先设定好的类别和文本中心（Centroids），后一种方法计算时间比较长。因此，我们在这里介绍一种新的文本分类的方法。和上述两种方法不同的是，这种方法既不需要事先设定好类别，也不需要对文本两两比较进行合并聚类，而是随机地挑出一些类别的中心，然后来优化这些中心，使它们和真实的聚类中心尽可能一致（即收敛）。当然，这种方法依然要用到文本TF-IDF向量和向量之间的余弦距离，这些概念在前面介绍过了，就不再重复了。

2　延伸阅读：期望最大化和收敛的必然性

可以把上面的思想扩展到更一般的机器学习问题中。上述算法实际上包含了两个过程和一组目标函数。这两个过程如下。

1. 根据现有的聚类结果，对所有数据（点）重新进行划分。如果把最终得到的分类结果看作是一个数学的模型，那么这些聚类的中心（值），以及每一个点和聚类的隶属关系，可以看成是这个模型的参数。
2. 根据重新划分的结果，得到新的聚类。

而目标函数就是上面的点到聚类的距离d和聚类之间的距离D，整个过程就是要最大化目标函数。

在一般性的问题中，如果有非常多的观测数据（点），可用类似上面的方法，让计算机不断迭代来学习一个模型。首先，根据现有的模型，计算各个观测数据输入到模型中的计算结果，这个过程称为期望值计算过程（Expectation），或E过程；接下来，重新计算模型参数，以最大化期望值。在上面的例子中，我们最大化D和-d，这个过程称为最大化的过程（Maximization），或M过程。这一类算法都称为EM算法。

前面介绍过的很多算法，其实都是EM算法，比如隐马尔可夫模型的训练方法Baum-Welch算法，以及最大熵模型的训练方法GIS算法。在 Baum-Welch算法中，E过程就是根据现有的模型计算每个状态之间转移的次数（可以是分数值）以及每个状态产生它们输出的次数，M过程就是根据这些次数重新估计隐马尔可夫模型的参数。这里最大化的目标函数就是观测值的概率。在最大熵模型的通用选代算法GIS中，E过程就是跟着现有的模型计算每一个特征的数学期望值，M过程就是根据这些特征的数学期望值和实际观测值的比值，调整模型参数。这里，最大化的目标函数是熵函数。

最后还要讨论一点，就是EM算法是否一定能保证获得全局最优解？如果我们优化的目标函数是一个凸函数，那么一定能保证得到全局最优解。所幸的是我们的熵函数是一个凸函数，如果在N维空间以欧氏距离做度量，聚类中我们试图优化的两个函数也是凸函数。但是，对应的很多情况，包括文本分类中的余弦距离都不保证是凸函数，因此有可能EM算法给出的是局部最佳解而非全局最佳解（见图27.5）。

小结

EM算法只需要有一些训练数据，定义一个最大化函数，剩下的事情就交给计算机了。经过若干次迭代，我们需要的模型就训练好了。这实在是太美妙了，这也许是造物主刻意安排的，所以我把它称作上帝的算法。

第28章　逻辑回归和搜索广告

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

搜索广告之所以比传统的在线展示广告（Display Ads）赚钱多很多，除了搜索者的意图明确外，更重要的是靠预测用户可能会点击哪些广告，来决定在搜索结果页中插入哪些广告。

1　搜索广告的发展

搜索广告基本上走过了三个阶段。第一个阶段是以早期Overture和百度的广告系统为代表，按广告主出价高低来排名的竞价排名广告。简单地说，谁给钱多，就优先展示谁的广告。为了支持这种做法，雅虎还给出了一个假设，出得起价钱的公司一定是好公司，因此不会破坏用户体验。但是这个假设等同于好货一定能淘汰劣货，事实并非如此，出得起价钱的公司常常是靠卖假药谋得暴利的公司。这样一来就破坏了用户体验，很快用户不再点这些广告了，久而久之，所有广告都乏人问津。如果这样持续多年，没有了点击量，广告商也就不来了，这个行业就要萎缩。

事实上，这种看上去挣钱多的方法，并没有给雅虎带来比Google更多的利润，它的单位搜索量带来的收入（一般以千次搜索量带来的收人来衡量，称为RPM）不到Google的一半。Google并不是简单地将出价高的广告放在前面，而是预测到哪个广告可能被点击，综合出价和点击率（Click Through Rate，CTR）等因素决定广告的投放。几年后，雅虎和百度看到自身与Google的差距，有样学样，推出了所谓的“Panama系统”和“凤巢系统”。它们相当于Google的第一个版本，可以看作是搜索广告的第二个阶段。这里面的关键技术就是预测用户可能点击候选广告的概率，或者称为点击率预估。第三个阶段其实是进一步的全局优化，与本章主题无关，就不赘述了。

……

现在麻烦了，这么多因素要用一个统一的数学模型来描述并不容易。更何况我们还希望这个模型能够随着数据量的增加越做越准确。早期有很多对经验值进行修正和近似的做法，但是在整合各个特征时，效果都不是很好。后来工业界普遍采用了逻辑回归模型（Logistic Regression Model）。

2　逻辑回归模型

上面的逻辑回归函数其实是一个一层的人工神经网络，如果需要训练的参数数量不多，则所有训练人工神经网络的方法都适用。但是，对于搜索广告的点击率预估这样的问题，需要训练的参数有上百万个，因此要求更有效的训练方法。读者可能已经发现，具有公式（28.1）形态的逻辑回归函数和前面介绍过的最大熵函数，在函数值和形态上有着共性，它们的训练方法也是类似的，训练最大熵模型的IIS方法可以直接用于训练逻辑回归函数的参数。

一个广告系统中，点击率预估机制的好坏决定了能否成倍提高单位搜索的广告收入。而目前Google和腾讯的广告系统在预估点击率都采用了逻辑回归函数。

小结

逻辑回归模型是一种将影响概率的不同因素结合在一起的指数模型。和很多指数模型（例如最大熵模型）一样，它们的训练方法相似，都可以采用通用选代算法GIS和改进的选代算法IIS来实现。除了在信息处理中的应用，逻辑回归模型还广泛应用于生物统计。

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

Google颇为神秘的云计算中最重要的MapReduce工具，其原理就是计算机算法中常用的“各个击破”算法，它的原理原来这么简单——将复杂的大问题分解成很多小问题分别求解，然后再把小问题的解合并成原始问题的解。由此可见，在生活中大量用到的、真正有用的方法常常都是简单朴实的。

1　分治算法的原理

分治算法是计算机科学中最漂亮的工具之一。它的基本原理是：将一个复杂的问题，分成若干个简单的子问题进行解决。然后，对子问题的结果进行合并，得到原有问题的解。

2　从分治算法到MapReduce

这就是MapReduce的根本原理。将一个大任务拆分成小的子任务，并且完成子任务的计算，这个过程叫作Map，将中间结果合并成最终结果，这个过程叫作Reduce。当然，如何将一个大矩阵自动拆分，保证各个服务器负载均衡，如何合并返回值，就是MapReduce在工程上所做的事情了。

在Google开发MapReduce之前，上述思想已经在很多高强度计算上应用了。我在约翰·霍普金斯大学训练最大熵模型时就遇到过类似的问题。我经常需要用20台左右的服务器（这在Google云计算出来前已经是非常奢侈了）同时工作。我工作的方式就是手工将这些大矩阵拆开并且推送（Push）到不同的服务器上，然后把结果组合起来。加州大学伯克利分校提供了一个在操作系统上检测各个子任务完成情况的工具，这样，我只需写一个批处理流水线来完成Map和Reduce这两个过程。唯一的差别是，有了MapReduce工具，所有的调度工作都是自动完成的，而在此以前，我需要手工完成计算机的调度工作。

小结

我们现在发现Google颇为神秘的云计算中最重要的MapReduce工具，其实原理就是计算机算法中常用的“各个击破”法，它的原理原来这么简单一将复杂的大问题分解成很多小问题分别求解，然后再把小问题的解合并成原始问题的解。由此可见，在生活中大量用到的、真正有用的方法往往简单而又朴实。

第30章　Google大脑和人工神经网络

Google大脑并不是一个什么都能思考的大脑，而是一个很能计算的人工神经网络。因此，与其说Google大脑很聪明,不如说它很能算。不过，换个角度来说，随着计算能力的不断提高，计算量大但简单的数学方法有时能够解决很复杂的问题。

2019年3月26日，美国计算机学会（ACM）公布了前一年（2018年）图灵奖评选的结果，对深度学习做出开创性贡献的三名美国和加拿大科学家本杰奥（Yoshua Bengio）、辛顿（Geoffrey Hinton）和莱昆（Yann LeCun）荣获该奖项。通常，在科技领域里最高的荣誉不是授予第一个吃螃蟹的人，而是授予最后一批还能做出重大贡献的幸运儿，本杰奥等三人就是这样的幸运儿。一方面，他们进人这个领域足够晚，很多可能的失败前人已经经历过了；另一方面他们进人这个领域又足够早，一些关键性问题还没有被解决。当然，他们也足够幸运，因为他们的理论一经提出，很快就被验证了，而最早验证他们理论的是Google。

2011年底，Google发布了一项新技术，基于深度学习（Deep Learning）的“Google大脑”。在对外的各种宣传中，这个“大脑”不仅“思考” 速度超快，而且比现有的计算机要“聪明”很多。为了证明它的聪明， Google列举了几个例子。比如，通过Google大脑的深度学习（训练）后，语音识别的错误率从13.6%下降至11.6%。大家可不要小看这两个百分点，要做到这一点，通常需要全世界语音识别专家们努力两年左右。而Google在语音识别方法上并未做什么新的研究，甚至没有使用更多的数据，只是用一个新的“大脑”重新学习了一遍原有声学模型的参数就做到了，可见这个“大脑”之聪明。又过了5年，在Google大脑基础架构之上开发出的AlphaGo围棋程序（AlphaGo研发团队领导者David Silver获得2019年图灵奖）则更是一鸣惊人，战胜了获得世界冠军最多的李世石九段，2017年又以3比0的总比分打败当时排名世界第一的柯洁九段，从此人类就进人一个下棋再也下不过计算机的时代了。

然而，如果你把Google的那个“大脑”打开来看一看，就会发现它其实并没有什么神秘可言，只不过是利用并行计算技术重新实现了一些人工神经网络（Artificial Neural Network）的训练方法。今天其他的深度学习工具，也是如此。因此，要说清楚Google大脑，就必须先说清楚什么是人工神经网络。

1　人工神经网络

2　训练人工神经网络

3　人工神经网络与贝叶斯网络的关系

从上面很多图中可以看到，人工神经网络与贝叶斯网络非常相似。比如图30.8所示的有向图，如果我们说它就是一个贝叶斯网络，也是完全正确的。人工神经网络和贝叶斯网络至少有这样几个共同点。

1. 它们都是有向图，每一个节点的取值只取决于前一级的节点，而与更前面的节点无关，也就是说遵从马尔可夫假设。
2. 它们的训练方法相似，这一点从上面的介绍中就能够看出来了。
3. 对于很多模式分类问题，这两种方法在效果上相似，也就是说很多用人工神经网络解决的问题，也能用贝叶斯网络解决，反之亦然，但是它们的效率可能会不同。如果把人工神经网络和贝叶斯网络都看成是统计模型，那么这两种模型的准确性也是类似的。
4. 它们的训练计算量都特别大，大家在使用人工神经网络时要有心理准备。

不过，人工神经网络与贝叶斯网络还是有不少差别的。

1. 人工神经网络在结构上是完全标准化的，而贝叶斯网络更灵活。 Google大脑选用人工神经网络，就是因为看中了它的标准化这一特点。
2. 虽然神经元函数为非线性函数，但是各个变量只能先进行线性组合，最后对一个变量（即前面组合出来的结果）进行非线性变换，因此用计算机实现起来比较容易。而在贝叶斯网络中，变量可以组合成任意的函数，毫无限制，在获得灵活性的同时，也增加了复杂性。
3. 贝叶斯网络更容易考虑（上下文）前后的相关性，因此可以解码一个输入的序列，比如将一段语音识别成文字，或者将一个英语句子翻译成中文。而人工神经网络的输出相对孤立，它可以识别一个个字，但是很难处理一个序列，因此它主要的应用常常是估计一个概率模型的参数，比如语音识别中声学模型参数的训练、机器翻译中语言模型参数的训练等，而不是作为解码器。

了解到人工神经网络和贝叶斯网络的异同，你会发现很多机器学习的数学工具其实是一通百通，并且可以根据实际问题找到最方便的工具。

4　延伸阅读：Google大脑

除了能够并行地训练人工神经网络的参数外，Google大脑在减少计算量方面做了两个改进。首先是降低每一次选代的计算量。Google大脑采用了随机梯度下降法（Stochastic Gradient Descent），而非前面介绍的梯度下降法。这种算法在计算成本函数时不必像梯度下降法那样对所有的样本都计算一遍，而只需要随机抽取少量的数据来计算成本函数，这样可以大大降低计算量，当然也会牺牲一点准确性。由于Google大脑训练的数据量很大，采用传统的梯度下降法每次选代的计算时间太长，因此平衡了计算时间和准确性后，采用了这种相对较快的算法。第二个改进是减少训练的选代次数。Google大脑采用比一般梯度下降法收敛更快的L-BFGS方法（Limited-memory Broyden Fletcher Goldfarb Shanno Method），其原理和随机梯度法相似，但要略微复杂些。它的好处是可以根据离最后目标的“远近”调整每次选代的步长，这样经过很少次的选代就能收敛，但是它每一次选代的计算量也会增加一点（因为要计算二阶导数）。另外，L-BFGS方法更容易并行化实现。

小结

人工神经网络是一个形式上非常简单但分类功能强大的机器学习工具，从中可以再次体会到数学中的简单之美。在现实生活中，真正能够通用的工具在形式上必定是简单的。

人工神经网络与其他机器学习的工具关联密切，这让我们能够触类旁通，这也是数学的美妙之处。 Google大脑并不是一个什么都能思考的大脑，而是一个很能计算的人工神经网络。与其说Google大脑很聪明，不如说它很能算。不过，换个角度来说，随着计算能力的不断提高，计算量大但简单的数学方法有时能够解决很复杂的问题。

第31章　区块链的数学基础——椭圆曲线加密原理

希尔伯特讲，“我们直到能够把一门自然科学的数学内核剥出并完全地揭示出来，才能够掌握它。”以比特币为代表的加密货币的基础是数学的算法，只有搞清楚加密货币的数学内核，我们才能了解它的本质。

1不对称、不透明之美

人们通常喜欢对称，厌恶不对称，觉得后者不完美。在获取信息时，大家都希望透明，因为不透明、藏着掖着总让人感觉不踏实。但是，不对称有时却自有其妙处与美感，比如黄金分割就是不对称的。对于信息安全来讲，完全透明、完全对称会带来很多的安全隐患。当自已是信息的拥有者时，我们其实并不希望别人可以获得我们的信息，特别是私密信息，只不过常常为了便利，不得不开放许多信息的访问权限，好让对方验证真伪，知道我们是谁，或者能够让对方进行一些统计，来为我们提供更好的服务。过去，我们不开放信息，很多事情就做不成，比如你向银行申请贷款时，几乎就是把所有个人和财务信息开放给了银行。

在完全开放信息的社会里，彻底保护信息安全几乎是天方夜谭。要想保护私有信息，特别是隐私，必须有一套不对称的机制，做到在特定授权的情况下，不需要拥有信息也能使用信息；在不授予访问信息的权限时，也能验证信息。而比特币的意义就在于，它证实了利用区块链能够做到上述这两件事。接下来，我们就说说区块链是如何让比特币做到不需要拥有信息，却能够验证信息的。

区块链由两个英文单词Block和Chain组成。顾名思义，它应该包含两方面的意思：Block即模块、单元或数据块的意思，它像一个存储信息的保险箱；Chain是链条的意思，即表示信息内容和交易的历史记录；交易的细节也存在Block中。因此，在一些地方区块链被比喻成是一个不断更新的账本，这是有一定道理的。但是区块链有三个普通账本不可能具备的优点，我们就以比特币为例展开说明。

……

最后，区块链可以成为一种按照约定自动执行的智能合约，而这种合约一旦达成，就不能更改，可以一步步地自动执行，这是一般账本做不到的。显然，区块链的这一性质可以用来解决前面提到的商业纠纷，比如三角债和拖欠农民工工资等问题。

关于区块链的这种形式带来的各种应用，我在《智能时代》一书中有详细的讲述，这里就不赘述了。

从上述三个特点可以看出，区块链给我们提供了超出原来信息加解密范围的应用场景。我们过去通常理解的信息安全是，我们用密钥对信息进行加密，得到加密信息，进行传输或存储，然后再用另一把密钥解密，恢复原来的信息。我们在第17章介绍密码学的数学原理时，已经接触到这种加密/解密的不对称性，它能够保证信息传输的安全。但是，区块链为它提供了一个新的应用场景，就是用一把密钥对信息加密后，让拿到解密钥匙（公钥）的人只能验证信息的真伪，而看不到信息本身。这就利用信息的不对称性保护了我们的隐私，因为大部分信息的使用者只需要验证信息，不需要拥有信息。比如我们在核实身份时便是如此。

具体到比特币所用到的区块链协议，以及今天大多数改进的协议，通常采用的是一种被称为椭圆曲线加密的方法。相比本书前面讲到的RSA加密算法，采用椭圆曲线加密方法可以用更短的密钥达到相当或更好的加密效果。那么，什么是椭圆曲线加密呢？我们就要从椭圆曲线及其性质说起。

2椭圆曲线加密的原理

综上，如果我告诉你一开始是从A经过B到C，一共走了K步，你可以推算出最后停到了Z，这一过程直观而简单。但是，如果我告诉你起点是 A，终点是Z，你要想猜出我经过了多少步完成上述过程，这几乎是不可能的，或者说，计算量是极大的。这种不对称性使得验证结果非常容易，但是想破解密码却难上加难。

……

椭圆曲线加密方法有很多种，它们的算法和密钥的长度虽然各不相同，但是它们的原理却大同小异。美国国家标准与技术局已经规定了这一类算法的最小密钥长度为160位，再往上还有192位、224位等。它们都比 RSA所要求的最短1024位短很多，这是椭圆曲线加密的优势所在。那么这么短的密钥安全么？2003年，一个研究团队用1万台PC花了一年半时间破解了一个较短的109位密钥。但是，破译的时间是随着密钥长度呈指数增长的，破解160位的密钥需要大约1亿倍的计算量，破译192位、 224位等密钥就更难了。因此，除非计算机的速度有百万倍的提升，否则很难破译椭圆曲线加密的信息。

小结

通过分析探讨比特币背后的数学基础，我们可以看到不对称性所带来的好处。它不仅可以解决信息安全问题，而且能将信息的访问和确认这两步分开，从根本上解决保护隐私的问题。

在实现区块链加密时，采用了非常简单的椭圆曲线。数学家和计算机科学家能想到通过在一条椭圆曲线上一次次求交点，来发明一种简单而漂亮的加密算法，可谓是匠心独运。当然，区块链的发明人利用这种加密方法，又发明了一整套信息验证机制，也是神来之笔。

第32章　大数据的威力——谈谈数据的重要性

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

1　数据的重要性

数据的重要性不仅体现在科学研究中，而且渗透到了我们社会生活的方方面面。在Google内部，产品经理们都遵循这样一个规则：在没有数据之前，不要给出任何结论。因为日常的很多感觉与数据给出的结论是相反的，如果不用数据说话，我们成功的概率就会小很多。为了说明这一点，不妨来看几个例子，来体会一下我们想象的结论和真实的数据差异有多大。

……

接着，我又问有多少人相信职业投资人所管理的基金能给他们带来比大盘更好的回报。几乎所有人都相信这一点，可是事实上70%（有时是 90%）的基金长期表现不如大盘。看到这个结论大家可能大感意外，但事实就是如此。这个例子说明我们的想象与现实的差距有多大，在没有获得足够的数据之前，我们难以作出正确的判断。顺便讲一句题外话，有的读者可能会问，如果无论是个人还是基金，表现都不如大盘好，那么钱都到哪儿去了？答案很简单，交易费和各种税（比如印花税、美国股市投资收入所得税等）首先吃掉了收益中的很大一部分，而基金经理的管理费则又吃掉了一大部分。一个动态管理的基金，如果每年收2%的管理费（常规），虽然看似不高，但是30-40年下来实际上吃掉了利润的一半”左右。股市在某种程度上是一个零和的游戏，证监会官员、交易所雇员的工资和各种奢侈的办公条件，其实都是羊毛出在羊身上，而基金经理开的豪车、住的豪宅都是投资人的钱。因此，如果一个散户投资人能真正做到“用数据说话”，只需奉行一条投资决策，那就是买指数基金。这当然不是我的发明，而是投资领域著名的经济学家威廉·夏普（William F. Sharpe）和伯顿·麦基尔（Burton G. Malkiel）等人一直倡导的。

扯了这么多闲话，只是为了强调一点：数据不仅在科学研究中，而且在生活的方方面面都很重要，它应该成为我们日常做决策的依据。

2　数据的统计和信息技术

有了数据之后，如何科学地使用数据，这就要用到一门应用科学——统计学了。今天很多大学里的非数学专业将概率和统计放在一门课里教授，但其实概率论和统计学虽然紧密相关，却是相对独立发展的。概率论是研究随机现象数量规律的数学分支。统计学是通过搜索、整理、分析数据的手段，以达到推断所测对象的本质，甚至预测对象未来的一门综合性科学。我们在前面章节中介绍了概率论在信息技术上的很多应用，而获得那些概率模型，依靠的是统计。

统计首先要求数据量充足。在第3章“统计语言模型”中我们讲过，对语言模型中所有参数（概率）的估计需要“足够多”的语料，这样得到的结果才有意义。那么为什么统计量要足够大呢？我们不妨看看下面这样一个例子。

……

除了要求数据量必须足够多，统计还要求采样的数据具有代表性。有些时候不是数据量足够大，统计结果就一定准确。统计所使用的数据必须与想要统计的目标相一致。为了说明这一点，下面来看一个有大量统计却没有得到准确估计的案例。

……

在搜索用到的诸多种数据中，最重要的数据有两类，即网页本身的数据和用户点击的数据。搜索引擎要想做得好，网页数据必须完备，也就是说，索引的数据量必须大，内容必须新，这一点不难理解，毕竟巧妇难为无米之炊。从工程上讲这是一件比烧钱的事情，只要投入足够的人力（工程师）和服务器就能做到。但是光有网页数据是不够的，还需要有大量的点击数据，也就是需要知道对于不同的搜索关键词，大部分的用户都点击了哪些搜索结果（网页）。比如对于“机器人”这个查询，网页A 点击了21000次，网页B点击了5000次，网页C点击1000次……根据这些点击数据，可以训练一个概率模型，来决定搜索结果的排列顺序（即按照A，B，C……这个次序）。这个模型中的搜索算法被称为“点击模型”，只要统计数量足够，这种根据点击决定的排名就非常准确。点击模型贡献了今天搜索排序至少60%一80%的权重，也就是说搜索算法中其他所有的因素加起来都不如它重要。

为了获得这样的点击数据，各家搜索引擎从一上线开始，就通过记录用户每次搜索的日志来收集用户的点击数据。遗憾的是，这些点击数据的积累是个漫长的过程，不可能像下载网页那样通过砸钱在短期内完成。对于那些不很常见的搜索（通常也称为长尾搜索），比如“毕加索早期作品介绍”，需要很长的时间才能收集到“足够多的数据”来训练模型。考虑到一些搜索结果的时效性，市场占有率较小的搜索引擎甚至在这些查询已经由热门变冷门之前，还没有凑齐那么多的统计数据，因此这些搜索引擎的点击模型就非常不准确。这才是微软的搜索引擎在很长时间里做不过Google的主要原因。同理，在中国，与百度相比，搜狗、搜搜或有道的市场占有率相差太大，搜索量可以说是微不足道，很难训练出有效的点击模型。如此一来，在搜索行业就形成了一种马太效应，即搜索量不足的搜索引擎因为用户点击数据量的不足，搜索质量会越变越差；相反，质量好的搜索引擎会因为数据量大而越变越好。

……

当然，数据对信息处理的帮助远不止在搜索质量这个特定的产品指标上，而是具有普遍意义。我们不妨再看两个例子，分别是Google如何利用大量数据来提高机器翻译质量，以及如何提高语音识别质量。

3　为什么需要大数据

大数据的好处远不只是成本和准确性的问题，它的优势还在于多维度（或叫全方位）。过去计算机能够存储和处理的数据通常有限，因此只收集与待解决问题相关的数据，这些数据只有很少的几个维度，而看似无关的维度都被省略掉了。这种限制也决定了特定的数据使用方式，即常常是先有假设或者结论，然后再用数据来验证。现在，云计算的出现使我们可以存储和处理大量关系很复杂甚至是原本看似没什么用的数据，工作的方法因此而改变。除了使用数据验证已有的结论外，还可以从这些数据本身出发，不带任何固有的想法，看看数据本身能够给出什么新的结论，这样一来，就可能会发现很多新的规律。比如百度百科中的数据乍一看杂乱无章，但其实数据之间有很多内在联系。在对这些大数据进行分析之前，产品经理们的头脑里并没有预先的假设，也不知道能得出什么样的结论。但是，最终通过对这些数据进行分析，发现了很多新的规律。我想，百度内部人士在第一时间看到这些结果时，恐怕也是会大跌眼镜的。

……

我之所以举医疗行业的例子，是因为除了IT行业，医疗保健是对大数据最热衷的行业。当然，另一个原因是Google和我本人对这个行业都比较热衷，比较容易举例子，但这并不表明大数据的应用只集中在这两个行业。

……

2013年，Google创立了一个叫Calico的公司，致力于用IT成果解决医疗问题，并且聘请了世界上最知名的生物制药专家、原基因泰克公司的 CEO阿瑟·李文森（Arthur D. Levinson）博士来主持这项富有创意的工作。身为苹果和基因泰克两家知名公司董事会主席的李文森以及他很多过去的同事，为什么要跑到一家毫无医疗和生物制药经验的IT公司去研究医疗问题呢？因为他们认为未来的世界是以数据为王的时代。很多难题，比如治愈癌症、防止衰老，靠传统的医学手段是无法解决的。要攻克这些难题，需要使用大数据相关的技术。

李文森博士在一次报告会上讲述了为什么今天人类依然无法治愈癌症，他认为主要有两方面的原因。首先，一种药是否有效，和人的基因密切相关。这样一来就需要针对不同基因的人使用不同的药，如果做到极致，就得为每一个人专门设计一种药。但是，这个想法即使行得通，也有一个成本的问题。按照他的估计，采用过去研制新药的传统做法，为特定的人研制一种抗癌新药的成本是10亿美元，当然不可能普及。第二，癌细胞的基因本身是在不断变化的。我们经常会听到这样的病例，一个患者使用一种抗癌药一开始效果很好，恢复得很快，但是后来这种药似乎不再起作用了，于是癌症复发而且控制不住。这是因为癌细胞的基因已经发生变化了，有别于原先的癌细胞，之前的药物自然也就不起作用了。据李文森博士介绍，目前最大的问题是，即使能为每一个人研制特定的抗癌药，现有的研制速度还是赶不上癌细胞变化的速度。针对上述两个问题（抗癌药需要因人而异，药物的研制必须快于细胞基因的变化），李文森博士认为必须依靠大数据，对人类共性的地方进行统计，这样很多研制新药的实验就不必重复进行了，而且在进行临床试验前，只需要进行少量的动物实验即可。最终，他认为可能会给每一位患者量身定制药物，成本控制在每个人5000美元以内。同时，由于大部分工作可以共享，对药品的改造周期可以非常短，使得药物的研制比癌细胞变化更快，从而有望治愈癌症。

目前，李文森及其同事正在利用Google的平台，整合全美国的医疗资源，试图解决人类延年益寿这个几千年来全世界的难题，希望他最终能给大家带来福音。

从上面这些例子中，我们可以看到大数据对信息产业以及其他产业的重大影响。现在，我们对大数据的重要性来做一个总结。首先，只有当一些随机事件的组合一同出现了很多次以后，才能得到有意义的统计规律；其次，大数据的采集过程是一个自然的过程，有利于消除主观性的偏差；当然，更重要的是，只有多维度的大数据才能让那些原本有联系，但似乎联系又不太紧密的事件反复出现，然后发现新的规律。最后，它可能是解决IT行业之外的一些难题（比如医疗）的钥匙。

小结

虽然人们对于数据的重要性早有认识，但是过去因为存储和计算条件的限制，一般认为数据量够用即可。随着信息技术的发展，当数据的计算和存储不再是问题时，人们发现超大量的数据会带来以前意想不到的惊喜，这才导致了大数据的兴起。

在未来的世界里，人们的生活会越来越离不开数据，很多围绕数据收集和处理的工作机会将不断涌现。而掌握处理和利用数据方法的人也必将成为新时代的成功者。推而广之，无论在什么领域，从事什么样的工作，谁懂得数据的重要性，谁会在工作中善用数据，就更有可能获得成功。

第33章　随机性带来的好处——量子密钥分发的数学原理

人们总是喜欢确定性而不喜欢随机性。但是，从对确定性规律的把握上升到对随机性规律的把握，恰恰是近代数学进步的标志。量子通信就是建立在把握有关随机性规律的基础之上。

如今我们每天都在和数据打交道，因此数据的安全就变得非常重要。到目前为止，还没有绝对的信息安全，而数据泄露的事情时有发生。

数据泄露无外乎有两种可能：在数据存储的地方被盗取，或者在数据传输的过程中被截获。要解决这个问题，最好的办法就是对数据进行加密。当然，理论上目前使用的所有加密算法都有可能被破解，只不过是时间问题。那么是否存在一种无法破解的密码呢？其实信息论的发明人香农早就指出了，一次性密码从理论上讲永远是安全的。但是要想在通信中使用这种密码，必须解决一个根本性的问题，就是如何让信息的发送方和接收方同时得到这一次性的密码。如果是由发送方传给接收方，密码的传输本身就有可能泄密，加密也就无从谈起了。近年来非常热门的量子通信，便是试图实现加密密钥的安全传输，确保保密通信不被破解。

虽然量子通信的概念来自量子力学中的量子纠缠，但是今天我们实现的实验性的量子通信密钥分发方法其实和量子纠缠没有任何关系，它用的是（光）量子的另一个特性，即对它进行观察后，它的状态会改变。当然，量子密钥分发（Quantum Key Distribution，QKD）这一套机制能够工作，背后靠的是数学上随机性的作用，接下来我们就分别从量子密钥分发的物理学原理和数学原理出发，介绍今天炙手可热的量子密钥分发技术。

1用（激光）量子的偏振方向传递信息

今天所说的量子通信，其实是一种特殊的激光通信。与传统激光通信不同，它不是把信息加载在振动的一束激光之上，而是利用一个个光子的某些特性对信息进行编码，直接传递信息。

我们知道光子既是一种粒子，又是一种波，其传播方向与振动方向垂直（见图33.1），这就是爱因斯坦指出的光的波粒二象性。光子有很多与振动相关的特性，比如它的（振动）频率和偏振的方向，均可人为控制。激光振动的频率是可控的，也可以用来传递信息，且已应用在今天的激光通信中，不过量子密钥分发则是利用了光子的偏振特性。

……

通常，随机性对我们来讲不是好事，但是在这里，利用这种性质恰好能设计出一种量子密钥分发的协议，以保证通信的安全。接下来我们就来说说它的原理。

2利用随机性保证信息安全

我们前面讲到，如果发送方所发送的光子振动方向都是垂直和水平的，而接收方偏振镜的光栅也是这两个方向的，那么接收方就可以准确无误地接收到发送方送来的信息。但是，如果发送方所发送的光子振动方向是呈45°和135°的，如果接收方还是把光栅的方向设置为水平和垂直的，那么接收的就是完全随机的信息。这个特性就被用来分发密钥，具体的做法是这样的。

……

上述这种通信协议被称为BB84协议，因为是查理斯·贝内特（Charles Bennett）和吉勒·布拉萨（Gilles Brassard）在1984年发表的，两个B字母，就是这两个人姓氏的首字母。后来，人们又在这个协议的基础上进行改进，有了其他的协议，但是其加密和通信原理并没有本质的变化。

在使用上述协议通信的过程中，发送方和接收方需要通过几次通信彼此确认密钥，而这个密钥只使用一次。如果要继续通信，就需要再产生和确认新的密钥。因此，这种做法实际上是用时间换取通信的安全性。在这个协议被提出来的头十几年里，没有什么需求让人觉得它很重要，因为当时一来没有那么多对信息安全的担心，二来通信的速率很慢，来来回回很多次才能确认一个一次性的密码，效率实在很低。但是，从2001 年开始，美国、欧盟、瑞士、日本和中国先后开始了量子通信的研究。

……

但是，量子通信绝不像很多媒体讲的是万能的。假如通信卫星真的被黑客攻击了，或者通信的光纤在半途被破坏了，虽然通信的双方知道有人在偷听，能够中断通信，不丢失保密信息，但是与此同时，它就无法保证正常的信息也能送出去了，就如同情报机关虽然抓不到对方的信使，却能把对方围堵在家里，不让消息发出。此外，虽然今天已经实现了上千千米量级的量子密钥分发，但是量子通信从实验到工程，再到商用，还有很长的路要走。

小结

量子通信并不是像很多媒体曲解的那样——靠量子纠缠实现通信，而是靠光量子的偏振特性承载信息，靠数学和信息论的基本原理保证它的保密性。在数学上，我们从中看到了不确定性带来的好处，它通过测定误码率来判断在密码分发的过程中是否泄密。这种方法把加密这种看似“阴谋”的事情变成了“阳谋”。在信息论方面，香农关于一次性密码永远是安全的想法，给人们指引了一个方向，循此，人们可以去寻找比现在公开密钥方式更安全的加密方法。

第34章　数学的极限——希尔伯特第十问题和机器智能的极限

世界上只有一小部分问题是数学问题，而数学问题中又只有极小的一部分问题有解。在这些问题中，今天已经找到相应算法的少之又少。因此，数学不是万能的，我们需要了解数学的边界在哪里。

今天，当计算机解决了越来越多的智能问题之后，人们对人工智能的态度从怀疑渐渐走向迷信。不了解人工智能背后技术的人开始凭着幻想猜测计算机的能力，即便是一些从业者也是糊里糊涂，完全忘却了计算机的能力有数学上的边界。这一边界，就如同物理学上无法超越的光速极限或绝对零度的极限一样，在最根本的层面上限制了人工智能的能力，这一边界与技术无关，仅取决于数学本身的限制。具体到今天大家使用的计算机，它有着两条不可逾越的边界，分别是由图灵和希尔伯特划定的。

1图灵划定计算机可计算问题的边界

对于机器智能也是如此，今天之所以机器智能显得极为强大，靠的是人们找到了让机器拥有智能的正确方法，即大数据、摩尔定律和数学模型这三个支柱。我们在前面各个章节中所介绍的内容，其实依然只是一部分数学模型而已。这些数学模型将各种形形色色的实际问题变成了计算问题，当然，这里面有一个前提，就是那些问题本质上就是数学问题，而且是可以用计算机计算的数学问题。但是，当计算机科学家们揭开了一个又一个这样的问题的数学本质之后，人们自然就不免会贪心地以为这样的进步是没有极限的，以致浪费时间去解决根本解决不了、可能也没有必要解决的问题。而那些行业之外的人若是有了这种想法，则难免会担心出现机器控制住人的事情。外行产生这样的想法情有可原，因为缺乏专业知识，但是如果不少从业者也想不清楚这个道理，那就是思维方式的问题了。大部分人的思维方式都是所谓的脚步累加，一点点进步，很难看清大的格局。

……

那么图灵是怎么给计算机划定边界的呢？这就要回溯到20世纪30年代中期，图灵对可计算这件事的思考。图灵思考了三个本源问题：第一，世界上是否所有的数学问题都有明确的答案；第二，如果一个问题有答案，能否通过有限步的计算得到答案，反过来，如果一个问题没有答案，能够通过有限步的推演证实这件事；第三，对于那些可以在有限步计算出来的数学问题，能否有一种机器，让它不断运转，最后当机器停下来的时候，那个数学问题就解决了。

图灵有两个精神导师，一位是冯·诺依曼，他在普林斯顿实际上是图灵的老师，另一位则是老一辈数学名家希尔伯特。图灵在思考可计算性问题时，读过冯·诺依曼写的一本介绍量子力学的专著《量子力学的数学原理》（Mathematical Foundations of Quantum Mechanics），并从中受到启发，认识到计算对应于确定性的机械运动，而人的意识则可能来自于测不准原理。图灵对于计算所具有的这种确定性的认识很重要，它保证了今天的计算机在同样条件下计算出来的结果是可重复的。当然，关于人的意识，图灵认为是不确定的，不属于计算的范畴。如果真是像图灵想的那样，那么宇宙本身就存在着大量数学问题之外的问题。事实上，与图灵同时代的数学家哥德尔在1930年便证明了数学不可能既是完备的，又是一致的，也就是说，一些命题即使是对的，我们也无法用数学证明它们。这被称为哥德尔不完全性定理，它说明数学的方法不是万能的。

当然，哥德尔的判定说起来有些绕口，听起来有点难以理解，但是我们普通人即便根据生活的经验，也能感受到这样的结论。比如，我们经常看到这样的新闻，一个看似并不难识破的骗局，为什么永远都会有人相信，而且同样的骗局会在几百年间不断地有人上当？这是因为你如果用骗子的思维方式去思考，则永远不可能识破骗局。那些上当受骗者心里的疙瘩，根本不是用理性逻辑能够解开的，他们所面临的问题也就更不是数学问题了。类似地，弗洛伊德所提出的很多问题，也是完全无法用数学建模解决的。因此，我们得承认数学不等于一切。

接下来，如果把要关注解决的问题局限于数学问题本身，是否它们就都有明确的答案呢？我们知道，今天很多数学问题并没有明确的答案，比如不存在一组正整数x，y，z，让它们满足$x^3+y^3=z^3$。这个问题实际上是著名的费马大定理的一个特例，而这个定理本身已于1994年由英国著名数学家怀尔斯（Andrew Wiles）证明了，也就是说，它是无解的。当然，不管怎么说，知道一个问题无解也算是有了答案。但是，是否还存在一些问题，我们根本无法判定答案存在与否呢？如果有，那么这一类问题显然是无法通过计算来解决的。在这一方面给了图灵启发的是希尔伯特。

2希尔伯特划定有解数学问题的边界

1900年，希尔伯特在国际数学大会上提出了23个（当时还无解的）著名的数学问题，其中第十个问题讲的是：

“任意一个（多项式）不定方程，能否通过有限步的运算，判定它是否存在整数解。”

所谓不定方程（也被称为丢番图方程，Diophantine equation），就是指有两个或更多未知数的方程，它们的解可能有无穷多个。为了对这个问题有感性认识，我们不妨看三个特例。

……

如果对希尔伯特第十问题（简称第十问题）普遍的答案是否定的，那么就说明很多数学问题其实上帝也不知道答案是否存在，因为不定方程求解问题还只是数学问题中很小的一部分。对于连答案存在与否都无法判定的问题，答案自然是找不到的，我们也就不用费心去解决这一类问题了。正是希尔伯特对数学问题边界的思考，让图灵明白了计算的极限所在。

当然，图灵自己并没有解决第十问题，只是隐约觉得大部分数学问题并没有答案。在第二次世界大战之后，欧美很多数学家都致力于解决第十问题，并取得了一些进展。在20世纪60年代，被公认最有可能解决这个问题的是美国数学家朱莉·罗宾逊。罗宾逊教授可能是20世纪最著名的女数学家，后来担任过世界数学大会的主席。虽然她在这个问题上取得了不少成就，但是最后的几步始终跨越不过去。在纯粹数学这个领域，常常是英雄出少年，1970年，苏联天才的数学家尤里·马蒂亚塞维奇（Yuri Matiyasevich）在大学毕业的第二年，就解决了第十问题。因而，今天对这个问题结论的表述，也被称为马蒂亚塞维奇定理。马蒂亚塞维奇严格地证明了，除了极少数特例，在一般情况下，无法通过有限步的运算，判定一个不定方程是否存在整数解。

第十问题的解决，对人类在认知上的冲击，远比它在数学上的影响还要大，因为它向世人宣告了很多问题我们无从得知是否有解。如果连是否有解都不知道，就更不可能通过计算来解决它们了。更重要的是，这种无法判定是否有解的问题，要远比有答案的问题多得多。基于这个事实，我们就可以用一张图（见图34.4）来总结一下上面提到的各种问题之间的关系。

在图34.4中我们可以看到，世界上只有一部分问题可以最终转化为数学问题。而在数学问题中，也只有一部分问题可以判定有无答案，这些问题就是我们所说的可判定问题。当然，对可判定问题判定的结果有两个，答案存在或者不存在。只有第一类答案存在的问题我们才有希望找到答案。因此，有答案的数学问题，不过是世界上所有问题中很少的一部分。

那么，有答案的数学问题是否都能够用计算机解决呢？那就要看计算机是怎么设计的了。1936年，图灵提出了一种抽象的计算机的数学模型，这就是后来人们常说的图灵机。图灵机这种数学模型在逻辑上非常强大，任何可以通过有限步逻辑和数学运算解决的问题，从理论上讲都可以遵循一个设定的过程，在图灵机上完成。今天的各种计算机，哪怕再复杂，也不过是图灵机这种模型的一种具体实现方式。不仅如此，今天那些还没有实现的假想的计算机，比如基于量子计算的计算机，在逻辑上也并没有超出图灵机的范畴。因此，在计算机科学领域，人们就把能够用图灵机计算的问题称为可计算的问题。

可计算的问题是有答案问题的一个子集，但是，这个子集是否等同于“有答案问题”这一全集，今天依然有争议：一方面，人们总可以构建出一些类似论的数学问题，显然无法用图灵机来解决；另一方面，在现实世界里是否有这样的问题存在，或者说这些构建出来的问题是否有意义，很多人觉得暂时没有必要去考虑。但不管怎么讲，依据丘奇和图灵这两位数学家对可计算问题的描述（也就是所谓的丘奇-图灵论题），有明确算法的任何问题都是可计算的，至于没有明确算法的问题，计算也无从谈起。

对于理论上可计算的问题，今天在工程上未必能够实现，因为一个问题虽然只要是能够用图灵机在有限步骤内解决，就被认为是可计算的，但是这个有限步骤可以是非常多步骤，计算时间可以特别长，长到宇宙灭亡还没有算完都没有关系。比如说一个计算复杂度是NP完全的问题，就可能永远都算不完，但却是可以计算的。此外，图灵机没有存储容量的限制，这在现实中也是不可能的。

如果把上面提到的这些问题的彼此关系再次总结一下，就会很清楚人工智能的边界了。从图34.5中可以看出，理想状态的图灵机可以解决的问题，只是有答案的问题中的一部分，而在今天和未来，在工程上可以解决的问题都不会超出可计算这一范畴。当然，很多可以用工程方法解决的问题并非人工智能问题，因此今天人工智能能够解决的问题，只是有答案问题中很小的一部分。如果结合图34.4所示的一个个彼此嵌套的集合，就更能看出人工智能的边界。

今天，我们所要担心的不是人工智能或计算机有多么强大，更不应觉得它们无所不能，因为它们的边界已经清清楚楚地由数学的边界划定了。我们今天所遇到的问题反而是不知道怎样将一些应用场景转化为计算机能够解决的数学问题。整本《数学之美》，其实讲的都是这件事。

从图34.4和图34.5可以看出，人工智能所能解决的问题真的只是世界上问题的很小一部分。对人工智能领域而言，如今尚未解决的问题还非常多，无论是使用者还是从业者，都应该设法解决各种人工智能问题，而不是杞人忧天，担心人工智能这一工具太强大了。对非计算机行业的人来讲，世界上还有很多需要由人来解决的问题，如何利用好人工智能工具，更有效地解决属于人的问题，才是应该给予更多关注的。

3延伸阅读：关于图灵机

最后，需要说明的是，如果有两种图灵机模型A和B，A可以模拟B的全部运算，B也可以模拟A的全部运算，则称它们等价。在不考虑效率的情况下，等价的图灵机模型解决问题的能力是相同的。一种特别的情况是，字母表$\Gamma$只有0和1两种状态，它和任意字母表的图灵机是等价的。因此，今天的计算机无论是采用二进制，还是其他什么进制，解决问题的能力都是相同的。一些媒体宣传量子计算突破了二进制，就能解决今天计算机解决不了的问题，这种说法是不对的，因为任何复杂进制的计算机，都与二进制的计算机等价。

小结

通过希尔伯特和图灵等人对于可计算这件事情边界的思考，我们可以看到一种不同于常人的思维方法一不是一点点地向前试探边界在哪里，而是高屋建瓴地从理论上找到一个不能越过的硬边界。知道边界在哪里不是我们的厄运，而是福气，因为我们可以集中精力在边界内解决问题，而不是把精力耗费在寻找边界之外可能并不存在的答案。

附录计算复杂度

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

对计算机算法来说，虽然衡量其好坏的标准非常多，比如运算速度的快慢、对存储量的需求大小、是否容易理解、是否容易实现，等等，但是为了便于公平地比较，我们需要一个客观的标准。这个标准就是算法的复杂程度。虽然1965年计算机科学家尤里斯·哈特马尼斯（Juris Hartmanis）和理查德·斯坦恩斯（Richard Stearns）在《论算法的计算复杂度》一文中提出了这个概念，并且二人因此在后来获得了图灵奖，但是最早将计算复杂度严格量化衡量的是著名计算机科学家、算法分析之父高德纳。高德纳的贡献在于找到了一种方法，使得一个算法好坏的度量和问题的大小不再有关，这是一个了不起的贡献。

如果一个算法的计算量不超过N的多项式函数（Polynomia lFunction），那么称这个算法是多项式函数复杂度的。如果一个问题存在一个多项式复杂度的算法，这个问题称为P问题（Polynomial的首字母）。这类问题被认为是计算机可以“有效”解决的。但是，如果一个算法的计算量比N的多项式函数还高，虽然从理论上讲如果有足够的时间也是可以计算的（图灵机概念下的可计算），但是实际上是做不到的。这时我们称它为非多项式（Non-polynomial）问题。比如找到每一步围棋的最佳走法就是这样的问题。

但是很多问题不是非黑即白的，要么有多项式复杂度的算法，要么没有。有一些问题虽然迄今为止还没有找到多项式复杂度的解，但是不等于以后找不到这样的解。在非多项式问题中，有一类问题即非确定的多项式（Nondeterministic Polynomial，NP）问题特别引起计算机科学家的关注。NP问题的重要性并非来自它可能有多项式时间的算法，事实上绝大多数理论计算机学者都认为NP不可能有多项式时间的算法，即P不等于NP。NP问题之所以重要的一个原因是现实中的绝大多数问题都是NP 的，另外它与密码理论也有重要的联系。如果一个问题，我们能够在多项式复杂度的时间里证实一个答案的正确与否，则不论目前这个问题是否能找到多项式复杂度的算法，都称这个问题为NP问题。

显然P问题是NP问题的一个特殊的子集。而NP问题集合中不知道是否属于P问题的那部分，即现在尚未找到多项式复杂度算法的问题，是否永远找不到多项式复杂度的算法呢？在这上面计算机科学家们有争议。有人认为确实找不到，但是有人认为最终能找到，他们认为只要一个问题能在多项式复杂度内证实答案正确与否，就能最终找到多项式复杂度的算法。如果真是这样的话，那么到时候所有的NP问题将变回为P问题。

在P问题与NP问题的一个重要研究进展是20世纪70年代初库克（Stephen Cook）和李文（Leonid Levin）在NP问题中发现一个被称作 NPC（NP-Complete）的特殊的问题类，所有的NP问题都可以在多项式时间内归约到NPC问题。这个发现被称为库克-李文定理。无疑NPC 问题是NP问题中最难的问题，因为如果任何一个NPC问题找到了多项式算法，那么所有的NP问题都可以用这个算法解决了，也就是NP=P了。

对于计算复杂度至少是NP完全（NP-Complete）甚至更大的问题，我们称它为NP困难（NP-Hard）问题。P问题、NP问题、NP完全问题和 NP困难问题的关系如图A.1所示。

寻找一个问题的计算机算法，首先要寻找多项式复杂度的算法。但是，对于那些至今找不到这样的算法而在应用中又无法回避的问题，比如贝叶斯网络的训练算法，我们只好简化问题找近似解了。

数学在计算机科学中的一个重要作用，就是找到计算复杂度尽可能低的解。同时，对于那些NP完全问题或者NP困难问题，找到近似解。

第三版后记

然而，在其他公司，包括美国一些还挂着高科技头衔的二流IT公司里，山寨情况依然很普遍。在国内，创业小公司做事情重量不重质，倒也无可厚非；但是，上了市、有了钱，甚至利润已经成为世界上数得上的公司，做事情依然如此就不免让人觉得太过随意、太缺乏追求了。很多公司都把精力和财力花在了怎样让产品显得花哨，或者如何购买流量上面，却很少愿意花力气修炼内功，没有把资源用在刀刃上。因此，我觉得有必要对“数学之美”进行系统化的整理，增加更多涉及专业技术的内容，以便让IT公司的工程主管们能够带领部属提高工程水平，逐渐远离山寨，让这些公司能够尽快成长为世界一流的IT公司。当然，我更希望中国做工程的年轻人，能够体会到在信息技术行业做事情的正确方法，以便在职业和生活上都获得成功。

……

写一本好书首先要选好素材，然后才是写作本身。

在选材方面，我多少有些工作上的便利，因为在长达20多年的时间里，我一直在语言信息处理、互联网技术、数据挖掘和机器学习等领域做研究和产品开发，因此有不少一手的经验。不过，这些领域都博大精深且发展迅速，而我所做的研究和开发工作也只涵盖了其中很小的一部分。因此，我着重介绍了我涉足过的比较有资格、有信心写的主题。我希望这本书能起到抛砖引玉的作用，让更多的专家愿意将自已的工作心得分享出来，供大家学习参考。对于大众读者，我则希望这本书可以通过一些实例，帮助大家体悟数学之道，领悟数学之美，以便今后解决实际问题时能够举一反三。

在写作方面，对我帮助最大的其实是两本书和一个节目。我在初中时读了《从一到无穷大》（One Two Three Infinity），这是一本介绍宇宙的科普读物。作者乔治·伽莫夫是美籍俄裔著名物理学家，他花了很多时间创作科普读物，影响了一代又一代人。第二本书是英国著名物理学家霍金的《时间简史》（A Brief History Of Time），霍金用最简单的语言把深奥的宇宙学原理讲出来，让这部科普读物成为全球畅销书。影响我的一个节目是美国著名演员摩根·弗里曼担任旁白和主持人的《穿越虫洞》（Through the Wormhole）。我的写作大多是在飞机上完成的，写作累了便看看电视节目，一次碰巧找到《穿越虫洞》，一个把当今最前沿的物理学知识做得浅显易懂的节目。节目中有包括很多诺贝尔奖获奖者在内的一流物理学家和数学家介绍他们的工作，这些人有一个共同的本领，就是能用很简单的比喻将所在领域内最深奥的道理说清楚，让大众容易理解。我想这可能正是他们成为世界顶级科学家的原因，他们一方面对自己的领域非常精通，同时他们又能用大白话把道理讲得明明白白。世界上最好的学者总是有办法深人浅出地把大道理讲给外行听，而不是故弄玄虚地把简单问题复杂化。因此，在写作《数学之美》时，我一直以伽莫夫、霍金等科学家为榜样，力图将数学之美展现给所有普通读者，而不只是有相关专业背景的读者。为了方便读者利用零碎的闲暇时间阅读，我在写作时尽量让各章相对独立、自成一体，这样读起来不会有多大压力，毕竟，让大部分读者从头到尾连续读一本以数学知识为主的书，总是有些困难的。

索引