Inverted Index Compression and Query Processing

PRML読書会第11回
8.4 グラフィカルモデルによる推論
2010-02-06
SUHARA YOSHIHIKO
(id:sleepy_yoshi)
目次
• 8.4 グラフィカルモデルによる推論
–
–
–
–
–
–
–
–
8.4.1
8.4.2
8.4.3
8.4.4
8.4.5
8.4.6
8.4.7
8.4.8
連鎖における推論
木
因子グラフ
積和アルゴリズム
max-sumアルゴリズム
一般のグラフにおける厳密推論
ループあり確率伝播
グラフ構造の学習
ここまで
1
本発表のポイント
(1) 連鎖ノードにおけるメッセージパッシング
(2) 因子グラフとは? 因子グラフの作り方
2
8.4 グラフィカルモデルに
おける推論
3
グラフィカルモデルにおける推論
• 目的: グラフィカルモデルにおける推論
– いくつかのノードが観測された際に，残ったノード
(のうちいくつか) の事後分布を知りたい
• アプローチ
– グラフ構造を利用して局所的なメッセージの伝播を
用いて厳密推論を行う
– cf. 近似推論は10章で紹介
4
ベイズの定理の例
???
• 2変数x, y上の同時分布を因数分解する
(a) p( x, y)  p( x) p( y | x)
(b) yが観測された
(c) ???
p ( y )   p ( y | x' ) p ( x' )
(8.47)
x'
p( y | x) p( x)
p( x | y ) 
p( y )
(8.48)
p( x, y)  p( x | y) p( y)  p( y | x) p( x) ではダメ?
5
8.4.1 連鎖における推論
6
無向連鎖のグラフの例
K状態離散変数
1
p(x)   1, 2 x1 , x2  2,3 x2 , x3  N 1, N x N 1 , xN 
Z
N-1個
(8.49)
K×Kの表
⇒ 同時分布は (N-1) K2 個のパラメータを持つ
復習
※有向グラフと同じ条件付き独立性を持つ
7
周辺分布の推論
• 連鎖途中のノードの周辺分布を推論したい
– どのノードも観測されていない場合
コレ
xn
周辺分布
p( xn )   p(x)
x1
xn1 xn1
(8.50)
xN
xn以外で周辺化
⇒ xが取りうる状態の数: KN個
ポイント: 連鎖の長さNに対して
指数オーダーO(KN)のメモリ容量と計算量
8
STOP! ポテンシャル関数って何なのさ？
• (規格化されるので) ψ(xC) > 0 であればなんでもよい
– 例えばボルツマン分布:  C (xC )  exp{E(xC )}
– エネルギー関数も本文中に記述なし
• ポテンシャル関数の周辺化ってどういうこと?
– 簡単のためxc={x1,x2}，x1,x2は0,1の2値離散確率変数とする
 C ( x1 )   exp{E( x1 , x2 )}
x2
 exp{E( x1 , x2  0)} exp{E( x1 , x2  1)}
私の認識
ポテンシャル関数を使って説明しているのは一般性を保つため
辛くなったら適宜確率に脳内変換すべし
9
周辺分布の効率よい推論: 道具立て
グラフィカルモデルの条件付き独立性を利用
xNの周辺化の例
 x , x  x , x 
1, 2
1
2
2, 3
2
3
N 1, N
xN 1, xN 
xN
  1,2 x1 , x2  2,3 x2 , x3  N 1, N xN 1 , xN 
xN
周辺化のイメージ
xNに依存する部分だけでよい
 N 1, N ( xN 1 )   N 1, N xN 1 , xN 
xN
xNについて
周辺化
  N 1, N ( xN 1  1, x N  1)   N 1, N ( xN 1  K , xN  1) 









 N 1, N ( xN 1  1, xN  K )   N 1, N ( xN 1  K , xN  K ) 

N 1, N
( xN 1  1)   N 1, N ( xN 1  K )
10
周辺分布の効率よい推論: 本番
p ( x) 
1
 1, 2 x1 , x2  2,3 x2 , x3  N 1, N xN 1 , xN 
