NLP プログラミング勉強会 5 – HMM による品詞推定

自然言語処理プログラミング勉強会 5 隠れマルコフモデルによる品詞推定

Graham Neubig
奈良先端科学技術大学院大学 (NAIST)1NLP プログラミング勉強会 5 – HMM による品詞推定

品詞推定●

文 X が与えられた時の品詞列 Y を予測する

Natural language processing ( NLP ) is a field of computer science
JJ
●

NN

NN -LRB- NN -RRB- VBZ DT NN IN NN

NN

予測をどうやって行うか？

2

NLP プログラミング勉強会 5 – HMM による品詞推定

タグ付けの確率モデル●

文が与えられた場合、最も確率の高いタグ列を計算

Natural language processing ( NLP ) is a field of computer science
JJ

NN

NN LRB NN RRB VBZ DT NN IN NN

NNargmax P (Y∣X )Y●これをどうやってモデル化？
3

NLP プログラミング勉強会 5 – HMM による品詞推定

系列に対する生成モデル●

ベイズ則で確率を分解

P ( X∣Y ) P(Y )argmax P (Y∣X )=argmaxP (X )Y
Y=argmax P ( X∣Y ) P(Y )Y

前の品詞と次の品詞の関係を考慮
単語と品詞の関係を考慮「 natural 」はたぶん形容詞 (JJ) 名詞 (NN) が限定詞 (DET) に続く4

NLP プログラミング勉強会 5 – HMM による品詞推定

隠れマルコフモデル (HMM)

5

NLP プログラミング勉強会 5 – HMM による品詞推定

品詞推定のための (HMM)●

品詞→品詞の遷移確率●●

2-gram モデルとほぼ一緒

品詞→単語の生成確率

I+ 1P (Y )≈ ∏i=1 PT (y i∣y i−1 )IP (X∣Y )≈ ∏1 P E ( x i∣y i )PT(JJ|
) * PT(NN|JJ) * PT(NN|NN)




JJ

NN

NN…

LRB

NN

RRB

...

natural language processing (nlp)...

PE(natural|JJ) * PE(language|NN) * PE(processing|NN)

…




6

NLP プログラミング勉強会 5 – HMM による品詞推定

タグ付きコーパスからの HMM 学習●

コーパス中の頻度を数え上げ、natural language processing ( nlp )c(JJ→natural)++
c(
 JJ)++●c(NN→language)++

JJ

NN
c(JJ NN)++

NN

is …

…

LRB NN RRB VB … 
…

文脈の頻度で割ることで確率を求める
PT(LRB|NN) = c(NN LRB)/c(NN) = 1/3
PE(language|NN) = c(NN → language)/c(NN) = 1/3
7

NLP プログラミング勉強会 5 – HMM による品詞推定

学習アルゴリズム# 入力データ形式は「 natural_JJ language_NN … 」
make a map emit, transition, context
for each line in fileprevious = “
”# 文頭記号
context[previous]++split line into wordtags with “ “
for each wordtag in wordtags
split wordtag into word, tag with “_”transition[previous+“ “+tag]++ # 遷移を数え上げる
context[tag]++# 文脈を数え上げる
emit[tag+“ “+word]++# 生成を数え上げる
previous = tagtransition[previous+” 
”]++# 遷移確率を出力for each key, value in transition
split key into previous, word with “ “print “T”, key, value/context[previous]# 同じく生成確率を出力（「 T 」ではなく「 E 」を付与）

8

NLP プログラミング勉強会 5 – HMM による品詞推定

平滑化●2-gram モデルで平滑化を用いた：
PLM(wi|wi-1) = λ PML(wi|wi-1) + (1-λ) PLM(wi)●HMM 遷移確率：タグの数は少ないので平滑化は不要
PT(yi|yi-1) = PML(yi|yi-1)●

HMM 生成確率：未知語を扱うために平滑化が必要
PE(xi|yi) = λ PML(xi|yi) + (1-λ) 1/N
9

NLP プログラミング勉強会 5 – HMM による品詞推定

品詞推定の探索10

NLP プログラミング勉強会 5 – HMM による品詞推定

マルコフモデルを使った品詞推定●やはらビタビアルゴリズムを利用重要だと言っただろう！

●

品詞推定の探索グラフの形は？

11

NLP プログラミング勉強会 5 – HMM による品詞推定

HMM 品詞推定のグラフ●0:<S>

品詞推定の探索グラフの形：
naturallanguage processing

(nlp)

1:NN

2:NN

3:NN

4:NN

5:NN

6:NN

1:JJ

2:JJ

3:JJ

4:JJ

5:JJ

6:JJ

1:VB

2:VB

3:VB

4:VB

5:VB

6:VB …

1:LRB

2:LRB

3:LRB

4:LRB

5:LRB

6:LRB

1:RRB

2:RRB

3:RRB

4:RRB

5:RRB

6:RRB

…

…

…

…

…

…
12

NLP プログラミング勉強会 5 – HMM による品詞推定

HMM 品詞推定のグラフ●

各パスは品詞列を表す

0:<S>




naturallanguage processing

(nlp)

1:NN

2:NN

3:NN

4:NN

5:NN

6:NN

1:JJ

2:JJ

3:JJ

