N-Gram

N-Gram（N 元模型）是自然语言处理中一个非常重要的概念，通常在 NLP 中，人们基于一定的语料库，可以利用 N-Gram 来评估一个句子是否合理。N-Gram 的另外一个作用是用来评估两个字符串之间的差异程度，这是模糊匹配中常用的一种手段。本文将从此开始，进而向读者展示 N-Gram 在自然语言处理中的各种 Powerful 的应用

基于 N-Gram 模型定义的字符串距离
利用 N-Gram 模型评估语句是否合理
使用 N-Gram 模型时的数据平滑算法

基于 N-Gram 模型定义的字符串距离

在自然语言处理中，最常用也是最基础的一个操作就是 “模式匹配”，或者称为 “字符串查找”。而模式匹配又分为精确匹配和模糊匹配两种

精确匹配，大家并不陌生，比如我们要统计一篇文章中关键词 infomation 出现的次数，这时所用的方法就是精确匹配。这方面算法也很多，例如 KMP 算法、BM 算法等

模糊匹配，它的应用也随处可见。一般的文字处理软件（Word 等）都会提供拼写检查的功能，当你输一个错误的单词，例如 informtaion，系统会提示你要输入的词是否其实是 information。将一个可能拼错的单词映射到一个推荐的正确拼写上，采用的技术就是模糊匹配

模糊匹配的关键在于如何衡量两个长得很像的单词（或字符串）之间的 “差异”。这种差异通常又称为 “距离”。这方面的算法有很多，甚至于在 LeetCode 上也有一道题 No.72 Edit Distance

首先介绍一下如何利用 N-Gram 来定义字符串之间的距离。假设有一个字符串 $s$，那么该字符串的 N-Gram 就表示按长度 N 切分原词得到的词段，也就是 $s$ 中所有长度为 N 的子字符串。设想如果有两个字符串，然后分别求它们的 N-Gram，那么就可以从它们公有字串的数量这个角度去定义两个字符串间的 N-Gram 距离。但是仅仅是简单地对公有子串进行计数显然也存在不足，这种方案显然忽略了两个字符串长度差异可能导致的问题。比如字符串 girl 和 girlfriend，二者所拥有的公共子串数量显然与 girl 和其自身所拥有的公共子串数量相等，但是我们并不能据此认为 girl 和 girlfriend 是两个等同的匹配

为了解决该问题，有学者提出以非重复的 N-Gram 分词为基础来定义 N-Gram 距离这一概念，具体公式如下：

$$ |G_N(s)|+|G_N(t)|-2\times |G_N(s)\cap G_N(t)| $$

其中，$|G_N (s)|$ 表示字符串 s 的 N-Gram 集合内元素的个数，N 值一般取 2 或者 3。以 N=2 为例对字符串 Gorbachev 和 Gorbechyov 进行分段。得到如下结果（下划线标出了其中的公共子串）

结合上面的公式，即可算出两个字符串之间的距离是 8+9-2*4=9，显然，字符串之间的距离越近，这个值就越小。当两个字符串完全相等的时候，它们之间的距离就是 0

利用 N-Gram 模型评估语句是否合理

从现在开始，我们所讨论的 N-Gram 模型跟前面所讲过的 N-Gram 模型从外在来看已经大不相同，但请注意它们内在的联系（或者说本质上仍是统一的概念）

为了引入 N-Gram 的应用，我们首先从几个例子开始

首先，从统计的角度来看，自然语言中的一个句子 $s$ 可以由任何词串构成，不过概率 $P (s)$ 有大有小罢了。例如：

$s_1=$ 我刚吃过晚饭
$s_2=$ 刚我吃过晚饭

显然，对于中文而言 $s_1$ 相较于 $s_2$ 来说，更通顺且有意义，因此 $P (s_1)>P (s_2)$

其次，另一个例子是，如果我们给出了某个句子的一个节选，我们其实可以能够猜出后续的词应该是什么，例如

