数理言語情報論 第8回
2009年11月25日
数理言語情報学研究室 講師 二宮 崇
1
今日の講義の予定
フルパージング (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
2
CFGパージング
フルパージング
full parsing, brute-force search, exhaustive search,
parsing
ある文sが与えられた時、文法Gによって導出できる全
ての構文木を導出する構文解析
何のために？
フルパージングした後に、確率計算を行って、最も良い構文木
を選択する
パラメータ推定の際に構文木の候補集合が必要（学習方法に
よっては必要ない）
デコーディング
inference, parsing, decoding
構文木の確率を計算するプロセス
最大確率の構文木やn-bestの構文木を求める
3
フルパージング
4
フルパージングのアルゴリズム
トップダウン型
アーリー法 (earley parsing algorithm)
ボトムアップ型
CKY法 (CKY parsing algorithm, CYK法ともい
う)
チャート法 (chart parsing algorithm)
左隅解析法 (left-corner parsing algorithm)
一般化LR法 (generalized LR parsing)
5
CKY法
Cocke, Kasami, Youngerにより提案され、それぞれの
頭文字をとって、CKYもしくはCYK構文解析アルゴリ
ズムと呼ばれる
多くのパーザーで用いられている
簡単
効率が良い
デコーディングと相性が良い
文法規則はバイナリルールかユーナリールールのみ
バイナリールール: 書換規則の右側の要素が二つしかない
ルール
ユーナリールール: 書換規則の右側の要素が一つしかない
ルール
CFGならチョムスキー標準形に変形
HPSG、CCGではバイナリールールを想定しているので特
に問題は無い
6
準備: 書換規則と位置
書換規則は次の3つを想定
A → B C (バイナリールール)
A → B (ユーナリールール)
A → w (辞書ルール)
位置
文 w1,w2,...,wn が与えられた時、
単語wiの位置:
<i-1, i>
句 wi,...,wjの位置: <i-1, j>
7
準備: 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
8
CKY法: 基本的なアイデア
目的: S0, nを計算
Si,jは次のSから計算できる
Si, i+1とSi+1, j
Si, i+2とSi+2, j
....
Si, j-1とSj-1, j
9
CKY法: 基本的なアイデア
Z→X Y
Y
X
Z
w 1 , w2 , w 3 , w4
Y
X
w 1 , w2 , w 3 , w4
w 1 , w2 , w 3 , w 4
X
Y
w 1 , w 2 , w 3 , w4
10
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
11
ルール適用と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)
12
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
13
文法
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
14
文法
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
15
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はユーナリールールを適用
して得られる非終端記号集合
16
CKY法: 計算量
最悪時間計算量 (worst-case time
complexity)
O(n3)
nは文長
アルゴリズムより明らか
非終端記号数を|VN|とすると、O(n3|VN|2)
ファクタリングのおかげで計算量が指数爆発
していないということに注意！
17
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
18
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
19
CKY法: データ構造
各CKYセルSi,jの内容はエッジの集合
エッジ
エッジID
非終端記号
リンクの集合
リンク:
このエッジがどのエッジから生成されたか
記録したデータ構造
バイナリールールならエッジIDのペア
ユーナリールールならエッジID
辞書ルールなら単語ID
20
チャート法
n分岐の書換規則を扱える最も一般的な考
え方のボトムアップ型パージングアルゴリ
ズム
CKYは2分岐の書換規則のみ
21
チャート法: データ構造
エッジ
活性エッジ <i, j, Y → X1 ... Xk・Xk+1 ... Xn>
書換規則の途中にドットをいれたもの
X1 ... Xkが解析済みということを意味する
エッジの左側の位置
(i)と右側の位置 (j)
右側の位置はドットまでの位置のこと
不活性エッジ <i, j, Y>
エッジの左の位置
(i)と右の位置 (j)
非終端記号
22
チャート法: 基本的な考え方
Shift-1: 新しい不活性エッジ<i, j, X>が生成された時、
左側にY→...・X...の形の活性エッジがあればY→...X・...
の活性エッジを生成
X
Y → X1 X2・X X3
new!
i
Y → X1 X2X・ X3
Y → X1 X2・X X3
j
new!
X
i
j
23
チャート法: 基本的な考え方
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
24
チャート法: 基本的な考え方
Reduce: Shift-1, Shift-2の結果新しい活性エッジ<i, j,
Y→...X・>が生成された場合
不活性エッジ<i, j, Y>に置き換える
Y
Y → X1 X 2 X3 ・
i
new!
j
i
j
25
チャート法: アルゴリズム
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
26
左隅解析法
チャート法をより効率的にしたアルゴリズ
ム
活性エッジをチャートに残さなくてもok
右側にエッジがないので、左側のみ解析の対
象とすれば良い(アルゴリズムが簡単)
27
左隅解析法: 基本的な考え方
left-to-right
バイナリールールに限れば、CKYの左隅解析
と同じ
w1, w2, w3,........,wi-1,wi,........., wn
28
左隅解析法: 基本的な考え方 (1)
w1,..,wi-1までは解析済みで、不活性エッジ
しか存在しないと考える
<i-1, i, l∈L(wi)>を新しい不活性エッジとし
て加える
w1, w2, w3,........,wi-1,wi,........., wn
29
左隅解析法: 基本的な考え方 (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,.........
30
左隅解析法: アルゴリズム
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
31
フルパージングまとめ
動的計画法(dynamic programming)
チャートに部分構文木を残しているため、一
度計算された部分構文木は二度計算されない
同じ位置の同じ非終端記号を一つにまとめる
(ファクタリング)
同じ計算を2回以上しないようにするため
出力は畳みこまれた構文木集合 (packed
forest)
AND, ORで表現されるグラフ構造
32
DECODING
33
ビタビアルゴリズム (viterbi
algorithm)
フルパージングを行うと同時に構文木の確
率を計算する手法
各エッジやリンクに部分木の確率値を格納
ファクタリングの際には最大確率のリンクの
み残す
c.f. maxの代わりにsumを求めると、全ての構文木の
確率の和が求まる
最適解
効率は悪い
34
ビタビアルゴリズム:基本的なアイデア
あるi, jに対し、
i k j, X , pX Si,k , Y , pY Sk , j , Z XY
を満たすk, Zが存在するなら、
Z,
max
k:i k j , X , p X Si ,k , Y , pY Sk , j
pX pYZ XY Si, j
Y
pXpYθZ→XY
X
Z
w1 , w 2 , w 3 , w 4
Y
X
w1 , w 2 , w 3 , w 4
pXpYθZ→XY
w1 , w 2 , w 3 , w 4
X
Y
w1 , w 2 , w 3 , w 4
pXpYθZ→XY
35
ビタビアルゴリズム
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>
36
ビタビアルゴリズム
<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
37
ビームサーチパージング
(beam search parsing)
ビタビアルゴリズムで解析する途中で、確
率値の低いエッジを除去する
最適解は保障されない
効率は良い
38
ビームサーチ
２つの刈り方
上位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のことをビーム幅と
呼ぶ
39
ビームサーチ
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
40
イテレィティブパージング
ビームサーチの問題点
ビーム幅が狭いと解が得られない
ビーム幅が広いと効率が悪い
イテレィティブパージング (iterative
parsing)
初めは狭いビーム幅で解析
解が出なければビーム幅を広げて再解析
PCFGの場合はチャートを空にして再解析
確率付HPSGの場合はチャートのデータを再利用
41
まとめ
フルパージング
デコーディング
ビタビアルゴリズム
ビームサーチ
イテレィティブパージング
http://www.r.dl.itc.u-tokyo.ac.jp/~ninomi/mistH21w/cl/
CKY法
チャート法
左隅解析法
次回は、12/2(水) 16:30～ EMアルゴリズムと
内側外側アルゴリズム
講義資料
42
© Copyright 2026 ExpyDoc
