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就介绍到这里，有兴趣的读者可以查阅相关资料以了解更多