数学之美 系列一 -- 统计语言模型

发表者: 吴军, Google 研究员

前言

也 许大家不相信，数学是解决信息检索和自然语言处理的最好工具。它能非常清晰地描述这些领域的实际问题并且给出漂亮的解决办法。每当人们应用数学工具解决一 个语言问题时，总会感叹数学之美。我们希望利用 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)/[P(wi-1,wi)]。

也许很多人不相信用这么简单的数学模型能解决复杂的语音识别、机器翻译等问题。其实不光是常人，就连很多语言学家都曾质疑过这种方法的有效性，但事实证明，统计语言模型比任何已知的借助某种规则的解决方法都有效。比如在 Google 的中英文自动翻译中，用的最重要的就是这个统计语言模型。去年美国标准局(NIST) 对所有的机器翻译系统进行了评测，Google 的系统是不仅是全世界最好的，而且高出所有基于规则的系统很多。

现 在，读者也许已经能感受到数学的美妙之处了，它把一些复杂的问题变得如此的简单。当然，真正实现一个好的统计语言模型还有许多细节问题需要解决。贾里尼克 和他的同事的贡献在于提出了统计语言模型，而且很漂亮地解决了所有的细节问题。十几年后，李开复用统计语言模型把 997 词语音识别的问题简化成了一个 20 词的识别问题，实现了有史以来第一次大词汇量非特定人连续语音的识别。

我是一名科学研究人员 ，我在工作中经常惊叹于数学语言应用于解决实际问题上时的神奇。我也希望把这种神奇讲解给大家听。当然，归根结底，不管什莫样的科学方法、无论多莫奇妙的解决手段都是为人服务的。我希望 Google 多努力一分，用户就多一分搜索的喜悦。

谈 Page Rank – Google 的民主表决式网页排名技术

发表者: 吴军， Google 工程师

大家可能听说过，Google 革命性的发明是它名为 “Page Rank” 的网页排名算法，这项技术彻底解决了搜索结果排序的问题。其实最先试图给互联网上的众多网站排序的并不是 Google。Yahoo！ 公司最初第 一个用目录分类的方式让用户通过互联网检索信息，但由于当时计算机容量和速度的限制，当时的 Yahoo！ 和同时代的其它搜索引擎都存在一个共同的问题： 收录的网页太少，而且只能对网页中常见内容相关的实际用词进行索引。那时，用户很难找到很相关信息。我记得 1999 年以前查找一篇论文，要换好几个搜索引擎。后来 DEC 公司开发了 AltaVista 搜索引擎，只用一台 ALPHA 服务器，却收录了比以往引擎都多的网页，而且对里面的每个词进行索引。AltaVista 虽然让用户搜索到大量结果，但大部分结果却与查询不太相关，有时找想看的网页需要翻好几页。所以最初的 AltaVista 在一定程度上解决了覆盖率的问题，但不能很好地对结果进行排序。

Google 的 “Page Rank” （网页排名）是怎么回事呢？其实简单说就是民主表决。打个比方，假如我们要找李开复博士，有一百个人举手说自己是李开复。那么谁是真的呢？也许有好几个真 的，但即使如此谁又是大家真正想找的呢？:-) 如果大家都说在 Google 公司的那个是真的，那么他就是真的。

在互联网上，如果一 个网页被很多其它网页所链接，说明它受到普遍的承认和信赖，那么它的排名就高。这就是 Page Rank 的核心思想。 当然 Google 的 Page Rank 算法实际上要复杂得多。比如说，对来自不同网页的链接对待不同，本身网页排名高的链接更可靠，于是给这些链接予较大的权重。Page Rank 考虑了这个因素，可是现在问题又来了，计算搜索结果的网页排名过程中需要用到网页本身的排名，这不成了先有鸡还是先有蛋的问题了吗？

Google 的两个创始人拉里•佩奇 （Larry Page ）和谢尔盖•布林 (Sergey Brin) 把这个问题变成了一个二维矩阵相乘的问题，并且用迭代的方法解决了这个问题。他们先假定所有网页的排名是相同的，并且根据这个初始值，算出各个网页的第一 次迭代排名，然后再根据第一次迭代排名算出第二次的排名。他们两人从理论上证明了不论初始值如何选取，这种算法都保证了网页排名的估计值能收敛到他们的真 实值。值得一提的事，这种算法是完全没有任何人工干预的。

理论问题解决了，又遇到实际问题。因为互联网上网页的数量是巨大的，上面提到的 二维矩阵从理论上讲有网页数目平方之多个元素。如果我们假定有十亿个网页，那么这个矩阵 就有一百亿亿个元素。这样大的矩阵相乘，计算量是非常大的。拉里和谢尔盖两人利用稀疏矩阵计算的技巧，大大的简化了计算量，并实现了这个网页排名算法。今 天 Google 的工程师把这个算法移植到并行的计算机中，进一步缩短了计算时间，使网页更新的周期比以前短了许多。

