パワーポイント2007(推奨)

数理言語情報論 第8回
2007年11月26日
数理言語情報学研究室 講師 二宮 崇
1
前回の説明に間違いがありました
m(_ _)m
2
何故マルコフ文法を講義で扱うの
か?

現在の(おおよそ)最高性能のパーザー
(Charniak&Johnson2005)の基礎


Collins(1999)のパーザーの出力をエントロピー
最大化法を用いてreranking
Charniakパーザーもマルコフ文法の一種
モデル
精度(LF)
collins1999
88.19%
charniak2000
89.55%
charniak&johnson2005
91.02%
Charniak(2000)
の間違いでした
3
今日の講義の予定



フルパージング (full parsing)
デコーディング (decoding)
教科書



北研二(著) 辻井潤一(編) 言語と計算4 確率的言語モ
デル 東大出版会
C. D. Manning & Hinrich Schütze
“FOUNDATIONS OF STATISTICAL NATURAL
LANGUAGE PROCESSING” MIT Press, 1999
D. Jurafsky, J. H. Martin, A. Kehler, K.V. Linden &
N. Ward “Speech and Language Processing: An
Introduction to Natural Language Processing,
Computational Linguistics, and Speech
Recognition” Prentice Hall Series in Artificial
Intelligence, 2000
4
簡単なCFGの例
CFG: 構文木
S → SUBJ VP1
S
S → SUBJ V
SUBJ → NP が
VP1 → OBJ1 V
SUBJ
OBJ1 → NP を
NP → S NP
V → 送った
V → 読んだ
NP → 香織
NP
NP → プレゼント
NP → 香織 NP1
NP → 恵 NP1
NP1 → と NP
OBJ1
が
V
を
NP
香織
S
NP → 恵
NP → 電子メール
VP1
SUBJ
NP
恵
が
NP
V
読んだ
電子メール
送った
5
PCFG
CFGの書換規則の適
用確率をパラメータ
化した文法
 構文木の確率は、適
用された書換規則の
パラメータの積
 各パラメータは
0.0≦θ≦1.0

簡単なCFGの例
パラメータ
S → SUBJ VP1
θS → SUBJ
VP1
S → SUBJ V
θS → SUBJ
V
SUBJ → NP が
θSUBJ → NP
VP1 → OBJ1 V
θVP1 → OBJ1
OBJ1 → NP を
θOBJ1 → NP を
NP → S NP
θNP → S
V → 送った
θV → 送った
V → 読んだ
θV → 読んだ
NP → 香織
θNP → 香織
NP → 恵
θNP → 恵
NP → 電子メール
θNP → 電子メール
NP → プレゼント
θNP → プレゼント
NP → 香織 NP1
θNP → 香織 NP1
NP → 恵 NP1
θNP → 恵
NP1 → と NP
θNP1 → と
が
V
NP
NP1
NP
6
構文木の確率
文 s = “香織が恵が送った電子メールを読んだ”
S
構文木 t
VP1
SUBJ
簡単なCFGの例
パラメータ
S → SUBJ VP1
θS → SUBJ
VP1
S → SUBJ V
θS → SUBJ
V
SUBJ → NP が
θSUBJ → NP
VP1 → OBJ1 V
θVP1 → OBJ1
OBJ1 → NP を
θOBJ1 → NP を
NP → S NP
θNP → S
V → 送った
θV → 送った
V → 読んだ
θV → 読んだ
NP → 香織
θNP → 香織
NP → 恵
θNP → 恵
NP → 電子メール
θNP → 電子メール
NP → プレゼント
θNP → プレゼント
NP → 香織 NP1
θNP → 香織 NP1
NP → 恵 NP1
θNP → 恵
NP1 → と NP
θNP1 → と
NP
香織
が
OBJ1
が
NP
V
S
SUBJ
NP
NP
が
V
を
読んだ
NP
V
電子メール
送った
恵
P(t) = θS → SUBJ VP1 × θSUBJ → NP が × θNP → 香織 ×
θVP1 → OBJ1 V × θOBJ1 → NP を × θNP → S NP ×
θS → SUBJ V × θSUBJ → NP が × θNP → 恵×
θV → 送った× θNP → 電子メール × θV → 読んだ
NP1
7
NP
CFGパージング