the large green ___.
Kate swallowed the large green ___.

显然，如果我们知道这个句子片段更多前面内容的情况下，我们会得到一个更加准确的答案。这就告诉我们，历史信息越多，对后面未知信息的约束就越强

如果有们有一个由 $m$ 个词组成的序列（或者说一个句子），我们希望算得概率 $P (w_1,w_2,...w_m)$，根据条件概率乘法公式可得

$$ P(w_1,w_2,...,w_m)=P(w_1)P(w_2|w_1)P(w_3|w_1,w_2)···P(w_m|w_1,..,w_{m-1}) $$

这个概率显然不好算，不妨利用马尔科夫链的假设，即当前这个词仅跟前面几个有限的词相关，因此也就不必追溯到最开始的那个词，这样便可以大幅缩减上诉算式的长度。即

$$ P(w_i|w_1,...,w_{i-1})=P(w_i|w_{i-n+1},...,w_{i-1}) $$

特别地，对于 n 取得较小值的情况

当 $n=1$，一元模型（unigram model）即为

$$ P(w_1,w_2,...,w_m)=\prod_{i=1}^m P(w_i) $$

当 $n=2$，二元模型（bigram model）即为

$$ P(w_1,w_2,...,w_m)=\prod_{i=1}^m P(w_i|w_{i-1}) $$

当 $n=3$，三元模型（trigram model）即为

$$ P(w_1,w_2,...,w_m)=\prod_{i=1}^m P(w_i|w_{i-2}w_{i-1}) $$

接下来的思路就比较明确了，可以利用最大似然估计法来求出一组参数，使得训练样本的概率取得最大值

对于 unigram model 而言，$C (w_1,...,w_n)$ 表示 N-Gram $w_1,...,w_n$ 在训练语料中出现的次数（Count），$M$ 是语料中的总字数（例如对于 yes no no no yes 而言，$M=5$）

$$ P(w_i)=\frac{C(w_i)}{M} $$

对于 bigram model 而言

$$ P(w_i|w_{i-1})=\frac{C(w_{i-1}w_i)}{C(w_{i-1})} $$

对于 N-Gram model 而言

$$ P(w_i|w_{i-n-1},...,w_{i-1})=\frac{C(w_{i-n-1},...,w_i)}{C(w_{i-n-1},...,w_{i-1})} $$

下面看一个具体的例子，假设现在有一个语料库，其中 <s> 是句首标记，</s > 是句尾标记

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

部分的 bigram 模型计算结果如下所示：

$$ \begin{aligned} P(\text{I}|\text{<s>}) &= \frac{2}{3} \\ P(\text{Sam}|\text{<s>}) &= \frac{1}{3} \\ P(\text{Sam}|\text{am}) &= \frac{1}{2} \end{aligned} $$

再举个例子，有一个语料库，其中 $C (w_i)$ 如下

同时，下面这个概率作为已知条件给出：

$$ \begin{aligned} P(\text{I}|\text{<s>})&=0.25 \\ P(\text{</s>}|\text{food})&=0.68 \end{aligned} $$

$C (w_{i-1},w_i)$ 如下：

其中第一行，第二列表示给定前一个词是 "i" 时，当前词为 "want" 的情况一共出现了 827 次。据此，我们便可以算得相应的 bigram 分布为

因为我们从第一张表中知道 "I" 一共出现了 2533 次，而其后出现 "want" 的情况一共有 827 次，所以 $P (\text {want}|\text {I})=\frac {827}{2533}\approx 0.33$

那么，句子 <s> I want chinese food </s> 的 bigram 概率为

$$ \begin{aligned} P(\text{<s>}\ \text{I}\ \text{want}\ \text{chinese}\ \text{food}\ \text{</s>}) &= P(\text{I}|\text{<s>}) \\ & \times P(\text{want} | \text{I}) \\ & \times P(\text{chinese}|\text{want}) \\ & \times P(\text{food} | \text{chinese}) \\ & \times P(\text{</s>}|\text{food}) \\ &= 0.000189618 \end{aligned} $$