我来 Google 后，拉里 (Larry) 在和我们几个新员工座谈时，讲起他当年和谢尔盖(Sergey) 是怎么想到网页排名算法的。他说："当时我们觉得整个互联网就像一张大的图 （Graph)，每个网站就像一个节点，而每个网页的链接就像一个弧。我想，互联网可以用一个图或者矩阵描述，我也许可以用这个发现做个博士论文。" 他和谢尔盖就这样发明了 Page Rank 的算法。

网页排名的高明之处在于它把整个互联网当作了一个整体对待。它无意识中符合了系统论的观点。相比之下，以前的信息检索大多把每一个网页当作独立的个体对待，很多人当初只注意了网页内容和查询语句的相关性，忽略了网页之间的关系。

今天，Google 搜索引擎比最初复杂、完善了许多。但是网页排名在 Google 所有算法中依然是至关重要的。在学术界, 这个算法被公认为是文献检索中最大的贡献之一，并且被很多大学引入了信息检索课程 (Information Retrieval) 的教程

男人好色是健康的体现~~~

动物界雄性看到心仪的异性，向来是二话不说就扑上去的。相比之下，人类已经很克制了。而且当你面对这种坦荡的男人时，你会很容易洞察他的性情，不喜欢也可以赶紧

避让，安全系数相对较高。男人就是应该好色，不好色，你就得怀疑一下他是不是健康的了。

记得在一个饭局上，曾经和两位成功女性探讨关于男人好色的问题，两位都已结婚，但观点一致："这男人要是不好色还有什么意思啊？"说得多好啊！这么多年都没找到理论基础，这回在现实中得到了印证。让我来给女士们总结一下男人不好色的几大原因，利用反证法来自圆其说。

一、首先，性趋向不常规的男士(还有什么表述清楚又不带歧视色彩的词汇吗)，肯定就不近女色了，这也是女性最接受不了的，除非你们想扮演一对貌合神离的夫妻。当然如果你碰巧遇到TomFord这样的双性恋男人，也只能自己作出选择了。

二、曾经有一个自称不好色的男人站在你面前，你信吗？有一种说法是这个社会的发展靠的就是男人雄性激素的分泌。所以对那些摆出道貌岸然姿态的男人，你都可以管他们叫"大尾巴狼"，这种人更危险。以绅士面貌进入你的生活，一有机会就会露出狼的本色，低劣的角色扮演。相反，一个敢于承认自己好色的男人，你绝不能说他思想复杂，他是单纯，不爱掩饰而已。而且当你面对这种坦荡的男人时，你会很容易洞察他的性情，不喜欢也可以赶紧避让，安全系数相对较高。

大师李敖从来没否认过自己对女人的喜爱，一边在宣扬自己的幸福家庭，一边又在电视节目中自报最后一任女朋友是两年前认识的一个1984年出生的美女，看来在他的字典里没有"晚节不保"这个词语。他最经典的理论就是：一个男人遇到喜欢的姑娘就一定要表达出来，很多人因为爱面子而退缩，一个男人如果爱面子超过爱女人，那将是件可悲的事情。

三、一个缺乏生活情趣的男人估计不好色，他们每天的工作议程不是算计人，就是防止被别人算计，所以一天算下来已经身心疲惫了。生活中很多美好的事物在他眼里都平淡无奇，而他本身也像是天泡在白水里的人，索然无味。以我个人的认识，好色是对生活充满希望的上进态度，如果用四个字总结，那就是--热爱生活。

听过那个笑话吗？一个老男人找到医生问："我怎么才能长命百岁呢？"医生说："你暴饮暴食吗？爱慕虚荣吗？过度工作吗？贪恋女色吗？"回答都是否定。既而医生又问："那你为什么要活那么长呢？"

四、好色也是需要硬件条件的，一个体弱多病的男人，
心里想的第一件事是如何活下去，哪有闲心好色呢？雄性总希望拥有更多的异性伴侣，究其根源，可能是希望优秀基因更多更广地传播下去，就像狮群中的首领那样，这是自然法则对人类的心理暗示。看，我们终于找到有科技含量的依据了，真不是他们坏啊。由此看出，为什么那些强健的男士被称为种男，也更有女人缘的原因了。

