N-gram模型

N-gram模型N-Gram是大词汇连续语音识别中常用的一种语言模型，对中文而言，我们称之为汉语语言模型(CLM,ChineseLanguageModel)。汉语语言模型利用上下文中相邻词间的搭配信息，在需要把连续无空格的拼音、笔划，或代表字母或笔划的数字，转换成汉字串(即句子)时，可以计算出具有最大概率的句子，从而实现到汉字的自动转换，无需用户手动选择，避开了许多汉字对应一个相同的拼音(或笔划串，或数字串)的重码问题。该模型基于这样一种假设，第n个词的出现只与前面N-1个词相关，而与其它任何词都不相关，整句的概率就是各个词出现概率的乘积。这些概率可以通过直接从语料中统计N个词同时出现的次数得到。常用的是二元的Bi-Gram和三元的Tri-Gram。在介绍N-gram模型之前，让我们先来做个香农游戏（ShannonGame）。我们给定一个词，然后猜测下一个词是什么。当我说“艳照门”这个词时，你想到下一个词是什么呢？我想大家很有可能会想到“陈冠希”，基本上不会有人会想到“陈志杰”吧。N-gram模型的主要思想就是这样的。对于一个句子T，我们怎么算它出现的概率呢？假设T是由词序列W1,W2,W3,…Wn组成的，那么P(T)=P(W1W2W3Wn)=P(W1)P(W2|W1)P(W3|W1W2)…P(Wn|W1W2…Wn-1)补充知识：但是这种方法存在两个致命的缺陷：一个缺陷是参数空间过大，不可能实用化；另外一个缺陷是数据稀疏严重。为了解决这个问题，我们引入了马尔科夫假设：一个词的出现仅仅依赖于它前面出现的有限的一个或者几个词。如果一个词的出现仅依赖于它前面出现的一个词，那么我们就称之为bigram。即P(T)=P(W1W2W3…Wn)=P(W1)P(W2|W1)P(W3|W1W2)…P(Wn|W1W2…Wn-1)≈P(W1)P(W2|W1)P(W3|W2)…P(Wn|Wn-1)如果一个词的出现仅依赖于它前面出现的两个词，那么我们就称之为trigram。在实践中用的最多的就是bigram和trigram了，而且效果很不错。高于四元的用的很少，因为训练它需要更庞大的语料，而且数据稀疏严重，时间复杂度高，精度却提高的不多。那么我们怎么得到P(Wn|W1W2…Wn-1)呢？一种简单的估计方法就是最大似然估计(MaximumLikelihoodEstimate）了。即P(Wn|W1W2…Wn-1)=(C(W1W2…Wn))/(C(W1W2…Wn-1))剩下的工作就是在训练语料库中数数儿了，即统计序列C(W1W2…Wn)出现的次数和C(W1W2…Wn-1)出现的次数。下面我们用bigram举个例子。假设语料库总词数为13,748P(IwanttoeatChinesefood)=P(I)*P(want|I)*P(to|want)*P(eat|to)*P(Chinese|eat)*P(food|Chinese)=0.25*1087/3437*786/1215*860/3256*19/938*120/213=0.000154171ps：网上很多资料中，表1，词与词频的张表是没有的，所以造成文章表意不清。这里还有一个问题要说，那就是数据稀疏问题了，假设词表中有20000个词，如果是bigram那么可能的N-gram就有400000000个，如果是trigram，那么可能的N-gram就有8000000000000个！那么对于其中的很多词对的组合，在语料库中都没有出现，根据最大似然估计得到的概率将会是0，这会造成很大的麻烦，在算句子的概率时一旦其中的某项为0，那么整个句子的概率就会为0，最后的结果是，我们的模型只能算可怜兮兮的几个句子，而大部分的句子算得的概率是0.因此，我们要进行数据平滑（dataSmoothing），数据平滑的目的有两个：一个是使所有的N-gram概率之和为1，使所有的N-gram概率都不为0.有关数据平滑的详细内容后面会再讲到，这里不再赘述。了解了噪声信道模型和N-gram模型的思想之后，其实我们自己就能实现一个音词转换系统了，它是整句智能输入法的核心，其实我们不难猜到，搜狗拼音和微软拼音的主要思想就是N-gram模型的，不过在里面多加入了一些语言学规则而已标签：杂谈统计语言模型假设一个句子S可以表示为一个序列S=w1w2…wn，语言模型就是要求句子S的概率P(S)：这个概率的计算量太大，解决问题的方法是将所有历史w1w2…wi-1按照某个规则映射到等价类S(w1w2…wi-1)，等价类的数目远远小于不同历史的数目，即假定：N-Gram模型当两个历史的最近的N-1个词（或字）相同时，映射两个历史到同一个等价类，在此情况下的模型称之为N-Gram模型。N-Gram模型被称为一阶马尔科夫链。N的值不能太大，否则计算仍然太大。根据最大似然估计，语言模型的参数：其中，C(w1w2…wi)表示w1w2…wi在训练数据中出现的次数平滑技术的引入传统的估计方法对于随机变量£的N次独立观察的样本容量N有如下要求：NK其中K为随机变量能够取到的值的个数。实际语言模型中往往无法满足这个要求。例如：词性标注问题，共有140个可能的标记，考虑当前词前后两个词的影响的三阶模型。K=140*140*140=2,744,000给定一个10万词左右的人工标注训练集，即N=100,00，可见训练数据显得非常不足。假设k泛指某一事件，N(k)表示事件k观察到的频数，极大似然法使用相对频数作为对事件k的概率估计：p(k)=N(k)/N在语言模型中，训练语料中大量的事件N(k)=0，这显然没有反映真实情况。我们把这个问题称为数据稀疏问题。这种零值的概率估计会导致语言模型算法的失败，例如：概率值作为乘数会使结果为0，而且不能做log运算。计数等价类根据对称性原理，事件除了出现次数之外不应具有细节特征，即所有具有相同计数r=N(k)的事件k（事件出现的次数称为事件的计数）应当具有相同的概率估计值，这些计数相同的事件称为计数等价，将它们组成的一个等价类记为计数等价类Gr。对于计数为r的计数等价类，定义nr为等价类中成员的个数，pr为等价类中事件的概率，R是最大可能出现的计数次数，则交叉检验交叉检验就是把训练样本分为m份，其中一份作为保留部分，其余m-1份作为训练部分。训练部分作为训练集估计概率pr，保留部分作为测试集进行测试。我们使用Cr表示保留部分中计数为r的计数等价类的观察个数。对于保留部分使用最大似然法对进行概率pr进行估计，即使对数似然函数最大化：使用拉格朗日乘子解决约束条件下的最大值问题，即：对pr求偏导，得到交叉检验估计：如果测试部分也作为保留部分的话，就是典型的极大似然估计：留一估计留一方法是交叉检验方法的扩展，基本思想是将给定N个样本分为N-1个样本作为训练部分，另外一个样本作为保留部分。这个过程持续N次，使每个样本都被用作过保留样本。优点：充分利用了给定样本，对于N中的每个观察，留一法都模拟了一遍没有被观察到的情形。对于留一方法，pr的极大似然估计为：Turing-Good公式因为nRpR与1相比一般可以忽略，留一估计公式可以近似为：留一估计可以利用计数r=1的事件来模拟未现事件，对于未现事件有如下估计：这个公式就是著名的Turing-Good公式。空等价类留一估计中要求么个nr均不为0，在实际问题中当r=5时，这个要求通常都不能满足，即计数等价类G1,…,GR中存在空的等价类。这时按照出现次数进行排序：对应的出现r(l)次的事件的个数记为nr(l)，在进行留一估计时，使用下一个非空的等价类Gr(l+1)代替可能为空的等价类Gr(l)+1，留一估计公式变为：式中对空的等价类没有估计概率，因为空等价类并没有对应任何有效事件。Turing-Good估计的优缺点和适用范围缺点：(1)无法保证概率估计的“有序性”，即出现次数多的事件的概率大于出现次数少的事件的概率。(2)pr与r/N不能很好地近似，好的估计应当保证pr=r/N。优点：其它平滑技术的基础。适用范围：对0r6的小计数事件进行估计。约束留一估计单调性约束：pr-1=pr；折扣约束：p=r/N。约束留一估计：让计数估计r*=pr•N处于距其最近的绝对频数之间：在这个约束下，单调性约束自然满足。计算方法：计算m时检查每个pr是否满足约束，不然就用约束的上下界进行裁剪，然后重新计算m，一直迭代下去直到所有pr满足约束。折扣模型Katz指出Turing-Good公式实质是对模型中观察到的事件进行折扣，将折扣得来的概率摊到所n0个未现事件中。在这个思想的指导下，估计公式可以下成如下形式：其中，dr是对计数为r的事件的计数的一个折扣函数。绝对折扣模型若折扣函数定义为：dr=b，其中b为一个大于0的常数。那么未现事件的总概率为：对应绝对折扣模型的估计公式为：线性折扣模型若折扣函数定义为：dr=a·r，其中a为一个大于0的常数。那么未现事件的总概率为：对应线性折扣模型的估计公式为：若a=n1/N，则n0p0=n1/N，与Turing-Good估计相同。删除插值法（DeletedInterpolation）其基本思想是，由于N-Gram比N+1-Gram出现的可能性大的多，所以使用N-Gram估计N+1-Gram的概率，例如trigram的计算公式如下：其中，参数l的确定：将训练数据分为两部分，一部分用于估计f(wi|w1w2…wi-1)，一部分用于计算参数l，求使语言模型的困惑度最小的l。