4:JJ

5:JJ

6:JJ

1:VB

2:VB

3:VB

4:VB

5:VB

6:VB

1:LRB

2:LRB

3:LRB

4:LRB

5:LRB

6:LRB

1:RRB

2:RRB

3:RRB

4:RRB

5:RRB

6:RRB

…

…

…

…

…

…

JJ

NN

NN

LRB

NN

RRB

…

13

NLP プログラミング勉強会 5 – HMM による品詞推定

復習：ビタビアルゴリズムのステップ●

前向きステップ：各ノードへたどる確率の計算●●

負の対数尤度がもっとも低くなるパス

後ろ向きステップ：パスの復元●

単語分割とほとんど同じ

14NLP プログラミング勉強会 5 – HMM による品詞推定

前向きステップ：文頭●

文頭記号 <S> から１単語目への遷移と１単語目の生成の確率
natural0:<S>

1:NN best_score[“1 NN”] = -log PT(NN|<S>) + -log PE(natural | NN)
1:JJ best_score[“1 JJ”] = -log PT(JJ|<S>) + -log PE(natural | JJ)
1:VB best_score[“1 VB”] = -log PT(VB|<S>) + -log PE(natural | VB)
1:LRB best_score[“1 LRB”] = -log PT(LRB|<S>) + -log PE(natural | LRB)
1:RRB best_score[“1 RRB”] = -log PT(RRB|<S>) + -log PE(natural | RRB)…

15NLP プログラミング勉強会 5 – HMM による品詞推定

前向きステップ：中間●

前の品詞を全部比べて、これまでのパス、遷移、生成を全て考慮した最短パスを利用

natural language
1:NN

2:NN

1:JJ

2:JJ

1:VB

2:VB

1:LRB

2:LRB

1:RRB

2:RRB

…

…

best_score[“2 NN”] = min(best_score[“1 NN”] + -log PT(NN|NN) + -log PE(language | NN),
best_score[“1 JJ”] + -log PT(NN|JJ) + -log PE(language | NN),
best_score[“1 VB”] + -log PT(NN|VB) + -log PE(language | NN),
best_score[“1 LRB”] + -log PT(NN|LRB) + -log PE(language | NN),
best_score[“1 RRB”] + -log PT(NN|RRB) + -log PE(language | NN),...
)
best_score[“2 JJ”] = min(best_score[“1 NN”] + -log PT(JJ|NN) + -log PE(language | JJ),
best_score[“1 JJ”] + -log PT(JJ|JJ) + -log PE(language | JJ),
best_score[“1 VB”] + -log PT(JJ|VB) + -log PE(language | JJ), 16...

NLP プログラミング勉強会 5 – HMM による品詞推定

前向きステップ：文末●

文末記号への遷移を考慮して終わり

science
I:NN
I:JJ
I:VB
I:LRB

I+1:</S>

best_score[“I+1 </S>”] = min(best_score[“I NN”] + -log PT(</S>|NN),
best_score[“I JJ”] + -log PT(</S>|JJ),
best_score[“I VB”] + -log PT(</S>|VB),
best_score[“I LRB”] + -log PT(</S>|LRB),
best_score[“I NN”] + -log PT(</S>|RRB),
...
)

I:RRB

…

17

NLP プログラミング勉強会 5 – HMM による品詞推定

実装：モデル読み込み
make a map for transition, emission, possible_tags
for each line in model_file
split line into type, context, word, prob
possible_tags[context] = 1 # 可能なタグとして保存
if type = “T”
transition[“context word”] = probelse
emission[“context word”] = prob

18NLP プログラミング勉強会 5 – HMM による品詞推定

実装：前向きステップ
split line into words
I = length(words)
make maps best_score, best_edge
best_score[“0 
”] = 0 # 
 から始まる
best_edge[“0 
”] = NULL
for i in 0 … I-1:
for each prev in keys of possible_tags
for each next in keys of possible_tags
if best_score[“i prev”] and transition[“prev next”] exist
score = best_score[“i prev”] +-log PT(next|prev) + -log PE(word[i]|next)
if best_score[“i+1 next”] is new or < score
best_score[“i+1 next”] = score
best_edge[“i+1 next”] = “i prev”# 最後、 
 に対して同じ操作を行う
19

NLP プログラミング勉強会 5 – HMM による品詞推定

実装：後ろ向きステップ
tags = [ ]next_edge = best_edge[ “I+1 
” ]while next_edge != “0 
”
# このエッジの品詞を出力に追加
split next_edge into position, tagappend tag to tags
next_edge = best_edge[ next_edge ]tags.reverse()
join tags into a string and print

20

NLP プログラミング勉強会 5 – HMM による品詞推定

演習問題

21

NLP プログラミング勉強会 5 – HMM による品詞推定

演習問題

●
●

●

●

train-hmm と test-hmm を実装
テスト：●

入力： test/05-{train,test}-input.txt●

正解： test/05-{train,test}-answer.txt

data/wiki-en-train.norm_pos を使ってモデルを学習し、 data/wiki-en-test.norm に対して品詞推定を行う

品詞推定の性能を評価して報告：

script/gradepos.pl data/wiki-en-test.pos my_answer.pos●

上級編：精度を向上させる方法を考える
22