数学之美 系列一 ‐‐ 统计语言模型 .............................................................................................. 2
数学之美 系列二 ‐‐ 谈谈中文分词 .............................................................................................. 3
数学之美 系列三 ‐‐ 隐含马尔可夫模型在语言处理中的应用 ................................................... 5
数学之美 系列四 ‐‐ 怎样度量信息? ............................................................................................ 7
数学之美 系列五 ‐‐ 简单之美：布尔代数和搜索引擎的索引 ................................................... 9
数学之美 系列六 ‐‐ 图论和网络爬虫 (Web Crawlers) ............................................................. 11
数学之美 系列七 ‐‐ 信息论在信息处理中的应用 .................................................................... 13
数学之美 系列八‐‐ 贾里尼克的故事和现代语言处理 .............................................................. 15
数学之美 系列九 ‐‐ 如何确定网页和查询的相关性 ................................................................ 17
数学之美 系列十 有限状态机和地址识别 ................................................................................. 19
数学之美 系列十一 ‐ Google 阿卡 47 的制造者阿米特.辛格博士 ........................................ 20
数学之美 系列十二 ‐ 余弦定理和新闻的分类 .......................................................................... 21
数学之美 系列十三 信息指纹及其应用 ..................................................................................... 24
数学之美 系列十四 谈谈数学模型的重要性 ............................................................................. 25
数学之美 系列十五 繁与简 自然语言处理的几位精英 ........................................................... 27
数学之美 系列十六（上） 不要把所有的鸡蛋放在一个篮子里 ‐‐ 谈谈最大熵模型 ........... 29
数学之美 系列十六 （下）－ 不要把所有的鸡蛋放在一个篮子里 最大熵模型 ............... 31
数学之美 系列十七 闪光的不一定是金子 谈谈搜索引擎作弊问题(Search Engine Anti‐SPAM)
........................................................................................................................................................ 32
数学之美 系列十八 － 矩阵运算和文本处理中的分类问题 ................................................... 35
数学之美 系列十九 － 马尔可夫链的扩展 贝叶斯网络 (Bayesian Networks) ...................... 37
数学之美 系列二十 －自然语
言处理的教父 马库斯 ............................................................... 38
数学之美 系列二十一 － 布隆过滤器（Bloom Filter） ........................................................... 39
数学之美 系列二十二 由电视剧《暗算》所想到的 - 谈谈密码学的数学原理 .................. 41
数学之美 系列二十三 输入一个汉字需要敲多少个键 - 谈谈香农第一定律 ...................... 44
数学之美 系列一 ‐‐ 统计语言模型
2006 年 4 月 3 日 上午 08:15:00
从本周开始，我们将定期刊登 Google 科学家吴军写的《数学之美》系列文章，介绍数学在信
息检索和自然语言处理中的主导作用和奇妙应用。
发表者: 吴军, Google 研究员
前言
也许大家不相信，数学是解决信息检索和自然语言处理的最好工具。它能非常清晰地描述这些领
域的实际问题并且给出漂亮的解决办法。每当人们应用数学工具解决一个语言问题时，总会感叹
数学之美。我们希望利用 Google 中文黑板报这块园地，介绍一些数学工具，以及我们是如何
利用这些工具来开发 Google 产品的。
系列一： 统计语言模型 (Statistical Language Models)
Google 的使命是整合全球的信息，所以我们一直致力于研究如何让机器对信息、语言做最好的
理解和处理。长期以来，人类一直梦想着能让机器代替人来翻译语言、识别语音、认识文字（不
论是印刷体或手写体）和进行海量文献的自动检索，这就需要让机器理解语言。但是人类的语言
可以说是信息里最复杂最动态的一部分。为了解决这个问题，人们容易想到的办法就是让机器模
拟人类进行学习 - 学习人类的语法、分析语句等等。尤其是在乔姆斯基（Noam Chomsky 有
史以来最伟大的语言学家）提出 。统计语言模型就是在那个时候提出的。
给大家举个例子：在很多涉及到自然语言处理的领域，如机器翻译、语音识别、印刷体或手写体
识别、拼写纠错、汉字输入和文献查询中，我们都需要知道一个文字序列是否能构成一个大家能
理解的句子，显示给使用者。对这个问题，我们可以用一个简单的统计模型来解决这个问题。
如果 S 表示一连串特定顺序排列的词 w1， w2，?， wn ，换句话说，S 可以表示某一个
由一连串特定顺序排练的词而组成的一个有意义的句子。现在，机器对语言的识别从某种角度来
说，就是想知道 S 在文本中出现的可能性，也就是数学上所说的 S 的概率用 P(S) 来表示。利
用条件概率的公式，S 这个序列出现的概率等于每一个词出现的概率相乘，于是 P(S) 可展开
为：
P(S) = P(w1)P(w2|w1)P(w3| w1 w2)?P(wn|w1 w2?wn-1)
其中 P (w1) 表示第一个词 w1 出现的概率；P (w2|w1) 是在已知第一个词的前提下，第二
个词出现的概率；以次类推。不难看出，到了词 wn，它的出现概率取决于它前面所有词。从计
算上来看，各种可能性太多，无法实现。因此我们假定任意一个词 wi 的出现概率只同它前面的
词 wi-1 有关(即马尔可夫假设），于是问题就变得很简单了。现在，S 出现的概率就变为：
P(S) = P(w1)P(w2|w1)P(w3|w2)?P(wi|wi-1)?
(当然，也可以假设一个词又前面 N-1 个词决定，模型稍微复杂些。）
接下来的问题就是如何估计 P (wi|wi-1)。现在有了大量机读文本后，这个问题变得很简单，
只要数一数这对词（wi-1,wi) 在统计的文本中出现了多少次，以及 wi-1 本身在同样的文本中
前后相邻出现了多少次，然后用两个数一除就可以了,P(wi|wi-1) = P(wi-1,wi)/ P (wi-1)。
也许很多人不相信用这么简单的数学模型能解决复杂的语音识别、机器翻译等问题。其实不光是
常人，就连很多语言学家都曾质疑过这种方法的有效性，但事实证明，统计语言模型比任何已知
的借助某种规则的解决方法都有效。比如在 Google 的中英文自动翻译中，用的最重要的就是
这个统计语言模型。去年美国标准局(NIST) 对所有的机器翻译系统进行了评测，Google 的系
统是不仅是全世界最好的，而且高出所有基于规则的系统很多。
现在，读者也许已经能感受到数学的美妙之处了，它把一些复杂的问题变得如此的简单。当然，
真正实现一个好的统计语言模型还有许多细节问题需要解决。贾里尼克和他的同事的贡献在于提
出了统计语言模型，而且很漂亮地解决了所有的细节问题。十几年后，李开复用统计语言模型把
997 词语音识别的问题简化
成了一个 20 词的识别问题，实现了有史以来第一次大词汇量非特
定人连续语音的识别。
我是一名科学研究人员 ，我在工作中经常惊叹于数学语言应用于解决实际问题上时的神奇。我
也希望把这种神奇讲解给大家听。当然，归根结底，不管什莫样的科学方法、无论多莫奇妙的解
决手段都是为人服务的。我希望 Google 多努力一分，用户就多一分搜索的喜悦。
数学之美 系列二 ‐‐ 谈谈中文分词
2006 年 4 月 10 日 上午 08:10:00
发表者: 吴军， Google 研究员
谈谈中文分词
----- 统计语言模型在中文处理中的一个应用
上回我们谈到利用统计语言模型进行语言处理，由于模型是建立在词的基础上的，对于中日韩等
语言，首先需要进行分词。例如把句子 ，那么 （P 表示概
率）：
P (A1, A2, A3, ..., Ak） 〉 P (B1, B2, B3, ..., Bm), 并且
P (A1, A2, A3, ..., Ak） 〉 P(C1, C2, C3, ..., Cn)
因此，只要我们利用上回提到的统计语言模型计算出每种分词后句子出现的概率，并找出其中概
率最大的，我们就能够找到最好的分词方法。
当然，这里面有一个实现的技巧。如果我们穷举所有可能的分词方法并计算出每种可能性下句子
的概率，那么计算量是相当大的。因此，我们可以把它看成是一个动态规划（Dynamic
Programming) 的问题，并利用 &id=980775
数学之美 系列三 ‐‐ 隐含马尔可夫模型在
语言处理中的应用
2006 年 4 月 17 日 上午 08:01:00
发表者：吴军，Google 研究员
前言：隐含马尔可夫模型是一个数学模型，到目前为之，它一直被认为是实现快速精确的语音识
别系统的最成功的方法。复杂的语音识别问题通过隐含马尔可夫模型能非常简单地被表述、解决，
让我不由由衷地感叹数学模型之妙。
自然语言是人类交流信息的工具。很多自然语言处理问题都可以等同于通信系统中的解码问题
-- 一个人根据接收到的信息，去猜测发话人要表达的意思。这其实就象通信中，我们根据接收
端收到的信号去分析、理解、还原发送端传送过来的信息。以下该图就表示了一个典型的通信系
统：
其中 s1，s2，s3...表示信息源发出的信号。o1, o2, o3 ... 是接受器接收到的信号。通信中
的解码就是根据接收到的信号 o1, o2, o3 ...还原出发送的信号 s1，s2，s3...。
其实我们平时在说话时，脑子就是一个信息源。我们的喉咙（声带），空气，就是如电线和光缆
般的信道。听众耳朵的就是接收端，而听到的声音就是传送过来的信号。根据声学信号来推测说
话者的意思，就是语音识别。这样说来，如果接收端是一台计算机而不是人的话，那么计算机要
做的就是语音的自动识别。同样，在计算机中，如果我们要根据接收到的英语信息，推测说话者
的汉语意思，就是机器翻译； 如果我们要根据带有拼写错误的语句推测说话者想表达的正确意
思，那就是自动纠错。
那么怎么根据接收到的信息来推测说话者想表达的意思呢？我们可以利用叫做许会问，你现在是不是把问题变得更复杂了，因为公式越写越长了。别着急，
我们现在就来简化这个问题。）我们在这里做两个假设：
第一，s1,s2,s3,... 是一个马尔可夫链，也就是说，si 只由 si-1 决定 (详见系列一)；
第二， 第 i 时刻的接收信号 oi 只由发送信号 si 决定（又称为独立输出假设, 即
P(o1,o2,o3,...|s1,s2,s3....) = P(o1|s1) * P(o2|s2)*P(o3|s3)...。
那么我们就可以很容易利用算法 Viterbi 找出上面式子的最大值，进而找出要识别的句子
s1,s2,s3,...。
满足上述两个假设的模型就叫隐含马尔可夫模型。我们之所以用gle 一直以 信息量比五比特少。香农指出，它的
准确信息量应该是
= -（p1*log p1 + p2 * log p2 + ．．． ＋p32 *log p32)，
其中，p1，p2 ， ．．．，p32 分别是这 32 个球队夺冠的概率。香农把它称为页自动下载。］
世界上不可能有比二进制更简单的计数方法了，也不可能有比布尔运算更简单的运算了。尽管今
天每个搜索引擎都宣称自己如何聪明、多么智能化，其实从根本上讲都没有逃出布尔运算的框框。
布尔（George Boole) 是十九世纪英国一位小学数学老师。他生前没有人认为他是数学家。布
尔在工作之余，喜欢阅读数学论著、思考数学问题。1854 年询语句器中。每当接受一个查询
时，这个查询就被分送到许许多多服务器中，这些服务器同时并行处理用户请求，并把结果送到
主服务器进行合并处理，最后将结果返回给用户。
不管索引如何复杂，查找的基本操作仍然是布尔运算。布尔运算把逻辑和数学联系起来了。它的
最大好处是容易实现，速度快，这对于海量的信息查找是至关重要的。它的不足是只能给出是与
否的判断，而不能给出量化的度量。因此，所有搜索引擎在内部检索完毕后，都要对符合要求的
网页根据相关性排序，然后才返回给用户。
数 学 之 美 系 列 六 ‐‐ 图 论 和 网 络 爬 虫
(Web Crawlers)
2006 年 5 月 15 日 上午 07:15:00
发表者: 吴军，Google 研究员
[离散数学是当代数学的一个重要分支，也是计算机科学的数学基础。它包括数理逻辑、集合论、
图论和近世代数四个分支。数理逻辑基于布尔运算，我们已经介绍过了。这里我们介绍图论和互
联网自动下载工具网络爬虫 (Web Crawlers) 之间的关系。顺便提一句，我们用 Google
Trends 来搜索一下可能广地访问每个节点所直接连接的其他节点。另外还
有一种策略是从北京出发，随便找到下一个要访问的城市，比如是济南，然后从济南出发到下一
个城市，比如说南京，再访问从南京出发的城市，一直走到头。然后再往回找，看看中间是否有
尚未访问的城市。这种方法叫务，就是网络设计和程序设计的艺术了。
数学之美 系列七 ‐‐ 信息论在信息处理中
的应用
2006 年 5 月 25 日 上午 07:56:00
发表者：吴军, Google 研究员
我们已经介绍了信息熵，它是信息论的基础，我们这次谈谈信息论在自然语言处理中的应用。
先看看信息熵和语言模型的关系。我们在系列一中谈到语言模型时，没有讲如何定量地衡量一个
语言模型的好坏，当然，读者会很自然地想到，既然语言模型能减少语音识别和机器翻译的错误，
那么就拿一个语音识别系统或者机器翻译软件来试试，好的语言模型必然导致错误率较低。这种
想法是对的，而且今天的语音识别和机器翻译也是这么做的。但这种测试方法对于研发语言模型
的人来讲，既不直接、又不方便，而且很难从错误率反过来定量度量语言模型。事实上，在贾里
尼克(Fred Jelinek)的人研究语言模型时，世界上既没有像样的语音识别系统，更没有机器翻译。
我们知道，语言模型是为了用上下文预测当前的文字，模型越好，预测得越准，那么当前文字的
不确定性就越小。
信息熵正是对不确定性的衡量，因此信息熵可以直接用于衡量统计语言模型的好坏。贾里尼克从
信息熵出发，定义了一个称为语言模型复杂度(Perplexity)的概念，直接衡量语言模型的好坏。
一个模型的复杂度越小，模型越好。李开复博士在介绍他发明的 Sphinx 语音识别系统时谈到，
如果不用任何语言模型（即零元语言模型）时，复杂度为 997，也就是说句子中每个位置有 997
个可能的单词可以填入。如果（二元）语言模型只考虑前后词的搭配不考虑搭配的概率时，复杂
度为 60。虽然它比不用语言模型好很多，但是和考虑了搭配概率的二元语言模型相比要差很多，
因为后者的复杂度只有 20。
信息论中仅次于熵的另外两个重要的概念是这个词呢？人们很容易想到要用语法、要分析语句等等。其实，至今为止，没有一种
语法能很好解决这个问题，真正实用的方法是使用互信息。具体的解决办法大致如下：首先从大
量文本中找出和总统布什一起出现的互信息最大的一些词，比如总统、美国、国会、华盛顿等等，
当然，再用同样的方法找出和灌木丛一起出现的互信息最大的词，比如土壤、植物、野生等等。
有了这两组词，在翻译 Bush 时，看看上下文中哪类相关的词多就可以了。这种方法最初是由
吉尔(Gale)，丘奇(Church)和雅让斯基(Yarowsky)提出的。
当时雅让斯基在宾西法尼亚大学是自然语言处理大师马库斯 (Mitch Marcus) 教授的博士生，
他很多时间泡在贝尔实验室丘奇等人的研究室里。也许是急于毕业，他在吉尔等人的帮助下想出
了一个最快也是最好地解决翻译中的二义性，就是上述的方法，这个看上去简单的方法效果好得
让同行们大吃一惊。雅让斯基因而只花了三年就从马库斯那里拿到了博士，而他的师兄弟们平均
要花六年时间。
信息论中另外一个重要的概念是经历的，要么是他亲口对我讲的。
弗莱德里克.贾里尼克(Fred Jelinek)出生于捷克一个富有的犹太家庭。他的父母原本打算送他
去英国的公学（私立学校）读书。为了教他德语，还专门请的一位德国的家庭女教师，但是第二
次世界大战完全打碎了他们的梦想。他们先是被从家中赶了出去，流浪到布拉格。他的父亲死在
了集中营，弗莱德自己成天在街上玩耍，完全荒废了学业。二战后，当他再度回到学校时，他的
成绩一塌糊涂， 全部是 D，但是很快他就赶上了班上的同学。不过，他在小学时从来没有得过
A。1949 年，他的母亲带领全家移民美国。在美国，贾里尼克一家生活非常贫困，全家基本是
靠母亲做点心卖钱为生，弗莱德自己十四五岁就进工厂打工补助全家。
贾里尼克最初想成为一个律师，为他父亲那样的冤屈者辩护，但他很快意识到他那浓厚的外国口
音将使他在法庭上的辩护很吃力。贾里尼克的第二个理想是成为医生，他想进哈佛大学医学院，
但经济上他无法承担医学院 8 年高昂的学费。与此同时麻省理工学院给于了他一份（为东欧移
民设的）全额奖学金。贾里尼克决定到麻省理工学电机工程。在那里，他遇到了信息论的鼻祖香
农博士，和语言学大师贾格布森 Roman Jakobson (他提出了著名的通信六功能）[注释一]，
后来贾里尼克又陪着太太听最伟大的语言学家乔姆斯基(Noam Chomsky)的课。这三位大师对
贾里尼克今后的研究方向--利用信息论解决语言问题产生的重要影响。
贾里尼克从麻省理工获得博士学位后，在哈佛大学教了一年书，然后到康乃尔大学任教。他之所
以选择康乃尔大学，是因为找工作时和那里的一位语言学家谈得颇为投机。当时那位教授表示愿
意和贾里尼克在利用信息论解决语言问题上合作。但是，等贾里尼克到康乃尔以后，那位教授表
示对语言学在没有兴趣而转向写歌剧了。贾里尼克对语言学家的坏印象从此开始。加上后来他在
IBM 时发现语言学家们嘴上头头是道，干起活来高不成低不就，对语言学家从此深恶痛绝。他
甚至说：建了阵容空前绝后强大的研究队伍，其中包括他的著名搭档波尔（Bahl），著名的语
音识别 Dragon 公司的创始人贝克夫妇，解决最大熵迭代算法的达拉皮垂(Della Pietra)孪生
兄弟，BCJR 算法的另外两个共同提出者库克(Cocke)和拉维夫(Raviv)，以及第一个提出机器
翻译统计模型的布朗。
七十年代的 IBM 有点像九十年代的微软和今天的 Google, 给于杰出科学家作任何有兴趣研
究的自由。在那种宽松的环境里，贾里尼克等人提出了统计语音识别的框架结构。 在贾里尼克
以前，科学家们把语音识别问题当作人工智能问题和模式匹配问题。而贾里尼克把它当成通信问
题，并用两个隐含马尔可夫模型（声学模型和语言模型）把语音识别概括得清清楚楚。这个框架
结构对至今的语音和语言处理有着深远的影响，它从根本上使得语音识别有实用的可能。 贾里
尼克本人后来也因此当选美国工程院院士。
贾里尼克和波尔，库克以及拉维夫对人类的另一大贡献是 BCJR 算法，这是今天数字通信中应
用的最广的两个算法之一（另一个是维特比算法）。有趣的是，这个算法发明了二十年后，才得
以广泛应用。IBM 于是把它列为了 IBM 有史以来对人类最大贡献之一，并贴在加州 Amaden
实现室墙上。遗憾的是 BCJR 四个人已经全部离开 IBM，有一次 IBM 的通信部门需要用这个
算法，还得从斯坦福大学请一位专家去讲解，这位专家看到 IBM 橱窗里的成就榜，感慨万分。
贾里尼克和 IBM 一批最杰出的科学家在九十年代初离开了 IBM，他们大多数在华尔街取得了
巨大的成功。贾里尼克的书生气很浓，于是去约翰霍普金斯大学建立了世界著名的 CLSP 实验
室。每年夏天，贾里尼克邀请世界上 20-30 名顶级的科学家和学生到 CLSP 一起工作，使得
CLSP 成为世界上语音和语言处理的中心之一。
贾里尼克治学极为严谨，对学生要求也极严。他淘汰学生的比例极高，即使留下来的，毕业时间
也极长。但是，另一方面，贾里尼克也千方百计利用自己的影响力为学生的学习和事业创造方便。
贾里尼克为组里的每一位学生提供从进组第一天到离开组最后一天全部的学费和生活费。他还为
每一位学生联系实习机会，并保证每位学生在博士生阶段至少在大公司实习一次。从他那里拿到
博士学位的学生，全部任职于著名实验室，比如 IBM, 微软，AT&T 和 Google 的实验室。为
了提高外国人的英语水平，贾里尼克用自己的经费为他们请私人英语教师。
贾里尼克生活俭朴，一辆老式丰田车开了二十多年，比组里学生的车都破。他每年都邀请组里的
学生
和教授到家里做客，很多毕业了的学生也专程赶来聚会。在那里，他不再谈论学术问题，而
会谈些巩俐的电影（他太太是哥伦比亚大学电影专业的教授），或是某著名教授被拉斯韦加斯的
赌馆定为不受欢迎的人等等。但是他聚会的食物实在难吃，无非是些生胡萝卜和芹菜。后来贾里
尼克掏钱让系里另一个教授承办聚会，那个教授每次请专业大厨在家作出极丰盛的晚宴，并准备
许多美酒，从此这种聚会就转移到那个教授家了。
除了巩俐的电影，贾里尼克对中国的了解就是清华大学和青岛啤酒了。他有时会把两个名字搞混，
有两次被香港科技大学的 Pascale 冯教授抓住。
贾里尼克说话心直口快，不留余地。在他面前谈论学术一定要十分严谨，否则很容易被他抓住辫
子。除了刚才提到的对语言学家略有偏见的评论，他对许多世界级的大师都有过很多ncy)，比如，在某个
一共有一千词的网页中单求和变成了加权求和，即 TF1*IDF1 +
TF2*IDF2 ＋... + TFN*IDFN。在上面的例子中，该网页和些状态（节点）和连接
这些状态的有向弧。下图是一个识别中国地址的有限状态机的简单的例子。
每一个有限状态机都有一个启始状态和一个终止状态和若干中间状态。每一条弧上带有从一个状
态进入下一个状态的条件。比如，在上图中，当前的状态是编程工具的
好传统，他们三人也把自己多年的心血拿出来和同行们共享。可惜好景不长，AT&T 实验室风
光不再，这三个人都离开了 AT&T，莫瑞成了纽约大学的教授，皮瑞尔当了宾西法尼亚大学计
算机系系主任，而瑞利成了 Google 的研究员，AT&T 实验室的新东家不再免费提供有限状态
机 C 语言工具库。虽然此前莫瑞等人公布了他们的详细算法，但是省略了实现的细节。因此在
学术界，不少科学家能够重写同样功能的工具库，但是很难达到 AT&T 工具库的效率（即运算
速度），这的确是一件令人遗憾的事。
数学之美 系列十一 ‐ Google 阿卡 47 的
制造者阿米特.辛格博士
2006 年 7 月 10 日 上午 09:52:00
发表者：Google 研究员，吴军
枪迷或者看过尼古拉斯.凯奇（Nicolas Cage)主演的电影方法的有效性。不少人试图用精确而复杂的办法对辛格的设计的各
种计算出它们的单
文本词汇频率/逆文本频率值（TF/IDF)。不难想象，和新闻主题有关的那些实词频率高，TF/IDF
值很大。我们按照这些实词在词汇表的位置对它们的 TF/IDF 值排序。比如，词汇表有六万四
千个词，分别为
单词编号 汉字词
------------------
1 阿
2 啊
3 阿斗
4 阿姨
...
789 服装
....
64000 做作
在一篇新闻中，这 64,000 个词的 TF/IDF 值分别为
单词编号 TF/IDF 值
==============
1 0
2 0.0034
3 0
4 0.00052
5 0
...
789 0.034
...
64000 0.075
如果单词表中的某个次在新闻中没有出现，对应的值为零，那么这 64,000 个数，组成一个
64,000 维的向量。我们就用这个向量来代表这篇新闻，并成为新闻的特征向量。如果两篇新闻
的特征向量相近，则对应的新闻内容相似，它们应当归在一类，反之亦然。
学过向量代数的人都知道，向量实际上是多维空间中有方向的线段。如果两个向量的方向一致，
即夹角接近零，那么这两个向量就相近。而要确定两个向量方向是否一致，这就要用到余弦定理
计算向量的夹角了。
余弦定理对我们每个人都不陌生，它描述了三角形中任何一个夹角和三个边的关系，换句话说，
给定三角形的三条边，我们可以用余弦定理求出三角形各个角的角度。假定三角形的三条边为 a,
b 和 c，对应的三个角为 A, B 和 C，那么角 A 的余弦 --
如果我们将三角形的两边 b 和 c 看成是两个向量，那么上述公式等价于
其中分母表示两个向量 b 和 c 的长度，分子表示两个向量的内积。举一个具体的例子，假如
新闻 X 和新闻 Y 对应向量分别是
x1,x2,...,x64000 和
y1,y2,...,y64000,
那么它们夹角的余弦等于，
当两条新闻向量夹角的余弦等于一时，这两条新闻完全重复（用这个办法可以删除重复的网页）；
当夹角的余弦接近于一时，两条新闻相似，从而可以归成一类；夹角的余弦越小，两条新闻越不
相关。
我们在中学学习余弦定理时，恐怕很难想象它可以用来对新闻进行分类。在这里，我们再一次看
到数学工具的用途。
数学之美 系列十三 信息指纹及其应用
2006 年 8 月 3 日 上午 11:17:00
发表者：吴军，Google 研究员
任何一段信息文字，都可以对应一个不太长的随机数，作为区别它和其它信息的指纹
（Fingerprint)。只要算法设计的好，任何两段信息的指纹都很难重复，就如同人类的指纹一样。
信息指纹在加密、信息压缩和处理中有着广泛的应用。
我们在图论和网络爬虫一文中提到，为了防止重复下载同一个网页，我们需要在哈希表中纪录已
经访问过的网址（URL)。但是
在哈希表中以字符串的形式直接存储网址，既费内存空间，又浪
费查找时间。现在的网址一般都较长，比如，如果在 Google 或者百度在查找数学之美，对应
的网址长度在一百个字符以上。下面是百度的链接
http://www.baidu.com/s?ie=gb2312&bs=%CA%FD%D1%A7%D6%AE%C3%C0&
sr=&z=&cl=3&f=8
&wd=%CE%E2%BE%FC+%CA%FD%D1%A7%D6%AE%C3%C0&ct=0
假定网址的平均长度为一百个字符，那么存贮 200 亿个网址本身至少需要 2 TB，即两千 GB
的容量，考虑到哈希表的存储效率一般只有 50%，实际需要的内存在 4 TB 以上。即使把这些
网址放到了计算机的内存中，由于网址长度不固定，以字符串的形式查找的效率会很低。因此，
我们如果能够找到一个函数，将这 200 亿个网址随机地映射到 128 二进位即 16 个字节的整
数空间，比如将上面那个很长的字符串对应成一个如下的随机数:
[***********][1**********]3
这样每个网址只需要占用 16 个字节而不是原来的一百个。这就能把存储网址的内存需求量降
低到原来的 1/6。这个 16 个字节的随机数，就称做该网址的信息指纹（Fingerprint)。可以
证明，只要产生随机数的算法足够好，可以保证几乎不可能有两个字符串的指纹相同，就如同不
可能有两个人的指纹相同一样。由于指纹是固定的 128 位整数，因此查找的计算量比字符串比
较小得多。网络爬虫在下载网页时，它将访问过的网页的网址都变成一个个信息指纹，存到哈希
表中，每当遇到一个新网址时，计算机就计算出它的指纹，然后比较该指纹是否已经在哈希表中，
来决定是否下载这个网页。这种整数的查找比原来字符串查找,可以快几倍到几十倍。
产生信息指纹的关键算法是伪随机数产生器算法（prng)。最早的 prng 算法是由计算机之父
冯诺伊曼提出来的。他的办法非常简单，就是将一个数的平方掐头去尾，取中间的几位数。比如
一个四位的二进制数 1001（相当于十进制的 9），其平方为 01010001 (十进制的 81）掐
头去尾剩下中间的四位 0100。当然这种方法产生的数字并不很随机，也就是说两个不同信息
很有可能有同一指纹。现在常用的 MersenneTwister 算法要好得多。
信息指纹的用途远不止网址的消重，信息指纹的的孪生兄弟是密码。信息指纹的一个特征是其不
可逆性, 也就是说,
无法根据信息指纹推出原有信息，这种性质， 正是网络加密传输所需要的。比如说，一个网站
可以根据用户的 Cookie 识别不同用户，这个 cookie 就是信息指纹。但是网站无法根据信息
指纹了解用户的身份，这样就可以保护用户的隐私。在互联网上，加密的可靠性，取决于
是否很
难人为地找到拥有同一指纹的信息， 比如一个黑客是否能随意产生用户的 cookie。从加密的
角度讲 MersenneTwister，算法并不好，因为它产生的随机数有相关性。
互联网上加密要用基于加密伪随机数产生器（csprng)。常用的算法有 MD5 或者 SHA1 等标
准，它们可以将不定长的信息变成定长的 128 二进位或者 160 二进位随机数。值得一提的事，
SHA1 以前被认为是没有漏洞的，现在已经被中国的王小云教授证明存在漏洞。但是大家不必
恐慌， 因为这和黑客能真正攻破你的注册信息是还两回事。
信息指纹的虽然历史很悠久，但真正的广泛应用是在有了互联网以后，这几年才渐渐热门起来。
数学之美 系列十四 谈谈数学模型的重要
性
2006 年 8 月 9 日 上午 09:12:00
发表者：吴军，Google 研究员
[注：一直关注数学之美系列的读者可能已经发现，我们对任何问题总是在找相应的准确的数学
模型。为了说明模型的重要性，今年七月份我在 Google 中国内部讲课时用了整整一堂课来讲
这个问题，下面的内容是我讲座的摘要。］
在包括哥白尼、伽利略和牛顿在内的所有天文学家中，我最佩服的是地心说的提出者托勒密。虽
然天文学起源于古埃及，并且在古巴比伦时，人们就观测到了五大行星（金、木、水、火、土）
运行的轨迹，以及行星在近日点运动比远日点快。（下图是在地球上看到的金星的轨迹，看过达
芬奇密码的读者知道金星大约每四年在天上画一个五角星。）
但是真正创立了天文学，并且计算出诸多天体运行轨迹的是两千年前古罗马时代的托勒密。虽然
今天我们可能会嘲笑托勒密犯的简单的错误，但是真正了解托勒密贡献的人都会对他肃然起敬。
托勒密发明了球坐标，定义了包括赤道和零度经线在内的经纬线，他提出了黄道，还发明了弧度
制。
当然，他最大也是最有争议的发明是地心说。虽然我们知道地球是围绕太阳运动的，但是在当时，
从人们的观测出发，很容易得到地球是宇宙中心的结论。从地球上看，行星的运动轨迹是不规则
的，托勒密的伟大之处是用四十个小圆套大圆的方法，精确地计算出了所有行星运动的轨迹。（托
勒密继承了毕达格拉斯的一些思想，他也认为圆是最完美的几何图形。）托勒密模型的精度之高，
让以后所有的科学家惊叹不已。即使今天，我们在计算机的帮助下，也很难解出四十个套在一起
的圆的方程。每每想到这里，我都由衷地佩服托勒密。一千五百年来，人们根据他的计算决定农
时。但是，经过了一千五百年，托勒密对太阳运动的累积误差
，还是差出了一星期。
地心说的示意图，我国天文学家张衡的浑天地动说其实就是地心说。
纠正地心说错误不是靠在托勒密四十个圆的模型上再多套上几个圆，而是进一步探索真理。哥白
尼发现，如果以太阳为中心来描述星体的运行，只需要 8-10 个圆，就能计算出一个行星的运
动轨迹，他提出了日心说。很遗憾的事，哥白尼正确的假设并没有得到比托勒密更好的结果，哥
白尼的模型的误差比托勒密地要大不少。这是教会和当时人们认为哥白尼的学说是邪说的一个原
因，所以日心说要想让人心服口服地接受，就得更准确地描述行星运动。
完成这一使命的是开普勒。开普勒在所有一流的天文学家中，资质较差，一生中犯了无数低级的
错误。但是他有两条别人没有的东西，从他的老师第谷手中继承的大量的、在当时最精确的观测
数据，以及运气。开普勒很幸运地发现了行星围绕太阳运转的轨道实际是椭圆形的，这样不需要
用多个小圆套大圆，而只要用一个椭圆就能将星体运动规律描述清楚了。只是开普勒的知识和水
平不足以解释为什么行星的轨道是椭圆形的。最后是伟大的科学家牛顿用万有引力解释了这个问
题。
故事到这里似乎可以结束了。但是，许多年后，又有了个小的波澜。天文学家们发现，天王星的
实际轨迹和用椭圆模型算出来的不太符合。当然，偷懒的办法是接着用小圆套大圆的方法修正，
但是一些严肃的科学家在努力寻找真正的原因。英国的亚当斯和法国的维内尔（Verrier）独立
地发现了吸引天王星偏离轨道的海王星。
讲座结束前，我和 Google 中国的工程师们一同总结了这么几个结论：
１ . 一个正确的数学模型应当在形式上是简单的。（托勒密的模型显然太复杂。）
２ . 一个正确的模型在它开始的时候可能还不如一个精雕细琢过的错误的模型来的准确，但是，
如果我们认定大方向是对的，就应该坚持下去。（日心说开始并没有地心说准确。）
３ . 大量准确的数据对研发很重要。
４ . 正确的模型也可能受噪音干扰，而显得不准确；这时我们不应该用一种凑合的修正方法来
弥补它，而是要找到噪音的根源，这也许能通往重大发现。
在网络搜索的研发中，我们在前面提到的单文本词频/逆文本频率指数（TF/IDF) 和网页排名
（page rank)都相当于是网络搜索中的单。但是，事实上，自然语言处理中也有一些
特例，比如有些学者将一个问题研究到极致，执著追求完善甚至可以说完美的程度。他们的工作
对同行有很大的参考价值，因此我们在科研中很需要这样的学者。在自然语言处理方面新一代的
顶级人物麦克尔 · 柯林斯 (Michael Collins) 就是这样的人。
柯林斯：追求完美
柯林斯从师于自然语言处理大师马库斯 (Mitch Marcus)（我们以后还会多次提到马库斯），从
宾夕法利亚大学获得博士学位，现任麻省理工学院 (MIT) 副教授（别看他是副教授，他的水平
在当今自然语言处理领域是数一数二的），在作博士期间，柯林斯写了一个后来以他名字命名的
自然语言文法分析器 (sentence parser)，可以将书面语的每一句话准确地进行文法分析。文
法分析是很多自然语言应用的基础。虽然柯林斯的师兄布莱尔 (Eric Brill) 和 Ratnaparkhi 以
及师弟 Eisnar 都完成了相当不错的语言文法分析器，但是柯林斯却将它做到了极致，使它在
相当长一段时间内成为世界上最好的文法分析器。柯林斯成功的关键在于将文法分析的每一个细
节都研究得很仔细。柯林斯用的数学模型也很漂亮，整个工作可以用完美来形容。我曾因为研究
的需要，找柯林斯要过他文法分析器的源程序，他很爽快地给了我。我试图将他的程序修改一下
来满足我特定应用的要求，但后来发现，他的程序细节太多以至于很难进一步优化。柯林斯的博
士论文堪称是自然语言处理领域的范文。它像一本优秀的小说，把所有事情的来龙去脉介绍的清
清楚楚，对于任何有一点计算机和自然语言处理知识的人，都可以轻而易举地读懂他复杂的方法。
柯林斯毕业后，在 AT&T 实验室度过了三年快乐的时光。在那里柯林斯完成了许多世界一流的
研究工作诸如隐含马尔科夫模型的区别性训练方法，卷积核在自然语言处理中的应用等等。三年
后，AT&T 停止了自然语言处理方面的研究，柯林斯幸运地在 MIT 找到了教职。在 MIT 的短
短几年间，柯林斯多次在国际会议上获得最佳论文奖。相比其他同行，这种成就是独一无二的。
柯林斯的特点就是把事情做到极致。如果说有人喜欢是基于变换规则的机器学习方法 (transformation rule based machine
learning)。这个方法名称虽然很复杂，其实非常简单。我们以拼音转换字为例来说明它：
第一步，我们把每个拼音对应的汉字中最常见的找出来作为第一遍变换的结果，当然结果有不少
错误。比如，是一个非常有意思的题目，但是把它讲清楚要用两个系列的篇幅。]
前段时间，Google 中国研究院的刘骏总监谈到在网络搜索排名中，用到的信息有上百种。更普
遍地讲，在自然语言处理中，我们常常知道各种各样的但是又不完全确定的信息，我们需要用一
个统一的模型将这些信息综合起来。如何综合得好，是一门很大的学问。
让我们看一个拼音转汉字的简单的例子。假如输入的拼音是反面一定是三点等等。（事实上，有的色子四点反面不是三点而是
一点。）这种基于直觉的猜测之所以准确，是因为它恰好符合了最大熵原理。
最大熵原理指出，当我们需要对一个随机事件的概率分布进行预测时，我们的预测应当满足全部
已知的条件，而对未知的情况不要做任何主观假设。（不做主观假设这点很重要。）在这种情况
下，概率分布最均匀，预测的风险最小。因为这时概率分布的信息熵最大，所以人们称这种模型
叫均匀分布。
2. 用第 N 次迭代的模型来估算每种信息特征在训练数据中的分布，如果超过了实际的，就把
相应的模型参数变小；否则，将它们便大。
3. 重复步骤 2 直到收敛。
GIS 最早是由 Darroch 和 Ratcliff 在七十年代提出的。但是，这两人没有能对这种算法的物
理含义进行很好地解释。后来是由数学家希萨（Csiszar)解释清楚的，因此，人们在谈到这个算
法时，总是同时引用 Darroch 和 Ratcliff 以及希萨的两篇论文。GIS 算法每次迭代的时间都
很长，需要迭代很多次才能收敛，而且不太稳定，即使在 64 位计算机上都会出现溢出。因此，
在实际应用中很少有人真正使用 GIS。大家只是通过它来了解最大熵模型的算法。
八十年代，很有天才的孪生兄弟的达拉皮垂(Della Pietra)在 IBM 对 GIS 算法进行了两方面
的改进，提出了改进迭代算法 IIS（improved iterative scaling）。这使得最大熵模型的训
练时间缩短了一到两个数量级。这样最大熵模型才有可能变得实用。即使如此，在当时也只有
IBM 有条件是用最大熵模型。
由于最大熵模型在数学上十分完美，对科学家们有很大的诱惑力，因此不少研究者试图把自己的
问题用一个类似最大熵的近似模型去套。谁知这一近似，最大熵模型就变得不完美了，结果可想
而知，比打补丁的凑合的方法也好不了多少。于是，不少热心人又放弃了这种方法。第一个在实
际信息处理应用中验证了最大熵模型的优势的，是宾夕法尼亚大学马库斯的另一个高徒原 IBM
现微软的研究员拉纳帕提(Adwait Ratnaparkhi)。拉纳帕提的聪明之处在于他没有对最大熵模
型进行近似，而是找到了几个最适合用最大熵模型、而计算量相对不太大的自然语言处理问题，
比如词性标注和句法分析。拉纳帕提成功地将上下文信息、词性（名词、动词和形容词等）、句
子成分（主谓宾）通过最大熵模型结合起来，做出了当时世界上最好的词性标识系统和句法分析
器。拉纳帕提的论文发表后让人们耳目一新。拉纳帕提的词性标注系统，至今仍然是使用单一方
法最好的系统。科学家们从拉纳帕提的成就中，又看到了用最大熵模型解决复杂的文字信息处理
的希望。
但是，最大熵模型的计算量仍然是个拦路虎。我在学校时花了很长时间考虑如何简化最大熵模型
的计算量。终于有一天，我对我的导师说，我发现一种数学变换，可以将大部分最大熵模型的训
练时间在 IIS 的基础上减少两个数量级。我在黑板上推导了一个多小时，他没有找出我的推导
中的任何破绽，接着他又回去想了两天，然后告诉我我的算法是
对的。从此，我们就建造了一些
很大的最大熵模型。这些模型比修修补补的凑合的方法好不少。即使在我找到了快速训练算法以
后，为了训练一个包含上下文信息，主题信息和语法信息的文法模型(language model)，我并
行使用了 20 台当时最快的 SUN 工作站，仍然计算了三个月。由此可见最大熵模型的复杂的
一面。最大熵模型快速算法的实现很复杂，到今天为止，世界上能有效实现这些算法的人也不到
一百人。有兴趣实现一个最大熵模型的读者可以阅读我的论文。
最大熵模型，可以说是集简与繁于一体，形式简单，实现复杂。值得一提的是，在 Google 的很
多产品中，比如机器翻译，都直接或间接地用到了最大熵模型。
讲到这里，读者也许会问，当年最早改进最大熵模型算法的达拉皮垂兄弟这些年难道没有做任何
事吗？他们在九十年代初贾里尼克离开 IBM 后，也退出了学术界，而到在金融界大显身手。他
们两人和很多 IBM 语音识别的同事一同到了一家当时还不大，但现在是世界上最成功对冲基金
(hedge fund)公司----文艺复兴技术公司 (Renaissance Technologies)。我们知道，决定股
票涨落的因素可能有几十甚至上百种，而最大熵方法恰恰能找到一个同时满足成千上万种不同条
件的模型。达拉皮垂兄弟等科学家在那里，用于最大熵模型和其他一些先进的数学工具对股票预
测，获得了巨大的成功。从该基金 1988 年创立至今，它的净回报率高达平均每年 34%。也
就是说，如果 1988 年你在该基金投入一块钱，今天你能得到 200 块钱。这个业绩，远远超
过股神巴菲特的旗舰公司伯克夏哈撒韦（Berkshire Hathaway)。同期，伯克夏哈撒韦的总回
报是 16 倍。
值得一提的是，信息处理的很多数学手段，包括隐含马尔可夫模型、子波变换、贝叶斯网络等等，
在华尔街多有直接的应用。由此可见，数学模型的作用。
数学之美 系列十七 闪光的不一定是金子
谈 谈 搜 索 引 擎 作 弊 问 题 (Search Engine
Anti‐SPAM)
2006 年 11 月 28 日 上午 03:18:00
Google 研究员 吴军
自从有了搜索引擎，就有了针对搜索引擎网页排名的作弊(SPAM)。以至于用户发现在搜索引擎
中排名靠前的网页不一定就是高质量的，用句俗话说，闪光的不一定是金子。
搜索引擎的作弊，虽然方法很多，目的只有一个，就是采用不正当手段提高自己网页的排名。早
期最常见的作弊方法是重复关键词。比如一个卖数码相机的网站，重复地罗列各种数码相机的品
牌，如尼康、佳能和柯达等等。为了不让读者看到众多讨厌的关键词，聪明一点的作弊者常用很
小
的字体和与背景相同的颜色来掩盖这些关键词。其实，这种做法很容易被搜索引擎发现并纠正。
在有了网页排名(page rank)以后，作弊者发现一个网页被引用的连接越多，排名就可能越靠前，
于是就有了专门卖链接和买链接的生意。比如，有人自己创建成百上千个网站，这些网站上没有
实质的内容，只有到他们的客户网站的连接。这种做法比重复关键词要高明得多，但是还是不太
难被发现。因为那些所谓帮别人提高排名的网站，为了维持生意需要大量地卖链接，所以很容易
露马脚。（这就如同造假钞票，当某一种假钞票的流通量相当大以后，就容易找到根源了。）再
以后，又有了形形色色的作弊方式，我们就不在这里一一赘述了。
几年前，我加入 Google 做的第一件事就是消除网络作弊。在 Google 最早发现搜索引擎作弊的
是 Matt Cutts，他在我加入 Google 前几个月开始研究这个问题，后来，辛格，马丁和我先后
加入进来。我们经过几个月的努力，清除了一半的作弊者。(当然，以后抓作弊的效率就不会有
这么高了。）其中一部分网站从此除，因为作弊者的方法不可能是随机的（否则就无法提高排
名了）。而且，作弊者也不可能是一天换一种方法，即作弊方法是时间相关的。因此，搞搜索引
擎排名算法的人，可以在搜集一段时间的作弊信息后，将作弊者抓出来，还原原有的排名。当然
这个过程需要时间，就如同采集汽车发动机噪音需要时间一样，在这段时间内，作弊者可能会尝
到些甜头。因此，有些人看到自己的网站经过所谓的优化（其实是作弊），排名在短期内靠前了，
以为这种所谓的优化是有效的。但是，不久就会发现排名掉下去了很多。这倒不是搜索引擎以前
宽容，现在严厉了，而是说明抓作弊需要一定的时间，以前只是还没有检测到这些作弊的网站而
已。
还要强调一点，Google 抓作弊和恢复网站原有排名的过程完全是自动的(并没有个人的好恶），
就如同手机消除噪音是自动的一样。一个网站要想长期排名靠前，就需要把内容做好，同时要和
那些作弊网站划清界限。
数学之美 系列十八 － 矩阵运算和文本处
理中的分类问题
2007 年 1 月 1 日 下午 03:10:00
发表者：Google 研究员，吴军
我在大学学习线性代数时，实在想不出它除了告诉我们如何解线性方程外，还能有什么别的用途。
关于矩阵的许多概念，比如特征值等等，更是脱离日常生活。后来在数值分析中又学了很多矩阵
的近似算法，还是看不到可以应用的地方。当时选这些课，完全是为了混学分的学位。我想，很
多同学都多多少少有过类似的经历。直到后来长期做自然语言处理的研究，我才发现数学家们提
出那些矩阵的概念和算法，是有实际应用的意义的。
在自然语言处理中，最常见的两类的分类问题分别是，将文本按主题归类（比如将所有介绍亚运
会的新闻归到体育类）和将词汇表中的字词按意思归类（比如将各种体育运动的名称个归成一类）。
这两种分类问题都可用通过矩阵运算来圆满地、同时解决。为了说明如何用矩阵这个工具类解决
这两个问题的，让我们先来来回顾一下我们在余弦定理和新闻分类中介绍的方法。
分类的关键是计算相关性。我们首先对两个文本计算出它们的内容词，或者说实词的向量，然后
求这两个向量的夹角。当这两个向量夹角为零时，新闻就相关；当它们垂直或者说正交时，新闻
则无关。当然，夹角的余弦等同于向量的内积。从理论上讲，这种算法非常好。但是计算时间特
别长。通常，我们要处理的文章的数量都很大，至少在百万篇以上，二次回标有非常长，比如说
有五十万个词（包括人名地名产品名称等等
）。如果想通过对一百万篇文章两篇两篇地成对比较，
来找出所有共同主题的文章，就要比较五千亿对文章。现在的计算机一秒钟最多可以比较一千对
文章，完成这一百万篇文章相关性比较就需要十五年时间。注意，要真正完成文章的分类还要反
复重复上述计算。
在文本分类中，另一种办法是利用矩阵运算中的奇异值分解（Singular Value Decomposition，
简称 SVD)。现在让我们来看看奇异值分解是怎么回事。首先，我们可以用一个大矩阵 A 来描
述这一百万篇文章和五十万词的关联性。这个矩阵中，每一行对应一篇文章，每一列对应一个词。
在上面的图中，M=1,000,000，N=500,000。第 i 行，第 j 列的元素，是字典中第 j 个词
在第 i 篇文章中出现的加权词频（比如，TF/IDF)。读者可能已经注意到了，这个矩阵非常大，
有一百万乘以五十万，即五千亿个元素。
奇异值分解就是把上面这样一个大矩阵，分解成三个小矩阵相乘，如下图所示。比如把上面的例
子中的矩阵分解成一个一百万乘以一百的矩阵 X，一个一百乘以一百的矩阵 B，和一个一百乘以
五十万的矩阵 Y。这三个矩阵的元素总数加起来也不过 1.5 亿，仅仅是原来的三千分之一。相应
的存储量和计算量都会小三个数量级以上。
三个矩阵有非常清楚的物理含义。第一个矩阵 X 中的每一行表示意思相关的一类词，其中的每
个非零元素表示这类词中每个词的重要性（或者说相关性），数值越大越相关。最后一个矩阵 Y
中的每一列表示同一主题一类文章，其中每个元素表示这类文章中每篇文章的相关性。中间的矩
阵则表示类词和文章雷之间的相关性。因此，我们只要对关联矩阵 A 进行一次奇异值分解，w 我
们就可以同时完成了近义词分类和文章的分类。（同时得到每类文章和每类词的相关性）。
现在剩下的唯一问题，就是如何用计算机进行奇异值分解。这时，线性代数中的许多概念，比如
矩阵的特征值等等，以及数值分析的各种算法就统统用上了。在很长时间内，奇异值分解都无法
并行处理。（虽然 Google 早就有了 MapReduce 等并行计算的工具，但是由于奇异值分解很
难拆成不相关子运算，即使在 Google 内部以前也无法利用并行计算的优势来分解矩阵。）最
近，Google 中国的张智威博士和几个中国的工程师及实习生已经实现了奇异值分解的并行算法，
我认为这是 Google 中国对世界的一个贡献。
数学之美 系列十九 － 马尔可夫链的扩展
贝叶斯网络 (Bayesian Networks)
2007 年 1 月 28 日 下午 09:53:00
发表者：Google 研究员，吴军
我们在前面的
系列中多次提到马尔可夫链 (Markov
Chain)，它描述了一种状态序列，其每个状态值取决于前面有限个状态。这种模型，对很多实
际问题来讲是一种很粗略的简化。在现实生活中，很多事物相互的关系并不能用一条链来串起来。
它们之间的关系可能是交叉的、错综复杂的。比如在下图中可以看到，心血管疾病和它的成因之
间的关系是错综复杂的。显然无法用一个链来表示。
我们可以把上述的有向图看成一个网络，它就是贝叶斯网络。其中每个圆圈表示一个状态。状态
之间的连线表示它们的因果关系。比如从心血管疾病出发到吸烟的弧线表示心血管疾病可能和吸
烟有关。当然，这些关系可以有一个量化的可信度 (belief)，用一个概率描述。我们可以通过
这样一张网络估计出一个人的心血管疾病的可能性。在网络中每个节点概率的计算，可以用贝叶
斯公式来进行，贝叶斯网络因此而得名。由于网络的每个弧有一个可信度，贝叶斯网络也被称作
信念网络 (belief networks)。
和马尔可夫链类似，贝叶斯网络中的每个状态值取决于前面有限个状态。不同的是，贝叶斯网络
比马尔可夫链灵活，它不受马尔可夫链的链状结构的约束，因此可以更准确地描述事件之间的相
关性。可以讲，马尔可夫链是贝叶斯网络的特例，而贝叶斯网络是马尔可夫链的推广。
使用贝叶斯网络必须知道各个状态之间相关的概率。得到这些参数的过程叫做训练。和训练马尔
可夫模型一样，训练贝叶斯网络要用一些已知的数据。比如在训练上面的网络，需要知道一些心
血管疾病和吸烟、家族病史等有关的情况。相比马尔可夫链，贝叶斯网络的训练比较复杂，从理
论上讲，它是一个 NP-complete 问题，也就是说，对于现在的计算机是不可计算的。但是，
对于某些应用，这个训练过程可以简化，并在计算上实现。
值得一提的是 IBM Watson 研究所的茨威格博士 (Geoffrey Zweig) 和西雅图华盛顿大学的
比尔默 (Jeff Bilmes) 教授完成了一个通用的贝叶斯网络的工具包，提供给对贝叶斯网络有兴
趣的研究者。
贝叶斯网络在图像处理、文字处理、支持决策等方面有很多应用。在文字处理方面，语义相近的
词之间的关系可以用一个贝叶斯网络来描述。我们利用贝叶斯网络，可以找出近义词和相关的词，
在 Google 搜索和 Google 广告中都有直接的应用。
数学之美 系列二十 －自然语言处理的教
父 马库斯
2007 年 4 月 13 日 下午 07:03:00
发表者：Google 研究员，吴军
我们在前面的系列中介绍和提到了一些年轻有为的科学家，迈克尔·柯林斯，艾里克·
布莱尔，大
卫·雅让斯基，拉纳帕提等等，他们都出自宾夕法尼亚计算机系米奇·马库斯(Mitch Marcus)名
下。就像许多武侠小说中描写的，弟子都成了各派的掌门，师傅一定了不得。的确，马库斯虽然
作为第一作者发表的论文并不多，但是从很多角度上讲，他可以说是自然语言处理领域的教父。
马库斯教授长期当任宾夕法尼亚大学计算机系主任，直到他在几年前从 AT&T 找到皮耶尔替代
他为止。作为一个管理者，马库斯显示出在自然处理和计算机科学方面的卓识的远见。在指导博
士生时，马库斯发现语料库在自然语言处理中的重要性。马库斯呕心沥血，花了十几年工夫建立
了一系列标准的语料库，提供给全世界的学者使用。这套被称为 LDC 的语料库，是当今全世界
自然语言处理的所有学者都使用的工具。我们在以前的系列中讲到，当今的自然语言处理几乎都
是使用给予统计的方法。要做统计，就需要大量有代表性的数据。利用这些数据开发一个自然语
言处理系统的过程，可以统称为训练。比如，我们要训练一个汉语分词系统，我们需要一些已经
分好词的中文句子。当然这些句子需要有代表性。如果想知道一个分词系统的准确性，我们也需
要一些人工分好词的句子进行测试。这些人工处理好的文字数据库，成为语料库(corpus)。如
果每个研究室都人工建立几个语料库，不仅浪费时间精力，而且发表文章时，数据没有可比性。
因此，马库斯想到了建立一系列标准的语料库为全世界的学者用。他利用自己的影响力让美国自
然科学基金会和 DARPA 出钱立项，联络的多所大学和研究机构，建立的数百个标准的语料库。
其中最著名的是 PennTree
Bank 的语料库。PennTree Bank 覆盖多种语言（包括中文）。每一种语言，它有几十万到
几百万字的有代表性的句子，每个句子都有的词性标注，语法分析树等等。LDC 语料库如今已
成为全世界自然语言处理科学家共用的数据库。如今，在自然语言处理方面发表论文，几乎都要
提供基于 LDC 语料库的测试结果。
马库斯给予他的博士生研究自己感兴趣的课题的自由，这是他之所以桃李满天下的原因。马库斯
对几乎所有的自然语言处理领域有独到的见解。和许多教授让博士生去做他拿到基金的项目，马
库斯让博士生提出自己有兴趣的课题，或者用他已有的经费支持学生，或者为他们的项目区申请
经费。马库斯高屋建瓴，能够很快的判断一个研究方向是否正确，省去了博士生很多
try-and-error 的时间。因此他的学生有些很快地拿到的博士学位。
作为系主任，马库斯在专
业设置方面显示出卓识的远见。我有幸和他在同一个校务顾问委员会任
职，一起讨论计算机系的研究方向。马库斯在几年前互联网很热门、很多大学开始互联网研究时，
看到 bioinformatics (生物信息学）的重要性，在宾夕法利亚大学设置这个专业，并且在其他
大学还没有意识到时，开始招聘这方面的教授。马库斯还建议一些相关领域的教授，包括后来的
系主任皮耶尔把一部分精力转到生物信息学方面。马库斯同时向他担任顾问的其他一些大学提出
同样的建议。等到网络泡沫破裂以后，很多大学的计算机系开始向生物信息学转向，但是发现已
经很难找到这些方面好的教授了。我觉得，当今中国的大学，最需要的就是马库斯这样卓有远见
的管理者。
过几天我又要和马库斯一起开顾问委员会的会议了，不知道这次他对计算机科学的发展有什么见
解。
数学之美 系列二十一 － 布隆过滤器
（Bloom Filter）
2007 年 7 月 3 日 上午 09:35:00
发表者：Google（谷歌）研究员 吴军
在日常生活中，包括在设计计算机软件时，我们经常要判断一个元素是否在一个集合中。比如在
字处理软件中，需要检查一个英语单词是否拼写正确（也就是要判断它是否在已知的字典中）；
在 FBI，一个嫌疑人的名字是否已经在嫌疑名单上；在网络爬虫里，一个网址是否被访问过等
等。最直接的方法就是将集合中全部的元素存在计算机中，遇到一个新元素时，将它和集合中的
元素直接比较即可。一般来讲，计算机中的集合是用哈希表（hash table）来存储的。它的好
处是快速准确，缺点是费存储空间。当集合比较小时，这个问题不显著，但是当集合巨大时，哈
希表存储效率低的问题就显现出来了。比如说，一个象 Yahoo,Hotmail 和 Gmai 那样的公众
电子邮件（email）提供商，总是需要过滤来自发送垃圾邮件的人（spamer）的垃圾邮件。一
个办法就是记录下那些发垃圾邮件的 email 地址。由于那些发送者不停地在注册新的地址，全
世界少说也有几十亿个发垃圾邮件的地址，将他们都存起来则需要大量的网络服务器。如果用哈
希表，每存储一亿个 email 地址， 就需要 1.6GB 的内存（用哈希表实现的具体办法是将每
一 个 email 地 址 对 应 成 一 个 八 字 节 的 信 息 指 纹
googlechinablog.com/2006/08/blog-post.html，然后将这些信息指纹存入哈希表，由于
哈希表的存储效率一般只有 50%，因此一个 email 地址需要占用十六个字节。一亿个地址大
约要 1.6GB， 即十六亿字节的内存）。因此存贮几十亿个邮件地址
可能需要上百 GB 的内存。
除非是超级计算机，一般服务器是无法存储的。
今天，我们介绍一种称作布隆过滤器的数学工具，它只需要哈希表 1/8 到 1/4 的大小就能解
决同样的问题。
布隆过滤器是由巴顿.布隆于一九七零年提出的。它实际上是一个很长的二进制向量和一系列随
机映射函数。我们通过上面的例子来说明起工作原理。
假定我们存储一亿个电子邮件地址，我们先建立一个十六亿二进制（比特），即两亿字节的向量，
然后将这十六亿个二进制全部设置为零。对于每一个电子邮件地址 X，我们用八个不同的随机
数产生器（F1,F2, ...,F8） 产生八个信息指纹（f1, f2, ..., f8）。再用一个随机数产生器 G 把
这八个信息指纹映射到 1 到十六亿中的八个自然数 g1, g2, ...,g8。现在我们把这八个位置的
二进制全部设置为一。当我们对这一亿个 email 地址都进行这样的处理后。一个针对这些
email 地址的布隆过滤器就建成了。（见下图）
现在，让我们看看如何用布隆过滤器来检测一个可疑的电子邮件地址 Y 是否在黑名单中。我们
用相同的八个随机数产生器（F1, F2, ..., F8）对这个地址产生八个信息指纹 s1,s2,...,s8，然
后将这八个指纹对应到布隆过滤器的八个二进制位，分别是 t1,t2,...,t8。如果 Y 在黑名单中，
显然，t1,t2,..,t8 对应的八个二进制一定是一。这样在遇到任何在黑名单中的电子邮件地址，
我们都能准确地发现。
布隆过滤器决不会漏掉任何一个在黑名单中的可疑地址。但是，它有一条不足之处。也就是它有
极小的可能将一个不在黑名单中的电子邮件地址判定为在黑名单中，因为有可能某个好的邮件地
址正巧对应个八个都被设置成一的二进制位。好在这种可能性很小。我们把它称为误识概率。在
上面的例子中，误识概率在万分之一以下。
布隆过滤器的好处在于快速，省空间。但是有一定的误识别率。常见的补救办法是在建立一个小
的白名单，存储那些可能别误判的邮件地址。
数学之美 系列二十二 由电视剧《暗算》所
想到的 - 谈谈密码学的数学原理
2007 年 9 月 13 日 下午 09:00:00
发表者：Google（谷歌）研究员 吴军
前一阵子看了电视剧《暗算》，蛮喜欢它的构思和里面的表演。其中有一个故事提到了密码学，
故事本身不错，但是有点故弄玄虚。不过有一点是对的，就是当今的密码学是以数学为基础的。
（ 没 有 看 过 暗 算 的 读 者 可 以 看 一 下 介 绍 ，
http://ent.sina.com.cn/v/2005-10-17/ba866985.shtml
因为我们后面要多次提到这
部电视剧。）
密码学的历史大致可以推早到两千年前，相传名将凯撒为了防止敌方截获情报，用密码传送情报。
凯撒的做法很简单，就是对二十几个罗马字母建立一张对应表，比如说
这样，如果不知道密码本，即使截获一段信息也看不懂，比如收到一个的消息是 EBKTBP，那
么在敌人看来是毫无意义的字，通过密码本解破出来就是 CAESAR 一词，即凯撒的名字。这
种编码方法史称凯撒大帝。当然，学过信息论的人都知道，只要多截获一些情报，统计一下字母
的频率，就可以解破出这种密码。柯蓝道尔在他的员老陈破译的一份密报后，但无法推广的原因，
而数学家黄依依预见到了这个结果，因为她知道敌人新的密码系统编出的密文是统计独立的。有
了信息论后，密码的设计就有了理论基础，现在通用的公开密钥的方法，包括《暗算》里的[***********][***********][1**********]051
[1**********]94
[***********][***********][***********][1**********]
[**************]
=
[***********][***********][***********][1**********]
55281177
×[***********][***********][***********]0043952099
[***********]6139
现在，让我们回到《暗算》中，黄依依第一次找的结果经过一系列计算发现无法归零，也就是说
除不尽，我猜她可能试图将一个大数 N 做分解，没成功。第二次计算的结果是归零了，说明她
找到的 N=P×Q 的分解方法。当然，这件事能不能用算盘完成，我就不知道了，但我觉得比较
夸张。另外我对该电视剧还有一个搞不懂的问题就是里面提到的输入法的字库从二级国标扩展到更大的字库 GBK，由于后面不常见的
字频率较短，平均编码长度比针对国标的大不了多少。让我们回忆一下汉字的信息熵（见
http://www.googlechinablog.com/2006/04/4.html），
H = -p1 * log p1 - ... - p6700 log p6700。
我们如果对每一个字进行统计，而且不考虑上下文相关性，大致可以估算出它的值在十比特以内，
当然这取决于用什么语料库来做估计。如果我们假定输入法只能用 26 个字母输入，那么每个
字母可以代表 log26=
4.7 比特的信息，也就是说，输入一个汉字平均需要敲 10/4.7= 2.1 次键。
聪明的读者也许一经发现，如果我们把汉字组成词，再以词为单位统计信息熵，那么，每个汉字
的平均信息熵将会减少。这样，平均输入一个字可以少敲零点几次键盘。不考虑词的上下文相关
性，以词为单位统计，汉字的信息熵大约是 8 比特作用，也就是说，以词为单位输入一个汉字
平均只需要敲 8/4.7=1.7 次键。这就是现在所有输入法都是基于词输入的内在原因。当然，
如 果 我 们 再 考 虑 上 下 文 的 相 关 性 ， 对 汉 语 建 立 一 个 基 于 词 的 统 计 语 言 模 型 （ 见
http://www.googlechinablog.com/2006/04/blog-post.html），我们可以将每个汉字的
信息熵降到 6 比特作用，这时，输入一个汉字只要敲 6/4.7=1.3 次键。如果一种输入方法能
做到这一点，那么汉字的输入已经比英文快的多了。
但是，事实上没有一种输入方法接近这个效率。这里面主要有两个原因。首先，要接近信息论给
的这个极限，就要对汉字的词组根据其词频进行特殊编码。事实上像王码这类的输入方法就是这
么做到，只不过它们第一没有对词组统一编码，第二没有有效的语言模型。这种编码方法理论上
讲有效，实际上不实用。原因有两个，第一，很难学；第二，从认知科学的角度上讲，人一心无
二用，人们在没有稿子边想边写的情况下不太可能在回忆每个词复杂的编码的同时又不中断思维。
我们过去在研究语言识别时做过很多用户测试，发现使用各种复杂编码输入法的人在脱稿打字时
的速度只有他在看稿打字时的一半到四分之一。因此，虽然每个字平均敲键次数少，但是打键盘
的速度也慢了很多，总的并不快。这也就是为什么基于拼音的简单输入法占统治地位的原因。事
实上，汉语全拼的平均长度为 2.98，只要基于拼音的输入法能利用上下文彻底解决一音多字的
问题，平均每个汉字输入的敲键次数应该在三次左右，每分钟输入 100 个字完全有可能达到。
另外一个不容易达到信息论极限的输入速度的原因在于，这个理论
值是根据一个很多的语言模型
计算出来的。在产品中，我们不可能占有用户太多的内存空间，因此各种输入方法提供给用户的
是一个压缩的很厉害的语音模型，而有的输入方法为了减小内存占用，根本没有语言模型。拼音
输入法的好坏关键在准确而有效的语言模型。
另一方面，由于现有输入方法离信息论给的极限还有很大的差距，汉语输入方法可提升的空间很
大，会有越来越好用的输入方法不断涌现。当然，输入速度只是输入法的一项而不是唯一的衡量
标 准 。 我 们 也 会 努 力 把 谷 歌 的 输 入 法 做 的 越 来 越 好 。 大 家 不 妨 先 试 试 现 在 的 版 本 ，
http://tools.google.com/pinyin/，半年后再看看我们有没有提高。
数学之美 系列一 ‐‐ 统计语言模型 .............................................................................................. 2
数学之美 系列二 ‐‐ 谈谈中文分词 .............................................................................................. 3
数学之美 系列三 ‐‐ 隐含马尔可夫模型在语言处理中的应用 ................................................... 5
数学之美 系列四 ‐‐ 怎样度量信息? ............................................................................................ 7
数学之美 系列五 ‐‐ 简单之美：布尔代数和搜索引擎的索引 ................................................... 9
数学之美 系列六 ‐‐ 图论和网络爬虫 (Web Crawlers) ............................................................. 11
数学之美 系列七 ‐‐ 信息论在信息处理中的应用 .................................................................... 13
数学之美 系列八‐‐ 贾里尼克的故事和现代语言处理 .............................................................. 15
数学之美 系列九 ‐‐ 如何确定网页和查询的相关性 ................................................................ 17
数学之美 系列十 有限状态机和地址识别 ................................................................................. 19
数学之美 系列十一 ‐ Google 阿卡 47 的制造者阿米特.辛格博士 ........................................ 20
数学之美 系列十二 ‐ 余弦定理和新闻的分类 .......................................................................... 21
数学之美 系列十三 信息指纹及其应用 ..................................................................................... 24
数学之美 系列十四 谈谈数学模型的重要性 ............................................................................. 25
数学之美 系列十五 繁与简 自然语言处理的几位精英 ........................................................... 27
数学之美 系列十六（上） 不要把所有的鸡蛋放在一个篮子里 ‐‐ 谈谈最大熵模型 ........... 29
数学之美 系列十六 （下）－ 不要把所有的鸡蛋放在一个篮子里 最大熵模型 ............... 31
数学之美 系列十七 闪光的不一定是金子 谈谈搜索引擎作弊问题(Search Engine Anti‐SPAM)
........................................................................................................................................................ 32
数学之美 系列十八 － 矩阵运算和文本处理中的分类问题 ................................................... 35
数学之美 系列十九 － 马尔可夫链的扩展 贝叶斯网络 (Bayesian Networks) ...................... 37
数学之美 系列二十 －自然语
言处理的教父 马库斯 ............................................................... 38
数学之美 系列二十一 － 布隆过滤器（Bloom Filter） ........................................................... 39
数学之美 系列二十二 由电视剧《暗算》所想到的 - 谈谈密码学的数学原理 .................. 41
数学之美 系列二十三 输入一个汉字需要敲多少个键 - 谈谈香农第一定律 ...................... 44
数学之美 系列一 ‐‐ 统计语言模型
2006 年 4 月 3 日 上午 08:15:00
从本周开始，我们将定期刊登 Google 科学家吴军写的《数学之美》系列文章，介绍数学在信
息检索和自然语言处理中的主导作用和奇妙应用。
发表者: 吴军, Google 研究员
前言
也许大家不相信，数学是解决信息检索和自然语言处理的最好工具。它能非常清晰地描述这些领
域的实际问题并且给出漂亮的解决办法。每当人们应用数学工具解决一个语言问题时，总会感叹
数学之美。我们希望利用 Google 中文黑板报这块园地，介绍一些数学工具，以及我们是如何
利用这些工具来开发 Google 产品的。
系列一： 统计语言模型 (Statistical Language Models)
Google 的使命是整合全球的信息，所以我们一直致力于研究如何让机器对信息、语言做最好的
理解和处理。长期以来，人类一直梦想着能让机器代替人来翻译语言、识别语音、认识文字（不
论是印刷体或手写体）和进行海量文献的自动检索，这就需要让机器理解语言。但是人类的语言
可以说是信息里最复杂最动态的一部分。为了解决这个问题，人们容易想到的办法就是让机器模
拟人类进行学习 - 学习人类的语法、分析语句等等。尤其是在乔姆斯基（Noam Chomsky 有
史以来最伟大的语言学家）提出 。统计语言模型就是在那个时候提出的。
给大家举个例子：在很多涉及到自然语言处理的领域，如机器翻译、语音识别、印刷体或手写体
识别、拼写纠错、汉字输入和文献查询中，我们都需要知道一个文字序列是否能构成一个大家能
理解的句子，显示给使用者。对这个问题，我们可以用一个简单的统计模型来解决这个问题。
如果 S 表示一连串特定顺序排列的词 w1， w2，?， wn ，换句话说，S 可以表示某一个
由一连串特定顺序排练的词而组成的一个有意义的句子。现在，机器对语言的识别从某种角度来
说，就是想知道 S 在文本中出现的可能性，也就是数学上所说的 S 的概率用 P(S) 来表示。利
用条件概率的公式，S 这个序列出现的概率等于每一个词出现的概率相乘，于是 P(S) 可展开
为：
P(S) = P(w1)P(w2|w1)P(w3| w1 w2)?P(wn|w1 w2?wn-1)
其中 P (w1) 表示第一个词 w1 出现的概率；P (w2|w1) 是在已知第一个词的前提下，第二
个词出现的概率；以次类推。不难看出，到了词 wn，它的出现概率取决于它前面所有词。从计
算上来看，各种可能性太多，无法实现。因此我们假定任意一个词 wi 的出现概率只同它前面的
词 wi-1 有关(即马尔可夫假设），于是问题就变得很简单了。现在，S 出现的概率就变为：
P(S) = P(w1)P(w2|w1)P(w3|w2)?P(wi|wi-1)?
(当然，也可以假设一个词又前面 N-1 个词决定，模型稍微复杂些。）
接下来的问题就是如何估计 P (wi|wi-1)。现在有了大量机读文本后，这个问题变得很简单，
只要数一数这对词（wi-1,wi) 在统计的文本中出现了多少次，以及 wi-1 本身在同样的文本中
前后相邻出现了多少次，然后用两个数一除就可以了,P(wi|wi-1) = P(wi-1,wi)/ P (wi-1)。
也许很多人不相信用这么简单的数学模型能解决复杂的语音识别、机器翻译等问题。其实不光是
常人，就连很多语言学家都曾质疑过这种方法的有效性，但事实证明，统计语言模型比任何已知
的借助某种规则的解决方法都有效。比如在 Google 的中英文自动翻译中，用的最重要的就是
这个统计语言模型。去年美国标准局(NIST) 对所有的机器翻译系统进行了评测，Google 的系
统是不仅是全世界最好的，而且高出所有基于规则的系统很多。
现在，读者也许已经能感受到数学的美妙之处了，它把一些复杂的问题变得如此的简单。当然，
真正实现一个好的统计语言模型还有许多细节问题需要解决。贾里尼克和他的同事的贡献在于提
出了统计语言模型，而且很漂亮地解决了所有的细节问题。十几年后，李开复用统计语言模型把
997 词语音识别的问题简化
成了一个 20 词的识别问题，实现了有史以来第一次大词汇量非特
定人连续语音的识别。
我是一名科学研究人员 ，我在工作中经常惊叹于数学语言应用于解决实际问题上时的神奇。我
也希望把这种神奇讲解给大家听。当然，归根结底，不管什莫样的科学方法、无论多莫奇妙的解
决手段都是为人服务的。我希望 Google 多努力一分，用户就多一分搜索的喜悦。
数学之美 系列二 ‐‐ 谈谈中文分词
2006 年 4 月 10 日 上午 08:10:00
发表者: 吴军， Google 研究员
谈谈中文分词
----- 统计语言模型在中文处理中的一个应用
上回我们谈到利用统计语言模型进行语言处理，由于模型是建立在词的基础上的，对于中日韩等
语言，首先需要进行分词。例如把句子 ，那么 （P 表示概
率）：
P (A1, A2, A3, ..., Ak） 〉 P (B1, B2, B3, ..., Bm), 并且
P (A1, A2, A3, ..., Ak） 〉 P(C1, C2, C3, ..., Cn)
因此，只要我们利用上回提到的统计语言模型计算出每种分词后句子出现的概率，并找出其中概
率最大的，我们就能够找到最好的分词方法。
当然，这里面有一个实现的技巧。如果我们穷举所有可能的分词方法并计算出每种可能性下句子
的概率，那么计算量是相当大的。因此，我们可以把它看成是一个动态规划（Dynamic
Programming) 的问题，并利用 &id=980775
数学之美 系列三 ‐‐ 隐含马尔可夫模型在
语言处理中的应用
2006 年 4 月 17 日 上午 08:01:00
发表者：吴军，Google 研究员
前言：隐含马尔可夫模型是一个数学模型，到目前为之，它一直被认为是实现快速精确的语音识
别系统的最成功的方法。复杂的语音识别问题通过隐含马尔可夫模型能非常简单地被表述、解决，
让我不由由衷地感叹数学模型之妙。
自然语言是人类交流信息的工具。很多自然语言处理问题都可以等同于通信系统中的解码问题
-- 一个人根据接收到的信息，去猜测发话人要表达的意思。这其实就象通信中，我们根据接收
端收到的信号去分析、理解、还原发送端传送过来的信息。以下该图就表示了一个典型的通信系
统：
其中 s1，s2，s3...表示信息源发出的信号。o1, o2, o3 ... 是接受器接收到的信号。通信中
的解码就是根据接收到的信号 o1, o2, o3 ...还原出发送的信号 s1，s2，s3...。
其实我们平时在说话时，脑子就是一个信息源。我们的喉咙（声带），空气，就是如电线和光缆
般的信道。听众耳朵的就是接收端，而听到的声音就是传送过来的信号。根据声学信号来推测说
话者的意思，就是语音识别。这样说来，如果接收端是一台计算机而不是人的话，那么计算机要
做的就是语音的自动识别。同样，在计算机中，如果我们要根据接收到的英语信息，推测说话者
的汉语意思，就是机器翻译； 如果我们要根据带有拼写错误的语句推测说话者想表达的正确意
思，那就是自动纠错。
那么怎么根据接收到的信息来推测说话者想表达的意思呢？我们可以利用叫做许会问，你现在是不是把问题变得更复杂了，因为公式越写越长了。别着急，
我们现在就来简化这个问题。）我们在这里做两个假设：
第一，s1,s2,s3,... 是一个马尔可夫链，也就是说，si 只由 si-1 决定 (详见系列一)；
第二， 第 i 时刻的接收信号 oi 只由发送信号 si 决定（又称为独立输出假设, 即
P(o1,o2,o3,...|s1,s2,s3....) = P(o1|s1) * P(o2|s2)*P(o3|s3)...。
那么我们就可以很容易利用算法 Viterbi 找出上面式子的最大值，进而找出要识别的句子
s1,s2,s3,...。
满足上述两个假设的模型就叫隐含马尔可夫模型。我们之所以用gle 一直以 信息量比五比特少。香农指出，它的
准确信息量应该是
= -（p1*log p1 + p2 * log p2 + ．．． ＋p32 *log p32)，
其中，p1，p2 ， ．．．，p32 分别是这 32 个球队夺冠的概率。香农把它称为页自动下载。］
世界上不可能有比二进制更简单的计数方法了，也不可能有比布尔运算更简单的运算了。尽管今
天每个搜索引擎都宣称自己如何聪明、多么智能化，其实从根本上讲都没有逃出布尔运算的框框。
布尔（George Boole) 是十九世纪英国一位小学数学老师。他生前没有人认为他是数学家。布
尔在工作之余，喜欢阅读数学论著、思考数学问题。1854 年询语句器中。每当接受一个查询
时，这个查询就被分送到许许多多服务器中，这些服务器同时并行处理用户请求，并把结果送到
主服务器进行合并处理，最后将结果返回给用户。
不管索引如何复杂，查找的基本操作仍然是布尔运算。布尔运算把逻辑和数学联系起来了。它的
最大好处是容易实现，速度快，这对于海量的信息查找是至关重要的。它的不足是只能给出是与
否的判断，而不能给出量化的度量。因此，所有搜索引擎在内部检索完毕后，都要对符合要求的
网页根据相关性排序，然后才返回给用户。
数 学 之 美 系 列 六 ‐‐ 图 论 和 网 络 爬 虫
(Web Crawlers)
2006 年 5 月 15 日 上午 07:15:00
发表者: 吴军，Google 研究员
[离散数学是当代数学的一个重要分支，也是计算机科学的数学基础。它包括数理逻辑、集合论、
图论和近世代数四个分支。数理逻辑基于布尔运算，我们已经介绍过了。这里我们介绍图论和互
联网自动下载工具网络爬虫 (Web Crawlers) 之间的关系。顺便提一句，我们用 Google
Trends 来搜索一下可能广地访问每个节点所直接连接的其他节点。另外还
有一种策略是从北京出发，随便找到下一个要访问的城市，比如是济南，然后从济南出发到下一
个城市，比如说南京，再访问从南京出发的城市，一直走到头。然后再往回找，看看中间是否有
尚未访问的城市。这种方法叫务，就是网络设计和程序设计的艺术了。
数学之美 系列七 ‐‐ 信息论在信息处理中
的应用
2006 年 5 月 25 日 上午 07:56:00
发表者：吴军, Google 研究员
我们已经介绍了信息熵，它是信息论的基础，我们这次谈谈信息论在自然语言处理中的应用。
先看看信息熵和语言模型的关系。我们在系列一中谈到语言模型时，没有讲如何定量地衡量一个
语言模型的好坏，当然，读者会很自然地想到，既然语言模型能减少语音识别和机器翻译的错误，
那么就拿一个语音识别系统或者机器翻译软件来试试，好的语言模型必然导致错误率较低。这种
想法是对的，而且今天的语音识别和机器翻译也是这么做的。但这种测试方法对于研发语言模型
的人来讲，既不直接、又不方便，而且很难从错误率反过来定量度量语言模型。事实上，在贾里
尼克(Fred Jelinek)的人研究语言模型时，世界上既没有像样的语音识别系统，更没有机器翻译。
我们知道，语言模型是为了用上下文预测当前的文字，模型越好，预测得越准，那么当前文字的
不确定性就越小。
信息熵正是对不确定性的衡量，因此信息熵可以直接用于衡量统计语言模型的好坏。贾里尼克从
信息熵出发，定义了一个称为语言模型复杂度(Perplexity)的概念，直接衡量语言模型的好坏。
一个模型的复杂度越小，模型越好。李开复博士在介绍他发明的 Sphinx 语音识别系统时谈到，
如果不用任何语言模型（即零元语言模型）时，复杂度为 997，也就是说句子中每个位置有 997
个可能的单词可以填入。如果（二元）语言模型只考虑前后词的搭配不考虑搭配的概率时，复杂
度为 60。虽然它比不用语言模型好很多，但是和考虑了搭配概率的二元语言模型相比要差很多，
因为后者的复杂度只有 20。
信息论中仅次于熵的另外两个重要的概念是这个词呢？人们很容易想到要用语法、要分析语句等等。其实，至今为止，没有一种
语法能很好解决这个问题，真正实用的方法是使用互信息。具体的解决办法大致如下：首先从大
量文本中找出和总统布什一起出现的互信息最大的一些词，比如总统、美国、国会、华盛顿等等，
当然，再用同样的方法找出和灌木丛一起出现的互信息最大的词，比如土壤、植物、野生等等。
有了这两组词，在翻译 Bush 时，看看上下文中哪类相关的词多就可以了。这种方法最初是由
吉尔(Gale)，丘奇(Church)和雅让斯基(Yarowsky)提出的。
当时雅让斯基在宾西法尼亚大学是自然语言处理大师马库斯 (Mitch Marcus) 教授的博士生，
他很多时间泡在贝尔实验室丘奇等人的研究室里。也许是急于毕业，他在吉尔等人的帮助下想出
了一个最快也是最好地解决翻译中的二义性，就是上述的方法，这个看上去简单的方法效果好得
让同行们大吃一惊。雅让斯基因而只花了三年就从马库斯那里拿到了博士，而他的师兄弟们平均
要花六年时间。
信息论中另外一个重要的概念是经历的，要么是他亲口对我讲的。
弗莱德里克.贾里尼克(Fred Jelinek)出生于捷克一个富有的犹太家庭。他的父母原本打算送他
去英国的公学（私立学校）读书。为了教他德语，还专门请的一位德国的家庭女教师，但是第二
次世界大战完全打碎了他们的梦想。他们先是被从家中赶了出去，流浪到布拉格。他的父亲死在
了集中营，弗莱德自己成天在街上玩耍，完全荒废了学业。二战后，当他再度回到学校时，他的
成绩一塌糊涂， 全部是 D，但是很快他就赶上了班上的同学。不过，他在小学时从来没有得过
A。1949 年，他的母亲带领全家移民美国。在美国，贾里尼克一家生活非常贫困，全家基本是
靠母亲做点心卖钱为生，弗莱德自己十四五岁就进工厂打工补助全家。
贾里尼克最初想成为一个律师，为他父亲那样的冤屈者辩护，但他很快意识到他那浓厚的外国口
音将使他在法庭上的辩护很吃力。贾里尼克的第二个理想是成为医生，他想进哈佛大学医学院，
但经济上他无法承担医学院 8 年高昂的学费。与此同时麻省理工学院给于了他一份（为东欧移
民设的）全额奖学金。贾里尼克决定到麻省理工学电机工程。在那里，他遇到了信息论的鼻祖香
农博士，和语言学大师贾格布森 Roman Jakobson (他提出了著名的通信六功能）[注释一]，
后来贾里尼克又陪着太太听最伟大的语言学家乔姆斯基(Noam Chomsky)的课。这三位大师对
贾里尼克今后的研究方向--利用信息论解决语言问题产生的重要影响。
贾里尼克从麻省理工获得博士学位后，在哈佛大学教了一年书，然后到康乃尔大学任教。他之所
以选择康乃尔大学，是因为找工作时和那里的一位语言学家谈得颇为投机。当时那位教授表示愿
意和贾里尼克在利用信息论解决语言问题上合作。但是，等贾里尼克到康乃尔以后，那位教授表
示对语言学在没有兴趣而转向写歌剧了。贾里尼克对语言学家的坏印象从此开始。加上后来他在
IBM 时发现语言学家们嘴上头头是道，干起活来高不成低不就，对语言学家从此深恶痛绝。他
甚至说：建了阵容空前绝后强大的研究队伍，其中包括他的著名搭档波尔（Bahl），著名的语
音识别 Dragon 公司的创始人贝克夫妇，解决最大熵迭代算法的达拉皮垂(Della Pietra)孪生
兄弟，BCJR 算法的另外两个共同提出者库克(Cocke)和拉维夫(Raviv)，以及第一个提出机器
翻译统计模型的布朗。
七十年代的 IBM 有点像九十年代的微软和今天的 Google, 给于杰出科学家作任何有兴趣研
究的自由。在那种宽松的环境里，贾里尼克等人提出了统计语音识别的框架结构。 在贾里尼克
以前，科学家们把语音识别问题当作人工智能问题和模式匹配问题。而贾里尼克把它当成通信问
题，并用两个隐含马尔可夫模型（声学模型和语言模型）把语音识别概括得清清楚楚。这个框架
结构对至今的语音和语言处理有着深远的影响，它从根本上使得语音识别有实用的可能。 贾里
尼克本人后来也因此当选美国工程院院士。
贾里尼克和波尔，库克以及拉维夫对人类的另一大贡献是 BCJR 算法，这是今天数字通信中应
用的最广的两个算法之一（另一个是维特比算法）。有趣的是，这个算法发明了二十年后，才得
以广泛应用。IBM 于是把它列为了 IBM 有史以来对人类最大贡献之一，并贴在加州 Amaden
实现室墙上。遗憾的是 BCJR 四个人已经全部离开 IBM，有一次 IBM 的通信部门需要用这个
算法，还得从斯坦福大学请一位专家去讲解，这位专家看到 IBM 橱窗里的成就榜，感慨万分。
贾里尼克和 IBM 一批最杰出的科学家在九十年代初离开了 IBM，他们大多数在华尔街取得了
巨大的成功。贾里尼克的书生气很浓，于是去约翰霍普金斯大学建立了世界著名的 CLSP 实验
室。每年夏天，贾里尼克邀请世界上 20-30 名顶级的科学家和学生到 CLSP 一起工作，使得
CLSP 成为世界上语音和语言处理的中心之一。
贾里尼克治学极为严谨，对学生要求也极严。他淘汰学生的比例极高，即使留下来的，毕业时间
也极长。但是，另一方面，贾里尼克也千方百计利用自己的影响力为学生的学习和事业创造方便。
贾里尼克为组里的每一位学生提供从进组第一天到离开组最后一天全部的学费和生活费。他还为
每一位学生联系实习机会，并保证每位学生在博士生阶段至少在大公司实习一次。从他那里拿到
博士学位的学生，全部任职于著名实验室，比如 IBM, 微软，AT&T 和 Google 的实验室。为
了提高外国人的英语水平，贾里尼克用自己的经费为他们请私人英语教师。
贾里尼克生活俭朴，一辆老式丰田车开了二十多年，比组里学生的车都破。他每年都邀请组里的
学生
和教授到家里做客，很多毕业了的学生也专程赶来聚会。在那里，他不再谈论学术问题，而
会谈些巩俐的电影（他太太是哥伦比亚大学电影专业的教授），或是某著名教授被拉斯韦加斯的
赌馆定为不受欢迎的人等等。但是他聚会的食物实在难吃，无非是些生胡萝卜和芹菜。后来贾里
尼克掏钱让系里另一个教授承办聚会，那个教授每次请专业大厨在家作出极丰盛的晚宴，并准备
许多美酒，从此这种聚会就转移到那个教授家了。
除了巩俐的电影，贾里尼克对中国的了解就是清华大学和青岛啤酒了。他有时会把两个名字搞混，
有两次被香港科技大学的 Pascale 冯教授抓住。
贾里尼克说话心直口快，不留余地。在他面前谈论学术一定要十分严谨，否则很容易被他抓住辫
子。除了刚才提到的对语言学家略有偏见的评论，他对许多世界级的大师都有过很多ncy)，比如，在某个
一共有一千词的网页中单求和变成了加权求和，即 TF1*IDF1 +
TF2*IDF2 ＋... + TFN*IDFN。在上面的例子中，该网页和些状态（节点）和连接
这些状态的有向弧。下图是一个识别中国地址的有限状态机的简单的例子。
每一个有限状态机都有一个启始状态和一个终止状态和若干中间状态。每一条弧上带有从一个状
态进入下一个状态的条件。比如，在上图中，当前的状态是编程工具的
好传统，他们三人也把自己多年的心血拿出来和同行们共享。可惜好景不长，AT&T 实验室风
光不再，这三个人都离开了 AT&T，莫瑞成了纽约大学的教授，皮瑞尔当了宾西法尼亚大学计
算机系系主任，而瑞利成了 Google 的研究员，AT&T 实验室的新东家不再免费提供有限状态
机 C 语言工具库。虽然此前莫瑞等人公布了他们的详细算法，但是省略了实现的细节。因此在
学术界，不少科学家能够重写同样功能的工具库，但是很难达到 AT&T 工具库的效率（即运算
速度），这的确是一件令人遗憾的事。
数学之美 系列十一 ‐ Google 阿卡 47 的
制造者阿米特.辛格博士
2006 年 7 月 10 日 上午 09:52:00
发表者：Google 研究员，吴军
枪迷或者看过尼古拉斯.凯奇（Nicolas Cage)主演的电影方法的有效性。不少人试图用精确而复杂的办法对辛格的设计的各
种计算出它们的单
文本词汇频率/逆文本频率值（TF/IDF)。不难想象，和新闻主题有关的那些实词频率高，TF/IDF
值很大。我们按照这些实词在词汇表的位置对它们的 TF/IDF 值排序。比如，词汇表有六万四
千个词，分别为
单词编号 汉字词
------------------
1 阿
2 啊
3 阿斗
4 阿姨
...
789 服装
....
64000 做作
在一篇新闻中，这 64,000 个词的 TF/IDF 值分别为
单词编号 TF/IDF 值
==============
1 0
2 0.0034
3 0
4 0.00052
5 0
...
789 0.034
...
64000 0.075
如果单词表中的某个次在新闻中没有出现，对应的值为零，那么这 64,000 个数，组成一个
64,000 维的向量。我们就用这个向量来代表这篇新闻，并成为新闻的特征向量。如果两篇新闻
的特征向量相近，则对应的新闻内容相似，它们应当归在一类，反之亦然。
学过向量代数的人都知道，向量实际上是多维空间中有方向的线段。如果两个向量的方向一致，
即夹角接近零，那么这两个向量就相近。而要确定两个向量方向是否一致，这就要用到余弦定理
计算向量的夹角了。
余弦定理对我们每个人都不陌生，它描述了三角形中任何一个夹角和三个边的关系，换句话说，
给定三角形的三条边，我们可以用余弦定理求出三角形各个角的角度。假定三角形的三条边为 a,
b 和 c，对应的三个角为 A, B 和 C，那么角 A 的余弦 --
如果我们将三角形的两边 b 和 c 看成是两个向量，那么上述公式等价于
其中分母表示两个向量 b 和 c 的长度，分子表示两个向量的内积。举一个具体的例子，假如
新闻 X 和新闻 Y 对应向量分别是
x1,x2,...,x64000 和
y1,y2,...,y64000,
那么它们夹角的余弦等于，
当两条新闻向量夹角的余弦等于一时，这两条新闻完全重复（用这个办法可以删除重复的网页）；
当夹角的余弦接近于一时，两条新闻相似，从而可以归成一类；夹角的余弦越小，两条新闻越不
相关。
我们在中学学习余弦定理时，恐怕很难想象它可以用来对新闻进行分类。在这里，我们再一次看
到数学工具的用途。
数学之美 系列十三 信息指纹及其应用
2006 年 8 月 3 日 上午 11:17:00
发表者：吴军，Google 研究员
任何一段信息文字，都可以对应一个不太长的随机数，作为区别它和其它信息的指纹
（Fingerprint)。只要算法设计的好，任何两段信息的指纹都很难重复，就如同人类的指纹一样。
信息指纹在加密、信息压缩和处理中有着广泛的应用。
我们在图论和网络爬虫一文中提到，为了防止重复下载同一个网页，我们需要在哈希表中纪录已
经访问过的网址（URL)。但是
在哈希表中以字符串的形式直接存储网址，既费内存空间，又浪
费查找时间。现在的网址一般都较长，比如，如果在 Google 或者百度在查找数学之美，对应
的网址长度在一百个字符以上。下面是百度的链接
http://www.baidu.com/s?ie=gb2312&bs=%CA%FD%D1%A7%D6%AE%C3%C0&
sr=&z=&cl=3&f=8
&wd=%CE%E2%BE%FC+%CA%FD%D1%A7%D6%AE%C3%C0&ct=0
假定网址的平均长度为一百个字符，那么存贮 200 亿个网址本身至少需要 2 TB，即两千 GB
的容量，考虑到哈希表的存储效率一般只有 50%，实际需要的内存在 4 TB 以上。即使把这些
网址放到了计算机的内存中，由于网址长度不固定，以字符串的形式查找的效率会很低。因此，
我们如果能够找到一个函数，将这 200 亿个网址随机地映射到 128 二进位即 16 个字节的整
数空间，比如将上面那个很长的字符串对应成一个如下的随机数:
[***********][1**********]3
这样每个网址只需要占用 16 个字节而不是原来的一百个。这就能把存储网址的内存需求量降
低到原来的 1/6。这个 16 个字节的随机数，就称做该网址的信息指纹（Fingerprint)。可以
证明，只要产生随机数的算法足够好，可以保证几乎不可能有两个字符串的指纹相同，就如同不
可能有两个人的指纹相同一样。由于指纹是固定的 128 位整数，因此查找的计算量比字符串比
较小得多。网络爬虫在下载网页时，它将访问过的网页的网址都变成一个个信息指纹，存到哈希
表中，每当遇到一个新网址时，计算机就计算出它的指纹，然后比较该指纹是否已经在哈希表中，
来决定是否下载这个网页。这种整数的查找比原来字符串查找,可以快几倍到几十倍。
产生信息指纹的关键算法是伪随机数产生器算法（prng)。最早的 prng 算法是由计算机之父
冯诺伊曼提出来的。他的办法非常简单，就是将一个数的平方掐头去尾，取中间的几位数。比如
一个四位的二进制数 1001（相当于十进制的 9），其平方为 01010001 (十进制的 81）掐
头去尾剩下中间的四位 0100。当然这种方法产生的数字并不很随机，也就是说两个不同信息
很有可能有同一指纹。现在常用的 MersenneTwister 算法要好得多。
信息指纹的用途远不止网址的消重，信息指纹的的孪生兄弟是密码。信息指纹的一个特征是其不
可逆性, 也就是说,
无法根据信息指纹推出原有信息，这种性质， 正是网络加密传输所需要的。比如说，一个网站
可以根据用户的 Cookie 识别不同用户，这个 cookie 就是信息指纹。但是网站无法根据信息
指纹了解用户的身份，这样就可以保护用户的隐私。在互联网上，加密的可靠性，取决于
是否很
难人为地找到拥有同一指纹的信息， 比如一个黑客是否能随意产生用户的 cookie。从加密的
角度讲 MersenneTwister，算法并不好，因为它产生的随机数有相关性。
互联网上加密要用基于加密伪随机数产生器（csprng)。常用的算法有 MD5 或者 SHA1 等标
准，它们可以将不定长的信息变成定长的 128 二进位或者 160 二进位随机数。值得一提的事，
SHA1 以前被认为是没有漏洞的，现在已经被中国的王小云教授证明存在漏洞。但是大家不必
恐慌， 因为这和黑客能真正攻破你的注册信息是还两回事。
信息指纹的虽然历史很悠久，但真正的广泛应用是在有了互联网以后，这几年才渐渐热门起来。
数学之美 系列十四 谈谈数学模型的重要
性
2006 年 8 月 9 日 上午 09:12:00
发表者：吴军，Google 研究员
[注：一直关注数学之美系列的读者可能已经发现，我们对任何问题总是在找相应的准确的数学
模型。为了说明模型的重要性，今年七月份我在 Google 中国内部讲课时用了整整一堂课来讲
这个问题，下面的内容是我讲座的摘要。］
在包括哥白尼、伽利略和牛顿在内的所有天文学家中，我最佩服的是地心说的提出者托勒密。虽
然天文学起源于古埃及，并且在古巴比伦时，人们就观测到了五大行星（金、木、水、火、土）
运行的轨迹，以及行星在近日点运动比远日点快。（下图是在地球上看到的金星的轨迹，看过达
芬奇密码的读者知道金星大约每四年在天上画一个五角星。）
但是真正创立了天文学，并且计算出诸多天体运行轨迹的是两千年前古罗马时代的托勒密。虽然
今天我们可能会嘲笑托勒密犯的简单的错误，但是真正了解托勒密贡献的人都会对他肃然起敬。
托勒密发明了球坐标，定义了包括赤道和零度经线在内的经纬线，他提出了黄道，还发明了弧度
制。
当然，他最大也是最有争议的发明是地心说。虽然我们知道地球是围绕太阳运动的，但是在当时，
从人们的观测出发，很容易得到地球是宇宙中心的结论。从地球上看，行星的运动轨迹是不规则
的，托勒密的伟大之处是用四十个小圆套大圆的方法，精确地计算出了所有行星运动的轨迹。（托
勒密继承了毕达格拉斯的一些思想，他也认为圆是最完美的几何图形。）托勒密模型的精度之高，
让以后所有的科学家惊叹不已。即使今天，我们在计算机的帮助下，也很难解出四十个套在一起
的圆的方程。每每想到这里，我都由衷地佩服托勒密。一千五百年来，人们根据他的计算决定农
时。但是，经过了一千五百年，托勒密对太阳运动的累积误差
，还是差出了一星期。
地心说的示意图，我国天文学家张衡的浑天地动说其实就是地心说。
纠正地心说错误不是靠在托勒密四十个圆的模型上再多套上几个圆，而是进一步探索真理。哥白
尼发现，如果以太阳为中心来描述星体的运行，只需要 8-10 个圆，就能计算出一个行星的运
动轨迹，他提出了日心说。很遗憾的事，哥白尼正确的假设并没有得到比托勒密更好的结果，哥
白尼的模型的误差比托勒密地要大不少。这是教会和当时人们认为哥白尼的学说是邪说的一个原
因，所以日心说要想让人心服口服地接受，就得更准确地描述行星运动。
完成这一使命的是开普勒。开普勒在所有一流的天文学家中，资质较差，一生中犯了无数低级的
错误。但是他有两条别人没有的东西，从他的老师第谷手中继承的大量的、在当时最精确的观测
数据，以及运气。开普勒很幸运地发现了行星围绕太阳运转的轨道实际是椭圆形的，这样不需要
用多个小圆套大圆，而只要用一个椭圆就能将星体运动规律描述清楚了。只是开普勒的知识和水
平不足以解释为什么行星的轨道是椭圆形的。最后是伟大的科学家牛顿用万有引力解释了这个问
题。
故事到这里似乎可以结束了。但是，许多年后，又有了个小的波澜。天文学家们发现，天王星的
实际轨迹和用椭圆模型算出来的不太符合。当然，偷懒的办法是接着用小圆套大圆的方法修正，
但是一些严肃的科学家在努力寻找真正的原因。英国的亚当斯和法国的维内尔（Verrier）独立
地发现了吸引天王星偏离轨道的海王星。
讲座结束前，我和 Google 中国的工程师们一同总结了这么几个结论：
１ . 一个正确的数学模型应当在形式上是简单的。（托勒密的模型显然太复杂。）
２ . 一个正确的模型在它开始的时候可能还不如一个精雕细琢过的错误的模型来的准确，但是，
如果我们认定大方向是对的，就应该坚持下去。（日心说开始并没有地心说准确。）
３ . 大量准确的数据对研发很重要。
４ . 正确的模型也可能受噪音干扰，而显得不准确；这时我们不应该用一种凑合的修正方法来
弥补它，而是要找到噪音的根源，这也许能通往重大发现。
在网络搜索的研发中，我们在前面提到的单文本词频/逆文本频率指数（TF/IDF) 和网页排名
（page rank)都相当于是网络搜索中的单。但是，事实上，自然语言处理中也有一些
特例，比如有些学者将一个问题研究到极致，执著追求完善甚至可以说完美的程度。他们的工作
对同行有很大的参考价值，因此我们在科研中很需要这样的学者。在自然语言处理方面新一代的
顶级人物麦克尔 · 柯林斯 (Michael Collins) 就是这样的人。
柯林斯：追求完美
柯林斯从师于自然语言处理大师马库斯 (Mitch Marcus)（我们以后还会多次提到马库斯），从
宾夕法利亚大学获得博士学位，现任麻省理工学院 (MIT) 副教授（别看他是副教授，他的水平
在当今自然语言处理领域是数一数二的），在作博士期间，柯林斯写了一个后来以他名字命名的
自然语言文法分析器 (sentence parser)，可以将书面语的每一句话准确地进行文法分析。文
法分析是很多自然语言应用的基础。虽然柯林斯的师兄布莱尔 (Eric Brill) 和 Ratnaparkhi 以
及师弟 Eisnar 都完成了相当不错的语言文法分析器，但是柯林斯却将它做到了极致，使它在
相当长一段时间内成为世界上最好的文法分析器。柯林斯成功的关键在于将文法分析的每一个细
节都研究得很仔细。柯林斯用的数学模型也很漂亮，整个工作可以用完美来形容。我曾因为研究
的需要，找柯林斯要过他文法分析器的源程序，他很爽快地给了我。我试图将他的程序修改一下
来满足我特定应用的要求，但后来发现，他的程序细节太多以至于很难进一步优化。柯林斯的博
士论文堪称是自然语言处理领域的范文。它像一本优秀的小说，把所有事情的来龙去脉介绍的清
清楚楚，对于任何有一点计算机和自然语言处理知识的人，都可以轻而易举地读懂他复杂的方法。
柯林斯毕业后，在 AT&T 实验室度过了三年快乐的时光。在那里柯林斯完成了许多世界一流的
研究工作诸如隐含马尔科夫模型的区别性训练方法，卷积核在自然语言处理中的应用等等。三年
后，AT&T 停止了自然语言处理方面的研究，柯林斯幸运地在 MIT 找到了教职。在 MIT 的短
短几年间，柯林斯多次在国际会议上获得最佳论文奖。相比其他同行，这种成就是独一无二的。
柯林斯的特点就是把事情做到极致。如果说有人喜欢是基于变换规则的机器学习方法 (transformation rule based machine
learning)。这个方法名称虽然很复杂，其实非常简单。我们以拼音转换字为例来说明它：
第一步，我们把每个拼音对应的汉字中最常见的找出来作为第一遍变换的结果，当然结果有不少
错误。比如，是一个非常有意思的题目，但是把它讲清楚要用两个系列的篇幅。]
前段时间，Google 中国研究院的刘骏总监谈到在网络搜索排名中，用到的信息有上百种。更普
遍地讲，在自然语言处理中，我们常常知道各种各样的但是又不完全确定的信息，我们需要用一
个统一的模型将这些信息综合起来。如何综合得好，是一门很大的学问。
让我们看一个拼音转汉字的简单的例子。假如输入的拼音是反面一定是三点等等。（事实上，有的色子四点反面不是三点而是
一点。）这种基于直觉的猜测之所以准确，是因为它恰好符合了最大熵原理。
最大熵原理指出，当我们需要对一个随机事件的概率分布进行预测时，我们的预测应当满足全部
已知的条件，而对未知的情况不要做任何主观假设。（不做主观假设这点很重要。）在这种情况
下，概率分布最均匀，预测的风险最小。因为这时概率分布的信息熵最大，所以人们称这种模型
叫均匀分布。
2. 用第 N 次迭代的模型来估算每种信息特征在训练数据中的分布，如果超过了实际的，就把
相应的模型参数变小；否则，将它们便大。
3. 重复步骤 2 直到收敛。
GIS 最早是由 Darroch 和 Ratcliff 在七十年代提出的。但是，这两人没有能对这种算法的物
理含义进行很好地解释。后来是由数学家希萨（Csiszar)解释清楚的，因此，人们在谈到这个算
法时，总是同时引用 Darroch 和 Ratcliff 以及希萨的两篇论文。GIS 算法每次迭代的时间都
很长，需要迭代很多次才能收敛，而且不太稳定，即使在 64 位计算机上都会出现溢出。因此，
在实际应用中很少有人真正使用 GIS。大家只是通过它来了解最大熵模型的算法。
八十年代，很有天才的孪生兄弟的达拉皮垂(Della Pietra)在 IBM 对 GIS 算法进行了两方面
的改进，提出了改进迭代算法 IIS（improved iterative scaling）。这使得最大熵模型的训
练时间缩短了一到两个数量级。这样最大熵模型才有可能变得实用。即使如此，在当时也只有
IBM 有条件是用最大熵模型。
由于最大熵模型在数学上十分完美，对科学家们有很大的诱惑力，因此不少研究者试图把自己的
问题用一个类似最大熵的近似模型去套。谁知这一近似，最大熵模型就变得不完美了，结果可想
而知，比打补丁的凑合的方法也好不了多少。于是，不少热心人又放弃了这种方法。第一个在实
际信息处理应用中验证了最大熵模型的优势的，是宾夕法尼亚大学马库斯的另一个高徒原 IBM
现微软的研究员拉纳帕提(Adwait Ratnaparkhi)。拉纳帕提的聪明之处在于他没有对最大熵模
型进行近似，而是找到了几个最适合用最大熵模型、而计算量相对不太大的自然语言处理问题，
比如词性标注和句法分析。拉纳帕提成功地将上下文信息、词性（名词、动词和形容词等）、句
子成分（主谓宾）通过最大熵模型结合起来，做出了当时世界上最好的词性标识系统和句法分析
器。拉纳帕提的论文发表后让人们耳目一新。拉纳帕提的词性标注系统，至今仍然是使用单一方
法最好的系统。科学家们从拉纳帕提的成就中，又看到了用最大熵模型解决复杂的文字信息处理
的希望。
但是，最大熵模型的计算量仍然是个拦路虎。我在学校时花了很长时间考虑如何简化最大熵模型
的计算量。终于有一天，我对我的导师说，我发现一种数学变换，可以将大部分最大熵模型的训
练时间在 IIS 的基础上减少两个数量级。我在黑板上推导了一个多小时，他没有找出我的推导
中的任何破绽，接着他又回去想了两天，然后告诉我我的算法是
对的。从此，我们就建造了一些
很大的最大熵模型。这些模型比修修补补的凑合的方法好不少。即使在我找到了快速训练算法以
后，为了训练一个包含上下文信息，主题信息和语法信息的文法模型(language model)，我并
行使用了 20 台当时最快的 SUN 工作站，仍然计算了三个月。由此可见最大熵模型的复杂的
一面。最大熵模型快速算法的实现很复杂，到今天为止，世界上能有效实现这些算法的人也不到
一百人。有兴趣实现一个最大熵模型的读者可以阅读我的论文。
最大熵模型，可以说是集简与繁于一体，形式简单，实现复杂。值得一提的是，在 Google 的很
多产品中，比如机器翻译，都直接或间接地用到了最大熵模型。
讲到这里，读者也许会问，当年最早改进最大熵模型算法的达拉皮垂兄弟这些年难道没有做任何
事吗？他们在九十年代初贾里尼克离开 IBM 后，也退出了学术界，而到在金融界大显身手。他
们两人和很多 IBM 语音识别的同事一同到了一家当时还不大，但现在是世界上最成功对冲基金
(hedge fund)公司----文艺复兴技术公司 (Renaissance Technologies)。我们知道，决定股
票涨落的因素可能有几十甚至上百种，而最大熵方法恰恰能找到一个同时满足成千上万种不同条
件的模型。达拉皮垂兄弟等科学家在那里，用于最大熵模型和其他一些先进的数学工具对股票预
测，获得了巨大的成功。从该基金 1988 年创立至今，它的净回报率高达平均每年 34%。也
就是说，如果 1988 年你在该基金投入一块钱，今天你能得到 200 块钱。这个业绩，远远超
过股神巴菲特的旗舰公司伯克夏哈撒韦（Berkshire Hathaway)。同期，伯克夏哈撒韦的总回
报是 16 倍。
值得一提的是，信息处理的很多数学手段，包括隐含马尔可夫模型、子波变换、贝叶斯网络等等，
在华尔街多有直接的应用。由此可见，数学模型的作用。
数学之美 系列十七 闪光的不一定是金子
谈 谈 搜 索 引 擎 作 弊 问 题 (Search Engine
Anti‐SPAM)
2006 年 11 月 28 日 上午 03:18:00
Google 研究员 吴军
自从有了搜索引擎，就有了针对搜索引擎网页排名的作弊(SPAM)。以至于用户发现在搜索引擎
中排名靠前的网页不一定就是高质量的，用句俗话说，闪光的不一定是金子。
搜索引擎的作弊，虽然方法很多，目的只有一个，就是采用不正当手段提高自己网页的排名。早
期最常见的作弊方法是重复关键词。比如一个卖数码相机的网站，重复地罗列各种数码相机的品
牌，如尼康、佳能和柯达等等。为了不让读者看到众多讨厌的关键词，聪明一点的作弊者常用很
小
的字体和与背景相同的颜色来掩盖这些关键词。其实，这种做法很容易被搜索引擎发现并纠正。
在有了网页排名(page rank)以后，作弊者发现一个网页被引用的连接越多，排名就可能越靠前，
于是就有了专门卖链接和买链接的生意。比如，有人自己创建成百上千个网站，这些网站上没有
实质的内容，只有到他们的客户网站的连接。这种做法比重复关键词要高明得多，但是还是不太
难被发现。因为那些所谓帮别人提高排名的网站，为了维持生意需要大量地卖链接，所以很容易
露马脚。（这就如同造假钞票，当某一种假钞票的流通量相当大以后，就容易找到根源了。）再
以后，又有了形形色色的作弊方式，我们就不在这里一一赘述了。
几年前，我加入 Google 做的第一件事就是消除网络作弊。在 Google 最早发现搜索引擎作弊的
是 Matt Cutts，他在我加入 Google 前几个月开始研究这个问题，后来，辛格，马丁和我先后
加入进来。我们经过几个月的努力，清除了一半的作弊者。(当然，以后抓作弊的效率就不会有
这么高了。）其中一部分网站从此除，因为作弊者的方法不可能是随机的（否则就无法提高排
名了）。而且，作弊者也不可能是一天换一种方法，即作弊方法是时间相关的。因此，搞搜索引
擎排名算法的人，可以在搜集一段时间的作弊信息后，将作弊者抓出来，还原原有的排名。当然
这个过程需要时间，就如同采集汽车发动机噪音需要时间一样，在这段时间内，作弊者可能会尝
到些甜头。因此，有些人看到自己的网站经过所谓的优化（其实是作弊），排名在短期内靠前了，
以为这种所谓的优化是有效的。但是，不久就会发现排名掉下去了很多。这倒不是搜索引擎以前
宽容，现在严厉了，而是说明抓作弊需要一定的时间，以前只是还没有检测到这些作弊的网站而
已。
还要强调一点，Google 抓作弊和恢复网站原有排名的过程完全是自动的(并没有个人的好恶），
就如同手机消除噪音是自动的一样。一个网站要想长期排名靠前，就需要把内容做好，同时要和
那些作弊网站划清界限。
数学之美 系列十八 － 矩阵运算和文本处
理中的分类问题
2007 年 1 月 1 日 下午 03:10:00
发表者：Google 研究员，吴军
我在大学学习线性代数时，实在想不出它除了告诉我们如何解线性方程外，还能有什么别的用途。
关于矩阵的许多概念，比如特征值等等，更是脱离日常生活。后来在数值分析中又学了很多矩阵
的近似算法，还是看不到可以应用的地方。当时选这些课，完全是为了混学分的学位。我想，很
多同学都多多少少有过类似的经历。直到后来长期做自然语言处理的研究，我才发现数学家们提
出那些矩阵的概念和算法，是有实际应用的意义的。
在自然语言处理中，最常见的两类的分类问题分别是，将文本按主题归类（比如将所有介绍亚运
会的新闻归到体育类）和将词汇表中的字词按意思归类（比如将各种体育运动的名称个归成一类）。
这两种分类问题都可用通过矩阵运算来圆满地、同时解决。为了说明如何用矩阵这个工具类解决
这两个问题的，让我们先来来回顾一下我们在余弦定理和新闻分类中介绍的方法。
分类的关键是计算相关性。我们首先对两个文本计算出它们的内容词，或者说实词的向量，然后
求这两个向量的夹角。当这两个向量夹角为零时，新闻就相关；当它们垂直或者说正交时，新闻
则无关。当然，夹角的余弦等同于向量的内积。从理论上讲，这种算法非常好。但是计算时间特
别长。通常，我们要处理的文章的数量都很大，至少在百万篇以上，二次回标有非常长，比如说
有五十万个词（包括人名地名产品名称等等
）。如果想通过对一百万篇文章两篇两篇地成对比较，
来找出所有共同主题的文章，就要比较五千亿对文章。现在的计算机一秒钟最多可以比较一千对
文章，完成这一百万篇文章相关性比较就需要十五年时间。注意，要真正完成文章的分类还要反
复重复上述计算。
在文本分类中，另一种办法是利用矩阵运算中的奇异值分解（Singular Value Decomposition，
简称 SVD)。现在让我们来看看奇异值分解是怎么回事。首先，我们可以用一个大矩阵 A 来描
述这一百万篇文章和五十万词的关联性。这个矩阵中，每一行对应一篇文章，每一列对应一个词。
在上面的图中，M=1,000,000，N=500,000。第 i 行，第 j 列的元素，是字典中第 j 个词
在第 i 篇文章中出现的加权词频（比如，TF/IDF)。读者可能已经注意到了，这个矩阵非常大，
有一百万乘以五十万，即五千亿个元素。
奇异值分解就是把上面这样一个大矩阵，分解成三个小矩阵相乘，如下图所示。比如把上面的例
子中的矩阵分解成一个一百万乘以一百的矩阵 X，一个一百乘以一百的矩阵 B，和一个一百乘以
五十万的矩阵 Y。这三个矩阵的元素总数加起来也不过 1.5 亿，仅仅是原来的三千分之一。相应
的存储量和计算量都会小三个数量级以上。
三个矩阵有非常清楚的物理含义。第一个矩阵 X 中的每一行表示意思相关的一类词，其中的每
个非零元素表示这类词中每个词的重要性（或者说相关性），数值越大越相关。最后一个矩阵 Y
中的每一列表示同一主题一类文章，其中每个元素表示这类文章中每篇文章的相关性。中间的矩
阵则表示类词和文章雷之间的相关性。因此，我们只要对关联矩阵 A 进行一次奇异值分解，w 我
们就可以同时完成了近义词分类和文章的分类。（同时得到每类文章和每类词的相关性）。
现在剩下的唯一问题，就是如何用计算机进行奇异值分解。这时，线性代数中的许多概念，比如
矩阵的特征值等等，以及数值分析的各种算法就统统用上了。在很长时间内，奇异值分解都无法
并行处理。（虽然 Google 早就有了 MapReduce 等并行计算的工具，但是由于奇异值分解很
难拆成不相关子运算，即使在 Google 内部以前也无法利用并行计算的优势来分解矩阵。）最
近，Google 中国的张智威博士和几个中国的工程师及实习生已经实现了奇异值分解的并行算法，
我认为这是 Google 中国对世界的一个贡献。
数学之美 系列十九 － 马尔可夫链的扩展
贝叶斯网络 (Bayesian Networks)
2007 年 1 月 28 日 下午 09:53:00
发表者：Google 研究员，吴军
我们在前面的
系列中多次提到马尔可夫链 (Markov
Chain)，它描述了一种状态序列，其每个状态值取决于前面有限个状态。这种模型，对很多实
际问题来讲是一种很粗略的简化。在现实生活中，很多事物相互的关系并不能用一条链来串起来。
它们之间的关系可能是交叉的、错综复杂的。比如在下图中可以看到，心血管疾病和它的成因之
间的关系是错综复杂的。显然无法用一个链来表示。
我们可以把上述的有向图看成一个网络，它就是贝叶斯网络。其中每个圆圈表示一个状态。状态
之间的连线表示它们的因果关系。比如从心血管疾病出发到吸烟的弧线表示心血管疾病可能和吸
烟有关。当然，这些关系可以有一个量化的可信度 (belief)，用一个概率描述。我们可以通过
这样一张网络估计出一个人的心血管疾病的可能性。在网络中每个节点概率的计算，可以用贝叶
斯公式来进行，贝叶斯网络因此而得名。由于网络的每个弧有一个可信度，贝叶斯网络也被称作
信念网络 (belief networks)。
和马尔可夫链类似，贝叶斯网络中的每个状态值取决于前面有限个状态。不同的是，贝叶斯网络
比马尔可夫链灵活，它不受马尔可夫链的链状结构的约束，因此可以更准确地描述事件之间的相
关性。可以讲，马尔可夫链是贝叶斯网络的特例，而贝叶斯网络是马尔可夫链的推广。
使用贝叶斯网络必须知道各个状态之间相关的概率。得到这些参数的过程叫做训练。和训练马尔
可夫模型一样，训练贝叶斯网络要用一些已知的数据。比如在训练上面的网络，需要知道一些心
血管疾病和吸烟、家族病史等有关的情况。相比马尔可夫链，贝叶斯网络的训练比较复杂，从理
论上讲，它是一个 NP-complete 问题，也就是说，对于现在的计算机是不可计算的。但是，
对于某些应用，这个训练过程可以简化，并在计算上实现。
值得一提的是 IBM Watson 研究所的茨威格博士 (Geoffrey Zweig) 和西雅图华盛顿大学的
比尔默 (Jeff Bilmes) 教授完成了一个通用的贝叶斯网络的工具包，提供给对贝叶斯网络有兴
趣的研究者。
贝叶斯网络在图像处理、文字处理、支持决策等方面有很多应用。在文字处理方面，语义相近的
词之间的关系可以用一个贝叶斯网络来描述。我们利用贝叶斯网络，可以找出近义词和相关的词，
在 Google 搜索和 Google 广告中都有直接的应用。
数学之美 系列二十 －自然语言处理的教
父 马库斯
2007 年 4 月 13 日 下午 07:03:00
发表者：Google 研究员，吴军
我们在前面的系列中介绍和提到了一些年轻有为的科学家，迈克尔·柯林斯，艾里克·
布莱尔，大
卫·雅让斯基，拉纳帕提等等，他们都出自宾夕法尼亚计算机系米奇·马库斯(Mitch Marcus)名
下。就像许多武侠小说中描写的，弟子都成了各派的掌门，师傅一定了不得。的确，马库斯虽然
作为第一作者发表的论文并不多，但是从很多角度上讲，他可以说是自然语言处理领域的教父。
马库斯教授长期当任宾夕法尼亚大学计算机系主任，直到他在几年前从 AT&T 找到皮耶尔替代
他为止。作为一个管理者，马库斯显示出在自然处理和计算机科学方面的卓识的远见。在指导博
士生时，马库斯发现语料库在自然语言处理中的重要性。马库斯呕心沥血，花了十几年工夫建立
了一系列标准的语料库，提供给全世界的学者使用。这套被称为 LDC 的语料库，是当今全世界
自然语言处理的所有学者都使用的工具。我们在以前的系列中讲到，当今的自然语言处理几乎都
是使用给予统计的方法。要做统计，就需要大量有代表性的数据。利用这些数据开发一个自然语
言处理系统的过程，可以统称为训练。比如，我们要训练一个汉语分词系统，我们需要一些已经
分好词的中文句子。当然这些句子需要有代表性。如果想知道一个分词系统的准确性，我们也需
要一些人工分好词的句子进行测试。这些人工处理好的文字数据库，成为语料库(corpus)。如
果每个研究室都人工建立几个语料库，不仅浪费时间精力，而且发表文章时，数据没有可比性。
因此，马库斯想到了建立一系列标准的语料库为全世界的学者用。他利用自己的影响力让美国自
然科学基金会和 DARPA 出钱立项，联络的多所大学和研究机构，建立的数百个标准的语料库。
其中最著名的是 PennTree
Bank 的语料库。PennTree Bank 覆盖多种语言（包括中文）。每一种语言，它有几十万到
几百万字的有代表性的句子，每个句子都有的词性标注，语法分析树等等。LDC 语料库如今已
成为全世界自然语言处理科学家共用的数据库。如今，在自然语言处理方面发表论文，几乎都要
提供基于 LDC 语料库的测试结果。
马库斯给予他的博士生研究自己感兴趣的课题的自由，这是他之所以桃李满天下的原因。马库斯
对几乎所有的自然语言处理领域有独到的见解。和许多教授让博士生去做他拿到基金的项目，马
库斯让博士生提出自己有兴趣的课题，或者用他已有的经费支持学生，或者为他们的项目区申请
经费。马库斯高屋建瓴，能够很快的判断一个研究方向是否正确，省去了博士生很多
try-and-error 的时间。因此他的学生有些很快地拿到的博士学位。
作为系主任，马库斯在专
业设置方面显示出卓识的远见。我有幸和他在同一个校务顾问委员会任
职，一起讨论计算机系的研究方向。马库斯在几年前互联网很热门、很多大学开始互联网研究时，
看到 bioinformatics (生物信息学）的重要性，在宾夕法利亚大学设置这个专业，并且在其他
大学还没有意识到时，开始招聘这方面的教授。马库斯还建议一些相关领域的教授，包括后来的
系主任皮耶尔把一部分精力转到生物信息学方面。马库斯同时向他担任顾问的其他一些大学提出
同样的建议。等到网络泡沫破裂以后，很多大学的计算机系开始向生物信息学转向，但是发现已
经很难找到这些方面好的教授了。我觉得，当今中国的大学，最需要的就是马库斯这样卓有远见
的管理者。
过几天我又要和马库斯一起开顾问委员会的会议了，不知道这次他对计算机科学的发展有什么见
解。
数学之美 系列二十一 － 布隆过滤器
（Bloom Filter）
2007 年 7 月 3 日 上午 09:35:00
发表者：Google（谷歌）研究员 吴军
在日常生活中，包括在设计计算机软件时，我们经常要判断一个元素是否在一个集合中。比如在
字处理软件中，需要检查一个英语单词是否拼写正确（也就是要判断它是否在已知的字典中）；
在 FBI，一个嫌疑人的名字是否已经在嫌疑名单上；在网络爬虫里，一个网址是否被访问过等
等。最直接的方法就是将集合中全部的元素存在计算机中，遇到一个新元素时，将它和集合中的
元素直接比较即可。一般来讲，计算机中的集合是用哈希表（hash table）来存储的。它的好
处是快速准确，缺点是费存储空间。当集合比较小时，这个问题不显著，但是当集合巨大时，哈
希表存储效率低的问题就显现出来了。比如说，一个象 Yahoo,Hotmail 和 Gmai 那样的公众
电子邮件（email）提供商，总是需要过滤来自发送垃圾邮件的人（spamer）的垃圾邮件。一
个办法就是记录下那些发垃圾邮件的 email 地址。由于那些发送者不停地在注册新的地址，全
世界少说也有几十亿个发垃圾邮件的地址，将他们都存起来则需要大量的网络服务器。如果用哈
希表，每存储一亿个 email 地址， 就需要 1.6GB 的内存（用哈希表实现的具体办法是将每
一 个 email 地 址 对 应 成 一 个 八 字 节 的 信 息 指 纹
googlechinablog.com/2006/08/blog-post.html，然后将这些信息指纹存入哈希表，由于
哈希表的存储效率一般只有 50%，因此一个 email 地址需要占用十六个字节。一亿个地址大
约要 1.6GB， 即十六亿字节的内存）。因此存贮几十亿个邮件地址
可能需要上百 GB 的内存。
除非是超级计算机，一般服务器是无法存储的。
今天，我们介绍一种称作布隆过滤器的数学工具，它只需要哈希表 1/8 到 1/4 的大小就能解
决同样的问题。
布隆过滤器是由巴顿.布隆于一九七零年提出的。它实际上是一个很长的二进制向量和一系列随
机映射函数。我们通过上面的例子来说明起工作原理。
假定我们存储一亿个电子邮件地址，我们先建立一个十六亿二进制（比特），即两亿字节的向量，
然后将这十六亿个二进制全部设置为零。对于每一个电子邮件地址 X，我们用八个不同的随机
数产生器（F1,F2, ...,F8） 产生八个信息指纹（f1, f2, ..., f8）。再用一个随机数产生器 G 把
这八个信息指纹映射到 1 到十六亿中的八个自然数 g1, g2, ...,g8。现在我们把这八个位置的
二进制全部设置为一。当我们对这一亿个 email 地址都进行这样的处理后。一个针对这些
email 地址的布隆过滤器就建成了。（见下图）
现在，让我们看看如何用布隆过滤器来检测一个可疑的电子邮件地址 Y 是否在黑名单中。我们
用相同的八个随机数产生器（F1, F2, ..., F8）对这个地址产生八个信息指纹 s1,s2,...,s8，然
后将这八个指纹对应到布隆过滤器的八个二进制位，分别是 t1,t2,...,t8。如果 Y 在黑名单中，
显然，t1,t2,..,t8 对应的八个二进制一定是一。这样在遇到任何在黑名单中的电子邮件地址，
我们都能准确地发现。
布隆过滤器决不会漏掉任何一个在黑名单中的可疑地址。但是，它有一条不足之处。也就是它有
极小的可能将一个不在黑名单中的电子邮件地址判定为在黑名单中，因为有可能某个好的邮件地
址正巧对应个八个都被设置成一的二进制位。好在这种可能性很小。我们把它称为误识概率。在
上面的例子中，误识概率在万分之一以下。
布隆过滤器的好处在于快速，省空间。但是有一定的误识别率。常见的补救办法是在建立一个小
的白名单，存储那些可能别误判的邮件地址。
数学之美 系列二十二 由电视剧《暗算》所
想到的 - 谈谈密码学的数学原理
2007 年 9 月 13 日 下午 09:00:00
发表者：Google（谷歌）研究员 吴军
前一阵子看了电视剧《暗算》，蛮喜欢它的构思和里面的表演。其中有一个故事提到了密码学，
故事本身不错，但是有点故弄玄虚。不过有一点是对的，就是当今的密码学是以数学为基础的。
（ 没 有 看 过 暗 算 的 读 者 可 以 看 一 下 介 绍 ，
http://ent.sina.com.cn/v/2005-10-17/ba866985.shtml
因为我们后面要多次提到这
部电视剧。）
密码学的历史大致可以推早到两千年前，相传名将凯撒为了防止敌方截获情报，用密码传送情报。
凯撒的做法很简单，就是对二十几个罗马字母建立一张对应表，比如说
这样，如果不知道密码本，即使截获一段信息也看不懂，比如收到一个的消息是 EBKTBP，那
么在敌人看来是毫无意义的字，通过密码本解破出来就是 CAESAR 一词，即凯撒的名字。这
种编码方法史称凯撒大帝。当然，学过信息论的人都知道，只要多截获一些情报，统计一下字母
的频率，就可以解破出这种密码。柯蓝道尔在他的员老陈破译的一份密报后，但无法推广的原因，
而数学家黄依依预见到了这个结果，因为她知道敌人新的密码系统编出的密文是统计独立的。有
了信息论后，密码的设计就有了理论基础，现在通用的公开密钥的方法，包括《暗算》里的[***********][***********][1**********]051
[1**********]94
[***********][***********][***********][1**********]
[**************]
=
[***********][***********][***********][1**********]
55281177
×[***********][***********][***********]0043952099
[***********]6139
现在，让我们回到《暗算》中，黄依依第一次找的结果经过一系列计算发现无法归零，也就是说
除不尽，我猜她可能试图将一个大数 N 做分解，没成功。第二次计算的结果是归零了，说明她
找到的 N=P×Q 的分解方法。当然，这件事能不能用算盘完成，我就不知道了，但我觉得比较
夸张。另外我对该电视剧还有一个搞不懂的问题就是里面提到的输入法的字库从二级国标扩展到更大的字库 GBK，由于后面不常见的
字频率较短，平均编码长度比针对国标的大不了多少。让我们回忆一下汉字的信息熵（见
http://www.googlechinablog.com/2006/04/4.html），
H = -p1 * log p1 - ... - p6700 log p6700。
我们如果对每一个字进行统计，而且不考虑上下文相关性，大致可以估算出它的值在十比特以内，
当然这取决于用什么语料库来做估计。如果我们假定输入法只能用 26 个字母输入，那么每个
字母可以代表 log26=
4.7 比特的信息，也就是说，输入一个汉字平均需要敲 10/4.7= 2.1 次键。
聪明的读者也许一经发现，如果我们把汉字组成词，再以词为单位统计信息熵，那么，每个汉字
的平均信息熵将会减少。这样，平均输入一个字可以少敲零点几次键盘。不考虑词的上下文相关
性，以词为单位统计，汉字的信息熵大约是 8 比特作用，也就是说，以词为单位输入一个汉字
平均只需要敲 8/4.7=1.7 次键。这就是现在所有输入法都是基于词输入的内在原因。当然，
如 果 我 们 再 考 虑 上 下 文 的 相 关 性 ， 对 汉 语 建 立 一 个 基 于 词 的 统 计 语 言 模 型 （ 见
http://www.googlechinablog.com/2006/04/blog-post.html），我们可以将每个汉字的
信息熵降到 6 比特作用，这时，输入一个汉字只要敲 6/4.7=1.3 次键。如果一种输入方法能
做到这一点，那么汉字的输入已经比英文快的多了。
但是，事实上没有一种输入方法接近这个效率。这里面主要有两个原因。首先，要接近信息论给
的这个极限，就要对汉字的词组根据其词频进行特殊编码。事实上像王码这类的输入方法就是这
么做到，只不过它们第一没有对词组统一编码，第二没有有效的语言模型。这种编码方法理论上
讲有效，实际上不实用。原因有两个，第一，很难学；第二，从认知科学的角度上讲，人一心无
二用，人们在没有稿子边想边写的情况下不太可能在回忆每个词复杂的编码的同时又不中断思维。
我们过去在研究语言识别时做过很多用户测试，发现使用各种复杂编码输入法的人在脱稿打字时
的速度只有他在看稿打字时的一半到四分之一。因此，虽然每个字平均敲键次数少，但是打键盘
的速度也慢了很多，总的并不快。这也就是为什么基于拼音的简单输入法占统治地位的原因。事
实上，汉语全拼的平均长度为 2.98，只要基于拼音的输入法能利用上下文彻底解决一音多字的
问题，平均每个汉字输入的敲键次数应该在三次左右，每分钟输入 100 个字完全有可能达到。
另外一个不容易达到信息论极限的输入速度的原因在于，这个理论
值是根据一个很多的语言模型
计算出来的。在产品中，我们不可能占有用户太多的内存空间，因此各种输入方法提供给用户的
是一个压缩的很厉害的语音模型，而有的输入方法为了减小内存占用，根本没有语言模型。拼音
输入法的好坏关键在准确而有效的语言模型。
另一方面，由于现有输入方法离信息论给的极限还有很大的差距，汉语输入方法可提升的空间很
大，会有越来越好用的输入方法不断涌现。当然，输入速度只是输入法的一项而不是唯一的衡量
标 准 。 我 们 也 会 努 力 把 谷 歌 的 输 入 法 做 的 越 来 越 好 。 大 家 不 妨 先 试 试 现 在 的 版 本 ，
http://tools.google.com/pinyin/，半年后再看看我们有没有提高。