N元语法

2020-08-21

字数统计: 1.4k字 | 阅读时长≈ 5分

$N$元语法

给定一个单词序列“Please turn your homework…”，我们把猜测下一个单词的问题采用 N元语法模型（N-gram model） 这样的概率模型来形式化描述。$N$元语法法模型是根据前面出现的$N-1$个单词猜测下面一个单词。一个$N$元语法是包含$N$个单词的序列：1 元语法（一般称为unigram）是包含 1 个单词的序列，2 元语法（一般称为bigram）是包含 2 个单词的序列，3 元语法（一般称为trigram）是包含 3 个单词的序列。一个$N$元语法模型是根据前面出现的单词计算后一个单词的模型，这种单词序列的概率模型又称为语言模型（LM）。

$N$元语法用处：

在噪声或者歧义的输入中辨认出单词；
机器翻译中，可以用于选择最通顺的译文；
在拼写中，可以用于发现并改正偶然的错误拼写；
词类标注、自然语言生成、单词相似度计算、匿名作者辨认、情感抽取，手机的预测式文本输入。

1. 简单的（非平滑的）$N$元语法

$N$元语法的目的是在给定了某个单词$w$的历史$h$的条件下，计算单词$w$的概率$P(w|h)$。假定历史$h$是“its water is so transparent that”，我们想知道这个历史$h$后面单词 the 的概率是多少：

$P(w=the|h=its\ water\ is \ so\ transparent\ that)$

怎样计算这个概率？有以下两种方法，一种是基于相对频率计算；另一种是基于单词序列的联合概率计算。

1.1 基于相对频率

我们通过它们在语料库出现的次数来计算，公式如下：

$h+w=its\ water\ is\ so\ transparent\ that\ the$ $P(w\ |\ h)=\frac{(h+w)在语料库中出现的次数}{h在语料库中出现的次数}$

1.2 给予单词序列的联合概率

我们用$ P(S)=P(w_1,w_2,\ldots,w_n) $来描述单词序列$S=(w_1,w_2,\ldots,w_n)$的概率：

$\begin{aligned} P(w_1,w_2,\ldots,w_n)&=P(w_1)P(w_2|w_1)P(w_3|w_1,w_2)\ldots P(w_n|w_1,w_2,\ldots,w_{n-1})\\ &=\prod_{i=1}^nP(w_i|w_1,w_2,\ldots,w_{i-1}) \end{aligned}$

当单词序列很长时，很难计算。所以，在计算某个单词的概率时，不是考虑他前面的全部历史，而是考虑最接近该单词的若干个单词，从而近似逼近该单词的历史。这就是$N$元语法模型的直觉解释。例如，我们只通过前面一个单词的条件概率$P(w_n|w_{n-1})$来逼近前面给定的所有单词的概率$P(w_n|w_1,w_2,\ldots,w_{n-1})$，这就是二元语法模型（bigram model），如下公式

$P(w=the|h=its\ water\ is \ so\ transparent\ that)\approx P(w=the|h=that)$

一个单词的概率只依赖于它前面单词的概率这种假设称为马尔可夫假设（Markov assumption）

推广到 $N$元语法模型（看过去的$N-1$个单词），这样一来，在一个序列中，$N$元语法对于下一个单词的条件概率逼近的通用公式是：

$P(w_n|w_1,w_2,\ldots,w_{n-1})\approx P(w_n|w_{n-N+1},w_{n-N+2},\ldots,w_{n-1})$

对于二元语法，只考虑前面一个单词的概率，则整个单词序列的概率是：

$P(w_1,w2,\ldots,w_n)\approx \prod_{i=1}^nP(w_i|w_{i-1})$

计算二元或$N$元语法的概率：
估计这种概率最简单和最直观的方法是最大似然估计（Maximum Likelihood Estimation，MLE），可以把从语料库得到的计数归一化，从而得到$N$元语法模型参数的MLE估计，进行归一化后，概率都处于0和1之间。

为了计算前面单词是$x$的条件下，单词$y$的二元语法概率，我们就要取第一个单词为$x$的所有二元语法$C(xy)$的计数（count，即出现次数），然后用第一个单词为$x$的所有二元语法的总数(即$x$出现的次数)作为除数来除这个计数，从而进行归一化：

$P(w_n|w_{n-1})=\frac{C(w_{n-1}w_n)}{\sum_wC(w_{n-1}w)}=\frac{C(w_{n-1}w_n)}{C(w_{n-1})}$

注意： 对于句子开头和结尾，如果采用$N$元语法，那么需要在句子开头添加$N-1$个特殊符号（如\和\），使得句子开头和结尾的单词具有$N$元语法的上下文。

如以下语料库：

1
2
3

<s> I am Sam </s>
<s> Sam I am </s>
<s> I do not like green eggs and ham </s>

根据这个语料库，可以得到如下二元语法概率计算的一些结果：

P(I|<s>)=\frac{2}{3}=0.67
P(Sam|<s>)=\frac{1}{3}=0.33 
P(am|I)=\frac{2}{3}=0.67
P(</s>|Sam)=\frac{1}{2}=0.5
P(Sam|am)=\frac{1}{2}=0.5
P(do|I)=\frac{1}{3}=0.33

推广到$N$元语法，MLE参数估计公式如下：

$P(w_n|w_{n-N+1},w_{n-N+2},\ldots,w_{n-1})==\frac{C(w_{n-N+1}\cdots w_{n-1}w_n)}{C(w_{n-N+1}\cdots w_{n-1})}$

本文作者： 程序猪-渔枫
本文链接： https://over-shine.github.io/2020/08/21/N元语法/
版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！