朱律读想 I 读吴军《数学之美》

八年前，“数学之美”系列文章原刊载于谷歌黑板报，获得上百万次点击，得到读者高度评价。读者说，读了“数学之美”，才发现大学时学的数学知识，比如马尔可夫链、矩阵计算，甚至余弦函数原来都如此亲切，并且栩栩如生，才发现自然语言和信息处理这么有趣。 在纸本书的创作中，作者几乎把所 有文章都重写了一遍，为的是把高深的数学原理讲得更加通俗易懂，让非专业读者也能领略数学的魅力。读者通过具体的例子学到的是思考问题的方式 —— 如何化繁为简，如何用数学去解决工程问题，如何跳出固有思维不断去思考创新。

朱律读想 I 读吴军《数学之美》

介绍

关于作者

吴军，计算机科学家，硅谷投资人。畅销书作家《文明之光》、《智能时代》、《浪潮之巅》、《硅谷之谜》等

关于本书

本书主要介绍了在计算机领域的底层逻辑中数学的重要性。会让人觉得数学真的不是一门索然无味的学科。

数学的用处

解决文字校验处理自然语言计算机句子的出现概率判断句子是否正确计算机新闻分类余弦定理判断特种向量间的夹角确定新闻的类别

数学为什么这么有用

帮助发现仅凭经验无法发现的规律，找到仅凭经验无法总结出来的办法发现行星围绕恒星的运转规律大幅优化全拼输入法

数学之美是简单之美

数学应用背后所包含的数学思想是简单的计算机基础：布尔代数计算机处理自然语言全拼输入法输入效率的提高

数学并不神秘，深入了解数学之“道”，发现真正数学之美

重点

各种数学的应用

离散数学：包括数理逻辑，集合论，图论和近世代数四个分支

搜索

类似在图书馆利用索引卡片找书

数据库查找，底层就是布尔运算

广度优先算法BFS

深度优先算法DFS

google的pagerank，加入链接

网络爬虫：利用哈希表记录网页下载信息

地图查找：有限状态机，基于概论的有限状态机

新闻分类：利用余弦定理计算特征向量的夹角

加密：公钥，私钥

搜索作弊：重复关键词，本质是在搜索中加入了噪音；反作弊就是消除噪音

汉字输入

双拼，五笔，汉字编码输入都是为了降低单字敲击次数，但违背认知科学原理，实际销量很低

利用动态规划算法实现拼音到汉字的快速转换

邮件黑名单：布隆过滤器

算法结构

计算机算法的效率是用计算复杂度来衡量

马尔科夫链：描述了一种状态序列，与每个状态值取决于前面有限个状态

贝叶斯网络：加权又向图，不受马尔科夫链结构的约束，可以准确描述事件之间的相关性，马尔科夫链是贝叶斯网络的特例，贝叶斯网络是马尔科夫链的推广；

网络中每个节点的概率都可以用贝叶斯公式计算

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

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

期望最大值算法

在一般性的问题中，如果有非常多的观测数据（点），可用类似上面的方法，让计算机不断迭代来学习一个模型。首先，根据现有的模型，计算各个观测数据输入到模型中的计算结果，这个过程称为期望值计算过程（Expectation），或E过程；接下来，重

距离更近，根据我们的算法，它将被安排到第j 类中。不难证明d (i +1)＜d (i )，同时D (i +1)＞D (i )。 好了，知道了每一步迭代后，我们都离目标（最佳分类）更近了一步，直到最终达到最佳分类。 可以把上面的思想扩展到更一般的机器学习问题中。上述算法实际上包含了两个过程和一组目标函数。这两个过程如下。 1．根据现有的聚类结果，对所有数据（点）重新进行划分。如果把最终得到的分类结果看作是一个数学的模型，那么这些聚类的中心（值），以及每一个点和聚类的隶属关系，可以看成是这个模型的参数。 2．根据重新划分的结果，得到新的聚类。 而目标函数就是上面的点到聚类的距离d 和聚类之间的距离D ，整个过程就是要最大化目标函数。 在一般性的问题中，如果有非常多的观测数据（点），可用类似上面的方法，让计算机不断迭代来学习一个模型。首先，根据现有的模型，计算各个观测数据输入到模型中的计算结果，这个过程称为期望值计算过程（Expectation），或E过程；接下来，重新计算模型参数，以最大化期望值。在上面的例子中，我们最大化和D -d ，这个过程称为最大化的过程（Maximization），或M过程。这一类算法都称为EM算法。 前面介绍过的很多算法，其实都是EM算法，比如隐马尔可夫模型的训练方法Baum-Welch算法，以及最大熵模型的训练方法GIS算法。在Baum-Welch算法中，E过程就是根据现有的模型计算每个状态之间转移的次数（可以是分数值）以及每个状态产生它们输出的次数，M过程就是根据这些次数重新估计隐马尔可夫模型的参数。这里最大化的目标函数就是观测值的概率。在最大熵模型的通用迭代算法GIS中，E过程就是跟着现有的模型计算每一个特征的数学期望值，M过程就是根据这些特征的数学期望值和实际观测值的比值，调整模型参数。这里，最大化的目标函数是熵函数。

维比特算法：一种动态规划算法，解决任何一个图中最短路径问题，应用在CDMA

MapReduce：

分治算法：将一个复杂问题分成若干简单的子问题进行解决

将一个大任务拆成小的子任务，并完成子任务的计算，这个过程叫Map，将中间结果和病虫害最终结果，这个过程叫Reduce

托勒密（地心说，40-60个圆形构成的完美轨道）→哥白尼（日心说）→开普勒（三个定律，行星的椭圆形轨道）

前言

今天的电视、手机和互联网，都遵循信息论规律，而整个信息论的基础就是数学。如果往更远看，我们自然语言和文字的起源背后都受到数学规律的支配

数学是解决语音识别、机器翻译和自然语言处理等问题最好工具

数学的本质常常是简单而直接的

01：文字和语言VS数字和信息

数字、文字和自然语言都是信息的载体，而非信息本身

文明发展过程中，概念概括和归类在在原理上与今天自然语言处理或机器学习的聚类有很大的相似性。但聚类会带来歧义，但对上下文建立的概率模型再好，也无法完全消除歧义，这是语言从产生伊始固有的特点

罗塞塔石碑的破译对于自然语言处理的两点指导意义：

信息冗余是信息安全的保障

语言数据（语料）尤其是双语或者多语的对照语料对翻译至关重要，也是从事机器翻译研究的基础

从象形文字到拼音文字是一个飞跃，因为人类在描述物体的方式上，从物体的外表到抽象的概念，同时不自觉地采用了对信息的编码

梁南元 分字查

