N-Gram Model

  在介绍N-gram模型之前,让我们先来做个香农游戏。我们给定一个词,然后猜测下一个词是什么。当我说“艳照门”这个词时,你想到下一个词是什么呢?我想大家很有可能会想到“陈冠希”,基本上不会有人会想到“刘德华”吧。N-gram模型的主要思想就是这样的。

  对于一个句子 T,我们怎么算它出现的概率呢?

  假设 T 是由词序列 W1,W2,W3,…Wn 组成的,那么 P(T)=P(W1W2W3…Wn)=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) 呢?一种简单的估计方法就是最大似然估计 (Maximum Likelihood Estimate)了。即 P(Wn|W1W2…Wn-1) = (C(W1 W2…Wn))/(C(W1 W2…Wn-1)),剩下的工作就是在训练语料库中数数儿了,即统计序列 C(W1 W2…Wn)  出现的次数和 C(W1 W2…Wn-1) 出现的次数。

  下面我们用 bigram 举个例子。假设语料库总词数为13748词

捕获

  P(I want to eat Chinese food) =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.000154171

  这里还有一个问题要说,那就是数据稀疏问题,假设词表中有20000个词,如果是 bigram 那么可能的 N-gram 就有400000000个,如果是 trigram,那么可能的 N-gram 就有8000000000000个!那么对于其中的很多词对的组合,在语料库中都没有出现,根据最大似然估计得到的概率将会是0,这会造成很大的麻烦,在算句子的概率时一旦其中的某项为0,那么整个句子的概率就会为0,最后的结果是,我们的模型只能算可怜兮兮的几个句子,而大部分的句子算得的概率是0。因此,我们要进行数据平滑(data Smoothing),数据平滑的目的有两个:一个是使所有的N-gram概率之和为1,使所有的N-gram概率都不为0。

  了解了噪声信道模型和 N-gram 模型的思想之后,其实我们自己就能实现一个音词转换系统了,它是整句智能输入法的核心,其实我们不难猜到,搜狗拼音和微软拼音的主要思想就是 N-gram 模型的,不过在里面多加入了一些语言学规则而已。

  转载自http://hi.baidu.com/bytechen/blog/item/94cf53def1d4ce5fcdbf1a40.html

发表评论

电子邮件地址不会被公开。 必填项已用*标注