フルパージング (full parsing)


ある文sが与えられた時、文法Gによって導出でき
る全ての構文木を導出する構文解析
何のために?
フルパージングした後に、確率計算を行って、最も良い
構文木を選択する
 パラメータ推定の際に構文木の候補集合が必要(学習方
法によっては必要ない)


デコーディング (decoding)


構文木の確率を計算するプロセス
フルパージングを行わずに直接デコーディングす
る場合もある
8
フルパージング
9
フルパージングのアルゴリズム

トップダウン型


アーリー法 (earley parsing algorithm)
ボトムアップ型
CKY法 (CKY parsing algorithm, CYK法ともい
う)
 チャート法 (chart parsing algorithm)
 左隅解析法 (left-corner parsing algorithm)


一般化LR法 (generalized LR parsing)
10
CKY法


Cocke, Kasami, Youngerにより提案され、それぞれの
頭文字をとって、CKYもしくはCYK構文解析アルゴリ
ズムと呼ばれる
多くのパーザーで用いられている




簡単
効率が良い
デコーディングと相性が良い
文法規則はバイナリルールかユーナリールールのみ




バイナリールール: 書換規則の右側の要素が二つしかない
ルール
ユーナリールール: 書換規則の右側の要素が一つしかない
ルール
CFGならチョムスキー標準形に変形
HPSG、CCGではバイナリールールを想定しているので特
に問題は無い
11
準備: 書換規則と位置

書換規則は次の3つを想定
A → B C (バイナリールール)
 A → B (ユーナリールール)
 A → w (辞書ルール)


位置

文 w1,w2,...,wn が与えられた時、
 単語wiの位置:
<i-1, i>
 句 wi,...,wjの位置: <i-1, j>
12
準備: CKYテーブル(チャート)

Si,j: wi+1,..., wjに対応する句の非終端記号の
集合
S0,6
S0,5
S0,4
S0,3
S0,2
S0,1
0
w1
S1,5
S1,4
S1,3
S1,2
1
w2
S1,6
S2,5
S2,4
S2,3
2
S2,6
w3
S3,6
S3,5
S3,4
3
w4
S4,6
S4,5
4
w5
S5,6
5
w6
6
13
CKY法: 基本的なアイデア
目的: S0, nを計算
 Si,jは次のSから計算できる

Si, i+1とSi+1, j
 Si, i+2とSi+2, j
 ....
 Si, j-1とSj-1, j

14
CKY法: 基本的なアイデア

Z→X Y
Y
X
Z
w 1 , w 2 , w 3 , w4
Y
X
w 1 , w 2 , w 3 , w4
w 1 , w2 , w 3 , w 4
X
Y
w 1 , w 2 , w 3 , w4
15
CKY法

矢印の順で全てのSi,jが求まる
S0,6
S0,5
S0,4
S0,3
スタート
0
S0,2
S0,1
w1
S1,5
S1,4
S1,3
S1,2
1
w2
S1,6
S2,5
S2,4
S2,3
2
S2,6
w3
S3,6
S3,5
S3,4
3
w4
S4,6
S4,5
4
w5
S5,6
5
w6
6
16
ルール適用とSi,jの求め方

G(X, Y) = {Z|∃p∈P.p=(Z→X Y)}

X Yに対する全ての親を返す関数
Y: 非終端記号
 P: 書換規則の集合
 X,
Si,jを求めるアルゴリズム
for k = i+1 to j-1
forall X∈ Si,k
forall Y ∈ Sk,j
Si,j := Si,j ∪ G(X, Y)

17
CKY法: Si,j

例: S1,5に対しk=2,3,4
S0,6
S0,5
S0,4
S0,3
S0,2
S0,1
0
w1
S1,5
S1,4
S1,3
S1,2
1
w2
S1,6
S2,5
S2,4
S2,3
2
S2,6
w3
S3,6
S3,5
S3,4
3
w4
S4,6
S4,5
4
w5
S5,6
5
w6
6
18
文法
CKY法
S → NP VP
VP → VP PP
VP → V NP