的梁南元教授提出的。“查字典”的方法，其实就是把一个句子从左向右扫描一遍，遇到字典里有的词就标识出来，遇到复合词（比如“上海大学”）就找最长的词匹配，遇到不认识的字串就分割成单字词，于是简单的分词就完成了。这种简单的分词方法完全能处理上面例子中的句子。当我们从左到右扫描时，先遇到“中”这个字，它本身是一个单字词，我们可以在这里做一个切割，但是，当我们再遇到“国”字时，发现它可以和前面的“中”字组成一个更长的词，因此，我们就将分割点放在“中国”的后面。接下来，我们发现“中国”不会和后面的字组成更长的词，那么这个分割点就最终确定了。

郭进

，语言中的歧义性伴随着语言的发展，困扰了学者们上千年。在中国古代，断句和说文解字从根本上讲，就是消除歧义性，而不同学者之间的看法也显然不相同。各种春秋的正义或者对论语的注释，就是各家按照自己的理解消除歧义性。分词的二义性是语言歧义性的一部分。20世纪90年代以前，海内外不少学者试图用一些文法规则来解决分词的二义性问题，都不是很成功。当然也有一些学者开始注意到统计信息的作用，但是并没有找到有完善理论基础的正确方法。1990年前后，当时在清华大学电子工程系工作的郭进博士用统计语言模型成功解决了分词二义性问题，将汉语分词的错误率降低了一个数量级。

…等都是汉语的词，上述各种分词结果可能产生不同数量的词串，因为我用了k,m,n

三个不同的下标表示这个句子在采用不同分词结果时词的数目。那么最好的一种分词方法应该保证分完词后这个句子出现的概率最大。也就是说，如果A

动态规划（DynamicProgramming）的问题，并利用维特比（Viterbi）算法快速地找到最佳分词（

。中文分词方法可以帮助判别英语单词的边界。

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

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

1950然后阿兰·图兰在《思想》杂志发表“计算的机器和智能”论文，提出“图灵测试”

早期20年（20世纪50年代到70年代），科学家们错误地迷信基于规则进行自然语言处理的方法，希望让计算机理解自然语言，需要分析语句和获取语义

直至20世纪70年代，基于数学模型和统计的方法，自然语言处理才进入实质发展阶段

03：统计语言模型

计算机处理自然语言，基本问题是考虑自然语言的上下文相关的信息表达和传递特点来建立数学模型，即统计语言模型

其广泛使用于机器翻译、语音识别、印刷体或手写体识别、拼写纠错、汉字输入和文献查询

统计语言模型主要以概率论和数理统计来分析，事实证明，其比任何已知的借助某种规则的解决方法更有效（如Googel Voice以及李开复对语音识别问题的简化）

04：谈谈中文分词

利用统计语言模型分词的方法，重点是找出多次分词方法中概率最大的，即为最好的分词方法

为避免穷举每种分词方法概率巨大的计算量，可将其看成是动态规划问题，利用维特比算法找到最佳分词

利用统计语言模型进行分词，也有其局限性，在于在特定情况下无法保证百分之百准确，但真实文本中几乎不会发生特定情况

如“此地安能居住，其人好不悲伤”

统计语言模型广泛应用后，不同分词器产生的结果差异要远小于人之间的看法差异

人工分词不一致的原因是在不同应用中，人们对词的颗粒度认识不一

但对于语言模型，与其根据应用构造不同的分词器，不如将分词器支持不同层次的词的切分

人类信息交流的发展贯穿了人类的进化和文明的全过程。而自然语言是人类交流信息的工具，语言和通信的联系是天然的。通信的本质就是一个编解码和传输的过程。但是自然语言处理早期的努力都集中在语法、语义和知识表述上，离通信的原理越走越远，而这样离答案也就越来越远。当自然语言处理的问题回归到通信系统中的解码问题时，很多难题都迎刃而解了。

05：隐含马尔可夫模型（本章需进一步学习研究概率论）

基于马尔可夫假设和独立输出假设，可计算出某个特定状态产生出输出符号的概率

需要训练算法（鲍姆-韦尔奇算法）和使用时的解码算法（维特比算法）

最早应用于语音识别，后陆续成功应用于机器翻译、拼写纠错、手写体识别、图像处理、基因序列分析等，还可应用于股票预测和投资

隐含马尔可夫模型的三个基本问题：

给定一个模型，如何计算某个特定的输出序列的概率

给定一个模型和某个特定的输出序列，如何找到最可能产生这个输出的状态序列

给定足够量的观测数据，如何估计隐含马尔可夫模型的参数

。20世纪80年代末李开复博士坚持采用隐马尔可夫模型的框架，成功研发出了世界上第一个大词汇量连续语音识别系统Sphinx。接下来，隐马尔可夫模型陆续成功地应用于机器翻译、拼写纠错、手写体识别、图像处理、基因序列分析等很多IT领域，近20年来，它还广泛应用于股票预测和投资。

王作英教授学习、研究语音识别时，他给了我几十篇文献。给我印象最深的就是贾里尼克和李开复的文章，它们的核心思想就是隐马尔可夫模型。复杂的语音识别问题居然能如此简单地表述、解决，令我由衷地感叹数学模型之妙。

06：信息的度量和作用

信息量就等于不确定性的多少

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

信息熵（符号H，单位比特），对于任意一个随机变量，变量的不确定性越大，熵就越大，所需信息量也就越大

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

在第二次世界大战中，当纳粹德国兵临莫斯科城下时，斯大林在欧洲已经无兵可派，而他们在西伯利亚的中苏边界却有60万大军不敢使用，因为苏联人不知道德国的轴心国盟友日本当时的军事策略是北上进攻苏联，还是南下和美国开战。如果是南下，那么苏联人就可以放心大胆地从亚洲撤回60万大军增援莫斯科会战。事实上日本人选择了南下，其直接行动是后来的偷袭珍珠港，但是苏联人并不知晓。斯大林不能猜，因为猜错了后果是很严重的。这个“猜”既是指扔钢镚儿似的卜卦，也包括主观的臆断。最后，传奇间谍佐尔格向莫斯科发去了信息量仅1比特却价值无限的情报（信息）：“日本将南下”，于是苏联就把西伯利亚所有的军队调往了欧洲战场。后面的故事大家都知道了。

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

弗里德时克·贾里尼克（吴军称呼为“弗莱德”）-将数学原理应用于自然语言处理领域的大师

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

贾里尼克与吴军对少年教育的看法：

中小学生花时间读书并不重要，而是社会经验、生活能力以及那时树立的志向很重要

中学阶段多读的课程，在大学阶段因理解能力更强会尽快学会，因此中小学优势会在大学丧失

学习教育是一非子的过程，很多中国中学成绩好的学生进入名校后会出现读书动力不足的情况

书本内容早学和晚学都一样，但错过成长阶段却无法补回来

吴军认为：一个人相要在自己的领域做到世界一流，他的周围必须有非常多的一流人物

贾里尼克的贡献：

上世纪70年代在IBM时提出统计语音识别的框架结构，将语音识别当成通信问题，是今天自然语言处理的基础

发明的BCJR算法是今天数字通信中应用最广的两个算法之一（另一个是维特比算法）

1994年在约翰·霍普金斯大学建立了世界著名的CLSP实验室

