《谷歌黑板报数学之美》由会员分享，可在线阅读，更多相关《谷歌黑板报数学之美（45页珍藏版）》请在金锄头文库上搜索。
1、数学之美 系列一 统计语言模型 . 2 数学之美 系列二 谈谈中文分词 . 3 数学之美 系列三 隐含马尔可夫模型在语言处理中的应用 . 5 数学之美 系列四 怎样度量信息? . 7 数学之美 系列五 简单之美：布尔代数和搜索引擎的索引 . 9 数学之美 系列六 图论和网络爬虫 (Web Crawlers) . 11 数学之美 系列七 信息论在信息处理中的应用 . 13 数学之美 系列八 贾里尼克的故事和现代语言处理 . 15 数学之美 系列九 如何确定网页和查询的相关性 . 17 数学之美 系列十 有限状态机和地址识别 . 19 数学之美 系列十一 Google 阿卡 47 的制造者阿米特.
2、辛格博士 . 20 数学之美 系列十二 余弦定理和新闻的分类 . 21 数学之美 系列十三 信息指纹及其应用 . 24 数学之美 系列十四 谈谈数学模型的重要性 . 25 数学之美 系列十五 繁与简 自然语言处理的几位精英 . 27 数学之美 系列十六（上） 不要把所有的鸡蛋放在一个篮子里 谈谈最大熵模型 . 29 数学之美 系列十六 （下） 不要把所有的鸡蛋放在一个篮子里 最大熵模型 . 31 数学之美 系列十七 闪光的不一定是金子 谈谈搜索引擎作弊问题(Search Engine AntiSPAM). 32 数学之美 系列十八 矩阵运算和文本处理中的分类问题 . 35 数学之美 系列十九
3、马尔可夫链的扩展 贝叶斯网络 (Bayesian Networks) . 37 数学之美 系列二十 自然语言处理的教父 马库斯 . 38 数学之美 系列二十一 布隆过滤器（Bloom Filter） . 39 数学之美 系列二十二 由电视剧暗算所想到的 谈谈密码学的数学原理 . 41 数学之美 系列二十三 输入一个汉字需要敲多少个键 谈谈香农第一定律 . 44 数学之美数学之美 系列一系列一 统计语言模型统计语言模型 2006 年 4 月 3 日 上午 08:15:00 从本周开始，我们将定期刊登 Google 科学家吴军写的数学之美系列文章，介绍数学在信息检索和自然语言处理中的主导作用和奇妙
4、应用。 发表者: 吴军, Google 研究员 前言 也许大家不相信， 数学是解决信息检索和自然语言处理的最好工具。 它能非常清晰地描述这些领域的实际问题并且给出漂亮的解决办法。 每当人们应用数学工具解决一个语言问题时， 总会感叹数学之美。我们希望利用 Google 中文黑板报这块园地，介绍一些数学工具，以及我们是如何利用这些工具来开发 Google 产品的。 系列一： 统计语言模型 (Statistical Language Models) Google 的使命是整合全球的信息， 所以我们一直致力于研究如何让机器对信息、 语言做最好的理解和处理。长期以来，人类一直梦想着能让机器代替人来翻译语
5、言、识别语音、认识文字（不论是印刷体或手写体）和进行海量文献的自动检索，这就需要让机器理解语言。但是人类的语言可以说是信息里最复杂最动态的一部分。 为了解决这个问题， 人们容易想到的办法就是让机器模拟人类进行学习 - 学习人类的语法、分析语句等等。尤其是在乔姆斯基（Noam Chomsky 有史以来最伟大的语言学家）提出 “形式语言” 以后，人们更坚定了利用语法规则的办法进行文字处理的信念。遗憾的是，几十年过去了，在计算机处理语言领域，基于这个语法规则的方法几乎毫无突破。 其实早在几十年前，数学家兼信息论的祖师爷 香农 (Claude Shannon)就提出了用数学的办法处理自然语言的想法。
6、遗憾的是当时的计算机条件根本无法满足大量信息处理的需要， 所以他这个想法当时并没有被人们重视。七十年代初，有了大规模集成电路的快速计算机后，香农的梦想才得以实现。 首先成功利用数学方法解决自然语言处理问题的是语音和语言处理大师贾里尼克 (Fred Jelinek)。当时贾里尼克在 IBM 公司做学术休假 (Sabbatical Leave)，领导了一批杰出的科学家利用大型计算机来处理人类语言问题。统计语言模型就是在那个时候提出的。 给大家举个例子：在很多涉及到自然语言处理的领域，如机器翻译、语音识别、印刷体或手写体识别、拼写纠错、汉字输入和文献查询中，我们都需要知道一个文字序列是否能构成一个大
7、家能理解的句子，显示给使用者。对这个问题，我们可以用一个简单的统计模型来解决这个问题。 如果 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 w2wn-1) 其中 P (w1) 表示第一个词 w1 出现的
8、概率；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)
9、在统计的文本中出现了多少次，以及 wi-1 本身在同样的文本中前后相邻出现了多少次，然后用两个数一除就可以了,P(wi|wi-1) = P(wi-1,wi)/ P (wi-1)。 也许很多人不相信用这么简单的数学模型能解决复杂的语音识别、 机器翻译等问题。 其实不光是常人，就连很多语言学家都曾质疑过这种方法的有效性，但事实证明，统计语言模型比任何已知的借助某种规则的解决方法都有效。比如在 Google 的中英文自动翻译中，用的最重要的就是这个统计语言模型。去年美国标准局(NIST) 对所有的机器翻译系统进行了评测，Google 的系统是不仅是全世界最好的，而且高出所有基于规则的系统很多。 现在
10、，读者也许已经能感受到数学的美妙之处了，它把一些复杂的问题变得如此的简单。当然，真正实现一个好的统计语言模型还有许多细节问题需要解决。 贾里尼克和他的同事的贡献在于提出了统计语言模型，而且很漂亮地解决了所有的细节问题。十几年后，李开复用统计语言模型把 997 词语音识别的问题简化成了一个 20 词的识别问题，实现了有史以来第一次大词汇量非特定人连续语音的识别。 我是一名科学研究人员 ，我在工作中经常惊叹于数学语言应用于解决实际问题上时的神奇。我也希望把这种神奇讲解给大家听。当然，归根结底，不管什莫样的科学方法、无论多莫奇妙的解决手段都是为人服务的。我希望 Google 多努力一分，用户就多一分
11、搜索的喜悦。 数学之美数学之美 系列二系列二 谈谈中文分词谈谈中文分词 2006 年 4 月 10 日 上午 08:10:00 发表者: 吴军， Google 研究员 谈谈中文分词 - 统计语言模型在中文处理中的一个应用 上回我们谈到利用统计语言模型进行语言处理， 由于模型是建立在词的基础上的， 对于中日韩等语言，首先需要进行分词。例如把句子 “中国航天官员应邀到美国与太空总署官员开会。” 分成一串词： 中国 / 航天 / 官员 / 应邀 / 到 / 美国 / 与 / 太空 / 总署 / 官员 / 开会。 最容易想到的， 也是最简单的分词办法就是查字典。 这种方法最早是由北京航天航空大学的梁南元教授提出的。 用 “查字典” 法，其实就是我们把一个句子从左向右扫描一遍，遇到字典里有的词就标识出来，遇到复合词（比如 “上海大学”）就找最长的词匹配，
