NLP中的N-gram模型

nlp 笔记

阅读资料：自然语言处理NLP中的N-gram模型述

1. Naive Bayes

首先我们复习一下一个非常基本的模型，朴素贝叶斯（Naive Bayes）。朴素贝叶斯的关键组成是贝叶斯公式与条件独立性假设。为了方便说明，我们举一个垃圾短信分类的例子。

"在家日赚百万，惊人秘密..."

上面这句话抄自我手机中的一条垃圾短信，自从去过澳门，手机就时不时收到这样的关于赌场的短信。朴素贝叶斯模型就是要衡量这句话属于垃圾短信敏感句子的概率，我们以前半句为例：
$$\begin{align*} P(垃圾邮件|“在家日赚百万”) \propto P(垃圾邮件)P(“在家日赚百万”|垃圾邮件) \end{align*}$$
由条件独立性假设：
$$\begin{align*} P(“在家日赚百万”|垃圾邮件) & = P(“在”, “家”, “日”, “赚”, “百”, “万”|垃圾邮件) \\& = P(“在”|垃圾邮件) \times P(“家”, 垃圾邮件) \times...\times P(“万”, 垃圾邮件) \end{align*}$$

上面每一项条件概率都可以通过在训练数据的垃圾短信中统计每个字出现的次数得到，然而这里有一个问题，朴素贝叶斯将句子处理为一个词袋模型（Bag-of-Words, BoW），以至于不考虑每个单词的顺序。这一点在中文里可能没有问题，因为有时候即使把顺序捣乱，我们还是能看懂这句话在说什么，但有时候不行，例如：

"我烤面筋" ≠ 面筋烤我

那么有没有模型是考虑句子中单词之间的顺序的呢？有，N-gram就是。

2. N-gram

在介绍N-gram之前，让我们回想一下“联想”的过程是怎样发生的。如果你是一个玩LOL的人，那么当我说“正方形打野”、“你是真的皮”，“你皮任你皮”这些词或词组时，你应该能想到的下一个词可能是“大司马”，而不是“五五开”。如果你不是LOL玩家，没关系，当我说“上火”、“金罐”这两个词，你能想到的下一个词应该更可能“加多宝”，而不是“可口可乐”。

N-gram正是基于这样的想法，它的第一个特点是某个词的出现依赖于其他若干个词，第二个特点是我们获得的信息越多，预测越准确。我想说，我们每个人的大脑中都有一个N-gram模型，而且是在不断完善和训练的。我们的见识与经历，都在丰富着我们的阅历，增强着我们的联想能力。

N-gram模型是一种语言模型（Language Model，LM），语言模型是一个基于概率的判别模型，它的输入是一句话（单词的顺序序列），输出是这句话的概率，即这些单词的联合概率（joint probability）。

N-gram本身也指一个由$N$个单词组成的集合，各单词具有先后顺序，且不要求单词之间互不相同。常用的有 Bi-gram ($N=2$) 和 Tri-gram ($N=3$)，一般已经够用了。例如在上面这句话里，我可以分解的 Bi-gram 和 Tri-gram ：

Bi-gram: {I, love}, {love, deep}, {deep, learning}
Tri-gram: {I, love, deep}, {love, deep, learning}

3. N-gram中的概率

3.1 LM的概率

假设我们有一个由 $n$ 个词组成的句子$S=(w_{1},w_{2},⋯,w_{n})$，如何衡量它的概率呢？让我们假设，每一个单词 $w_{i}$ 都要依赖于从第一个单词 $w_{1}$ 到它之前一个单词 $w_{i−1}$的影响：

$$\begin{align*} P(S) = P(w_{1},w_{2},⋯,w_{n}) = P(w_{1})P(w_{2}|w_{1})⋯P(w_{n}|w_{n-1}⋯w_{2}w_{1}) \end{align*}$$

3.2 马尔科夫假设

是不是很简单？是的，不过这个衡量方法有两个缺陷：

• 参数空间过大：概率 $P(w_{n}|w_{n-1}⋯w_{2}w_{1})$ 的参数有 $O(n)$ 个。
• 数据稀疏严重：词同时出现的情况可能没有，组合阶数高时尤其明显。

为了解决第一个问题，我们引入马尔科夫假设（Markov Assumption）：一个词的出现仅与它之前的若干个词有关。

$$\begin{align*} P(w_{1},w_{2},⋯,w_{n}) & = \prod_{i=1}^{n} P(w_{i}|w_{i-1}⋯w_{2}w_{1}) \\& \approx \prod_{i=1}^{n} P(w_{i}|w_{i-1}⋯w_{i-N+1}) \end{align*}$$

• 如果仅依赖前一个词，则是Bi-gram：
  $$\begin{align*} P(S) = P(w_{1},w_{2},⋯,w_{n}) = P(w_{1})P(w_{2}|w_{1})⋯P(w_{n}|w_{n-1}) \end{align*}$$
• 如果仅依赖前两个词，则是Tri-gram：
  $$\begin{align*} P(S) = P(w_{1},w_{2},⋯,w_{n}) = P(w_{1})P(w_{2}|w_{1})P(w_{3}|w_{2}w_{1})⋯⋯P(w_{n}|w_{n-1}w_{n-2}) \end{align*}$$ N-gram的 $N$ 可以取很高，然而现实中一般Bi-gram和Tri-gram就够用了。

