数理言語情報論　第11回 2009年12月16日 数理言語情報学研究室　講師　二宮　崇

今日の講義の予定 単一化アルゴリズム HPSGのフルパージング 生成モデルと識別モデル 教科書 北研二(著) 辻井潤一(編) 言語と計算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

型付素性構造の単一化アルゴリズム データ構造 アルゴリズム 型テーブル ヒープ ポインタ Unify(F, G) 破壊的単一化アルゴリズム 出力: F, Gのポインタは同じデータを指し、そのデータがF, Gの単一化の結果

型テーブル：型定義 （復習）型階層 特殊 一般 adj verb 正方形 perp 円筒 長方形 菱形 subst 円 func 四角 丸 plus minus head bool 図形 ⊥ 一般 (ボトム)

型テーブル:型の包摂関係 t4 ⊔ t9=t12 型単一化の結果: 共通の特殊な型のうち最も一般な型 特殊 一般 t13 t8 t6 t12 ⊥ 一般 (ボトム)

型テーブル 型定義は単一化実行前に与えられていると仮定 静的に全ての型の組み合わせに対する単一化を計算 t ⊔u=u ⊔tなので、表の半分だけ計算すれば良い スパースになるケースが多いのでハッシュで実装することが多い ⊥ t1 t2 t3 t4 t5 t6 t7 t8 t9 t10 t11 t12 t13 -

ヒープとセル ヒープ セル セルの列 タグとデータのペア アドレス タグ データ 0x00000000 VAR a 0x00000001 STR e 0x00000002 0x00000003 INT 15 0x00000004 FLO 0.335 0x00000005 f 0x00000006 PTR 0x00000007 STG “Taro” ...

ヒープとヒープポインタ ヒープには使用領域と未使用領域の二つがある ヒープポインタ 新しいデータは未使用領域に追加される 未使用領域の先頭アドレス（＝使用領域の末尾アドレス＋１）を格納した変数 0x00000000 0x00000001 ..... 0xffffffff used ヒープポインタ unused

タグの種類 重要なタグ 特殊なデータのためのタグ VAR: 枝をまだ持っていないノード。データ部は整数の型ID。 STR: 枝を持つノード。データ部は整数の型ID。 PTR: ポインタ。データ部はアドレス。 特殊なデータのためのタグ INT: 整数(integer) FLO: 浮動小数 STG: 文字列

ヒープ上の素性構造 F F アドレス タグ データ 0x00010000 STR d 0x00010001 VAR e 0x00010002 PTR 0x00010005 0x00010006 0x00010007 ... d F: G: F d F: G: e a 10

VAR もしかしたら今後、枝(素性)を持つようになるかもしれないけど今は持っていないノード データ部にはノードの型のID (整数値)を格納 枝を持つようになったら、ポインタで上書きして、ポインタの先に新しい枝つきのデータを作成 アドレス タグ データ .... ... 0x00010001 VAR e アドレス タグ データ .... ... 0x00010001 PTR 0x0020002e STR e 0x0020002f VAR g HP

STR 枝(素性)つきノード 後続するアドレスのセルにはそのノードが持つ素性の値が入る データ部にはノードの型のID(整数) 後続するアドレスのセルにはそのノードが持つ素性の値が入る 素性の順番はSTRタグを持ったノードの型と素性によって静的に決定しておく Index(f, t)=1, 2, 3,...,nt 例えば、素性にIDをつけて、型tがもつ素性集合のうちIDの昇順に並べる、など。型tが素性fを持たない時は0を返すようにすると便利 新しくSTRタグのデータをつくるときは、その素性値にはデフォルト値として、appropriateな型を格納する Approp(f, t) アドレス タグ データ .... ... 0x00010001 STR e 0x00010002 VAR g 0x00010003 PTR 0x0001023f

PTR 実データを指すポインタ ポインタはチェーンになっていても構わない 手続き型言語でよくあるポインタのポインタといった複雑な構造ではないので注意！ アドレス タグ データ .... ... 0x00010001 PTR 0x00010005 0x00010002 STR f 0x00010003 VAR g 0x00010004 0x00010006 0x00010007 h 矢印が指すアドレスの素性構造は全部同じ(0x00010007のデータ)

Deref ポインタを辿って実データのアドレスを得る操作 Deref( p ) ## アドレス p while(Heap[p].tag = PTR ) ## タグがPTR p := Heap[p].data ## pをアドレスpのセルのデータで置き換える return p 0x00010001 PTR 0x00010005 0x00010002 STR f 0x00010003 VAR g 0x00010004 0x00010006 0x00010007 h Deref(0x00010001) = 0x00010007

ポインタに対する考え方 同じノードを指すポインタの集合 local local foo cat nil valence noun nom HOGE: cat VALENCE: nil COMPS: valence noun nom CASE: nil SPR:

