N-Gram 模型

【概述】

N-Gram 模型是一种基于统计语言模型的算法，常用于预测一个文本中下一个单词出现的概率

其基本思想是将文本内容按词进行大小为 $N$ 的滑动窗口操作，形成长度是 $N$ 的词片段序列，每一个词片段被称为 gram，通过这种序列信息，来预测下一个项的出现概率

【基本思想】

概率计算

假设有一个由 $n$ 个词组成的句子 $S=(w_1,w_2,\cdots,w_n)$，每一个单词 $w_i$ 都依赖于从第 $w_1$ 个词到它前一个词 $w_{i-1}$ 的影响，整句的概率就是各个词出现概率的乘积，那么这个句子的概率为：

$$\begin{align*} P(S) &=p(w_1,w_2,\cdots,w_m) \\ &=p(w_1)p(w_2|w_1)\cdots p(w_n|w_{n-1}\cdots w_2w_1) \end{align*}$$

这种计算方法看上去十分简单，不过有两个缺陷：

1. 参数空间过大：概率 $p(w_1,w_2,\cdots,w_m)$ 的参数有 $O(n)$ 个
2. 数据稀疏严重：词的组合在语料库中的重复出现的概率极低，组合阶数高时尤为明显

马尔可夫假设的引入

对于第一个问题，引入马尔可夫假设（Markov Assumption），即一个词的出现仅与它之前的 $N$ 个词有关，称为 N-Gram

$$\begin{align*} p(w_1,w_2,\cdots,w_n) &= \prod_{i=1}^n p(w_i|w_{i-1}\cdots w_1) \\ &\approx \prod_{i=1}^n p(w_i|w_{i-1}\cdots w_{i-N+1}) \end{align*}$$

如果一个词的出现不依赖于它之前的词，即 $N=1$，那么就称为一元模型（Unigram Model），也称为上下文无关模型，此时有：

$$\begin{align*} P(S) &=p(w_1,w_2,\cdots,w_m) \\ &= \prod_{i=1}^n p(w_i) \\ &=p(w_1)p(w_2)\cdots p(w_n) \end{align*}$$

如果一个词的出现仅依赖于它之前的一个词，即 $N=2$，那么就称为二元模型（Bi-gram Model），此时有：

$$\begin{align*} P(S) &=p(w_1,w_2,\cdots,w_m) \\ &= \prod_{i=1}^n p(w_i|w_{i-1}) \\ &=p(w_1)p(w_2|w_1)\cdots p(w_n|w_{n-1}) \end{align*}$$

如果一个词的出现仅依赖于它之前的两个词，即 $N=3$，那么就称为三元模型（Tri-gram Model），此时有：

$$\begin{align*} P(S) &=p(w_1,w_2,\cdots,w_m) \\ &= \prod_{i=1}^n p(w_i|w_{i-2}w_{i-1}) \\ &=p(w_1)p(w_2|w_1)\cdots p(w_n|w_{n-1}w_{n-2}) \end{align*}$$

以此类推，$N$ 可以取很高，这一类模型即 N-Gram 模型

条件概率的计算

在引入马尔可夫假设后，对于 N-Gram，有：

$$\begin{align*} p(w_1,w_2,\cdots,w_n) &= \prod_{i=1}^n p(w_i|w_{i-1}\cdots w_1) \\ &\approx \prod_{i=1}^n p(w_i|w_{i-1}\cdots w_{i-N+1}) \end{align*}$$

此时问题的核心就是如何计算每一项的条件概率 $p(w_i|w_{i-1}\cdots w_2 w_1)$，由于整句的概率就是各个词出现概率的乘积，那么有：

$$p(w_i|w_{i-1}\cdots w_{i-N+1}) = \frac{C(w_1w_2\cdots w_i)}{C(w_1w_2\cdots w_{i-1})}$$

其中，函数 $C(*)$ 代表取参数 $*$​​ 的频数

可以发现，对于词袋法来说，其本质上就是一个 Uni-Gram 模型

实例

以 Bi-Gram 为例，假设有如下两句话组成的语料库：

S1: <s>I am Sam<s>
S2: <s>Sam I am<s>

容易统计，I 出现了 $2$ 次，I am 出现了 $2$ 次，因此能计算概率：

