PRML読書会第11回 8.4 グラフィカルモデルによる推論 2010-02-06 SUHARA YOSHIHIKO (id:sleepy_yoshi)

Presentation on theme: "PRML読書会第11回 8.4 グラフィカルモデルによる推論 2010-02-06 SUHARA YOSHIHIKO (id:sleepy_yoshi)"— Presentation transcript:

1 PRML読書会第11回 8.4 グラフィカルモデルによる推論 2010-02-06 SUHARA YOSHIHIKO (id:sleepy_yoshi)

2 1 目次 8.4 グラフィカルモデルによる推論 –8.4.1 連鎖における推論 –8.4.2 木 –8.4.3 因子グラフ –8.4.4 積和アルゴリズム –8.4.5 max-sumアルゴリズム –8.4.6 一般のグラフにおける厳密推論 –8.4.7 ループあり確率伝播 –8.4.8 グラフ構造の学習 ここまで

3 2 本発表のポイント (1) 連鎖ノードにおけるメッセージパッシング (2) 因子グラフとは? 因子グラフの作り方

4 3 8.4 グラフィカルモデルに おける推論

5 4 グラフィカルモデルにおける推論 目的: グラフィカルモデルにおける推論 –いくつかのノードが観測された際に，残ったノード (のうちいくつか) の事後分布を知りたい アプローチ –グラフ構造を利用して局所的なメッセージの伝播を 用いて厳密推論を行う –cf. 近似推論は10章で紹介

6 5 ベイズの定理の例 2変数x, y上の同時分布を因数分解する ??? (a) (b) y が観測された (8.47) (8.48) (b) y が観測された (c) ??? ではダメ ?

7 6 8.4.1 連鎖における推論

8 7 無向連鎖のグラフの例 ※有向グラフと同じ条件付き独立性を持つ (8.49) K 状態離散変数 N-1 個 K×K の表 復習 ⇒ 同時分布は (N-1) K 2 個のパラメータを持つ

9 8 周辺分布の推論 連鎖途中のノードの周辺分布を推論したい –どのノードも観測されていない場合 ⇒ x が取りうる状態の数 : K N 個 ポイント : 連鎖の長さ N に対して 指数オーダー O(K N ) のメモリ容量と計算量 周辺分布 (8.50) xnxn コレ x n 以外で周辺化

10 9 STOP! ポテンシャル関数って何なのさ？ (規格化されるので) ψ(x C ) > 0 であればなんでもよい –例えばボルツマン分布: –エネルギー関数も本文中に記述なし ポテンシャル関数の周辺化ってどういうこと? –簡単のためx c ={x 1,x 2 }，x 1,x 2 は0,1の2値離散確率変数とする 私の認識 ポテンシャル関数を使って説明しているのは一般性を保つため 辛くなったら適宜確率に脳内変換すべし

11 10 周辺分布の効率よい推論: 道具立て グラフィカルモデルの条件付き独立性を利用 x N の周辺化の例 x N について 周辺化 x N に依存する部分だけでよい 周辺化のイメージ

12 11 周辺分布の効率よい推論: 本番 代入 さきほどの条件付き独立性を利用

13 12 順序入れ替えによる計算量削減 演算順序による計算量削減の例: を x 1 について周辺化 K×K の演算 同じことを N-1 回繰り返すので， p(x n ) を求めるために必要な 計算量は O(NK 2 ) 3回 ⇒ 2回3回 ⇒ 2回 ポイント : 連鎖の長さ N に対して 線形オーダー O(NK 2 ) の計算量

14 13 局所的なメッセージ伝播 –μ α : 前向きに伝わるメッセージ –μ β : 後ろ向きに伝わるメッセージ 前向き 後ろ向き 規格化係数

15 14 連鎖上全てのノードに対しての推 論 伝播中すべてのメッセージを保存 (1) メッセージμ α をx 1 からx N まで前向きに伝播 (2) メッセージμ β をx N からx 1 まで後ろ向きに伝播 (8.54) 任意のノードの周辺分布を式 (8.54) を用いて計算可能 ※ 1 計算量は 1 つのノードに対する計算量の 2 倍 ※ 2 Z は都合のよいノードで計算すればよい

