NLP プログラミング勉強会 8 – 句構造解析
自然言語処理プログラミング勉強会 8 句構造解析
Graham Neubig
奈良先端科学技術大学院大学 (NAIST)
1
NLP プログラミング勉強会 8 – 句構造解析
自然言語は曖昧性だらけ!
I saw a girl with a telescope
●
構文解析(パージング)は構造的な曖昧性を解消
2
NLP プログラミング勉強会 8 – 句構造解析
構文解析の種類
●
係り受け解析 : 単語と単語のつながりを重視
I saw a girl with a telescope
●
句構造解析 : 句とその再帰的な構造を重視
S
VP
PP
NP
NP
PRP VBD DT NN
NP
IN
DT
NN
I saw a girl with a telescope
3
NLP プログラミング勉強会 8 – 句構造解析
句の再帰的な構造
S
VP
PP
NP
NP
PRP
I
VBD
saw
DT NN
a girl
NP
IN
DT
NN
with a telescope
4
NLP プログラミング勉強会 8 – 句構造解析
句の再帰的な構造
S
VP
PP
NP
NP
PRP
I
VBD
saw
DT NN
a girl
NP
IN
DT
NN
with a telescope
5
NLP プログラミング勉強会 8 – 句構造解析
句の再帰的な構造
S
VP
???
PP
NP
NP
PRP
I
VBD
saw
DT NN
a girl
NP
IN
DT
NN
with a telescope
6
NLP プログラミング勉強会 8 – 句構造解析
句の再帰的な構造
S
VP
???
PP
NP
NP
PRP
I
VBD
saw
DT NN
a girl
NP
IN
DT
NN
with a telescope
7
NLP プログラミング勉強会 8 – 句構造解析
句の再帰的な構造
S
VP
???
PP
NP
NP
PRP
I
VBD
saw
DT NN
a girl
NP
IN
DT
NN
with a telescope
8
NLP プログラミング勉強会 8 – 句構造解析
違う構造→違う解釈
S
VP
???
NP
PP
NP
NP
PRP
I
VBD
saw
DT NN
a girl
NP
IN
DT
NN
with a telescope
9
NLP プログラミング勉強会 8 – 句構造解析
違う構造→違う解釈
S
VP
???
NP
PP
NP
NP
PRP
I
VBD
saw
DT NN
a girl
NP
IN
DT
NN
with a telescope
10
NLP プログラミング勉強会 8 – 句構造解析
違う構造→違う解釈
S
VP
???
NP
PP
NP
NP
PRP
I
VBD
saw
DT NN
a girl
NP
IN
DT
NN
with a telescope
11
NLP プログラミング勉強会 8 – 句構造解析
違う構造→違う解釈
S
VP
???
NP
PP
NP
NP
PRP
I
VBD
saw
DT NN
a girl
NP
IN
DT
NN
with a telescope
12
NLP プログラミング勉強会 8 – 句構造解析
非終端記号、前終端記号、終端記号
S
VP
非終端記号
PP
NP
NP
前終端記号
終端記号
PRP
I
VBD
saw
DT NN
a girl
NP
IN
DT
NN
with a telescope
13
NLP プログラミング勉強会 8 – 句構造解析
予測問題としての構文解析
●
文 X が与えられ、構文木 Y を予測
S
VP
PP
NP
NP
NP
PRP VBD DT NN
IN
DT
NN
I saw a girl with a telescope
●
「構造予測」の問題(品詞推定、単語分割と同様)
14
NLP プログラミング勉強会 8 – 句構造解析
構文解析の確率モデル
●
文 X が与えられ、事後確率の最も高い構文木 Y を予測
S
VP
PP
NP
NP
PRP VBD DT NN
NP
IN
DT
NN
I saw a girl with a telescope
argmax P (Y∣X )
Y
15
NLP プログラミング勉強会 8 – 句構造解析
生成モデル
●
構文木 Y と文 X が同時に確率モデルにより生成された
とする
P(Y , X )
●
X を固定すると、同時確率が最も高い Y は事後確率も
最も高い
argmax P (Y∣X )=argmax P(Y , X)
Y
Y
16
NLP プログラミング勉強会 8 – 句構造解析
確率的文脈自由文法 (PCFG)
●
構文木の同時確率をどう定義するか?
S
VP
P(
)
PP
NP
NP
PRP VBD DT NN
NP
IN
DT
NN
I saw a girl with a telescope
17
NLP プログラミング勉強会 8 – 句構造解析
確率的文脈自由文法 (PCFG)
●
PCFG :各ノードの確率を個別に定義
P(S → NP VP)
S
VP
P(VP → VBD NP PP)
P(PP → IN NP)
PP
P(PRP → “I”) NP
NP
PRP VBD DT NN
NP
IN
DT
P(NP → DT NN)
NN
P(NN → “telescope”)
I saw a girl with a telescope
18
NLP プログラミング勉強会 8 – 句構造解析
確率的文脈自由文法 (PCFG)
●
PCFG :各ノードの確率を個別に定義
P(S → NP VP)
S
VP
P(VP → VBD NP PP)
P(PP → IN NP)
PP
P(PRP → “I”) NP
NP
PRP VBD DT NN
NP
IN
DT
P(NP → DT NN)
NN
P(NN → “telescope”)
I saw a girl with a telescope
●
構文木の確率はノードの確率の積
P(S → NP VP) * P(NP → PRP) * P(PRP → “I”)
* P(VP → VBD NP PP) * P(VBD → “saw”) * P(NP → DT NN)
* P(DT → “a”) * P(NN → “girl”) * P(PP → IN NP) * P(IN → “with”)
19
* P(NP → DT NN) * P(DT → “a”) * P(NN → “telescope”)
NLP プログラミング勉強会 8 – 句構造解析
確率的構文解析
●
構文解析は確率が最大の構文木を探索すること
argmax P (Y , X )
Y
●
ビタビアルゴリズムは利用可能か?
20
NLP プログラミング勉強会 8 – 句構造解析
確率的構文解析
●
構文解析は確率が最大の構文木を探索すること
argmax P (Y , X )
Y
●
ビタビアルゴリズムは利用可能か?
●
●
答え:いいえ!
理由:構文木の候補はグラフで表せず超グラフとなる
21
NLP プログラミング勉強会 8 – 句構造解析
超グラフとは?
●
2 つの構文木があ
るとする
S
0,7
VP
1,7 NP
2,7
S
0,7
PP
4,7
NP
0,1
VP
1,7
PRP VBD DT
0,1 1,2 2,3
PP
4,7
NP
0,1
NP
2,4
PRP VBD DT
0,1 1,2 2,3
NP
5,7
NN
3,4
IN
4,5
DT
5,6
NP
2,4
NP
5,7
NN
3,4
IN
4,5
DT
5,6
NN
6,7
I saw a girl with a telescope
NN
6,7
I saw a girl with a telescope
22
NLP プログラミング勉強会 8 – 句構造解析
超グラフとは?
●
その大半は同じ
S
0,7
VP
1,7 NP
2,7
S
0,7
PP
4,7
NP
0,1
VP
1,7
PRP VBD DT
0,1 1,2 2,3
PP
4,7
NP
0,1
NP
2,4
PRP VBD DT
0,1 1,2 2,3
NP
5,7
NN
3,4
IN
4,5
DT
5,6
NP
2,4
NP
5,7
NN
3,4
IN
4,5
DT
5,6
NN
6,7
I saw a girl with a telescope
NN
6,7
I saw a girl with a telescope
23
NLP プログラミング勉強会 8 – 句構造解析
超グラフとは?
●
両方に現れるエッジだけを残すと:
S
0,7
VP
1,7
NP
2,7
PP
4,7
NP
0,1
PRP VBD
0,1 1,2
I saw
NP
2,4
DT
2,3
NP
5,7
NN
3,4
IN
4,5
DT
5,6
NN
6,7
a girl with a telescope
24
NLP プログラミング勉強会 8 – 句構造解析
超グラフとは?
●
1 番目の構文木のみに存在するエッジを追加:
S
0,7
VP
1,7
NP
2,7
PP
4,7
NP
0,1
PRP VBD
0,1 1,2
I saw
NP
2,4
DT
2,3
NP
5,7
NN
3,4
IN
4,5
DT
5,6
NN
6,7
a girl with a telescope
25
NLP プログラミング勉強会 8 – 句構造解析
超グラフとは?
●
2 番目の構文木のみに存在するエッジを追加:
S
0,7
VP
1,7
NP
2,7
PP
4,7
NP
0,1
PRP VBD
0,1 1,2
I saw
NP
2,4
DT
2,3
NP
5,7
NN
3,4
IN
4,5
DT
5,6
NN
6,7
a girl with a telescope
26
NLP プログラミング勉強会 8 – 句構造解析
超グラフとは?
●
両方の構文木のみに存在するエッジを追加:
S
0,7
VP
1,7
ここで 2 択:
赤を選択すると 1 番目構文木
青を選択すると 2 番目構文木
NP
2,7
PP
4,7
NP
0,1
PRP VBD
0,1 1,2
I saw
NP
2,4
DT
2,3
NP
5,7
NN
3,4
IN
4,5
DT
5,6
NN
6,7
a girl with a telescope
27
NLP プログラミング勉強会 8 – 句構造解析
なぜ「超」グラフ?
●
エッジの「次数」は子の数
次数 1
PRP
0,1
VBD
1,2
I
saw
次数 2
次数 3
VP
1,7
VP
1,7
VBD
1,2
VBD
1,2
NP
2,7
NP
2,4
●
超グラフの次数はエッジの次数の最大値
●
グラフは次数 1 の超グラフ!
PP
4,7
1.4
例→
0
2.5
1
4.0
2
2.1
2.3
3
28
NLP プログラミング勉強会 8 – 句構造解析
重み付き超グラフ
●
グラフと同じく:
●
●
超グラフのエッジに重みを付与
負の対数確率(ビタビアルゴリズムと同等の理由)
S
0,7
-log(P(S → PRP VP))
-log(P(VP → VBD NP PP))
-log(P(VP → VBD NP))
VP
1,7
NP
2,7
PP
4,7
NP
0,1
log(P(PRP → “I”))
PRP VBD
0,1 1,2
I saw
NP
2,4
DT
2,3
NP
5,7
NN
3,4
IN
4,5
DT
5,6
NN
6,7
a girl with a telescope
29
NLP プログラミング勉強会 8 – 句構造解析
超グラフの探索法
●
構文解析=超グラフの最もスコアの小さい木を探索
30
NLP プログラミング勉強会 8 – 句構造解析
超グラフの探索法
●
構文解析=超グラフの最もスコアの小さい木を探索
●
グラフではビタビアルゴリズムを利用
●
●
前向きステップ : 各ノードまでの最短経路を計算
後ろ向き : 最短経路を復元
31
NLP プログラミング勉強会 8 – 句構造解析
超グラフの探索法
●
構文解析=超グラフの最もスコアの小さい木を探索
●
グラフではビタビアルゴリズムを利用
●
●
●
前向きステップ : 各ノードまでの最短経路を計算
後ろ向き : 最短経路を復元
超グラフもほとんど同等のアルゴリズム
●
●
内ステップ : 各ノードの最小部分木のスコアを計算
外ステップ : スコア最小の木を復元
32
NLP プログラミング勉強会 8 – 句構造解析
復習:ビタビアルゴリズム
e2 1.4
0
2.5
e1
1
4.0
e3
2
2.3
e5
2.1 e4
3
best_score[0] = 0
for each node in the graph ( 昇順 )
best_score[node] = ∞
for each incoming edge of node
score = best_score[edge.prev_node] + edge.score
if score < best_score[node]
best_score[node] = score
33
best_edge[node] = edge
NLP プログラミング勉強会 8 – 句構造解析
例:
1.4
0
0.0
2.5
e1
1
∞
e2
4.0
e3
2
∞
2.1
2.3
e5
3
∞
e4
初期化 :
best_score[0] = 0
34
NLP プログラミング勉強会 8 – 句構造解析
例:
1.4
0
0.0
2.5
e1
1
2.5
e2
4.0
e3
2
∞
2.3
e5
2.1
3
∞
e4
初期化 :
best_score[0] = 0
e1 を計算 :
score = 0 + 2.5 = 2.5 (< ∞)
best_score[1] = 2.5
best_edge[1] = e1
35
NLP プログラミング勉強会 8 – 句構造解析
例:
1.4
0
0.0
2.5
e1
1
2.5
e2
4.0
e3
2
1.4
2.3
e5
2.1
3
∞
e4
初期化 :
best_score[0] = 0
e1 を計算 :
score = 0 + 2.5 = 2.5 (< ∞)
best_score[1] = 2.5
best_edge[1] = e1
e2 を計算 :
score = 0 + 1.4 = 1.4 (< ∞)
best_score[2] = 1.4
best_edge[2] = e2
36
NLP プログラミング勉強会 8 – 句構造解析
例:
1.4
0
0.0
2.5
e1
1
2.5
e2
4.0
e3
2
1.4
2.3
e5
2.1
初期化 :
best_score[0] = 0
e4
3
∞
e3 を計算 :
score = 2.5 + 4.0 = 6.5 (> 1.4)
変更なし !
e1 を計算 :
score = 0 + 2.5 = 2.5 (< ∞)
best_score[1] = 2.5
best_edge[1] = e1
e2 を計算 :
score = 0 + 1.4 = 1.4 (< ∞)
best_score[2] = 1.4
best_edge[2] = e2
37
NLP プログラミング勉強会 8 – 句構造解析
例:
1.4
0
0.0
2.5
e1
1
2.5
e2
4.0
e3
2
1.4
2.3
e5
2.1
初期化 :
best_score[0] = 0
e1 を計算 :
score = 0 + 2.5 = 2.5 (< ∞)
best_score[1] = 2.5
best_edge[1] = e1
e4
3
4.6
e3 を計算 :
score = 2.5 + 4.0 = 6.5 (> 1.4)
変更なし !
e4 を計算 :
score = 2.5 + 2.1 = 4.6 (< ∞)
best_score[3] = 4.6
best_edge[3] = e4
e2 を計算 :
score = 0 + 1.4 = 1.4 (< ∞)
best_score[2] = 1.4
best_edge[2] = e2
38
NLP プログラミング勉強会 8 – 句構造解析
例:
1.4
0
0.0
2.5
e1
1
2.5
e2
4.0
e3
2
1.4
2.3
e5
2.1
初期化 :
best_score[0] = 0
e4
3
3.7
e3 を計算 :
score = 2.5 + 4.0 = 6.5 (> 1.4)
変更なし !
e1 を計算 :
e4 を計算 :
e2 を計算 :
e5 を計算 :
score = 0 + 2.5 = 2.5 (< ∞)
best_score[1] = 2.5
best_edge[1] = e1
score = 0 + 1.4 = 1.4 (< ∞)
best_score[2] = 1.4
best_edge[2] = e2
score = 2.5 + 2.1 = 4.6 (< ∞)
best_score[3] = 4.6
best_edge[3] = e4
score = 1.4 + 2.3 = 3.7 (< 4.6)
best_score[3] = 3.7
39
best_edge[3] = e5
NLP プログラミング勉強会 8 – 句構造解析
前向きステップの結果:
e2 1.4
0
0.0
2.5
e1
1
2.5
4.0
e3
2
1.4
2.3
e5
3
3.7
2.1 e4
best_score = ( 0.0, 2.5, 1.4, 3.7 )
best_edge = ( NULL, e1, e2, e5 )
40
NLP プログラミング勉強会 8 – 句構造解析
後ろ向きステップ
41
NLP プログラミング勉強会 8 – 句構造解析
後ろ向きステップのアルゴリズム
e2 1.4
0
0.0
2.5
e1
1
2.5
4.0
e3
2
1.4
2.3
e5
3
3.7
2.1 e4
best_path = [ ]
next_edge = best_edge[best_edge.length – 1]
while next_edge != NULL
add next_edge to best_path
next_edge = best_edge[next_edge.prev_node]
reverse best_path
42
NLP プログラミング勉強会 8 – 句構造解析
e2 1.4
0
0.0
2.5
e1
初期化 :
1
2.5
4.0
e3
2
1.4
2.3
e5
3
3.7
2.1 e4
best_path = []
next_edge = best_edge[3] = e5
43
NLP プログラミング勉強会 8 – 句構造解析
後ろ向きステップの例
e2 1.4
0
0.0
2.5
e1
初期化 :
1
2.5
4.0
e3
2
1.4
2.3
e5
3
3.7
2.1 e4
best_path = []
next_edge = best_edge[3] = e5
e5 を計算 :
best_path = [e5]
next_edge = best_edge[2] = e2
44
NLP プログラミング勉強会 8 – 句構造解析
後ろ向きステップの例
e2 1.4
0
0.0
2.5
e1
初期化 :
1
2.5
4.0
e3
2
1.4
2.3
e5
2.1 e4
best_path = []
next_edge = best_edge[3] = e5
3
3.7
e2 を計算 :
best_path = [e5, e2]
next_edge = best_edge[0] = NULL
e5 を計算 :
best_path = [e5]
next_edge = best_edge[2] = e2
45
NLP プログラミング勉強会 8 – 句構造解析
後ろ向きステップの例
e2 1.4
0
0.0
2.5
e1
初期化 :
1
2.5
4.0
e3
2
1.4
2.3
e5
2.1 e4
best_path = []
next_edge = best_edge[3] = e5
e5 を計算 :
best_path = [e5]
next_edge = best_edge[2] = e2
3
3.7
e5 を計算 :
best_path = [e5, e2]
next_edge = best_edge[0] = NULL
逆順に並べ替え :
best_path = [e2, e5]
46
NLP プログラミング勉強会 8 – 句構造解析
ノードの内ステップ
VP1,7 の最小スコアを計算
●
VP
1,7
e2
e1
NP
2,7
PP
4,7
NP
2,4
VBD
1,2
47
NLP プログラミング勉強会 8 – 句構造解析
ノードの内ステップ
VP1,7 の最小スコアを計算
●
VP
1,7
e2
e1
PP
4,7
NP
2,4
VBD
1,2
NP
2,7
score(e1) =
-log(P(VP → VBD NP PP)) +
best_score[VBD1,2] +
best_score[NP2,4] +
best_score[NP2,7]
score(e2) =
-log(P(VP → VBD NP)) +
best_score[VBD1,2] +
best_score[VBD2,7]
48
NLP プログラミング勉強会 8 – 句構造解析
ノードの内ステップ
VP1,7 の最小スコアを計算
●
VP
1,7
e2
e1
PP
4,7
NP
2,4
VBD
1,2
NP
2,7
score(e1) =
-log(P(VP → VBD NP PP)) +
best_score[VBD1,2] +
best_score[NP2,4] +
best_score[NP2,7]
score(e2) =
-log(P(VP → VBD NP)) +
best_score[VBD1,2] +
best_score[VBD2,7]
best_edge[VB1,7] = argmine1,e2 score
49
NLP プログラミング勉強会 8 – 句構造解析
ノードの内ステップ
VP1,7 の最小スコアを計算
●
VP
1,7
e2
e1
PP
4,7
NP
2,4
VBD
1,2
NP
2,7
score(e1) =
-log(P(VP → VBD NP PP)) +
best_score[VBD1,2] +
best_score[NP2,4] +
best_score[NP2,7]
score(e2) =
-log(P(VP → VBD NP)) +
best_score[VBD1,2] +
best_score[VBD2,7]
best_edge[VB1,7] = argmine1,e2 score
best_score[VB1,7] =
50
score(best_edge[VB1,7])
NLP プログラミング勉強会 8 – 句構造解析
文法からの超グラフ構築
●
超グラフは解けるが、構文解析で与えられるのは
文法
P(S → NP VP) = 0.8
P(S → PRP VP) = 0.2
P(VP → VBD NP PP) = 0.6
P(VP → VBD NP)= 0.4
P(NP → DT NN) = 0.5
P(NP → NN) = 0.5
P(PRP → “I”) = 0.4
P(VBD → “saw”) = 0.05
P(DT → “a”) = 0.6
...
●
文
I saw a girl with a telescope
解くための超グラフをどうやって構築するか?
51
NLP プログラミング勉強会 8 – 句構造解析
CKY アルゴリズム
●
●
CKY(Cocke-Kasami-Younger) アルゴリズムは文法に
基づいてハイパーグラフを構築して解く
文法はチョムスキー標準形 (CNF)
●
ルールの右側は非終端記号 2 つもしくは終端記号 1 つ
OK
S → NP VP
S → PRP VP
VP → VBD NP
●
OK
Not OK!
PRP → “I”
VBD → “saw”
DT → “a”
VP → VBD NP PP
NP → NN
NP → PRP
この条件を満たさないルールは変更可能
VP → VBD NP PP
NP → PRP + PRP → “I”
VP → VBD NP_PP
NP_PP → NP PP
NP → “I”
52
NLP プログラミング勉強会 8 – 句構造解析
CKY アルゴリズム
●
まずは終端記号のルールをスコア付きで展開
1.0
PRP NP
0,1 0,1 0.5
I
VP VBD
3.2 1,2 1,2 1.4
saw
PRP
2.4 2,3
NP
2,3 2.6
him
53
NLP プログラミング勉強会 8 – 句構造解析
CKY アルゴリズム
●
0,2 のノードを全て展開
S
4.7 0,2
1.0
PRP NP
0,1 0,1 0.5
I
SBAR
5.3
0,2
VP VBD
3.2 1,2 1,2 1.4
saw
PRP
2.4 2,3
NP
2,3 2.6
him
54
NLP プログラミング勉強会 8 – 句構造解析
CKY アルゴリズム
●
1,3 のノードを全て展開
S
4.7 0,2
1.0
PRP NP
0,1 0,1 0.5
I
SBAR
5.3
0,2
VP VBD
3.2 1,2 1,2 1.4
saw
VP
1,3
5.0
PRP
2.4 2,3
NP
2,3 2.6
him
55
NLP プログラミング勉強会 8 – 句構造解析
CKY アルゴリズム
●
0,3 のノードを全て展開
6.1
SBAR
0,3
S
4.7 0,2
1.0
PRP NP
0,1 0,1 0.5
I
S
5.9
0,3
SBAR
5.3
0,2
VP VBD
3.2 1,2 1,2 1.4
saw
VP
1,3
5.0
PRP
2.4 2,3
NP
2,3 2.6
him
56
NLP プログラミング勉強会 8 – 句構造解析
CKY アルゴリズム
●
文を全てカバーする「 S 」ノードを見つけて、エッジ
を展開
6.1
SBAR
0,3
S
4.7 0,2
1.0
PRP NP
0,1 0,1 0.5
I
S
5.9
0,3
SBAR
5.3
0,2
VP VBD
3.2 1,2 1,2 1.4
saw
VP
1,3
5.0
PRP
2.4 2,3
NP
2,3 2.6
him
57
NLP プログラミング勉強会 8 – 句構造解析
CKY アルゴリズム
●
左の子、右の子を再帰的に展開
6.1
SBAR
0,3
S
4.7 0,2
1.0
PRP NP
0,1 0,1 0.5
I
S
5.9
0,3
SBAR
5.3
0,2
VP VBD
3.2 1,2 1,2 1.4
saw
VP
1,3
5.0
PRP
2.4 2,3
NP
2,3 2.6
him
58
NLP プログラミング勉強会 8 – 句構造解析
CKY アルゴリズム
●
左の子、右の子を再帰的に展開
6.1
SBAR
0,3
S
4.7 0,2
1.0
PRP NP
0,1 0,1 0.5
I
S
5.9
0,3
SBAR
5.3
0,2
VP VBD
3.2 1,2 1,2 1.4
saw
VP
1,3
5.0
PRP
2.4 2,3
NP
2,3 2.6
him
59
NLP プログラミング勉強会 8 – 句構造解析
CKY アルゴリズム
●
左の子、右の子を再帰的に展開
6.1
SBAR
0,3
S
4.7 0,2
1.0
PRP NP
0,1 0,1 0.5
I
S
5.9
0,3
SBAR
5.3
0,2
VP VBD
3.2 1,2 1,2 1.4
saw
VP
1,3
5.0
PRP
2.4 2,3
NP
2,3 2.6
him
60
NLP プログラミング勉強会 8 – 句構造解析
CKY アルゴリズム
●
左の子、右の子を再帰的に展開
6.1
SBAR
0,3
S
4.7 0,2
1.0
PRP NP
0,1 0,1 0.5
I
S
5.9
0,3
SBAR
5.3
0,2
VP VBD
3.2 1,2 1,2 1.4
saw
VP
1,3
5.0
PRP
2.4 2,3
NP
2,3 2.6
him
61
NLP プログラミング勉強会 8 – 句構造解析
構文木の出力
●
構文木の出力:「 Penn Treebank 形式」( S 式)
PP
NP
IN
DT
NN
with a telescope
(PP
(IN with)
(NP
(DT a)
(NN telescope)))
62
NLP プログラミング勉強会 8 – 句構造解析
構文木の出力
●
再帰を使うと簡単に出力できる:
print(S0,7) = “(S “ + print(NP0,1) + “ “ + print(VP1,7)+”)”
print(NP0,1) = “(NP “ + print(PRP0,1) + ”)”
print(PRP0,1) = “(PRP I)”
S
0,7
VP
1,7
...
PP
4,7
NP
0,1
PRP VBD
0,1 1,2
I saw
NP
2,4
DT
2,3
NP
5,7
NN
3,4
IN
4,5
DT
5,6
NN
6,7
a girl with a telescope
63
NLP プログラミング勉強会 8 – 句構造解析
擬似コード
64
NLP プログラミング勉強会 8 – 句構造解析
CKY 擬似コード : 文法の読み込み
# “lhs \t rhs \t prob \n” 形式の文法を読み込む
make list nonterm # ( 左 , 右 1, 右 2, 確率 ) の非終端記号
make map preterm # pre[ 右 ] = [ ( 左 , 確率 ) ...] 形式のマップ
for rule in grammar_file
split rule into lhs, rhs, prob (with “\t”) # P( 左→右 )= 確率
split rhs into rhs_symbols (with “ “) if length(rhs) == 1: # 前終端記号
add (lhs, log(prob)) to preterm[rhs]
else: # 非終端記号
add (lhs, rhs[0], rhs[1], log(prob)) to nonterm
65
NLP プログラミング勉強会 8 – 句構造解析
CKY 擬似コード : 前終端記号を追加
split line into words
make map best_score # 引数 =symi,j 値 = 最大対数確率
make map best_edge # 引数 =symi,j 値 =(lsymi,k, rsymk,j)
# 前終端記号を追加
for i in 0 .. length(words)-1:
for lhs, log_prob in preterm where P(lhs → words[i]) > 0:
best_score[lhsi,i+1] = [log_prob]
66
NLP プログラミング勉強会 8 – 句構造解析
CKY 擬似コード :
非終端記号の組み合わせ
for j in 2 .. length(words): # j はスパンの右側
for i in j-2 .. 0:
# i はスパンの左側 ( 右から左へ処理 !)
for k in i+1 .. j-1:
# k は rsym の開始点
# 各文法ルールを展開 :log(P(sym → lsym rsym)) = logprob
for sym, lsym, rsym, logprob in nonterm:
# 両方の子供の確率が 0 より大きい
if best_score[lsymi,k] > -∞ and best_score[rsymk,j] > -∞:
# このノード・辺の対数確率を計算
my_lp = best_score[lsymi,k] + best_score[rsymk,j] + logprob
# この辺が確率最大のものなら更新
if my_lp > best_score[symi,j]:
best_score[symi,j] = my_lp
best_edge[symi,j] = (lsymi,k, rsymk,j)
67
NLP プログラミング勉強会 8 – 句構造解析
CKY 擬似コード : 木を出力
print(S0,length(words)) # 文全体を覆う「 S 」を出力
subroutine print(symi,j):
if symi,j exists in best_edge: # 非終端記号
return “(“+sym+” “
+ print(best_edge[0]) + “ ” +
+ print(best_edge[1]) + “)”
else: # 終端記号
return “(“+sym+“ ”+words[i]+“)”
68
NLP プログラミング勉強会 8 – 句構造解析
演習課題
69
NLP プログラミング勉強会 8 – 句構造解析
演習課題
●
実装 cky.py
●
テスト
●
●
入力 : test/08­input.txt
●
文法 : test/08­grammar.txt
●
出力 : test/08­output.txt
実際のデータに対して動かす
●
●
木を可視化
●
08­parsing/print­trees.py < wiki­en­test.trees
(NLTK をインストールする必要あり : http://nltk.org/)
70
チャレンジ 未知語に対処できるように改良
●
●
data/wiki­en­test.grammar, data/wiki­en­short.tok
NLP プログラミング勉強会 8 – 句構造解析
Thank You!
71
ダウンロード

自然言語処理プログラミング勉強会 8 - 句構造解析