数理言語

Size: px

Start display at page:

Download "数理言語"

さやはまもり
5 years ago
Views:

1 人工知能特論 II 二宮崇

2 今日の講義の予定 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 Dae M. Bke 004 Itcaces of Cos Pasg Mode Comutatoa gustcs

3 構文木 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 褒める = =

4 最大確率の木を選ぶ構文解析ある文 s に対し CFG<V N V T P σ> を用いて s を導出できる全ての構文木集合を Ts としたとき ~ t ag max tt s t 4

5 単純な数え上げパラメータ推定学習教師付学習のもっとも単純な実現正解構文木の集合ツリーバンクと呼ばれるがあればその中で使われている CFG 書換規則の頻度をカウントすれば各々のパラメータを簡単に計算できる最尤推定教師無学習の最も有名な実現正解構文木がない場合や書換規則パラメータ以外のパラメータが存在する場合に使われる 5

6 パラメータは条件付き確率 α という形の CFG ルールに対するパラメータ θ α パラメータの関数と明示するほうがわかりやすいけどその確率は親が生成された時の条件確率 θ α = α 今後はパラメータの形ではなくて条件付き確率の形式で説明していきます 6

7 PCFG 概説 7

8 ツリーバンクを使った構文解析文法規則辞書 S NP VP NP DET N NP N 人間が文法を直接定義するのは困難構文木の実例ツリーバンクに基づく定量的評価が必要文法はツリーバンクから導出ツリーバンク文法検証開発コンピュータツリーバンク 8

9 ツリーバンク実世界の文に対して人手で構文木を付与する明示的な文法を仮定しない構造は開発者の言語直感とガイドラインに依存ガイドラインはあるが文法で定義されるような何が正解かの客観的基準は存在しない文法? ecod date as t bee set. 9

10 有名なツリーバンク構文木や係り受け木を人手で付与したコーパスツリーバンクの登場 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

11 Pe Teebak / 構文木が付与された最初の大規模英語ツリーバンク [Macus et a. 993] 様々な分野の英語テキストを収録 Wa Steet Joua 新聞約 5 万文 00 万語 TIS 航空券予約の会話 Bo 様々な分野のテキスト Stcboad 電話の自由発話

12 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. 普通名詞三単現動詞副詞過去分詞

13 ツリーバンクから文法を抽出するツリーバンクの背後にある文法を自動抽出潜在的な規則性を自動獲得できるはず S VP 文法抽出文法? NP VP DT NN NN VBZ RB VBN VBN ecod date as t bee set. ツリーバンク開発 3

14 確率 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

15 確率 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

16 問題点 : 文法が大きい文から約 5000 の CFG 規則 CFG 規則数が収束しない [Caete et a. 997] 抽象化一般化しきれていない文法規則数

17 問題点 : 精度が低い 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

18 ツリーバンク文法の改良文法が大きい CFG 規則の自動圧縮 [Kotov et a. 998; 999] CFG 規則の確率モデル化 [Magema 995; Cos 997; Caak 000] 精度が低い非終端記号の細分化 [Magema 995; Cos 996; 997; Joso 998; Caak 000] 8

19 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

20 非終端記号の細分化 / 語彙化 : 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

21 非終端記号の細分化 / 非終端記号だけでは構造を決める情報が少ない例親の非終端記号で細分化 [Joso 998] S S NP VP NP-S VP-S V NP 主語の NP と目的語の NP が区別できる主語は代名詞が出やすい目的語は長くなりやすい V-VP NP-VP その他様々な周辺情報で細分化 [Caak 000; Ke et a. 003]

22 マルコフ文法

23 マルコフ文法 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

24 何故マルコフ文法を講義で扱うのか? 現在のおおよそ最高性能のパーザー Caak&Joso005 の基礎 Caak000 のパーザーの出力をエントロピー最大化法を用いて eakg Caak パーザーもマルコフ文法の一種モデル精度 F cos % caak % caak&joso % 4

25 マルコフ過程 : シャノンゲーム Naa eats a???? 次に何が来るのか予測バイグラム P ae a C a ae C a P ae eats a C eats a C eats ae a トライグラム 5

26 マルコフ過程 : 確率モデル条件付き確率はだからつまり B B B B 6

27 マルコフ過程 : 確率モデル単語列の確率モデル単語列の N グラムモデル N- 次のマルコフ過程直前の N- 個の単語列の影響のみ受けるユニグラム 0 次のマルコフ過程バイグラム次のマルコフ過程トライグラム次のマルコフ過程 N 7

28 高次のマルコフ過程の問題高い次数のマルコフ過程より精度が高いことが期待できる訓練データに出現しなかった単語列に対しては推定ができないゼロ頻度問題データスパースネス次数が高いほどデータスパースになってしまう 8

