首页 数学之美.pdf

数学之美.pdf

数学之美.pdf

上传者: 米修米修 2011-01-07 评分4 评论1 下载2w+次 收藏113 阅读量3w+ 暂无简介 简介 举报

简介:本文档为《数学之美pdf》,可适用于学术研究领域,主题内容包含数学之美-、统计语言模型二、谈谈中文分词三、隐含马尔可夫模型在语言处理中的应用四、数学之美系列四怎样度量信息五、简单之美:布尔代数和搜索引擎的索引六符等。

数学之美-、统计语言模型二、谈谈中文分词三、隐含马尔可夫模型在语言处理中的应用四、数学之美系列四怎样度量信息五、简单之美:布尔代数和搜索引擎的索引六、图论和网络爬虫(WebCrawlers)七、信息论在信息处理中的应用八、贾里尼克的故事和现代语言处理九、如何确定网页和查询的相关性十、有限状态机和地址识别十一、Google阿卡的制造者阿米特辛格博士十二、余弦定理和新闻的分类十三、信息指纹及其应用十四、谈谈数学模型的重要性十五、繁与简自然语言处理的几位精英十六、不要把所有的鸡蛋放在一个篮子里谈谈最大熵模型(上)十六、不要把所有的鸡蛋放在一个篮子里最大熵模型(下)十七、闪光的不一定是金子谈谈搜索引擎作弊问题(SearchEngineAntiSPAM)十八、矩阵运算和文本处理中的分类问题十九、马尔可夫链的扩展贝叶斯网络(BayesianNetworks)二十、自然语言处理的教父马库斯二十一、布隆过滤器(BloomFilter)二十二、谈谈密码学的数学原理二十三、输入一个汉字需要敲多少个键谈谈香农第一定律摘自互联网:http:harryxucnbloggooglemath整理人:心灯(bjbshotmailcom)-、统计语言模型年月日上午::从本周开始我们将定期刊登Google科学家吴军写的《数学之美》系列文章介绍数学在信息检索和自然语言处理中的主导作用和奇妙应用。发表者:吴军,Google研究员前言也许大家不相信数学是解决信息检索和自然语言处理的最好工具。它能非常清晰地描述这些领域的实际问题并且给出漂亮的解决办法。每当人们应用数学工具解决一个语言问题时总会感叹数学之美。我们希望利用Google中文黑板报这块园地介绍一些数学工具以及我们是如何利用这些工具来开发Google产品的。系列一:统计语言模型(StatisticalLanguageModels)Google的使命是整合全球的信息所以我们一直致力于研究如何让机器对信息、语言做最好的理解和处理。长期以来人类一直梦想着能让机器代替人来翻译语言、识别语音、认识文字(不论是印刷体或手写体)和进行海量文献的自动检索这就需要让机器理解语言。但是人类的语言可以说是信息里最复杂最动态的一部分。为了解决这个问题人们容易想到的办法就是让机器模拟人类进行学习学习人类的语法、分析语句等等。尤其是在乔姆斯基(NoamChomsky有史以来最伟大的语言学家)提出“形式语言”以后人们更坚定了利用语法规则的办法进行文字处理的信念。遗憾的是几十年过去了在计算机处理语言领域基于这个语法规则的方法几乎毫无突破。其实早在几十年前数学家兼信息论的祖师爷香农(ClaudeShannon)就提出了用数学的办法处理自然语言的想法。遗憾的是当时的计算机条件根本无法满足大量信息处理的需要所以他这个想法当时并没有被人们重视。七十年代初有了大规模集成电路的快速计算机后香农的梦想才得以实现。首先成功利用数学方法解决自然语言处理问题的是语音和语言处理大师贾里尼克(FredJelinek)。当时贾里尼克在IBM公司做学术休假(SabbaticalLeave)领导了一批杰出的科学家利用大型计算机来处理人类语言问题。统计语言模型就是在那个时候提出的。给大家举个例子:在很多涉及到自然语言处理的领域如机器翻译、语音识别、印刷体或手写体识别、拼写纠错、汉字输入和文献查询中我们都需要知道一个文字序列是否能构成一个大家能理解的句子显示给使用者。对这个问题我们可以用一个简单的统计模型来解决这个问题。如果S表示一连串特定顺序排列的词ww…wn换句话说S可以表示某一个由一连串特定顺序排练的词而组成的一个有意义的句子。现在机器对语言的识别从某种角度来说就是想知道S在文本中出现的可能性也就是数学上所说的S的概率用P(S)来表示。利用条件概率的公式S这个序列出现的概率等于每一个词出现的概率相乘于是P(S)可展开为:P(S)=P(w)P(w|w)P(w|ww)…P(wn|ww…wn)其中P(w)表示第一个词w出现的概率P(w|w)是在已知第一个词的前提下第二个词出现的概率以次类推。不难看出到了词wn它的出现概率取决于它前面所有词。从计算上来看各种可能性太多无法实现。因此我们假定任意一个词wi的出现概率只同它前面的词wi有关(即马尔可夫假设)于是问题就变得很简单了。现在S出现的概率就变为:P(S)=P(w)P(w|w)P(w|w)…P(wi|wi)…(当然也可以假设一个词又前面N个词决定模型稍微复杂些。)接下来的问题就是如何估计P(wi|wi)。现在有了大量机读文本后这个问题变得很简单只要数一数这对词(wi,wi)在统计的文本中出现了多少次以及wi本身在同样的文本中前后相邻出现了多少次然后用两个数一除就可以了,P(wi|wi)=P(wi,wi)P(wi)。也许很多人不相信用这么简单的数学模型能解决复杂的语音识别、机器翻译等问题。其实不光是常人就连很多语言学家都曾质疑过这种方法的有效性但事实证明统计语言模型比任何已知的借助某种规则的解决方法都有效。比如在Google的中英文自动翻译中用的最重要的就是这个统计语言模型。去年美国标准局(NIST)对所有的机器翻译系统进行了评测Google的系统是不仅是全世界最好的而且高出所有基于规则的系统很多。现在读者也许已经能感受到数学的美妙之处了它把一些复杂的问题变得如此的简单。当然真正实现一个好的统计语言模型还有许多细节问题需要解决。贾里尼克和他的同事的贡献在于提出了统计语言模型而且很漂亮地解决了所有的细节问题。十几年后李开复用统计语言模型把词语音识别的问题简化成了一个词的识别问题实现了有史以来第一次大词汇量非特定人连续语音的识别。我是一名科学研究人员我在工作中经常惊叹于数学语言应用于解决实际问题上时的神奇。我也希望把这种神奇讲解给大家听。当然归根结底不管什莫样的科学方法、无论多莫奇妙的解决手段都是为人服务的。我希望Google多努力一分用户就多一分搜索的喜悦二、谈谈中文分词年月日上午::发表者:吴军Google研究员谈谈中文分词统计语言模型在中文处理中的一个应用上回我们谈到利用统计语言模型进行语言处理由于模型是建立在词的基础上的对于中日韩等语言首先需要进行分词。例如把句子“中国航天官员应邀到美国与太空总署官员开会。”分成一串词:中国航天官员应邀到美国与太空总署官员开会。最容易想到的也是最简单的分词办法就是查字典。这种方法最早是由北京航天航空大学的梁南元教授提出的。用“查字典”法其实就是我们把一个句子从左向右扫描一遍遇到字典里有的词就标识出来遇到复合词(比如“上海大学”)就找最长的词匹配遇到不认识的字串就分割成单字词于是简单的分词就完成了。这种简单的分词方法完全能处理上面例子中的句子。八十年代哈工大的王晓龙博士把它理论化发展成最少词数的分词理论即一句话应该分成数量最少的词串。这种方法一个明显的不足是当遇到有二义性(有双重理解意思)的分割时就无能为力了。比如对短语“发展中国家”正确的分割是“发展中国家”而从左向右查字典的办法会将它分割成“发展中国家”显然是错了。另外并非所有的最长匹配都一定是正确的。比如“上海大学城书店”的正确分词应该是“上海大学城书店”而不是“上海大学城书店”。九十年代以前海内外不少学者试图用一些文法规则来解决分词的二义性问题都不是很成功。年前后清华大学的郭进博士用统计语言模型成功解决分词二义性问题将汉语分词的错误率降低了一个数量级。利用统计语言模型分词的方法可以用几个数学公式简单概括如下:我们假定一个句子S可以有几种分词方法为了简单起见我们假定有以下三种:A,A,A,,Ak,B,B,B,,BmC,C,C,,Cn其中A,A,B,B,C,C等等都是汉语的词。那么最好的一种分词方法应该保证分完词后这个句子出现的概率最大。也就是说如果A,A,,Ak是最好的分法那么(P表示概率):P(A,A,A,,Ak)〉P(B,B,B,,Bm),并且P(A,A,A,,Ak)〉P(C,C,C,,Cn)因此只要我们利用上回提到的统计语言模型计算出每种分词后句子出现的概率并找出其中概率最大的我们就能够找到最好的分词方法。当然这里面有一个实现的技巧。如果我们穷举所有可能的分词方法并计算出每种可能性下句子的概率那么计算量是相当大的。因此我们可以把它看成是一个动态规划(DynamicProgramming)的问题并利用“维特比”(Viterbi)算法快速地找到最佳分词。在清华大学的郭进博士以后海内外不少学者利用统计的方法进一步完善中文分词。其中值得一提的是清华大学孙茂松教授和香港科技大学吴德凯教授的工作。需要指出的是语言学家对词语的定义不完全相同。比如说“北京大学”有人认为是一个词而有人认为该分成两个词。一个折中的解决办法是在分词的同时找到复合词的嵌套结构。在上面的例子中如果一句话包含“北京大学”四个字那么先把它当成一个四字词然后再进一步找出细分词“北京”和“大学”。这种方法是最早是郭进在“ComputationalLinguistics”(《计算机语言学》)杂志上发表的以后不少系统采用这种方法。一般来讲根据不同应用汉语分词的颗粒度大小应该不同。比如在机器翻译中颗粒度应该大一些“北京大学”就不能被分成两个词。而在语音识别中“北京大学”一般是被分成两个词。因此不同的应用应该有不同的分词系统。Google的葛显平博士和朱安博士专门为搜索设计和实现了自己的分词系统。也许你想不到中文分词的方法也被应用到英语处理主要是手写体识别中。因为在识别手写体时单词之间的空格就不很清楚了。中文分词方法可以帮助判别英语单词的边界。其实语言处理的许多数学方法通用的和具体的语言无关。在Google内我们在设计语言处理的算法时都会考虑它是否能很容易地适用于各种自然语言。这样我们才能有效地支持上百种语言的搜索。对中文分词有兴趣的读者可以阅读以下文献:梁南元书面汉语自动分词系统http:wwwtouchwritecomdemoLiangNanyuanJCIPpdf郭进统计语言模型和汉语音字转换的一些新结果http:wwwtouchwritecomdemoGuoJinJCIPpdf郭进CriticalTokenizationanditsPropertieshttp:aclldcupenneduJJJpdf孙茂松Chinesewordsegmentationwithoutusinglexiconandhandcraftedtrainingdatahttp:portalacmorgcitationcfmcoll=GUIDEdl=GUIDEid=三、隐含马尔可夫模型在语言处理中的应用年月日上午::发表者:吴军Google研究员前言:隐含马尔可夫模型是一个数学模型到目前为之它一直被认为是实现快速精确的语音识别系统的最成功的方法。复杂的语音识别问题通过隐含马尔可夫模型能非常简单地被表述、解决让我不由由衷地感叹数学模型之妙。自然语言是人类交流信息的工具。很多自然语言处理问题都可以等同于通信系统中的解码问题一个人根据接收到的信息去猜测发话人要表达的意思。这其实就象通信中我们根据接收端收到的信号去分析、理解、还原发送端传送过来的信息。以下该图就表示了一个典型的通信系统:其中sss表示信息源发出的信号。o,o,o是接受器接收到的信号。通信中的解码就是根据接收到的信号o,o,o还原出发送的信号sss。其实我们平时在说话时脑子就是一个信息源。我们的喉咙(声带)空气就是如电线和光缆般的信道。听众耳朵的就是接收端而听到的声音就是传送过来的信号。根据声学信号来推测说话者的意思就是语音识别。这样说来如果接收端是一台计算机而不是人的话那么计算机要做的就是语音的自动识别。同样在计算机中如果我们要根据接收到的英语信息推测说话者的汉语意思就是机器翻译如果我们要根据带有拼写错误的语句推测说话者想表达的正确意思那就是自动纠错。那么怎么根据接收到的信息来推测说话者想表达的意思呢?我们可以利用叫做“隐含马尔可夫模型”(HiddenMarkovModel)来解决这些问题。以语音识别为例当我们观测到语音信号o,o,o时我们要根据这组信号推测出发送的句子s,s,s。显然我们应该在所有可能的句子中找最有可能性的一个。用数学语言来描述就是在已知o,o,o,的情况下求使得条件概率P(s,s,s,|o,o,o)达到最大值的那个句子s,s,s,当然上面的概率不容易直接求出于是我们可以间接地计算它。利用贝叶斯公式并且省掉一个常数项可以把上述公式等价变换成P(o,o,o,|s,s,s)*P(s,s,s,)其中P(o,o,o,|s,s,s)表示某句话s,s,s被读成o,o,o,的可能性,而P(s,s,s,)表示字串s,s,s,本身能够成为一个合乎情理的句子的可能性所以这个公式的意义是用发送信号为s,s,s这个数列的可能性乘以s,s,s本身可以一个句子的可能性得出概率。(读者读到这里也许会问你现在是不是把问题变得更复杂了因为公式越写越长了。别着急我们现在就来简化这个问题。)我们在这里做两个假设:第一s,s,s,是一个马尔可夫链也就是说si只由si决定(详见系列一)第二第i时刻的接收信号oi只由发送信号si决定(又称为独立输出假设,即P(o,o,o,|s,s,s)=P(o|s)*P(o|s)*P(o|s)。那么我们就可以很容易利用算法Viterbi找出上面式子的最大值进而找出要识别的句子s,s,s,。满足上述两个假设的模型就叫隐含马尔可夫模型。我们之所以用“隐含”这个词是因为状态s,s,s,是无法直接观测到的。隐含马尔可夫模型的应用远不只在语音识别中。在上面的公式中如果我们把s,s,s,当成中文把o,o,o,当成对应的英文那么我们就能利用这个模型解决机器翻译问题如果我们把o,o,o,当成扫描文字得到的图像特征就能利用这个模型解决印刷体和手写体的识别。P(o,o,o,|s,s,s)根据应用的不同而又不同的名称在语音识别中它被称为“声学模型”(AcousticModel)在机器翻译中是“翻译模型”(TranslationModel)而在拼写校正中是“纠错模型”(CorrectionModel)。而P(s,s,s,)就是我们在系列一中提到的语言模型。在利用隐含马尔可夫模型解决语言处理问题前先要进行模型的训练。常用的训练方法由伯姆(Baum)在年代提出的并以他的名字命名。隐含马尔可夫模型在处理语言问题早期的成功应用是语音识别。七十年代当时IBM的FredJelinek(贾里尼克)和卡内基梅隆大学的JimandJanetBaker(贝克夫妇李开复的师兄师姐)分别独立地提出用隐含马尔可夫模型来识别语音语音识别的错误率相比人工智能和模式匹配等方法降低了三倍(从到)。八十年代李开复博士坚持采用隐含马尔可夫模型的框架成功地开发了世界上第一个大词汇量连续语音识别系统Sphinx。我最早接触到隐含马尔可夫模型是几乎二十年前的事。那时在《随机过程》(清华“著名”的一门课)里学到这个模型但当时实在想不出它有什么实际用途。几年后我在清华跟随王作英教授学习、研究语音识别时他给了我几十篇文献。我印象最深的就是贾里尼克和李开复的文章它们的核心思想就是隐含马尔可夫模型。复杂的语音识别问题居然能如此简单地被表述、解决我由衷地感叹数学模型之妙。四、数学之美系列四怎样度量信息年月日上午::发表者:吴军Google研究员前言:Google一直以“整合全球信息让人人能获取使人人能受益”为使命。那么究竟每一条信息应该怎样度量呢?信息是个很抽象的概念。我们常常说信息很多或者信息较少但却很难说清楚信息到底有多少。比如一本五十万字的中文书到底有多少信息量。直到年香农提出了“信息熵”(shāng)的概念才解决了对信息的量化度量问题。一条信息的信息量大小和它的不确定性有直接的关系。比如说我们要搞清楚一件非常非常不确定的事或是我们一无所知的事情就需要了解大量的信息。相反如果我们对某件事已经有了较多的了解我们不需要太多的信息就能把它搞清楚。所以从这个角度我们可以认为信息量的度量就等于不确定性的多少。那么我们如何量化的度量信息量呢?我们来看一个例子马上要举行世界杯赛了。大家都很关心谁会是冠军。假如我错过了看世界杯赛后我问一个知道比赛结果的观众“哪支球队是冠军”?他不愿意直接告诉我而要让我猜并且我每猜一次他要收一元钱才肯告诉我是否猜对了那么我需要付给他多少钱才能知道谁是冠军呢我可以把球队编上号从到然后提问:“冠军的球队在号中吗”假如他告诉我猜对了我会接着问:“冠军在号中吗”假如他告诉我猜错了我自然知道冠军队在中。这样只需要五次我就能知道哪支球队是冠军。所以谁是世界杯冠军这条消息的信息量只值五块钱。当然香农不是用钱而是用“比特”(bit)这个概念来度量信息量。一个比特是一位二进制数计算机中的一个字节是八个比特。在上面的例子中这条消息的信息量是五比特。(如果有朝一日有六十四个队进入决赛阶段的比赛那么“谁世界杯冠军”的信息量就是六比特因为我们要多猜一次。)读者可能已经发现,信息量的比特数和所有可能情况的对数函数log有关。(log=,log=。)有些读者此时可能会发现我们实际上可能不需要猜五次就能猜出谁是冠军因为象巴西、德国、意大利这样的球队得冠军的可能性比日本、美国、韩国等队大的多。因此我们第一次猜测时不需要把个球队等分成两个组而可以把少数几个最可能的球队分成一组把其它队分成另一组。然后我们猜冠军球队是否在那几只热门队中。我们重复这样的过程根据夺冠概率对剩下的候选球队分组直到找到冠军队。这样我们也许三次或四次就猜出结果。因此当每个球队夺冠的可能性(概率)不等时“谁世界杯冠军”的信息量的信息量比五比特少。香农指出它的准确信息量应该是=(p*logpp*logp...+p*logp)其中pp...p分别是这个球队夺冠的概率。香农把它称为“信息熵”(Entropy)一般用符号H表示单位是比特。有兴趣的读者可以推算一下当个球队夺冠概率相同时对应的信息熵等于五比特。有数学基础的读者还可以证明上面公式的值不可能大于五。对于任意一个随机变量X(比如得冠军的球队)它的熵定义如下:变量的不确定性越大熵也就越大把它搞清楚所需要的信息量也就越大。有了“熵”这个概念我们就可以回答本文开始提出的问题即一本五十万字的中文书平均有多少信息量。我们知道常用的汉字(一级二级国标)大约有字。假如每个字等概率那么我们大约需要个比特(即位二进制数)表示一个汉字。但汉字的使用是不平衡的。实际上前的汉字占文本的以上。因此即使不考虑上下文的相关性而只考虑每个汉字的独立的概率那么每个汉字的信息熵大约也只有个比特。如果我们再考虑上下文相关性每个汉字的信息熵只有比特左右。所以一本五十万字的中文书信息量大约是万比特。如果用一个好的算法压缩一下整本书可以存成一个KB的文件。如果我们直接用两字节的国标编码存储这本书大约需要MB大小是压缩文件的三倍。这两个数量的差距在信息论中称作“冗余度”(redundancy)。需要指出的是我们这里讲的万比特是个平均数同样长度的书所含的信息量可以差很多。如果一本书重复的内容很多它的信息量就小冗余度就大。不同语言的冗余度差别很大而汉语在所有语言中冗余度是相对小的。这和人们普遍的认识“汉语是最简洁的语言”是一致的。在下一集中我们将介绍信息熵在信息处理中的应用以及两个相关的概念互信息和相对熵。对中文信息熵有兴趣的读者可以读我和王作英教授在电子学报上合写的一篇文章《语信息熵和语言模型的复杂度》五、简单之美:布尔代数和搜索引擎的索引年月日上午::发表者:吴军Google研究员建立一个搜索引擎大致需要做这样几件事:自动下载尽可能多的网页建立快速有效的索引根据相关性对网页进行公平准确的排序。我们在介绍GooglePageRank(网页排名)时已经谈到了一些排序的问题这里我们谈谈索引问题以后我们还会谈如何度量网页的相关性和进行网页自动下载。]世界上不可能有比二进制更简单的计数方法了也不可能有比布尔运算更简单的运算了。尽管今天每个搜索引擎都宣称自己如何聪明、多么智能化其实从根本上讲都没有逃出布尔运算的框框。布尔(GeorgeBoole)是十九世纪英国一位小学数学老师。他生前没有人认为他是数学家。布尔在工作之余喜欢阅读数学论著、思考数学问题。年“思维规律”(AnInvestigationoftheLawsofThought,onwhicharefoundedtheMathematicalTheoriesofLogicandProbabilities)一书第一次向人们展示了如何用数学的方法解决逻辑问题。布尔代数简单得不能再简单了。运算的元素只有两个(TRUE真)和(FALSE假)。基本的运算只有“与”(AND)、“或”(OR)和“非”(NOT)三种(后来发现这三种运算都可以转换成“与”“非”AND-NOT一种运算)。全部运算只用下列几张真值表就能完全地描述清楚。AND|||这张表说明如果AND运算的两个元素有一个是则运算结果总是。如果两个元素都是运算结果是。例如“太阳从西边升起”这个判断是假的(),“水可以流动”这个判断是真的()那么“太阳从西边升起并且水可以流动”就是假的()。OR|||这张表说明如果OR运算的两个元素有一个是则运算结果总是。如果两个元素都是运算结果是。比如说“张三是比赛第一名”这个结论是假的()“李四是比赛第一名”是真的()那么“张三或者李四是第一名”就是真的()。NOT|||这张表说明NOT运算把变成把变成。比如如果“象牙是白的”是真的()那么“象牙不是白的”必定是假的()。读者也许会问这么简单的理论能解决什么实际问题。布尔同时代的数学家们也有同样的问题。事实上在布尔代数提出后多年里它确实没有什么像样的应用直到年香农在他的硕士论文中指出用布尔代数来实现开关电路才使得布尔代数成为数字电路的基础。所有的数学和逻辑运算加、减、乘、除、乘方、开方等等全部能转换成二值的布尔运算。现在我们看看文献检索和布尔运算的关系。对于一个用户输入的关键词搜索引擎要判断每篇文献是否含有这个关键词如果一篇文献含有它我们相应地给这篇文献一个逻辑值真(TRUE,或)否则给一个逻辑值假(FALSE,或)。比如我们要找有关原子能应用的文献但并不想知道如何造原子弹。我们可以这样写一个查询语句“原子能AND应用AND(NOT原子弹)”表示符合要求的文献必须同时满足三个条件:包含原子能包含应用不包含原子弹一篇文献对于上面每一个条件都有一个True或者False的答案根据上述真值表就能算出每篇文献是否是要找的。早期的文献检索查询系统大多基于数据库严格要求查询语句符合布尔运算。今天的搜索引擎相比之下要聪明的多它自动把用户的查询语句转换成布尔运算的算式。当然在查询时不能将每篇文献扫描一遍来看看它是否满足上面三个条件因此需要建立一个索引。最简单索引的结构是用一个很长的二进制数表示一个关键字是否出现在每篇文献中。有多少篇文献就有多少位数每一位对应一篇文献代表相应的文献有这个关键字代表没有。比如关键字“原子能”对应的二进制数是表示第二、第五、第九、第十、第十六篇文献包含着个关键字。注意这个二进制数非常之长。同样我们假定“应用”对应的二进制数是。那么要找到同时包含“原子能”和“应用”的文献时只要将这两个二进制数进行布尔运算AND。根据上面的真值表我们知道运算结果是。表示第五篇第十六篇文献满足要求。注意计算机作布尔运算是非常非常快的。现在最便宜的微机都可以一次进行三十二位布尔运算一秒钟进行十亿次以上。当然由于这些二进制数中绝大部分位数都是零我们只需要记录那些等于的位数即可。于是搜索引擎的索引就变成了一张大表:表的每一行对应一个关键词而每一个关键词后面跟着一组数字是包含该关键词的文献序号。对于互联网的搜索引擎来讲每一个网页就是一个文献。互联网的网页数量是巨大的网络中所用的词也非常非常多。因此这个索引是巨大的在万亿字节这个量级。早期的搜索引擎(比如AltaVista以前的所有搜索引擎)由于受计算机速度和容量的限制只能对重要的关键的主题词建立索引。至今很多学术杂志还要求作者提供个关键词。这样所有不常见的词和太常见的虚词就找不到了。现在为了保证对任何搜索都能提供相关的网页所有的搜索引擎都是对所有的词进行索引。为了网页排名方便索引中还需存有大量附加信息诸如每个词出现的位置、次数等等。因此整个索引就变得非常之大以至于不可能用一台计算机存下。大家普遍的做法就是根据网页的序号将索引分成很多份(Shards)分别存储在不同的服务器中。每当接受一个查询时这个查询就被分送到许许多多服务器中这些服务器同时并行处理用户请求并把结果送到主服务器进行合并处理最后将结果返回给用户。不管索引如何复杂查找的基本操作仍然是布尔运算。布尔运算把逻辑和数学联系起来了。它的最大好处是容易实现速度快这对于海量的信息查找是至关重要的。它的不足是只能给出是与否的判断而不能给出量化的度量。因此所有搜索引擎在内部检索完毕后都要对符合要求的网页根据相关性排序然后才返回给用户。六、图论和网络爬虫(WebCrawlers)年月日上午::发表者:吴军Google研究员离散数学是当代数学的一个重要分支也是计算机科学的数学基础。它包括数理逻辑、集合论、图论和近世代数四个分支。数理逻辑基于布尔运算我们已经介绍过了。这里我们介绍图论和互联网自动下载工具网络爬虫(WebCrawlers)之间的关系。顺便提一句我们用GoogleTrends来搜索一下“离散数学”这个词可以发现不少有趣的现象。比如武汉、哈尔滨、合肥和长沙市对这一数学题目最有兴趣的城市。我们上回谈到了如何建立搜索引擎的索引那么如何自动下载互联网所有的网页呢它要用到图论中的遍历(Traverse)算法。图论的起源可追溯到大数学家欧拉(LeonhardEuler)。年欧拉来到德国的哥尼斯堡(Konigsberg大哲学家康德的故乡现在是俄罗斯的加里宁格勒)发现当地市民们有一项消遣活动就是试图将下图中的每座桥恰好走过一遍并回到原出发点从来没有人成功过。欧拉证明了这件事是不可能的并写了一篇论文一般认为这是图论的开始。图论中所讨论的的图由一些节点和连接这些节点的弧组成。如果我们把中国的城市当成节点连接城市的国道当成弧那么全国的公路干线网就是图论中所说的图。关于图的算法有很多但最重要的是图的遍历算法也就是如何通过弧访问图的各个节点。以中国公路网为例我们从北京出发看一看北京和哪些城市直接相连比如说和天津、济南、石家庄、南京、沈阳、大同直接相连。我们可以依次访问这些城市然后我们看看都有哪些城市和这些已经访问过的城市相连比如说北戴河、秦皇岛与天津相连青岛、烟台和济南相连太原、郑州和石家庄相连等等我们再一次访问北戴河这些城市直到中国所有的城市都访问过一遍为止。这种图的遍历算法称为“广度优先算法”(BFS)因为它先要尽可能广地访问每个节点所直接连接的其他节点。另外还有一种策略是从北京出发随便找到下一个要访问的城市比如是济南然后从济南出发到下一个城市比如说南京再访问从南京出发的城市一直走到头。然后再往回找看看中间是否有尚未访问的城市。这种方法叫“深度优先算法”(DFS)因为它是一条路走到黑。这两种方法都可以保证访问到全部的城市。当然不论采用哪种方法我们都应该用一个小本本记录已经访问过的城市以防同一个城市访问多次或者漏掉哪个城市。现在我们看看图论的遍历算法和搜索引擎的关系。互联网其实就是一张大图我们可以把每一个网页当作一个节点把那些超链接(Hyperlinks)当作连接网页的弧。很多读者可能已经注意到网页中那些蓝色的、带有下划线的文字背后其实藏着对应的网址当你点下去的的时候浏览器是通过这些隐含的网址转到相应的网页中的。这些隐含在文字背后的网址称为“超链接”。有了超链接我们可以从任何一个网页出发用图的遍历算法自动地访问到每一个网页并把它们存起来。完成这个功能的程序叫做网络爬虫或者在一些文献中称为"机器人"(Robot)。世界上第一个网络爬虫是由麻省理工学院(MIT)的学生马休格雷(MatthewGray)在年写成的。他给他的程序起了个名字叫“互联网漫游者”("wwwwanderer")。以后的网络爬虫越写越复杂但原理是一样的。我们来看看网络爬虫如何下载整个互联网。假定我们从一家门户网站的首页出发先下载这个网页然后通过分析这个网页可以找到藏在它里面的所有超链接也就等于知道了这家门户网站首页所直接连接的全部网页诸如雅虎邮件、雅虎财经、雅虎新闻等等。我们接下来访问、下载并分析这家门户网站的邮件等网页又能找到其他相连的网页。我们让计算机不停地做下去就能下载整个的互联网。当然我们也要记载哪个网页下载过了以免重复。在网络爬虫中我们使用一个称为“哈希表”(HashTable)的列表而不是一个记事本纪录网页是否下载过的信息。现在的互联网非常巨大不可能通过一台或几台计算机服务器就能完成下载任务。比如雅虎公司(Google没有公开公布我们的数目所以我这里举了雅虎的索引大小为例)宣称他们索引了亿个网页假如下载一个网页需要一秒钟下载这亿个网页则需要年。因此一个商业的网络爬虫需要有成千上万个服务器并且由快速网络连接起来。如何建立这样复杂的网络系统如何协调这些服务器的任务就是网络设计和程序设计的艺术了。七、信息论在信息处理中的应用我们已经介绍了信息熵它是信息论的基础我们这次谈谈信息论在自然语言处理中的应用。先看看信息熵和语言模型的关系。我们在系列一中谈到语言模型时没有讲如何定量地衡量一个语言模型的好坏当然读者会很自然地想到既然语言模型能减少语音识别和机器翻译的错误那么就拿一个语音识别系统或者机器翻译软件来试试好的语言模型必然导致错误率较低。这种想法是对的而且今天的语音识别和机器翻译也是这么做的。但这种测试方法对于研发语言模型的人来讲既不直接、又不方便而且很难从错误率反过来定量度量语言模型。事实上在贾里尼克(FredJelinek)的人研究语言模型时世界上既没有像样的语音识别系统更没有机器翻译。我们知道语言模型是为了用上下文预测当前的文字模型越好预测得越准那么当前文字的不确定性就越小。信息熵正是对不确定性的衡量因此信息熵可以直接用于衡量统计语言模型的好坏。贾里尼克从信息熵出发定义了一个称为语言模型复杂度(Perplexity)的概念直接衡量语言模型的好坏。一个模型的复杂度越小模型越好。李开复博士在介绍他发明的Sphinx语音识别系统时谈到如果不用任何语言模型(即零元语言模型)时复杂度为也就是说句子中每个位置有个可能的单词可以填入。如果(二元)语言模型只考虑前后词的搭配不考虑搭配的概率时复杂度为。虽然它比不用语言模型好很多但是和考虑了搭配概率的二元语言模型相比要差很多因为后者的复杂度只有。信息论中仅次于熵的另外两个重要的概念是“互信息”(MutualInformation)和“相对熵”(KullbackLeiblerDivergence)。“互信息”是信息熵的引申概念它是对两个随机事件相关性的度量。比如说今天随机事件北京下雨和随机变量空气湿度的相关性就很大但是和姚明所在的休斯敦火箭队是否能赢公牛队几乎无关。互信息就是用来量化度量这种相关性的。在自然语言处理中经常要度量一些语言现象的相关性。比如在机器翻译中最难的问题是词义的二义性(歧义性)问题。比如Bush一词可以是美国总统的名字也可以是灌木丛。(有一个笑话美国上届总统候选人凯里Kerry的名字被一些机器翻译系统翻译成了"爱尔兰的小母牛"Kerry在英语中另外一个意思。)那么如何正确地翻译这个词呢?人们很容易想到要用语法、要分析语句等等。其实至今为止没有一种语法能很好解决这个问题真正实用的方法是使用互信息。具体的解决办法大致如下:首先从大量文本中找出和总统布什一起出现的互信息最大的一些词比如总统、美国、国会、华盛顿等等当然再用同样的方法找出和灌木丛一起出现的互信息最大的词比如土壤、植物、野生等等。有了这两组词在翻译Bush时看看上下文中哪类相关的词多就可以了。这种方法最初是由吉尔(Gale)丘奇(Church)和雅让斯基(Yarowsky)提出的。当时雅让斯基在宾西法尼亚大学是自然语言处理大师马库斯(MitchMarcus)教授的博士生他很多时间泡在贝尔实验室丘奇等人的研究室里。也许是急于毕业他在吉尔等人的帮助下想出了一个最快也是最好地解决翻译中的二义性就是上述的方法这个看上去简单的方法效果好得让同行们大吃一惊。雅让斯基因而只花了三年就从马库斯那里拿到了博士而他的师兄弟们平均要花六年时间。信息论中另外一个重要的概念是“相对熵”在有些文献中它被称为成“交叉熵”。在英语中是KullbackLeiblerDivergence是以它的两个提出者库尔贝克和莱伯勒的名字命名的。相对熵用来衡量两个正函数是否相似对于两个完全相同的函数它们的相对熵等于零。在自然语言处理中可以用相对熵来衡量两个常用词(在语法上和语义上)是否同义或者两篇文章的内容是否相近等等。利用相对熵我们可以到处信息检索中最重要的一个概念:词频率逆向文档频率(TFIDF)。我们下回会介绍如何根据相关性对搜索出的网页进行排序就要用的餐TFIDF的概念。另外在新闻的分类中也要用到相对熵和TFIDF。对信息论有兴趣又有一定数学基础的读者可以阅读斯坦福大学托马斯科弗(ThomasCover)教授的专著"信息论基础"(ElementsofInformationTheory):http:wwwamazoncomgpproductref=nosimn=http:wwwcnforyoucomquerybookdetailaspviBookCode=科弗教授是当今最权威的信息论专家。八、贾里尼克的故事和现代语言处理年月日上午::发表者:Google研究员吴军读者也许注意到了我们在前面的系列中多次提到了贾里尼克这个名字。事实上现代语音识别和自然语言处理确实是和它的名字是紧密联系在一起的。我想在这回的系列里介绍贾里尼克本人。在这里我不想列举他的贡献而想讲一讲他作为一个普普通通的人的故事。这些事要么是我亲身经历的要么是他亲口对我讲的。弗莱德里克贾里尼克(FredJelinek)出生于捷克一个富有的犹太家庭。他的父母原本打算送他去英国的公学(私立学校)读书。为了教他德语还专门请的一位德国的家庭女教师但是第二次世界大战完全打碎了他们的梦想。他们先是被从家中赶了出去流浪到布拉格。他的父亲死在了集中营弗莱德自己成天在街上玩耍完全荒废了学业。二战后当他再度回到学校时他的成绩一塌糊涂全部是D但是很快他就赶上了班上的同学。不过他在小学时从来没有得过A。年他的母亲带领全家移民美国。在美国贾里尼克一家生活非常贫困全家基本是靠母亲做点心卖钱为生弗莱德自己十四五岁就进工厂打工补助全家。贾里尼克最初想成为一个律师为他父亲那样的冤屈者辩护但他很快意识到他那浓厚的外国口音将使他在法庭上的辩护很吃力。贾里尼克的第二个理想是成为医生他想进哈佛大学医学院但经济上他无法承担医学院年高昂的学费。与此同时麻省理工学院给于了他一份(为东欧移民设的)全额奖学金。贾里尼克决定到麻省理工学电机工程。在那里他遇到了信息论的鼻祖香农博士和语言学大师贾格布森RomanJakobson(他提出了著名的通信六功能)注释一后来贾里尼克又陪着太太听最伟大的语言学家乔姆斯基(NoamChomsky)的课。这三位大师对贾里尼克今后的研究方向利用信息论解决语言问题产生的重要影响。贾里尼克从麻省理工获得博士学位后在哈佛大学教了一年书然后到康乃尔大学任教。他之所以选择康乃尔大学是因为找工作时和那里的一位语言学家谈得颇为投机。当时那位教授表示愿意和贾里尼克在利用信息论解决语言问题上合作。但是等贾里尼克到康乃尔以后那位教授表示对语言学在没有兴趣而转向写歌剧了。贾里尼克对语言学家的坏印象从此开始。加上后来他在IBM时发现语言学家们嘴上头头是道干起活来高不成低不就对语言学家从此深恶痛绝。他甚至说:"我每开除一名语言学家我的语音识别系统错误率就降低一个百分点。"这句话后来在业界广为流传为每一个搞语音识别和语言处理的人所熟知。贾里尼克在康乃尔十年磨一剑潜心研究信息论终于悟出了自然语言处理的真谛。1972年贾里尼克到IBM华生实验室(IBMT.G.WatsonLabs

职业精品

XX有限公司(薪资福利管理制度).doc

公司采购流程管理制度制定方法.doc

招聘管理与面试技巧.ppt

公司采购流程管理制度.doc

用户评论(1)

0/200
  • simonyanzi 2013-05-19 07:44:17

    很好,值得一看

上传我的资料

精彩专题

相关资料换一换

资料评价:

/ 58
所需积分:0 立即下载

意见
反馈

返回
顶部