Z
代入
p( xn )   p(x)
x1
xn1 xn1
xN
さきほどの条件付き独立性を利用
1 

 
p ( xn ) 
 n1,n xn1 , xn   2,3 x2 , x3  1, 2 x1 , x2  
Z  x
x
x
 
n1
2
1
 ( xn )


 
 n,n 1 xn , xn1   N 1, N xN 1 , xN  
 xn1
 xN
 
 ( xn )
11
順序入れ替えによる計算量削減
• 演算順序による計算量削減の例: ab  ac  a(b  c)
 1,2 ( x1 , x2 ) をx1について周辺化
3回 ⇒ 2回
  1, 2 ( x1  1, x2  1)   1, 2 ( x1  K , x2  1) 







 ( x  1, x  K )   ( x  K , x  K ) 
2
1, 2
1
2
 1, 2 1

  1, 2 ( x2  1) 





 ( x  K ) 
 1, 2 2

K×Kの演算
同じことをN-1回繰り返すので，p(xn)を求めるために必要な
計算量はO(NK2)
ポイント: 連鎖の長さNに対して
線形オーダーO(NK2)の計算量
12
局所的なメッセージ伝播
規格化係数
1
p ( x N )   a ( xn )   ( xn )
Z
Z   a ( xn ) ( xn )
xn
– μα: 前向きに伝わるメッセージ
– μβ: 後ろ向きに伝わるメッセージ
前向き


 a ( xn )   n 1,n ( xn 1 , xn )  
xn1
 xn2 
  n1,n ( xn1 , xn ) ( xn1 )
xn1
後ろ向き


  ( xn )   n,n 1 ( xn , xn 1 ) 
xn1
 xn  2 
  n,n1 ( xn , xn1 ) ( xn1 )
xn1
13
連鎖上全てのノードに対しての推
論
• 伝播中すべてのメッセージを保存
(1) メッセージμαをx1からxNまで前向きに伝播
(2) メッセージμβをxNからx1まで後ろ向きに伝播
a ( x2 ) a ( xn1 ) a ( xn )
a ( xn1 )
 ( x1 )  ( xn2 )
 ( xn1 )
 ( xn )
a ( xN )
 ( xN 1 )
※1 計算量は1つのノードに対する計算量の2倍
※2 Zは都合のよいノードで計算すればよい
任意のノードの周辺分布を式(8.54)を用いて計算可能
1
p( xn )   a ( xn )  ( xn )
(8.54)
Z xn
14
演習8.15: 隣接する2点の同時分布
• 隣接する2点の同時分布 p(xn-1, xn)
xn, xn-1以外を周辺化する
1
p( xn 1 , xn ) 
Z  n1,n xn1, xn 


 
 n 2,n 1 xn 2 , xn 1   2,3 x2 , x3  1, 2 x1 , x2  
x2
 xn2
 x1
 
 ( xn1 )


 
 n,n 1 xn , xn1   N 1, N xN 1 , xN  
 xn1
 xN
 
 ( xn )