为了避免数据溢出、提高性能，通常会使用取 log 后转为加法运算代替乘法运算

$$ \log(p_1*p_2*p_3*p_4)=\log(p_1)+\log(p_2)+\log(p_3)+\log(p_4) $$

使用 N-Gram 模型时的数据平滑算法

有研究人员用 150 万词的训练语料来训练 trigram 模型，然后用同样来源的测试语料做验证，结果发现 23% 的 trigram 没有在训练语料中出现过。这就意味着有些概率为 0，导致了数据稀疏的可能性，上面第三张表中也确实有些为 0 的情况。对语言而言，由于数据稀疏的存在，极大似然估计法就不是一种很好的参数估计方法了

此时的解决办法，我们称之为” 平滑技术 “（Smoothing）。其基本思想是 “降低已出现 N-Gram 条件概率分布，以使未出现的 N-Gram 条件概率分布非零，且经数据平滑后一定保证概率和为 1，详细如下：

1. Add-one (Laplace) Smoothing

加一平滑法，又称拉普拉斯定律，其保证每个 N-Gram 在训练语料中至少出现 1 词次，以 bigram 为例，公式如下：

Add-1 estimate：$P_{\text {Add-1}}(w_i|w_{i-1})=\frac {C (w_{i-1},w_i)+1}{C (w_{i-1})+V}$，其中，V 是所有 bigram 的个数

承接上面的例子，经过 Add-one Smoothing 后，$C (w_{i-1},w_i)$ 如下所示：

则 bigram 为：

再例如，对于句子 <s> the rat ate the cheese </s>，我们可以来试着计算一下经 Add-one 平滑后的 $P (\text {ate}|\text {rat})$ 以及 $P (\text {ate}|\text {cheese})$，即

$$ \begin{aligned} P(\text{ate}|\text{rat}) &= \frac{C(\text{rat}\ \text{ate})+1}{C(\text{rat})+V} = \frac{2}{6} \\ P(\text{ate}|\text{cheese}) &= \frac{C(\text{cheese}\ \text{ate})+1}{C(\text{cheese}) + V} = \frac{1}{6} \end{aligned} $$

总结一下 Add-one Smoothing：

训练语料中未出现的 N 元组概率不再为 0，而是一个大于 0 的较小的概率值
由于训练语料中出现 N 元组数量太多，平滑后，所有未出现的 N 元组占据了整个概率分布很大的比例。因此，在 NLP 中，Add-one 给训练预料中没有出现过的 N 元组分配了太多的概率空间
在训练语料中出现的那些 N 元组，都增加同样的频度，这不太公平。经过平滑后所有未出现的 N 元组概率都相等，这也不太合理

2.Good-Turing Smoothing

基本思想：用观察计数较高的 N-Gram 数量来重新估计概率量的大小，并把它指派给那些具有零计数或较低计数的 N-Gram

一般情况下，我们选出现过一次的概率，也就是 Things seen once 这一概念：

Things seen once：使用刚才已经看过一次的事物的数量来帮助估计从来没有见过的事物的数量。举个例子，假设你在钓鱼，然后抓了 18 条鱼，种类如下：10 carp, 3 perch, 2 whitefish, 1 trout, 1 salmon, 1 eel，那么

下一条鱼是 trout 的概率是多少？很简单，我们认为是 1/18

下一条鱼是新品种的概率是多少？不考虑其他，那么概率是 0，然而根据 Things seen once 来估计新事物，概率是 3/18

下一条鱼是 trout 的概率是多少？在 Good Turing 下，对每一个频数 $c$，我们做一个调整，变为 $c^*$，公式如下，其中 $n_c$ 表示出现过 $c$ 次的 N-Gram

$$ c^*=(c+1)\frac{n_{c+1}}{n_c},\ \text{where}\ n_c=\sum_{b:C(b)=c}1 $$

