NLP プログラミング勉強会 12 – 係り受け解析

自然言語処理プログラミング勉強会 12係り受け解析

Graham Neubig
奈良先端科学技術大学院大学 (NAIST)1NLP プログラミング勉強会 12 – 係り受け解析

自然言語は曖昧性だらけ！
I saw a girl with a telescope●

構文解析（パージング）は構造的な曖昧性を解消
2

NLP プログラミング勉強会 12 – 係り受け解析

構文解析の種類●

係り受け解析 : 単語と単語のつながりを重視

I saw a girl with a telescope●

句構造解析 : 句とその再帰的な構造を重視
S
VP
PP
NP

NP

PRP VBD DT NNNPINDT

NN

I saw a girl with a telescope

3

NLP プログラミング勉強会 12 – 係り受け解析

係り受けを使った曖昧性解消

I saw a girl with a telescope

I saw a girl with a telescope

4

NLP プログラミング勉強会 12 – 係り受け解析

係り受けの種類●

ラベルあり : 単語間の関係の種類を記述
prepnsubj

dobj
detpobjdet

I saw a girl with a telescope●

ラベルなし : 関係の種類を問わず、親と子のみ

I saw a girl with a telescope

5

NLP プログラミング勉強会 12 – 係り受け解析

係り受け解析手法
●Shift-reduce
左から右へ貪欲的に解析● 高速（線形時間）、少し精度が低い● ソフト： MaltParser
●

●

全域木
文全体の係り受けを最適化● 精度が少し高く、スピードが少し落ちる● ソフト： MSTParser, Eda●●

チャンク同定の段階適用
1) 単語を句にチャンキング、 2) 主辞（親）を発見の繰り返し● ソフト： CaboCha●

6

NLP プログラミング勉強会 12 – 係り受け解析最大全域木
●各係り受けは有向グラフの辺●

機械学習を用いて辺に対してスコアを付与●

スコア最大の木を返す
グラフ

スコア付きグラフ

係り受け木saw

saw

saw

6girl

IaI-2-1

2

1

7

a6

4

girl

4girl

I
75a(Chu-Liu-Edmonds アルゴリズム )7

NLP プログラミング勉強会 12 – 係り受け解析

チャンク同定の段階適用●

親が必ず最後にくる日本語に対して有効●文をチャンクに分割、親を右の単語にする

私 は 望遠鏡 で
は
私

で
望遠鏡

は
私

女 の 子 を 見たの 子 を 見た
女

で
望遠鏡

子 を 見たの女
は
私

見たで
望遠鏡
女の子を 見た

はでを子
私 望遠鏡の8
女

NLP プログラミング勉強会 12 – 係り受け解析

Shift-Reduce●

左から右へ単語を１個ずつ処理●

2 つのデータ構造
キュー : 未処理の単語を格納● スタック : 処理中の単語を格納●●

各時点で 1 つの動作を選択
shift: 1 単語をキューからスタックへ移動● reduce 左 : スタックの１単語目は２単語目の親● reduce 右 : スタックの１単語目は２単語目の親●●

分類器を使ってどの動作を取るかを学習
9

NLP プログラミング勉強会 12 – 係り受け解析

Shift-Reduce の例
スタック

キュー

スタック

I saw a girlsaw a girlshiftIキューI
saw a girlr left

shift
I saw

sawa girl

shift

Igirl
ar leftsawa girl

II

sawI

shift
saw ar rightgirl

girla10NLP プログラミング勉強会 12 – 係り受け解析

Shift-Reduce のための分類●状態が与えられ：スタック

キュー

saw agirlI●

どの動作を選択 ?
shift ?

r left ?

saw a girlar right ?
girlsawIsawIgirla

I●

正しい選択 → 正しい係り受け木11

NLP プログラミング勉強会 12 – 係り受け解析

Shift-Reduce のための分類
●

●

●

●

「 shift 」「 reduce 左」「 reduce 右」の重みベクトル
ws wl wr
キューとスタックに基づいて素性関数を計算
φ(queue, stack)
素性関数と重みを掛け合わせてスコアを計算
ss = ws * φ(queue,stack)
スコアが最大の動作を利用
ss > sl && ss > sr → do shift

12

NLP プログラミング勉強会 12 – 係り受け解析

Shift-Reduce の素性●

素性は少なくともスタックの最後の２項目、キューの最初の項目をカバー

単語 :
品詞 :

stack[-2]stack[-1]queue[0]saw
VBDaDETgirl
NN(-2 → 最後から２番 )(-1 → 最後 )(0 → 最初 )φW-2saw,W-1a = 1

