注：

Unimelb Comp90042 NLP笔记

相关tutorial代码链接

N-grams Language Model （N-grams语言模型）

语句生成demo网站，大家可以去玩一玩。

N-gram一种基于统计语言模型的算法。它的基本思想是将文本里面的内容按照字节进行大小为N的滑动窗口操作，形成了长度是N的字节片段序列。

普遍应用：搜索框下方提示、机器翻译、生成总结、对话系统…现代的nlp系统的脊柱就是预训练语言模型。

如何理解N-gram：¹

目前有一句话“its water is so transparent that”，然后我们想知道这个that后面第一个词是the的概率是什么该怎么办？首先我们将这件事用公式表达：
$$P(the|itswaterissotransparentthat)$$
为了计算这个概率，最简单的办法就是在一个巨大的语料库中去数数，然后得到：
$$\begin{gathered} P(the|itswaterissotransparentthat)= \\ \frac{C(itswaterissotransparentthatthe)}{C(itswaterissotransparentthat)} \end{gathered}$$
但就算找了很多，也达不到很好的估计，因为语言总是千变万化，有可能我们在网上看到的是一句"Walden Pond’s water is so transparent that the"，那和我们想要计数的句子就不一样了。
除此之外，当我们想知道一串任意单词的概率一起出现的概率是什么，比如$P(itswaterissotransparentthat)$，最简单的方法就是这句话出现的数量比上所有任意单词中挑选五个的数量，但根本不能实现。那我们得用更聪明的方法来计算概率，接下来往下看！

1.1 Deriving n-gram language models（推导）

联合概率转变条件概率
目的是得到一串任意单词的概率：$P(w_1,w_2,\dots ,w_m)$
用chain rule将联合(joint)概率变成条件(conditional)概率
$$\begin{gathered} P(w_1,w_2,\dots ,w_m)= \\ P(w_1)P(w_2|w_1)P(w_3|w_1,w_2)\dots P(w_m|w_1,\dots ,w_{m-1}) \end{gathered}$$
但这似乎没有改变计算难度，所以就要用到马可夫假设。

马可夫假设（The Markov Assumption）
TODO：markov证明
Markov可以假设 $P(w_i|w_1,\dots ,w_{i-1})\approx P(w_i|w_{i-n+1},\dots ,w_{i-1})$.
也就是原本要考虑前面单词1、单词2…单词i-1出现的时候，单词i才出现的概率是什么，现在通过假设，我们只要在意单词i-n+1到单词i-1这部分单词出现，然后单词i出现的概率。
举个例子：
$$\begin{gathered} P(the|itswaterissotransparentthat)\approx \\ P(the|transparentthat) \end{gathered}$$
我们现在只关心当前面是$transparentthat$ 的时候，后面出现$the$的概率有多少，然后用这个概率来估计。

这里我们引出N-gram的本意，就是用前面N-1个词就可以来估计前面一大段词语的概率。

1. 当 n=1，称为unigram model，只关注这个词出现的概率，那一串词语同时出现的概率就是这些词单独出现概率进行相乘（他们各自都独立互不影响）：
   $$P(w_1,w_2,\dots ,w_m)=\prod _{i=1}^{m}P(w_i)$$
2. 当 n=2，称为bigram model，看要预测的词前面的单词是什么。就相当于遍历这些词看每一个词在前面是某个词的情况下出现的概率是多少，并相乘。：
   $$P(w_1,w_2,\dots ,w_m)=\prod _{i=1}^{m}P(w_i|w_{i-1})$$
   比如 the dog barks，我们想知道$P(barks|thelittledog)$的概率，那在bigram下我们可以只看$P(barks|dog)$的概率。
3. 当 n=3, 称为trigram model:
   $$P(w_1,w_2,\dots ,w_m)=\prod _{i=1}^{m}P(w_i|w_{i-2}{w}_{i-1})$$
   用$P(barks|littledog)$的概率预估。

那我们现在该怎么计算这些变简单的概率？

最大似然估计（Maximum Likelihood Estimation）
通过在语料库中数数，然后将它们归一化（通常会对概率结果进行log，但此处没有）。

