数理言語

Size: px

Start display at page:

Download "数理言語"

なおあかさか
5 years ago
Views:

1 人工知能特論 II 二宮崇 1

2 今日の講義の予定 CFG 構文解析教科書北研二 ( 著 ) 辻井潤一 ( 編 ) 言語と計算 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,

3 CFG の構文解析ある文 s が与えられた時文法 G によって導出できる全ての構文木を導出する構文解析何のために? PCFG 構文解析の基礎構文解析後に確率計算を行って最も良い構文木を選択するパラメータ推定の際に構文木の候補集合が必要 ( 学習方法によっては必要ない ) 3

4 CFG 構文解析 4

5 CFG 構文解析のアルゴリズムトップダウン型アーリー法 (earley parsing algorithm) ボトムアップ型 CKY 法 (CKY parsing algorithm, CYK 法ともいう ) チャート法 (chart parsing algorithm) 左隅解析法 (left-corner parsing algorithm) 一般化 LR 法 (generalized LR parsing) 5

6 CKY 法 Cocke, Kasami, Younger により提案されそれぞれの頭文字をとって CKY もしくは CYK 構文解析アルゴリズムと呼ばれる多くのパーザーで用いられている簡単効率が良いデコーディングと相性が良い文法規則はバイナリルールかユーナリールールのみバイナリールール : 書換規則の右側の要素が二つしかないルールユーナリールール : 書換規則の右側の要素が一つしかないルール CFG ならチョムスキー標準形に変形 HPSG CCG ではバイナリールールを想定しているので特に問題は無い 6

7 準備 : 書換規則と位置書換規則は次の 3 つを想定 A B C ( バイナリールール ) A B ( ユーナリールール ) A w ( 辞書ルール ) 位置文 w 1,w 2,...,w n が与えられた時単語 w i の位置 : <i-1, i> 句 w i,...,w j の位置 : <i-1, j> 7

8 準備 : CKY テーブル ( チャート ) S i,j : w i+1,..., w j に対応する句の非終端記号の集合 S 0,6 S 0,5 S 1,6 S 0,4 S 0,3 S 1,4 S 1,5 S 2,6 S 2,5 S 3,6 S 0,2 S 1,3 S 2,4 S 0,1 S 1,2 S 2,3 S 3,4 S 3,5 S 4,6 S 4,5 S 5, w 1 w 2 w 3 w 4 w 5 w 6 8

9 CKY 法 : 基本的なアイデア目的 : S 0, n を計算 S i,j は次のSから計算できる S i, i+1 とS i+1, j S i, i+2 とS i+2, j... S i, j-1 とS j-1, j 9

10 CKY 法 : 基本的なアイデア Z X Y Y X Z w 1, w 2, w 3, w 4 X Y w 1, w 2, w 3, w 4 w 1, w 2, w 3, w 4 X Y w 1, w 2, w 3, w 4 10

11 CKY 法矢印の順で全ての S i,j が求まる S 0,6 S 0,5 S 1,6 S 0,4 S 1,5 S 2,6 S 0,3 S 1,4 S 2,5 S 3,6 スタート S 0,2 S 1,3 S 2,4 S 0,1 S 1,2 S 2,3 S 3,4 S 3,5 S 4,6 S 4,5 S 5, w 1 w 2 w 3 w 4 w 5 w 6 11

12 ルール適用と S i,j の求め方 G(X, Y) = {Z p P.p=(Z X Y)} X Y に対する全ての親を返す関数 X, Y: 非終端記号 P: 書換規則の集合 S i,j を求めるアルゴリズム for k = i+1 to j-1 forall X S i,k forall Y S k,j S i,j := S i,j G(X, Y) 12

13 CKY 法 : S i,j 例 : S 1,5 に対し k=2,3,4 S 0,6 S 0,5 S 1,6 S 0,4 S 1,5 S 2,6 S 0,3 S 1,4 S 2,5 S 3,6 S 0,2 S 1,3 S 2,4 S 0,1 S 1,2 S 2,3 S 3,4 S 3,5 S 4,6 S 4,5 S 5, w 1 w 2 w 3 w 4 w 5 w 6 13