前两年NBA巨星乔丹出过一些性丑闻，媒体以尖刻的言辞对此事大加渲染，似乎连他在篮球上的成就也要一并颠覆。事实证明，这些批判在他的男性球迷心中几乎没有激起丝毫的涟漪。他们心底藏着一句话："没事儿吧你？像乔丹这样的优秀人种，我们难道不该多留下一些基因吗？"

在此我们需要明确一点，历史上没有哪个男人是因为好色而被世人称颂的。在"风流"后面需加上"才子"二字才算是有里有面儿、功德圆满。唐伯虎是有不少艳遇，谁让人家画儿画得好。所以我们在对好色男人宽容的同时，并没有忽略对他们完善自我方面的高标准严要求。修身出众者接近异性向来顺其自然，不需要摆局下套儿。无才无德再没体力，好起色来也挺费劲的，不提倡。

综上所述，女人似乎唯有选择好色男人才能幸福一生似的。现在就得好分析一下实际问题了--好色是否就意味着不专情。类似问题我再问一个："胳膊粗是否就一定得打人才能显出来？我国追求上进研究核武器，是否一定要扔在邻国两颗方显大国之威？有明星潜质就都能成超女吗？"看了这些问题，你似乎可以松一下心了，好色并不意味着一定要博爱。可我真正想说的是，好色真的有更多机会勾引或被勾引。但我们今天更需要的是有情趣、有品质的生活，天天喝白水你受得了吗？

在选择好色老公之前，有以下几点建议：

请选择好色而有魅力的老公，只好色没魅力的人靠边站去吧。

他既然可以吸引你，也会吸引别人，只要不是勾引，应该给他交流空间。好色的品性是随时随地都会发散的，但一个有理智的男人完全可以分清哪道是主菜、哪道是甜品。男人世界中，他们可以谈论色，但决不会讨论如何分裂家庭。

你就那么没自信吗？就不能成为他眼中那块不可替代的色？添点魅力可不可以？男人对色的认识也不只停留在外貌上，才智占有重要地位，李诗诗不还吹拉弹唱样样精通的吗？简单点的办法是买些漂亮衣服，最好用他的钱买。

退一万步，再告诉你一句话：最好的防守就是进攻，好色已不是男人的专利。你也可以武装到牙齿，行使自己好色的权利。

中文元搜索引擎简单比较

北斗搜索 推荐

一、明确概念

百狗、百度谷歌不算元搜索引擎，因为它们仅仅在一个网页中展示两个或多个搜索引擎的结果；真正的元搜索引擎是指把用户的搜索请求提交给多个独立的搜索引擎， 然后对返回的搜索结果进行去重、排序等工作，再把处理后的结果显示给用户。

具体可参考邢志宇老师的《集成搜索引擎和元搜索引擎》。

二、中文元搜索引擎

1、万纬搜索

据说是最早的中文元搜索引擎，还有学术论文以其作代表论述元搜索引擎。但现在貌似不可用了，速度慢且不说，搜索完成后，

出来一句话：共查到 N 条记录符合字符串 X 本次取出 1 - 0 条

没有结果，怎么玩！

2、壹家搜

速度慢，动不动就宕掉了；标题都显示是“百度快照”。

3、知合网的网页搜索

速度较慢，这个知合网的网页搜索，我记得以前是综合百度、Google搜索结果的，但现在跟百度的结果完全相同。这样的话，有什么意义呢！

4、我要搜搜你

首页上介绍说“综合了Baidu,Google,Yahoo的搜索结果” “结果比他们好一些”，但随意搜索几个词，很明显是比他们差很多。

搜“Google”，Baidu,Google,Yahoo排第一的都是Google的主站（Google.com或Google.cn）,而我要搜搜你排第一的是

下载 Google 桌面，这个结果仅仅在百度排第五，Google、Yahoo前十项中都没有；真不知它是什么算出来的。

5、deyeb 社会化搜索引擎

上一篇文章《中文元搜索引擎(欢迎补充)》发表后，bookye说“最知名的deyeb社会化搜索，你怎么落下了呢”。使用deyeb 后，发现仅仅热门词有结果，稍微冷一些的词，就无结果了。搜“李宇春”，有97个结果；搜“何洁”， 就只有一项指向http://www.deyeb.cn/

的百度贴吧_何洁吧。更别说普通的词了，多数是无结果。deyeb不能算是搜索引擎。

6、北斗搜索

跟前面地比较，北斗是目前唯一能用的元搜索引擎，当然也是最好的了。速度还可以；结果来自百度、搜狗、雅虎；左侧有深入搜索、相关搜索； 缩略图功能很cool；可以评价结果。


※所谓元搜索引擎，最重要的是把各独立搜索引擎的结果进行二次处理，重新排序。