比如在bigram model里，我们通过数$w_{n-1}{w}_n$一起出现的次数，再比上$w_{n-1}w$出现的次数。这里$w$是指任意一个单词但前面一定是$w_{n-1}$。
$$P(w_n|w_{n-1})=\frac{C(w_{n-1}{w}_n)}{{\sum }_{w}C(w_{n-1}w)}$$
这个公式我们也可以进行简化，不同$w_{n-1}w$出现的次数就等于$w_{n-1}$出现的次数。
$$P(w_n|w_{n-1})=\frac{C(w_{n-1}{w}_n)}{C(w_{n-1})}$$
总结：

1. unigram,
   $$P(w_i)=\frac{C(w_i)}{M},M是所有出现过单词的数量$$
2. bigram,
   $$P(w_i|w_{i-1})=\frac{C(w_{i-1}{w}_i)}{C(w_{i-1})},\frac{C(dogbarks)}{C(dog)}$$
3. n-gram,
   $$P(w_i|w_{i-n+1}\dots w_{i-1})=\frac{C(w_{i-n+1}\dots w_{i-1}{w}_i)}{C(w_{i-n+1}\dots w_{i-1})}$$

Trigram计算例子：
补充：在每一句需要处理的话前后需要加上两个特殊标签
<s> = 语句开始; </s> = 语句结束，tag可以当做一个单词来做处理。<s>的数量根据n决定，n > 1时，数量为n-1。
句子1 “yes no no no no yes”
句子2 “no no no yes yes yes no”
问：在trigram model下，"yes no no yes"会出现的概率是多少？
答：给句子加上tag
句子1：<s> <s> yes no no no no yes </s>
句子2： <s> <s> no no no yes yes yes no </s>
遍历每一个词和该词前面两个词，注意语句结束tag也需要计算概率，因为需要确定最后结束语句的单词是什么。
$$\begin{gathered} P(yesnonoyes)=P(yes|<s><s>)\times \\ P(no|<s>yes)\times \\ P(no|yesno)\times \\ P(yes|nono)\times \\ P(</s>|noyes) \end{gathered}$$

P(x)	P	x
P(yes | <s> <s>)	1/2	<s> <s> yes <s> <s> no
P(no | <s> yes)	1/1	<s> yes no
P(no | yes no)	1/2	yes no no yes no </s>
P(yes | no no)	2/5	no no no no no no no no yes no no no no no yes
P( </s> | no yes)	1/2	no yes </s> no yes yes
$P(yesnonoyes)=0.05$

存在的问题：

1. 如果一句话中有很多单词，那就面临着越来越多概率的相乘，结果会越来越小，导致underflow。（如果每次相乘都要避免underflow，那会增加很大算量，所以可以用log probability来帮忙。使得 $p_1\times p_2\times p_3=exp(log{p}_1+log{p}_2+log{p}_3)$，让每次概率用log之和来计算，并在最后通过e的指数来得到最终概率。）
2. 一句话中前后相互影响的单词间隔可能很长，则需要的n会很大。
   比如： The lecture/s that took place last week was/were on preprocessing. 前面的单复数会影响后面be动词的形态。
3. 当出现没有见过的单词组合（但见过单词）怎么办？那这样概率就会为0，所以需要smooth。 **注：**如果出现没见的单词，则需要另一种处理方法（增加的token）

注：一般一个模型的好坏可以通过困惑度（perplexity） 来表示，句子概率越大，模型越好，困惑度越小。（参考）

1.2 Smoothing（平滑）

Basic idea：给每个没见过的事件都来点概率。但同时要保证整体概率还是1。
不同的smoothing方法²：

• Laplacian (add-one) smoothing (拉普拉斯平滑)
• Add-k smoothing
• Absolute discounting
• Kneser-Ney
• …

1.2.1 Laplacian (Add-one)

Simple idea: 假装每一个n-gram都多了一个，那这样分母就会多|V|个（当前词表的数量，不重复）。
$$P(w_i|w_{i-n+1}\dots w_{i-1})=\frac{C(w_{i-n+1}\dots w_{i-1}{w}_i)+1}{C(w_{i-n+1}\dots w_{i-1})+|V|}$$