φW-1a,W0girl = 1

φW-2saw,P-1DET = 1

φW-1a,P0NN = 1

φP-2VBD,W-1a = 1

φP-1DET,W0girl = 1

φP-2VBD,P-1DET = 1

φP-1DET,P0NN = 1

13

NLP プログラミング勉強会 12 – 係り受け解析

アルゴリズムの定義●●

アルゴリズム ShiftReduce の入力 :●重み ws wl wr●

queue=[ (1, word1, POS1), (2, word2, POS2), …]

スタックは特別な ROOT 記号のみを格納 :●●stack = [ (0, “ROOT”, “ROOT”) ]戻り値は各単語の親の ID を格納した配列 :●heads = [ -1, head1, head2, … ]14NLP プログラミング勉強会 12 – 係り受け解析

Shift-Reduce アルゴリズム

ShiftReduce(queue)
make list heads
stack = [ (0, “ROOT”, “ROOT”) ]while |queue| > 0 or |stack| > 1:feats = MakeFeats(stack, queue)ss = ws * feats# “shift” のスコア
sl = wl * feats# “reduce left” のスコア
sr = wr * feats# “reduce right” のスコア
if ss >= sl and ss >= sr and |queue| > 0:
stack.push( queue.popleft() ) # shift を実行
elif sl >= sr:# reduce 左を実行
heads[ stack[-2].id ] = stack[-1].idstack.remove(-2)
else:# reduce 右を実行
heads[ stack[-1].id ] = stack[-2].idstack.remove(-1)

15

NLP プログラミング勉強会 12 – 係り受け解析

Shift-Reduce の学習●●●

パーセプトロンで学習可能解析を行い、正解 corr が分類器の戻り値 ans と異なる
際、重みを更新
例： if ans = SHIFT and corr = LEFT
ws -= φ(queue,stack)
wl += φ(queue,stack)16

NLP プログラミング勉強会 12 – 係り受け解析「正解」の計算 (1)●

各単語の親 head を知っている場合、とりあえず：
stack[-1].head == stack[-2].id→ corr = RIGHT( 左が右の親 )stack[-2].head == stack[-1].id→ corr = LEFT

( 右が左の親 )else→ corr = SHIFT●

問題 : reduce 右を速すぎる段階で実行！

gotoschool

stack[-2] stack[-1] queue[0]gotoschoolid:123
head: 012→ RIGHT
17

NLP プログラミング勉強会 12 – 係り受け解析「正解」の計算 (2)●

各単語の未処理の子供の数 unproc を考慮 :stack[-1].head == stack[-2].id( 右が左の親 )stack[-1].unproc == 0 ( 左に未処理の子供がない )→ corr = RIGHT
stack[-2].head == stack[-1].id( 左が右の親 )stack[-2].unproc == 0( 右に未処理の子供がない )→ corr = LEFTelse→ corr = SHIFT●

木を読み込みながらに unproc の初期値を計算
reduce を行うたびに unproc から１を引く
corr == RIGHT → stack[-1].unproc -= 1

18

NLP プログラミング勉強会 12 – 係り受け解析

Shift-Reduce の学習アルゴリズム
ShiftReduceTrain(queue)
make list heads
stack = [ (0, “ROOT”, “ROOT”) ]while |queue| > 0 or |stack| > 1:feats = MakeFeats(stack, queue)
calculate ans# ShiftReduce と同様
calculate corr
# 前のスライドと同様
if ans != corr:wans -= feats
wcorr += feats
perform action according to corr
19

NLP プログラミング勉強会 12 – 係り受け解析

CoNLL ファイル形式 :●係り受けの標準的な形式●

タブで区切られた行、空の１行で区切られた文
ID 単語
1 ms.
2 haag
3 plays
4 elianti
5 .

原型ms.
haag
plays
elianti.

品詞 品詞 2
NNP NNPNNP NNPVBZ VBZ
NNP NNP.
.

拡張 親_2
_3
_0
_
3
_3

ラベル
DEP
NP-SBJ
ROOT
NP-OBJ
DEP

20

NLP プログラミング勉強会 12 – 係り受け解析

演習課題

21

NLP プログラミング勉強会 12 – 係り受け解析

演習課題●

実装 train-sr.py test-sr.py●

学習data/mstparser­en­train.dep●

実行data/mstparser­en­test.dep●●

評価 精度を測る
script/grade­dep.pyチャレンジ素性の拡張● 識別学習アルゴリズムの改良● よくある誤りの分析●

22

NLP プログラミング勉強会 12 – 係り受け解析

Thank You!

23