两件大事：政府主管申请经费、邀请顶级科学家和学生在实验室工作

两件小事：招募了潜力年轻学者、暑期安排学生到世界最好的公司实习

水门事件

（1972年）恰恰是统计语音识别和自然语言处理开始的时间，而因莱温斯基事件弹劾克林顿总统也正好发生于当时会议的前一年。

贾里尼克在康奈尔十年磨一剑，潜心研究信息论，终于悟出了自然语言处理的真谛。

08：简单之美：布尔代数和搜索引擎的索引

所有的搜索产品都有：自动下载尽可能多网页（下载）、建立快速有效的索引（索引）、根据相关性进行公平准确的排序（排序）三个基本服务

布尔代数是1854年英国的一名中学数学老师布尔发布的《思维规律》，展示用数学方法解决逻辑问题

两个运算元素：1（TURE，真）和0（FALSE,假），三种运算：与（AND)，或（OR),非（NOT)

后来1938年香蕉农在硕士认文中指出布尔代数可实现开关电路，使布尔代数成为数字电路的基础

布尔运算对于搜索的应用主要集中在文献检索，判断是否包含关键词

建立有效快速的索引而非扫描所有文本，最简单的索引结构是用很长的二进制判断每篇文献中的关键字

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

，而且远比古高尔（googol，10100

）要小得

目前主要的搜索引擎都是对所有词进行索引，并通过分布式存储避免数据宠大，同时通过对索引进行分级管理实现有效访问

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

09：图论和网络爬虫

图论的遍历算法——广度优先搜索、深度优先搜索

何自动下载互联网所有的网页呢？这需要用到图论中的遍历（Travers

关于网络爬虫

世界上第一个网络爬虫是由麻省理工学院的学生马休·格雷在1993年写成

一个商业网络爬虫需要成千上万个服务器，并通过高速网络连接，因此如何建立复杂的网络系统，如何协调服务器的任务，就是网络设计和程序设计的艺术

网络爬虫在工程实现需要考虑的细节

用BFS算法还是DFS算法

页面的分析和URL的提取

，若你发现一些网页明明存在，但搜索引擎就是没有收录，一个可能的原因是网络爬虫中的解析程序没能成功解析网页中不规范的脚本程序。

记录哪些网页已经下载的小本本——URL表

由于每个下载服务器在开始下载前和完成下载后都要访问和维护这张表，以免不同的服务器做重复的工作，这个

存储哈希表的服务器的通信就成了整个爬虫系统的瓶颈。如何消除这个瓶颈是我经常考应聘者的试题。

互联网虽然很复杂，但是说穿了其实就是一张大图而已—可以把每一个网页当作一个节点，把那些超链接（Hyperlinks）当作连接网页的弧。

欧拉七桥

哥尼斯堡七桥的抽象图

路线

把中国的城市当成节点，把连接城市的国道当成弧，那么全国的公路干线网就是图论中所说的图。关于图的算法有很多，但最重要的是图的遍历算法，也就是如何通过弧访问图的各个节点。以中国公路网为例，我们从北京出发，访问所有的城市。可以先看一看北京和哪些城市直接相连，比如与天津、济南、石家庄、沈阳、呼和浩特直接相连（图9.2中的黑色线条）。当然，这些城市之间还可以有其他的连接（图9.2中的灰色线）。

广度优先

者子网站）时，还是需要用BFS的。

总结起来，网络爬虫对网页遍历的次序不是简单的BFS或者DFS，而是有一个相对复杂的下载优先级排序的方法。管理这个优先级排序的子系统一般称为

10：PageRank——Googel的民主表决式网页排名技术

最先为网站排序的是雅虎的杨致远和费罗，采用目录分类方式，缺点在收录网页很少

Googel的创始人拉里·佩奇和谢尔盖·布林找到计算网页自身质量的完美数学模型——PageRank算法

将整个互联网当作一个整体来对待——系统论

若网页被其他网页所链接，说明其受到普遍的承认和信赖，其排名就高

当然算法实际要复杂得多，如对不同网页的链接区别对待

主要依赖于线性代数中的矩阵相乘（要学习研究一下）

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

网页相关性的重要指标：关键词频率=关键词的次数/网页总字数

1．完备的索引。俗话说巧妇难为无米之炊，如果一个网页不在索引中，那么再好的算法也找不到。

2．对网页质量的度量，比如PageRank。当然，正如在前面一章中介绍的那样，现在来看，PageRank的作用比10年前已经小了很多。今天，对网页质量的衡量是全方位的，比如对网页内容权威性的衡量，一些八卦网站的PageRank可能很高，但是它们的内容权威性很低。

3．用户偏好。这一点也很容易理解，因为不同用户的喜好不同，因此一个好的搜索引擎会针对不同用户，对相同的搜索给出不同的排名。

4．确定一个网页和某个查询的相关性的方法。这就是我们这一章要谈论的内容。

还需要对关键词进行权重分析

相关词对预测主题的能力越强，权重越大；反之权重越小

停止词（的、是、和、地、得等）权重为零

“的”这个词占了总词频的80%上，而它对确定网页的主题几乎没什么用处。我们称这种词叫“停止词”（Stop Word），也就是说，在度量相关性时不应考虑它们的频率。在汉语中，停止词还有“是”“和”“中”“地”“得”等几十个。忽略这些停止词后，上述网页和查询的相关性就变成了0.007，其中“原子能”贡献了0.002，“应用”贡献了0.005。

。在汉语中，“应用”是个很通用的词，而“原子能”是个很专业的词，后者在相关性排名中比前者重要。因此，需要对汉语中的每一个词给一个权重，这个权重的设定必须满足下面两个条件。

1．一个词预测主题的能力越强，权重越大，反之，权重越小。在网页中看到“原子能”这个词，或多或少能了解网页的主题。而看到“应用”一词，则对主题基本上还是一无所知。因此，“原子能”的权重就应该比“应用”大。

2．停止词的权重为零。

TF-IDF（词频-逆文本频率指数）是信息检索中最重要的发明，由剑桥大学计算机女科学家斯巴克·琼期发明

用信息论解释IDE即一个特定条件下关键词的概率分布的交叉熵

，在网页中找到一个“原子能”的命中率（Hits）相当于找到九个“应用”的命中率。利用IDF，上述相关性计算的公式就由词频的简单求和变成了加权求和，即

在上面的例子中，该网页和“原子能的应用”的相关性为0.0161，其中“原子能”贡献了0.0126，而“应用”只贡献了0.0035。这个比例和我们的直觉比较一致了。

TF-IDF（Term Frequency／Inverse DocumentFrequency）的概念被公认为信息检索中最重要的发明。在搜索、文献分类和其他相关领域有着广泛的应用。

12：地图和本地搜索的最基本技术——有限状态机和动态规划

智能手机的定位导航功能，其关键技术为：卫星定位、地址识别、最短或最快路线规划

使用有限状态机识别地址，关键要解决两个问题：

