NLP プログラミング勉強会 2 – n-gram 言語モデル

自然言語処理プログラミング勉強会 2n-gram 言語モデル

Graham Neubig
奈良先端科学技術大学院大学 (NAIST)1NLP プログラミング勉強会 2 – n-gram 言語モデル

先週の復習：文の確率計算●

文の確率が欲しいW = speech recognition system●

変数で以下のように表す ( 連鎖の法則を用いて ):P(|W| = 3, w1=”speech”, w2=”recognition”, w3=”system”) =P(w1=“speech” | w0 = “
”)* P(w2=”recognition” | w0 = “
”, w1=“speech”)* P(w3=”system” | w0 = “
”, w1=“speech”, w2=”recognition”)* P(w4=”
” | w0 = “
”, w1=“speech”, w2=”recognition”, w3=”system”)

注：
文頭「 
 」と文末「 
 」記号

注：
P(w0 = 
) = 1

2

NLP プログラミング勉強会 2 – n-gram 言語モデル

確率の漸次的な計算●前のスライドの積を以下のように一般化∣W ∣+ 1

P(W )=∏i =1 P( wi∣w 0 … wi−1 )●以下の条件付き確率の決め方は？

P( wi∣w 0 … wi−1 )3

NLP プログラミング勉強会 2 – n-gram 言語モデル

1-gram モデルは語順を考慮しない●

以下の確率は同等

Puni(w=speech recognition system) =P(w=speech) * P(w=recognition) * P(w=system) * P(w=
)=Puni(w=system recognition speech ) =P(w=speech) * P(w=recognition) * P(w=system) * P(w=
)

4NLP プログラミング勉強会 2 – n-gram 言語モデル

1-gram モデルは単語の関係性を考慮しない●

文法的な文：（名詞と活用が一致）

Puni(w=i am) =P(w=i) * P(w=am) * P(w=
)●Puni(w=we are) =P(w=we) * P(w=are) * P(w=
)

文法的でない文：（名詞と活用が矛盾）

Puni(w=we am) =Puni(w=i are) =P(w=we) * P(w=am) * P(w=
)P(w=i) * P(w=are) * P(w=
)

しかし、確率は上記の文と同等
5

NLP プログラミング勉強会 2 – n-gram 言語モデル

文脈を考慮することで解決！
●1-gram モデルは文脈を考慮しない

P( wi∣w 0 … wi−1 )≈P (w i)●

2-gram は１単語の文脈を考慮

P( wi∣w 0 … wi−1 )≈P (w i∣wi−1 )●3-gram は２単語の文脈を考慮

P( wi∣w 0 … wi−1 )≈P (w i∣wi− 2 w i−1)●4-gram 、 5-gram 、 6-gram などなど

6

NLP プログラミング勉強会 2 – n-gram 言語モデル

n-gram 確率の最尤推定●

n 単語と n-1 単語からなる文字列の頻度を利用

c (w i−n+ 1 … wi )P( wi∣w i−n+ 1 … wi−1 )=c ( wi− n+ 1 … wi−1)
i live in osaka . 
i am a graduate student . 

my school is in nara . 
P(osaka | in) = c(in osaka)/c(in) = 1 / 2 = 0.5
n=2 →P(nara | in) = c(in nara)/c(in) = 1 / 2 = 0.5
7NLP プログラミング勉強会 2 – n-gram 言語モデル

低頻度 n-gram の問題●

n-gram 頻度が 0→n-gram 確率も 0P(osaka | in)P(nara | in)= c(in osaka)/c(in) = 1 / 2 = 0.5= c(in nara)/c(in) = 1 / 2 = 0.5

P(school | in) = c(in school)/c(in) = 0 / 2 = 0!!
●

1-gram モデルと同じく、線形補間を用いる

2-gram:1-gram:P( wi∣w i−1)=λ 2 P ML (w i∣wi −1)+ (1−λ 2) P( wi )1P( wi )=λ1 P ML ( wi )+ (1−λ 1)
N
8NLP プログラミング勉強会 2 – n-gram 言語モデル

補間係数の選択法：グリッド探索●

λ2 と λ1 の様々な値を試し、尤度が最も高くなるように選択

λ 2=0.95, λ1 =0.95
λ 2=0.95, λ1 =0.90
λ 2=0.95, λ1 =0.85…
λ 2=0.95, λ1 =0.05
λ 2=0.90, λ1 =0.95
λ 2=0.90, λ1 =0.90…
λ 2=0.05, λ1 =0.10
λ 2=0.05, λ1 =0.05

問題 :選択肢が多すぎる→ 選択に時間がかかる！
全ての n-gram に対して同じ λ→ 尤度が最適とは限らない！

9NLP プログラミング勉強会 2 – n-gram 言語モデル