然后计算 $P_{GT}$

$$ P_{GT}(x:c(x)=c)=\frac{c^*}{N} $$

对于这个例子，$c^*(\text {trout})=2*\frac {1}{3}=\frac {2}{3}$，$P_{GT}(\text {trout})=\frac {2/3}{18}=\frac {1}{27}$，因此下一条鱼是 trout 的概率是 $\frac {1}{27}$

Katz 所做的改进：Katz 认为，实际上，并非对于所有的频数 $c$ 都使用平滑频数 $c^*$ 是可靠的，假定对较大的频数是可靠的（对于某个阈值 $k,c>k$），他建议取 $k$ 的值为 5，即：

$$ c^*=\frac{(c+1)\frac{N_{c+1}}{N_c}-c\frac{(k+1)N_{k+1}}{N_1}}{1-\frac{(k+1)N_{k+1}}{N_1}}, 1\leq c \leq k $$

3.Backoff

通常我们会认为高阶模型更加可靠，当能够获知更多历史信息时，其实就获得了当前推测的更多约束，这样就更容易得出正确的结论。所以在高阶模型可靠时，尽可能使用高阶模型。但是有时候高阶模型的计数结果可能为 0，这时我们就转而使用低阶模型来避免稀疏数据的问题。公式如下：

$$ P_{\text{backoff}}(w_i|w_{i-n+1,...,w_{i-1}})= \begin{cases} P^*(w_i|w_{i-n+1},...,w_{i-1}), \quad\text{if} \ C(w_{i-n+1,...,w_i})>0\\ \alpha(w_{i-n+1},...,w_{i-1})\times P_{\text{backoff}}(w_i|w_{i-n+2},...,w_{i-1}), \quad\text{otherwise}\\ \end{cases} $$

其中 $\alpha$ 和 $P^*$ 是归一化因子，以保证 $\sum P_{\text {backoff}}=1$

4.Interpolation Smoothing

不管是 Add-one 还是 Good Turing 平滑技术，对于未出现的 N-Gram 都一视同仁，难免存在不合理（事件发生的概率存在差别），所以这里再介绍一种线性插值平滑技术，其基本思想是将高阶模型和低阶模型作线性组合，利用低元 N-Gram 模型对高元 N-Gram 模型进行线性插值，因为在没有足够的数据对高元 N-Gram 模型进行概率估计时，低元 N-Gram 模型通常可以提供有用的信息。

设想对于一个 trigram 模型，我们要统计语料库中 like chinese food 出现的次数，结果发现它没出现过，则计数为 0

公式如下：

$$ \begin{aligned} \hat P(w_n|w_{n-1}w_{n-2}) &=\lambda_1P(w_n|w_{n-1}w_{n-2}) \\ &+\lambda_2P(w_n|w_{n-1}) \\ &+\lambda_3P(w_n) \end{aligned} $$

其中 $0\leq \lambda_i\leq 1,\sum_i \lambda_i=1$。$\lambda_i$ 可以根据试验凭经验设定，也可以通过应用某些算法确定，例如 EM 算法

5.Absolute Discounting

想想之前的 Add-one 算法，本上说其实是将一些频繁出现的 N-Gram 的概率匀出一部分，分给那些没有出现的 N-Gram 上。因为所有可能性的概率之和等于 1，所以我们只能在各种可能的情况之间相互腾挪这些概率