0,1 1,2 2,3 3,4 4,5 5,6 0 1 2 3 4 5 6 John sees Mary with a telescope NP PP NP 文法 VP VP PP

14 CKY 法例同じ記号が複数でた場合は一つにまとめて構わない (factoring, ファクタリング ) この後のステップでの処理は全て同じになる 0,4 はずだから S 0,3 1,4 VP 0,6 0,5 1,6 VP,VP 1,5 2,6 2,5 3,6 S NP VP 0,2 1,3 2,4 3,5 4,6 NP V NP P DT NP 0,1 1,2 2,3 3,4 4,5 5, John sees Mary with a telescope NP PP NP 文法 VP VP PP VP V NP VP V NP NP PP NP John NP Mary PP P NP P with NP DT NP DT a NP telescope V sees V runs 14

15 CKY 法例 S 0,6 VP 0,5 1,6 NP 0,4 1,5 2,6 S PP 0,3 1,4 2,5 3,6 VP NP 文法 S NP VP VP VP PP VP V NP VP V NP NP PP NP John NP Mary PP P NP P with NP DT NP DT a NP telescope V sees V runs 0,2 1,3 2,4 3,5 4,6 NP V NP P DT NP 0,1 1,2 2,3 3,4 4,5 5, John sees Mary with a telescope 15

16 CKY 法 : アルゴリズム for j = 1 to n S j-1,j := L(w j ) ## 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 S i,k forall Y S k,j Si,j := Si,j G(X, Y) S i,j := S i,j U(S i,j ) ## Uはユーナリールールを適用して得られる非終端記号集合 16

17 CKY 法 : 計算量最悪時間計算量 (worst-case time complexity) O(n 3 ) n は文長アルゴリズムより明らか非終端記号数を V N とすると O(n 3 V N 2 ) ファクタリングのおかげで計算量が指数爆発していないということに注意! 17

18 CKY 法 : 計算順序次の順番で計算しても ok ( 左隅 ) S 0,6 S 0,5 S 1,6 S 0,4 S 1,5 S 2,6 S 0,3 S 1,4 S 2,5 S 3,6 スタート S 0,2 S 1,3 S 2,4 S 0,1 S 1,2 S 2,3 S 3,4 S 3,5 S 4,6 S 4,5 S 5, w 1 w 2 w 3 w 4 w 5 w 6 18

19 CKY 法 : 計算順序次の順番で計算しても ok ( 右隅 ) S 0,6 S 0,5 S 1,6 S 0,4 S 1,5 S 2,6 S 0,3 S 1,4 S 2,5 S 3,6 S 0,2 S 1,3 S 2,4 S 3,5 S 4,6 スタート S 0,1 S 1,2 S 2,3 S 3,4 S 4,5 S 5, w 1 w 2 w 3 w 4 w 5 w 6 19

20 CKY 法 : データ構造各 CKY セル S i,j の内容はエッジの集合エッジエッジ ID 非終端記号リンクの集合リンク : このエッジがどのエッジから生成されたか記録したデータ構造バイナリールールならエッジ ID のペアユーナリールールならエッジ ID 辞書ルールなら単語 ID 20

21 チャート法 n 分岐の書換規則を扱える最も一般的な考え方のボトムアップ型パージングアルゴリズム CKY は 2 分岐の書換規則のみ 21

22 チャート法 : データ構造エッジ活性エッジ <i, j, Y X 1... X k X k+1... X n > 書換規則の途中にドットをいれたもの X 1... X k が解析済みということを意味するエッジの左側の位置 (i) と右側の位置 (j) 右側の位置はドットまでの位置のこと不活性エッジ <i, j, Y> エッジの左の位置 (i) と右の位置 (j) 非終端記号 22