通过一些有效的地址建立状态机（是基于概率的有限状态机实现模糊匹配）

给定一个有限状态机后，地址字串的匹配算法

这些地址写得都有点不清楚，但是邮件和包裹我都收到了，说明邮递员可以识别。但是，如果让一个程序员写一个分析器分析这些地址的描述，恐怕就不是一件容易的事了。其根本原因在于，地址的描述虽然看上去简单，但是它依然是比较复杂的上下文有关的文法，而不是上下文无关。

因此有许多识别和分析的方法，但最有效的是有限状态机。

有限状态机是一个特殊的有向图（参见本书第9章中与图论相关的内容），它包括一些状态（节点）和连接这些状态的有向弧。

“北京市双清路83号”对于上面的有限状态来讲有效，而“上海市辽宁省马家庄”则无效（因为无法从“市”走回到“省”）。

使用有限状态机识别地址，关键要解决两个问题，即通过一些有效的地址建立状态机，以及给定一个有限状态机后，地址字串的匹配算法。好在这两个问题都有现成的算法。有了关于地址的有限状态机后，就可以用它分析网页，找出网页中的地址部分，建立本地搜索的数据库。同样，也可以对用户输入的查询进行分析，挑出其中描述地址的部分，当然，剩下的关下一个词组和城市有关，那么就进入“市”的状态，如此等等。如果一条地址能从状态机的开始状态经过状态机的若干中间状态，走到终止状态，则这条地址有效，否则无效。比如，“北京市双清路83号”对于上面的有限状态来讲有效，而“上海市辽宁省马家庄”则无效（因为无法从“市”走回到“省”）。 使用有限状态机识别地址，关键要解决两个问题，即通过一些有效的地址建立状态机，以及给定一个有限状态机后，地址字串的匹配算法。好在这两个问题都有现成的算法。有了关于地址的有限状态机后，就可以用它分析网页，找出网页中的地址部分，建立本地搜索的数据库。同样，也可以对用户输入的查询进行分析，挑出其中描述地址的部分，当然，剩下的关键词就是用户要找的内容。

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

不少科学家能够重写同样功能的工具库，但是很难达到AT&T工具库的效率（即运算速度），这一度是一件令人遗憾的事。但是近年来，随着开源软件在世界上的影响力越来越大，AT&T又重新开放了这个工具的源代码。有限状态机的程序不是很好写，它要求编程者既懂得里面的原理和技术细节，又要有很强的编程能力，因此建议大家直接采用开源的代码就好。

是加权图（Weighted Graph）。比如说中国公路网就是一个很好的“加权图”例子（见图12.2）：每个城市是一个节点，每一条公路是一条弧。图中弧的权重对应于地图上的距离，或者是行车时间、过路费金额，等等。

。采用动态规划可以大大降低最短路径的计算复杂度。在上面的例子中，每加入一条横切线，线上平均有10个城市，从广州到北京最多经过15个城市，那么采用动态规划的计算量是10×10×15，而采用穷举路径的笨办法是1015

，前后差了万亿倍。

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

本地生活服务变得越来越重要，而确认地点、查看地图、查找路线等依然是本地生活服务的基础。

卫星导航的功能早在2000年前后就已有车载设备使用，但是售价昂贵。

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

子主题

它们在语音识别、拼写和语法纠错、拼音输入法、工业控制和生物的序列分析等领域都有着极其重要的应用。其中在拼音输入法中的应用后面还要再介绍。

子主题

，最成功的是前AT&T实验室的三位科学家，莫瑞（Mehryar Mohri）、皮耶尔（Fernando Pereira）和瑞利（Michael Riley）。他们三人花了很多年时间，编写成一个通用的基于概率的有限状态机C语言工具库。由于AT&T有对学术界免费提供各种编程工具的好传统，他们三人也把自己多年的心血拿出来和同行们共享。可惜好景不长，

Σ

是输入符号的集合，

S

是一个非空的有限状态集合，

s

0

是S

中的一个特殊状态，起始状态，

δ

是一个从空间S×Σ

到S

的映射函数，即δ:S×Σ→S

。

f

是S

中另外一个特殊状态，终止状态。

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

简单哲学：在计算机科学领域，一个好的算法应该像AK-47冲锋枪那样“简单、有效、可靠性好而且容易读懂（或者说易操作）”，而非故弄玄虚

，因为它从不卡壳，不易损坏，可在任何环境下使用，可靠性好，杀伤力大并且操作简单（

。我们发现绝大多数作弊的搜索都多少有些商业意图。这也合情合理，因为利益使然。因此，我们需要建一个分类器，准确区分一个搜索是否有商业意图。我以前一直在学术界学习和工作，凡事力求完美的解决方案。设计一个可用的、漂亮的分类器对我来讲不是难事，但是实现和训练却要花上三四个月，当时Google还没有MapReduce这种并行计算工具，复杂的机器学习非常耗时。

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

副总裁韦恩·罗森（Wayne Rosing）打了个赌，如果我们能减少40%的作弊，他就给我们发工程奖，送我们四个家庭（不止是四个员工）去夏威夷度假五天。

”这个分类器设计得非常小巧（占用内存很小），而且运行速度非常快（几台服务器就能处理全球搜索的分类），至今运行得很好，即使在我离开Google后，依然在使用。这项技术，也是Google在反作弊方面取得的第一个美国专利。

在2002年，Google虽然支持对70种语言的检索，但是所有的语言只有一个排名算法

，不可能为了中日韩这三个占总流量不到10%的语言额外增加一批服务器。辛格提出用一个拟合函数替代很耗内存的语言模型，这样不需要增加任何服务器。但是，这样一来搜索质量的提高幅度只有原来采用大模型时的80%。我对此多少有点不甘心。辛格解释说，这样我们至少可以提早两个月将这个新算法提供给中国的用户，而且用户体验也会有质的提高，这是雪中送炭。我们暂时放弃掉的20%收益，对用户而言不过是锦上添花。我接受了他的建议，在2003年初我发布了第一个专门为中日韩语言设计的搜索算法。一年后，Google的服务器数量也有所增加，我在模型压缩上也有了进步，这时便发布了完整的中日韩语言搜索算法。辛格这种做事情的哲学，即先帮助用户解决80%的问题，再慢慢解决剩下的20%问题，是在工业界成功的秘诀之一。许多失败并不是因为人不优秀，而是做事情的方法不对，一开始追求大而全的解决方案，之后长时间不能完成，最后不了了之。

辛格博士坚持寻找简单有效的解决方案：

奉行简单的哲学（要有经验，同时要不怕失败大胆尝试）

简单的方案才容易解释每一个步骤和方法背后的道理，便于问题查错和找到改进的目标

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

