数理言语-中川研究室.PPT

例: 混合モデルのパラメータ更新式導出 ラグランジュ関数を偏微分 * 例: 混合モデルのパラメータ更新式導出 * PCFGのパラメータ更新式導出 PCFGのQ関数 * PCFGのパラメータ更新式導出 PCFGのQ関数 ラグランジュ関数 * PCFGのパラメータ更新式導出 ラグランジュ関数をパラメータで偏微分 * PCFGのパラメータ更新式導出 パラメータ更新式 書換規則の適用回数の期待値になっていることに注意 * PCFGに対するEMアルゴリズムの問題点 構文木が多すぎて現実的な時間で各構文木の相対確率を計算できない！(文長に対して指数爆発的に増加。簡単に数百億ぐらいになる。) s parse p(t)/Z = 0.21 0.06 0.001 0.05 0.07 ... 数百億続く！ * →CKYテーブルを展開することなく期待値が計算できればよい (内側外側アルゴリズム) まとめ EMアルゴリズム 次回は、12/9(水) 16:30～ 前向き後ろ向きアルゴリズム、内側外側アルゴリズム 講義資料 http://www.r.dl.itc.u-tokyo.ac.jp/~ninomi/mistH21w/cl/ * * * 数理言語情報論　第9回 数理言語情報学研究室　講師　二宮　崇 2009年12月2日 * 今日の講義の予定 EMアルゴリズム 教科書 北研二(著) 辻井潤一(編) 言語と計算4 確率的言語モデル 東大出版会 C. D. Manning Hinrich Schütze “FOUNDATIONS OF STATISTICAL NATURAL LANGUAGE PROCESSING” MIT Press, 1999 Christopher M. Bishop “PATTERN RECOGNITION AND MACHINE LEARNING” Springer, 2006 * PCFG CFGの書換規則の適用確率をパラメータ化した文法 構文木の確率は、適用された書換規則のパラメータの積 各パラメータは0.0≦θ≦1.0 簡単なCFGの例 パラメータ S → SUBJ VP1 θS → SUBJ VP1 S → SUBJ V θS → SUBJ V SUBJ → NP が θSUBJ → NP が VP1 → OBJ1 V θVP1 → OBJ1 V OBJ1 → NP を θOBJ1 → NP を NP → S NP θNP → S NP V → 送った θV → 送った V → 読んだ θV → 読んだ NP → 香織 θNP → 香織 NP → 恵 θNP → 恵 NP → 電子メール θNP → 電子メール NP → プレゼント θNP → プレゼント NP → 香織 NP1 θNP → 香織 NP1 NP → 恵 NP1 θNP → 恵 NP1 NP1 → と NP θNP1 → と NP * 構文木の確率 簡単なCFGの例 パラメータ S → SUBJ VP1 θS → SUBJ VP1 S → SUBJ V θS → SUBJ V SUBJ → NP が θSUBJ → NP が VP1 → OBJ1 V θVP1 → OBJ1 V OBJ1 → NP を θOBJ1 → NP を NP → S NP θNP → S NP V → 送った θV → 送った V → 読んだ θV → 読んだ NP → 香織 θNP → 香織 NP → 恵 θNP → 恵 NP → 電子メール θNP → 電子メール NP → プレゼント θNP → プレゼント NP → 香織 NP1 θNP → 香織 NP1 NP → 恵 NP1 θNP → 恵 NP1 NP1 → と NP θNP1 → と NP S SUBJ VP1 NP が OBJ1 V 香織 読んだ を NP S NP 電子メール SUBJ V NP が 恵 送った 構文木　t 文　s = “香織が恵が送った電子メールを読んだ” P(t) = θS → SUBJ VP1 × θSUBJ → NP が × θNP → 香織 × θVP1 → OBJ1 V × θOBJ1 → NP を × θNP → S NP × θS → SUBJ V × θSUBJ → NP が × θNP → 恵× θV → 送った× θNP → 電子メール × θV → 読んだ * PCFG パラメータ推定 (estimation) 単純な数え上げ (教師付学習) 最尤法 (教師無学習)