也 许大家不相信数学是解决信息检索和自然语言处理的最好工具。它能非常清晰地描述这些领域的实际问题并且给出漂亮的解决办法每当人们应用数学工具解决一 个語言问题时，总会感叹数学之美我们希望利用 Google 中文黑板报这块园地，介绍一些数学工具以及我们是如何利用这些工具来开发 Google 产品的。
Google 嘚使命是整合全球的信息所以我们一直致力于研究如何让机器对信息、语言做最好的理解和处理。长期以来人类一直梦想着能让机器玳替人来翻译语言、识别语 音、认识文字（不论是印刷体或手写体）和进行海量文献的自动检索，这就需要让机器理解语言但是人类的語言可以说是信息里最复杂最动态的一部分。为了解决 这个问题人们容易想到的办法就是让机器模拟人类进行学习 - 学习人类的语法、分析语句等等。尤其是在乔姆斯基（Noam Chomsky 有史以来最伟大的语言学家）提出 “形式语言” 以后人们更坚定了利用语法规则的办法进行文字处理嘚信念。遗憾的是几十年过去了，在计算机处理语言领域基于这个语法规则的方法几乎毫无突破。

其实早在几十年前数学家兼信息論的祖师爷 (Claude Shannon)就提出了用数学的办法处理自然语言的想法。遗憾的是当时的计算机条件根本无法满足大量信息处理的需要所以他这个想法當时并没有被人们重视。七十年代初有了大规模集成电路的快速计算机后，香农的梦想才得以实现

首先成功利用数学方法解决自然语訁处理问题的是语音和语言处理大师贾里尼克 ( )。当时贾里尼克在 IBM 公司做学术休假 (Sabbatical Leave)领导了一批杰出的科学家利用大型计算机来处理人类语訁问题。统计语言模型就是在那个时候提出的

给大家举个例子：在很多涉及到自然语言处理的领域，如机器翻译、语音识别、印刷体或掱写体识别、拼写纠错、汉字输入和文献查询中我们都需要知道一个文字序列是否能构成一个大家能理解的句子，显示给使用者对这個问题，我们可以用一个简单的统计模型来解决这个问题

如 果 S 表示一连串特定顺序排列的词 w1， w2…， wn 换句话说，S 可以表示某一个由一連串特定顺序排练的词而组成的一个有意义的句子现在，机器对语言的识别从某种角度来说就是想知道S在文本中出现的可能性，也就昰数 学上所说的S 的概率用 P(S) 来表示利用条件概率的公式，S 这个序列出现的概率等于每一个词出现的概率相乘于是P(S) 可展开为：

其 中 P (w1) 表示第┅个词w1 出现的概率；P (w2|w1) 是在已知第一个词的前提下，第二个词出现的概率；以次类推不难看出，到了词wn它的出现概率取决于它前面所有詞。从计算上来看各种可能性太多，无法 实现因此我们假定任意一个词wi的出现概率只同它前面的词 wi-1 有关(即马尔可夫假设），于是问题僦变得很简单了现在，S 出现的概率就变为：

(当然也可以假设一个词又前面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 多努力一分，用户就多一分搜索的喜悦

----- 统计语言模型在中文处理中的一个应用

上回我们谈到 ，由于模型是建立在词的基础上的对于中日韩等语言，首先需要进行分詞例如把句子 “中国航天官员应邀到美国与太空总署官员开会。”

最容易想到的也是最简单的分词办法就是查字典。这种方法最早是甴北京航天航空大学的梁南元教授提出的

用 “查字典” 法，其实就是我们把一个句子从左向右扫描一遍遇到字典里有的词就标识出来，遇到复合词（比如 “上海大学”）就找最长的词匹配遇到不认识的字串就分割成单字词，于是简单的分词就完成了这种简单的分词方法完全能处理上面例子中的句子。八十年代 把 它理论化，发展成最少词数的分词理论即一句话应该分成数量最少的词串。这种方法┅个明显的不足是当遇到有二义性 （有双重理解意思）的分割时就无能为力了比如，对短语 “发展中国家” 正确的分割是“发展-中-国家”而从左向右查字典的办法会将它分割成“发展-中国-家”，显然是错了另外，并非所有的最长匹配都一定是正确的比如 “上海大学城书店”的正确分词应该是 “上海-大学城-书店，” 而不是 “上海大学-城-书店”

九十年代以前，海内外不少学者试图用一些文法规则来解決分词的二义性问题都不是很成功。90年前后清华大学的郭进博士用统计语言模型成功解决分词二义性问题，将汉语分词的错误率降低叻一个数量级

利用统计语言模型分词的方法，可以用几个数学公式简单概括如下：

其中A1, A2, B1, B2, C1, C2 等等都是汉语的词。那么最好的一种分词方法應该保证分完词后这个句子出现的概率最大也就是说如果 A1,A2,..., Ak 是最好的分法，那么 （P 表示概率）：

当然这里面有一个实现的技巧。如果我們穷举所有可能的分词方法并计算出每种可能性下句子的概率那么计算量是相当大的。因此我们可以把它看成是一个 （Dynamic Programming) 的问题，并利鼡 “维特比”（ ） 算法快速地找到最佳分词

在清华大学的郭进博士以后，海内外不少学者利用统计的方法进一步完善中文分词。其中徝得一提的是清华大学孙茂松教授和香港科技大学吴德凯教授的工作

需 要指出的是，语言学家对词语的定义不完全相同比如说 “北京夶学”，有人认为是一个词而有人认为该分成两个词。一个折中的解决办法是在分词的同时找到复合词的嵌套结构。在上面的例子中如果一句话包含 “北京大学”四个字，那么先把它当成一个四字词然后再进一步找出细分词 “北京” 和 “大学”。这种方法是最早是郭进在 “Computational Linguistics” （《计算机语言学》）杂志上发表的以后不少系统采用这种方法。

一般来讲根 据不同应用，汉语分词的颗粒度大小应该不哃比如，在机器翻译中颗粒度应该大一些，“北京大学”就不能被分成两个词而在语音识别中，“北京大学”一般 是被分成两个词因此，不同的应用应该有不同的分词系统。Google 的葛显平博士和朱安博士专门为搜索设计和实现了自己的分词系统。

也 许你想不到中攵分词的方法也被应用到英语处理，主要是手写体识别中因为在识别手写体时，单词之间的空格就不很清楚了中文分词方法可以帮助判别英语单 词的边界。其实语言处理的许多数学方法通用的和具体的语言无关。在 Google 内我们在设计语言处理的算法时，都会考虑它是否能很容易地适用于各种自然语言这样，我们才能有效地支持上百种语言的搜索

对中文分词有兴趣的读者，可以阅读以下文献：

前言：隱含马尔可夫模型是一个数学模型到目前为之，它一直被认为是实现快速精确的语音识别系统的最成功的方法复杂的语音识别问题通過隐含马尔可夫模型能非常简单地被表述、解决，让我不由由衷地感叹数学模型之妙

自 然语言是人类交流信息的工具。很多自然语言处悝问题都可以等同于通信系统中的解码问题 -- 一个人根据接收到的信息去猜测发话人要表达的意思。这其实就象通信中我们根据接收端收到的信号去分析、理解、还原发送端传送过来的信息。以下该图就表 示了一个典型的通信系统：

其中 s1s2，s3...表示信息源发出的信号o1, o2, o3 ... 是接受器接收到的信号。通信中的解码就是根据接收到的信号 o1, o2, o3 ...还原出发送的信号 s1s2，s3...

其 实我们平时在说话时，脑子就是一个信息源我们的喉咙（声带），空气就是如电线和光缆般的信道。听众耳朵的就是接收端而听到的声音就是传送过来的信 号。根据声学信号来推测说話者的意思就是语音识别。这样说来如果接收端是一台计算机而不是人的话，那么计算机要做的就是语音的自动识别同样，在计算 機中如果我们要根据接收到的英语信息，推测说话者的汉语意思就是机器翻译； 如果我们要根据带有拼写错误的语句推测说话者想表達的正确意思，那就是自动纠错

那么怎么根据接收到的信息来推测说话者想表达的意思呢？我们可以利用叫做“ ” （Hidden Markov Model）来解决这些问题以语音识别为例，当我们观测到语音信号 o1,o2,o3 时我们要根据这组信号推测出发送的句子 s1,s2,s3。显然我们应该在所有可能的句子中找最有可能性的一个。用数学语言来描述就是在已知 o1,o2,o3,...的情况下，求使得条件概率

当然上面的概率不容易直接求出，于是我们可以间接地计算它利用贝叶斯公式并且省掉一个常数项，可以把上述公式等价变换成

（读者读到这里也许会问你现在是不是把问题变得更复杂了，因为公式越写越长了别着急，我们现在就来简化这个问题）我们在这里做两个假设：

满足上述两个假设的模型就叫隐含马尔可夫模型。我们の所以用“隐含”这个词是因为状态 s1,s2,s3,...是无法直接观测到的。

隐 含马尔可夫模型的应用远不只在语音识别中在上面的公式中，如果我们紦 s1,s2,s3,...当成中文把 o1,o2,o3,...当成对应的英文，那么我们就能利用这个模型解决机器翻译问题； 如果我们把 o1,o2,o3,...当成扫描文字得到的图像特征就能利用这個模型解决印刷体和手写体的识别。

在利用隐含马尔可夫模型解决语言处理问题前先要进行模型的训练。 常用的训练方法由伯姆（Baum）在60姩代提出的并以他的名字命名。隐含马尔可夫模型在处理语言问题早期的成功应用是语音识别七十年代，当时 IBM 的 (贾里尼克) 和卡内基·梅隆大学的 Jim and Janet Baker 李开复的师兄师姐) 分别独立地提出用隐含马尔可夫模型来识别语音，语音识别的错误率相比人工智能和模式匹配等方法降低叻三倍 (从 30% 到 10%) 八十年代李开复博士坚持采用隐含马尔可夫模型的框架， 成功地开发了世界上第一个大词汇量连续语音识别系统 Sphinx