23 チャート法 : 基本的な考え方 Shift-1: 新しい不活性エッジ <i, j, X> が生成された時左側に Y... X... の形の活性エッジがあれば Y...X... の活性エッジを生成 Y X 1 X 2 X X 3 X new! i j Y X 1 X 2 X X 3 Y X 1 X 2 X X 3 new! X i j 23

24 チャート法 : 基本的な考え方 Shift-2: 新しい活性エッジ <i, j, Y... X...> が生成された時, 右側に接する全ての不活性エッジXに対し活性エッジを生成 Y X 1 X X 2 X 3 X new! i j Y X 1 X X 2 X 3 new! Y X 1 X X 2 X 3 X i j 24

25 チャート法 : 基本的な考え方 Reduce: Shift-1, Shift-2 の結果新しい活性エッジ <i, j, Y...X > が生成された場合不活性エッジ <i, j, Y> に置き換える Y X 1 X 2 X 3 Y new! i j i j 25

$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

..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

26 チャート法 : アルゴリズム for j = 1 to n Queue := Queue L(w j ) ## 不活性エッジ <j-1, j, wj に対する非終端記号 > の集合 Chart := Chart L(w j ) 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

27 左隅解析法チャート法をより効率的にしたアルゴリズム活性エッジをチャートに残さなくても ok 右側にエッジがないので左側のみ解析の対象とすれば良い ( アルゴリズムが簡単 ) 27

28 左隅解析法 : 基本的な考え方 left-to-right バイナリールールに限れば CKY の左隅解析と同じ w 1, w 2, w 3,...,w i-1,w i,..., wn 28

29 左隅解析法 : 基本的な考え方 (1) w 1,..,w i-1 までは解析済みで不活性エッジしか存在しないと考える <i-1, i, l L(w i )> を新しい不活性エッジとして加える w 1, w 2, w 3,...,w i-1,w i,..., wn 29

30 左隅解析法 : 基本的な考え方 (2) 新しく出来た不活性エッジ <_, i, X> に対し Y X 1...X k X という形の全ての規則に対し X と連接する X k,..x 1 のエッジを左に向かって探す見つかったら新しく不活性エッジ <_, i, Y> を生成新しく出来たエッジの右端は常にiなので右側にエッジは存在しない右側を気にしなくてもよい Y A B C X Y A B C X...,w i-1,w i,... 30

31 左隅解析法 : アルゴリズム search-left(y, β(=x 1...X k ), i,j) if( β is empty ) edges := edges <i, j, Y> forall <h,i,x k > Chart search-left(y, X 1...X k-1, h, j) left-corner-parsing(w 1,...,w n ) for j = 1 to n Queue := L(w j ) ## <j-1, j, w j の非終端記号 > while(queue is not empty) <i, j, X> := shift(queue) forall (Y X 1... X k X) P edges := {} search-left(y, X 1...X k, i, j) チャートにエッジを格納するときにファクタリングをする Chart := Chart edges; Queue := Queue edges 31

32 まとめ CFG 構文解析動的計画法 (dynamic programming) チャートに部分構文木を残しているため一度計算された部分構文木は二度計算されない同じ位置の同じ非終端記号を一つにまとめる ( ファクタリング ) 同じ計算を 2 回以上しないようにするため出力は畳みこまれた構文木集合 (packed forest) AND, OR で表現されるグラフ構造 CKY 法チャート法左隅解析法資料 32

nlp1-04a.key

nlp1-04a.key 自然言語処理論 I. 文法 ( 構文解析 ) その構文解析 sytctic lysis, prsig 文の構文的な構造を決定すること句構造文法が使われることが多い文法による構文木は一般に複数ある構文木の違い = 解釈の違い構文解析の目的句構造文法の規則を使って, 文を生成できる構文木を全て見つけだすこと文法が入力文を生成できるかどうかを調べるだけではない pro I 構文解析とは構文木の違い