N元模型
在自然語言處理的任務(wù)中，拼音糾錯、機器翻譯等任務(wù)都需要對某個句子的下一個單詞進(jìn)行預(yù)測，或者評估某個句子的概率大小。例如預(yù)測如下句子的下一個單詞：
Please turn your home work...
在這個語境中，我們可能會預(yù)測下一個單詞是over或是in，而不是預(yù)測為the或其他單詞。
像這種對自然語言的句子進(jìn)行建模，并賦予單詞或句子概率的模型稱為語言模型(LMs,Language Models)。在這篇博客中將介紹一種最簡單的語言模型-n元模型。n元模型對N個單詞組成的序列進(jìn)行建模，例如2-元模型、3-元模型等。2-元模型就是兩個單詞組成的序列，比如please turn,turn your,your homework等等。
N元模型
根據(jù)語境預(yù)測下一個單詞是什么的任務(wù)可以形式化的表示為：已知history h，求下一個單詞是w的概率 $P(w|h) $。例如
\[ P(the|\ its\ water\ is\ so\ transparent\ that\ ) \]
如果有一個很大的語料庫（比如web語料），我們可以采用頻率估計的方法計算上式，這個問題可以轉(zhuǎn)化為
\[ P(w|h) = \frac {P(hw)}{P(h)} = \frac {Count(hw)}{Count(h)} \]
\[ P(the|\ its\ water\ is\ so\ transparent\ that\ ) =\frac {P(\ its\ water\ is\ so\ transparent\ that\ the\ )}{P(\ its\ water\ is\ so\ transparent\ that\ )} = \frac {Count(\ its\ water\ is\ so\ transparent\ that\ the\ )}{Count(\ its\ water\ is\ so\ transparent\ that\ )}\]
即分別計算在語料庫中its water is so transparent that the出現(xiàn)的次數(shù)和its water is so transparent that出現(xiàn)的次數(shù)，然后做除法。這種方法在一些任務(wù)上的效果很好，但在一些任務(wù)中不能給出很好的結(jié)果，主要原因有以下兩點：
語言具有創(chuàng)造性：新的句子和單詞的組合方式總是在出現(xiàn)，我們不能總是計算整個句子的概率。而且在這種方法中，即使只是簡單的對例句進(jìn)行了擴(kuò)展也可能會產(chǎn)生句子的出現(xiàn)概率為0的情況。
計算量過大：在這種計算方式下，如果我們想要計算its water is so transparent出現(xiàn)的概率，我們首先需要獲得語料庫中這個句子出現(xiàn)的次數(shù)，還要計算語料庫中所有五個單詞組成的句子的次數(shù)。毫無疑問，這種方法的計算量太大了。
我們需要采用一種更好的方法來計算，首先可以采用鏈?zhǔn)椒▌t將整個句子的概率計算簡化為如下形式
\[ P(w^{n}_{1}) = P(w_{1})P(w_{2}|w_{1})P(w_{3}|w^{2}_{1})....P(w_{n}|w^{n-1}_{1}) \]
但是\(P(w_{n}|w^{n-1}_{1})\)的概率還是無法計算。N元模型的思想是，將history簡化為最近的幾個單詞。例如在二元模型中，\(P(w_{n}|w^{n-1}_{1}) = P(w_{n}|w_{n-1})\)。也就是在計算\(P(the|\ its\ water\ is\ so\ transparent\ that\ )\)的概率時近似的用 $P(the|that) $來代替。
這種采用 \(P(w_{n}|w_{n-1})\) 來近似 \(P(w_{n}|w^{n-1}_{1})\) 的假設(shè)稱為馬爾科夫假設(shè)。馬爾科夫模型是指在預(yù)測的時候不過多的考慮前文的一系列模型。將馬爾科夫假設(shè)應(yīng)用到N元模型中為：\(P(w_{n}|w^{n-1}_{1})\ =\ P(w_{n}|w^{n-1}_{n-N+1})\)
對二元模型來說，$ P(w^{n}{1}) $的的計算可以簡化為如下公式：
\[ P(w^{n}_{1})\ =\ \prod^{n}_{k=1} P(w_{k}|w_{k-1})\]
在這個公式中，模型的參數(shù)是所有的 \(P(w_{k}w_{k-1}),P(w_{k-1})\)。極大似然估計可以證明，在n次實驗、m種可能結(jié)果的情況下，如果我們已知每種結(jié)果發(fā)生的頻次，可以用 \(P(p_{i})=\frac{n_{i}}{n}\) 作為對第i種結(jié)果的概率估計，即用頻率估計參數(shù)。在本模型中，m種可能的結(jié)果為$ w{k}$的各種排列組合結(jié)果，n為語料庫的語句，則可得到如下式子：
\[ P(w_{n}|w_{n-1})=\frac{C(w_{n-1}w_{n})}{\sum_{w}{C(w_{n-1}w)}} \]
其中 \(\sum_{w}{C(w_{n-1}w)}\) 計算了\(w_{n-1}\)的各種后綴的數(shù)目總和。其實就是\(w_{n-1}\)的總數(shù)。則上式可以簡化為
\[ P(w_{n}|w_{n-1})=\frac{C(w_{n-1}w_{n})}{C(w_{n-1})} \]將整個式子推廣到一般情況可得
\[ P(w_{n}|w^{n-1}_{n-N+1})=\frac{C(w^{n-1}_{n-N+1}w_{n})}{C(w^{n-1}_{n-N+1})} \]
將二元模型應(yīng)用在實際中我們可以看到統(tǒng)計學(xué)可以將語法知識，甚至文化等編碼進(jìn)概率。比如eat的后面常常跟著一個名字或者副詞，to后面常常跟著一個動詞等語法常識，或者是I通常是一句話的開頭等個人習(xí)慣，以及人們尋求中餐的概率比英式食物的概率要高等文化習(xí)俗。另外，由于概率是介于0和1之間的浮點數(shù)，在將多個概率相乘后得到的數(shù)可能會非常小，因此我們常常對概率取log進(jìn)行表示。
語言模型的評估
評估一個語言模型的最好方法是將它放在應(yīng)用系統(tǒng)中，看這個模型為系統(tǒng)帶來了多少提升。這種方法被稱為外部測試（extrinsic evaluation）。外部測試可以準(zhǔn)確的知道這個模型對系統(tǒng)是否真的有用，但是這種測試的代價太高，一版不會使用。相對的，我們一般采用內(nèi)部測試，內(nèi)部測試的思想是獨立于任何一個應(yīng)用系統(tǒng)對模型進(jìn)行測試。
內(nèi)部測試需要測試集（test set）和訓(xùn)練集（training set）。我們拿到一份語料后，將其劃分為訓(xùn)練集和測試集兩部分。模型在訓(xùn)練集上進(jìn)行參數(shù)訓(xùn)練，在測試集上評估模型效果。需要注意的是，測試集和訓(xùn)練集的數(shù)據(jù)不能有交叉，測試集必須是模型“沒有見過”的數(shù)據(jù)。那么在測試集上如何評估模型效果呢？如果模型能更準(zhǔn)確地預(yù)測數(shù)據(jù)或是更緊的收斂于測試集，就稱這個模型的效果更好。
有時我們頻繁的使用某個測試集，會使得模型隱式地被這個測試集校準(zhǔn)。這時我們需要一個全新的測試集來評估模型，之前的測試集又被稱為開發(fā)集（development set）。那我們?nèi)绾螌⑽覀兊臄?shù)據(jù)集劃分為訓(xùn)練集、開發(fā)集和測試集呢？我們不僅希望測試集足夠大（小的測試集可能不具有代表性），又希望獲得更多的訓(xùn)練數(shù)據(jù)。我們可以選擇在能夠提供足夠的統(tǒng)計數(shù)據(jù)測試模型的效果的前提下的最小測試集。在實踐中，我們通常將數(shù)據(jù)集劃分為80%的訓(xùn)練集，10%開發(fā)集和10%的測試集。
困惑度
我們一般不直接使用模型的測試結(jié)果作為模型的評價指標(biāo)，而是一種叫做困惑度（perplexity，pp）的變量。模型的困惑度是模型在測試集上的概率被詞匯數(shù)N規(guī)范化以后的值。例如，測試集\(W=w_{1}w_{2}w_{3}...w_{N}\)的困惑度為
\[ PP(W)= P(w_{1}w_{2}w_{3}...w_{N})^{-\frac{1}{N}} = \sqrt[N]{\frac{1}{P(w_{1}w_{2}w_{3}...w_{N})}}\]
我們可以采用鏈?zhǔn)椒▌t進(jìn)行簡化
\[ PP(W)= \sqrt[N]{\prod^{N}_{i=1}{\frac{1}{P(w_{i}|w_{1}...w_{i-1})}}} \]
應(yīng)用二元模型可得
\[ PP(W)=\sqrt[N]{\prod^{N}_{i=1}{\frac{1}{P(w_{i}|w_{i-1})}}} \]
可以看到，要最大化模型在測試集上的概率，可以通過最小化困惑度來完成。
接下來我們通過一個例子來看困惑度如何比較模型的效果。基于華爾街日報訓(xùn)練的三個模型：一元模型、二元模型和三元模型的困惑度如下表所示：
| \ | 一元模型 | 二元模型 | 三元模型 |
|---|---|---|---|
| 困惑度 | 962 | 170 | 109 |
可以看出，模型提供的信息量越大（三元模型），模型的困惑度就越低，單詞的后繼詞匯就越確定。需要注意的是，在比較困惑度時，必須基于同一個測試集。
采用模型生成語句
像很多統(tǒng)計模型一樣，N元模型也依賴于訓(xùn)練語料。這意味著模型中編碼了訓(xùn)練集中的一些特定信息，而且隨著N的增大，N元模型對訓(xùn)練集的建模效果會越來越好。下面我們將直觀的反應(yīng)N元模型的這兩個特點。
我們采用香農(nóng)和米勒在1951年提出的生成隨機語句的方法來展示N元模型的特點。一元模型是最容易展示的。
一元模型生成語句算法：
- 為詞匯賦予概率：根據(jù)每個詞匯的頻率為其賦予一個0到1之間的數(shù)字
- 產(chǎn)生隨機數(shù)序列：產(chǎn)生一個隨機數(shù)序列，每個隨機數(shù)都在0到1之間
根據(jù)隨機數(shù)序列產(chǎn)生隨機語句：隨機序列中的每個隨機數(shù)a都可以找到一個詞匯，該詞匯的概率為a
根據(jù)上述算法可以產(chǎn)生一元模型的隨機語句。類似的，我們可以得到二元模型的隨機語句，其產(chǎn)生算法如下所示：- 計算每個二元詞組的概率P(a|b)
- 假設(shè)句子的開始標(biāo)志為<s>，從所有以<s<開始的二元組中隨機選出一組，假設(shè)這組為(<s>,w)
接下來從以w開頭的二元組中隨機選擇一組，重復(fù)這兩個過程，直到產(chǎn)生結(jié)束符</s>
下面給出四個模型產(chǎn)生的隨機語句：
| 模型 | 隨機語句 |
|---|---|
| 一元模型 | -To him swallowed confess hear both.Which .Of save on trail for are ay device and rote life have . -Hill he late speaks;or! a more to leg less first you enter |
| 二元模型 | -Why dost stand forth thy canopy,forsooth;he is this palpable hit the King Henry.Live king.Follow. -What means,sir.I confess she?then all sorts,he is trim,captain. |
| 三元模型 | -Fly,and will rid me these news of price.Therefore the sadness of parting,as they say,'tis done. -This shall forbid it should be branded ,if renown made it empty. |
| 四元模型 | -King Henry.What! I will go seek the traitor Gloucester.Exeunt some of the watch. A great banquet serv'd in; -It cannot be but so. |
這八條語句由四個N元模型產(chǎn)生，訓(xùn)練語料均為莎士比亞的作品。可以看出，模型訓(xùn)練的上下文越長，句子越連貫。在一元模型中，單詞之間沒有關(guān)聯(lián)，二元模型中單詞之間有一些關(guān)聯(lián)，三元模型和四元模型生成的語句看起來就很像莎士比亞的風(fēng)格了。It cannot be but so直接來自《King John》。
為了理解模型對訓(xùn)練語料的依賴，我們在另外一個語料（華爾街日報）上重新訓(xùn)練了這四個模型。結(jié)果如下：
| 模型 | 隨機語句 |
|---|---|
| 一元模型 | Months the my and issue of year foreign new exchange's september were recession exchange new endorsed a acquire to six executives. |
| 二元模型 | Last December through the way to preserve the Hudson corporation N.B.E.C.Taylor would seem to complete the major central planners one point five percent of U.S.E. has already old M.X. corporation of living on information such as more frequently fishing to keep her |
| 三元模型 | They also point to ninety nine point six billion dollars from two hundred four oh six three percent of the rates of interest stores as Mexico and Brazil on market conditions. |
比較在兩個語料上生成的模型可以發(fā)現(xiàn)，兩個模型生成的語句之間沒有交叉，甚至是詞組上也沒有交叉。可見，如果訓(xùn)練集是莎士比亞作品而測試集是華爾街日報，那么這個模型將會變得無用。因此，在訓(xùn)練N元模型時，我們需要確認(rèn)訓(xùn)練集和測試集是同一種類型的語料。同時，語料的語氣等也需要加以區(qū)分，尤其是與正式文稿或口語化文稿相關(guān)的任務(wù)。
語料的類型和語氣等匹配了仍然不夠，我們的模型還受到語料稀疏度的影響。由于語料的有限性，一些很常見的語句可能不被包含在內(nèi)，造成一些“零概率短語”實際上應(yīng)該擁有非零值的概率。比如在華爾街日報的語料中，denied the有以下短語：
- denied the allegations:5
- denied the speculation:2
- denied the rumors:1
- denied the report:1
如果訓(xùn)練集中包含下述語料他們的概率將會被視為0： - denied the offer
- denied the load
除了二元概率為0的情況（沒見過的詞匯組合），我們還可能會在測試集中遇到完全沒見過的單詞。這種情況下應(yīng)該怎么辦呢？
有時我們的語言模型不可能會遇到?jīng)]出現(xiàn)過的詞匯。這種封閉詞匯袋（closed vocabulary）的假設(shè)在某些語言任務(wù)中是合理的假設(shè)，例如語音識別、機器翻譯等，這些任務(wù)中我們會提前設(shè)置好發(fā)音詞典，語言模型只需要識別詞典中出現(xiàn)過的詞匯。
在其他的任務(wù)中，我們必須處理之前沒有遇到過的詞匯（unknown words，或者成為oov，out of vocabulary）。OOV出現(xiàn)的比例被稱為OOV率。開放詞匯袋（Open vocabulary）系統(tǒng)是指我們通過一個偽詞匯<UNK>來對測試集中可能出現(xiàn)的unknown word進(jìn)行建模的系統(tǒng)。下面介紹兩種訓(xùn)練帶有<UNK>詞匯訓(xùn)練集的方法。
第一種方法將這個問題轉(zhuǎn)化為封閉詞袋問題。首先選擇一個固定的詞匯集，然后在文本正則化（text normalization）的過程中，將不屬于固定詞匯集的單詞替換為<UNK>。根據(jù)頻率估計<UNK>的概率。
第二種方法主要針對無法事先準(zhǔn)備一個詞袋的情況，這時我們可以構(gòu)建一個詞典，將訓(xùn)練集中的一些單詞替換為<UNK>。比如我們可以將出現(xiàn)的頻率低于n的單詞都替換為<UNK>，其中n是一個很小的數(shù)字。或者設(shè)定一個詞袋的容量N，對詞袋中所有的詞匯頻率進(jìn)行統(tǒng)計并排序，取前N個詞匯組成固定詞袋，剩下的詞匯是unknown word。
平滑（smoothing）
接下來解決一種新的情景：某個在訓(xùn)練集中出現(xiàn)過的單詞，在測試集里出現(xiàn)在一種新的語境中，該如何計算？為了使語言模型在這種情況下不會賦予短語0概率，我們需要將高頻事件的概率勻一部分給未知的新事件。這種概率的修改稱為平滑（smoothing）或者折扣（discount），下面將介紹幾種平滑方式：add-1 smoothing,add-k smoothing,stupid backoff和Kneser-Ney smoothing。
Laplace Smoothing
最簡單的平滑方式是在計算概率之前，為所有的二元詞組的計數(shù)都加一。之前頻數(shù)為1的詞組變成2，頻數(shù)為2的詞組變成3。這平滑方式又被稱為拉普拉斯平滑（Laplace Smoothing）。拉普拉斯平滑雖然在現(xiàn)在的很多模型中表現(xiàn)不是很好，但是可以為我們引入許多平滑的術(shù)語，并為其他的平滑方式提供一個基準(zhǔn)線（baseline），而且在文本分類等任務(wù)中有較好的效果。
我們可以先嘗試將拉普拉斯平滑加入一元模型中。根據(jù)極大似然估計計算一元模型中某個詞的概率公式為：
\[ P(w_{i})=\frac{c_{i}}{N} \]
其中\(w_{i}\)為訓(xùn)練集中的詞匯，\(c_{i}\)為\(w_{i}\)的頻數(shù)，\(N\)為所有詞匯的頻數(shù)總和。拉普拉斯平滑只是為每個詞匯的頻數(shù)都加1。假設(shè)訓(xùn)練集中共有\(V\)個詞匯，因此公式中的分母相應(yīng)的調(diào)整為\(N+V\)。完整的公式如下：
\[P(w_{i})=\frac{c_{i}+1}{N+V}\]
我們可以定義一個新的變量\(c^{*}_{i}\)作為系數(shù)，在計算一個詞匯的平滑概率時不用同時改變分子、分母，只需要將原來的概率乘以該系數(shù)即可。\(c^{*}_{i}\)的定義如下：
\[c^{*}_{i}=(c_{i}+1)*\frac{N}{N+V}\]
現(xiàn)在我們可以將\(c^{*}_{i}\)直接除以\(N\)得到概率\(P^{*}_{i}\)。我們可以通過另一種方式描述這種平滑：詞匯的原始頻數(shù)與平滑后的頻數(shù)之比，也即詞匯頻數(shù)的折扣\(discount \ d_{c}\):
\[d_{c}=\frac{c^{*}}{c}\]
現(xiàn)在我們有了一元模型的平滑計算方法，繼續(xù)看二元模型的拉普拉斯平滑。二元模型的概率計算方法為：
\[P(w_{n}|w_{n-1})=\frac{C(w_{n-1}w_{n})}{C(w_{n-1})}\]
二元模型的平滑即為給每個二元詞組的共現(xiàn)頻數(shù)都加一。計算公式改為如下形式：
\[P^{*}_{Laplace}(w_{n}|w_{n-1})=\frac{C(w_{n-1}w_{n})+1}{\sum_{w}{(C(w_{n-1}w)+1)}}=\frac{C(w_{n-1}w_{n})+1}{C(w_{n-1})+V}\]
通過上面的公式我們計算出二元概率模型中每個二元詞組的概率。二元模型的平滑系數(shù)計算方法如下：
\[c^{*}(w_{n-1}w_{n})=P^{*}_{Laplace}*C(w_{n-1})=\frac{[C(w_{n-1}w_{n}+1)]*C(w_{n-1})}{C(w_{n-1})+V}\]
以下兩個表格分別是二元模型在某一語料上的平滑前和平滑后的頻數(shù)。
| \ | i | want | to | eat | chinese | food | lunch | spend |
|---|---|---|---|---|---|---|---|---|
| i | 5 | 827 | 0 | 9 | 0 | 0 | 0 | 2 |
| want | 2 | 0 | 608 | 1 | 6 | 6 | 5 | 1 |
| to | 2 | 0 | 4 | 686 | 2 | 0 | 6 | 211 |
| eat | 0 | 0 | 2 | 0 | 16 | 2 | 42 | 0 |
| chinese | 1 | 0 | 0 | 0 | 0 | 82 | 1 | 0 |
| food | 15 | 0 | 15 | 0 | 1 | 4 | 0 | 0 |
| lunch | 2 | 0 | 0 | 0 | 0 | 1 | 0 | 0 |
| speed | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |
以下是平滑后的頻數(shù)表：
| \ | i | want | to | eat | chinese | food | lunch | spend |
|---|---|---|---|---|---|---|---|---|
| i | 3.8 | 527 | 0.64 | 6.4 | 0.64 | 0.64 | 0.64 | 1.9 |
| want | 1.2 | 0.39 | 238 | 0.78 | 2.7 | 2.7 | 2.3 | 0.78 |
| to | 1.9 | 0.63 | 3.1 | 430 | 1.9 | 0.63 | 4.4 | 133 |
| eat | 0.34 | 0.34 | 1 | 0.34 | 5.8 | 1 | 15 | 0.34 |
| chinese | 0.2 | 0.098 | 0.098 | 0.098 | 0.098 | 8.2 | 0.2 | 0.098 |
| food | 6.9 | 0.43 | 6.9 | 0.43 | 0.86 | 2.2 | 0.43 | 0.43 |
| lunch | 0.57 | 0.19 | 0.19 | 0.19 | 0.19 | 0.38 | 0.19 | 0.19 |
| speed | 0.32 | 0.16 | 0.32 | 0.16 | 0.16 | 0.16 | 0.16 | 0.16 |
從上面兩個表可以看出拉普拉斯平滑對詞匯的頻數(shù)改變是很大的。\(C(want to)\)的頻數(shù)從608降到了238！計算頻數(shù)的折扣可以看出頻數(shù)的變化是多么劇烈，\(C(chinese food)\)的折扣率竟然高達(dá)10！這種頻數(shù)和概率的劇烈變化是因為我們從高頻詞的地方借來了太多概率！
add-k smoothing
既然add-1平滑的折扣率太高了，一個很自然的想法是降低從高頻詞匯那里勻出來的概率，每個詞的頻數(shù)不是加1，而是加上一個小于1的浮點數(shù)k，這種方法被稱為add-k smoothing。
\[P^{*}_{Add-k}(w_{n}|w_{n-1}) = \frac{C(w_{n-1}w_{n})+k}{C(w_{n-1})+kV}\]
add-k 平滑要求我們有選擇k的算法，例如我們可以通過在dev集上優(yōu)化k值。盡管add-k smoothing在一些任務(wù)上很有效（包括文本分類的任務(wù)），但它應(yīng)用在語言模型上的效果仍然不是很好，平滑后的頻數(shù)要么對原頻數(shù)沒什么改變，要么有著不恰當(dāng)?shù)恼劭勐省?/p>
backoff and interpolation
add-1平滑和add-k平滑可以解決N元模型的詞匯零頻數(shù)問題，但是N元模型的零值問題還包含另一種情況：假設(shè)我們要計算\(P(w_{n}|w_{n-2}w_{n-1})\)，但是我們沒有\(w_{n-2}w_{n-1}w_{n}\)的詞組，我們可以退而求其次，計算二元概率\(P(w_{n}|w_{n-1})\)代替三元概率。類似的，如果我們沒有二元概率\(P(w_{n}|w_{n-1})\)，可以使用一元概率\(P(w_{n})\)進(jìn)行代替。
換句話說，有時在訓(xùn)練的時候少一點上下文可以模型的泛化能力。有兩種方法利用這種n元模型之間的“繼承關(guān)系”，分別是后退和插值。當(dāng)模型無法估計N元詞組時，后退一步選用N-1元模型替代，這種方法稱為后退。而插值的方法會利用所有的N元模型信息。
插值算法
當(dāng)估計一個三元詞組的概率時，加權(quán)結(jié)合三元模型、二元模型和一元模型的結(jié)果。線性插值是相對簡單的插值方法，將N個模型的結(jié)果做線性組合。利用線性插值估計三元詞組的概率時，公式如下：
\[P(w_{n}|w_{n-1}w_{n-2})=\lambda_{1}P(w_{n}|w_{n-1}w_{n-2})+\lambda_{2}P(w_{n}|w_{n-1})+\lambda_{3}P(w_{n}) \]
其中所有的\(\lambda\)和為1，\(\sum_{i}\lambda_{i}=1\)
稍微復(fù)雜一點的情況是，根據(jù)上下文來計算\(\lambda\)的值，計算公式如下：
\[P(w_{n}|w_{n-1}w_{n-2})=\lambda_{1}(w^{n-1}_{n-2})P(w_{n}|w_{n-1}w_{n-2})+\lambda_{2}(w^{n-1}_{n-2})P(w_{n}|w_{n-1})+\lambda_{3}(w^{n-1}_{n-2})P(w_{n}) \]
公式中的\(\lambda\)值如何確定呢？線性插值和條件插值中的\(\lambda\)值都可以通過held-out corpus學(xué)習(xí)得到的，其中held-out語料是一個附加訓(xùn)練集，用于訓(xùn)練超參數(shù)（比如上面的\(\lambda\)）。比如，固定N元模型的概率，尋找使\(P(w_{n}|w_{n-1}w_{n-2})\)最大的\(\lambda\)值，可以采用EM算法確定\(\lambda\)值。
后退算法
在使用后退算法計算概率時，如果N元詞組計算的概率為0，使用N-1元近似來N元詞組的概率。為了維持概率分布的正確性，在后退算法中，需要對higher-order概率折扣處理。如果higher-order的概率不進(jìn)行折扣處理，而是直接使用lower-order的概率去近似，概率空間會被擴(kuò)大，概率和將大于1。比如\(P(w_{n}|w_{n-1})\)的概率明顯比\(P(w_{n})\)概率小，如果直接用一元概率替代，所有二元概率的概率和將大于一。因此，我們需要用一個函數(shù)\(\alpha\)來均衡概率分布。
這種有折扣的后退方法被稱為Katz backoff。在Katz后退方法中，如果\(C(w^{n}_{n-N+1})\)不為0，那么概率值為折扣概率\(P^{*}\)，如果\(C(w^{n}_{n-N+1})\)是0，就遞歸地退回N-1的短上下文情境中計算概率并乘以\(\alpha\)函數(shù)的結(jié)果，具體公式如下所示：
Katz后退通常跟Good-Turing平滑方法結(jié)合在一起使用。
Kneser-Ney算法
Kneser-Ney將絕對折扣算法加以擴(kuò)充，能更好的處理地lower-order模型的概率分布。現(xiàn)在考慮這樣一個問題，采用二元模型和一元模型預(yù)測一句話中的下一個單詞，舉例如下：
I can't see without my reading...
單詞glasses是比較合理的后繼詞匯，因此我們希望一元模型能預(yù)測出glasses而不是Kong。但是由于Hong Kong是一個很常見的詞組，一元模型給Kong賦予的概率要比glasses高。對比Kong和glasses兩個詞匯可以發(fā)現(xiàn)，雖然Kong是一個很常見的詞匯，但是Kong一般只出現(xiàn)在Hong之后，而glasses的分布更為廣泛。也就是說，在一個新的語境中，一元模型預(yù)測的概率不應(yīng)該只是：這個詞匯出現(xiàn)的概率有多大？而是：這個詞匯在新語境中出現(xiàn)的概率有多大？我們將這種新的概率記為\(P_{CONTINUATION}\)。KN算法通過統(tǒng)計詞匯w出現(xiàn)在不同語境中的次數(shù)來計算\(P_{CONTINUATION}\)，其假設(shè)為一個單詞在過去出現(xiàn)在不同語境中的頻率越高，在未來出現(xiàn)在新語境中的可能性就越高。即為
\[P_{CONTINUATION}(w) \propto | {v:C(vw)>0}|\]
為了將這種正比關(guān)系轉(zhuǎn)化為概率公式，我們可以用所有二元詞組的數(shù)目來正則化。即：
\[P_{CONTINUATION}(w)=\frac{| {v:C(vw)>0}|}{|{(u',w'):C(u'w')>0|}}\]
另一種歸一化的方法是采用單詞w的所有前繼的后繼數(shù)目之和，公式如下：
\[P_{CONTINUATION}(w)=\frac{| {v:C(vw)>0}|}{\sum_{w'}|{(vw')>0|}}\]
在這個公式中高頻詞匯Kong的概率很低，達(dá)到了我們的預(yù)期。最終的KN插值公式如下：
\[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_{CONTINUATION}(w_{i})\]
其中\(\lambda\)的計算方法為：
\[\lambda(w_{i-1})=\fracze8trgl8bvbq{\sum_{v}{C(w_{i-1}w)}}|\{w:C(w_{i-1}w)>0|\}\]
其中第一項\(\fracze8trgl8bvbq{\sum_{v}{C(w_{i-1}w)}}\)計算了\(w_{i-1}\)的所有后繼的頻數(shù)之和，第二項\(|\{w:C(w_{i-1}w)>0|\}\)計算了\(w_{i-1}\)的后繼種類。
將KN公式推廣到一般情況，遞歸公式如下：
\[P_{KN}(w_{i}|w^{i-1}_{i-n+1})=\frac{max(c_{KN}(w^{i}_{i-n+1})-d,0)}{\sum_{v}{c_{KN}(w^{i-1}_{i-n+1}v)}}+\lambda(w^{i-1}_{i-n+1})P_{KN}(w_{i}|w^{i-1}_{i-n+2})\]
其中\(count()\)函數(shù)的值取決于計算的是highest-order的頻數(shù)還是lower-ouder的頻數(shù)。如果是highest-order，則直接計算頻數(shù)即可，如果是lower-ouder則計算其語境的數(shù)目。即：
遞歸過程的最后一步是均勻分布\(\frac{1}{V}\)的一元插值，參數(shù)\(\epsilon\)是一個空字符串，計算公式如下：
\[P_{KN}(w)=\frac{max(c_{KN}(w)-d,0)}{\sum_{w'}{c_{KN}(w')}}+\lambda(\epsilon)\frac{1}{V}\]
KN插值算法的效果最好的版本是modified Kneser-Ney smoothing，該算法不只使用一個\(d\)進(jìn)行計算折扣，而是用了三個折扣參數(shù)\(d_{1},d_{2},d_{3}\)，分別用于頻數(shù)為1、2和3及以上頻數(shù)的詞匯。
網(wǎng)絡(luò)和后退算法
web極大的豐富了自然語言處理的語料庫，有了網(wǎng)絡(luò)，訓(xùn)練high-oder的N元模型成為可能。google在2016年發(fā)布了一個極大的N元詞組count集，包括從一元到五元所有詞組的頻數(shù)。要在大規(guī)模語料集上構(gòu)建語言模型，性能問題需要慎重考慮。例如字符串形式的單詞放在磁盤上，內(nèi)存中只放一個64位的哈希碼。還有其他的方式來縮減N元模型的大小：僅僅存儲頻數(shù)大于某個閾值的N元詞組或是利用熵去掉某些不重要的N元詞組。
盡管有了這些方法的幫助，我們可以在web語料集上采用KN平滑算法，但是Brants在2007年的研究結(jié)果表明沒有必要采用KN等復(fù)雜算法，當(dāng)語料集合非常大時（例如web語料），簡單的平滑算法反而更加有效。這種簡單的算法就是后退算法（stupid backoff）。后退算法不會平衡概率分布，當(dāng)higher-order的概率為0時，直接后退到lower-order進(jìn)行代替，計算公式如下：
后退算法在一元模型時停止，此時概率\(S(w)=\frac{count(w)}{N}\)，此外Brants在2007年給出了\(\lambda\)的優(yōu)值0.4。
轉(zhuǎn)載于:https://www.cnblogs.com/AnnaJuly/p/10626443.html
總結(jié)
- 上一篇： 修一个惠普的鼠标键盘和触碰面板多少钱？
- 下一篇： 及开头的四字成语有哪些啊？