爱问 爱问共享资料 爱问分类
首页 > > > 数学之美.pdf

数学之美.pdf

数学之美.pdf

上传者: 米修米修
2w+次下载 83人收藏 暂无简介 简介 2011-01-07 举报

简介:当前资料暂无简介!

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

数学之美.pdf

数学之美.pdf

上传者: 米修米修
2w+次下载 83人收藏 暂无简介 简介 2011-01-07 举报

简介:当前资料暂无简介!

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

用户评论(1)

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

    很好,值得一看

上传我的资料

资料阅读排行

关闭

请选择举报的类型

关闭

提示

提交成功!

感谢您对爱问共享资料的支持,我们将尽快核实并处理您的举报信息。

关闭

提示

提交失败!

您的举报信息提交失败,请重试!

关闭

提示

重复举报!

亲爱的用户!感觉您对爱问共享资料的支持,请勿重复举报噢!

全屏 缩小 放大
收藏
资料评价:

/ 58
所需积分:0 立即下载
返回
顶部
举报
资料
关闭

温馨提示

感谢您对爱问共享资料的支持,精彩活动将尽快为您呈现,敬请期待!