VP → V
例
NP → NP PP
同じ記号が複数でた場
0,6
合は、一つにまとめて
構わない (factoring,
0,5
ファクタリング)
この後のステップでの
0,4
1,5
処理は全て同じになる
S
はずだから。
0,3
1,4
NP → John
NP → Mary
PP → P NP
VP,VP
P → with
1,6
NP → DT NP
NP
DT → a
2,6
PP
2,5
0
John
sees
2,4
NP
2,3
1,2
1
NP
1,3
V
NP
0,1
2
V → sees
3,6
VP
0,2
NP → telescope
Mary
3
3,5
V → runs
4,6
P
DT
NP
3,4
4,5
5,6
with
4
a
5
telescope
6
19
文法
CKY法
S → NP VP
VP → VP PP
VP → V NP

VP → V
例
NP → NP PP
NP → John
S
NP → Mary
0,6
PP → P NP
VP
0,5
P → with
1,6
NP → DT NP
NP
S
0,4
1,5
DT → a
2,6
PP
0,3
1,4
2,5
0
John
sees
2,4
NP
2,3
1,2
1
NP
1,3
V
NP
0,1
2
V → sees
3,6
VP
0,2
NP → telescope
Mary
3
3,5
V → runs
4,6
P
DT
NP
3,4
4,5
5,6
with
4
a
5
telescope
6
20
CKY法: アルゴリズム
for j = 1 to n
Sj-1,j := L(wj) ## Lは単語wに対する非終端記号の
集合を返す関数
for l = 2 to n
for i = 0 to n – l
j := i + l;
for k = i+1 to j - 1
forall X∈Si,k
forall Y∈Sk,j
Si,j := Si,j ∪ G(X, Y)
Si,j := Si,j ∪ U(Si,j) ## Uはユーナリールールを適用
して得られる非終端記号集合
21
CKY法: 計算量

最悪時間計算量 (worst-case time
complexity)

O(n3)
 nは文長
 アルゴリズムより明らか
非終端記号数を|VN|とすると、O(n3|VN|2)
 ファクタリングのおかげで計算量が指数爆発
していないということに注意!

22
CKY法: 計算順序

次の順番で計算してもok (左隅)
S0,6
S0,5
S0,4
S0,3
スタート
0
S0,2
S0,1
w1
S1,5
S1,4
S1,3
S1,2
1
w2
S1,6
S2,5
S2,4
S2,3
2
S2,6
w3
S3,6
S3,5
S3,4
3
w4
S4,6
S4,5
4
w5
S5,6
5
w6
6
23
CKY法: 計算順序

次の順番で計算してもok (右隅)
S0,6
S0,5
S0,4
S0,3
S0,2
S0,1
0
w1
S1,5
S1,4
S1,3
S1,2
1
w2
S1,6
S2,5
S2,4
S2,3
2
S2,6
w3
S3,6
S3,5
S3,4
3
w4
S4,6
S4,5
4
w5
スタート
S5,6
5
w6
6
24
CKY法: データ構造
各CKYセルSi,jの内容はエッジの集合
 エッジ

エッジID
 非終端記号
 リンクの集合

 リンク:
このエッジがどのエッジから生成されたか
記録したデータ構造



バイナリールールならエッジIDのペア
ユーナリールールならエッジID
辞書ルールなら単語ID
25
チャート法

n分岐の書換規則を扱える最も一般的な考
え方のボトムアップ型パージングアルゴリ
ズム

CKYは2分岐の書換規則のみ
26
チャート法: データ構造

エッジ

活性エッジ <i, j, Y → X1 ... Xk・Xk+1 ... Xn>
 書換規則の途中にドットをいれたもの

X1 ... Xkが解析済みということを意味する
 エッジの左側の位置


(i)と右側の位置 (j)
右側の位置はドットまでの位置のこと
不活性エッジ <i, j, Y>
 エッジの左の位置
(i)と右の位置 (j)
 非終端記号
