NLP プログラミング勉強会 11 – 構造化パーセプトロン

自然言語処理プログラミング勉強会 11
構造化パーセプトロン

Graham Neubig
奈良先端科学技術大学院大学 (NAIST)1NLP プログラミング勉強会 11 – 構造化パーセプトロン

予測問題
x が与えられた時y を予測する

本のレビュー「良い」評価なのか？ ２値予測
( 選択肢が２つ )Oh, man I love this book!
yesThis book is so boring...
noツイートOn the way to the park!
公園に行くなう！

書かれた言語EnglishJapanese

文

構文木
S

構造化予測
( 選択肢が膨大 )VP

I read a bookNPN

VBD DET

多クラス予測( 選択肢が数個 )NN

I read a book

2

NLP プログラミング勉強会 11 – 構造化パーセプトロン

予測問題
x が与えられた時y を予測する

本のレビュー「良い」評価なのか？ ２値予測
( 選択肢が２つ )Oh, man I love this book!
yesThis book is so boring...
noツイートOn the way to the park!
公園に行くなう！

書かれた言語EnglishJapanese文

自然言語処理のほとんど！
構造化予測( 選択肢が膨大 )

構文木
S
VP

I read a bookNPN

VBD DET

多クラス予測( 選択肢が数個 )NN

I read a book

3

NLP プログラミング勉強会 11 – 構造化パーセプトロン

今まで勉強した予測手法
２値分類器

生成モデル

パーセプトロン , SVM,ニューラルネット

HMM 品詞推定
PCFG 構文解析

多くの素性

最尤推定による確率推定

２値予測

構造予測

構造化パーセプトロン →構造予測に対して、多くの素性が利用可能！
4

NLP プログラミング勉強会 11 – 構造化パーセプトロン

構造化パーセプトロンの利用例●HMM 品詞推定

Collins “Discriminative Training Methods for Hidden Markov Models:Theory and Experiments with Perceptron Algorithms” ACL02●

構文解析
Huang+ “Forest Reranking: Discriminative Parsing with Non-LocalFeatures” ACL08●

機械翻訳
Liang+ “An End-to-End Discriminative Approach to MachineTranslation” ACL06(Neubig+ “Inducing a Discriminative Parser for Machine Translation
Reordering”, EMNLP12, ステマ :) )●識別言語モデルRoark+ “Discriminative Language Modeling with Conditional Random
Fields and the Perceptron Algorithm” ACL04
5

NLP プログラミング勉強会 11 – 構造化パーセプトロン

例：品詞推定●文 X が与えられた時の品詞列 Y を予測する

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

NN

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

NN「構造予測」に分類される

6

NLP プログラミング勉強会 11 – 構造化パーセプトロン

復習：品詞推定のための (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)

…




7NLP プログラミング勉強会 11 – 構造化パーセプトロン

素性はなぜ必要？
●

HMM なら、確率の兼ね合いなどに配慮が必要●

素性なら新しいアイデアをどんどん試せる
文中に大文字として現れるものは名詞が多い？
→「名詞＋大文字」素性の追加● 「 -ed 」や「 -ing 」で終わる単語は動詞が多い？
→「動詞 +-ed 」「動詞 +-ing 」素性の追加●

8

NLP プログラミング勉強会 11 – 構造化パーセプトロン

素性が使えるように HMM を変形
通常の HMM

II +1

P (X ,Y )=∏ 1 P E ( x i∣y i ) ∏i=1 PT ( y i∣y i−1 )9NLP プログラミング勉強会 11 – 構造化パーセプトロン

素性が使えるように HMM を変形
通常の HMM

対数尤度II +1

P (X ,Y )=∏ 1 P E ( x i∣y i ) ∏i=1 PT ( y i∣y i−1 )I

I+1logP ( X ,Y )=∑1 logP E ( x i∣y i ) ∑ i=1 logPT ( y i∣y i −1 )10

NLP プログラミング勉強会 11 – 構造化パーセプトロン

素性が使えるように HMM を変形
通常の HMM

対数尤度
スコア

II +1P (X ,Y )=∏ 1 P E ( x i∣y i ) ∏i=1 PT ( y i∣y i−1 )I

I+1logP ( X ,Y )=∑1 logP E ( x i∣y i ) ∑ i=1 logPT ( y i∣y i −1 )I

I+1S (X ,Y )=∑1 w E , y , x ∑ i=1 w E , yiii −1, yi

11

NLP プログラミング勉強会 11 – 構造化パーセプトロン

素性が使えるように HMM を変形
通常の HMM

II +1P (X ,Y )=∏ 1 P E ( x i∣y i ) ∏i=1 PT ( y i∣y i−1 )I

