手算KN-based ngram语言模型
什么是ngram語(yǔ)言模型
語(yǔ)言模型是NLP中最最基礎(chǔ)的模塊，從傳統(tǒng)基于統(tǒng)計(jì)的ngram語(yǔ)言模型，再到基于深度學(xué)習(xí)的CNN，RNN語(yǔ)言模型，再到現(xiàn)在基于tranformer的預(yù)訓(xùn)練語(yǔ)言模型，每次語(yǔ)言模型的發(fā)展都能給整個(gè)NLP領(lǐng)域帶來(lái)巨大推動(dòng)。
由于傳統(tǒng)的ngram語(yǔ)言模型具備原理簡(jiǎn)單，推斷速度快等特點(diǎn)，所以至今依然在廣泛應(yīng)用在眾多NLP任務(wù)中，尤其在計(jì)算資源受限的移動(dòng)端。本文將系統(tǒng)介紹ngram語(yǔ)言模型的內(nèi)部原理，計(jì)算方法及相關(guān)工具。
ngram語(yǔ)言模型計(jì)算方法
給定一句話(huà):
，這里的 為語(yǔ)言描述的最小單元，可以是字，也可以是詞。語(yǔ)言模型是用來(lái)評(píng)價(jià)這一句話(huà)成立的概率：對(duì)于其中的每一小項(xiàng)
， 可以用頻率來(lái)估計(jì)概率，即：這里
表示在整個(gè)語(yǔ)料中 聯(lián)合出現(xiàn)的次數(shù)。理論上語(yǔ)料足夠充足，就可以很好的用頻率直接估計(jì)出概率，但實(shí)際操作中對(duì)于較長(zhǎng)的序列
可能數(shù)量非常少，或者不存在。例如，計(jì)算: p(處理| {我, 愛(ài), 自然, 語(yǔ)言})，可能整個(gè)語(yǔ)料中都沒(méi)有{我, 愛(ài), 自然, 語(yǔ)言, 處理}這個(gè)表達(dá)。ngram語(yǔ)言模型的核心就在于一個(gè)強(qiáng)假設(shè)：當(dāng)前詞的概率分布只與前N-1個(gè)詞有關(guān)，即：
本質(zhì)上 N-gram 模型的假設(shè)類(lèi)似于馬爾可夫鏈當(dāng)中的 N-1 階馬爾可夫性假設(shè)。通常情況下n=1,2,3。對(duì)于再高階的4-gram，5-gram就很少見(jiàn)，因?yàn)樾枰浅４蟮恼Z(yǔ)料才能訓(xùn)練充分高階的語(yǔ)言模型，而且模型本身的體積也會(huì)非常大（占內(nèi)存）。
- 當(dāng)n=1時(shí)為unigram：當(dāng)前詞的概率分布與歷史信息無(wú)關(guān)
- 當(dāng)n=2時(shí)為bigram：當(dāng)前詞的概率分布只和前一個(gè)詞有關(guān)
- 當(dāng)n=3時(shí)為trigram：當(dāng)前詞的概率分布只和前兩個(gè)詞有關(guān)
所以假設(shè)n=2，p(處理| {我, 愛(ài), 自然, 語(yǔ)言}) = p(處理| 語(yǔ)言) = #{語(yǔ)言, 處理} / #{語(yǔ)言} ，這樣相對(duì)而言就可算了。
基于kenlm的ngram語(yǔ)言模型訓(xùn)練
運(yùn)用ngram語(yǔ)言模型目前最便捷的工具就是kenlm，可快速實(shí)現(xiàn)語(yǔ)言模型的訓(xùn)練與應(yīng)用。
首先準(zhǔn)備一份語(yǔ)言模型訓(xùn)練語(yǔ)料（test_corpus.txt）注意每個(gè)詞之前需要空格分割，如果訓(xùn)練基于字的語(yǔ)言模型，則每個(gè)字之前用空格分割。
模型 語(yǔ)言 模型 傳統(tǒng) 模型 語(yǔ)言關(guān)于kenlm的安裝網(wǎng)上有很多教程，實(shí)際操作的過(guò)程中也確實(shí)有坑，為了避免踩坑，可直接采用docker來(lái)獲得已安裝了kenlm的環(huán)境。具體參見(jiàn)：GitHub - nghuyong/kenlm-docker: docker for kenlm 。下面采用kenlm訓(xùn)練一個(gè)bigram語(yǔ)言模型：
# 拉取鏡像 docker pull nghuyong/kenlm # 啟動(dòng)并進(jìn)入容器 docker run -it -v $(pwd):/var nghuyong/kenlm bash # 容器內(nèi)訓(xùn)練kenlm ./lmplz -o 2 --verbose_header --text /var/test_corpus.txt --arpa /var/arpa.kenlm這樣就完成了語(yǔ)言模型的訓(xùn)練，并獲得arpa模型文件。
下面是輸出的apra文件
# Input file: /var/test_corpus.txt # Token count: 6 # Smoothing: Modified Kneser-Ney \data\ ngram 1=6 ngram 2=7\1-grams: -0.89085555 <unk> 0 0 <s> -0.22184873 -0.89085555 </s> 0 -0.46488678 模型 0 -0.69896996 語(yǔ)言 -0.30103 -0.69896996 傳統(tǒng) -0.30103\2-grams: -0.89085555 模型 </s> -0.50267535 語(yǔ)言 </s> -0.24850096 傳統(tǒng) </s> -0.44889864 <s> 模型 -0.37527603 語(yǔ)言 模型 -0.56863624 <s> 語(yǔ)言 -0.6575773 <s> 傳統(tǒng)\end\可以看到生成的arpa文件包括ngram的統(tǒng)計(jì)值以及ngram的概率。基于這份arpa文件就可以計(jì)算一句話(huà)的概率分布了。
再看一下kenlm訓(xùn)練過(guò)程輸出的日志情況：
=== 1/5 Counting and sorting n-grams === Reading /data/mm64/rightyonghu/code/kenlm/build/bin/test_corpus.txt ----5---10---15---20---25---30---35---40---45---50---55---60---65---70---75---80---85---90---95--100 **************************************************************************************************** Unigram tokens 6 types 6 === 2/5 Calculating and sorting adjusted counts === Chain sizes: 1:72 2:33536714342 Statistics: 1 6 D1=0.5 D2=0.5 D3+=3 2 7 D1=0.5 D2=1.25 D3+=3 Memory estimate for binary LM: type B probing 292 assuming -p 1.5 probing 320 assuming -r models -p 1.5 trie 226 without quantization trie 1235 assuming -q 8 -b 8 quantization trie 226 assuming -a 22 array pointer compression trie 1235 assuming -a 22 -q 8 -b 8 array pointer compression and quantization === 3/5 Calculating and sorting initial probabilities === Chain sizes: 1:72 2:112 ----5---10---15---20---25---30---35---40---45---50---55---60---65---70---75---80---85---90---95--100 #################################################################################################### === 4/5 Calculating and writing order-interpolated probabilities === Chain sizes: 1:72 2:112 ----5---10---15---20---25---30---35---40---45---50---55---60---65---70---75---80---85---90---95--100 #################################################################################################### === 5/5 Writing ARPA model === ----5---10---15---20---25---30---35---40---45---50---55---60---65---70---75---80---85---90---95--100 **************************************************************************************************** Name:lmplz VmPeak:33297604 kB VmRSS:3344 kB RSSMax:8928344 kB user:0.484 sys:3.636 CPU:4.12075 real:4.12281根據(jù)日志可以看出，kenlm在訓(xùn)練語(yǔ)言模型時(shí)候分成了5個(gè)主要步驟：統(tǒng)計(jì)并排序ngram，計(jì)算并排序調(diào)整就計(jì)數(shù)，計(jì)算并排序初始概率，計(jì)算并寫(xiě)入差值概率以及生成arpa模型文件。
下面我們就將細(xì)致拆解這個(gè)幾個(gè)步驟，給定語(yǔ)料，硬核的手算出arpa模型。
手算基于KN的語(yǔ)言模型
繼續(xù)以test_corpus.txt為語(yǔ)料，手算一個(gè)bigram的語(yǔ)言模型。
模型 語(yǔ)言 模型 傳統(tǒng) 模型 語(yǔ)言1. ngram初始統(tǒng)計(jì)
第一步是進(jìn)行ngram的統(tǒng)計(jì)，因?yàn)檫@里訓(xùn)練bigram的語(yǔ)言模型，所以需要統(tǒng)計(jì)unigram以及bigram的數(shù)量。
在進(jìn)行統(tǒng)計(jì)之前需要先給語(yǔ)料中每句話(huà)的開(kāi)始和結(jié)束加上特殊的token：<s> 和 </s>。這樣語(yǔ)料進(jìn)一步處理成：
<s> 模型 </s> <s> 語(yǔ)言 模型 </s> <s> 傳統(tǒng) </s> <s> 模型 </s> <s> 語(yǔ)言 </s>根據(jù)以上語(yǔ)料統(tǒng)計(jì)ngram的數(shù)量
| unigram | count |
| <s> | 5 |
| 傳統(tǒng) | 1 |
| 語(yǔ)言 | 2 |
| 模型 | 3 |
| </s> | 5 |
| bigram | count |
| <s> 模型 | 2 |
| <s> 語(yǔ)言 | 2 |
| <s> 傳統(tǒng) | 1 |
| 語(yǔ)言 模型 | 1 |
| 模型 </s> | 3 |
| 傳統(tǒng) </s> | 1 |
| 語(yǔ)言 </s> | 1 |
2. ngram計(jì)數(shù)調(diào)整
對(duì)于N-gram的語(yǔ)言模型，調(diào)整技術(shù)主要針對(duì)n<N的ngram進(jìn)行計(jì)數(shù)調(diào)整。核心是將計(jì)數(shù)從原先的直接數(shù)量統(tǒng)計(jì)調(diào)整為可接詞數(shù)量的統(tǒng)計(jì)。具體的計(jì)算方法如下：
這里的
表明對(duì)于 語(yǔ)料中的直接計(jì)數(shù)，表明調(diào)整后的計(jì)數(shù)。當(dāng)n=N或者 為<s>時(shí)不需要調(diào)整計(jì)數(shù)；對(duì)于其他情況，需要將計(jì)數(shù)調(diào)整為 之前可接詞的數(shù)量。所以調(diào)整后計(jì)數(shù)的結(jié)果為：
| unigram | adjust count | reason |
| <s> | 5 | w1 = <s>, a = c = 5 |
| 傳統(tǒng) | 1 | | {<s>, 傳統(tǒng)} | = 1 |
| 語(yǔ)言 | 1 | | {<s>, 語(yǔ)言} | = 1 |
| 模型 | 2 | | {<s>, 模型}, {語(yǔ)言, 模型} | = 2 |
| </s> | 3 | | {模型, </s>}, {傳統(tǒng), </s>}, {語(yǔ)言, </s>} | = 3 |
| bigram | adjust count | reason |
| <s> 模型 | 2 | n = N, a = c =2 |
| <s> 語(yǔ)言 | 2 | n = N, a = c =2 |
| <s> 傳統(tǒng) | 1 | n = N, a = c =1 |
| 語(yǔ)言 模型 | 1 | n = N, a = c =1 |
| 模型 </s> | 3 | n = N, a = c =3 |
| 傳統(tǒng) </s> | 1 | n = N, a = c =1 |
| 語(yǔ)言 </s> | 1 | n = N, a = c =1 |
3. 計(jì)數(shù)打折
計(jì)數(shù)打折的思想為：對(duì)于出現(xiàn)頻率較高的ngram減少一點(diǎn)對(duì)最終的概率影響不會(huì)很大，可將其加到那些未出現(xiàn)的ngram上；對(duì)于出現(xiàn)頻率較低的ngram則不能減少。
具體根據(jù)Chen and Goodman提出的打折公式進(jìn)行計(jì)算
這里的
表示出現(xiàn)了k次的ngram個(gè)數(shù)，這里的| t_{n,k} (n=1,2; k=1,2,3,4) | value | reason |
| t_{1,1} | 2 | n=1, |a(語(yǔ)言) , a(傳統(tǒng)) | = 2 |
| t_{1,2} | 1 | n=1, |a(模型) | = 1 |
| t_{1,3} | 1 | n=1, |a(</s>)| = 1 |
| t_{1,4} | 0 | n=1, 不存在a為4的unigram |
| t_{2,1} | 4 | n = 2, |a({<s>, 傳統(tǒng)}), a({語(yǔ)言, 模型}), a({傳統(tǒng), </s>}), a({語(yǔ)言, </s>})| = 4 |
| t_{2,2} | 2 | n = 2, |a({<s>, 模型}), a({<s>, 語(yǔ)言})| = 2 |
| t_{2,3} | 1 | n = 2, |a({模型, </s>})| = 1 |
| t_{2,4} | 0 | n=2, 不存在a為4的bigram |
| D_{n,k} | value |
| D_{1}(1) | 1/2 |
| D_{1}(2) | 1/2 |
| D_{1}(3) | 3 |
| D_{1}(4) | 3 |
| D_{2}(1) | 1/2 |
| D_{2}(2) | 5/4 |
| D_{2}(3) | 3 |
| D_{2}(4) | 3 |
4. 計(jì)算偽概率
偽概率的計(jì)算公式如下:
可以看到，分子如果沒(méi)有減去
這項(xiàng)就是最基礎(chǔ)的用概率估計(jì)頻率，減去這個(gè)折扣項(xiàng)蘊(yùn)含的思想是”劫富濟(jì)貧“，即對(duì)那些出現(xiàn)次數(shù)較多的 n-gram 減少對(duì)應(yīng)的次數(shù)，之后加到未出現(xiàn)的 n-gram 上面。| unigram | u value | reason |
| <s> | 2/7 | a = 5, D_{1}(5) = 3, a(傳統(tǒng)) + a(語(yǔ)言) + a(模型) + a(</s>) = 7(5-3) / 7 = 2/7 |
| 傳統(tǒng) | 1/14 | a = 1, D_{1}(1) = 1/2 (1-1/2)/7 = 1/14 |
| 語(yǔ)言 | 1/14 | a = 1, D_{1}(1) = 1/2 (1-1/2)/7 = 1/14 |
| 模型 | 3/14 | a = 2, D_{1}(2). = 1/2 (2-1/2)/7 = 3/14 |
| </s> | 0 | a =3, D_{1}(3) = 3 (3-3) / 7 = 0 |
| bigram | u value | reason |
| <s> 模型 | 3/20 | a = 2, D_{2}(2) = 5/4, a({<s> 模型}) + a({<s> 語(yǔ)言}) + a({<s> 傳統(tǒng)}) = 5(2-5/4)/5 = 3/20 |
| <s> 語(yǔ)言 | 3/20 | a = 2, D_{2}(2) = 5/4 (2-5/4)/5 = 3/20 |
| <s> 傳統(tǒng) | 1/10 | a = 1, D_{2}(1) = 1/2 (1-1/2)/5 = 1/10 |
| 語(yǔ)言 模型 | 1/4 | a = 1, D_{2}(1) = 1/2 a({語(yǔ)言 模型}) + a({語(yǔ)言 </s>}) = 2(1-1/2) / 2 = 1/4 |
| 模型 </s> | 0 | a = 3, D_{2}(3) = 3 a({模型 </s>}) = 3(3-3) / 3 = 0 |
| 傳統(tǒng) </s> | 1/2 | a = 1, D_{2}(1) = 1/2 a({模型 </s>}) = 1(1-1/2)/1 = 1/2 |
| 語(yǔ)言 </s> | 1/4 | a = 1, D_{2}(1) = 1/2 a({語(yǔ)言 </s> }) + a({語(yǔ)言 模型}) = 2(1-1/2)/2= 1/4 |
注意，當(dāng)n=1時(shí)，計(jì)算
不考慮<s>， 因?yàn)?lt;s>之前不可能再接入詞5. 回退值計(jì)算
定義回退值為接詞的能力，具體回退值的計(jì)算公式如下:
| unigram | backoff value | reason |
| <s> | 3/5 | (1/2*1 + 5/4 * 2 + 3 * 0) / 5= 3/5 |
| 傳統(tǒng) | 1/2 | (1/2*1 + 5/4*0 + 3*0) / 1 = 1/2 |
| 語(yǔ)言 | 1/2 | (1/2*2 + 5/4 *0 + 3*0) / 2 = 1/2 |
| 模型 | 1 | (1/2*0 + 5/4 *0 + 3*1) / 3 = 1 |
| </s> | 0 | 0 |
注意</s>后面不可能接新詞，所以backoff為0
6. 差值計(jì)算
差值的計(jì)算可根據(jù)遞推公式：
根據(jù)此遞推公式一定會(huì)遞歸到unigram，而unigram可直接由以下公式進(jìn)行計(jì)算
這里的
為空字符串，即可以認(rèn)為是 ，所以回退值可計(jì)算為:首先計(jì)算unigram插值后的概率值，注意對(duì)于<s>的概率直接置為0
| unigram | p | reason |
| <s> | 0 | 0 |
| 傳統(tǒng) | 1/5 | 1/14 + 9/14 * (1/5) = 14/70 |
| 語(yǔ)言 | 1/5 | 1/14 + 9/14 * (1/5) = 14/70 |
| 模型 | 12/35 | 3/14 + 9/14 * (1/5) = 24/70 |
| </s> | 9/70 | 0 + 9/14 * (1/5) = 9/70 |
| <unk> | 9/70 | 0 + 9/14 * (1/5) = 9/70 |
再根據(jù)遞推公式，進(jìn)一步計(jì)算bigram插值后的概率值
| bigram | p | reason |
| <s> 模型 | 249/700 | 3/20 + 3/5 * 24/70 = 249/700 |
| <s> 語(yǔ)言 | 27/100 | 3/20 + 3/5 * 1/5 = 27/100 |
| <s> 傳統(tǒng) | 11/50 | 1/10 + 3/5 * 1/5 = 11/50 |
| 語(yǔ)言 模型 | 59/140 | 1/4 + 1/2 * 24/70 = 59/140 |
| 模型 </s> | 9/70 | 0 + 1 * 9/70 = 9/70 |
| 傳統(tǒng) </s> | 79/140 | 1/2 + 1/2 * 9/70 = 79/140 |
| 語(yǔ)言 </s> | 11/35 | 1/4 + 1/2 * 9/70 = 11/35 |
7. 生成語(yǔ)言模型
整理上文中計(jì)算的概率以及backoff，并計(jì)算log10
| unigram | p | log10 p | backoff | log10 backoff |
| <s> | 0 | 0 | 3/5 | -0.221849 |
| 傳統(tǒng) | 1/5 | -0.698970 | 1/2 | -0.301030 |
| 語(yǔ)言 | 1/5 | -0.698970 | 1/2 | -0.301030 |
| 模型 | 12/35 | -0.464887 | 1 | 0 |
| </s> | 9/70 | -0.890856 | 0 | 0 |
| <unk> | 9/70 | -0.890856 | 0 | 0 |
| bigram | p | log10 p | ||
| <s> 模型 | 249/700 | -0.448899 | ||
| <s> 語(yǔ)言 | 27/100 | -0.568636 | ||
| <s> 傳統(tǒng) | 11/50 | -0.657577 | ||
| 語(yǔ)言 模型 | 59/140 | -0.375276 | ||
| 模型 </s> | 9/70 | -0.890856 | ||
| 傳統(tǒng) </s> | 79/140 | -0.248501 | ||
| 語(yǔ)言 </s> | 11/35 | -0.502675 |
進(jìn)一步整理成arpa格式， 可以發(fā)現(xiàn)與之前kenlm計(jì)算的結(jié)果一致
\data\ ngram 1=6 ngram 2=7\1-grams: -0.890856 <unk> 0 0 <s> -0.22184873 -0.69896996 傳統(tǒng) -0.30103 -0.69896996 語(yǔ)言 -0.30103 -0.46488678 模型 0 -0.89085555 </s> 0 -0.890856 <unk> 0\2-grams: -0.24850096 傳統(tǒng) </s> -0.44889864 <s> 模型 -0.56863624 <s> 語(yǔ)言 -0.6575773 <s> 傳統(tǒng) -0.37527603 語(yǔ)言 模型 -0.89085555 模型 </s> -0.50267535 語(yǔ)言 </s>\end\參考文獻(xiàn)
Scalable Modified Kneser-Ney Language Model Estimation: https://aclanthology.org/P13-2121.pdf
AI教室：傳統(tǒng)語(yǔ)言模型+KenLM 實(shí)現(xiàn)
總結(jié)
以上是生活随笔為你收集整理的手算KN-based ngram语言模型的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
- 上一篇： 2020电脑蓝屏代码大全
- 下一篇： BUGKU-CTF入门笔记