NLP：n-gram
N-Gram
N-Gram（有时也称为N元模型）是自然语言处理中一个非常重要的概念。N-gram模型是一种语言模型（Language Model，LM），语言模型是一个基于概率的判别模型，它的输入是一句话（单词的顺序序列），输出是这句话的概率，即这些单词的联合概率。主要有两个重要应用场景：
（1）人们基于一定的语料库，可以利用N-Gram来预计或者评估一个句子是否合理。
（2）用来评估两个字符串之间的差异程度。这是模糊匹配中常用的一种手段。
习惯上，1-gram叫unigram，2-gram称为bigram，3-gram是trigram。还有four-gram、five-gram等，不过大于n>5的应用很少见。常用的是 Bi-gram (N = 2) 和 Tri-gram (N = 3)，一般已经够用了。
数学基础
①联合概率
P(A,B) ,表示的是A,B同时发生的概率.
1.1 当A,B相互独立时，也就是交集为空的时候，P(A,B) = P(A)P(B)
1.2 当A,B相关联的时候，或者说存在交集的时候，P(A,B) = P(A)P(B|A)
即 P(w1,w2,w3) = P(W1)P(W2|W1)P(W3|W1,W2)
一般形式为： P(W1,W2,..,Wn) = P(W1)P(W2|W1)...(Wn|Wn-1,...,W2,W1);
抽象为：P(W1,W2,...,Wn) = ∏ni P(wi|w1,w2,..wi-1) (累乘)
②条件概率
P(A|B) = P(A,B)/P(A)
我们将其扩展到一般形式：P(A|B,C) = P(A,B,C) / P(B,C) = P(A,B,C) / ( P(B|C) P(C) )
原理
N-Gram是基于一个假设：第n个词出现与前n-1个词相关，而与其他任何词不相关。整个句子出现的概率就等于各个词出现的概率乘积。各个词的概率可以通过语料中统计计算得到。N-gram的第一个特点是某个词的出现依赖于其他若干个词，第二个特点是我们获得的信息越多，预测越准确。
假设句子S是有词序列w1,w2,w3...wn组成，用公式表示N-Gram语言模型如下（每一个单词wi都要依赖于从第一个单词w1到它之前一个单词wi−1的影响）：
P(S) = P(w1)P(w2)P(w3)...P(wn) = P(w1)P(w2|w1)P(w3|w1w2)...P(wn|w1w2w3...)
不过这个衡量方法有两个缺陷：
-
参数空间过大，概率
的参数有 O ( n )个。
- 数据稀疏严重，词同时出现的情况可能没有，组合阶数高时尤其明显。
为了解决第一个问题，我们引入马尔科夫假设（Markov Assumption）：一个词的出现仅与它之前的若干个词有关。
那么，如何计算其中的每一项条件概率 p (wn∣wn−1 ⋯ w2w1 ) 呢？答案是**极大似然估计**，说人话就是数频数
应用
①评估句子是否合理
# Example 1：对于一元模型（1-gram）,每个词都是独立分布的，也就是对于P(A,B,C) 其中A,B,C互相之间没有交集. 所以P(A,B,C) = P(A)P(B)P(C)
比如语句：“猫，跳上，椅子” ，P(A="猫"，B="跳上"，C="椅子") = P("猫")P(“跳上”)P("椅子")；其中各个词的数量数语料库中统计的数量
依据这些数据就可以求出P(A,B,C),也就是这个句子的合理的概率.
P(A,B,C) = P(A)P(B)P(C) =13/M * 16/M * 23/M
# Example 2：对于二元模型，每个词都与它左边的最近的一个词有关联，也就是对于P(A,B,C) = P(A)P(B|A)P(C|B)
比如语句：“猫，跳上，椅子” ，P(A="猫"，B="跳上"，C="椅子") = P("猫")P(“跳上”|“猫”)P("椅子"|“跳上”)；其中各个词的数量数语料库中统计的数量
依据这些图表一和图表二就可以求出P(A,B,C),也就是这个句子的合理的概率.
P(A,B,C) = P(A)P(B|A)P(C|B) = 13/M * 9/13 * 15/16
# Example 评估：对于一个训练好的模型，我们需要评估模型的好坏，N-gram常用的评估方式是：
pp(w1,w2,...,Wn) = p(w1,w2,...,Wn)-1/n
我们以上面的一元模型和二元模型来为例，进行评估计算.
可以看出二元模型比一元模型的值要小，而值越小说明模型越好
②评估两个字符串之间的差异程度
以非重复的N-Gram分词为基础来定义 N-Gram距离这一概念，可以用下面的公式来表述：
此处，|GN(s)| 是字符串 s 的 N-Gram集合，N 值一般取2或者3。以 N = 2 为例对字符串Gorbachev和Gorbechyov进行分段，可得如下结果（我们用下画线标出了其中的公共子串）
结合上面的公式，即可算得两个字符串之间的距离是8 + 9 − 2 × 4 = 9。显然，字符串之间的距离越小，它们就越接近。当两个字符串完全相等的时候，它们之间的距离就是0。
③其他应用
分词算法、语音识别、输入法、机器翻译等
数据平滑
N-gram的N NN越大，模型 Perplexity 越小，表示模型效果越好。这在直观意义上是说得通的，毕竟依赖的词越多，我们获得的信息量越多，对未来的预测就越准确。然而，语言是有极强的创造性的（Creative），当N变大时，更容易出现这样的状况：某些n-gram从未出现过，这就是稀疏问题。
n-gram最大的问题就是稀疏问题（Sparsity）。例如，在bi-gram中，若词库中有20k个词，那么两两组合就有近2亿个组合。其中的很多组合在语料库中都没有出现，根据极大似然估计得到的组合概率将会是0，从而整个句子的概率就会为0。最后的结果是，我们的模型只能计算零星的几个句子的概率，而大部分的句子算得的概率是0，这显然是不合理的。
因此，我们要进行数据平滑（data Smoothing），数据平滑的目的有两个：一个是使所有的N-gram概率之和为1，使所有的n-gram概率都不为0。它的本质，是重新分配整个概率空间，使已经出现过的n-gram的概率降低，补充给未曾出现过的n-gram。