例：
句子<s> the rat ate the cheese </s>，$P(ate|rat)$和$P(ate|cheese)$在add-one smoothing下的bigram probability是多少？
答：
$P=\frac{C(ratate)+1}{C(rat)+|V|}=\frac{2}{6}$,
V = { t h e , r a t , a t e , c h e e s e , < / s > } V=\{the,rat,ate,cheese,</s>\} V={the,rat,ate,cheese,</s>},这里不用加上<s>是因为不需要去预测它出现的概率;
$P=\frac{C(cheeseate)+1}{C(cheese)+|V|}=\frac{1}{6}$

注：M可以理解为$M={\sum }_{i=1}^V{c}_i$, c_i是token i的数量。V可以理解为有多少不同的单词出现。

1.2.2 Add-k smoothing

通常加1已经很多了，所以我们会在1前面加一个因子$k$（hyper parameter）。Add-k smoothing, aka Lidstone Smoothing 或者 Add-$\alpha$ Smoothing。
$$P_{addk}(w_i|w_{i-n+1}\dots w_{i-1})=\frac{C(w_{i-n+1}\dots w_{i-1}{w}_i)+k}{C(w_{i-n+1}\dots w_{i-1})+k|V|}$$
问题就在于如何选取$k$。

例：
以bigram model为例子，假设我们当前要预测alleged ____ 后面出现某个词的概率。这里给了已有的情况：alleged impropriety总共出现了8次，alleged offense出现了5次…（见下表）
假设要预测$P(offense|alleged)=\frac{C(allegedoffense)}{C(alleged)}$，经过平滑处理之后可以算的结果为$\frac{8+0.1}{20+7\ast 0.1}=0.391$。
根据add-k算出smoothed probability之后再去乘上总数量，就有有效计数（effective counts）。

在这里，M是20，V是7。

1.2.3 Absolute Discounting

通过从已经观察到的n-gram上借一个固定的概率质量（probability mass），然后将它们重新分配到没见到的单词上面。下图第一组出现的"effective counts"和"smoothed probability"是add-$k$的，用于对比展示。最后两列是根据absolute discounting得到的结果。
与add-$k$不同的是，absolute discounting先算出effective count，再得到smoothed probability。
下图中有5个单词是出现过的，所以我们设$d=0.1$，即从每一个出现过的单词数量中扣除0.1，然后扣除总和再去平方给没出现过的单词（这里是两个，所以是0.1 * 5 / 2 = 0.25）

1.2.4 Backoff (Katz Backoff)

与absolute discounting类似，但backoff是将概率质量根据 低阶模型（a lower order model）将值分给所有没见过的单词。

• 如果我们想知道某个trigram的概率$P(w_n|w_{n-1}{w}_{n-2})$，但是这个概率当前为0。
• 那我们可以通过bigram的概率$P(w_n|w_{n-1})$来估计。
• 如果bigram的也是0，那就看unigram的概率$P(w_n)$
• 我们只会在高n没有概率的时候采用backoff的方法到一个低n的概率（a lower order model）
• 如果tirgram原本就存在，那我们就用absolute discounting给它进行平滑。

