2.2.2 N-Gram算法

联合概率链规则虽然考虑了所有词之间的依赖关系，但是随着词序列长度的增加，需要估计的参数数目也呈指数级增长，并且很难从训练数据中准确地计算，在实际中很难应用。为了解决参数空间过大的问题，会假设一个词出现的概率只依赖于它前面的n个词，这一假设称为马尔可夫假设。

引入马尔可夫假设后，词序列的概率P（S）可以表示为：

这就是N-Gram模型。

理论上来说，n越大，约束信息越多，模型就具有更大的辨别力。但是随着n的增大，参数数量也呈现指数级增长，参数空间过大，会产生维数灾难。同时，由于训练语料有限，也容易产生数据稀疏。n越小，统计信息更加可靠和实用。综合考虑，一般情况下，n的取值不会大于4。

1）当n=1时，即假设每个词的出现与周围的词独立，记作Unigram，也就是一元语言模型，即词袋模型。词序列的概率为：

2）当n=2时，即假设每个词的出现只与前一个词有关，记作Bigram，也就是二元语言模型，也叫一阶马尔可夫链。词序列的概率为：

其中每一项条件概率使用极大似然估计进行计算，即：

P（wi|wi-1）=C（wiwi-1）/C（wi-1）

其中，C表示词或词序列出现的频次。

3）当n=3时，即假设每个词的出现与其前面的两个词相关，记作Trigram，也就是三元语言模型，也叫二阶马尔可夫链。词序列的概率为：

其中每一项条件概率使用极大似然估计进行计算，即：

其中，C表示词或词序列出现的频次。

在实际计算过程中，对于句首词与句尾词的条件概率制造伪词进行计算。一般标记句首为〈S〉，句尾为〈E〉。

以Bigram为例，假设语料库为：

·文本1：〈S〉鼠标是计算机外设〈E〉。

·文本2：〈S〉键盘是计算机外设〈E〉。

·文本3：〈S〉触摸显示器是鼠标和键盘的替代〈E〉。

计算词序列S=（触摸显示器是计算机外设）的概率。

P（触摸|〈S〉）=C（〈S〉触摸）/C（〈S〉）=1/3；

P（显示器|触摸）=C（触摸显示器）/C（触摸）=1/1；

P（是|显示器）=C（显示器是）/C（显示器）=1/1；

P（计算机|是）=C（是计算机）/C（是）=2/3；

P（外设|计算机）=C（计算机外设）/C（计算机）=2/2；

P（〈E〉|外设）=C（外设〈E〉）/C（外设）=2/2。

因此P（S）=1/3*1*1*2/3*1*1=2/9。即从文本1、文本2、文本3得到的信息，序列S出现的概率为2/9。