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

统计语言模型,刘杰liujxxxy,2,主要内容,概述数学建模一.统计语言模型概述二.现有的主要统计语言模型三.数据平滑方法,3,概述,我们为什么需要统计语言模型？统计语言模型出现的历史：1、从小规模受限语言处理走向大规模真实文本处理的。把这个新目标正式列入大会主题的是1990年在赫尔辛基举行的第13届国际计算语言学大会（Coling90）。2、1992年在蒙特利尔召开的第4届机器翻译的理论和方法国际会议(TMI-92)宣布大会的主题是：“机器翻译中的经验主义和理性主义方法”。公开承认，在传统的基于语言学和人工智能方法的自然语言处理技术以外，还有一种基于语料库和统计语言模型的新方法正在迅速崛起。,4,概述,首先成功利用数学方法解决自然语言处理问题的是语音和语言处理大师贾里尼克(FredJelinek)。当时贾里尼克在IBM公司做学术休假(SabbaticalLeave)，领导了一批杰出的科学家利用大型计算机来处理人类语言问题。统计语言模型就是在那个时候提出的。十几年后，李开复用统计语言模型把997词语音识别的问题简化成了一个20词的识别问题，实现了有史以来第一次大词汇量非特定人连续语音的识别。,5,概述,历史上曾经先后出现过两个方法迥异的英语词性标注系统：TAGGIT系统拥有3000条上下文相关规则，而CLAWS系统6完全采用概率统计方法。两个系统各自完成了100万词次的英语语料库的自动词性标注任务。评则结果表明，采用概率统计方法的CLAWS系统的标注精度达到96%，比TAGGIT系统提高了近20个百分点。,6,语言建模,从统计角度看，自然语言中的一个句子s可以由任何词串构成。不过P(s)有大有小。如：s1=我刚吃过晚饭s2=刚我过晚饭吃(并不要求语法是完备的,可对任意s给出概率)P(s1)P(s2)对于给定的句子s而言，通常P(s)是未知的。对于一个服从某个未知概率分布P的语言L，根据给定的语言样本估计P的过程被称作语言建模。,7,语言建模,根据语言样本估计出的概率分布P就称为语言L的语言模型。语言建模技术首先在语音识别研究中提出，后来陆续用到OCR、手写体识别、机器翻译、信息检索等领域。在语音识别中，如果识别结果有多个，则可以根据语言模型计算每个识别结果的可能性，然后挑选一个可能性较大的识别结果。汉语切分歧义消解？（借助语言模型）,8,一、统计语言模型概述,设wi是文本中的任意一个词，如果已知它在该文本中的前两个词wi-2wi-1，便可以用条件概率P(wi|wi-2wi-1)来预测wi出现的概率。这就是统计语言模型的概念。,9,一、统计语言模型概述,“Johnreada_”给定一个句子中前面n-1个词，预测下面的词是哪个词。由于语言的规律性，句子中前面出现的词对后面可能出现的词有很强的预示作用。,10,一、现有的主要统计语言模型,对于二元模型：,对于一个句子出现的概率可用下式估计（链式规则）：,我们引进一个起始词,11,概率p(wi|wi-1)一般采用最大相似度估计的方法估计:,12,1、n-gram,为了便于计算，通常考虑的历史不能太长，一般只考虑前面n-1个词构成的历史。即：,13,1、n-gram,“thelargegreen_.”“mountain”?“tree”?“Sueswallowedthelargegreen_.”“pill”?“broccoli”?如果知道“Sueswallowed”会缩小可选择的下一个词的范围。如何选择n?,14,1、n-gram,n较大时提供了更多的语境信息，语境更具区别性但是，参数个数多、计算代价大、训练语料需要多、参数估计不可靠。n较小时语境信息少，不具区别性但是，参数个数少、计算代价小、训练语料无需太多、参数估计可靠。,15,1、n-gram语言模型,一般来说，如果用变量s代表文本中一个任意的词序列，它由顺序排列的L个词组成，即s=w1w2.wL，则统计语言模型就是该词序列s在文本中出现的概率P(s)利用概率的乘积公式，P(s)可展开为：,不难看出，为了预测词wn的出现概率，必须知道它前面所有词的出现概率。从计算上来看，这种方法太复杂了。,16,统计语言模型有点像天气预报中使用的概率方法，用来估计概率参数的大规模语料库好比是一个地区历年积累起来的气象记录。而用三元模型来做天气预报，就好比是根据前两天的天气情况来预测今天的天气。天气预报当然不可能百分之百准确，但是我们大概不会因此就全盘否定这种实用的概率方法.,17,三元模型（或一般的N元模型）只利用了语言的表层信息（或知识），即符号（字、词、词性标记等）序列的同现信息。不能说它是十全十美的。在这一领域中，下一个研究目标应当是结构化对象（如句法树或语义框架）的统计模型。当然能做到语言理解是了不起的成果，它肯定会比目前这种统计语言模型强得多，这是不争的事实。问题是目前国内外还没有哪一种语言的句法-语义分析系统可以胜任大规模真实文本处理的重任。因此，对于世界各国的语言来说，当前的主流技术仍是语料库方法和统计语言模型。,18,1、n-gram语言模型,计算量：设词表里共有V个不同的词，共有个不同的N-1元组，对于每个分布，又必须估算V个参数，因此共需估算出个参数。若V=10000,N=3,则必须计算出1012个参数。因此N不能取得太大，一般取2或3。,19,1、n-gram,unigram(n=1)p(wi)若语言中有20000个词，则需要估计20000个参数bigram(n=2)p(wi|wi-1)若语言中有20000个词，则需要估计200002个参数trigram(n=3)p(wi|wi-2wi-1)若语言中有20000个词，则需要估计200003个参数four-gram(n=4)很少使用、不太现实(有时也称为digram或quadrigram),20,1、n-gram语言模型,二元、三元及n元模型的公式表示：tri-gram:如果任意一个词wi的出现概率只同它前面的两个词有关，问题就可以得到极大的简化。这时的语言模型叫做三元模型,bi-gram:假设当前词的出现概率仅与前一个词有关，句子的概率可以表示为,21,1.n-gram语言模型,式中c(.)表示一个特定词序列在整个语料库中出现的累计次数。,n-gram:一般来说，n元模型就是假设当前词的出现概率只同它前面的n-1个词有关。,重要的是这些概率参数都是可以通过大规模语料库来计算的。比如三元、二元概率有,22,1、n-gram语言模型举例,两个概念：训练语料(trainingdata)：用于建立模型的给定语料。最大似然估计(maximumlikelihood,ML)：用相对频率计算概率的公式。例如，给定训练语料：“JohnreadMobyDick”，“Maryreadadifferentbook”,“ShereadabookbyCher”求”Johnreadabook”的二元文法的概率.,23,1、n-gram语言模型举例,24,1、n-gram语言模型举例,句子的概率表现为若干bigram参数的乘积，若句子太长，计算时，会引起下溢(underflow)，可以采用取对数并相加的方式。Ln(P(JOHNREADABOOK)=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或切分句子边界，增加两个特殊的词和Ieat.Ieat.Isleep.Isleep.参数估计利用训练语料，估计模型参数,26,1、建立n-gram（最大似然估计(MLE)）,令c(w1,.,wn)表示n-gramw1,.,wn在训练语料中出现的次数。则,27,1.n-gram语言模型应用,1.1语音识别语音识别作为计算机汉字输入的另一种方式越来越受到业内人士的青睐。所谓听写机就是语音识别的一种商品。那么当前商品化的听写机采用的是什么技术呢？其实，语音识别任务可视为对以下条件概率极大值的计算问题：s*=argmaxsP(s|speechsignal)=argmaxsP(speechsignal|s)P(s)/P(speechsignal)=argmaxsP(speechsignal|s)P(s)式中数学符号argmaxs表示对不同的候选词序列s计算条件概率P(s|speechsignal)的值，从而使s*成为条件概率值最大的词序列。它也就是当前输入语音信号speechsignal所对应的输出词串了。,28,1.n-gram语言模型应用,公式第二行是利用贝叶斯定律转写的结果，因为条件概率P(speechsignal|s)比较容易估值。公式的分母P(speechsignal)对给定的语音信号是一个常数，不影响极大值的计算，故可以从公式中删除。在公式第三行所示的结果中，P(s)叫做统计语言模型；P(speechsignal|s)叫做声学模型。据调查，目前市场上中文和英文的听写机产品都是用词的三元模型实现的,几乎完全不用句法-语义分析手段。如同汉语拼音输入法中的拼音汉字转换,29,1.n-gram语言模型应用,1.2分词句子s=c1c2cms=w1w2wk，n元模型,如果n1，即uni-gram，C为语料,30,1.3词性标注句子分词后，对每个词进行词性标注。由于存在兼类词，例如“学习”就是n、v兼类。考虑用n-gram模型(词性的n元语法模型)。,31,2、上下文无关模型,1、上下文无关模型：Nw表示词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,三、数据平滑技术,数据稀疏问题（datasparseness）N-gram存在问题，训练语料毕竟是有限的，这样导致很多事件，如trigram中，w1w2w3根本没有出现过。根据最大似然估计，这些事件的概率为零。然而这些事件的真实概率并不一定为零。这个问题被成为数据稀疏问题。,37,三、数据平滑技术,MLE给训练样本中未观察到的事件赋以0概率。若某n-gram在训练语料中没有出现,则该n-gram的概率必定是0。解决的办法是扩大训练语料的规模。但是无论怎样扩大训练语料，都不可能保证所有的词在训练语料中均出现。由于训练样本不足而导致所估计的分布不可靠的问题，称为数据稀疏问题。在NLP领域中，数据稀疏问题永远存在，不太可能有一个足够大的训练语料，因为语言中的大部分词都属于低频词。,38,Zipf定律描述了词频以及词在词频表中的位置之间的关系。针对某个语料库，若某个词w的词频是f，并且该词在词频表中的序号为r(即w是所统计的语料中第r常用词)，则fr=k(k是一个常数)若wi在词频表中排名50，wj在词频表中排名150，则wi的出现频率大约是wj的频率的3倍。例：马克吐温的小说TomSawyer共71,370词(wordtokens)出现了8,018个不同的词(wordtypes),39,40,41,42,43,Zipf定律告诉我们语言中只有很少的常用词，语言中大部分词都是低频词(不常用的词)Zipf的解释是PrincipleofLeasteffort(讲话的人和听话的人都想省力的平衡)说话人只想使用少量的常用词进行交流听话人只想使用没有歧义的词(量大低频)进行交流Zipf定律告诉我们对于语言中的大多数词，它们在语料中的出现是稀疏的.只有少量词语料库可以提供它们规律的可靠样本。,44,数据稀疏问题,“JohnreadMobyDick”，“Maryreadadifferentbook”,“ShereadabookbyCher”考虑计算句子CHERREADABOOK的概率。c(CHERREAD)=0p(READ|CHER)0p(CHERREADABOOK)=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|11P(Johnreadabook)=P(John|)P(read|John)P(a|read)P(book|a)P(|book)P(Cherreadabook)=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-gr