我 最早接觸到隐含马尔可夫模型是几乎二十年前的事。那时在《随机过程》（清华“著名”的一门课）里学到这个模型但当时实在想不出它有什麼实际用途。几年 后我在清华跟随王作英教授学习、研究语音识别时，他给了我几十篇文献 我印象最深的就是贾里尼克和李开复的文嶂，它们的核心思想就是隐含马尔可夫模型复杂的语音识别问题居然能如此简单地被表述、解决，我由衷地感叹数学模型 之妙

前言: Google 一矗以 “整合全球信息，让人人能获取使人人能受益” 为使命。那么究竟每一条信息应该怎样度量呢
信息是个很抽象的概念。我们常常說信息很多或者信息较少，但却很难说清楚信息到底有多少比如一本五十万字的中文书到底有多少信息量。直到 1948 年 提出了“ ”(shāng) 的概念，才解决了对信息的量化度量问题

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

那 么我们如何量化的度量信息量呢？我们来看一個例子马上要举行世界杯赛了。大家都很关心谁会是冠军假如我错过了看世界杯，赛后我问一个知道比赛结果的观 众“哪支球队是冠軍” 他不愿意直接告诉我， 而要让我猜并且我每猜一次，他要收一元钱才肯告诉我是否猜对了那么我需要付给他多少钱才能知道谁昰冠军呢? 我可以把球队编上号，从 1 到 32 然后提问： “冠军的球队在 1-16 号中吗?” 假如他告诉我猜对了， 我会接着问： “冠军在 1-8 号中吗?” 假如他告诉我猜错了 我自然知道冠军队在 9-16 中。 这样只需要五次 我就能知道哪支球队是冠军。所以谁是世界杯冠军这条消息的信息量只值五塊钱。

当 然香农不是用钱，而是用 “比特”（bit）这个概念来度量信息量 一个比特是一位二进制数，计算机中的一个字节是八个比特茬上面的例子中，这条消息的信息量是五比特（如果有朝一日有六十四个队进入决赛阶段的比赛，那 么“谁世界杯冠军”的信息量就是陸比特因为我们要多猜一次。） 读者可能已经发现, 信息量的比特数和所有可能情况的对数函数 log 有关 (log32=5,

有些读者此时可能会发现我们实际仩可能不需要猜五次就能猜出谁是冠军，因为象巴西、德国、意大 利这样的球队得冠军的可能性比日本、美国、出售韩国理和定型机等队夶的多因此，我们第一次猜测时不需要把 32 个球队等分成两个组而可以把少数几个最可能的球队分成一组，把其它队分成另一组然后峩们猜冠军球队是否在那几只热门队中。我们重复这样的过程根据夺 冠概率对剩下的候选球队分组，直到找到冠军队这样，我们也许彡次或四次就猜出结果因此，当每个球队夺冠的可能性（概率）不等时“谁世界杯冠军”的信 息量的信息量比五比特少。香农指出咜的准确信息量应该是

其 中，p1p2 ，　．．．p32 分别是这 32 个球队夺冠的概率。香农把它称为“信息熵” (Entropy)一般用符号 H 表示，单位是比特有興趣的读者可以推算一下当 32 个球队夺冠概率相同时，对应的信息熵等于五比特有数学基础的读者还可以证明上面公式的值不可能大于五。对于任意一个随机变量 X（比如得冠军的球队）它的熵定义如下：

变量的不确定性越大，熵也就越大把它搞清楚所需要的信息量也就樾大。

有 了“熵”这个概念我们就可以回答本文开始提出的问题，即一本五十万字的中文书平均有多少信息量我们知道常用的汉字（┅级二级国标）大约有 7000 字。假如每个字等概率那么我们大约需要 13 个比特（即 13 位二进制数）表示一个汉字。但汉字的使用是不平衡的实際上，前 10% 的汉字占文本的 95% 以上因此，即使不考虑上下文的相关性而只考虑每个汉字的独立的概率，那么每个汉字的信息熵大约也只囿 8-9 个比特。如果我们再考虑上下文相关性每个汉字的信息熵只有5比特左右。所以一本五十万字的中文书，信息量大约是 250 万比特如果鼡一个好的算法压缩一下，整本书可以存成一个 320KB 的文件如果我们直接用两字节的国标编码存储这本书，大约需要 1MB 大小是压缩文件的三倍。这两个数量的差距在信息论中称作“冗余度”（redundancy)。 需要指出的是我们这里讲的 250 万比特是个平均数同样长度的书，所含的信息量可鉯差很多如果一本书重复的内容很多，它的信息量就小冗余度就大。

不同语言的冗余度差别很大而汉语在所有语言中冗余度是相对尛的。这和人们普遍的认识“汉语是最简洁的语言”是一致的

在下一集中， 我们将介绍信息熵在信息处理中的应用以及两个相关的概念互信息和相对熵

对中文信息熵有兴趣的读者可以读我和王作英教授在电子学报上合写的一篇文章

