人工知能特論II 第6回 二宮 崇 1 今日の講義の予定 確率的文法 品詞解析 構文解析 HMM PCFG 教科書 北研二(著) 辻井潤一(編) 言語と計算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 2 品詞解析 PART-OF-SPEECH (POS) TAGGING 3 品詞解析 品詞タガー “I have a pen.” トーカナイザー I have a pen . POSタガー I 代名詞 have 動詞 a pen 不定冠詞 名詞 . ピリオド 4 隠れマルコフモデル Hidden Markov Model (HMM) (1/3) I he 名詞 出力 (emission) Mary ピリオド … 代名詞 不定 冠詞 遷移 (transition) 動詞 I 代名詞 have 動詞 a pen 不定冠詞 名詞 . ピリオド 5 隠れマルコフモデル Hidden Markov Model (HMM) (2/3) 0.3 ピリオド 0.5 名詞 0.01 0.1 he 0.25 出力 (emission) 0.01 … 代名詞 遷移 (transition) 動詞 have 0.3 Mary 0.43 不定 冠詞 I I a pen 不定冠詞 名詞 . 0.3 代名詞 0.4 動詞 0.01 ピリオド 6 隠れマルコフモデル Hidden Markov Model (HMM) (3/3) Q: 状態の有限集合 Σ: 出力記号の有限集合 πq: 文頭が状態qになる確率 aq,r: 状態qから状態rへの遷移確率 Σr∈Q aq,r=1 bq,o: 状態qにおける記号oの出力確率 Σo∈Σ bq,o = 1 7 状態記号列に対する確率の例 π a b 名詞 代名詞 動詞 不定冠詞 ピリオド 0.2 0.4 0.1 0.3 0.0 遷移元＼遷移先 名詞 代名詞 動詞 不定冠詞 ピリオド 名詞 0.5 0.0 0.3 0.0 0.2 代名詞 0.1 0.0 0.5 0.2 0.2 動詞 0.2 0.2 0.2 0.2 0.2 不定冠詞 1.0 0.0 0.0 0.0 0.0 ピリオド 0.5 0.0 0.5 0.0 0.0 状態＼出力 a … have … I … pen … . … 名詞 0.01 … 0.0 … 0.01 … 0.1 … 0.0 … 代名詞 0.0 … 0.0 … 0.3 … 0.0 … 0.0 … 動詞 0.0 … 0.2 … 0.0 … 0.0 … 0.0 … 不定冠詞 0.2 … 0.0 … 0.0 … 0.0 … 0.0 … ピリオド 0.0 … 0.0 … 0.0 … 0.0 … 1.0 … I 0.3 have 0.2 0.4 0.2 動詞 代名詞 0.5 a 不定冠詞 0.2 pen . 0.1 1.0 名詞 1.0 ピリオド 0.2 0.4*0.3*0.5*0.2*0.2* 0.2*1.0*0.1*0.2*1.0 =0.0000096 8 状態記号列の確率と 生成確率 状態と記号の列が与えられた時 状態記号列 : q1o1q2 o2 qT oT p (q1o1q2 o2 qT oT ) q1 bq1 ,o1 aq1 ,q2 bq2 ,o2 aqT 1 ,qT bqT ,oT q1 aq1 ,q2 aqT 1 ,qT bq1 ,o1 bq2 ,o2 bqT ,oT T T t 2 t 1 q1 aqt 1 ,qt bqt ,ot 記号列のみが与えられた時 記号列 : o1o2 oT p(o1o2 oT ) p(q o q o q o 1 1 2 2 q1Q , q2 Q ,qT Q T T ) (生成確率) 9 品詞解析 品詞解析 (入力: o1o2…oT) q~1q~2 q~T arg max q1Q , q2 Q ,qT Q p(q1o1q2o2 qT oT ) 10 HMMの教師無し学習 Unsupervised Learning of HMMs パラメータ推定 訓練データ (入力) 訓練データ : x1 x2 xn xi : 文を表す記号列 (単語列)。 xi oi1oi 2 oi 3 oiTiとする。 Ti : xiの記号列長 パラメータ (出力) n , a, b arg max p( xi ) , a ,b i 1 n arg max p (oi1oi 2 oiTi ) , a ,b i 1 n arg max , a ,b p(q o q o 1 i1 2 i 2 i 1 q1Q , q2 Q ,qTi Q qTi oiTi ) 11 HMMの教師付学習 Supervised Learning of HMMs パラメータ推定 訓練データ (入力) 訓練データ : x1 x2 xn , y1 y2 yn xi : 文を表す記号列 (単語列)。 xi oi1oi 2 oi 3 oiTiとする。 Ti : xiの記号列長 yi : xiに対応する正解状態列 (正解品詞列)。 yi qi1qi 2 qi 3 qiTiとする。 パラメータ (出力) n , a, b arg max p( xi , yi ) , a ,b i 1 n arg max p(qi1oi1qi 2 oi 2 qiTi oiTi ) , a ,b i 1 12 確率的文脈自由文法 (PCFG) PROBABILISTIC CONTEXT FREE GRAMMAR (PCFG) 13 簡単なCFGの例 CFG: 構文木 S → SUBJ VP1 S S → SUBJ V SUBJ → NP が VP1 → OBJ1 V SUBJ OBJ1 → NP を NP → S NP V → 送った V → 読んだ NP → 香織 NP NP → プレゼント NP → 香織 NP1 NP → 恵 NP1 NP1 → と NP OBJ1 が V を NP 香織 S NP → 恵 NP → 電子メール VP1 SUBJ NP 恵 が NP V 読んだ 電子メール 送った 14 確率的CFG (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 OBJ1 → NP を θOBJ1 → NP を NP → S NP θNP → S V → 送った θV → 送った V → 読んだ θV → 読んだ NP → 香織 θNP → 香織 NP → 恵 θNP → 恵 NP → 電子メール θNP → 電子メール NP → プレゼント θNP → プレゼント NP → 香織 NP1 θNP → 香織 NP1 NP → 恵 NP1 θNP → 恵 NP1 → と NP θNP1 → と が V NP NP1 NP 15 構文木の確率 文 x = “香織が恵が送った電子メールを読んだ” S 構文木 t VP1 SUBJ 簡単なCFGの例 パラメータ S → SUBJ VP1 θS → SUBJ VP1 S → SUBJ V θS → SUBJ V SUBJ → NP が θSUBJ → NP VP1 → OBJ1 V θVP1 → OBJ1 OBJ1 → NP を θOBJ1 → NP を NP → S NP θNP → S V → 送った θV → 送った V → 読んだ θV → 読んだ NP → 香織 θNP → 香織 NP → 恵 θNP → 恵 NP → 電子メール θNP → 電子メール NP → プレゼント θNP → プレゼント NP → 香織 NP1 θNP → 香織 NP1 NP → 恵 NP1 θNP → 恵 NP1 → と NP θNP1 → と NP 香織 が OBJ1 が NP V S SUBJ NP NP が V を 読んだ NP V 電子メール 送った 恵 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 → 読んだ NP1 16 NP 書換規則の制約 Sからの生成 Sからの生成は2通りしかない ので、 S→SUBJ VP1を使う場合 S→SUBJ Vを使う場合 θS → SUBJ VP1+θS → SUBJ V = 1.0 同様にNPも θNP → S NP + θNP → 香織 + θNP → 恵 + θNP → 電子メール + θNP → プレゼント+θNP → 香織 NP1 + θNP → 恵 NP1 = 1.0 簡単なCFGの例 パラメータ S → SUBJ VP1 θS → SUBJ VP1 S → SUBJ V θS → SUBJ V SUBJ → NP が θSUBJ → NP VP1 → OBJ1 V θVP1 → OBJ1 OBJ1 → NP を θOBJ1 → NP を NP → S NP θNP → S V → 送った θV → 送った V → 読んだ θV → 読んだ NP → 香織 θNP → 香織 NP → 恵 θNP → 恵 NP → 電子メール θNP → 電子メール NP → プレゼント θNP → プレゼント NP → 香織 NP1 θNP → 香織 NP1 NP → 恵 NP1 θNP → 恵 NP1 → と NP θNP1 → と が V NP NP1 NP 17 書換規則の制約 CFG書換規則をA→ αと表したとき、(Aは非終端記号、α は非終端記号列)すべての非終端記号Aに対し、 A 1.0 とする。 18 構文木の確率 S 構文木 t CFG G パラメータ S → NP VP θS → NP NP → N PP θNP → N N → N PP N θN → N VP → NP VP θVP → NP VP → V θVP → V 0.7 PP → が θPP → が 0.5 PP → を θPP → を 0.3 PP → と θPP → と 0.2 N → 太郎 θN → 太郎 0.3 N → 花子 θN → 花子 0.2 N → 映画 θN → 映画 0.4 V → 褒める θV → 褒める 0.3 V → 見る θV → 見る 0.7 値 VP 1.0 PP 1.0 PP N 0.1 VP 0.3 VP NP N PP VP NP V 太郎 が PP N 褒める N 花子 PP N と 映画 を p(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 → 褒める = 1.0×1.0×0.3×0.5×0.3×1.0× 0.1×0.2×0.2×0.4×0.3×0.7×0.3 = 0.000004536 19 構文木tの確率 C(r; t): CFG<VN, VT, P, σ>の書換規則r∈Pが 構文木t中で使われた回数 p (t ) r C ( r ;t ) rP 20 文の生成確率 ある文xに対し、xを導出する全ての構文木 集合をT(x)としたとき、 0.0 p ( x) 1.0 p ( x ) p (t ) tT ( x ) PCFGによって生成されうる全ての構文木 集合をTとしたとき、 p(t ) 1.0 tT 21 構文解析 ある文xに対し、CFG<VN, VT, P, σ>を用い てxを導出できる全ての構文木集合をT(x)と したとき、 ~ t arg max p (t ) tT ( x ) arg max r tT ( x ) C ( r ;t ) rP 22 構文解析の例 ”太郎が花子と映画を褒める”に対する構文木は次の二種類しかない 構文木 t1 構文木 t2 S VP NP N 太郎 N が N 花子 PP N と 映画 VP NP VP NP PP S PP V を 褒める N 太郎 p(t1) = θS → NP VP × θNP → N PP2 × θN → 太郎 × θPP → が × θVP → NP VP × θN → N PP N × θN → 花子 × θPP → と× θN → 映画 × θPP → を × θVP → V × θV → 褒める = 1.0×1.02×0.3×0.5×0.3×0.1×0.2×0.2× 0.4×0.3×0.7×0.3 = 0.000004536 NP PP が N 花子 VP と VP NP PP N PP V 褒める 映画 を p(t2) = θS → NP VP × θNP → N PP3 × θN → 太郎 × θPP → が × θVP → NP VP2 × θN → 花子 × θPP → と × θN → 映画 × θPP → を × θVP → V × θV → 褒める = 1.0×1.03×0.3×0.5×0.32×0.2×0.2×0.4× 0.3×0.7×0.3 23 = 0.000013608 PCFGの教師無し学習 Unsupervised Learning of PCFG パラメータ推定 訓練データ (入力) 訓練データ : x1 x2 xn xi : 文 パラメータ (出力) n θ arg max p ( xi ) θ i 1 n arg max p(t ) arg max θ θ i 1 tT ( xi ) n C ( r ;t ) r i 1 tT ( xi ) rP 24 PCFGの教師付パラメータ推定 Supervised Learning of PCFG 教師付学習 訓練データ (入力) 訓練データ : x1 x2 xn , y1 y2 yn xi : 文 yi : xiに対する正解構文木 パラメータ (出力) n θ arg max p( xi , yi ) θ i 1 n arg max p( yi ) θ i 1 n arg max rC ( r ; yi ) θ i 1 rP 25 まとめ 品詞解析 構文解析 HMM PCFG 資料 http://aiweb.cs.ehime-u.ac.jp/~ninomiya/ai2/ 26
© Copyright 2024 ExpyDoc