ポインタに対する考え方 どこから指されているのか気にせず実データの書き換えを簡単に行える goo goo 今ここを書き変えたい local CAT: local CAT: DEE: dee cat cat

単一化アルゴリズム(1/8) Unify(p, q): アドレス pとアドレス qの素性構造を単一化 もしp=qなら終了 p tp q tq G: I: G: H: H: もしp=qなら終了

単一化アルゴリズム(2/8) Unify(p, q): アドレス pとアドレス qの素性構造を単一化 新しいノードを生成 r p tp q tr tq F: G: I: G: H: H: 新しいノードを生成 ノードの型trはtr = tp ⊔ tq

単一化アルゴリズム(3/8) Unify(p, q): アドレス pとアドレス qの素性構造を単一化 pとqをrを指すポインタに書換 r p tr F: G: I: G: H: H: pとqをrを指すポインタに書換

単一化アルゴリズム(4/8) Unify(p, q): アドレス pとアドレス qの素性構造を単一化 r p q tr F: G: I: F: G: H: H: G: H: J: I: 新しいノードの型trが持つ素性に対する枝を作る

単一化アルゴリズム(5/8) Unify(p, q): アドレス pとアドレス qの素性構造を単一化 共通でない素性には単純にポインタをはる r p q tr F: G: I: F: G: H: H: G: H: J: I: 共通でない素性には単純にポインタをはる