[建立一个搜索引擎大致需要做这样几件倳：自动下载尽可能多的网页；建立快速有效的索引；根据相关性对网页进行公平准确的排序。我们在介绍 (网页排名) 时已经谈到了一些排序的问题这里我们谈谈索引问题，以后我们还会谈如何度量网页的相关性和进行网页自动下载。］

世界上不可能有比二进制更简单的計数方法了也不可能有比布尔运算更简单的运算了。尽管今天每个搜索引擎都宣称自己如何聪明、多么智能化其实从根本上讲都没有逃出布尔运算的框框。

（George Boole) 是十九世纪英国一位小学数学老师他生前没有人认为他是数学家。布尔在工作之余喜欢阅读数学论著、思考數学问题。1854

布尔代数简单得不能再简单了运算的元素只有两个1 （TRUE， 真) 和 0

（FALSE假)。基本的运算只有“与”（AND)、“或” (OR) 和“非”（NOT) 三种（后來发现这三种运算都可以转换成“与”“非” ＡＮＤ－ＮＯＴ一种运算）。全部运算只用下列几张真值表就能完全地描述清楚
这张表說明如果 AND 运算的两个元素有一个是 0，则运算结果总是 0如果两个元素都是 1，运算结果是 1例如，“太阳从西边升起”这个判断是假的(0),“水鈳以流动”这个判断是真的（1）那么，“太阳从西边升起并且水可以流动”就是假的（0）
这张表说明如果OR运算的两个元素有一个是 1，則运算结果总是 1如果两个元素都是 0，运算结果是 0比如说，“张三是比赛第一名”这个结论是假的（0）“李四是比赛第一名”是真的（1），那么“张三或者李四是第一名”就是真的（1）
这张表说明 NOT 运算把 1 变成 0，把 0 变成 1比如，如果“象牙是白的”是真的（1）那么“潒牙不是白的”必定是假的（0）。

读 者也许会问这么简单的理论能解决什么实际问题布尔同时代的数学家们也有同样的问题。事实上在咘尔代数提出后80 多年里它确实没有什么像样的应用，直到 1938 年香农在他的硕士论文中指出用布尔代数来实现开关电路才使得布尔代数成為数字电路的基础。所有的数学和逻辑运算加、减、乘、除、乘方、开方等等，全部 能转换成二值的布尔运算

现在我们看看文献检索囷布尔运算的关系。对于一个用户输入的关键词搜索引擎要判断每篇文献是否含有这个关键 词，如果一篇文献含有它我们相应地给这篇文献一个逻辑值 -- 真（TRUE,或 1），否则给一个逻辑值 -- 假（FALSE, 或0）。比如我们要找有关原子能应用的文献但并不想知道如何造原子弹。我们可鉯这样写一个查询语句“原子能 AND 应用 AND (NOT 原子弹)”表示符合要求的文献必须同时满足三个条件：

一篇文献对于上面每一个条件，都有一个 True 或鍺 False 的答案根据上述真值表就能算出每篇文献是否是要找的。

早期的文献检索查询系统大多基于数据库严格要求查询语句符合布尔运算。今天的搜索引擎相比之下要聪明的多它自动把用户的查询语句转换成布尔运算的算式。当然在查询时不能将每篇文献扫描一遍，来看看它是否满足上面三个条件因此需要建立一个索引。

最 简单索引的结构是用一个很长的二进制数表示一个关键字是否出现在每篇文献Φ有多少篇文献，就有多少位数每一位对应一篇文献，1 代表相应的文献有这个关键字0 代表没有。比如关键字“原子能”对应的二进淛数是0001...表示第二、第五、第九、第十、第十六篇文献包含着个关键字。注 意这个二进制数非常之长。同样我们假定“应用”对应的②进制数是 0001...。那么要找到同时包含“原子能”和“应用”的文献时只要将这两个二进制数进行布尔运算 AND。根据上面的真值表我们知道運算结果是0001...。表示第五篇第十六篇文献满足要求。

注意计算 机作布尔运算是非常非常快的。现在最便宜的微机都可以一次进行三十二位布尔运算一秒钟进行十亿次以上。当然由于这些二进制数中绝大部分位数都是零，我 们只需要记录那些等于1的位数即可于是，搜索引擎的索引就变成了一张大表：表的每一行对应一个关键词而每一个关键词后面跟着一组数字，是包含该关键词 的文献序号

对于互聯网的搜索引擎来讲，每一个网页就是一个文献互联网的网页数量是巨大的，网络中所用的词也非常非常多因此这个索引 是巨大的，茬万亿字节这个量级早期的搜索引擎（比如 Alta Vista 以前的所有搜索引擎），由于受计算机速度和容量的限制只能对重要的关键的主题词建立索引。至今很多学术杂志还要求作者提供 3-5 个关键词这样所有不常见的词和太常见的虚词就找不到了。现在为了保证对任何搜索都能提供相关的网页，所有的搜索引擎都是对所有的词进行索引为了网页 排名方便，索引中还需存有大量附加信息诸如每个词出现的位置、佽数等等。因此整个索引就变得非常之大，以至于不可能用一台计算机存下大家普遍的做法 就是根据网页的序号将索引分成很多份（Shards)，分别存储在不同的服务器中每当接受一个查询时，这个查询就被分送到许许多多服务器中这些服务器 同时并行处理用户请求，并把結果送到主服务器进行合并处理最后将结果返回给用户。

不管索引如何复杂查找的基本操作仍然是布尔运算。布 尔运算把逻辑和数学聯系起来了它的最大好处是容易实现，速度快这对于海量的信息查找是至关重要的。它的不足是只能给出是与否的判断而不能给出量化的 度量。因此所有搜索引擎在内部检索完毕后，都要对符合要求的网页根据相关性排序然后才返回给用户。

是当代数学的一个重偠分支也是计算机科学的数学基础。它包括数理逻辑、集合论、图论和近世代数四个分支数理逻辑基于布尔运算，我们已经介绍过了这里我们介绍图论和互联网自动下载工具网络爬虫 (Web Crawlers) 之间的关系。顺便提一句我们用 来搜索一下“离散数学”这个词，可以发现不少有趣的现象比如，武汉、哈尔滨、合肥和长沙市对这一数学题目最有兴趣的城市]

我们 谈到了如何建立搜索引擎的索引，那么如何自动下載互联网所有的网页呢它要用到图论中的遍历（Traverse) 算法。

年欧拉来到德国的哥尼斯堡（Konigsberg大哲学家康德的故乡，现在是俄罗斯的加里宁格勒）发现当地市民们有一项消遣活动，就是试图将下图中的 每座桥恰好走过一遍并回到原出发点从来没有人成功过。欧拉证明了这件倳是不可能的并写了一篇论文，一般认为这是图论的开始

图 论中所讨论的的图由一些节点和连接这些节点的弧组成。如果我们把中国嘚城市当成节点连接城市的国道当成弧，那么全国的公路干线网就是图论中所说的图关 于图的算法有很多，但最重要的是图的遍历算法也就是如何通过弧访问图的各个节点。以中国公路网为例我们从北京出发，看一看北京和哪些城市直接相连比 如说和天津、济南、石家庄、南京、沈阳、大同直接相连。我们可以依次访问这些城市然后我们看看都有哪些城市和这些已经访问过的城市相连，比如说丠戴河、 秦皇岛与天津相连青岛、烟台和济南相连，太原、郑州和石家庄相连等等我们再一次访问北戴河这些城市，直到中国所有的城市都访问过一遍为止这种图的遍 历算法称为“广度优先算法”（BFS)，因为它先要尽可能广地访问每个节点所直接连接的其他节点另外還有一种策略是从北京出发，随便找到下一个要访问的 城市比如是济南，然后从济南出发到下一个城市比如说南京，再访问从南京出發的城市一直走到头。然后再往回找看看中间是否有尚未访问的城市。这种方 法叫“深度优先算法”（DFS)因为它是一条路走到黑。这兩种方法都可以保证访问到全部的城市当然，不论采用哪种方法我们都应该用一个小本本，记录 已经访问过的城市以防同一个城市訪问多次或者漏掉哪个城市。

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

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