2006年夏天，乌迪·曼波加盟Google。曼波是世界上最早研究搜索的学者之一，之前是大学教授、雅虎的首席科学家和首席算法官（Chief Algorithm Officer，这个职务有点无聊）和亚马逊搜索引擎A9的CEO。曼波一来就召集了十几名科学家和工程师，利用机器学习的方法来改进辛格的那些简单模型。经过半年的努力，曼波发现他似乎是在做无用功，一年后彻底放弃了这方面的努力，从此转向人事管理工作。2008年，Google花了很大代价动员了世界著名的语音识别和自然语言处理专家、宾夕法尼亚大学计算机系主任费尔南多·皮耶尔加盟。皮耶尔是辛格在AT&T时的直接上司，著名的有限状态机AT&T FST工具的作者之一。皮耶尔和辛格对做好计算机搜索的认识完全不同。皮耶尔认为最好的计算机搜索算法一定要先理解文本的意思，然后才能准确检索。因此，提高搜索质量的关键是文本的句法分析。辛格认为，计算机不必学习人的做法，就如同飞机不必像鸟一样飞行。在Google，两人的关系已经反了个个儿，辛格成了唱主角的。辛格原本希望皮耶尔能在公司的基础上帮助搜索质量更上一层楼，

。两种技术如何结合成为一个伤脑筋的事情，最后两个人取得妥协，皮耶尔负责对Google下载并索引的全部文本进行句法分析，作为一种资源放到Google的索引中（工作量巨大），然后由每个项目的工程师决定是否采用句法分析提供的信息。后来一些搜索以外的项目，包括我本人负责的自动问答项目，还是用到了皮耶尔的句法分析信息的。但是，对于网页搜索，它的帮助依然不大。

辛格坚持选择简单方案的另一个原因是容易解释每一个步骤和方法背后的道理，这样不仅便于出了问题时查错（Debug），而且容易找到今后改进的目标。今天，整个业界的搜索质量与十多年前佩奇和布林开始研究搜索时相比，已经有了很大的提高，大的改进之处已经不存在了。现在几乎所有的改进都非常细微：通常对一类搜索有改进的方法，会对另外某一类搜索产生稍稍负面的影响。这时候，必须很清楚“所以然”，才能找出这个方法产生负面影响的原因和场景，并且避免它的发生。对于非常复杂的方法，尤其是像黑盒子似的基于机器学习的方法，这一点是做不到的。而如果每一项改进都是有得有失，甚至得失相差无几，那么长期下来搜索的质量不会有什么明显提升。辛格要求对于搜索质量的改进方法都要能说清楚理由，说不清楚理由的改进，即使看上去有效也不会采用，因为这样将来可能是个隐患。这一点和微软、雅虎把搜索质量的提升当作一个黑盒子完全不同。辛格的做法基本上能保证Google搜索的质量长期来讲是稳步提高的。当然，随着Google积累的有关搜索的各种数据量越来越多，采用机器学习的办法调整搜索引擎的各种参数显然要比手工调试更有效。在2011年之后，辛格也越来越提倡靠机器学习和大数据改进搜索质量，

，才能找出这个方法产生负面影响的原因和场景，并且避免它的发生。对于非常复杂的方法，尤其是像黑盒子似的基于机器学习的方法，这一点是做不到的。而如果每一项改进都是有得有失，甚至得失相差无几，那么长期下来搜索的质量不会有什么明显提升。辛格要求对于搜索质量的改进方法都要能说清楚理由，说不清楚理由的改进，即使看上去有效也不会采用，因为这样将来可能是个隐患。这一点和微软、雅虎把搜索质量的提升当作一个黑盒子完全不同。辛格的做法基本上能保证Google搜索的质量长期来讲是稳步提高的。当然，随着Google积累的有关搜索的各种数据量越来越多，采用机器学习的办法调整搜索引擎的各种参数显然要比手工调试更有效。在2011年之后，辛格也越来越提倡靠机器学习和大数据改进搜索质量，不过他一直要求工程师必须能对机器学习出来的参数和公式给予合理的物理解释，否则新的模型和参数不能上线。

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

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

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

计算机读不懂新闻，其本质是快速计算

。计算机本质上只能做快速计算。为了让计算机能够“算”新闻（而不是读新闻），就要求我们先把文字的新闻变成一组可计算的数字，然后再设计一个算法来算出任意两篇新闻的相似性。

。新闻是传递信息的，而词是信息的载体，新闻的信息和词的语义是联系在一起的。套用俄罗斯文豪托尔斯泰在《安娜·卡列尼娜》开篇的那句话来讲，“同一类新闻用词都是相似的，不同类的新闻用词各不相同”。当然，一篇新闻有很多词，有些词表达的语义重要，有些词相对次要。那么如何确定哪些重要，哪些次要呢？首先，直觉告诉我们含义丰富的实词一定比“的、地、得”这些助词，或者“之乎者也”这样的虚词重要，这点是肯定的。接下来，需要进一步对每个实词的重要性进行度量。回忆一下我们在“如何确定网页和查询的相关性”一章中介绍的单文本词汇频率／逆文本频率值TF-IDF的概念，在一篇文章中，重要的词TF-IDF值就高。不难想象，和新闻主题有关的那些实词频率高，TF-IDF值很大。

新闻的特征向量（Feature Vector）。每一篇新闻都可以对应这样一个特征向量，向量中每一个维度的大小代表每个词对这篇新闻主题的贡献。当新闻从文字变成了数字后，计算机就有可能“算一算”新闻之间是否相似了

第一步是将新闻文字变成按词典顺序组织的数字（特征向量）

同一类新闻一定是某些主题词用得较多，另外一些词则用得较少。比如金融类的新闻，这些词出现的频率就很高：股票，利息，债券，基金，银行，物价，上涨。而这些词出现的就较少：二氧化碳，宇宙，诗歌，木匠，诺贝尔，包子。反映在每一篇新闻的特征上，如果两篇新闻属于同一类，它们的特征向量在某几个维度的值都比较大，而在其他维度的值都比较小。反过来看，如果两篇新闻不属于同一类，由于用词的不同，在它们的特征向量中，值较大的维度应该没有什么交集。这样我们就定性地认识到，两篇新闻的主题是否接近，取决于它们的特征向量“长得像不像”。当然，我们还需要定量地衡量两个特征向量之间的相似性。

第二步依据余弘定理计算特征向量的相似性

第三步就是设计新闻分类的算法——IBM华生实验室的科学家弗洛里安发明了一个自底向上不断合并的办法

也可以进一步优化算法：

如分母部分（向量长度）不需要重复计算、只考虑向量中的非零元素、删除虚词、对位置进行加权（文章开头和结尾的词会比中间重要）等

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

新闻分类其实是一个聚类问题，关键是计算新闻间的相似程度，利用矩阵运算中的奇异值分解（SVD）

将大矩阵分解成三个小矩阵相乘，减少存储量和计算量

优势在于无需一次次迭代，适合处理超大规模文本的粗分类

可在使用奇异值分解后再利用计算向量余弦方法得到比较精确结果

真实的文本分类聚合过程

当然，这里面有很多的技术细节，有兴趣和基础的读者可以读他们的论文。

弗洛里安和雅让斯基1998年做这项工作的动机很有意思。当

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