⇒ (8.54)
15
補足: チャップマン-コルモゴロフの等式
• ホワイトボードで説明
16
8.4.2 木
17
メッセージパッシングの拡張
• ノードの連鎖から成るグラフでは，ノード数に
線形な時間で厳密推論可能なことを示した
• 木 (tree) と呼ばれるクラスでも同様に局所的
なメッセージパッシングによる推論が可能
⇒ 連鎖についてのメッセージパッシングを一般化
した積和アルゴリズムを導出
積和アルゴリズムについては
8.4.4を乞うご期待！
18
木の種類
• 無向木
– 任意のノード間に唯一の経路が存在
• 有向木
– 根 (root) と呼ばれる親を持たないノードを1つだけ持ち，他の全ての
ノードは親を1つだけ持つ
• 多重木
– 2つ以上親を持つノードが存在するが，任意の2ノード間の (方向を無
視した) 経路が1つしかない有向グラフ
無向木
有向木
モラル化で変化なし
多重木
モラル化でループが発生
19
復習: モラル化
• 有向グラフから無向グラフへの変換方法
– 親同士を結婚させる≒できちゃった婚
父
母
子
父
結婚!
母
子
モラル化
重婚!
父1
父2
父1
母
子
モラル化?!
母
子
父2
ザ・ばっくれ・バーク
レー・ボーイズ
by 秋里和国
20
モラル化：参考情報
などなど
21
演習8.18
• 有向木によって表現される分布が，対応する無向木上の
等価な分布によって (自明に) 表現されることを示せ．
無向木で表現される分布が，クリークポテンシャルを適
切に規格化することにより，有向木で表現可能であるこ
とも示せ．ある与えられた無向木から構築できる有向木
の数を計算せよ．
⇒ ホワイトボードで説明
22
8.4.3 因子グラフ
23
因子グラフ
• 有向グラフ，無向グラフを因子グラフで表現
– 局所的な変数の部分集合のみに依存する関数の集合
の積として表現可能
因子グラフ
p(x)   f s (x s )
(8.59)
s
有向グラフ
⇒ 親にのみ依存という条件付き独立性を利用
K
p(x)   p( xk | pak )
(8.5)
k 1
無向グラフ ⇒ 極大クリーク上のポテンシャル関数の積で表現
1
p(x)   C (xC )
Z C
(8.39)
24
因子グラフの例
p(x)  f a ( x1, x2 ) fb ( x1, x2 ) f c ( x2 , x3 ) f d ( x3 )
• この因数分解のグラフ表現
変数ノード
因子ノード
無向グラフ表現では，これらの積は
ひとつのポテンシャル関数に統合された
⇒ 因子グラフではより詳細な情報が表現される
25
有向グラフからの変換
(1) ノードに対応する変数ノードを作る
(2) 条件付き分布に対応する因子を付け加える
(3) 適切なリンクを加える
条件付き分布
に着目
これはダメ? なぜ?
f ( x1 , x2 , x3 )
f a ( x1 )  p( x1 )
 p( x1 ) p( x2 ) p( x3 | x1 , x2 )
fb ( x2 )  p( x2 )
f c ( x1, x2 , x3 )  p( x3 | x1, x2 )
26
無向グラフからの変換
(1) 各ノードに対応する変数ノードを作る
(2) 極大クリークxsに対応する因子ノードを加える
f ( x1 , x2 , x3 )   ( x1 , x2 , x3 )
注意点
f a ( x1 , x2 , x3 ) f b ( x2 , x3 )
  ( x1 , x2 , x3 )
f a ( x1, x2 , x3 ) fb ( x2 , x3 )   ( x1 , x2 , x3 ) ( x2 , x3 )
27
局所的な閉路を持つグラフ
• 有向グラフにおいて，適切な因子関数を設定す
ることにより局所的な閉路を除去可能
f ( x1, x2 , x3 )  p( x1 ) p( x2 | x1 ) p( x3 | x1 , x2 )
28
複数の因子グラフによる表現
• 複数の因子グラフが，ひとつの有向グラフ／無向グラフ
を表現することがある
p(x)  f ( x1 , x2 , x3 )
p(x)  f a ( x1 , x2 ) fb ( x1 , x3 ) f c ( x2 , x3 )
何の条件付き独立性も表現しない
29
(再掲) 本発表のポイント
(1) 連鎖ノードにおけるメッセージパッシング
(2) 因子グラフとは? 因子グラフの作り方
30
発表まとめ
• 連鎖による推論を通じて，メッセージによる推
論の概要を解説した
• 有向／無向グラフから因子グラフと因子関数を
生成する方法を解説した
• 疑問「因子グラフがなんで嬉しいの?」
続く発表に乞うご期待！
31
次回予告
32
…
地ノほこ
獄ーんれ
だテとか
ーうら
シのが
ョ
ン
33
34
おしまい
35

Download Report