27
チャート法: 基本的な考え方
Shift-1: 新しい不活性エッジ<i, j, X>が生成された時、

左側にY→...・X...の形の活性エッジがあればY→...X・...
の活性エッジを生成
X
Y → X1 X2・X X3
new!
i
j
Y → X1 X2X・ X3 new!
Y → X1 X2・X X3
X
i
j
28
チャート法: 基本的な考え方
Shift-2: 新しい活性エッジ<i, j, Y→...・X...>が生成さ
れた時,

右側に接する全ての不活性エッジXに対し、活性エッ
Y → X1・X X2 X3
X
ジを生成
new!
i
j
Y → X1X・ X2 X3 new!
Y → X1・X X2 X3
i
X
j
29
チャート法: 基本的な考え方
Reduce: Shift-1, Shift-2の結果新しい活性エッジ<i, j,
Y→...X・>が生成された場合

不活性エッジ<i, j, Y>に置き換える
Y
Y → X1 X 2 X3 ・
i
new!
j
i
j
30
チャート法: アルゴリズム
for j = 1 to n
Queue := Queue ∪ L(wj) ## 不活性エッジ<j-1, j, wjに対する非終端記号>の集合
Chart := Chart ∪ L(wj) ∪Y→β∈P<j-1, j-1, Y→・β>
while(Queue is not empty)
E := shift(Queue) ##EはQueueの先頭
edges := {}; reduced_edges := {}
if(E is 不活性エッジ<i, j, X>)
チャートとキュー
forall F∈Chart s.t. F=<h, i, Y→ ...・X...>
にエッジを格納す
edges := edges ∪ <h, j, Y→ ...X・...>
if(E is 活性エッジ<i, j, Y→...・X...>)
るときにファクタ
forall F∈Chart s.t. F=<j, k, X>
リングをする
edges := edges ∪ <i, k, Y→ ...X・...>
forall E’ ∈ edges
if(E’ is <x, y, Y→β・>)
reduced_edges := reduced_edges∪<x, y, Y>
else
reduced_edges := reduced_edges ∪ E’
Queue := Queue ∪ reduced_edges; Chart := Chart ∪ reduced_edges
31
左隅解析法

チャート法をより効率的にしたアルゴリズ
ム
活性エッジをチャートに残さなくてもok
 右側にエッジがないので、左側のみ解析の対
象とすれば良い(アルゴリズムが簡単)

32
左隅解析法: 基本的な考え方

left-to-right

バイナリールールに限れば、CKYの左隅解析
と同じ
w1, w2, w3,........,wi-1,wi,........., wn
33
左隅解析法: 基本的な考え方 (1)
w1,..,wi-1までは解析済みで、不活性エッジ
しか存在しないと考える
 <i-1, i, l∈L(wi)>を新しい不活性エッジとし
て加える

w1, w2, w3,........,wi-1,wi,........., wn
34
左隅解析法: 基本的な考え方 (2)

新しく出来た不活性エッジ<_, i, X>に対し、
Y→X1....XkXという形の全ての規則に対し、X
と連接するXk,..X1のエッジを左に向かって探す
 見つかったら新しく不活性エッジ<_, i, Y>を生
成

 新しく出来たエッジの右端は常にiなので、右側に
エッジは存在しない⇒右側を気にしなくてもよい
Y
Y→A B C X
A
B
C
X
........,wi-1,wi,.........
35
左隅解析法: アルゴリズム
search-left(Y, β(=X1...Xk), i,j)
if( β is empty )
edges := edges ∪ <i, j, Y>
forall <h,i,Xk> ∈ Chart
search-left(Y, X1...Xk-1, h, j)
チャートにエッジ
を格納するときに
ファクタリングを
する
left-corner-parsing(w1,...,wn)
for j = 1 to n
Queue := L(wj) ## <j-1, j, wjの非終端記号>
while(Queue is not empty)
<i, j, X> := shift(Queue)
forall (Y→X1 ... Xk X) ∈ P
edges := {}
search-left(Y, X1...Xk, i, j)
Chart := Chart ∪ edges; Queue := Queue ∪ edges
36
フルパージングまとめ