既然我们打算把经常出现的拿一血 N-Gram 概率分一些出来，其实也就等同于将它们出现的次数减去（Discount）一部分，那到底改 discount 多少呢？Church&Gale（1991）设计了一种非常巧妙的方法。首先他们在一个留存语料库（held-out corpus）考察那些在训练集中出现了 4 词的 bigram 的个数。具体来说，他们首先在一个同样有 2200 万词的留存语料库中检索出所有出现了 4 次的 bigrams（例如：chinese food, good boy, want to 等），然后再从一个同样有 2200 万词的训练集中，分别统计这些 bigrams 出现的次数（假设 $C (\text {chinese}\ \text {food}) = 4, C (\text {good}\ \text {boy}) = 3, C (\text {want}\ \text {to}) = 3$）。最终，平均下来，他们发现：在第一个 2200 万词的语料库中出现 4 次的 bigrams，在第二个 2200 万词的语料库中出现了 3.23 次。下面这张表给出了 c 从 0 到 9 取值时（也就是出现了 c 次），统计的 bigrams 在留存集和训练集中出现的次数

很容易发现规律，出了计数为 0 和 1 的 bigram 之外，held-out set 中的平均频数值，都大约相当于 training set 中的计数值减去 0.75

基于上面这个实验结果所诱发的直接，Absolute discouting 会从每一个频数中减去一个（绝对的）数值 $d$。这样做的道理就在于，对于出现次数比较多的频数，我们已经得到了一个相对比较好的估计，那么当我们从这个计数值中减去一个较小的数值 $d$ 后应该影响不大。上面的实验结果暗示在实践中，我们通常会对从 2 到 9 的频数进行处理

$$ P_{\text{AbsDiscount}}(w_i|w_{i-1})=\frac{C(w_{i-1}w_i)-d}{C(w_{i-1})}+\lambda(w_{i-1})P(w_i) $$

6.Kneser-Ney Smoothing

这种算法目前是一种标准的、非常先进的平滑算法，由于这个算法比较复杂，我们从一个直观上的例子开始

假设我们使用 bigram 和 unigram 的插值模型来预测下面这个句子中空缺的词应该填什么

I used to eat Chinese food with _ instead of knife and fork

直觉上你一定能猜到这个地方应该填 chopsticks（筷子）。但是有一种情况是训练语料库中，Zealand 这个词出现的频率非常高，因为 New Zealand 是语料库中高频词。如果你采用标准的 unigram 模型，那么显然 Zealand 会比 chopsticks 具有更高的权重，所以最终计算机会选择 Zealand 这个词（而非 chopsticks）填入上面的空格，尽管这个结果看起来相当不合理。但这其实就暗示我们应该调整一下策略，最好当且仅当前一个词是 New 时，我们才给 Zealand 赋一个较高的权值，否则尽管在语料库中 Zealand 也是高频词，但我们并不打算单独使用它

如果说 $P (w)$ 衡量了 $w$ 这个词出现的可能性，那么我们现在想创造一个新的 unigram 模型，叫做 $P_{\text {continuation}}$，它的意思是将 $w$ 这个词作为一个新的接续的可能性。注意这其实暗示我我们要考虑前面一个词（即历史）的影响。或者说，为了评估 $P_{\text {continuation}}$（注意这是一个 unigra 模型），我们其实需要考察使用了 $w$ 这个词生成的不同 bigram 的数量。注意这里说使用了 $w$ 这个词生成的不同类型 bigram 的数量，是指当前词为 $w$，而前面一个词不同时，就产生了不同的类型。例如：$w=\text {food}$，那么不同的 bigram 类型就可能包括 "chinese food"，"english food"，"japanese food" 等。每一个 bigram 类型，当我们第一次遇到时，就视为一个新的接续（novel continuation）

也就是说 $P_{\text {continuation}}$ 应该同所有新的接续（novel continuation）构成的集合之势成比例。所以，可知

$$ P_{\text{continuation}}(w_i)\propto |w_{i-1}:C(w_{i-1}w_i)>0| $$

如果你对此尚有困惑，我再来解释一下上面这个公式的意思。当前词是 $w_i$，例如 food，由此构成的不同类型的 bigram 即为 $w_{i-1} w_i$，其中 $w_{i-1}$ 表示前一个词（preceding word）。显然，所有 $w_{i-1} w_i$ 构成的集合的势，其实就取决于出现在 $w_i$ 之前不同的 $w_{i-1}$ 的数量