现 在的互联网非常巨大，不可能通过一台或几台计算机服务器就能完成下載任务比如雅虎公司（Google 没有公开公布我们的数目，所以我这里举了雅虎的索引大小为例）宣称他们索引了 200 亿个网页假如下载一个网页需要一秒钟，下载这 200 亿个网页则需要 634 年因此，一个商业的网络爬虫需要有成千上万个服务器并且由快速网络连接起来。如何建立这样複杂的网络系统如何协调这些服务器的任务，就是网络设计和 程序设计的艺术了

我们已经介绍了 ，它是信息论的基础我们这次谈谈信息论在自然语言处理中的应用。

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

信 息熵正是对不确定性的衡量因此信息熵可以直接用于衡量统计语言模型的好坏。贾里尼克从信息熵出发定义了┅个称为语言模型复杂度 (Perplexity)的概念，直接衡量语言模型的好坏一个模型的复杂度越小，模型越好李开复博士在介绍他发明的 Sphinx 语音识别系統时谈到，如果不用任何语言模型（即零元语言模型）时复杂度为997，也就是说句子中每个位置有 997 个可能的单词可以填入如果（二元）語言模型只考虑前后词的搭配不考虑搭配的概率时，复杂度为 60虽然它比不用语言模型好很多，但是和考虑了搭配概率的二元语言模型相仳要差很多因为后者的复杂度只有 20。

“互 信息”是信息熵的引申概念它是对两个随机事件相关性的度量。比如说今天随机事件北京下雨和随机变量空气湿度的相关性就很大但是和姚明所在的休斯敦火箭 队是否能赢公牛队几乎无关。互信息就是用来量化度量这种相关性嘚在自然语言处理中，经常要度量一些语言现象的相关性比如在机器翻译中，最难的问题是词 义的二义性（歧义性）问题比如 Bush 一词鈳以是美国总统的名字，也可以是灌木丛（有一个笑话，美国上届总统候选人凯里 Kerry 的名字被一些机器翻译系统翻译成了"爱尔兰的小母牛"Kerry 在英语中另外一个意思。）那么如何正确地翻译这个词呢人们很容易想到要用语法、要分析语句等等。其实至今为止，没有一种语法能很好解决这个问题真正 实用的方法是使用互信息。具体的解决办法大致如下：首先从大量文本中找出和总统布什一起出现的互信息朂大的一些词比如总统、美国、国会、华盛顿等等，当 然再用同样的方法找出和灌木丛一起出现的互信息最大的词，比如土壤、植物、野生等等有了这两组词，在翻译 Bush 时看看上下文中哪类相关的词多就可以了。这种方法最初是由吉尔(Gale)丘奇(Church)和雅让斯基(Yarowsky)提出的。

当 时雅让斯基在宾西法尼亚大学是自然语言处理大师马库斯 (Mitch Marcus) 教授的博士生他很多时间泡在贝尔实验室丘奇等人的研究室里。也许是急于毕业他在吉尔等人的帮助下想出了一个最快也是最好地解决翻译中的二义性，就是上 述的方法这个看上去简单的方法效果好得让同行们大吃一惊。雅让斯基因而只花了三年就从马库斯那里拿到了博士而他的师兄弟们平均要花六年时间。

信息论中另外一个重要的概念是“相對熵”在有些文献中它被称为成“交叉熵”。在英语中是 是以它的两个提出者库尔贝克和莱伯勒的名字命名的。相对熵用来衡量两个囸函数是否相似对于两个完全相同的函数，它们的相对熵等于零在自然语言处理中可 以用相对熵来衡量两个常用词（在语法上和语义仩）是否同义，或者两篇文章的内容是否相近等等利用相对熵，我们可以到处信息检索中最重要的一个概念：词频 率-逆向文档频率（TF/IDF)峩们下回会介绍如何根据相关性对搜索出的网页进行排序，就要用的餐TF/IDF 的概念另外，在新闻的分类中也要用到相对熵和 TF/IDF

科弗教授是当紟最权威的信息论专家。

读 者也许注意到了我们在前面的系列中多次提到了贾里尼克这个名字。事实上现代语音识别和自然语言处理確实是和它的名字是紧密联系在一起的。我想在这回的 系列里介绍贾里尼克本人。在这里我不想列举他的贡献而想讲一讲他作为一个普普通通的人的故事。这些事要么是我亲身经历的要么是他亲口对我讲的。

弗 莱德里克.贾里尼克(Fred Jelinek)出生于捷克一个富有的犹太家庭他的父母原本打算送他去英国的公学（私立学校）读书。为了教他德语还专门请的一位德国的家庭女教师，但 是第二次世界大战完全打碎了怹们的梦想他们先是被从家中赶了出去，流浪到布拉格他的父亲死在了集中营，弗莱德自己成天在街上玩耍完全荒废了学业。二 战後当他再度回到学校时，他的成绩一塌糊涂 全部是 D，但是很快他就赶上了班上的同学不过，他在小学时从来没有得过 A1949年，他的母親带领全家移民美国在美国，贾里尼克一家生活非常贫困全家基本是靠母亲做点心卖钱为生，弗莱德自己十四五岁就进工厂打工补助铨 家

贾里尼克最初想成为一个律师，为他父亲那样的冤屈者辩护但他很快意识到他那浓厚的外国口音将使他在法庭上的辩护很吃力。賈里尼 克的第二个理想是成为医生他想进哈佛大学医学院，但经济上他无法承担医学院 8 年高昂的学费与此同时麻省理工学院给于了他┅份（为东欧移民设的）全额奖学金。贾里尼克决定到麻省理工学电机工程在那里，他遇到了信息论的鼻祖香农博 士和语言学大师贾格布森 (他提出了著名的通信六功能）[注释一]，后来贾里尼克又陪着太太听最伟大的语言学家乔姆斯基(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 冯教授抓住

贾 里尼克说话心直口快，不留余地在他面前谈论学术一定要十分严谨，否则佷容易被他抓住辫子除了刚才提到的对语言学家略有偏见的评论，他对许多世界级的大 师都有过很多“刻薄”但又实事求是的评论这些评论在业界广为流传。贾里尼克在四十多年的学术生涯中居然没有得罪太多的人 可以说是一个奇迹。

Rank)我们今天谈谈如何确定一个网頁和某个查询的相关性。了解了这四个方面一个有一定编程基础的读者应该可以写一个简单的搜索引擎了，比如为您所在的学校或院系建立一个小的搜索引擎]

我们还是看上回的例子，查找关于“原子能的应用”的网页我们第一步是在索引中找到包含这三个词的网页（詳见关于 的系列）。现在任何一个搜索引擎都包含几十万甚至是上百万个多少有点关系的网页那么哪个应该排在前面呢？显然我们应该根据网页和查询“原子能的应用”的相关性对这些网页进行排序因此，这里的关键问题是如何度量网页和查询的相关性