但 Xisoso 元搜索号称元搜索，也写着“Google+baidu”、“Google+Yahoo”等，但实际上显示的结果都是某一搜索引擎的结果。“Google+baidu”的结果都是百度的，“Google+Yahoo”都是雅虎的。

bbmao 顶多只能是集成搜索引擎。它仅仅在搜索结果页显示各搜索引擎的图标，点击图标，显示相应搜索引擎的结果；默认的bbmao显示的是百度的结果。Google、sogou还不愿被它框住，自动跳转。把别人的搜索结果拿过来，放上自己的广告，bbmao的生意可真会做！

知合网的网页搜索，以前是综合百度、Google的结果，但现在仅仅显示百度的结果。当然不是元搜索引擎。

六度分隔与最短路径

【最短路径】

圆明园的北部有一个迷宫，据说古时候每次有庆典在圆明园的时候，皇帝会派一些宫女走迷宫，看谁最先走到迷宫内的亭子，会有不错的奖赏。

迷宫问题对数学家们来讲虽然是小儿科但在计算机课程上却非常重要，因为不同的求解会涉及到递归，广度优先和深度优先等算法。

迷宫毕竟是一个放置在2维空间的有限联系的网络，也就是说，迷宫里的每一个点，最多只和周围的4个点(上下左右)发生关系，而且这些点的位置是固定的。

六度分割通常用来描述一个广阔的社会网路（SN），现在大部分的社会网路服务都提供了搜索功能，即搜索出一个用户到达另外一个用户的最短路径，也就是找出这两个用户之间通过最少的用户的链接。

一般的SN提供的搜索都是4度的，也就是例如A-B-C-D-E 称为4度的分隔。提供5度搜索和6度搜索的几乎寥寥无几，当然一方面是5，6度分隔的用户很少，大部分的用户都应该在4度内，另外一个方面是5，6度分隔的搜索在实际计算上也涉及非常大的运算量。

【SN搜索算法】

如果说寻找两个人之间的最小分隔的路径和寻找最短路径可以类比，那么唯一不同的是SN上每个节点的联系可以非常的广阔，不只是上下左右，而是十个甚 至上百个联系。这是是一个多维空间内的最短路径的寻找。假设一个用户平均有n个好友，那么粗略估计一个用户的4度好友大约有n×n×n×n＋n×n×n+ n×n+n ~ n^4，无疑是一个非常恐怖的数目。因此采用传统的递归的方法显然是不大现实的。

当然，事情并非这么麻烦，有简洁的方法可以加快找到用户之间的最小分隔：不单是从一个用户搜索，而是从两个用户同时搜索，而看两个用户的2度之内的用户是否有相同：
A-B-C
E-D-C
A和E的处在在两度分隔的用户基本上数目估计都在n的平方。问题变成了比较n^2和n^2之间有没有相同，这个计算的时间等同于2×n^2的排序所需要的时间。

【SN索引】

那么能否继续加快速度？
当然可以，可以提前对用户的好友进行索引，对好友的好友进行索引，这样在未来进行关系的搜索时会大大加快：

A: {A1} {A2} A1为A的好友的集合，A2为A的好友的好友的集合
E: {E1} {E2}

那么
1度分隔为： A 属于｛E1｝，等同于E属于 {A1}
2度分隔为： A 属于｛E2｝，等同于E属于 {A2}，{A1}{E1}有共同项。
3度分隔为： {A1} ｛E2｝有共同项，等同于A属于 {E2}
4度分隔为： {A2} ｛E2｝有共同项

【SN关系的更新】

当然，发现是一个核心问题，另外一个问题就是更新，因为SN的关系不会是一成不变的，在一个活跃的SN社区里，每天用户之间的关系的更新更是可观。这里只考虑关系添加的例子：

A: {A1} {A2}
E: {E1} {E2}

当A 与 E 直接建立了好友关系后，应该说整合系统的关系全都变化了，因为这个新的关系一定会导致一些关系的短路，从而导致很多现有的关系的调整。但是因为我们只存储 2度分隔以内的关系，也只关心两度分隔以内的关系，因此当发生了一个新的关系后，2度内关系的变化一定是A和E本身或者他们的一度关系的用户，再远的用户 将不受这个关系的影响。

因此首先 所有｛A1｝的元素的二度分隔集合里要加上E，所有｛E1｝的元素的二度分隔集合里要加上A。

然后是二度的修正。分别加上对方的1度。
{A2} = {A2 + E1}
{E2} = {E2 + A1}

最后是一度的修正：A, E 的 一度{A1}{E1}需要加入E,A:
{A1} = {A1 + E}
{E1} = {E1 + A}

整体操作的量大约在2n次操作，比我们通常认为的要小的多 :) 。