3.3 概率的计算

那么，如何计算其中的每一项条件概率$P(w_{n}|w_{n-1}⋯w_{2}w_{1})$呢？答案是极大似然估计（Maximum Likelihood Estimation，MLE），从数据集中可通过数频数得到。

• Bi-gram:
  

  $$\begin{align*} P(w_{n}|w_{n-1}) = \frac{C(w_{n-1}w_n)}{C(w_{n-1})} \end{align*}$$

• Tri-gram:
  

  $$\begin{align*} P(w_{n}|w_{n-2}w_{n-1}) = \frac{C(w_{n-2}w_{n-1}w_n)}{C(w_{n-2}w_{n-1})} \end{align*}$$

• N-gram:
  

  $$\begin{align*} P(w_{n}|w_{1}w_{2}⋯w_{n-2}w_{n-1}) = \frac{C(w_{1}w_{2}⋯w_{n-1}w_{n})}{C(w_{1}w_{2}⋯w_{n-2}w_{n-1})} \end{align*}$$

3.4 例子

具体地，以Bi-gram为例，我们有这样一个由三句话组成的语料库：

$“I”$出现了3次，$“I\ am”$出现了2次，因此能计算概率：

$$\begin{align*} P(am|I) = \frac{P(I,am)}{P(I)} = \frac{2}{3} \end{align*}$$

另外再提供一个《Language Modeling with Ngrams》中的例子，Jurafsky et al., 1994 从加州一个餐厅的数据库中做了一些统计：

可以计算$“I\ want\ chinese\ food”$这句话在当前语言模型中的概率：

$$\begin{align*} P(<s>I\ want\ chinese\ food<s>) & = P(<s>)P(I|<s>)P(want|I)P(chinese|want)P(food|chinese)P(<s>|food) \end{align*}$$

4. N-gram的用途

4.1 词性标注

N-gram可以实现词性标注。例如“爱”这个词，它既可以作为动词使用，也可以作为名词使用。不失一般性，假设我们需要匹配一句话中“爱”的词性。

我们可以将词性标注看成一个多分类问题，按照Bi-gram计算每一个词性概率：

$$\begin{align*} P(词性_i|前一个词“龙龙”的词性_j，当前文字“爱”) & = \frac{C(前一个词的词性为j，当前文字为“爱”且词性为i)}{C(前一个词的词性为j，当前文字为“爱”)} \end{align*}$$

通过对每种词性的概率计算，得到一个生成模型。最终选取概率更大的词性（比如动词）作为这句话中“爱”字的词性。

4.2 垃圾邮件分类

开头提到的那个垃圾短信分类问题，我们可以用N-gram来解决。在朴素贝叶斯的基础上，稍微对条件概率做一点改动即可。

$$\begin{align*} P(垃圾邮件|“在家日赚百万”) \propto P(垃圾邮件)P(“在家日赚百万”|垃圾邮件) \end{align*}$$

在N-gram模型下，各个特征(这里是文字)之间不再满足独立的条件，在Bi-gram下：

$$\begin{align*} P(“在家日赚百万”|J) & = P(“在”, “家”, “日”, “赚”, “百”, “万”|J) \\& = P(“在”|J) \times P(“家”|“在”, J) \times...\times P(“万”|“百”, J) \end{align*}$$
一个可实施的方案如下：

• 步骤一：给短信的每个句子断句。
• 步骤二：用N-gram判断每个句子是否垃圾短信中的敏感句子。
• 步骤三：若敏感句子个数超过一定阈值，认为整个邮件是垃圾短信。

4.3 分词器

在NLP中，分词的效果很大程度上影响着模型的性能，因此分词甚至可以说是最重要的工程。用N-gram可以实现一个简单的分词器（Tokenizer）。同样地，将分词理解为多分类问题：$X$ 表示有待分词的句子，$Y_i$ 表示该句子的一个分词方案。

$$\begin{align*} X = “我爱深度学习” \end{align*}$$

$$\begin{align*} \\Y_1 = \{“我”, “爱深”, “度学习”\} \\ Y_2 = \{“我爱”, “深”, “度学”, “习”\} \\Y_3 = \{“我”, “爱”, “深度学习”\} \end{align*}$$

$$\begin{align*} \\P(Y_1) = P(我)P(爱深|我)P(度学习|爱深) \\P(Y_2) = P(我爱)P(深|我爱)P(度学|深)P(习|度学) \\P(Y_3) = P(我)P(爱|我)P(深度学习|爱) \end{align*}$$

三个概率中，“我爱”可能在语料库中比较常见，因此$P(爱∣我)$ 会比较大，然而“我爱深”这样的组合比较少见，于是$P(爱深∣我)$和$P(深∣我爱)$都比较小，导致$P(Y_3)$比$P(Y_1)$和$P(Y_2)$都大，因此第三种分词方案最佳。

4.4 机器翻译和语音识别

• 机器翻译
  同一句话，可能有多种翻译方式，它们的区别仅在于单词的组合顺序，这时候使用N-gram分别计算各种情况的概率，选最大的那个即可。

• 语音识别
  同一种发音，可能被解析成不同的句子，然而其中有一种更符合语法规则。