Microsoft PowerPoint PCFG.ppt

Size: px

Start display at page:

Download "Microsoft PowerPoint PCFG.ppt"

かずまさあみおか
5 years ago
Views:

1 [ 言語情報科学論 A] Statistical Parsing 2007 年 06 月 04 日言語情報科学講座林良彦教授 Text: Courtesy of Dr. Jurafsky, D. and Dr. Martin, J.H: Speech and Language Processing,1 st edition (Prentice Hall, 2000) & 2 nd edition, Copyright 2007, Yoshihiko Hayashi 1

2 Agenda Introduction: need for Probabilistic Parsing disambiguation: より尤もらしい構文構造により高い確率を与える language modeling: speech recognition などにおいて, より言語らしい文字列単語列により高い確率を与える PCFG Probabilistic CKY Algorithm Learning PCFG Probabilities Problems with PCFG Probabilistic Lexicalized CFG Evaluating Parsers Copyright 2007, Yoshihiko Hayashi 2

Probabilistic CFG 各文法規則に条件付き確率 (conditional probability) を付与 A -> β [p] p: non-terminal A が与えられているときに, それがβという文法シンボルの系列に展開される確率同じシンボルを左辺にもつ規則に付与された確率の総和は1にならないといけない構文木 T

3 Probabilistic CFG 各文法規則に条件付き確率 (conditional probability) を付与 A -> β [p] p: non-terminal A が与えられているときに, それがβという文法シンボルの系列に展開される確率同じシンボルを左辺にもつ規則に付与された確率の総和は1にならないといけない構文木 T の確率 : それを導出するために適用された規則に付与された確率の積 Courtesy of Dr. Jurafsky, D. and Dr. Martin, J.H: Speech and Language Processing, 2nd edition, CH. 14 Copyright 2007, Yoshihiko Hayashi 3