I+1logP ( X ,Y )=∑1 logP E ( x i∣y i ) ∑ i=1 logPT ( y i∣y i −1 )

対数尤度

I

I+1

S (X ,Y )=∑1 w E , y , x ∑ i=1 w E , y

スコア

iw E , y , x =log P E (x i∣y i )iiwT ,yi−1, yii=logP T ( y i∣y i−1 )log P(X,Y) = S(X,Y)

i −1, yiならが成り立つ
12

NLP プログラミング勉強会 11 – 構造化パーセプトロン

例：φ(IvisitedNara

PRP

VBDNNP)=

φT,<S>,PRP(X,Y1) = 1

φT,PRP,VBD(X,Y1) = 1

φE,PRP,”I”(X,Y1) = 1

φE,VBD,”visited”(X,Y1) = 1 φE,NNP,”Nara”(X,Y1) = 1

φ(φT,VBD,NNP(X,Y1) = 1

Ivisited

Nara

NNP

VBD

NNP

φT,NNP,</S>(X,Y1) = 1)=

φT,<S>,NNP(X,Y1) = 1

φT,NNP,VBD(X,Y1) = 1

φT,VBD,NNP(X,Y1) = 1

φT,NNP,</S>(X,Y1) = 1

φE,NNP,”I”(X,Y1) = 1

φE,VBD,”visited”(X,Y1) = 1 φE,NNP,”Nara”(X,Y1) = 113

NLP プログラミング勉強会 11 – 構造化パーセプトロン

例：φ(Ivisited

Nara

PRP

VBDNNP)=

φT,<S>,PRP(X,Y1) = 1

φT,PRP,VBD(X,Y1) = 1

φE,PRP,”I”(X,Y1) = 1

φE,VBD,”visited”(X,Y1) = 1 φE,NNP,”Nara”(X,Y1) = 1

φCAPS,PRP(X,Y1) = 1

φCAPS,NNP(X,Y1) = 1

φ(

φT,VBD,NNP(X,Y1) = 1

Ivisited

Nara

NNP

VBD

NNP

φT,NNP,</S>(X,Y1) = 1)=

φT,<S>,NNP(X,Y1) = 1

φT,NNP,VBD(X,Y1) = 1

φE,NNP,”I”(X,Y1) = 1

φE,VBD,”visited”(X,Y1) = 1 φE,NNP,”Nara”(X,Y1) = 1

φCAPS,NNP(X,Y1) = 2

φT,VBD,NNP(X,Y1) = 1

φT,NNP,</S>(X,Y1) = 114

NLP プログラミング勉強会 11 – 構造化パーセプトロン

例：φ(Ivisited

Nara

PRP

VBD

NNP)=

φT,<S>,PRP(X,Y1) = 1

φT,PRP,VBD(X,Y1) = 1

φE,PRP,”I”(X,Y1) = 1

φE,VBD,”visited”(X,Y1) = 1 φE,NNP,”Nara”(X,Y1) = 1

φCAPS,PRP(X,Y1) = 1

φCAPS,NNP(X,Y1) = 1

φ(φT,VBD,NNP(X,Y1) = 1

φT,NNP,</S>(X,Y1) = 1

φSUF,VBD,”...ed”(X,Y1) = 1

IvisitedNara

NNP

VBDNNP)=φT,<S>,NNP(X,Y1) = 1

φT,NNP,VBD(X,Y1) = 1

φT,VBD,NNP(X,Y1) = 1

φT,NNP,</S>(X,Y1) = 1

φE,NNP,”I”(X,Y1) = 1

φE,VBD,”visited”(X,Y1) = 1 φE,NNP,”Nara”(X,Y1) = 1

φCAPS,NNP(X,Y1) = 2

φSUF,VBD,”...ed”(X,Y1) = 1

15

NLP プログラミング勉強会 11 – 構造化パーセプトロン

最適解の探索●以下の式に従って最適解を見つけたいŶ =argmax Y ∑ i w i ϕi (X ,Y )16NLP プログラミング勉強会 11 – 構造化パーセプトロン

復習： HMM のビタビ探索●

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

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

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

単語分割とほとんど同じ

17

NLP プログラミング勉強会 11 – 構造化パーセプトロン

前向きステップ：文頭●

文頭記号 <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)…

18

NLP プログラミング勉強会 11 – 構造化パーセプトロン

前向きステップ：中間●

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

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), 19...

NLP プログラミング勉強会 11 – 構造化パーセプトロン

素性を使った HMM ビタビ●

確率と同じように素性を利用
I

0:<S>