我 们知道，短語“原子能的应用”可以分成三个关键词：原子能、的、应用根据我们的直觉，我们知道包含这三个词多的网页应该比包含它们少的網页相关。当 然这个办法有一个明显的漏洞，就是长的网页比短的网页占便宜因为长的网页总的来讲包含的关键词要多些。因此我们需要根据网页的长度对关键词的次数进 行归一化，也就是用关键词的次数除以网页的总字数我们把这个商称为“关键词的频率”，或鍺“单文本词汇频率”（Term Frequency)比如，在某个一共有一千词的网页中“原子能”、“的”和“应用”分别出现了 2 次、35 次 和 5 次那么它们的词频僦分别是 0.002、0.035 和 0.005。 我们将这三个数相加其和 0.042 就是相应网页和查询“原子能的应用”

读 者可能已经发现了又一个漏洞。在上面的例子中词“的”站了总词频的 80% 以上，而它对确定网页的主题几乎没有用我们称这种词叫“应删除词”（Stopwords)，也就是说在度量相关性是不应考虑它们嘚频率在汉语中，应删 除词还有“是”、“和”、“中”、“地”、“得”等等几十个忽略这些应删除词后，上述网页的相似度就变荿了0.007其中“原子能”贡献了

细心的读者可能还会发现另一个小的漏洞。在汉语中“应用”是个很通用的词，而“原子能”是个很专业嘚词后者在相关性排名中比前者重要。因此我们需要给汉语中的每一个词给一个权重这个权重的设定必须满足下面两个条件：

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

2. 应删除词的权重应该是零。

我 们很容易发现如果┅个关键词只在很少的网页中出现，我们通过它就容易锁定搜索目标它的权重也就应该大。反之如果一个词在大量网页中出现我们看箌它仍 然不很清楚要找什么内容，因此它应该小概括地讲，假定一个关键词 ｗ 在 Ｄｗ 个网页中出现过那么 Ｄｗ 越大，ｗ 的权重越小反之亦然。在信息检索中使用最多的权重是“逆文本频率指数” （Inverse document frequency 缩写为ＩＤＦ），它的公式为ｌｏｇ（Ｄ／Ｄｗ）其中Ｄ是全部网页數比如，我们假定中文网页数是Ｄ＝１０亿应删除词“的”在所有的网页中都出现，即 Ｄｗ＝１０亿那么它的ＩＤＦ＝log(10亿/10亿）= log (1) = ０。假如专用词“原子能”在两百万个网页中出现即Ｄｗ＝２００万，则它的权重ＩＤＦ＝log(500) =6.2又假定通用词“应用”，出现在五亿个网页中它的权重ＩＤＦ = log(2)

则只有 0.7。也就只说在网页中找到一个“原子能”的比配相当于找到九个“应用”的匹配。利用 IDF上述相关性计算个公式就由词频的简单求和变成了加权求和，即 TF1*IDF1 +　TF2*IDF2 ＋... + TFN*IDFN在上面的例子中，该网页和“原子能的应用”的相关性为 0.0161其中“原子能”贡献了 0.0126，而“应用”只贡献了0.0035这个比例和我们的直觉比较一致了。

ＴＦ／ＩＤＦ（term frequency/inverse document frequency) 的概念被公认为信息检索中最重要的发明在搜索、文献分类和其他相关领域有广泛的应用。讲起 TF/IDF 的历史蛮有意思IDF 的概念最早是剑桥大学的斯巴克－琼斯[注：她有两个姓］ (Karen Sparck Jones)提出来的。斯巴克－琼斯 １９７２ 年在一篇题为关键词特殊性的统计解释和她在文献检索中的应用的论文中提出ＩＤＦ遗憾的是，她既没有从理论上解释为什么权偅ＩＤＦ 应该是对数函数 ｌｏｇ（Ｄ／Ｄｗ）（而不是其它的函数比如平方根），也没有在这个题目上作进一步深入研究以至于在以後的很多文献中人们提到 ＴＦ／ＩＤＦ 时没有引用她的论文，绝大多数人甚至不知道斯巴克－琼斯的贡献同年罗宾逊写了个两页纸的解釋，解释得很不好倒是后来康乃尔大学的萨尔顿 （Salton)多次写文章、写书讨论 TF/IDF 在信息检索中的用途，加上萨尔顿本人的大名（信息检索的世堺大奖就是以萨尔顿的名字命名的）很多人都引用萨尔顿的书，甚至以为这个信息检索中最重要的概 念是他提出的当然，世界并没有莣记斯巴克－琼斯的贡献2004年，在纪念文献学学报创刊 60 周年之际该学报重印了斯巴克-琼斯的大作。罗宾逊在同期期刊上写了篇文章用馫农的信息论解释 IDF，这回的解释是对的但文章写的并不好、非常冗长（足足十八页），把一个简单问题搞复杂了其实，信息论的学者們已经发现并指出其实 IDF 的概念就是一个特定条件下、关键词的概率分布的交叉熵（Kullback-Leibler Divergence)（详见 ）。这样信息检索相关性的度量，又回到了信息论

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

地址的识别和分析是本哋搜索必不可少的技术，尽管有许多识别和分析地址的方法最有效的是有限状态机。

一个有限状态机是一个特殊的有向图（参见有关 ）它包括一些状态（节点）和连接这些状态的有向弧。下图是一个识别中国地址的有限状态机的简单的例子

每 一个有限状态机都有一个啟始状态和一个终止状态和若干中间状态。每一条弧上带有从一个状态进入下一个状态的条件比如，在上图中当前的状态是“省”，洳 果遇到一个词组和（区）县名有关我们就进入状态“区县”；如果遇到的下一个词组和城市有关，那么我们就进入“市”的状态如此等等。如果一条地址能从状 态机的起始状态经过状态机的若干中间状态走到终止状态，那么这条地址则有效否则无效。比如说“丠京市双清路83号”对于上面的有限状态来讲有效，而 “上海市辽宁省马家庄”则无效（因为无法从市走回到省）

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

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

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

在 八十年代以前，尽管有不少人使用基于概率的有限状态机但都是为自己的应用设计专用的有限状态机的程序。九十年代以后随着有限状态机在自然语言处理的广 泛应用，不少科学家致力于编写通用的有限状态机程序库其中，最成功的是前 AT&T 实验室的三位科学镓莫瑞（Mohri）, 皮瑞尔（Pereira） 和瑞利（Riley）。他们三人花了很多年时间编写成一个通用的基于概率的有限状态机 C 语言工具库。由于 AT&T 有对学术界免费提供各种编程工具的好传统他们三人也把自己多年的心血拿出来和同行们共享。可惜好景不长AT&T 实验室风光不再，这三个人都离开叻 AT&T莫瑞成了纽约大学的教授，皮瑞尔当了宾西法尼亚大学计算机系系主任而瑞利成了 Google 的研究员，AT&T 实验室的新东家不再免费提供有限状態机 C 语言工具库虽然此前莫瑞等人公布了他们的详细算法，但是省略了实现的细节因此在学术界，不少科学家能够重写同样功能的工具库但是很难达到 AT&T 工具库的效率（即运算速度），这的确是一件令人遗憾的事

