PCFG の EM アルゴリズムとス ムージング 二宮 崇 1

今日の講義の予定 PCFG (Probabilistic Context Free Grammar, 確率付 文脈自由文法 ) EM アルゴリズム スムージング 教科書 北研二 ( 著 ) 辻井潤一 ( 編 ) 言語と計算 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,

PCFG の最尤推定 次の二文を訓練データとして、パラメータ 推定 “John sees Mary with_a_telescope” “Mary with_a_telescope runs” rPrPr S → NP VP 1.0 VP → VP PP θ1θ1 VP → V NP θ2θ2 VP → V θ3θ3 NP → NP PP θ4θ4 NP → John θ5θ5 NP → Mary θ6θ6 PP → with_a_telescope 1.0 V → sees θ7θ7 V → runs θ8θ8 3

PCFG の最尤推定 S S NP VP John with_a_telescope V V NP Mary sees 構文木 t 1,1 PP NP 構文木 t 1,2 S S VP John with_a_telescope V V NP Mary sees PP VP NP 構文木 t 2,1 S S VP with_a_telescope V V NP Mary runs PP NPNP NPNP θ1θ1 θ2θ2 θ2θ2 θ5θ5 θ5θ5 θ7θ7 θ7θ7 θ6θ6 θ6θ6 θ4θ4 θ3θ3 θ8θ8 θ4θ4 θ6θ6 t s,u : s は文 ID u は s に対する構文木集 合の中での各々の木 ID 4

PCFG の最尤推定 問題 PCFG の場合この制約を満たすように最大値を 求めなければならない 制約付き極値問題⇒ラグランジュの未定乗数法 PCFG の場合この制約を満たすように最大値を 求めなければならない 制約付き極値問題⇒ラグランジュの未定乗数法 文 1 に対する確率文 2 に対する確率 5

PCFG の最尤推定 ラグランジュの未定乗数法 6

PCFG の最尤推定 結果 θ 1 = θ 2 = θ 3 = θ 4 = θ 5 = θ 6 = θ 7 = 0.5 θ 8 = 0.5 rPrPr S → NP VP 1.0 VP → VP PP θ1θ1 VP → V NP θ2θ2 VP → V θ3θ3 NP → NP PP θ4θ4 NP → John θ5θ5 NP → Mary θ6θ6 PP → with_a_telescope 1.0 V → sees θ7θ7 V → runs θ8θ8 7

EM アルゴリズム 最尤推定をコンピュータで行うためによく 用いられるアルゴリズム アルゴリズム 1. θ : = 適当な値 2. [E ステップ ] θ を用いて各構文木の確率を計算 3. [M ステップ ] 全体の尤度がより高くなる新し い θ を求める に戻る 8

EM アルゴリズム : E ステップ θ (i) : 前回求めたパラメータ 各構文木の確率 9

EM アルゴリズム : M ステップ 書換規則の適用回数 rPrPr C(r; t 11 )C(r; t 12 )C(r; t 21 )C’(r; t 11 )C’(r; t 12 )C’(r; t 21 ) S → NP VP ??1 VP → VP PP θ1θ1 010??0 VP → V NP θ2θ2 110??0 VP → V θ3θ3 001??1 NP → NP PP θ4θ4 101??1 NP → John θ5θ5 110??0 NP → Mary θ6θ6 111??1 PP → with_a_telescope ??0 V → sees θ7θ7 110??0 V → runs θ8θ8 001??1 10

EM アルゴリズム : M ステップ 各構文木ごとの書換規則の適用回数の期待 値 更新パラメータ 11

EM アルゴリズムの心 S S NP VP John with_a_telescope V V NP Mary sees 構文木 t 11 PP NP 構文木 t 12 S S VP John with_a_telescope V V NP Mary sees PP VP NP 構文木 t 21 S S VP with_a_telescope V V NP Mary runs PP NPNP NPNP θ1θ1 θ2θ2 θ2θ2 θ5θ5 θ5θ5 θ7θ7 θ7θ7 θ6θ6 θ6θ6 θ4θ4 θ3θ3 θ8θ8 θ4θ4 θ6θ6 ・新しいパラメータは単純な数え上げと同様に書換規則の適 用頻度から求まる ・ただし、曖昧性のある文に対しては、書換規則の適用頻度 の期待値として数え上げる ・構文木の確率は現在のパラメータから求まる ・新しいパラメータは単純な数え上げと同様に書換規則の適 用頻度から求まる ・ただし、曖昧性のある文に対しては、書換規則の適用頻度 の期待値として数え上げる ・構文木の確率は現在のパラメータから求まる 12