$$p(\text{am}|\text{I}) = \frac{1}{1} = 1$$

同理，可计算出：

$$\begin{matrix} p(\text{I}|\text{<s>}) = \frac{1}{4} & p(\text{Sam}|\text{am}) = \frac{1}{2} & p(\text{<s>}|\text{Sam}) = \frac{1}{2} \\ p(\text{Sam}|\text{<s>}) = \frac{1}{4} & p(\text{I}|\text{Sam}) = \frac{1}{2} & p(\text{<s>}|\text{am}) = \frac{1}{2} \\ \end{matrix}$$

那么，对于句子 $S_1$，有：

$$\begin{align*} p(S_1) &= p(\text{<s>I am Sam<s>}) \\ &= p(\text{I}|\text{<s>})p(\text{am}|\text{I})p(\text{Sam}|\text{am})p(\text{<s>}|\text{Sam}) \\ &= \frac{1}{4} \cdot \frac{1}{1}\cdot \frac{1}{2}\cdot \frac{1}{2} \\ &= \frac{1}{16} \end{align*}$$

同理，可计算出句子 $S_2$ 的概率为

$$p(S_2) = \frac{1}{16}$$

需要注意的是，当句子很长时，概率的相乘可能会造成数据下溢，即多个小于 $1$ 的常数相乘使得结果接近于 $0$，此时通常使用 $\log$​ 概率来解决

【N 的选取】

为确定 $N$ 的最佳取值，《Language Modeling with N-grams》 中，针对 Unigram、Bigram、Trigram 模型，计算各自的 Perplexity 指标，该指标越小说明一个语言模型的效果越好

$$\begin{align*} PP(S) &= \sqrt[n]{\frac{1}{p(w_1,w_2,\cdots,w_n)}} \\ &= \sqrt[n]{\frac{1}{\prod\limits_{i=1}^n p(w_i|w_{i-1}\cdots w_{i-N+1})}} \end{align*}$$

结果显示，Tri-Gram 的 Perplexity 最小，因此其效果也是最好的

【数据平滑方法】

稀疏问题

当 N-Gram 模型的 $N$ 取值越大时，Perplexity 越小，这在直观意义上是说得通的，即依赖的词越多，获得的信息量就越多

然而，随着 $N$ 的增大，词的组合在语料库中的概率极低，即之前提到的稀疏性问题

例如在 Bi-Gram 中，若词库中有 $20000$ 个单词，那么两两组合就有 $C_{20000}^2 = 199990000$ 种组合，计算大部分句子的概率时都将为 $0$，这显然是不合理的

为解决这种稀疏性问题，在计算条件概率时引入数据平滑（Data Smoothing），重新分配整个概率空间，使得已经出现的 N-Gram 的概率降低，补充给未曾出现过的 N-Gram

常见的数据平滑方法有内插法、回溯法、拉普拉斯平滑、add-K、Absolute Discounting、Kneser-Ney 平滑等，这里仅介绍最简单的两种

内插法

内插法（Interpolation）有点像滑动平均，其核心思想是：既然高阶组合可能出现次数为 $0$，那稍微低阶一点的组合总有不为 $0$ 的，因此利用低阶的组合来计算高阶组合的概率

例如，对于一个三阶组合 $p(w_{i}|w_{i-1}w_{i-2})=0$，有 $p(w_{i}|w_{i-1})>0$ 且 $p(w_i)>0$，那么加权平均后有：

$$\tilde{p}(w_{i}|w_{i-1}w_{i-2}) = \lambda_3 p(w_{i}|w_{i-1}w_{i-2}) + \lambda_2 p(w_{i}|w_{i-1}) + \lambda_1 p(w_i)$$

拉普拉斯平滑

拉普拉斯平滑（Laplacian Smoothing），是强制让所有的 N-Gram 至少出现一次，只需要在分子和分母上分别做加法即可，但由于大部分的 N-Gram 都是没有出现过的，该方法很容易为他们分配过多的概率空间

$$p(w_i|w_{i-1}\cdots w_{i-N+1}) = \frac{C(w_1w_2\cdots w_i)+1}{C(w_1w_2\cdots w_{i-1})+|V|}$$