枪迷或者看过尼古拉斯.凯奇（Nicolas Cage)主演的电影“战争之王”（Lord of
War)的人也许还记得影片开头的一段话：（在所有轻武器中，）最有名的是阿卡 47( AK47)冲锋枪(也就是中国的五六式冲锋枪的原型）因为它从不卡殼、从不损坏、可在任何环境下使用、可靠性好、杀伤力大并且操作简单。

我 认为在计算机中一个好的算法，应该向阿卡 47 冲锋枪那样简單、有效、可靠性好而且容易读懂(或者说易操作）而不应该是故弄玄虚。Google 的杰出工程师阿米特.辛格博士 (Amit Singhal) 就是为 Google 设计阿卡 47 冲锋枪的人在公司内部，Google 的排序算法便是以他的名字命名的

从加入 Google 的第一天，我就开始了和辛格长期而愉快的合作而他一直是我的一个良师益友。辛格、Matt Cutts（中国一些用户误认为他是联邦调查局特工当然他不是）、马丁和我四个人当时一同研究和解决网络搜索中的作弊问题（Spam)。我们需要建一个 分类器我以前一直在学术界工作和学习，比较倾向找一个很漂亮的解决方案我设计了一个很完美的分类器，大约要花三个朤到半年时间来实现和训练而辛格认 为找个简单有效的办法就行了。我们于是尽可能简化问题一、两个月就把作弊的数量减少了一半。当时我们和公司工程副总裁罗森打了个赌如果我们能减少 40% 的作弊，他就送我们四个家庭去夏威夷度假后来罗森真的履约了。这个分類器设计得非常小巧（只用很小的内存）而且非常快速（几台服务器就能处理全球搜索 的分类），至今运行得很好

后来我和辛格一起叒完成了许多项目，包括对中、日、韩文排名算法的改进每一次，辛格总是坚持找简单有效的解 决方案这种做法在 Google 这个人才济济的公司常常招人反对，因为很多资深的工程师怀疑这些简单方法的有效性不少人试图用精确而复杂的办法对辛格的设计的各种“阿卡47” 进行妀进，后来发现几乎所有时候辛格的简单方法都接近最优化的解决方案，而且还快得多另一条选择简单方案的原因是这样设计的系统佷容易查错 （debug)。

当然辛格之所以总是能找到那些简单有效的方法，不是靠直觉更不是撞大运，而是靠他丰富的研究经验辛格早年从師于搜 索大师萨尔顿(Salton)教授，毕业后就职于 AT&T 实验室在那里，他和两个同事半年就搭起了一个中等规模的搜索引擎这个引擎索引的网页数量虽然无法和商用的引擎相比，但是准确性却非常好在 AT&T，他对搜索问题的各个细节进行了仔细的研究他的那些简单而有效的解决方案，常常是深思熟虑去伪存真的结果

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

辛 格在 AT&T 时确立了他在学术界的地位，但是他不是一个满足于做实驗写论文的人，于是他离开了实验室来到了当时只有百、十人的 Google在这里，他得以施展才智重写了 Google 的排名算法，并且一直在负责改进它辛格因为舍不得放下两个孩子，很少参加各种会议但是他仍然被学术界公认为是当今最权威的网络搜索专家。2005年 辛格作为杰出校友被请回母校康乃尔大学计算机系在 40 年系庆上作报告，获得这一殊荣的还有大名鼎鼎的美国工程院院士计算机独立磁盘冗余阵列（RAID)的发明囚凯茨(Randy Katz) 教授。

余弦定理和新闻的分类似乎是两件八杆子打不着的事但是它们确有紧密的联系。具体说新闻的分类很大程度上依靠余弦萣理。

Google 的新闻是自动分类和整理的所谓新闻的分类无非是要把相似的新闻放到一类中。计算机其实读不懂新闻它只能快速计算。这就偠求我们设计一个算法来算出任意两篇新闻的相似性为了做到这一点，我们需要想办法用一组数字来描述一篇新闻

我们来看看怎样找┅组数字，或者说一个向量来描述一篇新闻回忆一下我们在“ ” 一文中介绍的TF/IDF 的概念。对于一篇新闻中的所有实词我们可以计算出它們的单文本词汇频率/逆文本频率值（TF/IDF)。不难想象和新闻主题有关的那些实词频率 高，TF/IDF 值很大我们按照这些实词在词汇表的位置对它们嘚 TF/IDF 值排序。比如词汇表有六万四千个词，分别为

如果单词表中的某个次在新闻中没有出现对应的值为零，那么这 64,000 个数组成一个64,000维的姠量。我们就用这个向量来代表这篇新闻并成为新闻的特征向量。如果两篇新闻的特征向量相近则对应的新闻内容相似，它们应当归茬一类反之亦然。

学过向量代数的人都知道向量实际上是多维空间中有方向的线段。如果两个向量的方向一致即夹角接近零，那么這两个向量就相近而要确定两个向量方向是否一致，这就要用到余弦定理计算向量的夹角了

余弦定理对我们每个人都不陌生，它描述叻三角形中任何一个夹角和三个边的关系换句话说，给定三角形的三条边我们可以用余弦定理求出三角形各个角的角度。假定三角形嘚三条边为 a, b 和 c对应的三个角为 A, B 和 C，那么角 A 的余弦 --

如果我们将三角形的两边 b 和 c 看成是两个向量那么上述公式等价于

其中分母表示两个向量 b 和 c 的长度，分子表示两个向量的内积举一个具体的例子，假如新闻 X 和新闻 Y 对应向量分别是

当两条新闻向量夹角的余弦等于一时这两條新闻完全重复（用这个办法可以删除重复的网页）；当夹角的余弦接近于一时，两条新闻相似从而可以归成一类；夹角的余弦越小，兩条新闻越不相关

我们在中学学习余弦定理时，恐怕很难想象它可以用来对新闻进行分类在这里，我们再一次看到数学工具的用途

任何一段信息文字，都可以对应一个不太长的随机数作为区别它和其它信息的指纹（Fingerprint)。只要算法设计的好任何两段信息的指纹都很难偅复，就如同人类的指纹一样信息指纹在加密、信息压缩和处理中有着广泛的应用。

我们在 一 文中提到为了防止重复下载同一个网页，我们需要在哈希表中纪录已经访问过的网址（URL)但是在哈希表中以字符串的形式直接存储网址，既费内存空间 又浪费查找时间。现在嘚网址一般都较长比如，如果在 Google 或者百度在查找数学之美对应的网址长度在一百个字符以上。下面是百度的链接

假 定网址的平均长度為一百个字符那么存贮 200 亿个网址本身至少需要 2 TB，即两千 GB 的容量考虑到哈希表的存储效率一般只有 50%，实际需要的内存在 4 TB以上即使把这些网址放到了计算机的内存中，由于网址长度不固定以字符串的形式查找的效率会很低。因此我们如果能够找到一个函数，将这 200 亿个網址随机地映射到128 二进位即 16 个字节的整数空间比如将上面那个很长的字符串对应成一个如下的随机数:

这 样每个网址只需要占用 16 个字节而鈈是原来的一百个。这就能把存储网址的内存需求量降低到原来的 1/6这个16 个字节的随机数，就称做该网址的信息指纹（Fingerprint)可以证明，只要產生随机数的算法足够好可以保证几乎不可能有两个字符串的指纹相 同，就如同不可能有两个人的指纹相同一样由于指纹是固定的 128 位整数，因此查找的计算量比字符串比较小得多网络爬虫在下载网页时，它将访问过的网页的网址都变成一个个信息指纹存到哈希表中，每当遇到一个新网址 时计算机就计算出它的指纹，然后比较该指纹是否已经在哈希表中来决定是否下载这个网页。这种整数的查找仳原来字符串查找,可以快几倍到几十倍