29 スムージング線形補間法 ea teoato N グラムの確率値を低次の M グラム M<N の確率値と線形に補間する方法トライグラムの場合 ~ N N N ~ 3 3 ただし 9

30 スムージング補間係数 λ を推定ヘルドアウト補間法 ed-out teoato 訓練データとヘルドアウトデータにわける訓練データで N グラムを学習ヘルドアウトデータで補間係数を学習補間係数は EM アルゴリズムで最尤推定トライグラムの場合 ~ ~ ~ D D D D D D 30

31 スムージング削除補間法 deeted teoato データを m 個に分割... m... m を N グラムの訓練データを補間係数推定のためのヘルドアウトデータとしてヘルドアウト推定法で学習同様に 3... m で N グラムで補間係数を学習これを繰り返して... m- で N グラム m で補間係数を学習以上のようにして求めた補間係数の平均をとる = の時リーヴィングワンアウト法と呼ばれるリーブワンアウトともいう 3

32 COINS MODE 3

33 ツリーバンクの変形語彙化 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

34 語彙化構文木ノードが非終端記号から非終端記号 + 主辞語 + 主辞品詞の組になった ue CFG の構文木ノード : NP 語彙化 CFG の構文木ノード : NPIBM NNP 書換規則も語彙化されたノードで表現 ue CFG: S NP NP VP 語彙化 CFG: Sbougt VBD NPeek NN NPIBM NNP VPbougt VBD 34

35 語彙化 CFG の書換規則書換規則 M... HR...R m m H: ead-cd M: 親 : 主辞の左側の修飾句 R: 主辞の右側の修飾句 : 主辞語と主辞品詞のペア : の主辞語と主辞品詞のペア : R の主辞語と主辞品詞のペア書換規則の確率... H R... Rm m M 35

36 書換規則のマルコフ化書換規則の確率 STOP R STOP H M R R R H M M H M R R H m m m m ただし 36

37 書換規則のマルコフ化書換規則の確率 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

38 書換規則のマルコフ化 : 例 Sbougt NPeek NPIBM VPbougt NPeekNPIBMVPbougtSbougt= VPS bougt NPIBMS VP bougt NPeekS VP bougt STOPS VP bougt STOPS VP bougt 38

39 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

40 Dstace 関数の中身 Dstace 関数が指す部分木 M H R... R - - R... R m m δ- はこの木のこと 40

41 Dstace 関数の中身求めようとする構文木ノードの条件付き確率 R... の一つ手前のノード R - - の下に広がる部分構文木が対象 Dstace 関数の返す値 R かである? 部分構文木の下に動詞を含むか否か? 4

42 COINS MODE 4

43 ツリーバンクの変形語彙化 + 補語句 / 修飾語句の区別 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

44 ツリーバンクの変形補語 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

45 下位範疇化フレーム : 問題補語や修飾語の区別をつけても文法的に誤った構文と正しい構文の確率に差がつかない例不正解 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

46 下位範疇化フレーム : 問題補語や修飾語の区別をつけても文法的に誤った構文と正しい構文の確率に差がつかない例不正解 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

47 下位範疇化フレーム解決策下位範疇化フレーム subcat fame を導入補語として取る非終端記号の多重集合 mut set HPSGで出てきたVの下のSUBJやCOMPSやSPR 47

48 書換規則の確率モデル 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

49 下位範疇化フレーム下位範疇化フレームは補語をひとつとる度に消費される減っていく下位範疇化フレームに要素が残っている間はSTOPに対する確率は0 下位範疇化フレームに要素が無い場合は補語をとる確率は0 49

50 下位範疇化フレーム : 例 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

51 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

52 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

53 主辞品詞主辞語スムージングと 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 t 53

54 性能評価 PRSEV という基準で評価構文木ノードの位置左端の位置と右端の位置と非終端記号ラベル abeed Pecso P= パーザーが正解したラベル数 / パーザーが出力したラベル数 abeed Reca R = パーザーが正解したラベル数 / ツリーバンク中のラベル数 abeed F-ScoeF-Scoe = abeed ecso と abeed eca の調和平均 =*P*R/P+R mode P R F Magema % 84.0% 84.% Cos % 85.3% 85.5% Mode 87.6% 86.8% 87.% Mode 88.% 87.5% 87.8% Mode 3 88.% 87.5% 87.8% 54

55 まとめマルコフ文法マルコフ過程スムージング Cos Mode Cos Mode Cos Mode 3 講義資料 tt://aeb.cs.eme-u.ac.j/~omya/a/ 55

数理言語

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