文脈を考慮した補間係数の選択●頻度の高い単語： Tokyo

頻度の低い単語： Tottoric(Tokyo city) = 40c(Tokyo is) = 35c(Tokyo was) = 24c(Tokyo tower) = 15c(Tokyo port) = 10…

c(Tottori is) = 2c(Tottori city) = 1c(Tottori was) = 0

ほとんどの 2-gram が既観測
→ 大きな λ が最適

未観測の 2-gram が多い→ 小さな λ が最適補間係数の選択にも文脈を考慮：

P( wi∣w i−1)=λ w P ML (w i∣wi−1 )+ (1−λ w ) P( wi )i−1i−1

10

NLP プログラミング勉強会 2 – n-gram 言語モデル

Witten-Bell 平滑化●λ w を選ぶ方法の１つi−1u( wi−1 )λ w =1−u( wi−1 )+ c ( wi −1)u( wi −1) = wi-1 の後に続く単語の異なり数
i−1●

例えば、c(Tottori is) = 2 c(Tottori city) = 1c(Tottori) = 3u(Tottori) = 2c(Tokyo city) = 40 c(Tokyo is) = 35 ...
c(Tokyo) = 270u(Tokyo) = 30

2
λ Tottori=1−=0.62+ 330
λ Tokyo =1−=0.930+ 270
11

NLP プログラミング勉強会 2 – n-gram 言語モデル

言語モデルのためのプログラミング技術

12

NLP プログラミング勉強会 2 – n-gram 言語モデル

配列への挿入●

文頭・文末記号を考慮するために以下の操作を利用
my_words = [“this”, “is”, “a”, “pen”]
my_words = [“
”, “this”, “is”, “a”, “pen”, “
”]●Python で append と insert 関数を利用
my_words.append(“
”) # 配列の最後い挿入
my_words.insert(0, “
”) # 配列の最初に挿入

13

NLP プログラミング勉強会 2 – n-gram 言語モデル

リストの一部の抜き出し●あるリストが与えられた時、 x-1 要素目から y 要素目を抜き出す
my_list[x:y]my_list = [“a”, “b”, “c”, “d”, “e”]
print my_list[1:3]# リストの 2 番と 3 番の要素をプリント
print my_list[:3]# リストの最初の 3 つの要素をプリント
print my_list[3:]# リストの 4 番目以降の要素をプリント
print my_list[:-2]# リストの最後の 2 つの要素以外をプリント●

n-gram wi-n+1 … wi が与えられた場合、文脈 wi-n+1 … wi-1の計算に利用
14

NLP プログラミング勉強会 2 – n-gram 言語モデル

演習問題

15

NLP プログラミング勉強会 2 – n-gram 言語モデル

演習問題●

2 つのプログラムを作成
train-bigram: 2-gram モデルを学習● test-bigram: 2-gram モデルに基づいて評価データのエントロピーを計算●●

テスト入力： test/02-train-input.txt●

学習データ： data/wiki-en-train.word●●

data/wiki-en-test.word に対してエントロピーを計算（線形補間を用いる場合、様々な λ2 を試す）
上級編：
●
●

Witten-Bell 平滑化を利用（線形補間の方が簡単）
任意な文脈長が利用可能なプログラムを作成

16

NLP プログラミング勉強会 2 – n-gram 言語モデル

train-bigram 擬似コード ( 線形補間 )create map counts, context_counts
for each line in the training_file
split line into an array of words
append “
” to the end and “
” to the beginning of words
for each i in 1 to length(words)-1 # 注： 
 の後に始まる
counts[“wi-1 wi”] += 1
# 2-gram の分子と分母を加算
context_counts[“wi-1”] += 1counts[“wi”] += 1
# 1-gram の分子と分母を加算
context_counts[“”] += 1
open the model_file for writingfor each ngram, count in counts
split ngram into an array of words # “wi-1 wi” → {“wi-1”, “wi”}
remove the last element of words # {“wi-1”, “wi”} → {“wi-1”}
join words into context# {“wi-1”} → “wi-1”
probability = counts[ngram]/context_counts[context]
print ngram, probability to model_file17

NLP プログラミング勉強会 2 – n-gram 言語モデル

test-bigram 擬似コード ( 線形補間 )λ1 = ???, λ2 = ???, V = 1000000, W = 0, H = 0
load model into probs
for each line in test_file
split line into an array of words
append “
” to the end and “
” to the beginning of words
for each i in 1 to length(words)-1# 注： 
 の後に始まる
P1 = λ1 probs[“wi”] + (1 – λ1) / V# 1-gram の平滑化された確率
P2 = λ2 probs[“wi-1 wi”] + (1 – λ2) * P1 # 2-gram の平滑化された確率
H += -log2(P2)W += 1
print “entropy = ”+H/W18