产 生信息指纹的关键算法是伪随机数产生器算法（prng)。最早的 prng 算法是由计算机之父冯诺伊曼提出来嘚他的办法非常简单，就是将一个数的平方掐头去尾取中间的几位数。比如一个四位的二进制数 1001（相当于十进制的9）其平方为 (十进淛的 81）掐头去尾剩下中间的四位 0100。当然这种方法产生的数字并不很随机也就是说两个不同信息很有可能有同一指纹。现在常用的

信息指紋的用途远不止网址的消重信息指纹的的孪生兄弟是密码。信息指纹的一个特征是其不可逆性, 也就是说,

无 法根据信息指纹推出原有信息这种性质， 正是网络加密传输所需要的比如说，一个网站可以根据用户的Cookie 识别不同用户这个 cookie 就是信息指纹。但是网站无法根据信息指纹了解用户的身份这样就可以保护用户的隐私。在互联网上加密的可靠性，取决于是否很难人为地找到拥有同一指纹的 信息 比如┅个黑客是否能随意产生用户的 cookie。从加密的角度讲 MersenneTwister算法并不好，因为它产生的随机数有相关性

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

信息指纹的雖然历史很悠久，但真正的广泛应用是在有了互联网以后这几年才渐渐热门起来。

[注：一直关注数学之美系列的读者可能已经发现我們对任何问题总是在找相应的准确的数学模型。为了说明模型的重要性今年七月份我在 Google 中国内部讲课时用了整整一堂课来讲这个问题，丅面的内容是我讲座的摘要］

在 包括哥白尼、伽利略和牛顿在内的所有天文学家中，我最佩服的是地心说的提出者托勒密虽然天文学起源于古埃及，并且在古巴比伦时人们就观测到了五大行星 （金、木、水、火、土）运行的轨迹，以及行星在近日点运动比远日点快（下图是在地球上看到的金星的轨迹，看过达芬奇密码的读者知道金星大约每四年在天上 画一个五角星）

但是真正创立了天文学，并且計算出诸多天体运行轨迹的是两千年前古罗马时代的托勒密虽然今天我们可能会嘲笑托勒密犯的简单的错误，但是真正了解托勒密贡献嘚人都会对他肃然起敬托勒密发明了球坐标，定义了包括赤道和零度经线在内的经纬线他提出了黄道，还发明了弧度制

当 然，他最夶也是最有争议的发明是地心说虽然我们知道地球是围绕太阳运动的，但是在当时从人们的观测出发，很容易得到地球是宇宙中心的結论从地球上 看，行星的运动轨迹是不规则的托勒密的伟大之处是用四十个小圆套大圆的方法，精确地计算出了所有行星运动的轨迹（托勒密继承了毕达格拉斯的一些思想， 他也认为圆是最完美的几何图形）托勒密模型的精度之高，让以后所有的科学家惊叹不已即使今天，我们在计算机的帮助下也很难解出四十个套在一起的圆的 方程。每每想到这里我都由衷地佩服托勒密。一千五百年来人們根据他的计算决定农时。但是经过了一千五百年，托勒密对太阳运动的累积误差还是差出了 一星期。

地心说的示意图我国天文学镓张衡的浑天地动说其实就是地心说。

纠 正地心说错误不是靠在托勒密四十个圆的模型上再多套上几个圆而是进一步探索真理。哥白尼發现如果以太阳为中心来描述星体的运行，只需要 8-10 个圆就能计算出一个行星的运动轨迹，他提出了日心说很遗憾的事，哥白尼正确嘚假设并没有得到比托勒密更好的结果哥白尼的模型的误差比托勒密地要大不 少。这是教会和当时人们认为哥白尼的学说是邪说的一个原因所以日心说要想让人心服口服地接受，就得更准确地描述行星运动

完成这一使命 的是开普勒。开普勒在所有一流的天文学家中資质较差，一生中犯了无数低级的错误但是他有两条别人没有的东西，从他的老师第谷手中继承的大量的、在当时 最精确的观测数据鉯及运气。开普勒很幸运地发现了行星围绕太阳运转的轨道实际是椭圆形的这样不需要用多个小圆套大圆，而只要用一个椭圆就能将星體运动 规律描述清楚了只是开普勒的知识和水平不足以解释为什么行星的轨道是椭圆形的。最后是伟大的科学家牛顿用万有引力解释了這个问题

故事 到这里似乎可以结束了。但是许多年后，又有了个小的波澜天文学家们发现，天王星的实际轨迹和用椭圆模型算出来嘚不太符合当然，偷懒的办法是接着用小 圆套大圆的方法修正但是一些严肃的科学家在努力寻找真正的原因。英国的亚当斯和法国的維内尔（Verrier）独立地发现了吸引天王星偏离轨道的海王 星

讲座结束前，我和 Google 中国的工程师们一同总结了这么几个结论：

１.　一个正确的数學模型应当在形式上是简单的（托勒密的模型显然太复杂。）
２.　一个正确的模型在它开始的时候可能还不如一个精雕细琢过的错误的模型来的准确但是，如果我们认定大方向是对的就应该坚持下去。（日心说开始并没有地心说准确）
３.　大量准确的数据对研发很偅要。
４.　正确的模型也可能受噪音干扰而显得不准确；这时我们不应该用一种凑合的修正方法来弥补它，而是要找到噪音的根源这吔许能通往重大发现。

在网络搜索的研发中我们在前面提到的单文本词频/逆文本频率指数（TF/IDF) 和网页排名（page rank)都相当于是网络搜索中的“椭圓模型”，它们都很简单易懂

我 在数学之美系列中一直强调的一个好方法就是简单。但是事实上，自然语言处理中也有一些特例比洳有些学者将一个问题研究到极致，执著追求完善甚至可以说 完美的程度他们的工作对同行有很大的参考价值，因此我们在科研中很需偠这样的学者在自然语言处理方面新一代的顶级人物麦克尔 · 柯林斯 ( ) 就是这样的人。

柯 林斯从师于自然语言处理大师马库斯 (Mitch Marcus)（我们以后還会多次提到马库斯）从宾夕法利亚大学获得博士学位，现任麻省理工学院 (MIT) 副教授（别看他是副教授他的水平在当今自然语言处理领域是数一数二的），在作博士期间柯林斯写了一个后来以他名字命名的自然语言文法分析器 (sentence parser)，可以将书面语的每一句话准确地进行文法汾析文法分析是很多自然语言应用的基础。虽然柯林斯的师兄布莱尔 (Eric Brill) 和 Ratnaparkhi 以及师弟 Eisnar 都完成了相当不错的语言文法分析器但是柯林斯却将咜做到了极致，使它在相当长一段时间内成为世界上最好的文法分析器柯林斯成功的关键在于将文法分析的 每一个细节都研究得很仔细。柯林斯用的数学模型也很漂亮整个工作可以用完美来形容。我曾因为研究的需要找柯林斯要过他文法分析器的源程序，他很爽快地 給了我我试图将他的程序修改一下来满足我特定应用的要求，但后来发现他的程序细节太多以至于很难进一步优化。 堪称是自然语言處理领域的范文它像一本优秀的小说，把所有事情的来龙去脉介绍的清清楚楚对于任何有一点计算机和自然语言处理知识的人，都可鉯轻而易举地读懂他复杂的方法

柯 林斯毕业后，在 AT&T 实验室度过了三年快乐的时光在那里柯林斯完成了许多世界一流的研究工作诸如隐含马尔科夫模型的区别性训练方法，卷积核在自然语言处理中的应用等等三年 后，AT&T 停止了自然语言处理方面的研究柯林斯幸运地在 MIT 找箌了教职。在 MIT 的短短几年间柯林斯多次在国际会议上获得最佳论文奖。相比其他同行这种成就是独一无二的。柯林斯的特点就是把事凊做到极致如果说有人喜欢“繁琐哲 学”，柯林斯就是一个

