数学之美-数学之美-2

数学之美-2

我们还是看上回的例子，查找关于“原子能的应用”的网页。我们第一步是在索引中找到包含这三个词的网页（详见关于布尔运算的系列）。现在任何一个搜索引擎都包含几十万甚至是上百万个多少有点关系的网页。那么哪个应该排在前面呢？显然我们应该根据网页和查询“原子能的应用”的相关性对这些网页进行排序。因此，这里的关键问题是如何度量网页和查询的相关性。我们知道，短语“原子能的应用”可以分成三个关键词：原子能、的、应用。根据我们的直觉，我们知道，包含这三个词多的网页应该比包含它们少的网页相关。当然，这个办法有一个明显的漏洞，就是长的网页比短的网页占便宜，因为长的网页总的来讲包含的关键词要多些。因此我们需要根据网页的长度，对关键词的次数进行归一化，也就是用关键词的次数除以网页的总字数。我们把这个商称为“关键词的频率”，或者“单文本词汇频率”（Term Frequency)，比如，在某个一共有一千词的网页中“原子能”、“的”和“应用”分别出现了 2 次、35 次和 5 次，那么它们的词频就分别是 0.002、0.035 和 0.005。我们将这三个数相加，其和 0.042 就是相应网页和查询“原子能的应用”相关性的一个简单的度量。概括地讲，如果一个查询包含关键词 w1,w2,...,wN, 它们在一篇特定网页中的词频分别是: TF1, TF2, ..., TFN 。（TF: term frequency)。那么，这个查询和该网页的相关性就是: TF1 + TF2 + ... + TFN。读者可能已经发现了又一个漏洞。在上面的例子中，词“的”站了总词频的 80% 以上，而它对确定网页的主题几乎没有用。我们称这种词叫“应删除词” （Stopwords)，也就是说在度量相关性是不应考虑它们的频率。在汉语中，应删除词还有“是”、“和”、“中”、“地”、“得”等等几十个。忽略这些应删除词后，上述网页的相似度就变成了 0.007，其中“原子能”贡献了 0.002，“应用”贡献了 0.005。细心的读者可能还会发现另一个小的漏洞。在汉语中，“应用”是个很通用的词，而“原子能”是个很专业的词，后者在相关性排名中比前者重要。因此我们需要给汉语中的每一个词给一个权重，这个权重的设定必须满足下面两个条件：1. 一个词预测主题能力越强，权重就越大，反之，权重就越小。我们在网页中-----------------------------------------------------Page 21-----------------------------------------------------看到“原子能”这个词，或多或少地能了解网页的主题。我们看到“应用”一次，对主题基本上还是一无所知。因此，“原子能“的权重就应该比应用大。2. 应删除词的权重应该是零。我们很容易发现，如果一个关键词只在很少的网页中出现，我们通过它就容易锁定搜索目标，它的权重也就应该大。反之如果一个词在大量网页中出现，我们看到它仍然不很清楚要找什么内容，因此它应该小。概括地讲，假定一个关键词ｗ在Ｄｗ个网页中出现过，那么Ｄｗ越大，ｗ的权重越小，反之亦然。在信息检索中，使用最多的权重是 “ 逆文本频率指数 ” （Inverse document frequency 缩写为ＩＤＦ），它的公式为ｌｏｇ（Ｄ／Ｄｗ）其中Ｄ是全部网页数。比如，我们假定中文网页数是Ｄ＝１０亿，应删除词“的”在所有的网页中都出现，即Ｄｗ＝１０亿，那么它的ＩＤＦ＝log(10 亿/10 亿）= log (1) = ０。假如专用词“原子能”在两百万个网页中出现，即Ｄｗ＝２００万，则它的权重ＩＤＦ＝log(500) =6.2。又假定通用词“应用”，出现在五亿个网页中，它的权重ＩＤＦ = log(2)则只有 0.7。也就只说，在网页中找到一个“原子能”的比配相当于找到九个 “应用”的匹配。利用 IDF，上述相关性计算个公式就由词频的简单求和变成了加权求和，即 TF1*IDF1 + TF2*IDF2 ＋... + TFN*IDFN。在上面的例子中，该网页和“原子能的应用”的相关性为 0.0161，其中“原子能”贡献了 0.0126，而“应用”只贡献了 0.0035。这个比例和我们的直觉比较一致了。ＴＦ／ＩＤＦ（term frequency/inverse document frequency) 的概念被公认为信息检索中最重要的发明。在搜索、文献分类和其他相关领域有广泛的应用。讲起 TF/IDF 的历史蛮有意思。IDF 的概念最早是剑桥大学的斯巴克－琼斯[注：她有两个姓］ (Karen Sparck Jones)提出来的。斯巴克－琼斯１９７２年在一篇题为关键词特殊性的统计解释和她在文献检索中的应用的论文中提出ＩＤＦ。遗憾的是，她既没有从理论上解释为什么权重ＩＤＦ应该是对数函数ｌｏｇ（Ｄ／Ｄｗ）（而不是其它的函数，比如平方根），也没有在这个题目上作进一步深入研究，以至于在以后的很多文献中人们提到ＴＦ／ＩＤＦ时没有引用她的论文，绝大多数人甚至不知道斯巴克－琼斯的贡献。同年罗宾逊写了个两页纸的解释，解释得很不好。倒是后来康乃尔大学的萨尔顿（Salton)多次写文章、写书讨论 TF/IDF 在信息检索中的用途，加上萨尔顿本人的大名（信息检索的世界大奖就是以萨尔顿的名字命名的）。很多人都引用萨尔顿的书，甚至以为这个信息检索中最重要的概念是他提出的。当然，世界并没有忘记斯巴克－琼斯的贡献，2004 年，在纪念文献学学报创刊 60 周年之际，该学报重印了斯巴克-琼斯的大作。罗宾逊在同期期刊上写了篇文章，用香农的信息论解释 IDF，这回的解释是对的，但文章写的并不好、非常冗长（足足十八页），把一个简单问题搞复杂了。其实，信息论的学者们已经发现并指出，其实 IDF 的概念就是一个特定条件下、关键词的概率分布的交叉熵（Kullback-Leibler Divergence)（详见上一系列）。这样，信息检索相关性的度量，又回到了信息论。现在的搜索引擎对 TF/IDF 进行了不少细微的优化，使得相关性的度量更加准确了。当然，对有兴趣写一个搜索引擎的爱好者来讲，使用 TF/IDF 就足够了。-----------------------------------------------------Page 22-----------------------------------------------------如果我们结合上网页排名(Page Rank)，那么给定一个查询，有关网页综合排名大致由相关性和网页排名乘积决定。-----------------------------------------------------Page 23-----------------------------------------------------十、有限状态机和地址识别2006 年 7 月 5 日上午 09:09:00发表者：吴军，Google 研究员地址的识别和分析是本地搜索必不可少的技术，尽管有许多识别和分析地址的方法，最有效的是有限状态机。一个有限状态机是一个特殊的有向图（参见有关图论的系列），它包括一些状态（节点）和连接这些状态的有向弧。下图是一个识别中国地址的有限状态机的简单的例子。每一个有限状态机都有一个启始状态和一个终止状态和若干中间状态。每一条弧上带有从一个状态进入下一个状态的条件。比如，在上图中，当前的状态是 “省”，如果遇到一个词组和（区）县名有关，我们就进入状态“区县”；如果遇到的下一个词组和城市有关，那么我们就进入“市”的状态，如此等等。如果一条地址能从状态机的起始状态经过状态机的若干中间状态，走到终止状态，那么这条地址则有效，否则无效。比如说，“北京市双清路 83 号”对于上面的有限状态来讲有效，而 “上海市辽宁省马家庄”则无效（因为无法从市走回到省）。使用有限状态机识别地址，关键要解决两个问题，即通过一些有效的地址建立状态机，以及给定一个有限状态机后，地址字串的匹配算法。好在这两个问题都有现成的算法。有了关于地址的有限状态机后，我们就可又用它分析网页，找出网页中的地址部分，建立本地搜索的数据库。同样，我们也可以对用户输入的查询进行分析，挑出其中描述地址的部分，当然，剩下的关键词就是用户要找的内容。比如，对于用户输入的“北京市双清路附近的酒家”，Google 本地会自动识别出地址“北京市双清路”和要找的对象“酒家”。-----------------------------------------------------Page 24-----------------------------------------------------上述基于有限状态机的地址识别方法在实用中会有一些问题：当用户输入的地址不太标准或者有错别字时，有限状态机会束手无策，因为它只能进行严格匹配。（其实，有限状态机在计算机科学中早期的成功应用是在程序语言编译器的设计中。一个能运行的程序在语法上必须是没有错的，所以不需要模糊匹配。而自然语言则很随意，无法用简单的语法描述。）为了解决这个问题，我们希望有一个能进行模糊匹配、并给出一个字串为正确地址的可能性。为了实现这一目的，科学家们提出了基于概率的有限状态机。这种基于概率的有限状态机和离散的马尔可夫链（详见前面关于马尔可夫模型的系列）基本上等效。在八十年代以前，尽管有不少人使用基于概率的有限状态机，但都是为自己的应用设计专用的有限状态机的程序。九十年代以后，随着有限状态机在自然语言处理的广泛应用，不少科学家致力于编写通用的有限状态机程序库。其中，最成功的是前 AT&T 实验室的三位科学家，莫瑞（Mohri）, 皮瑞尔（Pereira）和瑞利（Riley）。他们三人花了很多年时间，编写成一个通用的基于概率的有限状态机 C 语言工具库。由于 AT&T 有对学术界免费提供各种编程工具的好传统，他们三人也把自己多年的心血拿出来和同行们共享。可惜好景不长，AT&T 实验室风光不再，这三个人都离开了 AT&T，莫瑞成了纽约大学的教授，皮瑞尔当了宾西法尼亚大学计算机系系主任，而瑞利成了 Google 的研究员，AT&T 实验室的新东家不再免费提供有限状态机 C 语言工具库。虽然此前莫瑞等人公布了他们的详细算法，但是省略了实现的细节。因此在学术界，不少科学家能够重写同样功能的工具库，但是很难达到 AT&T 工具库的效率（即运算速度），这的确是一件令人遗憾的事。-----------------------------------------------------Page 25-----------------------------------------------------十一、 Google 阿卡 47 的制造者阿米特.辛格博士2006 年 7 月 10 日上午 09:52:00发表者：Google 研究员，吴军枪迷或者看过尼古拉斯.凯奇（Nicolas Cage)主演的电影“战争之王”（Lord of War)的人也许还记得影片开头的一段话：（在所有轻武器中，）最有名的是阿卡 47( AK47)冲锋枪(也就是中国的五六式冲锋枪的原型），因为它从不卡壳、从不损坏、可在任何环境下使用、可靠性好、杀伤力大并且操作简单。我认为，在计算机中一个好的算法，应该向阿卡 47 冲锋枪那样简单、有效、可靠性好而且容易读懂(或者说易操作），而不应该是故弄玄虚。Google 的杰出工程师阿米特.辛格博士 (Amit Singhal) 就是为 Google 设计阿卡 47 冲锋枪的人，在公司内部，Google 的排序算法便是以他的名字命名的。从加入 Google 的第一天，我就开始了和辛格长期而愉快的合作，而他一直是我的一个良师益友。辛格、Matt Cutts（中国一些用户误认为他是联邦调查局特工，当然他不是）、马丁和我四个人当时一同研究和解决网络搜索中的作弊问题（Spam)。我们需要建一个分类器，我以前一直在学术界工作和学习，比较倾向找一个很漂亮的解决方案。我设计了一个很完美的分类器，大约要花三个月到半年时间来实现和训练，而辛格认为找个简单有效的办法就行了。我们于是尽可能简化问题，一、两个月就把作弊的数量减少了一半。当时我们和公司工程副总裁罗森打了个赌，如果我们能减少 40% 的作弊，他就送我们四个家庭去夏威夷度假，后来罗森真的履约了。这个分类器设计得非常小巧（只用很小的内存），而且非常快速（几台服务器就能处理全球搜索的分类），至今运行得很好。后来我和辛格一起又完成了许多项目，包括对中、日、韩文排名算法的改进。每一次，辛格总是坚持找简单有效的解决方案。这种做法在 Google 这个人才济济的公司常常招人反对，因为很多资深的工程师怀疑这些简单方法的有效性。不少人试图用精确而复杂的办法对辛格的设计的各种“阿卡 47” 进行改进，后来发现几乎所有时候，辛格的简单方法都接近最优化的解决方案，而且还快得多。另一条选择简单方案的原因是这样设计的系统很容易查错（debug)。当然，辛格之所以总是能找到那些简单有效的方法，不是靠直觉，更不是撞大运，而是靠他丰富的研究经验。辛格早年从师于搜索大师萨尔顿(Salton)教授，毕业后就职于 AT&T 实验室。在那里，他和两个同事半年就搭起了一个中等规模的搜索引擎，这个引擎索引的网页数量虽然无法和商用的引擎相比，但是准确性却非常好。在 AT&T，他对搜索问题的各个细节进行了仔细的研究，他的那些简单而有效的解决方案，常常是深思熟虑去伪存真的结果。辛格非常鼓励年轻人不怕失败，大胆尝试。一次一位刚毕业不久的工程师因为把带有错误的程序推出到 Google 的服务器上而惶惶不可终日。辛格安慰她讲，-----------------------------------------------------Page 26-----------------------------------------------------你知道，我在 Google 犯的最大一次错误是曾经将所有网页的相关性得分全部变成了零，于是所有搜索的结果全部是随机的了。这位工程师后来为 Google 开发了很多好的产品。辛格在 AT&T 时确立了他在学术界的地位，但是，他不是一个满足于做实验写论文的人，于是他离开了实验室来到了当时只有百、十人的 Google。在这里，他得以施展才智，重写了 Google 的排名算法，并且一直在负责改进它。辛格因为舍不得放下两个孩子，很少参加各种会议，但是他仍然被学术界公认为是当今最权威的网络搜索专家。2005 年，辛格作为杰出校友被请回母校康乃尔大学计算机系在 40 年系庆上作报告，获得这一殊荣的还有大名鼎鼎的美国工程院院士，计算机独立磁盘冗余阵列（RAID)的发明人凯茨(Randy Katz) 教授。-----------------------------------------------------Page 27-----------------------------------------------------十二、余弦定理和新闻的分类2006 年 7 月 20 日上午 10:12:00发表者：吴军，Google 研究员余弦定理和新闻的分类似乎是两件八杆子打不着的事，但是它们确有紧密的联系。具体说，新闻的分类很大程度上依靠余弦定理。Google 的新闻是自动分类和整理的。所谓新闻的分类无非是要把相似的新闻放到一类中。计算机其实读不懂新闻，它只能快速计算。这就要求我们设计一个算法来算出任意两篇新闻的相似性。为了做到这一点，我们需要想办法用一组数字来描述一篇新闻。我们来看看怎样找一组数字，或者说一个向量来描述一篇新闻。回忆一下我们在 “ 如何度量网页相关性 ” 一文中介绍的TF/IDF 的概念。对于一篇新闻中的所有实词，我们可以计算出它们的单文本词汇频率/逆文本频率值（TF/IDF)。不难想象，和新闻主题有关的那些实词频率高， TF/IDF 值很大。我们按照这些实词在词汇表的位置对它们的 TF/IDF 值排序。比如，词汇表有六万四千个词，分别为单词编号汉字词----------------- - 1 阿 2 啊3 阿斗 4 阿姨 ...789 服装 ....64000 做作在一篇新闻中，这 64,000 个词的 TF/IDF 值分别为单词编号 TF/IDF 值 ============== 1 02 0.0 034 3 04 0.0 0052 5 0 ...789 0 .034 ...-----------------------------------------------------Page 28-----------------------------------------------------64000 0.075如果单词表中的某个次在新闻中没有出现，对应的值为零，那么这 64,000 个数，组成一个 64,000 维的向量。我们就用这个向量来代表这篇新闻，并成为新闻的特征向量。如果两篇新闻的特征向量相近，则对应的新闻内容相似，它们应当归在一类，反之亦然。学过向量代数的人都知道，向量实际上是多维空间中有方向的线段。如果两个向量的方向一致，即夹角接近零，那么这两个向量就相近。而要确定两个向量方向是否一致，这就要用到余弦定理计算向量的夹角了。余弦定理对我们每个人都不陌生，它描述了三角形中任何一个夹角和三个边的关系，换句话说，给定三角形的三条边，我们可以用余弦定理求出三角形各个角的角度。假定三角形的三条边为 a, b 和 c，对应的三个角为 A, B 和 C，那么角 A 的余弦 --如果我们将三角形的两边 b 和 c 看成是两个向量，那么上述公式等价于其中分母表示两个向量 b 和 c 的长度，分子表示两个向量的内积。举一个具体的例子，假如新闻 X 和新闻 Y 对应向量分别是 x1,x2,...,x64000 和 y1,y2,...,y64000,那么它们夹角的余弦等于，当两条新闻向量夹角的余弦等于一时，这两条新闻完全重复（用这个办法可以删除重复的网页）；当夹角的余弦接近于一时，两条新闻相似，从而可以归成一类；夹角的余弦越小，两条新闻越不相关。-----------------------------------------------------Page 29-----------------------------------------------------我们在中学学习余弦定理时，恐怕很难想象它可以用来对新闻进行分类。在这里，我们再一次看到数学工具的用途。-----------------------------------------------------Page 30-----------------------------------------------------十三、信息指纹及其应用2006 年 8 月 3 日上午 11:17:00发表者：吴军，Google 研究员任何一段信息文字，都可以对应一个不太长的随机数，作为区别它和其它信息的指纹（Fingerprint)。只要算法设计的好，任何两段信息的指纹都很难重复，就如同人类的指纹一样。信息指纹在加密、信息压缩和处理中有着广泛的应用。我们在图论和网络爬虫一文中提到，为了防止重复下载同一个网页，我们需要在哈希表中纪录已经访问过的网址（URL)。但是在哈希表中以字符串的形式直接存储网址，既费内存空间，又浪费查找时间。现在的网址一般都较长，比如，如果在 Google 或者百度在查找数学之美，对应的网址长度在一百个字符以上。下面是百度的链接m/s?ie=gb2312&bs=%CA%FD%D1%A7%D6%AE%C3%C0&sr=& z=&cl=3&f=8&wd=%CE%E2%BE%FC+%CA%FD%D1%A7%D6%AE%C3%C0&ct=0假定网址的平均长度为一百个字符，那么存贮 200 亿个网址本身至少需要 2 TB，即两千 GB 的容量，考虑到哈希表的存储效率一般只有 50%，实际需要的内存在 4 TB以上。即使把这些网址放到了计算机的内存中，由于网址长度不固定，以字符串的形式查找的效率会很低。因此，我们如果能够找到一个函数，将这 200 亿个网址随机地映射到 128 二进位即 16 个字节的整数空间，比如将上面那个很长的字符串对应成一个如下的随机数:893249432984398432980545454543这样每个网址只需要占用 16 个字节而不是原来的一百个。这就能把存储网址的内存需求量降低到原来的 1/6。这个 16 个字节的随机数，就称做该网址的信息指纹（Fingerprint)。可以证明，只要产生随机数的算法足够好，可以保证几乎不可能有两个字符串的指纹相同，就如同不可能有两个人的指纹相同一样。由于指纹是固定的 128 位整数，因此查找的计算量比字符串比较小得多。网络爬虫在下载网页时，它将访问过的网页的网址都变成一个个信息指纹，存到哈希表中，每当遇到一个新网址时，计算机就计算出它的指纹，然后比较该指纹是否已经在哈希表中，来决定是否下载这个网页。这种整数的查找比原来字符串查找,可以快几倍到几十倍。产生信息指纹的关键算法是伪随机数产生器算法（prng)。最早的 prng 算法是由计算机之父冯诺伊曼提出来的。他的办法非常简单，就是将一个数的平方掐头去尾，取中间的几位数。比如一个四位的二进制数 1001（相当于十进制的 9），其平方为 01010001 (十进制的 81）掐头去尾剩下中间的四位 0100。当然这种-----------------------------------------------------Page 31-----------------------------------------------------方法产生的数字并不很随机，也就是说两个不同信息很有可能有同一指纹。现在常用的 MersenneTwister 算法要好得多。信息指纹的用途远不止网址的消重，信息指纹的的孪生兄弟是密码。信息指纹的一个特征是其不可逆性, 也就是说,无法根据信息指纹推出原有信息，这种性质，正是网络加密传输所需要的。比如说，一个网站可以根据用户的Cookie 识别不同用户，这个 cookie 就是信息指纹。但是网站无法根据信息指纹了解用户的身份，这样就可以保护用户的隐私。在互联网上，加密的可靠性，取决于是否很难人为地找到拥有同一指纹的信息，比如一个黑客是否能随意产生用户的cookie 。从加密的角度讲MersenneTwister，算法并不好，因为它产生的随机数有相关性。互联网上加密要用基于加密伪随机数产生器（csprng)。常用的算法有 MD5 或者 SHA1 等标准，它们可以将不定长的信息变成定长的 128 二进位或者 160 二进位随机数。值得一提的事，SHA1 以前被认为是没有漏洞的，现在已经被中国的王小云教授证明存在漏洞。但是大家不必恐慌，因为这和黑客能真正攻破你的注册信息是还两回事。信息指纹的虽然历史很悠久，但真正的广泛应用是在有了互联网以后，这几年才渐渐热门起来。-----------------------------------------------------Page 32-----------------------------------------------------十四、谈谈数学模型的重要性2006 年 8 月 9 日上午 09:12:00发表者：吴军，Google 研究员[注：一直关注数学之美系列的读者可能已经发现，我们对任何问题总是在找相应的准确的数学模型。为了说明模型的重要性，今年七月份我在 Google 中国内部讲课时用了整整一堂课来讲这个问题，下面的内容是我讲座的摘要。］在包括哥白尼、伽利略和牛顿在内的所有天文学家中，我最佩服的是地心说的提出者托勒密。虽然天文学起源于古埃及，并且在古巴比伦时，人们就观测到了五大行星（金、木、水、火、土）运行的轨迹，以及行星在近日点运动比远日点快。（下图是在地球上看到的金星的轨迹，看过达芬奇密码的读者知道金星大约每四年在天上画一个五角星。）但是真正创立了天文学，并且计算出诸多天体运行轨迹的是两千年前古罗马时代的托勒密。虽然今天我们可能会嘲笑托勒密犯的简单的错误，但是真正了解托勒密贡献的人都会对他肃然起敬。托勒密发明了球坐标，定义了包括赤道和零度经线在内的经纬线，他提出了黄道，还发明了弧度制。当然，他最大也是最有争议的发明是地心说。虽然我们知道地球是围绕太阳运动的，但是在当时，从人们的观测出发，很容易得到地球是宇宙中心的结论。从地球上看，行星的运动轨迹是不规则的，托勒密的伟大之处是用四十个小圆套大圆的方法，精确地计算出了所有行星运动的轨迹。（托勒密继承了毕达格拉斯的一些思想，他也认为圆是最完美的几何图形。）托勒密模型的精度之高，让-----------------------------------------------------Page 33-----------------------------------------------------以后所有的科学家惊叹不已。即使今天，我们在计算机的帮助下，也很难解出四十个套在一起的圆的方程。每每想到这里，我都由衷地佩服托勒密。一千五百年来，人们根据他的计算决定农时。但是，经过了一千五百年，托勒密对太阳运动的累积误差，还是差出了一星期。地心说的示意图，我国天文学家张衡的浑天地动说其实就是地心说。纠正地心说错误不是靠在托勒密四十个圆的模型上再多套上几个圆，而是进一步探索真理。哥白尼发现，如果以太阳为中心来描述星体的运行，只需要 8-10 个圆，就能计算出一个行星的运动轨迹，他提出了日心说。很遗憾的事，哥白尼正确的假设并没有得到比托勒密更好的结果，哥白尼的模型的误差比托勒密地要大不少。这是教会和当时人们认为哥白尼的学说是邪说的一个原因，所以日心说要想让人心服口服地接受，就得更准确地描述行星运动。完成这一使命的是开普勒。开普勒在所有一流的天文学家中，资质较差，一生中犯了无数低级的错误。但是他有两条别人没有的东西，从他的老师第谷手中继承的大量的、在当时最精确的观测数据，以及运气。开普勒很幸运地发现了行星围绕太阳运转的轨道实际是椭圆形的，这样不需要用多个小圆套大圆，而只要用一个椭圆就能将星体运动规律描述清楚了。只是开普勒的知识和水平不足以解释为什么行星的轨道是椭圆形的。最后是伟大的科学家牛顿用万有引力解释了这个问题。故事到这里似乎可以结束了。但是，许多年后，又有了个小的波澜。天文学家们发现，天王星的实际轨迹和用椭圆模型算出来的不太符合。当然，偷懒的办法是接着用小圆套大圆的方法修正，但是一些严肃的科学家在努力寻找真正的原因。英国的亚当斯和法国的维内尔（Verrier）独立地发现了吸引天王星偏离轨道的海王星。讲座结束前，我和 Google 中国的工程师们一同总结了这么几个结论：１. 一个正确的数学模型应当在形式上是简单的。托勒密的模型显然太复杂。）２. 一个正确的模型在它开始的时候可能还不如一个精雕细琢过的错误的模型来的准确，但是，如果我们认定大方向是对的，就应该坚持下去。（日心说开始并没有地心说准确。）３. 大量准确的数据对研发很重要。-----------------------------------------------------Page 34-----------------------------------------------------４. 正确的模型也可能受噪音干扰，而显得不准确；这时我们不应该用一种凑合的修正方法来弥补它，而是要找到噪音的根源，这也许能通往重大发现。在网络搜索的研发中，我们在前面提到的单文本词频/逆文本频率指数（TF/IDF) 和网页排名（page rank)都相当于是网络搜索中的“椭圆模型”，它们都很简单易懂。-----------------------------------------------------Page 35-----------------------------------------------------十五、繁与简自然语言处理的几位精英2006 年 8 月 23 日下午 11:22:00发表者：吴军，Google 研究员我在数学之美系列中一直强调的一个好方法就是简单。但是，事实上，自然语言处理中也有一些特例，比如有些学者将一个问题研究到极致，执著追求完善甚至可以说完美的程度。他们的工作对同行有很大的参考价值，因此我们在科研中很需要这样的学者。在自然语言处理方面新一代的顶级人物麦克尔 · 柯林斯 ( Michael Collins ) 就是这样的人。柯林斯：追求完美柯林斯从师于自然语言处理大师马库斯 (Mitch Marcus)（我们以后还会多次提到马库斯），从宾夕法利亚大学获得博士学位，现任麻省理工学院 (MIT) 副教授（别看他是副教授，他的水平在当今自然语言处理领域是数一数二的），在作博士期间，柯林斯写了一个后来以他名字命名的自然语言文法分析器 (sentence parser)，可以将书面语的每一句话准确地进行文法分析。文法分析是很多自然语言应用的基础。虽然柯林斯的师兄布莱尔 (Eric Brill) 和 Ratnaparkhi 以及师弟 Eisnar 都完成了相当不错的语言文法分析器，但是柯林斯却将它做到了极致，使它在相当长一段时间内成为世界上最好的文法分析器。柯林斯成功的关键在于将文法分析的每一个细节都研究得很仔细。柯林斯用的数学模型也很漂亮，整个工作可以用完美来形容。我曾因为研究的需要，找柯林斯要过他文法分析器的源程序，他很爽快地给了我。我试图将他的程序修改一下来满足我特定应用的要求，但后来发现，他的程序细节太多以至于很难进一步优化。柯林斯的博士论文堪称是自然语言处理领域的范文。它像一本优秀的小说，把所有事情的来龙去脉介绍的清清楚楚，对于任何有一点计算机和自然语言处理知识的人，都可以轻而易举地读懂他复杂的方法。柯林斯毕业后，在 AT&T 实验室度过了三年快乐的时光。在那里柯林斯完成了许多世界一流的研究工作诸如隐含马尔科夫模型的区别性训练方法，卷积核在自然语言处理中的应用等等。三年后，AT&T 停止了自然语言处理方面的研究，柯林斯幸运地在 MIT 找到了教职。在 MIT 的短短几年间，柯林斯多次在国际会议上获得最佳论文奖。相比其他同行，这种成就是独一无二的。柯林斯的特点就是把事情做到极致。如果说有人喜欢“繁琐哲学”，柯林斯就是一个。布莱尔：简单才美在研究方法上，站在柯林斯对立面的典型是他的师兄艾里克 · 布莱尔 ( Eric Brill ) 和雅让斯基，后者我们已经介绍过了，这里就不再重复。与柯林斯从工-----------------------------------------------------Page 36-----------------------------------------------------业界到学术界相反，布莱尔职业路径是从学术界走到工业界。与柯里斯的研究方法相反，布莱尔总是试图寻找简单得不能再简单的方法。布莱尔的成名作是基于变换规则的机器学习方法 (transformation rule based machine learning)。这个方法名称虽然很复杂，其实非常简单。我们以拼音转换字为例来说明它：第一步，我们把每个拼音对应的汉字中最常见的找出来作为第一遍变换的结果，当然结果有不少错误。比如，“常识”可能被转换成“长识”；第二步，可以说是“去伪存真”，我们用计算机根据上下文，列举所有的同音字替换的规则，比如，如果 chang 被标识成“长”，但是后面的汉字是“识”，则将“长”改成“常”；第三步，应该就是“去粗取精”，将所有的规则用到事先标识好的语料中，挑出有用的，删掉无用的。然后重复二三步，直到找不到有用的为止。布莱尔就靠这么简单的方法，在很多自然语言研究领域，得到了几乎最好的结果。由于他的方法再简单不过了，许许多多的人都跟着学。布莱尔可以算是我在美国的第一个业师，我们俩就用这么简单的方法作词性标注 (part of speech tagging)，也就是把句子中的词标成名词动词，很多年内无人能超越。（最后超越我们的是后来加入 Google 的一名荷兰工程师，用的是同样的方法，但是做得细致很多）布莱尔离开学术界后去了微软研究院。在那里的第一年，他一人一年完成的工作比组里其他所有人许多年做的工作的总和还多。后来，布莱尔又加入了一个新的组，依然是高产科学家。据说，他的工作真正被微软重视要感谢 Google，因为有了 Google，微软才对他从人力物力上给于了巨大的支持，使得布莱尔成为微软搜索研究的领军人物之一。在研究方面，布莱尔有时不一定能马上找到应该怎么做，但是能马上否定掉一种不可能的方案。这和他追求简单的研究方法有关，他能在短时间内大致摸清每种方法的好坏。由于布莱尔总是找简单有效的方法，而又从不隐瞒自己的方法，所以他总是很容易被包括作者我自己在内的很多人赶上和超过。好在布莱尔很喜欢别人追赶他，因为，当人们在一个研究方向超过他时，他已经调转船头驶向它方了。一次，艾里克对我说，有一件事我永远追不上他，那就是他比我先有了第二个孩子：）在接下来了系列里，我们还会介绍一个繁与简结合的例子。-----------------------------------------------------Page 37-----------------------------------------------------十六、不要把所有的鸡蛋放在一个篮子里 -- 谈谈最大熵模型（上）2006 年 10 月 8 日上午 07:27:00发表者：Google 研究员，吴军[我们在投资时常常讲不要把所有的鸡蛋放在一个篮子里，这样可以降低风险。在信息处理中，这个原理同样适用。在数学上，这个原理称为最大熵原理 (the maximum entropy principle)。这是一个非常有意思的题目，但是把它讲清楚要用两个系列的篇幅。]前段时间，Google 中国研究院的刘骏总监谈到在网络搜索排名中，用到的信息有上百种。更普遍地讲，在自然语言处理中，我们常常知道各种各样的但是又不完全确定的信息，我们需要用一个统一的模型将这些信息综合起来。如何综合得好，是一门很大的学问。让我们看一个拼音转汉字的简单的例子。假如输入的拼音是"wang-xiao-bo"，利用语言模型，根据有限的上下文(比如前两个词)，我们能给出两个最常见的名字“王小波”和“王晓波”。至于要唯一确定是哪个名字就难了，即使利用较长的上下文也做不到。当然，我们知道如果通篇文章是介绍文学的，作家王小波的可能性就较大；而在讨论两岸关系时，台湾学者王晓波的可能性会较大。在上面的例子中，我们只需要综合两类不同的信息，即主题信息和上下文信息。虽然有不少凑合的办法，比如：分成成千上万种的不同的主题单独处理，或者对每种信息的作用加权平均等等，但都不能准确而圆满地解决问题，这样好比以前我们谈到的行星运动模型中的小圆套大圆打补丁的方法。在很多应用中，我们需要综合几十甚至上百种不同的信息，这种小圆套大圆的方法显然行不通。数学上最漂亮的办法是最大熵(maximum entropy)模型，它相当于行星运动的椭圆模型。“最大熵”这个名词听起来很深奥，但是它的原理很简单，我们每天都在用。说白了，就是要保留全部的不确定性，将风险降到最小。让我们来看一个实际例子。有一次，我去 AT&T 实验室作关于最大熵模型的报告，我带去了一个色子。我问听众“每个面朝上的概率分别是多少”，所有人都说是等概率，即各点的概率均为 1/6。这种猜测当然是对的。我问听众们为什么，得到的回答是一致的：对这个“一无所知”的色子，假定它每一个朝上概率均等是最安全的做法。（你不应该主观假设它象韦小宝的色子一样灌了铅。）从投资的角度看，就是风险最小的做法。从信息论的角度讲，就是保留了最大的不确定性，也就是说让熵达到最大。接着，我又告诉听众，我的这个色子被我特殊处理过，已知四点朝上的概率是三分之一，在这种情况下，每个面朝上的概率是多少？这次，大部分人认为除去四点的概率是 1/3，其余的均是 2/15，也就是说已知的条件（四点概率为 1/3）必须满足，而对其余各点的概率因为仍然无从知道，因此只好认为它们均等。注意，在猜测这两种不同情况下的概率分布时，大家都没有添加任何主-----------------------------------------------------Page 38-----------------------------------------------------观的假设，诸如四点的反面一定是三点等等。（事实上，有的色子四点反面不是三点而是一点。）这种基于直觉的猜测之所以准确，是因为它恰好符合了最大熵原理。最大熵原理指出，当我们需要对一个随机事件的概率分布进行预测时，我们的预测应当满足全部已知的条件，而对未知的情况不要做任何主观假设。（不做主观假设这点很重要。）在这种情况下，概率分布最均匀，预测的风险最小。因为这时概率分布的信息熵最大，所以人们称这种模型叫“最大熵模型”。我们常说，不要把所有的鸡蛋放在一个篮子里，其实就是最大熵原理的一个朴素的说法，因为当我们遇到不确定性时，就要保留各种可能性。回到我们刚才谈到的拼音转汉字的例子，我们已知两种信息，第一，根据语言模型，wang-xiao-bo 可以被转换成王晓波和王小波；第二，根据主题，王小波是作家，《黄金时代》的作者等等，而王晓波是台湾研究两岸关系的学者。因此，我们就可以建立一个最大熵模型，同时满足这两种信息。现在的问题是，这样一个模型是否存在。匈牙利著名数学家、信息论最高奖香农奖得主希萨（Csiszar）证明，对任何一组不自相矛盾的信息，这个最大熵模型不仅存在，而且是唯一的。而且它们都有同一个非常简单的形式 -- 指数函数。下面公式是根据上下文（前两个词）和主题预测下一个词的最大熵模型，其中 w3 是要预测的词（王晓波或者王小波）w1 和 w2 是它的前两个字（比如说它们分别是 “ 出版 ” ，和 “”），也就是其上下文的一个大致估计，subject 表示主题。我们看到，在上面的公式中，有几个参数 lambda 和 Z ，他们需要通过观测数据训练出来。最大熵模型在形式上是最漂亮的统计模型，而在实现上是最复杂的模型之一。我们在将下一个系列中介绍如何训练最大熵模型的诸多参数，以及最大熵模型在自然语言处理和金融方面很多有趣的应用。-----------------------------------------------------Page 39-----------------------------------------------------十六、不要把所有的鸡蛋放在一个篮子里最大熵模型（下）2006 年 11 月 16 日上午 06:50:00发表者：Google 研究员，吴军我们上次谈到用最大熵模型可以将各种信息综合在一起。我们留下一个问题没有回答，就是如何构造最大熵模型。我们已经所有的最大熵模型都是指数函数的形式，现在只需要确定指数函数的参数就可以了，这个过程称为模型的训练。最原始的最大熵模型的训练方法是一种称为通用迭代算法 GIS(generalized iterative scaling) 的迭代算法。GIS 的原理并不复杂，大致可以概括为以下几个步骤：1. 假定第零次迭代的初始模型为等概率的均匀分布。2. 用第 N 次迭代的模型来估算每种信息特征在训练数据中的分布，如果超过了实际的，就把相应的模型参数变小；否则，将它们便大。 3. 重复步骤 2 直到收敛。GIS 最早是由 Darroch 和 Ratcliff 在七十年代提出的。但是，这两人没有能对这种算法的物理含义进行很好地解释。后来是由数学家希萨（Csiszar)解释清楚的，因此，人们在谈到这个算法时，总是同时引用 Darroch 和Ratcliff 以及希萨的两篇论文。GIS 算法每次迭代的时间都很长，需要迭代很多次才能收敛，而且不太稳定，即使在 64 位计算机上都会出现溢出。因此，在实际应用中很少有人真正使用 GIS。大家只是通过它来了解最大熵模型的算法。八十年代，很有天才的孪生兄弟的达拉皮垂(Della Pietra)在 IBM 对 GIS 算法进行了两方面的改进，提出了改进迭代算法 IIS（improved iterative scaling）。这使得最大熵模型的训练时间缩短了一到两个数量级。这样最大熵模型才有可能变得实用。即使如此，在当时也只有 IBM 有条件是用最大熵模型。由于最大熵模型在数学上十分完美，对科学家们有很大的诱惑力，因此不少研究者试图把自己的问题用一个类似最大熵的近似模型去套。谁知这一近似，最大熵模型就变得不完美了，结果可想而知，比打补丁的凑合的方法也好不了多少。于是，不少热心人又放弃了这种方法。第一个在实际信息处理应用中验证了最大熵模型的优势的，是宾夕法尼亚大学马库斯的另一个高徒原 IBM 现微软的研究员拉纳帕提(Adwait Ratnaparkhi)。拉纳帕提的聪明之处在于他没有对最大熵模型进行近似，而是找到了几个最适合用最大熵模型、而计算量相对不太大的自然语言处理问题，比如词性标注和句法分析。拉纳帕提成功地将上下文信息、词性（名词、动词和形容词等）、句子成分（主谓宾）通过最大熵模型结合起来，做出了当时世界上最好的词性标识系统和句法分析器。拉纳帕提的论文发表后让人们耳目一新。拉纳帕提的词性标注系统，至今仍然是使用单一方法最好的系统。科学家们从拉纳帕提的成就中，又看到了用最大熵模型解决复杂的文字信息处理的希望。-----------------------------------------------------Page 40-----------------------------------------------------但是，最大熵模型的计算量仍然是个拦路虎。我在学校时花了很长时间考虑如何简化最大熵模型的计算量。终于有一天，我对我的导师说，我发现一种数学变换，可以将大部分最大熵模型的训练时间在 IIS 的基础上减少两个数量级。我在黑板上推导了一个多小时，他没有找出我的推导中的任何破绽，接着他又回去想了两天，然后告诉我我的算法是对的。从此，我们就建造了一些很大的最大熵模型。这些模型比修修补补的凑合的方法好不少。即使在我找到了快速训练算法以后，为了训练一个包含上下文信息，主题信息和语法信息的文法模型(language model)，我并行使用了 20 台当时最快的 SUN 工作站，仍然计算了三个月。由此可见最大熵模型的复杂的一面。最大熵模型快速算法的实现很复杂，到今天为止，世界上能有效实现这些算法的人也不到一百人。有兴趣实现一个最大熵模型的读者可以阅读我的论文。最大熵模型，可以说是集简与繁于一体，形式简单，实现复杂。值得一提的是，在Google的很多产品中，比如机器翻译，都直接或间接地用到了最大熵模型。讲到这里，读者也许会问，当年最早改进最大熵模型算法的达拉皮垂兄弟这些年难道没有做任何事吗？他们在九十年代初贾里尼克离开 IBM 后，也退出了学术界，而到在金融界大显身手。他们两人和很多 IBM 语音识别的同事一同到了一家当时还不大，但现在是世界上最成功对冲基金(hedge fund)公司----文艺复兴技术公司 (Renaissance Technologies)。我们知道，决定股票涨落的因素可能有几十甚至上百种，而最大熵方法恰恰能找到一个同时满足成千上万种不同条件的模型。达拉皮垂兄弟等科学家在那里，用于最大熵模型和其他一些先进的数学工具对股票预测，获得了巨大的成功。从该基金 1988 年创立至今，它的净回报率高达平均每年 34%。也就是说，如果 1988 年你在该基金投入一块钱，今天你能得到 200 块钱。这个业绩，远远超过股神巴菲特的旗舰公司伯克夏哈撒韦（Berkshire Hathaway)。同期，伯克夏哈撒韦的总回报是 16 倍。值得一提的是，信息处理的很多数学手段，包括隐含马尔可夫模型、子波变换、贝叶斯网络等等，在华尔街多有直接的应用。由此可见，数学模型的作用。-----------------------------------------------------Page 41-----------------------------------------------------十七、闪光的不一定是金子谈谈搜索引擎作弊问题(Search EngineAnti-SPAM)2006 年 11 月 28 日上午 03:18:00Google 研究员吴军自从有了搜索引擎，就有了针对搜索引擎网页排名的作弊(SPAM)。以至于用户发现在搜索引擎中排名靠前的网页不一定就是高质量的，用句俗话说，闪光的不一定是金子。搜索引擎的作弊，虽然方法很多，目的只有一个，就是采用不正当手段提高自己网页的排名。早期最常见的作弊方法是重复关键词。比如一个卖数码相机的网站，重复地罗列各种数码相机的品牌，如尼康、佳能和柯达等等。为了不让读者看到众多讨厌的关键词，聪明一点的作弊者常用很小的字体和与背景相同的颜色来掩盖这些关键词。其实，这种做法很容易被搜索引擎发现并纠正。在有了网页排名(page rank)以后，作弊者发现一个网页被引用的连接越多，排名就可能越靠前，于是就有了专门卖链接和买链接的生意。比如，有人自己创建成百上千个网站，这些网站上没有实质的内容，只有到他们的客户网站的连接。这种做法比重复关键词要高明得多，但是还是不太难被发现。因为那些所谓帮别人提高排名的网站，为了维持生意需要大量地卖链接，所以很容易露马脚。（这就如同造假钞票，当某一种假钞票的流通量相当大以后，就容易找到根源了。）再以后，又有了形形色色的作弊方式，我们就不在这里一一赘述了。几年前，我加入 Google 做的第一件事就是消除网络作弊。在 Google 最早发现搜索引擎作弊的是 Matt Cutts，他在我加入 Google 前几个月开始研究这个问题，后来，辛格，马丁和我先后加入进来。我们经过几个月的努力，清除了一半的作弊者。(当然，以后抓作弊的效率就不会有这么高了。）其中一部分网站从此" 痛改前非"，但是还是有很多网站换一种作弊方法继续作弊，因此，抓作弊成了一种长期的猫捉老鼠的游戏。虽然至今还没有一个一劳永逸地解决作弊问题的方法，但是，Google 基本做到了对于任何已知的作弊方法，在一定时间内发现并清除它，从而总是将作弊的网站的数量控制在一个很小的比例范围。抓作弊的方法很像信号处理中的去噪音的办法。学过信息论和有信号处理经验的读者可能知道这么一个事实，我们如果在发动机很吵的汽车里用手机打电话，对方可能听不清；但是如果我们知道了汽车发动机的频率，我们可以加上一个和发动机噪音相反的信号，很容易地消除发动机的噪音，这样，收话人可以完全听不到汽车的噪音。事实上，现在一些高端的手机已经有了这种检测和消除噪音的功能。消除噪音的流程可以概括如下：-----------------------------------------------------Page 42-----------------------------------------------------在图中，原始的信号混入了噪音，在数学上相当于两个信号做卷积。噪音消除的过程是一个解卷积的过程。这在信号处理中并不是什么难题。因为第一，汽车发动机的频率是固定的，第二，这个频率的噪音重复出现，只要采集几秒钟的信号进行处理就能做到。从广义上讲，只要噪音不是完全随机的、并且前后有相关性，就可以检测到并且消除。事实上，完全随机不相关的高斯白噪音是很难消除的。）搜索引擎的作弊者所作的事，就如同在手机信号中加入了噪音，使得搜索结果的排名完全乱了。但是，这种人为加入的噪音并不难消除，因为作弊者的方法不可能是随机的（否则就无法提高排名了）。而且，作弊者也不可能是一天换一种方法，即作弊方法是时间相关的。因此，搞搜索引擎排名算法的人，可以在搜集一段时间的作弊信息后，将作弊者抓出来，还原原有的排名。当然这个过程需要时间，就如同采集汽车发动机噪音需要时间一样，在这段时间内，作弊者可能会尝到些甜头。因此，有些人看到自己的网站经过所谓的优化（其实是作弊），排名在短期内靠前了，以为这种所谓的优化是有效的。但是，不久就会发现排名掉下去了很多。这倒不是搜索引擎以前宽容，现在严厉了，而是说明抓作弊需要一定的时间，以前只是还没有检测到这些作弊的网站而已。还要强调一点，Google 抓作弊和恢复网站原有排名的过程完全是自动的(并没有个人的好恶），就如同手机消除噪音是自动的一样。一个网站要想长期排名靠前，就需要把内容做好，同时要和那些作弊网站划清界限。-----------------------------------------------------Page 43-----------------------------------------------------十八、矩阵运算和文本处理中的分类问题2007 年 1 月 1 日下午 03:10:00发表者：Google 研究员，吴军我在大学学习线性代数时，实在想不出它除了告诉我们如何解线性方程外，还能有什么别的用途。关于矩阵的许多概念，比如特征值等等，更是脱离日常生活。后来在数值分析中又学了很多矩阵的近似算法，还是看不到可以应用的地方。当时选这些课，完全是为了混学分的学位。我想，很多同学都多多少少有过类似的经历。直到后来长期做自然语言处理的研究，我才发现数学家们提出那些矩阵的概念和算法，是有实际应用的意义的。在自然语言处理中，最常见的两类的分类问题分别是，将文本按主题归类（比如将所有介绍亚运会的新闻归到体育类）和将词汇表中的字词按意思归类（比如将各种体育运动的名称个归成一类）。这两种分类问题都可用通过矩阵运算来圆满地、同时解决。为了说明如何用矩阵这个工具类解决这两个问题的，让我们先来来回顾一下我们在余弦定理和新闻分类中介绍的方法。分类的关键是计算相关性。我们首先对两个文本计算出它们的内容词，或者说实词的向量，然后求这两个向量的夹角。当这两个向量夹角为零时，新闻就相关；当它们垂直或者说正交时，新闻则无关。当然，夹角的余弦等同于向量的内积。从理论上讲，这种算法非常好。但是计算时间特别长。通常，我们要处理的文章的数量都很大，至少在百万篇以上，二次回标有非常长，比如说有五十万个词（包括人名地名产品名称等等）。如果想通过对一百万篇文章两篇两篇地成对比较，来找出所有共同主题的文章，就要比较五千亿对文章。现在的计算机一秒钟最多可以比较一千对文章，完成这一百万篇文章相关性比较就需要十五年时间。注意，要真正完成文章的分类还要反复重复上述计算。在文本分类中，另一种办法是利用矩阵运算中的奇异值分解（Singular Value Decomposition，简称 SVD)。现在让我们来看看奇异值分解是怎么回事。首先，我们可以用一个大矩阵A来描述这一百万篇文章和五十万词的关联性。这个矩阵中，每一行对应一篇文章，每一列对应一个词。-----------------------------------------------------Page 44-----------------------------------------------------在上面的图中，M=1,000,000，N=500,000。第 i 行，第 j 列的元素，是字典中第 j 个词在第 i 篇文章中出现的加权词频（比如， TF/IDF )。读者可能已经注意到了，这个矩阵非常大，有一百万乘以五十万，即五千亿个元素。奇异值分解就是把上面这样一个大矩阵，分解成三个小矩阵相乘，如下图所示。比如把上面的例子中的矩阵分解成一个一百万乘以一百的矩阵X，一个一百乘以一百的矩阵B，和一个一百乘以五十万的矩阵Y。这三个矩阵的元素总数加起来也不过 1.5 亿，仅仅是原来的三千分之一。相应的存储量和计算量都会小三个数量级以上。三个矩阵有非常清楚的物理含义。第一个矩阵X中的每一行表示意思相关的一类词，其中的每个非零元素表示这类词中每个词的重要性（或者说相关性），数值越大越相关。最后一个矩阵Y中的每一列表示同一主题一类文章，其中每个元素表示这类文章中每篇文章的相关性。中间的矩阵则表示类词和文章雷之间的相关性。因此，我们只要对关联矩阵A进行一次奇异值分解，w 我们就可以同时完成了近义词分类和文章的分类。（同时得到每类文章和每类词的相关性）。现在剩下的唯一问题，就是如何用计算机进行奇异值分解。这时，线性代数中-----------------------------------------------------Page 45-----------------------------------------------------的许多概念，比如矩阵的特征值等等，以及数值分析的各种算法就统统用上了。在很长时间内，奇异值分解都无法并行处理。虽然 Google 早就有了MapReduce 等并行计算的工具，但是由于奇异值分解很难拆成不相关子运算，即使在 Google 内部以前也无法利用并行计算的优势来分解矩阵。）最近，Google 中国的张智威博士和几个中国的工程师及实习生已经实现了奇异值分解的并行算法，我认为这是 Google 中国对世界的一个贡献。-----------------------------------------------------Page 46-----------------------------------------------------十九、马尔可夫链的扩展贝叶斯网络 (Bayesian Networks)我们在前面的系列中多次提到马尔可夫链 (MarkovChain) ，它描述了一种状态序列，其每个状态值取决于前面有限个状态。这种模型，对很多实际问题来讲是一种很粗略的简化。在现实生活中，很多事物相互的关系并不能用一条链来串起来。它们之间的关系可能是交叉的、错综复杂的。比如在下图中可以看到，心血管疾病和它的成因之间的关系是错综复杂的。显然无法用一个链来表示。我们可以把上述的有向图看成一个网络，它就是贝叶斯网络。其中每个圆圈表示一个状态。状态之间的连线表示它们的因果关系。比如从心血管疾病出发到吸烟的弧线表示心血管疾病可能和吸烟有关。当然，这些关系可以有一个量化的可信度 (belief) ，用一个概率描述。我们可以通过这样一张网络估计出一个人的心血管疾病的可能性。在网络中每个节点概率的计算，可以用贝叶斯公式来进行，贝叶斯网络因此而得名。由于网络的每个弧有一个可信度，贝叶斯网络也被称作信念网络 (belief networks) 。和马尔可夫链类似，贝叶斯网络中的每个状态值取决于前面有限个状态。不同的是，贝叶斯网络比马尔可夫链灵活，它不受马尔可夫链的链状结构的约束，因此可以更准确地描述事件之间的相关性。可以讲，马尔可夫链是贝叶斯网络的特例，而贝叶斯网络是马尔可夫链的推广。使用贝叶斯网络必须知道各个状态之间相关的概率。得到这些参数的过程叫做训练。和训练马尔可夫模型一样，训练贝叶斯网络要用一些已知的数据。比如在训练上面的网络，需要知道一些心血管疾病和吸烟、家族病史等有关的情况。相比马尔可夫链，贝叶斯网络的训练比较复杂，从理论上讲，它是一个 NP-complete 问题，也就是说，对于现在的计算机是不可计算的。但是，对于某些应用，这个训练过程可以简化，并在计算上实现。值得一提的是 IBM Watson 研究所的茨威格博士 (Geoffrey Zweig) 和西雅图华盛顿大学的比尔默 (Jeff Bilmes) 教授完成了一个通用的贝叶斯网络的工具包，提供给对贝叶斯网络有兴趣的研究者。-----------------------------------------------------Page 47-----------------------------------------------------贝叶斯网络在图像处理、文字处理、支持决策等方面有很多应用。在文字处理方面，语义相近的词之间的关系可以用一个贝叶斯网络来描述。我们利用贝叶斯网络，可以找出近义词和相关的词，在 Google 搜索和 Google 广告中都有直接的应用。-----------------------------------------------------Page 48-----------------------------------------------------