以bigram model为例：
$$P_{katz}(w_i|w_{i-1})=\{\begin{array}{lr}\frac{C(w_{i-1},w_i)-D}{C(w_i-1)},& ifC(w_{i-1}{w}_i)>0,else\\ \alpha (w_{i-1})\frac{P(w_i)}{{\sum }_{w_j:C(w_{i-1},w_j)=0}P(w_j)},& otherwise\end{array}$$
其中，$\alpha (w_{i-1})$表示从$w_{i-1}$中扣除的概率质量；$P(w_i)$表示$w_i$的unigram概率；${\sum }_{w_j:C(w_{i-1},w_j)=0}P(w_j)$表示所有没有和$w_{i-1}$共现的单词的unigram概率之和（以前面表格为例，$w_j$就是infirmity和cephalopods）。

• 如果$C(w_{i-1},w_i)>0$，backoff就等于先前的absolute discounting
• 当为想要的概率不存在，那么$\alpha (w_{i-1})$就为分配到$w_{i-1}$的概率质量（以前面表格为例就是 5 * 0.1 = 0.5）
• 以前面表格为例，假设infirmity比cephalopods出现的更频繁（因为bigram没有出现过，但是unigram的时候会出现），就给infirmity更高的权重（公式来看的话，因为分母相同分子大所以概率更大）。

Backoff会有的问题:
可能由于语料库数据分布不均匀，导致结果不合理。
举个例子，现有个句子：
I cannot see without my reading ____
假设我们现在用bigram model，然后来看看reading后面跟glasses和Francisco的概率如何？
但不巧，现有语料库中从来没有出现过reading glasses和reading Francisco这两种组合，那我们使用Backoff Smoothing来尝试解决。由于bigram下两者Count都是0，所以就去看他们的unigram model的概率。假设语料库中，Francisco出现的次数比glasses多很多，那根据公式就得出，Francisco出现在reading后面的概率更大。
但实际上 reading glasses在语境中才更有意义。

1.2.5 Kneser-Ney Smoothing

为了解决backoff的缺陷，有了这个平滑方法。
我们将概率质量的分配基于低阶模型的多功能性上（versatility）。一个词的多功能性，就是说这个词会和多少个不同的词一起出现。
以上文中glasses和Francisco为例，我们经常能看到men’s glasses, buy glasses, etc，但是Francisco一般只会和San Francisco一起出现。那glasses的多功能性就比Francisco高。
这种多功能性也叫做连续概率（continuation probability）。

以bigram model为例：
$$P_{KN}(w_i|w_{i-1})=\{\begin{array}{lr}\frac{C(w_{i-1},w_i)-D}{C(w_i-1)},& ifC(w_{i-1}{w}_i)>0,else\\ \beta (w_{i-1})P_{cont}(w_i),& otherwise\end{array}$$
其中，
P c o n t ( w i ) = ∣ { w i − 1 : C ( w i − 1 , w i ) > 0 } ∑ w i ∣ { w i − 1 : C ( w i − 1 , w i ) > 0 } ∣ P_{cont}(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\}|} Pcont​(wi​)=∑wi​​∣{wi−1​:C(wi−1​,wi​)>0}∣∣{wi−1​:C(wi−1​,wi​)>0}​
$P_{cont}$中，分子部分计算的是一共有多少个 唯一 的单词$w_{i-1}$ 和当前单词$w_i$ 共同出现过（co-occur）；而分母部分就是将所有可能的单词 $w_i$对应的不同共现上下文单词数量（即分子部分）进行一个累加。可以想做分子是分母的去重。
$\beta (w_{i-1})$和前文的$\alpha$是一个意思。

1.2.6 Interpolation（插值）

相比之前的回退算法，我们可以将不同阶的n-gram做一个结合。
以一个trigram model为例子：
$$\begin{array}{rl}{P}_{IN}(w_i|w_{i-1},w_{i-2})& ={\lambda }_3{P}_3(w_i|w_{i-2},w_{i-1})\\ & +{\lambda }_2{P}_2(w_i|w_{i-1})\\ & +{\lambda }_1{P}_1(w_i)\\ {\lambda }_1+{\lambda }_2+{\lambda }_3=1& \end{array}$$
$\lambda$不需要人工设置，而是通过模型对于一些留存数据学习到的，这样可以学习到一个最好的平衡。
当所有的概率都0的时候，我们需要 zero gram概率，也就是OOV概率，即一个单词他没有出现的概率是什么，一般最简单的做法就是统计当前词典中所有词出现的次数，这个数分之一就是OOV的概率。

1.2.7 Interpolation Kneser-Ney

目前所有已经介绍过的平滑中最有效的方法。
以bigram model为例子：
$$P_{IKN}(w_i|w_{i-1})=\frac{C(w_{i-1},w_i)-D}{C(w_{i-1})}+\beta (w_{i-1})P_{cont}(w_i)$$
但这里$\beta (w_{i-1})$是一个归一化常数，以确保两项之和小于等于1。

1.3 应用

可参考链接
一般用于判断句子是否合理，通过看 N 个词出现的频次如何。现实中的应用就是在搜索栏打字的时候，下方会进行联想，也就是根据当前你所输入的内容弹出下一个概率最大的词

---

1. N-gram standford pdf：https://web.stanford.edu/~jurafsky/slp3/3.pdf ↩︎

2. n-gram平滑的方法：https://blog.csdn.net/fuermolei/article/details/81353746 ↩︎