1:NN best_score[“1 NN”] = wT,<S>,NN + wE,NN,I
1:JJ best_score[“1 JJ”] = wT,<S>,JJ + wE,JJ,I
1:VB best_score[“1 VB”] = wT,<S>,VB + wE,VB,I
1:PRP best_score[“1 PRP”] = wT,<S>,PRP + wE,PRP,I
1:NNP best_score[“1 NNP”] = wT,<S>,NNP + wE,NNP,I…

20

NLP プログラミング勉強会 11 – 構造化パーセプトロン

素性を使った HMM ビタビ●

他の素性も導入可能
I

0:<S>

1:NN best_score[“1 NN”] = wT,<S>,NN + wE,NN,I + wCAPS,NN1:JJ best_score[“1 JJ”] = wT,<S>,JJ + wE,JJ,I + wCAPS,JJ
1:VB best_score[“1 VB”] = wT,<S>,VB + wE,VB,I + wCAPS,VB
1:PRP best_score[“1 PRP”] = wT,<S>,PRP + wE,PRP,I + wCAPS,PRP
1:NNP best_score[“1 NNP”] = wT,<S>,NNP + wE,NNP,I + wCAPS,NNP…

21

NLP プログラミング勉強会 11 – 構造化パーセプトロン

構造化パーセプトロンの学習●

パーセプトロンアルゴリズムの重み更新●

誤りの場合：w ← w + y ϕ (x)
●

●

重みが：
正例に対して大きくなる
負例に対して小さくなる ように更新
構造化パーセプトロンの「正例」と「負例」とは ?

22

NLP プログラミング勉強会 11 – 構造化パーセプトロン

構造化パーセプトロンの学習●

正例：正しいタグ列に対する素性ベクトル

φ(●Ivisited

Nara

PRP

VBDNNP)

負例：正しくないタグ列に対する素性ベクトル

φ(Ivisited

Nara

NNP

VBDNNP)
23

NLP プログラミング勉強会 11 – 構造化パーセプトロン

負例の選び方●φ(

正しくない素性ベクトルがたくさん！
I

visited

Nara

NNP

VBD

NNP

φ(Ivisited

Nara

PRP

VBD

NN
visitedφ(●どれを利用するか？

)
I

PRP

VB)
Nara
NNP)
24

NLP プログラミング勉強会 11 – 構造化パーセプトロン

負例の選び方
●解決策：スコア最大の正しくない素性ベクトルを利用

Ŷ =argmax Y ∑ i w i ϕi (X ,Y )●更新式は：w ← w +ϕ (X , Y ' )−ϕ ( X , Ŷ )●●(Y' は正しいタグ列 )注：スコア最大のタグ列が正解の場合、変更なし
25

NLP プログラミング勉強会 11 – 構造化パーセプトロン

構造化パーセプトロンアルゴリズム
create map w
for I iterations
for each labeled pair X, Y_prime in the data
Y_hat = hmm_viterbi(w, X)
phi_prime = create_features(X, Y_prime)
phi_hat = create_features(X, Y_hat)w += phi_prime - phi_hat

26

NLP プログラミング勉強会 11 – 構造化パーセプトロン

HMM の素性計算●

各遷移、生成に対して素性構築関数を作成

create_trans( NNP,VBD)

create_emit( NNP,Nara )φ[“T,NNP,VBD”] = 1

φ[“E,NNP,Nara”] = 1
φ[“CAPS,NNP”] = 127

NLP プログラミング勉強会 11 – 構造化パーセプトロン

構造化パーセプトロンの素性計算●

単語列の素性を構築する create_features 関数
create_features(X, Y):
create map phi
for i in 0 .. |Y|:
if i == 0: first_tag = “
”else:first_tag = Y[i-1]
if i == |Y|: next_tag = “
”else:
next_tag = Y[i]phi += create_trans(first_tag, next_tag)
for i in 0 .. |Y|-1:
phi += create_emit(Y[i], X[i])return phi28

NLP プログラミング勉強会 11 – 構造化パーセプトロン

素性を使ったビタビアルゴリズム
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)
w*(create_t(prev,next)+create_e(next,word[i]))if best_score[“i+1 next”] is new or < score
best_score[“i+1 next”] = score
best_edge[“i+1 next”] = “i prev”
29# 
 に対して同様の処理

NLP プログラミング勉強会 11 – 構造化パーセプトロン

演習課題

30

NLP プログラミング勉強会 11 – 構造化パーセプトロン

演習課題●

実装 train-hmm-percep と test-hmm-percep

●

テスト

●

●

●

入力 : 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●●

比較 通常の生成モデルを用いた HMM とチャレンジ
新しい素性を導入
平均化、マージン、正則化などの識別学習を利用

31

NLP プログラミング勉強会 11 – 構造化パーセプトロン

Thank You!

32