注：

Unimelb Comp90042 NLP筆記

相關tutorial代碼鏈接

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

目錄

• N-grams Language Model （N-grams語言模型）
• 1.1 Deriving n-gram language models（推導）
• 1.2 Smoothing（平滑）
• • 1.2.1 Laplacian (Add-one)
  • 1.2.2 Add-k smoothing
  • 1.2.3 Absolute Discounting
  • 1.2.4 Backoff (Katz Backoff)
  • 1.2.5 Kneser-Ney Smoothing
  • 1.2.6 Interpolation（插值）
  • 1.2.7 Interpolation Kneser-Ney
  • 1.3 應用

語句生成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個詞就可以來估計前面一大段詞語的概率。

當 n=1，稱為unigram model，只關注這個詞出現的概率，那一串詞語同時出現的概率就是這些詞單獨出現概率進行相乘（他們各自都獨立互不影響）：
$$P(w_1,w_2,\dots ,w_m)=\prod _{i=1}^{m}P(w_i)$$

當 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)$的概率。

當 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})}$$
總結：

unigram,
$$P(w_i)=\frac{C(w_i)}{M},M是所有出現過單詞的數量$$

bigram,
$$P(w_i|w_{i?1})=\frac{C(w_{i?1}{w}_i)}{C(w_{i?1})},\frac{C(dogbarks)}{C(dog)}$$

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)Px

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$

存在的問題：

如果一句話中有很多單詞，那就面臨著越來越多概率的相乘，結果會越來越小，導致underflow。（如果每次相乘都要避免underflow，那會增加很大算量，所以可以用log probability來幫忙。使得 $p_1\times p_2\times p_3=exp(log{p}_1+log{p}_2+log{p}_3)$，讓每次概率用log之和來計算，并在最后通過e的指數來得到最終概率。）

一句話中前后相互影響的單詞間隔可能很長，則需要的n會很大。
比如： The lecture/s that took place last week was/were on preprocessing. 前面的單復數會影響后面be動詞的形態。

當出現沒有見過的單詞組合（但見過單詞）怎么辦？那這樣概率就會為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=\{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?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_{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\}|}$$
$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 個詞出現的頻次如何?，F實中的應用就是在搜索欄打字的時候，下方會進行聯想，也就是根據當前你所輸入的內容彈出下一個概率最大的詞

---

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

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

總結

以上是生活随笔為你收集整理的【NLP基础理论】02 N-grams语言模型和Smoothing的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。