word数学之美系列完整版〔最新全集列表〕 吴军, Google 研究员 来源：Google黑板报 酷勤网收集 2007-12-04数学之美 一 统计语言模型数学之美 二 谈谈中文分词数学之美 三 隐含马尔可夫模型在语言处理中的应用数学之美 四 怎样度量信息?数学之美 五 简单之美：布尔代数和搜索引擎的索引数学之美 六 图论和网络爬虫 (Web Crawlers)数学之美 七 信息论在信息处理中的应用数学之美 八 贾里尼克的故事和现代语言处理数学之美 九 如何确定网页和查询的相关性数学之美 十 有限状态机和地址识别数学之美 十二 余弦定理和新闻的分类数学之美 十三 信息指纹与其应用数学之美 十四 谈谈数学模型的重要性数学之美 十五 繁与简 自然语言处理的几位精英数学之美 十六 不要把所有的鸡蛋放在一个篮子里 最大熵模型数学之美 十七 闪光的不一定是金子 谈谈搜索引擎作弊问题(Search Engine Anti-SPAM)数学之美 十八 矩阵运算和文本处理中的分类问题数学之美 十九 马尔可夫链的扩展 贝叶斯网络 (Bayesian Networks)数学之美 二十 自然语言处理的教父 马库斯数学之美 二十一 布隆过滤器〔Bloom Filter〕数学之美 二十二 由电视剧《暗算》所想到的 — 谈谈密码学的数学原理数学之美 二十三 输入一个汉字需要敲多少个键 — 谈谈香农第一定律数学之美 二十四 从全球导航到输入法——谈谈动态规划数学之美系列一：统计语言模型在很多涉与到自然语言处理的领域，如机器翻译、语音识别、印刷体或手写体识别、拼写纠错、汉字输入和文献查询中，我们都需要知道一个文字序列是否能构成一个大家能理解的句子，显示给使用者。
对这个问题，我们可以用一个简单的统计模型来解决这个问题前言也许大家不相信，数学是解决信息检索和自然语言处理的最好工具它能非常清晰地描述这些领域的实际问题并且给出漂亮的解决方法每当 人们应用数学工具解决一个语言问题时，总会感叹数学之美我们希望利用 Google 中文黑板报这块园地，介绍一些数学工具，以与我们是如何利用这些工具来开发 Google 产品的系列一： 统计语言模型 (Statistical Language Models)Google 的使命是整合全球的信息，所以我们一直致力于研究如何让机器对信息、语言做最好的理解和处理长期以来，人类一直梦想着能让机器代替人来翻译语言、识别语 音、认识文字〔不论是印刷体或手写体〕和进展海量文献的自动检索，这就需要让机器理解语言但是人类的语言可以说是信息里最复杂最动态的一局部为了解决 这个问题，人们容易想到的方法就是让机器模拟人类进展学习 - 学习人类的语法、分析语句等等尤其是在乔姆斯基〔Noam Chomsky 有史以来最伟大的语言学家〕提出 “形式语言〞 以后，人们更坚决了利用语法规如此的方法进展文字处理的信念遗憾的是，几十年过去了，在计算机处理语言领域，基于这个语法规如此的方法几乎毫无突破。
其实早在几十年前，数学家兼信息论的祖师爷 香农 (Claude Shannon)就提出了用数学的方法处理自然语言的想法遗憾的是当时的计算机条件根本无法满足大量信息处理的需要，所以他这个想法当时并没有被人们重视七十年代初，有了大规模集成电路的快速计算机后，香农的梦想才得以实现首先成功利用数学方法解决自然语言处理问题的是语音和语言处理大师贾里尼克 (Fred Jelinek)当时贾里尼克在 IBM 公司做学术休假 (Sabbatical Leave)，领导了一批杰出的科学家利用大型计算机来处理人类语言问题统计语言模型就是在那个时候提出的给大家举个例子：在很多涉与到自然语言处理的领域，如机器翻译、语音识别、印刷体或手写体识别、拼写纠错、汉字输入和文献查询中，我们都需要知道一个文字序列是否能构成一个大家能理解的句子，显示给使用者对这个问题，我们可以用一个简单的统计模型来解决这个问题如 果 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 多努力一分，用户就多一分搜索的喜悦数学之美系列二：谈谈中文分词一般来讲，根据不同应用，汉语分词的颗粒度大小应该不同。
比如，在机器翻译中，颗粒度应该大一些，“大学〞就不能被分成两个词而在语音识别中，“大学〞一般是被分成两个词因此，不同的应用，应该有不同的分词系统谈谈中文分词----- 统计语言模型在中文处理中的一个应用上回我们谈到利用统计语言模型进展语言处理，由于模型是建立在词的根底上的，对于中日韩等语言，首先需要进展分词例如把句子 “中国航天官员应邀到美国与太空总署官员开会〞 分成一串词：中国 / 航天 / 官员 / 应邀 / 到 / 美国 / 与 / 太空 / 总署 / 官员 / 开会最容易想到的，也是最简单的分词方法就是查字典这种方法最早是由航天航空大学的梁南元教授提出的用 “查字典〞 法，其实就是我们把一个句子从左向右扫描一遍，遇到字典里有的词就标识出来，遇到复合词〔比如 “某某大学〞〕就找最长的词匹配，遇到不认识的字串就分割成单字词，于是简单的分词就完成了这种简单的分词方法完全能处理上面例子中的句子八十年代，哈工大的王晓龙博士把 它理论化，开展成最少词数的分词理论，即一句话应该分成数量最少的词串这种方法一个明显的不足是当遇到有二义性 〔有双重理解意思〕的分割时就无能为力了比如，对短语 “开展中国家〞 正确的分割是“开展-中-国家〞，而从左向右查字典的方法会将它分割成“开展-中国-家〞，显然是错了。
另外，并非所有的最长匹配都一定是正确的比如“ 某某大学城书店〞的正确分词应该是 “某某-大学城-书店，〞 而不是 “某某大学-城-书店〞九十年代以前，海内外不少学者试图用一些文法规如此来解决分词的二义性问题，都不是很成功90年前后，清华大学的郭进博士用统计语言模型成功解决分词二义性问题，将汉语分词的错误率降低了一个数量级利用统计语言模型分词的方法，可以用几个数学公式简单概括如下：我们假定一个句子S可以有几种分词方法，为了简单起见我们假定有以下三种：A1, A2, A3, ..., Ak,B1, B2, B3, ..., BmC1, C2, C3, ..., 其中，A1, A2, B1, B2, C1, C2 等等都是汉语的词那么最好的一种分词方法应该保证分完词后这个句子出现的概率最大也就是说如果 A1,A2,..., Ak 是最好的分法，那么 〔P 表示概率〕：P (A1, A2, A3, ..., Ak〕 〉 P (B1, B2, B3, ..., Bm), 并且P (A1, A2, A3, ..., Ak〕 〉 P(C1, C2, C3, ..., )因此，只要我们利用上回提到的统计语言模型计算出每种分词后句子出现的概率，并找出其中概率最大的，我们就能够找到最好的分词方法。
当然，这里面有一个实现的技巧如果我们穷举所有可能的分词方法并计算出每种可能性下句子的概率，那么计算量是相当大的因此，我们可以把它看成是一个动态规划〔Dynamic Programming) 的问题，并利用 “维特比〞〔Viterbi〕 算法快速地找到最优分词在清华大学的郭进博士以后，海内外不少学者利用统计的方法，进一步完善中文分词其中值得一提的是清华大学孙茂松教授和某某科技大学吴德凯教授的工作需 要指出的是，语言学家对词语的定义不完全一样比如说 “大学〞，有人认为是一个词，而有人认为该分成两个词一个折中的解决方法是在分词的同时，找到复合词的嵌套结构在上面的例子中，如果一句话包含“ 大学〞四个字，那么先把它当成一个四字词，然后再进一步找出细分词 “〞 和 “大学〞这种方法是最早是郭进在 “putational Linguistics〞 〔《计算机语言学》〕杂志上发表的，以后不少系统采用这种方法一般来讲，根 据不同应用，汉语分词的颗粒度大小应该不同比如，在机器翻译中，颗粒度应该大一些，“大学〞就不能被分成两个词而在语音识别中，“大学〞一般 是被分成两个词因此，不同的应用，应该有不同的分词系统。
Google 的葛显平博士和朱安博士，专门为搜索设计和实现了自己的分词系统也 许你想不到，中文分词的方法也被应用到英语处理，主要是手写体识别中因为在识别手写体时，单词之间的空格就不很清楚了中文分词方法可以帮助判别英语单 词的边界其实，语言处理的许多数学方法通用的和具体的语言无关在 Google 内，我们在设计语言处理的算法时，都会考虑它是否能很容易地适用于各种自然语言这样，我们才能有效地支持上百种语言的搜索对中文分词有兴趣的读者，可以阅读以下文献：1. 梁南元 书面汉语自动分词系统 .touchwrite./demo/LiangNanyuan-JCIP-。