16：信息指纹及其应用

信息指纹在加密、信息压缩和处理中有着广泛的应用

使用伪随机数产生器算法（常用为MD5或者SHA-1等），将网址随机映射到128位二进制

信息指纹的其一特征“不可逆性”，即无法根据信息指纹推出原有信息

信息指纹可应用于反盗版，在计算时无法逐一对比，可选择特征词的集合并计算指纹差异（如为视频反盗版则找到关键帧）

信息指纹可理解为将一段信息（文字、图片、音频、视频等）随机地映射到一个多维二进制空间中的一个点（二进制数字），只要该随机函数做得好，不同信息对应的点不会重合，则该二进制数字就成为了独一无二的指纹

小结

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

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

好的编码方法会使得解密者无法从密码中统计出明码的统计信息

根据信息论，密码的最高境界是对方信息量没有增加，要求：

密码之间分布均匀

统计独立

学过信息论的人都知道，只要多截获一些情报（即使是加密的），统计一下字母的频率，就可以破解出这种密码。柯南·道尔（Sir Arthur Ignatius Conan Doyle）在他的《福尔摩斯探案集》中“跳舞的小人”一案中介绍过这种小技巧（见图17.2）。近年来在一些谍报题材的电视剧中，编剧还在经常使用这种蹩脚的密码，比如用菜价（一组数字）传递信息，这些数字对应康熙字典的页码和字的次序。对于学过信息论的人来说，破译这种密码根本不需要密码本，只要多收集几次情报就可以破译出来。

“恺撒大帝”的玩具

加密和解密是一对函数和反函数

矛和盾

信息论时代的密码学

在第二次世界大战中，很多顶尖的科学家都开始为军方和情报部门工作。

比如维纳和爱因斯坦为美军改进火炮，香农和图灵都在研究加密和解密。香农被分配到的工作是，研究如何为英国首相丘吉尔和美国的通话加密，即便通话遭德国人窃听，对方也无法得知具体内容。而图灵的任务则相反，他在研究如何解密德国人的密码机。那时，香农和图灵经常在贝尔实验室一起喝咖啡，但是出于保密需要，他们从来不谈工作，否则这两个当时

2

信息论时代的密码学

在第二次世界大战中，很多顶尖的科学家都开始为军方和情报部门工作。

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

《暗算》中，黄依依第一次找的结果经过一系列计算发现无法归零，也就是说除不尽。虽然在20世纪60年代还没有公开密钥加密计算，但是编导应该是借鉴了后来密码破译的通用方法，她可能试图对一个大数N

做分解，没成功。第二次计算的结果是归零了，说明她找到了N=P×Q

的分解方法。当然，这件事恐怕是不能用算盘完成的，所以我觉得编导在这一点上有些夸张。另外，该电视剧还有一个讲得不清不楚的地方，就是里面提到的“光复一号”密码的误差问题。一个密码是不能有误差的，否则就是有了密钥也无法解码了。我想编导可能是指在构造密码时有些实现的漏洞，这时密码的保密性就差了很多。在前面引用的“20年对RSA的攻击”一文中作者给出了一些在密码系统中原理严密、实现却有漏洞的例子。再有，该电视剧提到冯·诺依曼，说他是现代密码学的祖宗，这是完全弄错了，应该是香农。冯·诺依曼的贡献在于发明现代电子计算机和提出博弈论（Game Theory），和密码无关。

，保证了二战后的密码几乎无法被破解。冷战时期美苏双方都投入了前所未有的精力去获得对方的情报，但是没有发生过因密码被破解而泄密的重大事件。

18：闪光的不一定是金子——谈谈搜索引擎反作弊问题

通信模型对于搜索反作弊依然适用，基本思路为二：

从信息源出发，加强通信（编码）自身的抗干扰能力——通过余弦定理识别虚假出链提升抗干扰

早期最常见的作弊方法是重复关键词。比如一个卖数码相机的网站，重复罗列各种数码相机的品牌，如尼康、佳能和柯达

从传输来看，过滤掉噪音，还原信息——通过“图论”发现Clique

网页搜索反作弊对于搜索引擎公司来讲是一项长期任务

有了网页排名（PageRank）以后，作弊者发现一个网页被引用的链接越多，排名就可能越靠前，于是就有了专门买卖链接的生意。比如，有人自己创建成百上千个网站，这些网站上没有实质的内容，只有链到其客户网站的链接。这种做法比重复关键词要高明得多，因为他们自己隐藏在背后，而他们那些客户的网页本身内容上没有什么问题，因此不容易被发现。但是，这些伎俩还是能够被识破的。因为那些所谓帮别人提高排名的网站，为了维持生意需要大量地卖链接，所以很容易露马脚。（这就如同制作假钞，当某一种假钞的流通量相当大以后，就容易找到源头。）

作弊者没有想到我们会清除他们。其中一部分网站从此“痛改前非”，但还是有很多网站换一种作弊方法继续作弊。这些是在我们预料之中的，我们也准备了后招等着他们。因此，抓作弊成了一种长期的“猫捉老鼠”的游戏。虽然至今还没有一个一劳永逸解决作弊问题的方法，但是，Google基本做到了对于任何已知的作弊方法，能在一定时间内发现并清除，从而将作弊网站的数量控制在一个很小的比例范围内。

做事情的方法有道和术两种境界，搜索反作弊也是如此。在“术”这个层面的方法大多是看到作弊的例子，分析并清除之，这种方法能解决问题，而且不需要太动脑筋，但是工作量较大，难以从个别现象上升到普遍规律。

作弊的本质是在网页排名信号中加入噪音，反作弊的关键是去噪音，需根本上提高搜索算法抗作弊能力

：如果在发动机很吵的汽车里用手机打电话，对方可能听不清；但是如果知道了汽车发动机的频率，可以加上一个与发动机噪声频率相同、振幅相反的信号，便很容易地消除发动机的噪声，这样，接听人可以完全听不到汽车的噪声。事实上，现在一些高端手机已经有了这种检测和消除噪声的功能。消除噪声的流程可以概括如下。

在图18.2中，原始的信号混入了噪声，在数学上相当于给两个信号做卷积。噪声消除的过程是一个解卷积的过程。这在信号处理中并不是什么难题。首先，汽车发动机的频率是固定的；其次，这个频率的噪声重复出现，只要采集几秒的信号进行处理就能做到。从广义上讲，只要噪声不是完全随机并且前后有相关性，就可以检测到并且消除。（事实上，完全随机不相关的高斯白噪声是很难消除的。）

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

从天文学的发展来看，数学模型重要性的几个结论如下：

正确的数学模型应当在形式上是简单的

一个正确的模型一开始可能还不如一个精雕细琢过的错误模型来得准确，但如果认定大方向是对的就应该坚持 下去

大量准确的数据对研发很重要

正确的模型可能受噪音干扰而显得不准确，此时不应该用凑合的修正方法来弥补，而是找到噪音的根源，也许能通往重大的发现