4 Probabilistic CFG 構文解析 : 最尤な構文木 T' を求める問題 T '( S) = ある文 S が木構造 T として解析される確率 P(S,T) ( 同時確率 ) は, 適用された規則 p(ri) の確率の積 ( 各規則は独立と仮定 P( S, T ) arg max P( T S -> VP (1.0) VP -> "saw" (0.01) VP -> V (0.5) VP -> VP PP (0.3)... = m i= 1 T p( r i ) S) = arg max T S V P P( S, T ) P( S) VP VP N DT P = arg max P( S, T ) PR PP Copyright 2007, Yoshihiko Hayashi 4 T DT I saw a girl with the telescope

5 Probabilistic CYK Parsing CYK (Cook-Younger-Kasami) Parser bottom-up parser (cf. Early parser: top-down) DP (Dynamic Programming) の考え方にもとづく CNF (Chomsky Normal Form) の文法形式 binary branching rule: A -> B C lexical rule: A -> a 注 : 任意のCFGはCNF 形式に変換可能 Copyright 2007, Yoshihiko Hayashi 5

6 Probabilistic CYK 法の概要入力文が n 単語からなるとき,n n の表 π を用意する π(i, j): i 番目の単語から j 番目の単語に対応する部分構造があれば, 確率最大となる文法シンボルを値とともに記録する手順対角線を初期化する ( 辞書ルール ) 対角線を右上に上がりながら表を埋める π(i, j): π(i, m) と π(m+1, j) から部分木が成長できるかをチェックし, もし可能なら, その確率値を計算するすでに記入された確率値があれば, それと比較し, 大きいほうを残す最後に π(1,n) に文法シンボル S があれば解析成功 j i Copyright 2007, Yoshihiko Hayashi 6

7 処理は対角線を右上に進んでいく! I saw a girl with the telesco pe I ->I 0.03 saw S-> VP 3.0e-4 VP->saw 0.01 a DT->a 0.4 girl S-> VP 6.0e-7 VP->VP 2.0e-5 with the telesco pe S-> VP 7.2e-11 VP->VP PP 2.4e-9 S-> ->DT S-> VP VP (1.0) (1.0) ->DT 4.0e-3 ->DT (0.5) (0.5) ->PP ->PP (0.1) (0.1) ->girl? ->"I" ->"I" (0.03) (0.03) >"girl" ->"girl" (0.02) (0.02) ->"telescope" PR->with PP->PR ->"telescope" (0.01) (0.01) VP->VP e-4 VP->VP (0.5) (0.5) VP->VP VP->VP PP PP (0.3) (0.3) DT->the ->DT VP->"saw" VP->"saw" (0.01) (0.01) e-3 DT->"a" DT->"a" (0.4) (0.4) DT->"the" -> DT->"the" (0.4) (0.4) telescope PR->"with" PR->"with" (0.2) (0.2) 0.01 PP-> PP-> PP PP (1.0) (1.0) Copyright 2007, Yoshihiko Hayashi 7?

Algorithm Courtesy of Dr. Jurafsky, D. and Dr. Martin, J.

9 PCFG の確率の推定解析済みのコーパスがある場合の基本は最尤推定 Penn Treebank のような木構造が括弧で示されたコーパス (bracketed corpus) における規則の適用回数から確率を求める例 (VP が左辺に来る総数が 500 回とする ) VP -> "saw" 5 回 (0.01) VP -> VP 250 回 (0.5) VP -> VP PP 150 回 (0.3) 解析済みのコーパスがない場合複数の解析結果を許しながら, 適当な初期値を持つ文法規則で解析を行い, 規則の適用回数を数える真の適用回数 ( 解析が一意に決まる場合の適用回数 ) を繰り返しアルゴリズムにより適用確率を求める Copyright 2007, Yoshihiko Hayashi 9

Problems with PCFG CFGの仮定 : 各規則は互いに独立しかし, あるシンボルがどのように展開されるかは, 文中の位置 ( 構文木中の位置 ) に依存する例 : 代名詞が主語になりやすい ( 代名詞は旧情報を表す ) 単語の情報を抽象化しすぎ例文 (13.19) ; Workers dumped sacks into a bin.

10 Problems with PCFG CFGの仮定 : 各規則は互いに独立しかし, あるシンボルがどのように展開されるかは, 文中の位置 ( 構文木中の位置 ) に依存する例 : 代名詞が主語になりやすい ( 代名詞は旧情報を表す ) 単語の情報を抽象化しすぎ例文 (13.19) ; Workers dumped sacks into a bin. 他の例 coordination: dogs in house and cats Courtesy of Dr. Jurafsky, D. and Dr. Martin, J.H: Speech and Language Processing, 2nd edition, CH. 12 Courtesy of Dr. Jurafsky, D. and Dr. Martin, J.H: Speech and Language Processing, 2nd edition, CH. 14 Copyright 2007, Yoshihiko Hayashi 10

11 Probabilistic Lexicalized CFG Lexicalized CFG: 文法シンボルを構造を持つものとして扱う非終端記号に lexical head の情報を加える (headtag) VP(dumped, VBD) VBD(dumped, VBD) (sacks, NNS) PP(into, IN) Internal rules Lexical rules ( 辞書規則 ) Probabilistic Lexicalized CFG: 語彙化された規則に確率を導入する Lexicalized CFG の問題点 : ルール数増大 data-sparseness 問題 Courtesy of Dr. Jurafsky, D. and Dr. Martin, J.H: Speech and Language Processing, 2nd edition, CH. 14 Copyright 2007, Yoshihiko Hayashi 11

12 Collins Parser Courtesy of Dr. Jurafsky, D. and Dr. Martin, J.H: Speech and Language Processing, 2nd edition, CH. 14 全ての internal rule を次のように扱う LHS Ln Ln-1 L1 H R1 Rn-1 Rn generative story まず head を生成する ( 確率 PH) 次に head の左側を生成する ( 確率 PL) 最後に head の右側を生成する ( 確率 PR) STOP の導入左 : STOP によって生成をやめ, 右側の生成へ移る右 : STOP によって生成をやめる Copyright 2007, Yoshihiko Hayashi 12

13 Collins Parser (cont.) P ( VP(dumped, VBD) VBD(dumped, VBD) (sacks, NNS) PP(into, P) ) の確率は以下のように推定する PH(VBD VP, dumped) PL(STOP VP, VBD, dumped) PR(PP(into,P) VP, VBD, dumped) PR(STOP VP, VBD, dumped) data-sparseness 問題を低減 Count-X: VP(dumped, VBD) の頻度 Count-y: VP(dumped, VBD) の配下で head( VPD(dumped, VBD) ) の右側に NNS(sacks) を持つものの頻度 Count-y / Count-x により計算 Copyright 2007, Yoshihiko Hayashi 13

14 Collins Parser (cont.) head H(hw,ht) を確率 PH(H(hw,ht) P,hw,ht) で生成するただし P は親の文法カテゴリ head の左側の modifiers を次の総確率で生成する n + 1 i= 1 P L ( L i ( lw i, lt i ) P, H, hw, ht) ただし H は head の文法カテゴリ Ln+1(lwn+1,ltn+1)=STOP である head の右側の modifiers を次の総確率で生成する n + 1 i= 1 P R ( R i ( rw i, rt i ) P, H, hw, ht) ただし Rn+1(rwn+1,rtn+1)=STOP である Courtesy of Dr. Jurafsky, D. and Dr. Martin, J.H: Speech and Language Processing, 2nd edition, CH. 14 Copyright 2007, Yoshihiko Hayashi 14

15 Evaluating Parsers tagged corpus を正解 (gold standard) とする評価指標 recall R: 見つけるべきものをどれだけ正しく見つけたか再現率 precision P: 見つけたものはどれだけ正しかったか適合率, 精度参考 : 総合指標としての F-measure (F 値 ): 2PR/(P+R) cross-bracket: ((A B) C) を (A (B C)) とする誤り構文解析における correct constituent start, end, non-terminal symbol が一致する treebank Precision =? Recall =? parsed Courtesy of University of Pennsylvania Copyright 2007, Yoshihiko Hayashi 15

16 Bottom-Up PCFG Chart Parser multiple parses: 構文多義を出力できる基本アイディア : queue of edges chart に追加できる edges を保持する順序つき : もっとも確率の高い edge を chart に追加する algorithm の停止十分な complete parses が見出される ( 成功 ) または,queue が空になる ( 失敗 ) probabilistic edge: dotつきの生成ルールに対応し,edgeの確率は, それ全体が completeになったときの部分木の確率の上限値に対応する例 : S ->. VP というdotつきの生成ルールに対応するedgeの確率は,completeになっているの部分木の確率と S-> VP のルールの確率をかけたもの.(VPの確率は上限値の1.0と見積もる) Copyright 2007, Yoshihiko Hayashi 16

17 Probabilistic Queue initialization: 入力中の token ごとにひとつの edge (= token edge) をつくり, 確率を 1.0 とする queueからedgeをひとつ選び,chartに追加する. この操作が行われると, 以下のルールによって新たなedgesがqueueに追加可能となる prediction rule: dotが最左にあるself-loopに対応する edgeを挿入する fundamental rule: すでにcharに存在するedgesを組み合わせて新たなedgeを作る Copyright 2007, Yoshihiko Hayashi 17

18 Sorting the Queue queue を sorting する strategy を変えることで,parsing のstrategy を変える Inside Parse: edgeに対応する部分木の確率によってsortする. すなわち, このedgeを使った任意の構文木の確率の上限値を与えるこのedgeを使うことの確率的コストは,1からこの木の確率を引いたものになる lowest-cost first strategy optimal strategy: 最初に見出される解が最良の解であることが保証される非効率である可能性 : 確率値の高い木 (= 小さい木 ) を先に探索しようとする Longest Parse: edgeの長さの長い順にsortする. すなわち, 長さが長い部分木が最終的な解の一部になると仮定する best-first strategy: but not an optimal strategy. 最初に見出される解が最良の解とは限らないただし, 通常はoptimal strategyより早く ( 何らかの )completeな構文木を見出すことができる Beam Parse: Inside Parseと同様のsortingを行う. 特に,queue 中の edges をあらかじめ決められたedges 数の最大値 (beam size) で枝狩り (pruning) する. すなわち, 確率の低いedgeを考慮の対象外とする not complete: 必要な部分解を捨ててしまう危険性がある Copyright 2007, Yoshihiko Hayashi 18

数理言語

数理言語人工知能特論 II 二宮崇 1 今日の講義の予定 CFG 構文解析教科書北研二 ( 著 ) 辻井潤一 ( 編 ) 言語と計算 4 確率的言語モデル東大出版会 C. D. Manning & Hinrich Schütze FOUNDATIONS OF STATISTICAL NATURAL LANGUAGE PROCESSING MIT Press, 1999 D. Jurafsky, J. H.