動的計画法(dynamic programming)
チャートに部分構文木を残しているため、一
度計算された部分構文木は二度計算されない
 同じ位置の同じ非終端記号を一つにまとめる
(ファクタリング)

 同じ計算を2回以上しないようにするため

出力は畳みこまれた構文木集合 (packed
forest)

AND, ORで表現されるグラフ構造
37
DECODING
38
ビタビアルゴリズム (viterbi
algorithm)

フルパージングを行うと同時に構文木の確
率を計算する手法
各エッジやリンクに部分木の確率値を格納
 ファクタリングの際には最大確率のリンクの
み残す

c.f. maxの代わりにsumを求めると、全ての構文木の
確率の和が求まる
最適解
 効率は悪い

39
ビタビアルゴリズム

Si,j: <X, p>の集合
X: 非終端記号
 p: 部分木の確率

ファクタリング(同
じ非終端記号が出
現した場合の畳込
み)の際には確率の
高い方を選ぶ
Si,jの求め方 (CKY法の場合)
for k = i+1 to j-1
forall <X, pX>∈ Si,k
forall <Y, pY>∈ Sk,j
forall Z ∈ G(X, Y)
Si,j := Si,j ∪ <Z, pX×pY×θZ→X Y>

40
ビタビアルゴリズム
<VP,
0.03>
例
<VP, 0.008>
をファクタリングす
る際は
<VP, 0.03>
と確率値の高い方を
残す
0.5×0.2×θVP→V
=0.01×0.8
=0.008
0,6
<VP,0.03>
<VP, 0.008>
0,5
1,6
<NP, 0.00016>
0,4
1,5
<S, 0.0008>
0,3
2,6
<PP, 0.008>
1,4
2,5
3,6
<VP, 0.008>
0,2
<NP, 0.05>
3,5
4,6
<NP,0.1> <V, 0.5> <NP, 0.2> <P, 1.0> <DT, 1.0><NP, 0.2>
0,1
1,2
2,3
3,4
4,5
5,6
0
1
2
3
4
5
6
John
1,3
NP
sees
2,4
Mary
with
a
telescope
41
ビームサーチパージング
(beam search parsing)
ビタビアルゴリズムで解析する途中で、確
率値の低いエッジを除去する
 最適解は保障されない
 効率は良い

42
ビームサーチ
N: 数による閾値
 W: 幅による閾値
 Si,jの求め方 (CKY法の場合)
for k = i+1 to j-1
forall <X, pX>∈ Si,k
forall <Y, pY>∈ Sk,j
forall Z ∈ G(X, Y)
Si,j := Si,j ∪ <Z, pX×pY×θZ→X Y>
sort Si,j according to its p (Si,j=<X1, p1>...<XM, pM>とす
る)
remove <XN+1, pN+1>...<XM, pM>
remove <X, p> ∈ Si,j s.t. p < p1×W

43
ビームサーチ

2つの刈り方
上位N個のみ残す
 トップの確率×W以上の確率のみ残す

Si,j
sort
<VP,0.03>
<NP, 0.002>
<S, 0.001>
<NP-S, 0.0005>
<NP-O, 0.0002>
<DT, 0.000001>
<WH, 0.00000083>
....
上位N個のみ残す
0.03×W以上のエッジのみ残す
Nや1-Wのことをビーム幅
と呼ぶ
44
イテレィティブパージング

ビームサーチの問題点
ビーム幅が狭いと解が得られない
 ビーム幅が広いと効率が悪い


イテレィティブパージング (iterative
parsing)
初めは狭いビーム幅で解析
 解が出なければビーム幅を広げて再解析

 PCFGの場合はチャートを空にして再解析
 確率付HPSGの場合はチャートのデータを再利用
45
まとめ

フルパージング




デコーディング

ビタビアルゴリズム
ビームサーチ
イテレィティブパージング

http://www.r.dl.itc.u-tokyo.ac.jp/~ninomi/mistH19w/




CKY法
チャート法
左隅解析法
次回は、12/3(月) 16:30~ EMアルゴリズムと
内側外側アルゴリズム
講義資料
46