语言的数学模型

语言的数学本质，任何语言都是一种编码方式，语法规则就是算法；字母，笔画，文字和数字都是信息编码的不同单位

图灵测试：让机器和人交流，如果人无法判断对方是人还是机器时，则认为机器具有智能

基于规则的自然语言和基于统计规则的自然语言处理的研究方法之争

新方法代替传统方法，一个理论要颠覆前面的理论，要等老科学家退休；钱钟书说，老科学家=老的科学家，老科学的家

分词，分词器

隐含马尔科夫模型

什么是好模型

1.要形式上简单

2.一开始可能不如旧的准确

3.需要大量准确的数据支持

4.找到影响模型准确性的根源

语音识别：就是听话的人去猜测说话人要表达的意思，所有的自然语言处理问题都可以等价成通信解码问题

利用计算机，根据接收到的英语信息，推测说话者的汉语意思就是机器翻译

根据带有拼音错误的语句推测说话者要表达的正确意思，就是自动纠错

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

最大熵模型的原理是保留全部的不确定性，将风险降到最小

最大熵模型在形式上是最漂亮、最完美的统计模型，在自然语言处理和金融方面有很多应用

如文艺复兴技术公司利用数学模型实现的稳定高额净回报率

最大熵模型在实现上非常复杂，计算量非常大

最原始的模型训练方法是通用迭代算法GIS，但因其不太稳定，很少实际应用

后期达拉皮垂孪生兄弟提出的改进迭代算法IIS才有可能变得实用

今天世界上能有效实现这些算法的也不到100人

香农《通信的数学原理》中提出信息熵，解决信息度量的问题

信息的作用就是消除不确定性，信息量等于不确定性的多少，单位是bit

信息作用的一个好案例

熵的定义

互信息

相对熵，交叉熵

最大熵：需要对一个随机事件的概论分布预测时，预测应该满足所有已知条件，而对未知情况不做任何主管假设

21:拼音输入法的数学原理

输入法输入汉字的快慢取决于汉字编码的平均长度，即击键次数X寻找该键所需时间，而输入法效率提升在于同时优化这两方面因素而非其一

这已经不是技术的比赛，而是市场的竞争。最后，王永民的五笔输入法暂时胜出，但并不是他的编码方法更合理，而是他比其他发明者（大多数是书呆子）更会做市场而已。现在，即使五笔输入法也已经没有多少市场了，这一批发明人可以说是全军覆没。

这一代输入法的问题在于减少了每个汉字击键的次数，而

忽视了找到每个键的时间。要求普通用户背下这些输入方法里所有汉字的编码是不现实的，这比背6 000个GRE单词还难。因此，他们在使用这些输入方法时都要按照规则即时“拆字”，即找到一个字的编码组合，这个时间不仅长，而且在脱稿打字时会严重中断思维。本书一开头就强调把语言和文字作为通信的编码手段，一个重要目的是帮助思维和记忆。如果一个输入法中断了人们的思维过程，就和人的自然行为不相符合。认知科学已经证明，人一心无二用。

对汉字的编码分为两部分：对拼音的编码（参照汉语拼音标准即可）和消除歧义性的编码

早期双拼输入法只优化局部，而伤害了整体，增加了编码上的歧义性（增加击键时间）并让思维在拆字过程中变慢，且容错性不好

全接输入法的优势在于不需要专门学习，且与符合思维自然过程，且容错性好，只剩下要排除一音多字的歧义性

输入法的进一步优化方向：

以香农第一定理（信息编码长度都不小于它的信息熵）确定每个汉字的击键效率为2.1次键（以词输入为1.7次键）

利用上下文建立大词库（提升关键是准确而有效地建立语言模型）

拼音转汉字的算法和导航中寻找最短路径的算法相同，都是动态规划（数学的妙处在于其工具都具有相当的普遍性，在不同应用中发挥作用）

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

米奇·马库斯更早发现建立标准语料库在自然语言处理研究中的重要性

马库斯通过在宾夕法尼亚大学建立LDC语料库，为全世界自然语言处理科学家共享

马库斯的优秀弟子：

柯林斯追求完美制作文法分析器，是“务于精纯”的精深专才

布莱尔善于寻找简单却有效的方法，是“观其大略”的通才

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

心血管疾病和成因的一个简单的贝叶斯网络

文本分析

“徐志摩—喜欢”“动词—名词”等，不同层次节点的组合其实是一些子树，比如“名词短语”重写（Rewrite）成“名词”，“动词短语”重写成“动词，名词短语”等。在考虑一些特征后，可以用下面的公式计算这个条件随机场的概率：

P

(徐志摩/名词，喜欢/动词，林徽因/名词，名词短语，动词短语/)

