人工知能特論 II 二宮崇
今日の講義の予定 PCFG Pobabstc Cotext Fee Gamma 確率付文脈自由文法 マルコフ文法 論文 Mcae Cos 997 Tee geeatve excased modes fo statstca asg I oc. of C-EC.6 3 Mcae Cos 999 Head-Dve Statstca Modes fo Natua aguage Pasg P.D tess Uvesty of Pesyvaa Mcae Cos 003 Head-Dve Statstca Modes fo Natua aguage Pasg Comutatoa gustcs 94 589--637. Dae M. Bke 004 Itcaces of Cos Pasg Mode Comutatoa gustcs 30 479 5
構文木 t の確率を計算 構文木 t S CFG G パラメータ 値 S NP VP θ S NP VP.0 NP N PP θ NP N PP.0 N NP PP NP VP VP N N PP N θ N N PP N 0. VP NP VP θ VP NP VP 0.3 VP V θ VP V 0.7 PP が θ PP が 0.5 太郎 N が PP N N PP を V 褒める PP を θ PP を 0.3 PP と θ PP と 0. 花子 と 映画 N 太郎 θ N 太郎 0.3 N 花子 θ N 花子 0. N 映画 θ N 映画 0.4 V 褒める θ V 褒める 0.3 V 見る θ V 見る 0.7 t = θ S NP VP θ NP N PP θ N 太郎 θ PP が θ VP NP VP θ NP N PP θ N N PP N θ N 花子 θ PP と θ N 映画 θ PP を θ VP V θ V 褒める =.0.0 0.3 0.5 0.3.0 0. 0. 0. 0.4 0.3 0.7 0.3 = 0.000004536 3
最大確率の木を選ぶ 構文解析 ある文 s に対し CFG<V N V T P σ> を用いて s を導出できる全ての構文木集合を Ts としたとき ~ t ag max tt s t 4
単純な数え上げ パラメータ推定 学習 教師付学習のもっとも単純な実現 正解構文木の集合 ツリーバンクと呼ばれる があれば その中で使われている CFG 書換規則の頻度をカウントすれば各々のパラメータを簡単に計算できる 最尤推定 教師無学習の最も有名な実現 正解構文木がない場合や書換規則パラメータ以外のパラメータが存在する場合に使われる 5
パラメータは条件付き確率 α という形の CFG ルールに対するパラメータ θ α パラメータの関数と明示するほうがわかりやすいけど その確率は親が生成された時の条件確率 θ α = α 今後は パラメータの形ではなくて 条件付き確率の形式で説明していきます 6
PCFG 概説 7
ツリーバンクを使った構文解析 文法規則 辞書 S NP VP NP DET N NP N 人間が文法を直接定義するのは困難 構文木の実例 ツリーバンク に基づく定量的評価が必要 文法はツリーバンクから導出 ツリーバンク文法 検証 開発 コンピュータ ツリーバンク 8
ツリーバンク 実世界の文に対して人手で構文木を付与する 明示的な文法を仮定しない 構造は開発者の言語直感とガイドラインに依存 ガイドラインはあるが 文法で定義されるような 何が正解か の客観的基準は存在しない 文法? ecod date as t bee set. 9
有名なツリーバンク 構文木や係り受け木を人手で付与したコーパス ツリーバンク の登場 Pe Teebak [Macus et a. 993] SUSNNE [Samso 995] TIGER Teebak [Bats et a. 00] Pague Deedecy Teebak [Hajc 998] Vebmob [Hcs et a. 000] EDR コーパス [EDR 995] 京都大学テキストコーパス [ 黒橋ら 997] 日本語話し言葉コーパス [ 前川ら 000] 0
Pe Teebak / 構文木が付与された最初の大規模英語ツリーバンク [Macus et a. 993] 様々な分野の英語テキストを収録 Wa Steet Joua 新聞 約 5 万文 00 万語 TIS 航空券予約の会話 Bo 様々な分野のテキスト Stcboad 電話の自由発話
Pe Teebak / 品詞 : NN 普通名詞 VBZ 三単現動詞 構文木 : NP 名詞句 VP 動詞句 Fucto tag u eemet: 述語項構造を計算するための付加情報 詳細省略 名詞句 S VP NP VP 限定詞 DT NN NN VBZ RB VBN VBN ecod date as t bee set. 普通名詞三単現動詞副詞過去分詞
ツリーバンクから文法を抽出す る ツリーバンクの背後にある文法を自動抽出 潜在的な規則性を自動獲得できるはず S VP 文法抽出 文法? NP VP DT NN NN VBZ RB VBN VBN ecod date as t bee set. ツリーバンク開発 3
確率 CFG の自動抽出 / ツリーバンクの各分岐を CFG 規則だと仮定して抽出する [Caak 996; 997] c.f. [Seke995] S VP NP VP DT NN NN VBZ RB VBN VBN ecod date as t bee set. CFG 規則 S NP VP NP DT NN NN VP VBZ RB VP VP VBN VBN 4
確率 CFG の自動抽出 / ツリーバンクでの出現頻度から確率値を推定 確率値最大の木を探索することで 構文解析の曖昧性解消ができる S VP NP VP DT NN NN VBZ RB VBN VBN ecod date as t bee set. S NP VP NP DT NN NN VP VBZ RB VP VP VBN VBN 0.5 0.03 0.0 0. 5
問題点 : 文法が大きい 40000 文から約 5000 の CFG 規則 CFG 規則数が収束しない [Caete et a. 997] 抽象化 一般化しきれていない 6000 4000 000 0000 8000 6000 4000 000 0 文法規則数 0 0000 0000 30000 40000 6
問題点 : 精度が低い Caak [996]: 80% NP S VP NP VP We aed te agotm to We seected te aoac to IE NN VBD DT NN IN NN NP S NP VP NP PP NP IE NP PP VP VP PP NP NP PP 同じ品詞列でも 単語によって構文木の形が変わる 7
ツリーバンク文法の改良 文法が大きい CFG 規則の自動圧縮 [Kotov et a. 998; 999] CFG 規則の確率モデル化 [Magema 995; Cos 997; Caak 000] 精度が低い 非終端記号の細分化 [Magema 995; Cos 996; 997; Joso 998; Caak 000] 8
CFG 規則の確率モデル化 Makov Gamma: CFG 規則を確率的に生成する [Cos 997; Caak 000] NP DT NN NN NP = NN NP NN NN NP DT NN NN NP 原理的には 全ての CFG 規則をもつ PCFG Pe Teebak から抽出したそのままの PCFG より高精度を達成する 9
非終端記号の細分化 / 語彙化 : Head ecoato tabe Magema 995 を用いて 非終端記号に ead od を付与 NP S VP aed aed NP VP aed NN VBD DT NN IN NN We aed te agotm to PP to NP We agotm IE 参考 語彙化の意味 [Gdea 00; Bke 004] IE Head ecoato tabe 親の記号主辞になる子の記号 S VP NP PP VP VP VBD VBZ NN IN Caak [996]: 80% vs. Magema [995]: 86% 0
非終端記号の細分化 / 非終端記号だけでは構造を決める情報が少ない 例 親の非終端記号で細分化 [Joso 998] S S NP VP NP-S VP-S V NP 主語の NP と目的語の NP が区別できる 主語は代名詞が出やすい 目的語は長くなりやすい V-VP NP-VP その他 様々な周辺情報で細分化 [Caak 000; Ke et a. 003]
マルコフ文法
マルコフ文法 CFG 規則を確率的に生成する [Cos 997; Caak 000] NP DT NN NN NP = NN NP NN NN NP DT NN NN NP 原理的には 全ての CFG 規則をもつ PCFG Pe Teebak から抽出したそのままの PCFG より高精度を達成する State-of-te-at の性能のパーザーの基本的な仕組 3
何故マルコフ文法を講義で扱うの か? 現在の おおよそ 最高性能のパーザー Caak&Joso005 の基礎 Caak000 のパーザーの出力をエントロピー最大化法を用いて eakg Caak パーザーもマルコフ文法の一種 モデル 精度 F cos999 88.9% caak000 89.55% caak&joso005 9.0% 4
マルコフ過程 : シャノンゲーム Naa eats a???? 次に何が来るのか予測 バイグラム P ae a C a ae C a P ae eats a C eats a C eats ae a トライグラム 5
マルコフ過程 : 確率モデル 条件付き確率は だから つまり B B 3 3 3 3 B B 6
マルコフ過程 : 確率モデル 単語列の確率モデル 単語列の N グラムモデル N- 次のマルコフ過程 直前の N- 個の単語列の影響のみ受ける ユニグラム 0 次のマルコフ過程 バイグラム 次のマルコフ過程 トライグラム 次のマルコフ過程 3 4 3 N 7
高次のマルコフ過程の問題 高い次数のマルコフ過程 より精度が高いことが期待できる 訓練データに出現しなかった単語列に対しては推定ができない ゼロ頻度問題 データスパースネス 次数が高いほどデータスパースになってしまう 8
スムージング 線形補間法 ea teoato N グラムの確率値を低次の M グラム M<N の確率値と線形に補間する方法 トライグラムの場合 ~ N N N ~ 3 3 ただし 9
スムージング 補間係数 λ を推定 ヘルドアウト補間法 ed-out teoato 訓練データとヘルドアウトデータにわける 訓練データで N グラムを学習 ヘルドアウトデータで補間係数を学習 補間係数は EM アルゴリズムで最尤推定 トライグラムの場合 3 3 3 3 3 ~ ~ ~ D D D D D D 30
スムージング 削除補間法 deeted teoato データを m 個に分割... m... m を N グラムの訓練データ を補間係数推定のためのヘルドアウトデータとしてヘルドアウト推定法で学習 同様に 3... m で N グラム で補間係数を学習 これを繰り返して... m- で N グラム m で補間係数を学習 以上のようにして求めた補間係数の平均をとる = の時 リーヴィング ワン アウト法と呼ばれる リーブ ワン アウトともいう 3
COINS MODE 3
ツリーバンクの変形 語彙化 TOP Sbougt VBD Head ecoato tabe 親の記号主辞になる子の記号 S VP VP VP VBD VBZ NP NN PP IN NPeek NN NPIBM NNP NNPIBM NNP VPbougt VBD JJast JJ VBDbougt VBD NPotus NNP ast NNeek NN eek IBM bougt NNPotus NNP otus 33
語彙化 構文木ノードが非終端記号から 非終端記号 + 主辞語 + 主辞品詞 の組になった ue CFG の構文木ノード : NP 語彙化 CFG の構文木ノード : NPIBM NNP 書換規則も語彙化されたノードで表現 ue CFG: S NP NP VP 語彙化 CFG: Sbougt VBD NPeek NN NPIBM NNP VPbougt VBD 34
語彙化 CFG の書換規則 書換規則 M... HR...R m m H: ead-cd M: 親 : 主辞の左側の修飾句 R: 主辞の右側の修飾句 : 主辞語と主辞品詞のペア : の主辞語と主辞品詞のペア : R の主辞語と主辞品詞のペア 書換規則の確率... H R... Rm m M 35
書換規則のマルコフ化 書換規則の確率 STOP R STOP H M R R R H M M H M R R H m m m m............... ただし 36
書換規則のマルコフ化 書換規則の確率 0 次のマルコフ過程 c.f. caak000 は 3 次のマルコフ文法 つまり... H M H M...... H M R H M R R R...... m m H M R H M M H M R R H 語彙化と 書換規則の確率の定義が変わるだけで その他は ue PCFG と同じであることに注意! 37
書換規則のマルコフ化 : 例 Sbougt NPeek NPIBM VPbougt NPeekNPIBMVPbougtSbougt= VPS bougt NPIBMS VP bougt NPeekS VP bougt STOPS VP bougt STOPS VP bougt 38
Dstace 関数の追加 マルコフ化の際に Dstace 関数を追加 書換規則の確率... H M H M...... H M R H M R R R...... m m H M R H M M H M R R H 39
Dstace 関数の中身 Dstace 関数が指す部分木 M H R... R - - R... R m m δ- はこの木のこと 40
Dstace 関数の中身 求めようとする構文木ノードの条件付き確率 R... の一つ手前のノード R - - の下に広がる部分構文木が対象 Dstace 関数の返す値 R か である? 部分構文木の下に動詞を含むか否か? 4
COINS MODE 4
ツリーバンクの変形 語彙化 + 補語 句 / 修飾語 句 の区別 TOP Sbougt VBD NPeek NN NP-CIBM NNP VPbougt VBD NNPIBM NNP NP-Cotus NNP JJast JJ NNeek NN IBM VBbougt VBD ast eek bougt NNPotus NNP otus 43
ツリーバンクの変形 補語 comemets/ 修飾語 adjucts の区別 次の条件を満たす非終端記号は全て補語 comemets 非終端記号は次のうちのいずれかである 親が S である NP SBR S 親が VP である NP SBR S 3 親が SBR である S 非終端記号は次のうちのいずれかの sematc tag をもっていてはいけない DV VOC BNF DIR EXT OC NMR TMP CR o PRP それに加えて 前置詞句の主辞の後にすぐに続く兄弟ノードは補語である 44
下位範疇化フレーム : 問題 補語や修飾語の区別をつけても 文法的に誤った構文と正しい構文の確率に差がつかない 例 不正解 S S 正解 VP NP-C VP NP-C Deyfus NP-C te best fud as DJP NP Deyfus NP te best fud as DJP o o 45
下位範疇化フレーム : 問題 補語や修飾語の区別をつけても 文法的に誤った構文と正しい構文の確率に差がつかない 例 不正解 NP-C Te ssue as S VP NP-C a b fudg VP-C NP-C Cogess NP-C Te ssue S as NP a b VP NP-C fudg 正解 VP NP-C Cogess 46
下位範疇化フレーム 解決策 下位範疇化フレーム subcat fame を導入 補語として取る非終端記号の多重集合 mut set HPSGで出てきたVの下のSUBJやCOMPSやSPR 47
書換規則の確率モデル C 左側の下位範疇化フレーム と RC 右側の下位範疇化フレーム の導入 例 RC={NP-C NP-C} C={NP-C} c {NP-C NP-C}S VP bougt} や c {NP-C VP- C}VP VB as は低い...... c c m m RC H M R C H M H M RC H M C M H M R R H 48
下位範疇化フレーム 下位範疇化フレームは補語をひとつとる度に消費される 減っていく 下位範疇化フレームに要素が残っている間はSTOPに対する確率は0 下位範疇化フレームに要素が無い場合は 補語をとる確率は0 49
下位範疇化フレーム : 例 Sbougt NPeek NP-CIBM VPbougt の確率 VPS bougt c {NP-C}S VP bougt c {}S VP bougt NP-CIBMS VP bougt {NP-C} NPeekS VP bougt {} STOPS VP bougt {} STOPS VP bougt {} 50
Cos Mode 3 痕跡 Tace と - 移動 ex. Te stoe SBR c TRCE bougt Books Botes ex. Te stoe SBR c Maks bougt TRCE ex.3 Te stoe SBR c Maks bougt Books Botes fom TRCE 5
Cos Mode 3 例 NPstoe NPstoe WHNPtat SBRtat+ga Sbougt+ga bougt が TRCE をとった後の下位範疇化フレームは空 : {} Te stoe WDT tat bougt の下位範疇化フレーム : {NP-C} NP-CMaks Maks VBD bougt VPbougt+ga TRCE NPeek ast eek 5
主辞品詞主辞語 スムージング と R t t R t 削除補間法 deeted teoato back-off eve M H C M H RC H... c C... c RC... t t... R t... M H C M H C M H RC M H RC...... Mt MHt MHtδC t MHtδC Mt MHt MHtδC t MHtδC 3 M MH MHδC t 4 - - - t 53
性能評価 PRSEV という基準で評価 構文木ノードの位置 左端の位置と右端の位置 と非終端記号ラベル abeed Pecso P= パーザーが正解したラベル数 / パーザーが出力したラベル数 abeed Reca R = パーザーが正解したラベル数 / ツリーバンク中のラベル数 abeed F-ScoeF-Scoe = abeed ecso と abeed eca の調和平均 =*P*R/P+R mode P R F Magema95 84.3% 84.0% 84.% Cos96 85.7% 85.3% 85.5% Mode 87.6% 86.8% 87.% Mode 88.% 87.5% 87.8% Mode 3 88.% 87.5% 87.8% 54
まとめ マルコフ文法 マルコフ過程 スムージング Cos Mode Cos Mode Cos Mode 3 講義資料 tt://aeb.cs.eme-u.ac.j/~omya/a/ 55