然后，为了把上面这个数变成一个概率，我们需要将其除以一个值，这个值就是所有 bigram 类型的数量，即 $|\{(w_{j-1},w_j):C (w_{j-1},w_j)>0\}|$，这里大于 0 的意思就是 “出现过”。于是有

$$ P_{\text{continuation}(w_i)}=\frac{|\{w_{i-1}:C(w_{i-1}w_i)>0\}|}{|\{(w_{j-1},w_j):C(w_{j-1},w_j)>0\}|} $$

当然，我们还可以采用下面这种等价形式

$$ P_{\text{continuation}(w_i)}=\frac{|\{w_{i-1}:C(w_{i-1}w_i)>0\}|}{\sum_{w^{'}_i}|\{w_{i-1}^{'}:C(w_{i-1}^{'}w_i^{'})>0\}|} $$

即所有不同的 bigram 的数量就等于出现在单词 $w_i^{'}$ 前面所有不同的词 $w_{i-1}^{'}$ 的数量

如此一来，一个仅出现在 New 后面的高频词 Zealand 只能获得一个较低的接续概率（continuation probability）。由此，再结合前面给出的 Absolute Discounting 的概率计算公式，就可以得出插值的 Kneser-Ney Smoothing 公式，即

$$ P_{KN}(w_i|w_{i-1})=\frac{\max(C(w_{i-1}w_i)-d, 0)}{c(w_{i-1})}+\lambda(w_{i-1})P_{\text{continuation}}(w_i) $$

其中，$\max (C (w_{i-1} w_i)-d,0)$ 的意思是要保证最后的频数在减去一个 $d$ 之后不会变成负数。其次，我们将原来 $P (w_i)$ 替换成了 $P_{\text {continuation}}(w_i)$。此外，$\lambda$ 是一个正则化常量，用于分配之前 discount 的概率值（也就是从高频词中减去的，准备分给那些未出现的低频词的概率值）

$$ \lambda(w_{i-1})=\frac{d}{C(w_{i-1})}·|\{w:C(w_{i-1},w)>0\}| $$

如果用递归的方式重写出一个更加普适的泛化公式则有：

$$ P_{KN}(w_i|w_{i-n+1},...,w_{i-1})=\frac{\max(0, C_{KN}(w_{i-n+1},...,w_i)-d)}{C_{KN}(w_{i-n+1},...,w_{i-1})}+\lambda(w_{i-n+1},...,w_{i-1})·P_{KN}(w_i|w_{i-n+2},...,w_{i-1}) $$

其中

$$ \lambda(w_{i-n+1},...,w_{i-1})=\frac{d}{C_{KN}(w_{i-n+1},...,w_{i-1})}·|\{w:C_{KN}(w_{i-n+1},...,w_{i-1})>0\}| $$

由于采用了上述这种递归写法，我们需要定义一个计数函数 $C_{KN}$，它取决于在插值组合中的各阶 N-GRam 处于哪个层级。例如，假设我们现在所使用的插值模型是 trigram，bigram 和 unigram 的组合，那么对于最高阶的 trigram 在计数时并不需要使用接续计数（采用普通计数即可），而其他低阶，即 bigram 和 unigram 则需要使用接续计数。这是因为在 unigram 中，我们遇到了一个 Zealand，我们可以参考它的 bigram，同理在 bigram，我们还可以再参考它的 trigram，但是如果我们的插值组合中最高阶就是 trigram，那么现在没有 4-gram 来给我做接续计数。用公式表示即为：

$$ C_{KN}(\cdot)=\begin{cases}\text{count}(\cdot) ,\quad \text{for}\ \text{the}\ \text{highest}\ \text{order}\\ \text{continuation count}(\cdot),\quad \text{for}\ \text{all}\ \text{other}\ \text{lower}\ \text{orders} \end{cases} $$

关于 Smoothing 就介绍到这里，有兴趣的读者可以查阅相关资料以了解更多