=exp{f

1

(徐志摩，名词)

+f

2

(喜欢，动词)+f

3

(林徽因，动词)

+f

4

(徐志摩，名词，名词短语)+f

(名词，名词短语)

+f

5

(喜欢，动词，林徽因，名词，动词短语)

+f

6

(名词短语，动词短语)+f

7

(名词短语)

+f

8

(动词短语)+f

(动词，名词，动词短语)｝

23：布隆过滤器

布隆过滤器只城要哈希表1/8到1/4的大小就能解决同样的问题，其实质上是一个很长的二进制向量和一系列随机映射函数，其好处在于快速、省空间，但有一定的误识别率。补救方法是再建立一个小的白名单，存储那些可能被误判的邮件地址

子主题

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

贝叶斯网络：每一个状态只和它直接相连的状态有关，而和它间接相连的状态没有直接关系

其拓扑结构比马尔可夫链灵活，不受马尔可夫链的链状结构的约束，可更准确地描述事件之间的相关性

先确定网络的拓扑结构（结构训练），还要知道各个状态之间的概率（参数训练）

在文本分类、概念抽取、生物统计、图像处理、决策支持系统和博弈论中有广泛应用

25：条件随机场和句法分析

布朗大学计算机系的计算语言学家尤金·查尼阿克统计出文法规则的概率，在选择文法规则时，坚持一个原则——让被分析的句子的语法树概念达到最大，无形中在数学和句法分析中搭建了一个桥梁。其学生拉纳帕提用最大熵模型实现了语法成分的统计，还用一个统计模型来预测句子成分的种类。

条件随机场：是隐含马尔可夫模型的一种扩展，是一种特殊的概率图模型，是用于预测的统计模型，在模式识别、机器学习和生物统计中都有很成功的应用（形式简单，但实现复杂）

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

维特比算法：是一个特殊但应用最广的动态规划算法，针对篱笆网络的有向图的最短路径问题而提出，包括数字通信、语音识别、机器翻译、拼音转汉字、分词等都可用其来解码

3G手机和移动互联网最关键的通信技术是码分多址（CDMA）技术，由业余发明家（本职为演员）海蒂·拉玛尔和维特比发明并普及贡献

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

频分多址：对频率进行切分，每一路通信使用一个不同的频率（如对讲机）

2007年，维特比作为数学家和计算机科学家，被授予美国科技界最高成就奖——国家科学奖

27：再谈文本自动分类问题——期望最大化算法

期望最大化算法：通过几次迭代收敛完成聚类，不需要任何人工干预和先验经验

28：逻辑回归和搜索广告

搜索广告的三个阶段：

第一阶段：广告主出价高低竞价排名

第二阶段：结合出价和点击率预测（CTR）来决定广告投放

第三阶段：全局优化

点击率预估的最好办法，就是根据以前经验值来预测——使用逻辑回归模型（将一个事件出现的概率适应到一条逻辑曲线）

两个技巧：

一是如何选取与广告点击相关的信息，这些是专门从事搜索广告的工程师和数据挖掘专家的工作；

二是如何决定这些参数，训练最大熵模型的IIS方法可以直接 训练逻辑回归函数的参数

扩展

26 云计算

云计算的起源

起源：上世纪９０年代，甲骨文公司的拉里·埃里森提出网络电脑的概念，利用釜底抽薪的方式企图撼动微软在客户端的地位，从而突破诺维格定律的限制。

结果：第一次互联网泡沫破灭。云计算由02年以后的谷歌、亚马逊、IBM主导

作者认为埃里森是IT行业仅次于盖茨的猛将。 当时甲骨文公司是世界第二的软件公司。微软掌握客户端，甲骨文掌握数据库。迫于诺维格定律，二者都在想办法侵入对方的领域。微软推出了SQL Server数据库系统，占据了一部分中小企业市场，但是甲骨文却没办法侵入微软的领域。

最初形式：埃里森提出一种只有简单计算功能（速度较慢，内存小，无硬盘），主要用于上网的网络电脑，售价500美元（现在的chromebook很类似，售价300美元）

失败原因：

第一，网络电脑实际上就是低端PC（cpu慢，内存小，无硬盘）。产品体验太差，能做的事太少

第二，普通pc的降价速度很快（摩尔定律作用），买得起pc的人迅速增多，削弱了网络电脑的价格优势

第三，当时用户上网费用过高，费用达到两年上网费就够一台ｐｃ了。很多人甚至买了ｐｃ但却只单机操作

第四，最重要的是，当时许多ＰＣ软件并没有网页版，网上服务较少

云计算的本质

早期三家大企业的理解各有不同：IBM侧重卖云计算服务器，亚马逊卖计算能力，谷歌卖服务

本质：

云计算保证用户可以随时随地访问和处理信息，非常方便与他人共享信息

云计算保证用户可以使用云端的大量计算资源，包括CPU处理器和存储器（内存和磁盘），而无需自己购买配置

云计算的核心技术

海量数据存储和结构化数据的存储

ＧＦＳ（Ｇｏｏｇｌｅ ｆｉｌｅ ｓｙｓｔｅｍ分布式海量存储的操作系统）

云计算资源管理

MapReduce：它将一个巨型任务分解为无数小任务，分配到不同服务器中完成，然后把每一台服务器上完成的小人物合并起来，最终完成大任务

Borg：它将整个云端的服务器资源作为整体管理，根据用户的需求动态分配这些资源

信息安全

作者认为，其实云计算模式的安全性能要比wintel模式更好，因为可以规模管理，就像是银行对于资产的保护比个人要好

需要完善配套的政策和法规

其他因素

大型数据中心的建设和全球高速光纤主干网的铺设

全球基础架构所需的其他的工程性技术（比如看似毫不相干的制冷技术）

足够多的互联网入口

最早由谷歌的两位创始人佩奇和布林在斯坦福大学攻读博士时提出。

ＢｉｇＴａｂｌｅ（大型结构化数据的系统）

新的IT产业链

操作系统重要性下降

对cpu依赖性下降

硬件厂商的产品线发生变化，更多向智能手机和数据中心转移

外设市场发生变化，如传统硬盘向固态硬盘转变

新的产业生态链形成，提供云计算服务的平台成为产业枢纽，如亚马逊的AWS，正扮演者当年微软的角色

软件就是服务

在美国、欧盟、日本等地区，企业级IT市场比个人用户市场大的多。而在中国却相反，大公司集中在针对个人用户的公司。

为什么美国的企业及软件市场规模会如此之大呢？

在美国企业，想要在同行竞争中占据更大的优势更有利的地位就不得不提高效率。而在ＩＴ领域的投入是提高效率的捷径。其实改善管理也能做到，但是不是谁都能改善的了得。

相比之下，中国的企业之间的竞争主要通过降低价格。这也导致需要收费的软件大多在中国活动的不太好。到了云计算时代，中国有可能会改善这种情况，因为云计算时代盗版软件变得非常困难，中国劳动力红利也不多了

为什么企业级市场总是那么几家公司在把持呢？

数据的忠诚度。当一个公司把大量的数据交由某一家公司处理的时候，再想要转变所付出的成本将会非常高，同时，很容易出现数据丢失等问题

销售成本。很多企业级ＩＴ公司在谈成一家客户后可以常年做生意，但是拉拢客户的过程却相对漫长，同时人工成本也很高。这导致很多初创公司很难坚持下去。

其他因素

为什么说云计算给了新公司，打破企业级市场格局的机会呢？

云计算使得服务成本大幅下降。

让许多传统软件公司不能做的事变的能做了。比如依赖大规模数据或者大量计算能力的公司，如圣杯公司，人类长寿公司（大数据医疗公司），人脸识别技术等等

为什么亚马逊能够保证自己服务的价格相当低廉？

规模经济的效应。

可以利用计算机的碎片化时间，更大程度的利用资源

中国市场的机会

中国早期的云计算泡沫有哪些特征

云计算定义不清，炒作概念。

大浪淘沙过后，总会有金子留下来。比如阿里云、腾讯云。云计算也解决了过去软件盗版的问题

仔细想想，这真的就是如此，随便找点什么和互联网相关的东西，加上个云字就是一个新的概念

云计算成了圈地搞基建的借口

小结

云计算的发展是对IT行业的一次大洗牌，动摇了wintel体系的根基，是新一轮的资源优化。中国过去很少有人愿意花钱买软件，但是新的云计算模式“软件即服务”却得到了认可，因此，中国有望诞生一个万亿级别的企业级软件和服务市场。当今，云计算的立法和执法方面的改善刻不容缓，信息安全问题亟待解决。

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

云计算的关键问题：如何将一个非常大的计算问题，自动分解到许鑫计算能力不是很强大的计算机止，共同完成（Google提出MapReduce程序），基本原理就是分治算法

分治算法原理：将一个复杂问题，分成若干个简单的子问题进行解决； 然后，对子问题的结果进行合并，得到原有问题的解

MapReduce：将一个大任务拆分成小的子任务，并且完成子任务的计算（Map），将中间结果合并成最终结果（Reduce)

如何将一个大矩阵自动拆分，保证各个服务器负载均衡，如何合并返回值

真正有用的方法往往简单而又朴实

浮动主题