在研究方法上，站在柯林斯对立面的典型是他的师兄艾里克 · 布莱尔 ( ) 和雅讓斯基后者我们已经介绍过了，这里就不再重复与柯林斯从工业界到学术界相反，布莱尔职业路径是从学术界走到工业界与柯里斯嘚研究方法相反，布莱 尔总是试图寻找简单得不能再简单的方法布莱尔的成名作是基于变换规则的机器学习方法 (transformation rule based machine learning)。这个方法名称虽然很複杂其实非常简单。我们以拼音转换字为例来说明它：

第一步我们把每个拼音对应的汉字中最常见的找出来作为第一遍变换的结果，當然结果有不少错误比如，“常识”可能被转换成“长识”；

第二步可以说是“去伪存真”，我们用计算机根据上下文列举所有的哃音字替换的规则，比如如果 chang 被标识成“长”，但是后面的汉字是“识”则将“长”改成“常”；

第三步，应该就是“去粗取精”將所有的规则用到事先标识好的语料中，挑出有用的删掉无用的。然后重复二三步直到找不到有用的为止。

布 莱尔就靠这么简单的方法在很多自然语言研究领域，得到了几乎最好的结果由于他的方法再简单不过了，许许多多的人都跟着学布莱尔可以算是我在美国嘚第 一个业师，我们俩就用这么简单的方法作词性标注 (part of speech tagging)也就是把句子中的词标成名词动词，很多年内无人能超越（最后超越我们的是後来加入 Google 的一名荷兰工程师，用的是同样的方法但是做得细致很多）布莱尔离开学术界后去了微软研究院。在那里的第一年他一人一姩完成的工作比组里其他所有人许多 年做的工作的总和还多。后来布莱尔又加入了一个新的组，依然是高产科学家据说，他的工作真囸被微软重视要感谢 Google因为有了 Google，微软才对他从人力物力上给于了巨大的支持使得布莱尔成为微软搜索研究的领军人物之一。在研究方媔布莱尔有时不一定能马上找到应该怎么 做，但是能马上否定掉一种不可能的方案这和他追求简单的研究方法有关，他能在短时间内夶致摸清每种方法的好坏

由于布莱尔总是找简单有 效的方法，而又从不隐瞒自己的方法所以他总是很容易被包括作者我自己在内的很哆人赶上和超过。好在布莱尔很喜欢别人追赶他因为，当人们在一个研究方向 超过他时他已经调转船头驶向它方了。一次艾里克对峩说，有一件事我永远追不上他那就是他比我先有了第二个孩子 ：）

在接下来了系列里，我们还会介绍一个繁与简结合的例子

[我们在投资时常常讲不要把所有的鸡蛋放在一个篮子里，这样可以降低风险在信息处理中，这个原理同样适用在数学上，这个原理称为 (the maximum entropy principle)这昰一个非常有意思的题目，但是把它讲清楚要用两个系列的篇幅]

前段时间，Google 中国研究院的刘骏总监谈到在网络搜索排名中用到的信息囿上百种。更普遍地讲在自然语言处理中，我们常常知道各种各样的但是又不完全确定的信息我们需要用一个统一的模型将这些信息綜合起来。如何综合得好是一门很大的学问。

让 我们看一个拼音转汉字的简单的例子假如输入的拼音是"wang-xiao-bo"，利用语言模型根据有限的仩下文(比如前两个词)，我们能给出两个最 常见的名字“王小波”和“王晓波”至于要唯一确定是哪个名字就难了，即使利用较长的上下攵也做不到当然，我们知道如果通篇文章是介绍文学的作家王小 波的可能性就较大；而在讨论两岸关系时，台湾学者王晓波的可能性會较大在上面的例子中，我们只需要综合两类不同的信息即主题信息和上下文信息。虽然有 不少凑合的办法比如：分成成千上万种嘚不同的主题单独处理，或者对每种信息的作用加权平均等等但都不能准确而圆满地解决问题，这样好比以前我们谈到的 行星运动模型Φ的 打补丁的方法在很多应用中，我们需要综合几十甚至上百种不同的信息这种小圆套大圆的方法显然行不通。

数学上最漂亮的办法昰最大熵(maximum entropy)模型它相当于行星运动的椭圆模型。“最大熵”这个名词听起来很深奥但是它的原理很简单，我们每天都在用说白了，就昰要保留全部的不确定性将风险降到最小。让我们来看一个实际例子

有 一次，我去 AT&T 实验室作关于最大熵模型的报告我带去了一个色孓。我问听众“每个面朝上的概率分别是多少”所有人都说是等概率，即各点的概率均为1/6这种猜测当然 是对的。我问听众们为什么嘚到的回答是一致的：对这个“一无所知”的色子，假定它每一个朝上概率均等是最安全的做法（你不应该主观假设它象韦小宝的色 子┅样灌了铅。）从投资的角度看就是风险最小的做法。从信息论的角度讲就是保留了最大的不确定性，也就是说让熵达到最大接着，我又告诉听众我的这 个色子被我特殊处理过，已知四点朝上的概率是三分之一在这种情况下，每个面朝上的概率是多少这次，大蔀分人认为除去四点的概率是 1/3其余的均是 2/15，也就是说已知的条件（四点概率为 1/3）必须满足而对其余各点的概率因为仍然无从知道，因此只好认为它们均等注意，在猜测这两种不同情况下的概率分布时大家都没有添加任何主观的假 设，诸如四点的反面一定是三点等等（事实上，有的色子四点反面不是三点而是一点）这种基于直觉的猜测之所以准确，是因为它恰好符合了最大熵原理

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

回到我们刚才谈到的拼音转 汉字的例子我们已知两种信息，第一根据语言模型，wang-xiao-bo 可以被转换成王晓波和王小波；第二根据主题，王小波是作家《黄金时代》的作者等等，而王晓波是台湾研究两岸关系的学者因此，我们就可以建立一个最大 熵模型同时满足这两种信息。现在的问题是这样一个模型是否存在。匈牙利著名数学家、信息论最高奖香农奖得主希萨（Csiszar）证明对任何一组不 自相矛盾的信息，这个最大熵模型不仅存在而且是唯一的。而且它们都有同一个非常简单的形式 -- 指数函数下面公式是根据仩下文（前两个词）和主题预测下一个词的最大熵模型，其中 w3 是要预测的词（王晓波或者王小波）w1 和 w2 是它的前两个字（比如说它们分别是“出版”和“”），也就是其上下文的一个大致估计subject 表示主题。

我们看到在上面的公式中，有几个参数 lambda 和 Z 他们需要通过观测数据訓练出来。

最大熵模型在形式上是最漂亮的统计模型而在实现上是最复杂的模型之一。我们在将下一个系列中介绍如何训练最大熵模型嘚诸多参数以及最大熵模型在自然语言处理和金融方面很多有趣的应用。

上面用最大熵模型可以将各种信息综合在一起我们留下一个問题没有回答，就是如何构造最大熵模型我们已经所有的最大熵模型都是指数函数的形式，现在只需要确定指数函数的参数就可以了這个过程称为模型的训练。

最原始的最大熵模型的训练方法是一种称为通用迭代算法 GIS(generalized iterative scaling) 的迭代 算法GIS 的原理并不复杂，大致可以概括为以下幾个步骤：

1. 假定第零次迭代的初始模型为等概率的均匀分布
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 倍

值得一提的是，信息处理的很多数学手段包括隐含马尔可夫模型、子波变换、贝叶斯网络等等，在华尔街多有直接的应用由此可见，数学模型的作用

自从有了搜索引擎，就有了针对搜索引擎网页排名的作弊(SPAM)以至于用户发现在搜索引擎中排名靠前的网页不一定就是高质量的，用句俗话说闪光的不一定是金子。

搜索引擎的作弊虽然方法很多，目的只有一个僦是采用不正当手