単一化アルゴリズム(6/8) Unify(p, q): アドレス pとアドレス qの素性構造を単一化 r p q tr G: F: G: H: H: G: H: J: I: tpにもtqにもない新しい素性J:にはAppropriateな型(trと素性J:に対して定義されるデフォルトの型）のノードを生成

単一化アルゴリズム(7/8) Unify(p, q): アドレス pとアドレス qの素性構造を単一化 r p q tr G: F: G: H: H: G: H: J: I: 共通の素性G: H: に対しては、とりあえず、pかqのどちらかの素性G:H:が指すノードに対し、ポインタを貼る

単一化アルゴリズム(8/8) Unify(p, q): アドレス pとアドレス qの素性構造を単一化 r p q tr p’’ q’ G: p’ F: q’’ G: H: H: G: H: J: I: Unify(p’, q’)とUnify(p’’, q’’)を再帰呼び出し

単一化アルゴリズム: まとめ Unify(p, q) # pとqはヒープ上のアドレス p := Deref(p); q := Deref(q); if( p = q ) return true; r := HP; HP := HP + 1; tagp := Heap[p].tag; tp := Heap[p].data; tagq: = Heap[q].tag; tq := Heap[q].data; tr :=Type-Unify(tp, tq); if (tr is not defined ) return false; Heap[p].tag := PTR; Heap[p].data := r; Heap[q].tag := PTR; Heap[q].data := r; Heap[r].tag := STR; Heap[r].data := tr; HP := HP + |Features(tr)|; foreach f ∈ Features(tr) if( f ∈ Features(tp) ∧ tagp = STR ) Heap[r + index(f, tr)].tag := PTR; Heap[r + index(f, tr)].data := p + index(f, tp) else if( f ∈ Features(tq) ∧ tagq = STR ) Heap[r + index(f, tr)].tag := PTR; Heap[r + index(f, tr)].data := q + index(f, tq) else Heap[r + index(f, tr)].tag := VAR; Heap[r + index(f, tr)].data := Approp(f, tr) foreach f ∈ (Features(tp) ∩ Features(tq)) if( ￢Unify(p + index(f, tp), q + index(f, tq)) ) return false; return true;

単一化アルゴリズムの特徴 素性構造にサイクルがあってもok 必ず終了する Unifyが再帰呼び出しされる度に実体ノード（ポインタ以外のノード）が一つずつ減る appropriateな型のノードが生成される時のみVARノードが増えるが、このノードを無視すれば、各ステップでノードが一つずつ減る VARノードを無視しても良い大雑把な説明 アルゴリズムを改良して、タグの組み合わせで処理を分類すると、各ステップでSTRノードの数が増えないようにすることができる VARとVAR→VAR (STRノード数は減らない) VARとSTR→STR (STRノード数は減らない) STRとSTR→STR( STRノード数がひとつ減る) 各STRノードが持つことができるVARノードは全ての型に対する最大素性数で抑えられるため、実ノード数をSTRノード数×最大素性数と考えれば、この数は各ステップごとに一つずつ減るので、必ず終了する

⊔ = 単一化の例 (1) 異なる型の場合は、型単一化を行う。型単一化に失敗すると、全体の単一化も失敗 F: G: F: G: F: G: F: a G: b F: a G: b F: a ⊔ = G: F: c G: H: a F: c H: a I: a J: b I: a J: b 異なる型の場合は、型単一化を行う。型単一化に失敗すると、全体の単一化も失敗

単一化の例 (1) Unify(p, q) q p G: F: F: G: G: F: G: H: F: F: J: I: b a a a c a b

単一化の例 (1) Unify(p, q) p q G: F: F: G: G: F: G: H: F: F: J: I: b a a a c a b

単一化の例 (1) Unify(p, q) p q G: F: G: F: G: H: F: F: J: I: b a a a c a b

単一化の例 (1) Unify(p, q) q p G: F: G: F: G: H: F: a J: I: b a b c a

⊔ = 単一化の例 (2) 1 1 1 1 (a⊔c=dとする) F: F: a F: F: G: F: d F: a G: b G: H:a F: a G: b ⊔ = 1 1 F: c H: a 1 1 (a⊔c=dとする)

単一化の例 (2) Unify(p, q) q p F: G: F: G: F: G: H: F: F: a b a c a

単一化の例 (2) Unify(p, q) q p F: G: F: G: F: G: H: F: F: a b a c a

単一化の例 (2) Unify(p, q) q p G: F: G: F: G: H: F: F: a b a c a

単一化の例 (2) Unify(p, q) q p G: F: G: G: F: H: F: b a c a

単一化の例 (2) Unify(p, q) q p G: F: G: F: H: F: b a c a

単一化の例 (2) Unify(p, q) q p G: F: F: H: G: F: b a a c

単一化の例 (2) Unify(p, q) q p G: F: F: H: G: b d a

HPSGのスキーマの単一化 synsem: dtrs: right-dtr: left-dtr: スキーマ （＝句構造規則）

HPSGのスキーマの単一化 ここが新しい親になる スキーマ （＝句構造規則） synsem: dtrs: right-dtr: left-dtr: right daughter left daughter 単一化 単一化

Reduce Sign 子供の部分はいらないので切ってしまう ここが新しい親になる synsem: dtrs: right-dtr: left-dtr: 子供の部分はいらないので切ってしまう

Reduce Sign 子供(daughters)の部分をカット 子供がまるまる残っていると、構文木のルートノードに全ての展開された構文木集合が格納されてしまう（簡単に数百億以上の構文木になってしまう） そこで、子供の部分をカットしてCKYチャートに格納してやればよい

CKYアルゴリズム CFGのCKYアルゴリズムとの違い 非終端記号のかわりに素性構造が格納される 子供をカットする操作 (reduce sign)が必要 単一化は破壊的操作なので、実行前にコピーをして元の素性構造を残しておく ルール規則の適用 CFG: 非終端記号X, Yに対し、G(X, Y)は親の非終端記号集合を返す HPSG: 素性構造X, Yに対し、G(X, Y)は親の素性構造集合を返す ファクタリング CFG: 等価な非終端記号 HPSG: 等価な素性構造 (X = Y iff X ⊑Y and X ⊒ Y) デコーディングの時も同様 ⊑⊏⊒⊔⊐

CKY法 for HPSG for j = 1 to n Sj-1,j := L(wj) ## Lは単語wに対する素性構造の集合を返す関数 for l = 2 to n for i = 0 to n – l j := i + l; for k = i+1 to j - 1 forall X∈Si,k forall Y∈Sk,j forall b ∈ BS # BSはバイナリースキーマの集合 X’ := copy(X); Y’ := copy(Y); b’ := copy(b) Si,j := Si,j ∪ Reduce(b’(X’, Y’)) Si,j := Si,j ∪ U(Si,j) ## Uはユーナリールールの適用手続き

等価性チェックとコピー 構造共有があるため素性構造の等価性チェックやコピーはそんなに簡単ではない 破壊的でない操作 すでに辿ったセルのアドレスをハッシュにいれておいて構造共有をチェック 破壊的操作＋バックトラック すでに辿ったセル上にマーキングタグと対応する相手側のアドレスを書き込む 変更履歴をたどることによって元のデータに戻す（バックトラック）

不完全ながら高速な等価性チェック セルの列とセルの列を単純なforループで簡単にチェック コピーする際に、ポインタの作り方や部分構造の作り方を工夫すれば、等価な素性構造はまったく同じセルの列になる ただし、VARタグを展開していない場合とVARタグが展開されてSTRになっている場合では正しいチェックができないので注意

HPSGの確率モデル？ PCFGは各書換規則に対応するパラメータを用意すれば良かった HPSGでは？？ NP 構文木　t S PCFGは各書換規則に対応するパラメータを用意すれば良かった HPSGでは？？ VP1 SUBJ NP OBJ1 V が 読んだ 香織 NP を S NP SUBJ V 電子メール NP が 送った 恵 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 → 読んだ

PHON: <he, gives, her, a present> VAL: SUBJ: <> COMPS: <> SPR: <> PHON: <gives, her, a present> VAL: SUBJ: < > COMPS: <> SPR:<> 1 PHON: <gives, her> VAL: SUBJ:< > COMPS:< > SPR:<> 1 3 PHON: <gives> VAL: SUBJ: < > COMPS: < , > SPR: <> 1 2 3 1 NP[nom][3rd, sing] NP[acc] 3 NP[acc] 2 he gives her a present

生成モデルから識別モデルへ 生成モデル CFGによる生成のステップ（書換規則の適用 A → B C）の確率をp(B C| A)とする p(B C |A)=θA→B Cとおき、これらパラメータの集合をθとおく CFGによる生成の過程の確率を、独立な事象の(条件付き)確率の積とする 全ての文sと構文木tに対する同時確率p(s, t)を計算できる

生成モデルの改良の先に 構文木の分岐の外の情報を条件部に導入 素性（特徴）という考え方 マルコフ文法 M→L...H...Rの確率 素性（特徴）という考え方 条件部をどんどんリッチにして線形補間をとればよいのでは？→構文木のノードxの確率p(x)=p(x|x周辺の状況)

生成モデルの問題点 生成モデルの問題点 独立性の仮定 PCFGでは、各構文木ノードは独立な(条件付き）試行により生成されていると仮定している 例えば、(S (NP John) (VP eats (NP apples)))という構文木は、以下の独立な（条件付き）事象に分解されている SからNP VPを生成 NPからJohnを生成 VPからeats NPを生成 NPからapplesを生成 結果、上記のNPの文脈(S→NP VP)から導出されたNPか(VP→eats NP)から導出されたNPかわからなくなっている→主語のNPなのか目的語のNPなのかわからない。

生成モデルの問題点 生成モデル しかし、 　であるからp (s;θ) が計算できてしまう分、冗長なモデルになっている。間接的に分類問題を解いている。 独立性を仮定した事象に分解しないと同時確率を計算することができない

識別モデル 識別モデル 直接 を解く 独立な事象を仮定しない 「条件部の確率」をモデルにいれない

生成モデルと識別モデル (イメージ) 生成モデル 識別モデル GOOD BAD

生成モデルと識別モデル （イメージ２） 生成モデル 識別モデル 絵を描いて全体像の比較 それぞれの特徴を比較 鼻の位置 耳の形 体の大きさ 舌の表面

識別するための訓練 教師付学習 良い例と悪い例を与えて、どこに注目すればより良く識別出来るのか学習 good examples bad examples

… 識別モデル s = “A blue eye girl with white hair and skin walked” 素性ベクトル (特徴ベクトル) (0,0,1,0) (1,0,1,0) (1,1,1,0) (0,0,1,1) (1,0,0,0) t1 t2 t3 t4 … tn 文法Gによりsから導出出来る全ての構文木集合 p(t3|s) はt1,t2,t3,..,tnからt3を選択する確率

生成モデルと識別モデル 生成モデル 識別モデル 1.0

どちらが優秀なのか？ Tom Minka (2005) Discriminative models, not discriminative training, MSR-TR-2005-144, 1 p. xを入力(文)、yを出力(構文木)としたときのパラメータ推定 生成モデル 識別モデル 一般モデル θ = θ’

まとめ 単一化アルゴリズム HPSGフルパージング 生成モデルと識別モデル 次回は、1/13(水) 16:30～ ロジスティック回帰と確率的HPSGとCRF 講義資料 http://www.r.dl.itc.u-tokyo.ac.jp/~ninomi/mistH21w/cl/

レポート課題 課題（いずれかのうち一つ） 言語学、パージングもしくは機械学習に関する論文を一つ以上読んで内容をまとめ、考察を加えよ。ただし、論文は次の国際会議から選ぶこととする。 NLP系の国際会議: ACL, NAACL, EACL, COLING, EMNLP 機械学習系の国際会議: ICML, NIPS, COLT, UAI, AIStats 人工知能系の国際会議: IJCAI, AAAI データマイニング系の国際会議: KDD, SDM, ICDM 授業内容でよくわからなかった箇所を教科書やスライドを頼りに例題を作りつつ内容をまとめ、考察せよ 例: CCGやHPSGで簡単な文法を紙の上に書き、紙の上で構文解析 例: 正規分布の混合分布に対するEMの導出 例: エントロピー最大化によるパラメータ推定とパラメトリック形式の最尤法によるパラメータ推定が一致することを確認 授業内容に関連する内容を発展させた内容を調査もしくは考察 例: 最大エントロピー法のスムージングのための正規分布の事前分布 例: 準ニュートン法について調べる

レポート課題 A4で4ページ以上 日本語か英語 締切: 2010年2月17日(水曜) 提出先 レポートには所属、学籍番号、名前を記入 工学部6号館 1F 計数教務室 レポートには所属、学籍番号、名前を記入