16 15 演習8.15: 隣接する2点の同時分布 隣接する2点の同時分布 p(x n-1, x n ) x n, x n-1 以外を周辺化する ⇒ (8.54)

17 16 補足: チャップマン-コルモゴロフの等式 ホワイトボードで説明

18 17 8.4.2 木

19 18 メッセージパッシングの拡張 ノードの連鎖から成るグラフでは，ノード数に 線形な時間で厳密推論可能なことを示した 木 (tree) と呼ばれるクラスでも同様に局所的 なメッセージパッシングによる推論が可能 ⇒ 連鎖についてのメッセージパッシングを一般化 した積和アルゴリズムを導出 積和アルゴリズムについては 8.4.4 を乞うご期待！

20 19 木の種類 無向木 –任意のノード間に唯一の経路が存在 有向木 –根 (root) と呼ばれる親を持たないノードを1つだけ持ち，他の全ての ノードは親を1つだけ持つ 多重木 –2つ以上親を持つノードが存在するが，任意の2ノード間の (方向を無 視した) 経路が1つしかない有向グラフ 無向木有向木多重木 モラル化で変化なし モラル化でループが発生

21 20 父1父1 父2父2 子 復習: モラル化 有向グラフから無向グラフへの変換方法 –親同士を結婚させる≒できちゃった婚 子 母 父 結婚 ! 子 母 父 モラル化 母 父1父1 父2父2 子 母 モラル化 ?! 重婚 ! ザ・ばっくれ・バーク レー・ボーイズ by 秋里和国

22 21 モラル化：参考情報 などなど

23 22 演習8.18 有向木によって表現される分布が，対応する無向木上の 等価な分布によって (自明に) 表現されることを示せ． 無向木で表現される分布が，クリークポテンシャルを適 切に規格化することにより，有向木で表現可能であるこ とも示せ．ある与えられた無向木から構築できる有向木 の数を計算せよ． ⇒ ホワイトボードで説明

24 23 8.4.3 因子グラフ

25 24 因子グラフ 有向グラフ，無向グラフを因子グラフで表現 –局所的な変数の部分集合のみに依存する関数の集合 の積として表現可能 (8.5) (8.39) 有向グラフ 無向グラフ 因子グラフ (8.59) ⇒ 親にのみ依存という条件付き独立性を利用 ⇒ 極大クリーク上のポテンシャル関数の積で表現

26 25 因子グラフの例 この因数分解のグラフ表現 無向グラフ表現では，これらの積は ひとつのポテンシャル関数に統合された ⇒ 因子グラフではより詳細な情報が表現される 変数ノード 因子ノード

27 26 有向グラフからの変換 (1) ノードに対応する変数ノードを作る (2) 条件付き分布に対応する因子を付け加える (3) 適切なリンクを加える これはダメ ? なぜ ? 条件付き分布 に着目

28 27 無向グラフからの変換 (1) 各ノードに対応する変数ノードを作る (2) 極大クリークx s に対応する因子ノードを加える 注意点

29 28 局所的な閉路を持つグラフ 有向グラフにおいて，適切な因子関数を設定す ることにより局所的な閉路を除去可能

30 29 複数の因子グラフによる表現 複数の因子グラフが，ひとつの有向グラフ／無向グラフ を表現することがある 何の条件付き独立性も表現しない

31 30 (再掲) 本発表のポイント (1) 連鎖ノードにおけるメッセージパッシング (2) 因子グラフとは? 因子グラフの作り方

32 31 発表まとめ 連鎖による推論を通じて，メッセージによる推 論の概要を解説した 有向／無向グラフから因子グラフと因子関数を 生成する方法を解説した 疑問「因子グラフがなんで嬉しいの?」 続く発表に乞うご期待！

33 32 次回予告

34 33

35 34

36 35 おしまい