数理言語情報論 第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
ビームサーチ
２つの刈り方
上位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
© Copyright 2024 ExpyDoc
