Google 数学之美 浪潮之巅 吴军 Google研究院 2008年12月30日整理
数学之美 & 浪潮之巅 吴军 Google 研究院 2008 年 12 月 30 日整理 I
目录 Google黑板报 1.数学之美 011 1.1.数学之美系列一一 统计语言模型..1 1.2.数学之美系列二一谈谈中文分词… 5 1.3.数学之美系列三一 隐含马尔可夫模型在语言处理中的应用.9 1.4. 数学之美系列四一怎样度量信息？…13 1.5.数学之美系列五一简单之美：布尔代数和搜索引擎的索引....17 1.6.数学之美系列六一 图论和网络爬虫(Web Crawlers)......... 22 1.7.数学之美系列七一信息论在信息处理中的应用.… 26 1.8.数学之美系列八一 贾里尼克的故事和现代语言处理..…29 1.9.数学之美系列九一 如何确定网页和查询的相关性… 35 1.10.数学之美系列十一有限状态机和地址识别…39 1.11.数学之美系列十一一G0ogle阿卡47的制造者阿米特.辛格博士. 42 1.12.数学之美系列十二一余弦定理和新闻的分类 45 1.13.数学之美系列十三 一信息指纹及其应用.. 49 1.14.数学之美系列十四一谈谈数学模型的重要性.…52 1.15.数学之美系列十五一繁与简自然语言处理的几位精英.… 55 1.16.数学之美系列十六（上）一不要把所有的鸡蛋放在一个篮子里-谈谈最大熵模型 59 1.17.数学之美系列十六（下）一不要把所有的鸡蛋放在一个篮子里-最大熵模型.63 1.18.数学之美系列十七一闪光的不一定是金子-谈谈搜索引擎作弊问题 (Search Engine Anti-SPAM)............67 1.19.数学之美系列十八一矩阵运算和文本处理中的分类问题.…70 1.20.数学之美系列十九一马尔可夫链的扩展贝叶斯网络(Bayesian Networks) 74 1.21.数学之美系列二十一自然语言处理的教父-马库斯…76 1.22.数学之美系列二十一一布隆过滤器(Bloom Filter).........79 1.23.数学之美系列二十二一由电视剧《暗算》所想到的-谈谈密码学的数学原理 82 1.24.数学之美系列二十三一输入一个汉字需要敲多少个键-谈谈香农第一定律87 1.25.数学之美系列二十四一从全球导航到输入法-谈谈动态规划… 91 2.浪潮之巅 … 97 2.1.浪潮之巅第一章一帝国的余辉(AT&T)（一）. 97 2.2.浪潮之巅第一章一帝国的余辉(AT&T)(二) .102
目录 1. 数学之美 ................................................................1 1.1. 数学之美系列一 — 统计语言模型 .................................................. 1 1.2. 数学之美系列二 — 谈谈中文分词 .................................................. 5 1.3. 数学之美系列三 — 隐含马尔可夫模型在语言处理中的应用.................... 9 1.4. 数学之美系列四 — 怎样度量信息?............................................... 13 1.5. 数学之美系列五 — 简单之美：布尔代数和搜索引擎的索引.................. 17 1.6. 数学之美系列六 — 图论和网络爬虫 (Web Crawlers) ...................... 22 1.7. 数学之美系列七 — 信息论在信息处理中的应用................................ 26 1.8. 数学之美系列八 — 贾里尼克的故事和现代语言处理 .......................... 29 1.9. 数学之美系列九 — 如何确定网页和查询的相关性............................. 35 1.10. 数学之美系列十 — 有限状态机和地址识别 ..................................... 39 1.11. 数学之美系列十一 — Google 阿卡 47 的制造者阿米特.辛格博士 ........ 42 1.12. 数学之美系列十二 — 余弦定理和新闻的分类 .................................. 45 1.13. 数学之美系列十三 — 信息指纹及其应用........................................ 49 1.14. 数学之美系列十四 — 谈谈数学模型的重要性 .................................. 52 1.15. 数学之美系列十五 — 繁与简 自然语言处理的几位精英 ...................... 55 1.16. 数学之美系列十六(上)—不要把所有的鸡蛋放在一个篮子里-谈谈最大熵模型 59 1.17. 数学之美系列十六(下)— 不要把所有的鸡蛋放在一个篮子里-最大熵模型.. 63 1.18. 数学之美系列十七 — 闪光的不一定是金子 -- 谈谈搜索引擎作弊问题 (Search Engine Anti-SPAM) ............................................................ 67 1.19. 数学之美系列十八 — 矩阵运算和文本处理中的分类问题..................... 70 1.20. 数学之美系列十九 — 马尔可夫链的扩展 贝叶斯网络 (Bayesian Networks) 74 1.21. 数学之美系列二十 — 自然语言处理的教父 -- 马库斯........................ 76 1.22. 数学之美系列二十一 — 布隆过滤器（Bloom Filter） ....................... 79 1.23. 数学之美系列二十二 — 由电视剧《暗算》所想到的-谈谈密码学的数学原理 82 1.24. 数学之美系列二十三 — 输入一个汉字需要敲多少个键-谈谈香农第一定律 87 1.25. 数学之美系列二十四 — 从全球导航到输入法-谈谈动态规划................. 91 2. 浪潮之巅 .............................................................. 97 2.1. 浪潮之巅第一章 — 帝国的余辉（AT&T)（一） ............................... 97 2.2. 浪潮之巅第一章 — 帝国的余辉（AT&T)（二） ..............................102 I
目录 2.3.浪潮之巅第一章一 帝国的余辉(AT&T)(三) .106 2.4.浪潮之巅第一章一 帝国的余辉 (AT&T)(四) .111 2.5.浪潮之巅第二章 一蓝色巨人(IBM) (-) .114 2.6.浪潮之巅第二章一 蓝色巨人(IBM)(二) .119 2.7. 浪潮之巅第二章 蓝色巨人(IBM)(三) .124 2.8.浪潮之巅第二章一 蓝色巨人(IBM)(四) .130 2.9.浪潮之巅第二章一蓝色巨人(IBM)(五) .134 2.10.浪潮之巅第二章一蓝色巨人(IBM)(六) .137 2.11.浪潮之巅第三章一“水果”公司的复兴（乔布斯和苹果公司） (一) .141 2.12.浪潮之巅第三章 “水果”公司的复兴 (乔布斯和苹果公司)（二） .147 2.13.浪潮之巅第三章一“水果”公司的复兴 (乔布斯和苹果公司)（三） ..150 2.14.浪潮之巅第三章一"水果"公司的复兴（乔布斯和苹果公司）（四） ..154 2.15.浪潮之巅第四章一计算机工业的生态链（一） .158 2.16.浪潮之巅第四章一计算机工业的生态链（二） .163 2.17.浪潮之巅第四章一 计算机工业的生态链（三） .167 2.18.浪潮之巅第五章一 奔腾的芯（英特尔一Intel)(一） .172 2.19.浪潮之巅第五章一奔腾的芯（英特尔一Intel) (二) .177 2.20.浪潮之巅第五章一奔腾的芯（英特尔一Intel))(三） .181 2.21.浪潮之巅第五章一 奔腾的芯（英特尔一Intel)(四） .186 2.22.浪潮之巅第五章一 奔腾的芯（英特尔一Intel)(五） .189 2.23.浪潮之巅第六章一互联网的金门大桥（思科）（一） ..193 2.24.浪潮之巅第六章一 互联网的金门大桥（思科）（二） ..196 2.25.浪潮之巅第六章一 互联网的金门大桥（思科）（三） .199 2.26.浪潮之巅第六章一互联网的金门大桥（思科） (四) 203 2.27.浪潮之巅第七章一硅谷的见证人（惠普公司）（一） .212 2.28.浪潮之巅第七章一硅谷的见证人一惠普公司（二） 217 2.29.浪潮之巅第七章一硅谷的见证人一惠普公司（三） ...221 2.30.浪潮之巅第七章一 硅谷的见证人一惠普公司（四）】 ..225 2.31.浪潮之巅第七章一硅谷的见证人一惠普公司（五）》 ,228 2.32.浪潮之巅第八章一没落的贵族一摩托罗拉（一） .233 2.33.浪潮之巅第八章一没落的贵族一摩托罗拉（二） .236 2.34.浪潮之巅第八章一没落的贵族一摩托罗拉（三） .240 2.35.浪潮之巅第八章一没落的贵族一摩托罗拉（四）》 245 2.36.浪潮之巅第八章一没落的贵族一摩托罗拉（五） 249 2.37.浪潮之巅第八章一没落的贵族一摩托罗拉（六） ,253 2.38.浪潮之巅第九章一硅谷的另一面（一） … 258 2.39.浪潮之巅第九章一硅谷的另一面（二） ,265 2.40.浪潮之巅第九章一硅谷的另一面（三）》 .269 2.41.浪潮之巅第九章一硅谷的另一面（四） .276 2.42.浪潮之巅第九章一硅谷的另一面（五） .280 2.43.浪潮之巅第十章一短暂的春秋一与机会失之交臂的公司（一) .289 2.44.浪潮之巅第十章一短暂的春秋— 与机会失之交臂的公司（二） .296 2.45.浪潮之巅第十章一短暂的春秋 与机会失之交臂的公司（三） .303 2.46.浪潮之巅第十章一短暂的春秋— 与机会失之交臂的公司（四） .308
目录 2.3. 浪潮之巅第一章 — 帝国的余辉（AT&T）（三） ..............................106 2.4. 浪潮之巅第一章 — 帝国的余辉（AT&T）（四） ..............................111 2.5. 浪潮之巅第二章 — 蓝色巨人（IBM）（一）...................................114 2.6. 浪潮之巅第二章 — 蓝色巨人（IBM）（二）...................................119 2.7. 浪潮之巅第二章 — 蓝色巨人（IBM）（三）...................................124 2.8. 浪潮之巅第二章 — 蓝色巨人（IBM）（四）...................................130 2.9. 浪潮之巅第二章 — 蓝色巨人（IBM）（五）...................................134 2.10. 浪潮之巅第二章 — 蓝色巨人（IBM）（六）...................................137 2.11. 浪潮之巅第三章 — “水果”公司的复兴 （乔布斯和苹果公司）（一） ...141 2.12. 浪潮之巅第三章 — “水果”公司的复兴 （乔布斯和苹果公司）（二） ...147 2.13. 浪潮之巅第三章 — “水果”公司的复兴 （乔布斯和苹果公司）（三） ...150 2.14. 浪潮之巅第三章 — "水果"公司的复兴 （乔布斯和苹果公司）（四）.......154 2.15. 浪潮之巅第四章 — 计算机工业的生态链（一）...............................158 2.16. 浪潮之巅第四章 — 计算机工业的生态链（二）...............................163 2.17. 浪潮之巅第四章 — 计算机工业的生态链（三）...............................167 2.18. 浪潮之巅第五章 — 奔腾的芯（英特尔—Intel）（一）.......................172 2.19. 浪潮之巅第五章 — 奔腾的芯（英特尔—Intel）（二）.......................177 2.20. 浪潮之巅第五章 — 奔腾的芯（英特尔—Intel）（三）.......................181 2.21. 浪潮之巅第五章 — 奔腾的芯（英特尔—Intel）（四）.......................186 2.22. 浪潮之巅第五章 — 奔腾的芯（英特尔—Intel）（五）.......................189 2.23. 浪潮之巅第六章 — 互联网的金门大桥（思科）（一）........................193 2.24. 浪潮之巅第六章 — 互联网的金门大桥（思科）（二）........................196 2.25. 浪潮之巅第六章 — 互联网的金门大桥（思科）（三）........................199 2.26. 浪潮之巅第六章 — 互联网的金门大桥（思科）（四）........................203 2.27. 浪潮之巅第七章 — 硅谷的见证人（惠普公司）（一）........................212 2.28. 浪潮之巅第七章 — 硅谷的见证人—惠普公司（二） .........................217 2.29. 浪潮之巅第七章 — 硅谷的见证人—惠普公司（三） .........................221 2.30. 浪潮之巅第七章 — 硅谷的见证人—惠普公司（四） .........................225 2.31. 浪潮之巅第七章 — 硅谷的见证人—惠普公司（五） .........................228 2.32. 浪潮之巅第八章 — 没落的贵族—摩托罗拉（一）............................233 2.33. 浪潮之巅第八章 — 没落的贵族—摩托罗拉（二）............................236 2.34. 浪潮之巅第八章 — 没落的贵族—摩托罗拉（三）............................240 2.35. 浪潮之巅第八章 — 没落的贵族—摩托罗拉（四）............................245 2.36. 浪潮之巅第八章 — 没落的贵族—摩托罗拉（五）............................249 2.37. 浪潮之巅第八章 — 没落的贵族—摩托罗拉（六）............................253 2.38. 浪潮之巅第九章 — 硅谷的另一面（一）.......................................258 2.39. 浪潮之巅第九章 — 硅谷的另一面（二）.......................................265 2.40. 浪潮之巅第九章 — 硅谷的另一面（三）.......................................269 2.41. 浪潮之巅第九章 — 硅谷的另一面（四）.......................................276 2.42. 浪潮之巅第九章 — 硅谷的另一面（五）.......................................280 2.43. 浪潮之巅第十章 — 短暂的春秋——与机会失之交臂的公司（一）.........289 2.44. 浪潮之巅第十章 — 短暂的春秋——与机会失之交臂的公司（二）.........296 2.45. 浪潮之巅第十章 — 短暂的春秋——与机会失之交臂的公司（三）.........303 2.46. 浪潮之巅第十章 — 短暂的春秋——与机会失之交臂的公司（四）.........308 II
目录 2.47.浪潮之巅第十章一短暂的春秋一与机会失之交臂的公司（五） .317 2.48.浪潮之巅第十章一短暂的春秋一与机会失之交臂的公司（六） .326 2.49.浪潮之巅第十一章一幕后的英雄一风险投资(Venture Capital) ...333 2.50.浪潮之巅第十一章一幕后的英雄一风险投资(Venture Capital)) .338 2.51.浪潮之巅第十一章一幕后的英雄一风险投资(Venture Capital) ..344 2.52.浪潮之巅第十一章一幕后的英雄一风险投资(Venture Capital) ..352 2.53.浪潮之巅第十一章一幕后的英雄一风险投资(Venture Capital).360 2.54.浪潮之巅第十一章一幕后的英雄-风险投资(Venture Capital)..367 2.55.浪潮之巅第十二章一信息产业的规律性（一）..376 2.56.浪潮之巅第十二章一信息产业的规律性（二).388 2.57.浪潮之巅第十二章一 信息产业的规律性（三） .397 m
目录 2.47. 浪潮之巅第十章 — 短暂的春秋——与机会失之交臂的公司（五）.........317 2.48. 浪潮之巅第十章 — 短暂的春秋——与机会失之交臂的公司（六）.........326 2.49. 浪潮之巅第十一章 — 幕后的英雄—风险投资（Venture Capital）.......333 2.50. 浪潮之巅第十一章 — 幕后的英雄—风险投资（Venture Capital）.......338 2.51. 浪潮之巅第十一章 — 幕后的英雄—风险投资（Venture Capital）.......344 2.52. 浪潮之巅第十一章 — 幕后的英雄—风险投资（Venture Capital）.......352 2.53. 浪潮之巅第十一章 — 幕后的英雄—风险投资（Venture Capital）.......360 2.54. 浪潮之巅第十一章 — 幕后的英雄—风险投资（Venture Capital）.......367 2.55. 浪潮之巅第十二章 — 信息产业的规律性 (一) ................................376 2.56. 浪潮之巅第十二章 — 信息产业的规律性 (二) ................................388 2.57. 浪潮之巅第十二章 — 信息产业的规律性 (三) ................................397 III
数学之美 1.数学之美 吴军，Google研究员 1.1.数学之美系列一一统计语言模型 2006年4月3日上午08：15：00 从本周开始，我们将定期刊登Go0g1e科学家吴军写的《数 学之美》系列文章，介绍数学在信息检索和自然语言处理中的主 导作用和奇妙应用。 发表者：吴军，Google研究员 前言 也许大家不相信，数学是解决信息检索和自然语言处理的最 好工具。它能非常清晰地描述这些领域的实际问题并且给出漂亮 的解决办法。每当人们应用数学工具解决一个语言问题时，总会 感叹数学之美。我们希望利用G00g1e中文黑板报这块园地，介 绍一些数学工具，以及我们是如何利用这些工具来开发Google 产品的。 系列一：统计语言模型(Statistical Language Models) G00g1e的使命是整合全球的信息，所以我们一直致力于研究 如何让机器对信息、语言做最好的理解和处理。长期以来，人类 一直梦想着能让机器代替人来翻译语言、识别语音、认识文字（不
数学之美 1.数学之美 吴军, Google 研究员 1.1. 数学之美系列一 — 统计语言模型 2006 年 4月3日 上午 08:15:00 从本周开始，我们将定期刊登 Google 科学家吴军写的《数 学之美》系列文章，介绍数学在信息检索和自然语言处理中的主 导作用和奇妙应用。 发表者: 吴军, Google 研究员 前言 也许大家不相信，数学是解决信息检索和自然语言处理的最 好工具。它能非常清晰地描述这些领域的实际问题并且给出漂亮 的解决办法。每当人们应用数学工具解决一个语言问题时，总会 感叹数学之美。我们希望利用 Google 中文黑板报这块园地，介 绍一些数学工具，以及我们是如何利用这些工具来开发 Google 产品的。 系列一： 统计语言模型 (Statistical Language Models) Google 的使命是整合全球的信息，所以我们一直致力于研究 如何让机器对信息、语言做最好的理解和处理。长期以来，人类 一直梦想着能让机器代替人来翻译语言、识别语音、认识文字（不 1
数学之美 论是印刷体或手写体)和进行海量文献的自动检索，这就需要让 机器理解语言。但是人类的语言可以说是信息里最复杂最动态的 一部分。为了解决这个问题，人们容易想到的办法就是让机器模 拟人类进行学习一学习人类的语法、分析语句等等。尤其是在 乔姆斯基(Noam Chomsky有史以来最伟大的语言学家)提出“形 式语言”以后，人们更坚定了利用语法规则的办法进行文字处 理的信念。遗憾的是，几十年过去了，在计算机处理语言领域， 基于这个语法规则的方法几乎毫无突破。 其实早在几十年前，数学家兼信息论的祖师爷香农(Claude Shannon)就提出了用数学的办法处理自然语言的想法。遗憾的是 当时的计算机条件根本无法满足大量信息处理的需要，所以他这 个想法当时并没有被人们重视。七十年代初，有了大规模集成电 路的快速计算机后，香农的梦想才得以实现。 首先成功利用数学方法解决自然语言处理问题的是语音和语 言处理大师贾里尼克(Fred Jelinek)。当时贾里尼克在IBM公 司做学术休假(Sabbatical Leave)),领导了一批杰出的科学家 利用大型计算机来处理人类语言问题。统计语言模型就是在那个 时侯提出的。 给大家举个例子：在很多涉及到自然语言处理的领域，如机 器翻译、语音识别、印刷体或手写体识别、拼写纠错、汉字输入 和文献查询中，我们都需要知道一个文字序列是否能构成一个大
数学之美 论是印刷体或手写体）和进行海量文献的自动检索，这就需要让 机器理解语言。但是人类的语言可以说是信息里最复杂最动态的 一部分。为了解决这个问题，人们容易想到的办法就是让机器模 拟人类进行学习 - 学习人类的语法、分析语句等等。尤其是在 乔姆斯基（Noam Chomsky 有史以来最伟大的语言学家）提出 “形 式语言” 以后，人们更坚定了利用语法规则的办法进行文字处 理的信念。遗憾的是，几十年过去了，在计算机处理语言领域， 基于这个语法规则的方法几乎毫无突破。 其实早在几十年前，数学家兼信息论的祖师爷 香农 (Claude Shannon)就提出了用数学的办法处理自然语言的想法。遗憾的是 当时的计算机条件根本无法满足大量信息处理的需要，所以他这 个想法当时并没有被人们重视。七十年代初，有了大规模集成电 路的快速计算机后，香农的梦想才得以实现。 首先成功利用数学方法解决自然语言处理问题的是语音和语 言处理大师贾里尼克 (Fred Jelinek)。当时贾里尼克在 IBM 公 司做学术休假 (Sabbatical Leave)，领导了一批杰出的科学家 利用大型计算机来处理人类语言问题。统计语言模型就是在那个 时候提出的。 给大家举个例子：在很多涉及到自然语言处理的领域，如机 器翻译、语音识别、印刷体或手写体识别、拼写纠错、汉字输入 和文献查询中，我们都需要知道一个文字序列是否能构成一个大 2
数学之美 家能理解的句子，显示给使用者。对这个问题，我们可以用一个 简单的统计模型来解决这个问题。 如果S表示一连串特定顺序排列的词w1,w2,.,wn, 换句话说，S可以表示某一个由一连串特定顺序排练的词而组成 的一个有意义的句子。现在，机器对语言的识别从某种角度来说， 就是想知道S在文本中出现的可能性，也就是数学上所说的S的 概率用P(S)来表示。利用条件概率的公式，S这个序列出现的 概率等于每一个词出现的概率相乘，于是P(S)可展开为： P(S)=P(w1)P(w2lw1)P(w3l w1 w2)...P(wnlw1 w2...wn-1) 其中P(w1)表示第一个词w1出现的概率；P(w2|w1)是在 已知第一个词的前提下，第二个词出现的概率；以次类推。不难 看出，到了词w,它的出现概率取决于它前面所有词。从计算 上来看，各种可能性太多，无法实现。因此我们假定任意一个词 wi的出现概率只同它前面的词wi-1有关（即马尔可夫假设）， 于是问题就变得很简单了。现在，S出现的概率就变为： P(S)=P(w1)P(w2lw1)P(w3lw2)...P(wilwi-1)... (当然，也可以假设一个词又前面N-1个词决定，模型稍微复 杂些。) 接下来的问题就是如何估计P(wi|wi-1)。现在有了大量机 读文本后，这个问题变得很简单，只要数一数这对词(wi-1,wi) 在统计的文本中出现了多少次，以及wi-1本身在同样的文本中
数学之美 家能理解的句子，显示给使用者。对这个问题，我们可以用一个 简单的统计模型来解决这个问题。 如果 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 本身在同样的文本中 3
数学之美 前后相邻出现了多少次，然后用两个数一除就可以了，P(wi|wi-1) =P(wi-1,wi)/p(wi-1)。 也许很多人不相信用这么简单的数学模型能解决复杂的语音 识别、机器翻译等问题。其实不光是常人，就连很多语言学家都 曾质疑过这种方法的有效性，但事实证明，统计语言模型比任何 已知的借助某种规则的解决方法都有效。比如在Google的中英 文自动翻译中，用的最重要的就是这个统计语言模型。去年美国 标准局(NIST)对所有的机器翻译系统进行了评测，Google的系 统是不仅是全世界最好的，而且高出所有基于规则的系统很多。 现在，读者也许已经能感受到数学的美妙之处了，它把一些 复杂的问题变得如此的简单。当然，真正实现一个好的统计语言 模型还有许多细节问题需要解决。贾里尼克和他的同事的贡献在 于提出了统计语言模型，而且很漂亮地解决了所有的细节问题。 十几年后，李开复用统计语言模型把997词语音识别的问题简 化成了一个20词的识别问题，实现了有史以来第一次大词汇量 非特定人连续语音的识别。 我是一名科学研究人员，我在工作中经常惊叹于数学语言应 用于解决实际问题上时的神奇。我也希望把这种神奇讲解给大家 听。当然，归根结底，不管什莫样的科学方法、无论多莫奇妙的 解决手段都是为人服务的。我希望Go0g1e多努力一分，用户就 多一分搜索的喜悦
数学之美 前后相邻出现了多少次，然后用两个数一除就可以了,P(wi|wi-1) = P(wi-1,wi)/ P (wi-1)。 也许很多人不相信用这么简单的数学模型能解决复杂的语音 识别、机器翻译等问题。其实不光是常人，就连很多语言学家都 曾质疑过这种方法的有效性，但事实证明，统计语言模型比任何 已知的借助某种规则的解决方法都有效。比如在 Google 的中英 文自动翻译中，用的最重要的就是这个统计语言模型。去年美国 标准局(NIST) 对所有的机器翻译系统进行了评测，Google 的系 统是不仅是全世界最好的，而且高出所有基于规则的系统很多。 现在，读者也许已经能感受到数学的美妙之处了，它把一些 复杂的问题变得如此的简单。当然，真正实现一个好的统计语言 模型还有许多细节问题需要解决。贾里尼克和他的同事的贡献在 于提出了统计语言模型，而且很漂亮地解决了所有的细节问题。 十几年后，李开复用统计语言模型把 997 词语音识别的问题简 化成了一个 20 词的识别问题，实现了有史以来第一次大词汇量 非特定人连续语音的识别。 我是一名科学研究人员 ，我在工作中经常惊叹于数学语言应 用于解决实际问题上时的神奇。我也希望把这种神奇讲解给大家 听。当然，归根结底，不管什莫样的科学方法、无论多莫奇妙的 解决手段都是为人服务的。我希望 Google 多努力一分，用户就 多一分搜索的喜悦。 4
数学之美 1.2.数学之美系列二一谈谈中文分词 2006年4月10日上午08：10：00 发表者：吴军，Google研究员 谈谈中文分词 统计语言模型在中文处理中的一个应用 上回我们谈到利用统计语言模型进行语言处理，由于模型是 建立在词的基础上的，对于中日韩等语言，首先需要进行分词。 例如把句子“中国航天官员应邀到美国与太空总署官员开会。” 分成一串词： 中国/航天/官员/应邀/到/美国/与/太空/ 总署/官员/开会。 最容易想到的，也是最简单的分词办法就是查字典。这种方 法最早是由北京航天航空大学的梁南元教授提出的。 用“查字典”法，其实就是我们把一个句子从左向右扫描 一遍，遇到字典里有的词就标识出来，遇到复合词（比如“上 海大学”)就找最长的词匹配，遇到不认识的字串就分割成单字 词，于是简单的分词就完成了。这种简单的分词方法完全能处理 上面例子中的句子。八十年代，哈工大的王晓龙博士把它理论化， 发展成最少词数的分词理论，即一句话应该分成数量最少的词 串。这种方法一个明显的不足是当遇到有二义性（有双重理解 意思)的分割时就无能为力了。比如，对短语“发展中国家”正 确的分割是“发展-中一国家”，而从左向右查字典的办法会将它
数学之美 1.2. 数学之美系列二 — 谈谈中文分词 2006 年 4 月 10 日 上午 08:10:00 发表者: 吴军， Google 研究员 谈谈中文分词 ----- 统计语言模型在中文处理中的一个应用 上回我们谈到利用统计语言模型进行语言处理，由于模型是 建立在词的基础上的，对于中日韩等语言，首先需要进行分词。 例如把句子 “中国航天官员应邀到美国与太空总署官员开会。” 分成一串词： 中国 / 航天 / 官员 / 应邀 / 到 / 美国 / 与 / 太空 / 总署 / 官员 / 开会。 最容易想到的，也是最简单的分词办法就是查字典。这种方 法最早是由北京航天航空大学的梁南元教授提出的。 用 “查字典” 法，其实就是我们把一个句子从左向右扫描 一遍，遇到字典里有的词就标识出来，遇到复合词（比如 “上 海大学”）就找最长的词匹配，遇到不认识的字串就分割成单字 词，于是简单的分词就完成了。这种简单的分词方法完全能处理 上面例子中的句子。八十年代，哈工大的王晓龙博士把它理论化， 发展成最少词数的分词理论，即一句话应该分成数量最少的词 串。这种方法一个明显的不足是当遇到有二义性 （有双重理解 意思）的分割时就无能为力了。比如，对短语 “发展中国家” 正 确的分割是“发展-中-国家”，而从左向右查字典的办法会将它 5
数学之美 分割成“发展-中国-家”，显然是错了。另外，并非所有的最长 匹配都一定是正确的。比如“上海大学城书店”的正确分词应该 是“上海-大学城-书店，”而不是“上海大学-城-书店”。 九十年代以前，海内外不少学者试图用一些文法规则来解决 分词的二义性问题，都不是很成功。90年前后，清华大学的郭 进博士用统计语言模型成功解决分词二义性问题，将汉语分词的 错误率降低了一个数量级。 利用统计语言模型分词的方法，可以用几个数学公式简单概 括如下： 我们假定一个句子S可以有几种分词方法，为了简单起见我 们假定有以下三种： A1,A2,A3,..,Ak, B1,B2,B3,·.,Bm C1,C2,C3,.,Cn 其中，A1,A2,B1,B2,C1,C2等等都是汉语的词。那么最 好的一种分词方法应该保证分完词后这个句子出现的概率最大。 也就是说如果A1,A2,·,Ak是最好的分法，那么(P表示概 率)： P(A1,A2,A3,,Ak)〉P(B1,B2,B3,.·,Bm),并 且
数学之美 分割成“发展-中国-家”，显然是错了。另外，并非所有的最长 匹配都一定是正确的。比如“上海大学城书店”的正确分词应该 是 “上海-大学城-书店，” 而不是 “上海大学-城-书店”。 九十年代以前，海内外不少学者试图用一些文法规则来解决 分词的二义性问题，都不是很成功。90 年前后，清华大学的郭 进博士用统计语言模型成功解决分词二义性问题，将汉语分词的 错误率降低了一个数量级。 利用统计语言模型分词的方法，可以用几个数学公式简单概 括如下： 我们假定一个句子 S 可以有几种分词方法，为了简单起见我 们假定有以下三种： A1, A2, A3, ..., Ak, B1, B2, B3, ..., Bm C1, C2, C3, ..., Cn 其中，A1, A2, B1, B2, C1, C2 等等都是汉语的词。那么最 好的一种分词方法应该保证分完词后这个句子出现的概率最大。 也就是说如果 A1,A2,..., Ak 是最好的分法，那么 （P 表示概 率）： P (A1, A2, A3, ..., Ak） 〉 P (B1, B2, B3, ..., Bm), 并 且 6