数理言語情報論第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 pYZ 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