数学之美－、统计语言模型 ...........................................................................................................2二、谈谈中文分词 ...........................................................................................................4三、隐含马尔可夫模型在语言处理中的应用 ...............................................................7四、数学之美系列四 — 怎样度量信息 .......................................................................9五、简单之美：布尔代数和搜索引擎的索引 .............................................................11六、图论和网络爬虫 (Web Crawlers)..........................................................................14七、信息论在信息处理中的应用 .................................................................................16八、贾里尼克的故事和现代语言处理 .........................................................................18九、如何确定网页和查询的相关性 .............................................................................21十、有限状态机和地址识别 .........................................................................................24十一、 Google 阿卡 47 的制造者阿米特 . 辛格博士 ..................................................26十二、余弦定理和新闻的分类 .....................................................................................28十三、信息指纹及其应用 .............................................................................................31十四、谈谈数学模型的重要性 .....................................................................................33十五、繁与简 自然语言处理的几位精英 ...................................................................36十六、不要把所有的鸡蛋放在一个篮子里 -- 谈谈最大熵模型 （上） ...............38十六、不要把所有的鸡蛋放在一个篮子里 最大熵模型 （下） .........................40十七、闪光的不一定是金子 谈谈搜索引擎作弊问题 (Search Engine Anti-SPAM)..42十八、矩阵运算和文本处理中的分类问题 .................................................................44十九、马尔可夫链的扩展 贝叶斯网络 (Bayesian Networks) ...................................47二十、自然语言处理的教父 马库斯 ...........................................................................49二十一、布隆过滤器（ Bloom Filter ） ........................................................................51二十二、谈谈密码学的数学原理 .................................................................................53二十三、输入一个汉字需要敲多少个键 — 谈谈香农第一定律 .............................57-----------------------------------------------------Page 1-----------------------------------------------------－、统计语言模型2006 年 4 月 3 日 上午 08:15:00从本周开始，我们将定期刊登 Google 科学家吴军写的《数学之美》系列文章， 介绍数学在信息检索和自然语言处理中的主导作用和奇妙应用。发表者: 吴军, Google 研究员前言也 许大家不相信，数学是解决信息检索和自然语言处理的最好工具。它能非常 清晰地描述这些领域的实际问题并且给出漂亮的解决办法。每当人们应用数学工 具解决一 个语言问题时，总会感叹数学之美。我们希望利用 Google 中文黑板 报这块园地，介绍一些数学工具，以及我们是如何利用这些工具来开发 Google 产品的。系列一： 统计语言模型 (Statistical Language Models)Google 的使命是整合全球的信息，所以我们一直致力于研究如何让机器对信息、 语言做最好的理解和处理。长期以来，人类一直梦想着能让机器代替人来翻译语 言、识别语 音、认识文字（不论是印刷体或手写体）和进行海量文献的自动检 索，这就需要让机器理解语言。但是人类的语言可以说是信息里最复杂最动态的 一部分。为了解决 这个问题，人们容易想到的办法就是让机器模拟人类进行学 习 - 学习人类的语法、分析语句等等。尤其是在乔姆斯基（Noam Chomsky 有史 以来最伟大的语言学家）提出 “形式语言” 以后，人们更坚定了利用语法规则 的办法进行文字处理的信念。遗憾的是，几十年过去了，在计算机处理语言领域， 基于这个语法规则的方法几乎毫无突破。其实早在几十年前，数学家兼信息论的祖师爷 香农 (Claude Shannon)就提出了 用数学的办法处理自然语言的想法。遗憾的是当时的计算机条件根本无法满足大 量信息处理的需要，所以他这个想法当时并没有被人们重视。七十年代初，有了 大规模集成电路的快速计算机后，香农的梦想才得以实现。首先成功利用数学方法解决自然语言处理问题的是语音和语言处理大师贾里尼 克 ( Fred Jelinek ) 。 当 时 贾 里 尼 克 在 IBM 公 司 做 学 术 休 假 (Sabbatical Leave)，领导了一批杰出的科学家利用大型计算机来处理人类语言问题。统计语 言模型就是在那个时候提出的。给大家举个例子：在很多涉及到自然语言处理的领域，如机器翻译、语音识别、 印刷体或手写体识别、拼写纠错、汉字输入和文献查询中，我们都需要知道一个 文字序列是否能构成一个大家能理解的句子，显示给使用者。对这个问题，我们 可以用一个简单的统计模型来解决这个问题。-----------------------------------------------------Page 2-----------------------------------------------------如 果 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 多努力 一分，用户就多一分搜索的喜悦-----------------------------------------------------Page 3-----------------------------------------------------二、谈谈中文分词2006 年 4 月 10 日 上午 08:10:00发表者: 吴军， Google 研究员谈谈中文分词----- 统计语言模型在中文处理中的一个应用上回我们谈到 利用统计语言模型进行语言处理 ，由于模型是建立在词的基础上 的，对于中日韩等语言，首先需要进行分词。例如把句子 “中国航天官员应邀 到美国与太空总署官员开会。”分成一串词：中国 / 航天 / 官员 / 应邀 / 到 / 美国 / 与 / 太空 / 总署 / 官员 / 开 会。最容易想到的，也是最简单的分词办法就是查字典。这种方法最早是由北京航天 航空大学的梁南元教授提出的。用 “查字典” 法，其实就是我们把一个句子从左向右扫描一遍，遇到字典里有 的词就标识出来，遇到复合词（比如 “上海大学”）就找最长的词匹配，遇到 不认识的字串就分割成单字词，于是简单的分词就完成了。这种简单的分词方法 完全能处理上面例子中的句子。八十年代， 哈工大的王晓龙博士 把 它理论化， 发展成最少词数的分词理论，即一句话应该分成数量最少的词串。这种方法一个 明显的不足是当遇到有二义性 （有双重理解意思）的分割时就无能为力了。比 如，对短语 “发展中国家” 正确的分割是“发展-中-国家”，而从左向右查字 典的办法会将它分割成“发展-中国-家”，显然是错了。另外，并非所有的最长 匹配都一定是正确的。比如 “上海大学城书店”的正确分词应该是 “上海-大 学城-书店，” 而不是 “上海大学-城-书店”。九十年代以前，海内外不少学者试图用一些文法规则来解决分词的二义性问题， 都不是很成功。90 年前后，清华大学的郭进博士用统计语言模型成功解决分词 二义性问题，将汉语分词的错误率降低了一个数量级。利用统计语言模型分词的方法，可以用几个数学公式简单概括如下：我们假定一个句子S可以有几种分词方法，为了简单起见我们假定有以下三种： A1, A2, A3, ..., Ak, B1, B2, B3, ..., Bm C1, C2, C3, ..., Cn其中，A1, A2, B1, B2, C1, C2 等等都是汉语的词。那么最好的一种分词方法 应该保证分完词后这个句子出现的概率最大。也就是说如果 A1,A2,..., Ak 是-----------------------------------------------------Page 4-----------------------------------------------------最好的分法，那么 （P 表示概率）：P (A1, A2, A3, ..., Ak） 〉 P (B1, B2, B3, ..., Bm), 并且 P (A1, A2, A3, ..., Ak） 〉 P(C1, C2, C3, ..., Cn)因此，只要我们利用上回提到的统计语言模型计算出每种分词后句子出现的概 率，并找出其中概率最大的，我们就能够找到最好的分词方法。当然，这里面有一个实现的技巧。如果我们穷举所有可能的分词方法并计算出每 种可能性下句子的概率，那么计算量是相当大的。因此，我们可以把它看成是一 个 动态规划 （Dynamic Programming) 的问题，并利用 “维特比”（ Viterbi ） 算 法快速地找到最佳分词。在清华大学的郭进博士以后，海内外不少学者利用统计的方法，进一步完善中文 分词。其中值得一提的是清华大学孙茂松教授和香港科技大学吴德凯教授的工 作。需 要指出的是，语言学家对词语的定义不完全相同。比如说 “北京大学”，有 人认为是一个词，而有人认为该分成两个词。一个折中的解决办法是在分词的同 时，找到复合词的嵌套结构。在上面的例子中，如果一句话包含 “北京大学” 四个字，那么先把它当成一个四字词，然后再进一步找出细分词 “北京” 和 “大学”。这种方法是最早是郭进在 “Computational Linguistics” （《计 算机语言学》）杂志上发表的，以后不少系统采用这种方法。一般来讲，根 据不同应用，汉语分词的颗粒度大小应该不同。比如，在机器翻 译中，颗粒度应该大一些，“北京大学”就不能被分成两个词。而在语音识别中， “北京大学”一般 是被分成两个词。因此，不同的应用，应该有不同的分词系 统。Google 的葛显平博士和朱安博士，专门为搜索设计和实现了自己的分词系 统。也 许你想不到，中文分词的方法也被应用到英语处理，主要是手写体识别中。 因为在识别手写体时，单词之间的空格就不很清楚了。中文分词方法可以帮助判 别英语单 词的边界。其实，语言处理的许多数学方法通用的和具体的语言无关。 在 Google 内，我们在设计语言处理的算法时，都会考虑它是否能很容易地适用 于各种自然语言。这样，我们才能有效地支持上百种语言的搜索。对中文分词有兴趣的读者，可以阅读以下文献：1. 梁南元书面汉语自动分词系统m/demo/LiangNanyuan-JCIP-1987.pdf2. 郭进统计语言模型和汉语音字转换的一些新结果m/demo/GuoJin-JCIP-1993.pdf-----------------------------------------------------Page 5-----------------------------------------------------3. 郭进Critical Tokenization and its Properties u/J/J97/J97-4004.pdf4. 孙茂松Chinese word segmentation without using lexicon and hand-crafted training datag/m?coll=GUIDE&dl=GUIDE&id=980775-----------------------------------------------------Page 6-----------------------------------------------------三、隐含马尔可夫模型在语言处理中的应用2006 年 4 月 17 日 上午 08:01:00发表者：吴军，Google 研究员前言：隐含马尔可夫模型是一个数学模型，到目前为之，它一直被认为是实现快 速精确的语音识别系统的最成功的方法。复杂的语音识别问题通过隐含马尔可夫 模型能非常简单地被表述、解决，让我不由由衷地感叹数学模型之妙。自 然语言是人类交流信息的工具。很多自然语言处理问题都可以等同于通信系 统中的解码问题 -- 一个人根据接收到的信息，去猜测发话人要表达的意思。这 其实就象通信中，我们根据接收端收到的信号去分析、理解、还原发送端传送过 来的信息。以下该图就表 示了一个典型的通信系统：其中 s1，s2，s3...表示信息源发出的信号。o1, o2, o3 ... 是接受器接收到 的信号。通信中的解码就是根据接收到的信号 o1, o2, o3 ...还原出发送的信 号 s1，s2，s3...。其 实我们平时在说话时，脑子就是一个信息源。我们的喉咙（声带），空气， 就是如电线和光缆般的信道。听众耳朵的就是接收端，而听到的声音就是传送过 来的信 号。根据声学信号来推测说话者的意思，就是语音识别。这样说来，如 果接收端是一台计算机而不是人的话，那么计算机要做的就是语音的自动识别。 同样，在计算 机中，如果我们要根据接收到的英语信息，推测说话者的汉语意 思，就是机器翻译； 如果我们要根据带有拼写错误的语句推测说话者想表达的 正确意思，那就是自动纠错。那么怎么根据接收到的信息来推测说话者想表达的意思呢？我们可以利用叫做 “ 隐含马尔可夫模型 ” （Hidden Markov Model）来解决这些问题。以语音识别 为例，当我们观测到语音信号 o1,o2,o3 时，我们要根据这组信号推测出发送的 句子 s1,s2,s3。显然，我们应该在所有可能的句子中找最有可能性的一个。用 数学语言来描述，就是在已知 o1,o2,o3,...的情况下，求使得条件概率 P (s1,s2,s3,...|o1,o2,o3....) 达到最大值的那个句子 s1,s2,s3,...当然，上面的概率不容易直接求出，于是我们可以间接地计算它。利用贝叶斯公 式并且省掉一个常数项，可以把上述公式等价变换成P(o1,o2,o3,...|s1,s2,s3....) * P(s1,s2,s3,...) 其中P(o1,o2,o3,...|s1,s2,s3....) 表示某句话 s1,s2,s3...被读成 o1,o2,o3,...-----------------------------------------------------Page 7-----------------------------------------------------的可能性, 而P(s1,s2,s3,...) 表示字串 s1,s2,s3,...本身能够成为一个合乎情理的句子的 可能性，所以这个公式的意义是用发送信号为 s1,s2,s3...这个数列的可能性乘 以 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,...。满足上述两个假设的模型就叫隐含马尔可夫模型。我们之所以用“隐含”这个 词，是因为状态 s1,s2,s3,...是无法直接观测到的。隐 含马尔可夫模型的应用远不只在语音 识别中。在上面的公式中，如果我们把 s1,s2,s3,...当成中文，把 o1,o2,o3,...当成对应的英文，那么我们就能利用 这个模型解决机器翻译问题； 如果我们把 o1,o2,o3,...当成扫描文字得到的图 像特征，就能利用这个模型解决印刷体和手写体的识别。P (o1,o2,o3,...|s1,s2,s3....) 根据应用的不同而又不同的名称，在语音识别 中它被称为“声学模型” (Acoustic Model)， 在机器翻译中是“翻译模型” (Translation Model) 而在拼写校正中是“纠错模型” (Correction Model)。 而P (s1,s2,s3,...) 就是我们在系列一中提到的语言模型。在利用隐含马尔可夫模型解决语言处理问题前，先要进行模型的训练。 常用的 训练方法由伯姆（Baum）在 60 年代提出的，并以他的名字命名。隐含马尔可夫 模型在处理语言问题早期的成功应用是语音识别。七十年代，当时 IBM 的 Fred Jelinek (贾里尼克) 和卡内基·梅隆大学的 Jim and Janet Baker (贝克夫妇 ， 李开复的师兄师姐) 分别独立地提出用隐含马尔可夫模型来识别语音，语音识别 的错误率相比人工智能和模式匹配等方法降低了三倍 (从 30% 到 10%)。 八十 年代李开复博士坚持采用隐含马尔可夫模型的框架， 成功地开发了世界上第一 个大词汇量连续语音识别系统 Sphinx。我 最早接触到隐含马尔可夫模型是几乎二十年前的事。那时在《随机过程》（清 华“著名”的一门课）里学到这个模型，但当时实在想不出它有什么实际用途。 几年 后，我在清华跟随王作英教授学习、研究语音识别时，他给了我几十篇文 献。 我印象最深的就是贾里尼克和李开复的文章，它们的核心思想就是隐含马 尔可夫模型。复杂的语音识别问题居然能如此简单地被表述、解决，我由衷地感 叹数学模型 之妙。-----------------------------------------------------Page 8-----------------------------------------------------四、数学之美系列四 — 怎样度量信息2006 年 4 月 26 日 上午 08:11:00发表者：吴军，Google 研究员前言: Google 一直以 “整合全球信息，让人人能获取，使人人能受益” 为使 命。那么究竟每一条信息应该怎样度量呢？信息是个很抽象的概念。我们常常说信息很多，或者信息较少，但却很难说清楚 信息到底有多少。比如一本五十万字的中文书到底有多少信息量。直到 1948 年， 香农 提出了“ 信息熵 ”(shāng) 的概念，才解决了对信息的量化度量问题。一 条信息的信息量大小和它的不确定性有直接的关系。比如说，我们要搞清楚 一件非常非常不确定的事，或是我们一无所知的事情，就需要了解大量的信息。 相反，如 果我们对某件事已经有了较多的了解，我们不需要太多的信息就能把 它搞清楚。所以，从这个角度，我们可以认为，信息量的度量就等于不确定性的 多少。那 么我们如何量化的度量信息量呢？我们来看一个例子，马上要举行世界杯赛 了。大家都很关心谁会是冠军。假如我错过了看世界杯，赛后我问一个知道比赛 结果的观 众“哪支球队是冠军”？ 他不愿意直接告诉我， 而要让我猜，并且 我每猜一次，他要收一元钱才肯告诉我是否猜对了，那么我需要付给他多少钱才 能知道谁是冠军呢? 我可以把球队编上号，从 1 到 32， 然后提问： “冠军的 球队在 1-16 号中吗?” 假如他告诉我猜对了， 我会接着问： “冠军在 1-8 号 中吗?” 假如他告诉我猜错了， 我自然知道冠军队在 9-16 中。 这样只需要五 次， 我就能知道哪支球队是冠军。所以，谁是世界杯冠军这条消息的信息量只 值五块钱。当然，香农不是用钱，而是用 “比特”（bit）这个概念来度量信息量。 一个 比特是一位二进制数，计算机中的一个字节是八个比特。在上面的例子中，这条 消息的信息量是五比特。（如果有朝一日有六十四个队进入决赛阶段的比赛，那 么“谁世界杯冠军”的信息量就是六比特，因为我们要多猜一次。） 读者可能 已经发现, 信息量的比特数和所有可能情况的对数函数 log 有关。 (log32=5, log64=6。）有些读者此时可能会发现我们实际上可能不需要猜五次就能猜出谁是冠军，因为 象巴西、德国、意 大利这样的球队得冠军的可能性比日本、美国、韩国等队大 的多。因此，我们第一次猜测时不需要把 32 个球队等分成两个组，而可以把少 数几个最可能的球队分成一组，把其它队分成另一组。然后我们猜冠军球队是否 在那几只热门队中。我们重复这样的过程，根据夺 冠概率对剩下的候选球队分 组，直到找到冠军队。这样，我们也许三次或四次就猜出结果。因此，当每个球 队夺冠的可能性（概率）不等时，“谁世界杯冠军”的信 息量的信息量比五比 特少。香农指出，它的准确信息量应该是-----------------------------------------------------Page 9-----------------------------------------------------= -（p1*log p1 + p2 * log p2 +．．．＋p32 *log p32)，其 中，p1，p2 ， ．．．，p32 分别是这 32 个球队夺冠的概率。香农把它称 为“信息熵” (Entropy)，一般用符号 H 表示，单位是比特。有兴趣的读者可 以推算一下当 32 个球队夺冠概率相同时，对应的信息熵等于五比特。有数学基 础的读者还可以证明上面公式的值不可能大于五。对于任意一个随机变量 X（比 如得冠军的球队），它的熵定义如下：变量的不确定性越大，熵也就越大，把它搞清楚所需要的信息量也就越大。有 了“熵”这个概念，我们就可以回答本文开始提出的问题，即一本五十万字 的中文书平均有多少信息量。我们知道常用的汉字（一级二级国标）大约有 7000 字。假如每个字等概率，那么我们大约需要 13 个比特（即 13 位二进制数）表 示一个汉字。但汉字的使用是不平衡的。实际上，前 10% 的汉字占文本的 95% 以 上。因此，即使不考虑上下文的相关性，而只考虑每个汉字的独立的概率，那么， 每个汉字的信息熵大约也只有 8-9 个比特。如果我们再考虑上下文相关性，每 个汉字的信息熵只有 5 比特左右。所以，一本五十万字的中文书，信息量大约是 250 万比特。如果用一个好的算法压缩一下，整本书可以存成一个 320KB 的文 件。如果我们直接用两字节的国标编码存储这本书，大约需要 1MB 大小，是压 缩文件的三倍。这两个数量的差距，在信息论中称作“冗余度”（redundancy)。 需要指出的是我们这里讲的 250 万比特是个平均数，同样长度的书，所含的信 息量可以差很多。如果一本书重复的内容很多，它的信息量就小，冗余度就大。不同语言的冗余度差别很大，而汉语在所有语言中冗余度是相对小的。这和人们 普遍的认识“汉语是最简洁的语言”是一致的。在下一集中， 我们将介绍信息熵在信息处理中的应用以及两个相关的概念互信 息和相对熵。对中文信息熵有兴趣的读者可以读我和王作英教授在电子学报上合写的一篇文 章《语信息熵和语言模型的复杂度》-----------------------------------------------------Page 10-----------------------------------------------------五 、 简单之美：布尔代数和搜索引擎的索引2006 年 5 月 10 日 上午 09:10:00发表者: 吴军，Google 研究员[建立一个搜索引擎大致需要做这样几件事：自动下载尽可能多的网页；建立快 速 有 效 的 索 引 ； 根 据 相 关 性 对 网 页 进 行 公 平 准 确 的 排 序 。 我 们 在 介 绍 Google Page Rank (网页排名) 时已经谈到了一些排序的问题，这里我们谈谈索引问题， 以后我们还会谈如何度量网页的相关性，和进行网页自动下载。］世界上不可能有比二进制更简单的计数方法了，也不可能有比布尔运算更简单的 运算了。尽管今天每个搜索引擎都宣称自己如何聪明、多么智能化，其实从根本 上讲都没有逃出布尔运算的框框。布尔 （George Boole) 是十九世纪英国一位小学数学老师。他生前没有人认为他 是数学家。布尔在工作之余，喜欢阅读数学论著、思考数学问题。1854 年“ 思 维规律 ” （An Investigation of the Laws of Thought, on which are founded the Mathematical Theories of Logic and Probabilities）一书，第一次向人 们展示了如何用数学的方法解决逻辑问题。布尔代数简单得不能再简单了。运算的元素只有两个 1 （TRUE， 真) 和 0 （FALSE，假)。基本的运算只有“与”（AND)、“或” (OR) 和“非”（NOT) 三 种（后来发现，这三种运算都可以转换成“与”“非” ＡＮＤ－ＮＯＴ一种运 算）。全部运算只用下列几张真值表就能完全地描述清楚。AND | 1 0----------------------- 1 | 1 0 0 | 0 0这张表说明如果 AND 运算的两个元素有一个是 0，则运算结果总是 0。如果两 个元素都是 1，运算结果是 1。例如，“太阳从西边升起”这个判断是假的 (0),“水可以流动”这个判断是真的（1），那么，“太阳从西边升起并且水可 以流动”就是假的（0）。OR | 1 0----------------------- 1 | 1 1 0 | 1 0这张表说明如果OR运算的两个元素有一个是 1，则运算结果总是 1。如果两个元 素都是 0，运算结果是 0。比如说，“张三是比赛第一名”这个结论是假的（0）， “李四是比赛第一名”是真的（1），那么“张三或者李四是第一名”就是真的 （1）。-----------------------------------------------------Page 11-----------------------------------------------------NOT |-------------- 1 | 0 0 | 1这张表说明 NOT 运算把 1 变成 0，把 0 变成 1。比如，如果“象牙是白的” 是真的（1），那么“象牙不是白的”必定是假的（0）。读 者也许会问这么简单的理论能解决什么实际问题。布尔同时代的数学家们也 有同样的问题。事实上在布尔代数提出后 80 多年里，它确实没有什么像样的应 用，直到 1938 年香农在他的硕士论文中指出用布尔代数来实现开关电路，才使 得布尔代数成为数字电路的基础。所有的数学和逻辑运算，加、减、乘、除、乘 方、开方等等，全部 能转换成二值的布尔运算。现在我们看看文献检索和布尔运算的关系。对于一个用户输入的关键词，搜索引 擎要判断每篇文献是否含有这个关键 词，如果一篇文献含有它，我们相应地给 这篇文献一个逻辑值 -- 真（TRUE,或 1），否则，给一个逻辑值 -- 假（FALSE, 或 0）。比如我们要找有关原子能应用的文献，但并不想知道如何造原子弹。我 们可以这样写一个查询语句“原子能 AND 应用 AND (NOT 原子弹)”，表示符合 要求的文献必须同时满足三个条件： - 包含原子能 - 包含应用- 不包含原子弹一篇文献对于上面每一个条件，都有一个 True 或者 False 的答案，根据上述 真值表就能算出每篇文献是否是要找的。早期的文献检索查询系统大多基于数据库，严格要求查询语句符合布尔运算。今 天的搜索引擎相比之下要聪明的多，它自动把用户的查询语句转换成布尔运算的 算式。当然在查询时，不能将每篇文献扫描一遍，来看看它是否满足上面三个条 件，因此需要建立一个索引。最 简单索引的结构是用一个很长的二进制数表示一个关键字是否出现在每篇文 献中。有多少篇文献，就有多少位数，每一位对应一篇文献，1 代表相应的文献 有这个关键字，0 代表没有。比如关键字“原子能”对应的二进制数是 0100100001100001...，表示第二、第五、第九、第十、第十六篇文献包含着个 关键字。注 意，这个二进制数非常之长。同样，我们假定“应用”对应的二进 制数是 0010100110000001...。那么要找到同时包含“原子能”和“应用”的文 献时，只要将这两个二进制数进行布尔运算 AND。根据上面的真值表，我们知道 运算结果是 0000100000000001...。表示第五篇，第十六篇文献满足要求。注意，计算 机作布尔运算是非常非常快的。现在最便宜的微机都可以一次进行 三十二位布尔运算，一秒钟进行十亿次以上。当然，由于这些二进制数中绝大部 分位数都是零，我 们只需要记录那些等于 1 的位数即可。于是，搜索引擎的索 引就变成了一张大表：表的每一行对应一个关键词，而每一个关键词后面跟着一-----------------------------------------------------Page 12-----------------------------------------------------组数字，是包含该关键词 的文献序号。对于互联网的搜索引擎来讲，每一个网页就是一个文献。互联网的网页数量是巨 大的，网络中所用的词也非常非常多。因此这个索引 是巨大的，在万亿字节这 个量级。早期的搜索引擎（比如 Alta Vista 以前的所有搜索引擎），由于受计 算机速度和容量的限制，只能对重要的关键的主题词建立索引。至今很多学术杂 志还要求作者提供 3-5 个关键词。这样所有不常见的词和太常见的虚词就找不 到了。现在，为了保证对任何搜索都能提供相关的网页，所有的搜索引擎都是对 所有的词进行索引。为了网页 排名方便，索引中还需存有大量附加信息，诸如 每个词出现的位置、次数等等。因此，整个索引就变得非常之大，以至于不可能 用一台计算机存下。大家普遍的做法 就是根据网页的序号将索引分成很多份 （Shards)，分别存储在不同的服务器中。每当接受一个查询时，这个查询就被 分送到许许多多服务器中，这些服务器 同时并行处理用户请求，并把结果送到 主服务器进行合并处理，最后将结果返回给用户。不管索引如何复杂，查找的基本操作仍然是布尔运算。布 尔运算把逻辑和数学 联系起来了。它的最大好处是容易实现，速度快，这对于海量的信息查找是至关 重要的。它的不足是只能给出是与否的判断，而不能给出量化的 度量。因此， 所有搜索引擎在内部检索完毕后，都要对符合要求的网页根据相关性排序，然后 才返回给用户。-----------------------------------------------------Page 13-----------------------------------------------------六、 图论和网络爬虫 (Web Crawlers)2006 年 5 月 15 日 上午 07:15:00发表者: 吴军，Google 研究员[ 离散数学 是当代数学的一个重要分支，也是计算机科学的数学基础。它包括数 理逻辑、集合论、图论和近世代数四个分支。数理逻辑基于布尔运算，我们已经 介绍过了。这里我们介绍图论和互联网自动下载工具网络爬虫 (Web Crawlers) 之间的关系。顺便提一句，我们用 Google Trends 来搜索一下“离散数学”这 个词，可以发现不少有趣的现象。比如，武汉、哈尔滨、合肥和长沙市对这一数 学题目最有兴趣的城市。]我们 上回 谈到了如何建立搜索引擎的索引，那么如何自动下载互联网所有的网页 呢，它要用到图论中的遍历（Traverse) 算法。图论的起源可追溯到大数学家 欧拉 （Leonhard Euler）。1736 年欧拉来到德国 的哥尼斯堡（Konigsberg，大哲学家康德的故乡，现在是俄罗斯的加里宁格勒）， 发现当地市民们有一项消遣活动，就是试图将下图中的 每座桥恰好走过一遍并 回到原出发点，从来没有人成功过。欧拉证明了这件事是不可能的，并写了一篇 论文，一般认为这是图论的开始。图 论中所讨论的的图由一些节点和连接这些节点的弧组成。如果我们把中国的 城市当成节点，连接城市的国道当成弧，那么全国的公路干线网就是图论中所说 的图。关 于图的算法有很多，但最重要的是图的遍历算法，也就是如何通过弧 访问图的各个节点。以中国公路网为例，我们从北京出发，看一看北京和哪些城 市直接相连，比 如说和天津、济南、石家庄、南京、沈阳、大同直接相连。我 们可以依次访问这些城市，然后我们看看都有哪些城市和这些已经访问过的城市 相连，比如说北戴河、 秦皇岛与天津相连，青岛、烟台和济南相连，太原、郑 州和石家庄相连等等，我们再一次访问北戴河这些城市，直到中国所有的城市都-----------------------------------------------------Page 14-----------------------------------------------------访问过一遍为止。这种图的遍 历算法称为“广度优先算法”（BFS)，因为它先 要尽可能广地访问每个节点所直接连接的其他节点。另外还有一种策略是从北京 出发，随便找到下一个要访问的 城市，比如是济南，然后从济南出发到下一个 城市，比如说南京，再访问从南京出发的城市，一直走到头。然后再往回找，看 看中间是否有尚未访问的城市。这种方 法叫“深度优先算法”（DFS)，因为它 是一条路走到黑。这两种方法都可以保证访问到全部的城市。当然，不论采用哪 种方法，我们都应该用一个小本本，记录 已经访问过的城市，以防同一个城市 访问多次或者漏掉哪个城市。现在我们看看图论的遍历算法和搜索引擎的关系。互联网其实就是一张大图，我 们可以把每一个网页当作一个节点，把那些超链接（Hyperlinks)当作连接网页 的弧。很多读者可能已经注意到，网页中那些蓝色的、带有下划线的文字 背后 其实藏着对应的网址，当你点下去的的时候，浏览器是通过这些隐含的网址转到 相应的网页中的。这些隐含在文字背后的网址称为“超链接”。有了超链接，我 们可以从任何一个网页出发，用图的遍历算法，自动地访问到每一个网页并把它 们存起来。完成这个功能的程序叫做网络爬虫，或者在一些文献中称为"机器人" （Robot) 。 世 界 上 第 一 个 网 络 爬 虫 是 由 麻 省 理 工 学 院 (MIT) 的 学 生 马 休. 格 雷 （Matthew Gray)在 1993 年写成的。他给他的程序起了个名字叫“互联网漫游 者”("www wanderer")。以后的网络爬虫越写越复杂，但原理是一样的。我 们来看看网络爬虫如何下载整个互联网。假定我们从一家门户网站的首页出 发，先下载这个网页，然后通过分析这个网页，可以找到藏在它里面的所有超链 接，也就 等于知道了这家门户网站首页所直接连接的全部网页，诸如雅虎邮件、 雅虎财经、雅虎新闻等等。我们接下来访问、下载并分析这家门户网站的邮件等 网页，又能找 到其他相连的网页。我们让计算机不停地做下去，就能下载整个 的互联网。当然，我们也要记载哪个网页下载过了，以免重复。在网络爬虫中， 我们使用一个称为“ 哈希表 ”(Hash Table)的列表而不是一个记事本纪录网页 是否下载过的信息。现 在的互联网非常巨大，不可能通过一台或几台计算机服务器就能完成下载任 务。比如雅虎公司（Google 没有公开公布我们的数目，所以我这里举了雅虎的 索引大小为例）宣称他们索引了 200 亿个网页，假如下载一个网页需要一秒钟， 下载这 200 亿个网页则需要 634 年。因此，一个商业的网络爬虫需要有成千上 万个服务器，并且由快速网络连接起来。如何建立这样复杂的网络系统，如何协 调这些服务器的任务，就是网络设计和 程序设计的艺术了。-----------------------------------------------------Page 15-----------------------------------------------------七 、 信息论在信息处理中的应用我们已经介绍了 信息熵 ，它是信息论的基础，我们这次谈谈信息论在自然语言处理中的应用。先看看信息熵和语言模型的关系。我们在 系列一 中 谈到语言模型时，没有讲如何定量地衡 量一个语言模型的好坏，当然，读者会很自然地想到，既然语言模型能减少语音识别和机器 翻译的错误，那么就拿一个语音识 别系统或者机器翻译软件来试试，好的语言模型必然导 致错误率较低。这种想法是对的，而且今天的语音识别和机器翻译也是这么做的。但这种测 试方法对于研发语 言模型的人来讲，既不直接、又不方便，而且很难从错误率反过来定量 度量语言模型。事实上，在贾里尼克 ( Fred Jelinek ) 的人研究语言模型时，世界上既没有像样 的语音识别系统，更没有机器翻译。我们知道，语言模型是为了用上下文预测当前的文字， 模型越好，预测得越准，那么当前文字的不确定性就越小。信 息熵正是对不确定性的衡量，因此信息熵可以直接用于衡量统计语言模型的好坏。贾里 尼克从信息熵出发，定义了一个称为语言模型复杂度 (Perplexity) 的概念，直接衡量语言模 型的好坏。一个模型的复杂度越小，模型越好。李开复博士在介绍他发明的 Sphinx 语音识 别系统时谈到，如果不用任何语言模型（即零元语言模型）时，复杂度为 997 ，也就是说句 子中每个位置有 997 个可能的单词可以填入。如果（二元）语言模型只考虑前后词的搭配 不考虑搭配的概率时，复杂度为 60 。虽然它比不用语言模型好很多，但是和考虑了搭配概 率的二元语言模型相比要差很多，因为后者的复杂度只有 20 。信 息 论 中 仅 次 于 熵 的 另 外 两 个 重 要 的 概 念 是 “ 互 信 息 ” （ Mutual Information) 和 “ 相 对 熵 ” （ Kullback-Leibler Divergence) 。“ 互 信息 ” 是信息熵的引申概念，它是对两个随机事件相关性的度量。比如说今天随机事件 北京下雨和随机变量空气湿度的相关性就很大，但是和姚明所在的休斯敦火箭 队是否能赢 公牛队几乎无关。互信息就是用来量化度量这种相关性的。在自然语言处理中，经常要度量 一些语言现象的相关性。比如在机器翻译中，最难的问题是词 义的二义性（歧义性）问题。 比如 Bush 一词可以是美国总统的名字，也可以是灌木丛。（有一个笑话，美国上届总统候 选人凯里 Kerry 的名字被一些机器翻译系统翻译成了 " 爱尔兰的小母牛 " ， Kerry 在英语中另 外一个意思。）那么如何正确地翻译这个词呢？人们很容易想到要用语法、要分析语句等等。 其实，至今为止，没有一种语法能很好解决这个问题，真正 实用的方法是使用互信息。具 体 的 解决 办法 大 致如 下： 首 先从 大量 文 本中 找出 和 总统 布什 一 起出 现的 互 信息 最大 的 一些 词，比如总统、美国、国会、华盛顿等等，当 然，再用同样的方法找出和灌木丛一起出现 的互信息最大的词，比如土壤、植物、野生等等。有了这两组词，在翻译 Bush 时，看看 上下文中哪类相关的词多就可以了。这种方法最初是由吉尔 (Gale) ，丘奇 (Church) 和雅让斯 基 (Yarowsky) 提出的。当 时雅让斯基在宾西法尼亚大学是自然语言处理大师马库斯 (Mitch Marcus) 教授的博士 生，他很多时间泡在贝尔实验室丘奇等人的研究室里。也许是急于毕业，他在吉尔等人的帮 助下想出了一个最快也是最好地解决翻译中的二义性，就是上 述的方法，这个看上去简单 的方法效果好得让同行们大吃一惊。雅让斯基因而只花了三年就从马库斯那里拿到了博士， 而他的师兄弟们平均要花六年时间。-----------------------------------------------------Page 16-----------------------------------------------------信息论中另外一个重要的概念是 “ 相对熵 ” ，在有些文献中它被称为成 “ 交叉熵 ” 。在英语中是 Kullback-Leibler Divergence ， 是以它的两个提出者库尔贝克和莱伯勒的名字命名的。相对 熵用来衡量两个正函数是否相似，对于两个完全相同的函数，它们的相对熵等于零。在自然 语言处理中可 以用相对熵来衡量两个常用词（在语法上和语义上）是否同义，或者两篇文 章的内容是否相近等等。利用相对熵，我们可以到处信息检索中最重要的一个概念：词频 率 - 逆向文档频率（ TF/IDF) 。我们下回会介绍如何根据相关性对搜索出的网页进行排序，就要 用的餐 TF/IDF 的概念。另外，在新闻的分类中也要用到相对熵和 TF/IDF 。对信息论有兴趣又有一定数学基础的读者，可以阅读斯坦福大学托马斯 . 科弗 (Thomas Cover) 教授的专著 " 信息论基础 "(Elements of Information Theory) ：m/gp/product/0471062596/ref=nosim/103-7880775-7782209?n=283155 m/query/p?viBookCode=17909 科弗教授是当今最权威的信息论专家。-----------------------------------------------------Page 17-----------------------------------------------------八、贾里尼克的故事和现代语言处理2006 年 6 月 8 日 上午 09:15:00发表者：Google 研究员，吴军读 者也许注意到了，我们在前面的系列中多次提到了贾里尼克这个名字。事实 上，现代语音识别和自然语言处理确实是和它的名字是紧密联系在一起的。我想 在这回的 系列里，介绍贾里尼克本人。在这里我不想列举他的贡献，而想讲一 讲他作为一个普普通通的人的故事。这些事要么是我亲身经历的，要么是他亲口 对我讲的。弗 莱德里克.贾里尼克(Fred Jelinek)出生于捷克一个富有的犹太家庭。他的父 母原本打算送他去英国的公学（私立学校）读书。为了教他德语，还专门请的一 位德国的家庭女教师，但 是第二次世界大战完全打碎了他们的梦想。他们先是 被从家中赶了出去，流浪到布拉格。他的父亲死在了集中营，弗莱德自己成天在 街上玩耍，完全荒废了学业。二 战后，当他再度回到学校时，他的成绩一塌糊 涂， 全部是 D，但是很快他就赶上了班上的同学。不过，他在小学时从来没有 得过 A。1949 年，他的母亲带领全家移民美国。在美国，贾里尼克一家生活非 常贫困，全家基本是靠母亲做点心卖钱为生，弗莱德自己十四五岁就进工厂打工 补助全 家。贾里尼克最初想成为一个律师，为他父亲那样的冤屈者辩护，但他很快意识到他 那浓厚的外国口音将使他在法庭上的辩护很吃力。贾里 尼克的第二个理想是成 为医生，他想进哈佛大学医学院，但经济上他无法承担医学院 8 年高昂的学费。 与此同时麻省理工学院给于了他一份（为东欧移民设的）全额奖学金。贾里尼克 决定到麻省理工学电机工程。在那里，他遇到了信息论的鼻祖香农博 士，和语 言学大师贾格布森 Roman Jakobson (他提出了著名的通信六功能）[注释一]， 后来贾里尼克又陪着太太听最伟大的语言学家乔姆斯基(Noam Chomsky)的课。这 三位大师对贾里尼克今后的研究方向--利用信息论解决语言问题产生的重要影 响。贾 里尼克从麻省理工获得博士学位后，在哈佛大学教了一年书，然后到康乃尔 大学任教。他之所以选择康乃尔大学，是因为找工作时和那里的一位语言学家谈 得颇为投 机。当时那位教授表示愿意和贾里尼克在利用信息论解决语言问题上 合作。但是，等贾里尼克到康乃尔以后，那位教授表示对语言学在没有兴趣而转 向写歌剧了。贾 里尼克对语言学家的坏印象从此开始。加上后来他在 IBM 时发 现语言学家们嘴上头头是道，干起活来高不成低不就，对语言学家从此深恶痛绝。 他甚至说："我每开除一名语言学家，我的语音识别系统错误率就降低一个百 分 点。" 这句话后来在业界广为流传，为每一个搞语音识别和语言处理的人所熟知。贾里尼克在康乃尔十年磨一剑，潜心研究信息论，终于悟 出了自然语言处理的 真谛。１９７２年，贾里尼克到ＩＢＭ 华生实验室（ＩＢＭ Ｔ．Ｇ．Ｗａｔ-----------------------------------------------------Page 18-----------------------------------------------------ｓｏｎ Ｌａｂｓ）做学术休假，无意中领导了语音识别实验室，两年后他在康 乃尔和ＩＢＭ 之间选择了留在ＩＢＭ。在那里，贾里尼克组建了阵容空前绝后 强大的研究队伍，其中包括他的著名搭档波尔（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 的实验室。 为了提高外国人的英语水平，贾里尼克用自己的经费为他们请私人英语教师。贾 里尼克生活俭朴，一辆老式丰田车开了二十多年，比组里学生的车都破。他 每年都邀请组里的学生和教授到家里做客，很多毕业了的学生也专程赶来聚会。 在那里， 他不再谈论学术问题，而会谈些巩俐的电影（他太太是哥伦比亚大学 电影专业的教授），或是某著名教授被拉斯韦加斯的赌馆定为不受欢迎的人等等。 但是他聚会的 食物实在难吃，无非是些生胡萝卜和芹菜。后来贾里尼克掏钱让 系里另一个教授承办聚会，那个教授每次请专业大厨在家作出极丰盛的晚宴，并 准备许多美酒，从此 这种聚会就转移到那个教授家了。-----------------------------------------------------Page 19-----------------------------------------------------除了巩俐的电影，贾里尼克对中国的了解就是清华大学和青岛啤酒了。他有时会 把两个名字搞混，有两次被香港科技大学的 Pascale 冯教授抓住。贾 里尼克说话心直口快，不留余地。在他面前谈论学术一定要十分严谨，否则 很容易被他抓住辫子。除了刚才提到的对语言学家略有偏见的评论，他对许多世 界级的大 师都有过很多“刻薄”但又实事求是的评论，这些评论在业界广为流 传。贾里尼克在四十多年的学术生涯中居然没有得罪太多的人 ，可以说是一个 奇迹。注释一：贾格布森的通信模型 1 上下文 2信息 3发送着 --------------- 4 接收者 5信道6 编码-----------------------------------------------------Page 20-----------------------------------------------------九、 如何确定网页和查询的相关性2006 年 6 月 27 日 上午 09:53:00发表者：吴军，Google 研究员[我们已经谈过了 如何自动下载网页 、 如何建立索引 、 如何衡量网页的质量 (Page Rank)。我们今天谈谈如何确定一个网页和某个查询的相关性。了解了这四个方 面，一个有一定编程基础的读者应该可以写一个简单的搜索引擎了，比如为您所 在的学校或院系建立一个小的搜索引擎。]