统计语言模型及数据平滑技术PPT.ppt

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,*,统计语言模型,刘杰,liujxxxy,1,2,主要内容,概述,数学建模,一,.,统计语言模型概述,二,.,现有的主要统计语言模型,三,.,数据平滑方法,3,概述,我们为什么需要统计语言模型？,统计语言模型出现的历史：,1,、,从小规模受限语言处理走向大规模真实文本处理的。把这个新目标正式列入大会主题的是,1990,年在赫尔辛基举行的第,13,届国际计算语言学大会（,Coling,90,）。,2,、,1,992,年在蒙特利尔召开的第,4,届机器翻译的理论和方法国际会议,(TMI-92),宣布大会的主题是：,“,机器翻译中的经验主义和理性主义方法,”,。公开承认，在传统的基于语言学和人工智能方法的自然语言处理技术以外，还有一种基于语料库和统计语言模型的新方法正在迅速崛起。,4,概述,首先成功利用数学方法解决自然语言处理问题的是语音和语言处理大师贾里尼克,(,Fred Jelinek,),。当时贾里尼克在,IBM,公司做学术休假,(Sabbatical Leave),，领导了一批杰出的科学家利用大型计算机来处理人类语言问题。统计语言模型就是在那个时候提出的。十几年后，李开复用统计语言模型把,997,词语音识别的问题简化成了一个,20,词的识别问题，实现了有史以来第一次大词汇量非特定人连续语音的识别。,5,概述,历史上曾经先后出现过两个方法迥异的英语词性标注系统：,TAGGIT,系统拥有,3000,条上下文相关规则，而,CLAWS,系统,6,完全采用概率统计方法。两个系统各自完成了,100,万词次的英语语料库的自动词性标注任务。评则结果表明，采用概率统计方法的,CLAWS,系统的标注精度达到,96%,，比,TAGGIT,系统提高了近,20,个百分点。,6,语言建模,从统计角度看，自然语言中的一个句子,s,可以,由任何词串构成。不过,P,(,s,),有大有小。如：,s,1=,我刚吃过晚饭,s,2=,刚我过晚饭吃,(,并不要求语法是完备的,可对任意,s,给出概率,),P,(,s,1),P,(,s,2),对于给定的句子,s,而言，通常,P,(,s,),是未知的。,对于一个服从某个未知概率分布,P,的语言,L,，,根据给定的语言样本估计,P,的过程被称作语言建模。,7,语言建模,根据语言样本估计出的概率分布,P,就称为语言,L,的语言模,型。,语言建模技术首先在语音识别研究中提出，后来陆续用,到,OCR,、手写体识别、机器翻译、信息检索等领域。,在语音识别中，如果识别结果有多个，则可以根据语言,模型计算每个识别结果的可能性，然后挑选一个可能性,较大的识别结果。,汉语切分歧义消解？（借助语言模型）,8,一、统计语言模型概述,设,w,i,是文本中的任意一个词，如果已知它在该文本中的前两个词,w,i-2,w,i,-1,，便可以用条件概率,P(w,i,|w,i-2,w,i,-1,),来预测,w,i,出现的概率。这就是,统计语言模型,的概念。,9,一、统计语言模型概述,“,John read a _,”,给定一个句子中前面,n,-1,个词，预测下面的词是哪个词。,由于语言的规律性，句子中前面出现的词对后面可能出现的词有很强的预示作用。,10,一、现有的主要统计语言模型,对于二元模型：,对于一个句子出现的概率可用下式估计（链式规则）：,我们引进一个起始词,11,概率,p(w,i,|w,i-1,),一般采用最大相似度估计的方法估计,:,12,1,、,n,-gram,为了便于计算，通常考虑的历史不能太长，一般只考虑前面,n-1,个词构成的历史。,即：,13,1,、,n,-gram,“,the large green _.,”,“,mountain,”,?,“,tree,”,?,“,Sue swallowed the large green _.,”,“,pill,”,?,“,broccoli,”,?,如果知道,“,Sue,swallowed,”,会缩小可选择的下一个词的范围。,如何选择,n,?,14,1,、,n,-gram,n,较大时,提供了更多的语境信息，语境更具区别性,但是，参数个数多、计算代价大、训练语料需要多、参数估计不可靠。,n,较小时,语境信息少，不具区别性,但是，参数个数少、计算代价小、训练语料无需太多、参数估计可靠。,15,1,、,n-gram,语言模型,一般来说，如果用变量,s,代表文本中一个任意的词序列，它由顺序排列的,L,个词组成，即,s=w,1,w,2,.w,L,，则统计语言模型就是该词序列,s,在文本中出现的概率,P(s),利用概率的乘积公式，,P(s),可展开为：,不难看出，为了预测词,w,n,的出现概率，必须知道它前面所 有词的出现概率。从计算上来看，这种方法太复杂了。,16,统计语言模型有点像天气预报中使用的概率方法，用来估计概率参数的大规模语料库好比是一个地区历年积累起来的气象记录。而用三元模型来做天气预报，就好比是根据前两天的天气情况来预测今天的天气。天气预报当然不可能百分之百准确，但是我们大概不会因此就全盘否定这种实用的概率方法,.,17,三元模型（或一般的,N,元模型）只利用了语言的表层信息（或知识），即符号（字、词、词性标记等）序列的同现信息。不能说它是十全十美的。在这一领域中，下一个研究目标应当是结构化对象（如句法树或语义框架）的统计模型。当然能做到语言理解是了不起的成果，它肯定会比目前这种统计语言模型强得多，这是不争的事实。问题是目前国内外还没有哪一种语言的句法,-,语义分析系统可以胜任大规模真实文本处理的重任。因此，对于世界各国的语言来说，当前的主流技术仍是语料库方法和统计语言模型。,18,1,、,n-gram,语言模型,计算量：,设词表里共有,V,个不同的词，共有 个不同的,N-1,元组，对于每个分布，又必须估算,V,个参数，因此共需估算出 个参数。若,V=10000,N=3,则必须计算出,10,12,个参数。因此,N,不能取得太大，一般取,2,或,3,。,19,1,、,n,-gram,unigram(,n,=1),p,(,w,i,),若语言中有,20000,个词，则需要估计,20000,个参数,bigram(,n,=2),p,(,w,i,|,w,i-,1,),若语言中有,20000,个词，则需要估计,20000,2,个参数,trigram(,n,=3),p,(,w,i,|,w,i-,2,w,i-,1,),若语言中有,20000,个词，则需要估计,20000,3,个参数,four-gram(,n,=4),很少使用、不太现实,(,有时也称为,digram,或,quadrigram),20,1,、,n-gram,语言模型,二元、三元及,n,元模型的公式表示：,tri-gram:,如果任意一个词,w,i,的出现概率只同它前面的两个词有关，问题就可以得到极大的简化。这时的语言模型叫做三元模型,bi-gram:,假设当前词的出现概率仅与前一个词有关，句子的概率可以表示为,21,1.n-gram,语言模型,式中,c(.),表示一个特定词序列在整个语料库中出现的累计次数。,n-gram:,一般来说，,n,元模型就是假设当前词的出现概率只同它前面的,n-1,个词有关。,重要的是这些概率参数都是可以通过大规模语料库来计算的。比如三元、二元概率有,22,1,、,n-gram,语言模型举例,两个概念：,训练语料,(,training data,),：用于建立模型的给定语料。,最大似然估计,(,maximum likelihood,ML),：用相对频率,计算概率的公式。,例如，给定训练语料：,“,John read Moby Dick,”,，,“,Mary read a different book,”,“,She read a book by Cher,”,求,”,John read a book,”,的,二元文法的概率,.,23,1,、,n-gram,语言模型举例,24,1,、,n-gram,语言模型举例,句子的概率表现为若干,bigram,参数的乘积，若句子,太长，计算时，会引起下溢,(underflow),，可以采用,取对数并相加的方式。,Ln,(,P,(,JOHN READ A BOOK,),=,Ln,(,p,(,JOHN|,),+Ln,(,p,(,READ|JOHN,),+Ln,(,p,(,A|READ,),+Ln,(,p,(,BOOK|A,),+Ln,(,p,(,|BOOK,),=Ln,(1/3),+Ln,(1),+Ln,(2/3),+Ln,(1/2),+Ln,(1/2),=-2.8902,25,1,、建立,n-gram,数据准备,:,确定训练语料,对语料进行,tokenization,或切分句子边界，增加两个特殊的词,和,I eat.,I eat.,I sleep.,I sleep.,参数估计,利用训练语料，估计模型参数,26,1,、建立,n-gram,（最大似然估计,(MLE),）,令,c,(,w,1,.,w,n,),表示,n-gram,w,1,.,w,n,在训练语料中出,现的次数。则,27,1.n-gram,语言模型应用,1.1,语音识别,语音识别作为计算机汉字输入的另一种方式越来越受到业内人士的青睐。所谓听写机就是语音识别的一种商品。那么当前商品化的听写机采用的是什么技术呢？,其实，语音识别任务可视为对以下条件概率极大值的计算问题：,s*=argmax,s,P(s|speech signal),=argmax,s,P(speech signal|s)P(s)/P(speech signal),=argmax,s,P(speech signal|s)P(s),式中数学符号,argmax,s,表示对不同的候选词序列,s,计算条件概率,P(s|speech signal),的值，从而使,s*,成为条件概率值最大的词序列。它也就是当前输入语音信号,speech signal,所对应的输出词串了。,28,1.n-gram,语言模型应用,公式第二行是利用贝叶斯定律转写的结果，因为条件概率,P(speech signal|s),比较容易估值。,公式的分母,P(speech signal),对给定的语音信号是一个常数，不影响极大值的计算，故可以从公式中删除。,在公式第三行所示的结果中，,P(s),叫做统计语言模型；,P(speech signal|s),叫做声学模型。,据调查，目前市场上中文和英文的听写机产品都是用词的三元模型实现的,几乎完全不用句法,-,语义分析手段。,如同汉语拼音输入法中的拼音汉字转换,29,1.n-gram,语言模型应用,1.2,分词,句子,s=c,1,c,2,c,m,s=w,1,w,2,w,k,，,n,元模型,如果,n,1,，即,uni-gram,，,C,为语料,30,1.3,词性标注,句子分词后，对每个词进行词性标注。由于存在兼类词，例如,“,学习,”,就是,n,、,v,兼类。考虑用,n-gram,模型,(,词性的,n,元语法模型,),。,31,2,、上下文无关模型,1,、上下文无关模型：,N,w,表示词,w,在训练文本中出现的总次数，,N,为训练文本的总词数，被称为,一元文法统计模型,优点：仅仅需要非常少的训练数据,缺点：没有考虑上下文信息，统计信息不充分，精确度不高。,32,3,、,N-POS,模型,在,N-pos,模型中，一个词出现的概率条件地依赖于前,N-1,个词的词类，令,g(w),表示词,w,的词类。,假设一个词的词类出现概率条件地依赖于前,N-1,个词的词类，而该词本身的概率依赖于该词所属的词类，则得到下式：,共需估算 个参数。,G,为词类的集合,.,共需估算出 个参数,33,3,、,N-POS,模型,考虑到一词多类，比如,“,学习,”,可以是动词也可以是名词，出现的概率应该是作为名词的概率加上作为动词的概率，有如下公式：,优点：需要的训练数据比,N-gram,模型少，模型的参数空间小得多,缺点：词的概率依赖词性，不如词本身的划分更加精细，实际应用中一般难以达到,N-gram,模型的精度。,34,4,、基于决策树的语言模型,一种通用的语言统计模型,35,5,、动态、自适应、基于缓存的语言模型,静态语言模型,概率分布都是预先从数据库里估算好的，在运用过程中，并不改变这些数据。,能够根据词在局部文本中的出现情况，动态地调整语言模型中的概率分布数据的语言模型称为动态的、自适应的或者基于缓存的语言模型。,N,个最近出现的词 存在一个缓存中，作为独立的训练数据，估算出一个单独的动态,Trigram,数据，在与静态模型中的频度分布数据通过线性插值结合在一起，形成一个混合的动态自适应的模型。,这种混合模型可以有效的避免数据稀疏问题，并提高原静态模型的表现能力。对现象,”,某些在文本中通常很少出现的词,在某一局部文本中突然大量地出现,”,具有较好效果,.,36,三、数据平滑技术,数据稀疏问题（,data sparseness,）,N-gram,存在问题，训练语料毕竟是有限的，这样导致很多事件，如,trigram,中，,w,1,w,2,w,3,根本没有出现过。根据最大似然估计，这些事件的概率为零。然而这些事件的真实概率并不一定为零。这个问题被成为数据稀疏问题。,37,三、数据平滑技术,MLE,给训练样本中未观察到的事件赋以,0,概率。,若某,n-gram,在训练语料中没有出现,则该,n-gram,的概率必定是,0,。,解决的办法是扩大训练语料的规模。但是无论怎样扩大训练语料，都不可能保证所有的词在训练语料中均出现。,由于训练样本不足而导致所估计的分布不可靠的问题，称为数据稀疏问题。,在,NLP,领域中，数据稀疏问题永远存在，不太可能有一个足够大的训练语料，因为语言中的大部分词都属于低频词。,38,Zipf,定律描述了词频以及词在词频表中的位置之间的关系。,针对某个语料库，若某个词,w,的词频是,f,，并且该词在词频表中的序号为,r(,即,w,是所统计的语料中第,r,常用词,),，则,f r=k(k,是一个常数,),若,w,i,在词频表中排名,50,，,w,j,在词频表中排名,150,，则,w,i,的出现频率大约是,w,j,的频率的,3,倍。,例：马克吐温的小说,Tom Sawyer,共,71,370,词,(word tokens),出现了,8,018,个不同的词,(word types),39,40,41,42,43,Zipf,定律告诉我们语言中只有很少的常用词，语言中大部分词都是低频词,(,不常用的词,),Zipf,的解释是,Principle of Least effort(,讲话的人和听话的人都想省力的平衡,),说话人只想使用少量的常用词进行交流,听话人只想使用没有歧义的词,(,量大低频,),进行交流,Zipf,定律告诉我们对于语言中的大多数词，它们在语料中的出现是稀疏的,.,只有少量词语料库可以提供它们规律的可靠样本。,44,数据稀疏问题,“,John read Moby Dick,”,，,“,Mary read a different book,”,“,She read a book by Cher,”,考虑计算句子,CHER READ A BOOK,的概率。,c,(,CHER READ,)=0,p,(,READ,|,CHER,),0,p,(,CHER READ A BOOK,)=0(,有问题,),45,数据稀疏问题,Balh,等人的工作,:,用,150,万词的训练语料训练,trigram,模型，测试语料（同样来源）中,23%,的,trigram,没有在训练语料中出现过。,MLE,给训练样本中未观察到的事件赋以,0,概率。,若某,n,-gram,在训练语料中没有出现,则该,n,-gram,的概率必定是,0,。,解决的办法是扩大训练语料的规模。但是无论怎样扩大训练语料，都不可能保证所有的词在训练语料中均出现。,由于训练样本不足而导致所估计的分布不可靠的问题，称为数据稀疏问题。,在,NLP,领域中，数据稀疏问题永远存在，不太可能有一个足够大的训练语料，因为语言中的大部分词都属于低频词。,46,对语言而言，由于数据稀疏的存在，,MLE,不是一种很好的参数估计办法。,解决办法,:,平滑技术,把在训练样本中出现过的事件的概率适当减小，把减小得到的概率密度分配给训练语料中没有出现过的事件,.,这个过程有时也称为,discounting(,减值,),减值法,(Discounting),基本思想：修改训练样本中的事件的实际计数，使样本中不同事件的概率之和小于,1,，剩余的概率量分配给未见概率。,47,三、数据平滑技术,数据平滑技术用来对采用最大似然规则的概率估计进行调整。,首先它可以保证模型中任何概率均不为零。,其次，数据平滑使模型参数概率分布趋向更加均匀。低概率（包括零概率）被调高，高概率被调低。,48,4,数据平滑技术,(1),.,加法平滑,(2).Good-turing,平滑,(3).backing-off,平滑,(3).jelinek-mercer,平滑,(4).katz,平滑,(5).church-gale,平滑,49,(1),.,加一平滑,每一种情况出现的次数加,1,。,规定任何一个,n-gram,在训练语料至少出现一次（即规定没有出现过的,n-gram,在训练语料中出现了一次），则,:new_count(n-gram)=old_count(n-gram)+1,没有出现过的,n-gram,的概率不再是,0,例如，对于,uni,-gram,，设,w1,w2,w3,三个词，概率分别,为：,1/3,0,2/3,，加,1,后情况？,2/6,1/6,3/6,50,(1),.,加法平滑,51,(1),.,加一平滑,平滑后的,bigram,频次,频次全都加,1,52,(1),.,加一平滑,=1,时,N:,训练语料中所有的,n-gram,的数量，包括重复的,V:,被考虑语料的词汇量,53,(1),.,加一平滑,在前面的,3,个句子的例子中，,|V|,11,P,(,John read a book,)=,P,(,John,|),P,(,read,|,John,),P,(,a|read,),P,(,book|a,),P,(|,book,),P(Cher read a book,),=,P,(,Cher,|),P,(,read|Cher,),P,(,a|read,),P,(,book|a,),P,(|,book,）,这种方法性能较差,为什么,?,54,(1),.,加一平滑,Add-one,平滑,训练语料中未出现的,n-gram,的概率不再为,0,，是一个大于,0,的较小的概率值。,但由于训练语料中未出现,n-gram,数量太多，平滑后，所有未出现的,n-gram,占据了整个概率分布中的一个很大的比例。,因此，在,NLP,中，,Add-one,给训练语料中没有现过的,n-gram,分配了太多的概率空间。,认为所有未出现的,n-gram,概率相等，,这是否合理？,出现在训练语料中的那些,n-gram,，都增加同样的频度值，,这是否公平？,(,低频、高频,),55,(1),.,加一平滑,56,(1),.,加法平滑,Add-delta,平滑,(Lidstone,s,不是加,1,而是加一个小于,1,的正数 ，通常,=0.5,，此时又称为,Jeffreys-Perks Law,或,ELE,效果比,Add-one,好，但是仍然不理想,57,(2)Good-Turing,平滑,I.J.Good 1953,年引用,Turing,的方法来估计概率分布。,Good-Turing,估计是许多数据平滑技术的核心。该方法的基本思想是：利用高频率,n,-gram,的频率调整低频的,n,-gram,的频率。,假设,N,是样本数据的大小，,n,r,是在,N,元模型的训练集中正好出现,r,次的事件的数目（在这里，事件为,N,元对）,n,r,表示有多少个,N,元对出现了,r,次,58,(2)Good-Turing,平滑,Good-Turing,估计适合单词量大并具有大量的观察数据的情况下使用，在观察数据不足的情况下，本身出现次数就是不可靠的，利用它来估计出现次数就更不可靠了,。,缺乏利用低元模型对高元模型进行线性插值的思想,。,59,（,3,）线性插值平滑,线性插值平滑（,Linear Interpolation Smoothing,）方法通常也被称作,Jelinek-Mercer,平滑。,Jelinek,和,Mercer,在,1980,年首先提出了这种数据平滑算法的思想，,Brown,在,1992,年给出了线性插值的平滑公式：,该参数平滑技术的基本思想是利用低元,n-gram,模型对高元,n-gram,模型进行线性插值。用降元的方法来弥补高元的数据稀疏问题，数据估计有一定的可靠性。但是参数估计较困难。,低元模型,60,作业：,1,、概述,N,元文法模型和,N-POS,模型,2,、数据平滑技术的概念，概述加法平滑和,Good-Turing,平滑的原理。,