EM アルゴリズム : まとめ 1. θ (0) : = 適当な値 2. [E ステップ ] θ (i) を用いて各構文木の確率を計 算 3. [M ステップ ] θ (i+1) を求める に戻る 13

EM アルゴリズム ( 一般 ) 1/2 パラメータ : θ 入力 : x 隠れ状態 : z データ : S={x (1), x (2), …, x (n) } 対数尤度 : L S (θ) 14 (Jensen の不等式 )

EM アルゴリズム ( 一般 ) 2/2 E ステップ M ステップ 15 隠れ状態の確率とパラメータを交互に動かして、 F を最大化

EM アルゴリズム : 局所解 極値を求めているので最適解とは限らない 良い解が得られるかどうかは初期値に依存 している 色々な初期値を試す 他の頻度情報を使って初期値を設定 16

EM アルゴリズム : 結果 iθ1θ2θ3θ4θ5θ6θ7θ

おまけ : 解析的に求めるのが難 しい PCFG の例 “ 太郎が花子と映画を褒める ” S S NP VP N N が が 太郎 褒める NP PP を を N N N N N N と と 花子 映画 構文木 t 1 PP PP p(t 1 ) = θ 3 θ 4 θ 5 θ 6 θ 7 θ 8 θ 9 θ 10 θ 11 θ 12 p(t 2 ) = θ 4 2 θ 5 θ 6 θ 7 θ 8 θ 9 θ 10 θ 11 θ 12 θ 3 +θ 9 +θ 10 +θ 11 =1, θ 4 +θ 5 =1, θ 6 +θ 7 +θ 8 =1, θ 12 +θ 13 =1 V V VP S S NP VP N N が が 太郎 褒める NP PP を を NP N N N N と と 花子 映画 構文木 t 2 PP PP V V VP rPrPr S → NP VP θ1θ1 NP → N PP θ2θ2 N → N PP N θ3θ3 VP → NP VP θ4θ4 VP → V θ5θ5 PP → が θ6θ6 PP → を θ7θ7 PP → と θ8θ8 N → 太郎 θ9θ9 N → 花子 θ 10 N → 映画 θ 11 V → 褒める θ 12 V → 見る θ 13 18

頻度のディスカウンティング ゼロ頻度問題 ある単語がたまたま訓練コーパス中に出現し なかったら、その単語に対するパラメータは 0 になってしまう その単語が出現するテストコーパスの構文木 の確率は 0 になってしまう ! 対策 : 出現回数を補正 19

加算法 (additive method) ラプラス法 頻度に 1 を加える N: 訓練データ中に出現した単語の総数 V: 出現確率の合計を 1 にするための定数 (n 単語列の異なり 総数に等しい ) 一般の方法 ( リッドストーン法とも呼ばれる ) 頻度に小さな値 (δ) を加える δ=1/2 の時、予期尤度推定法 (expected likelihood estimation) 、あるいはジェフリース・パークス法を呼 ばれる 20

ヘルドアウト推定法 訓練データを二分割 訓練データ ヘルドアウトデータ ( C h をヘルドアウトデータ中の 出現回数とする ) 訓練データでの出現回数をヘルドアウトデー タでの出現回数で置き換える 21

削除推定法 (deleted estimation) ヘルドアウト推定法のクロスバリデーショ ン版 訓練データとヘルドアウトデータの役割をさ らに交換すれば 2 倍データが増える 22

グッド・チューリング推定法 (Good-Turing estimation) 出現回数の補正値として次の r* を用いる 出現確率 23

各種推定法による比較 AP コーパス中の 2 単語組の出現回数の推定 最尤推定ラプラス法ヘルドアウト 法 削除推定法グッド・チューリ ング法

まとめ PCFG と EM アルゴリズム EM アルゴリズム ディスカウンティング 25