グラフィカルモデル
339 Views
August 02, 23
スライド概要
PRMLのグラフィカルモデルの章をまとめたものです．
関連スライド
各ページのテキスト
グラフィカルモデル 公⽴⼩松⼤学 藤⽥ ⼀寿 PRMLの個⼈的に気になるところをまとめたものです．個⼈的に分 かりにくいところには説明および計算を追加してあります．
同時分布の分解 • 3変数𝑎, 𝑏, 𝑐の同時分布𝑝 𝑎, 𝑏, 𝑐 を考える． • 乗法定理を適⽤すると • 𝑝 𝑎, 𝑏, 𝑐 = 𝑝 𝑐 𝑎, 𝑏 𝑝 𝑎, 𝑏 • と書ける．更に，もう⼀度，第2因⼦に乗法定理を適⽤すると • 𝑝 𝑎, 𝑏, 𝑐 = 𝑝 𝑐 𝑎, 𝑏 𝑝 𝑏 𝑎 𝑝 𝑎 • と書ける．この分解は任意の同時分布に対して常に可能である．
同時分布をグラフィカルモデルで表現 • 確率分布をグラフで表現したものをグラフィカルモデルという． • 確率変数をノード（円）で書く． 𝑎 • 3変数なのでノードが3つある． 𝑏 • 条件付き分布を⽮印（有向エッジ）で書く． • ⽮印は，条件から発する． • 𝑝 𝑏 𝑎 なら𝑎から𝑏へ⽮印を書く． 𝑐 𝑝 𝑎, 𝑏, 𝑐 = 𝑝 𝑐 𝑎, 𝑏 𝑝 𝑏 𝑎 𝑝 𝑎 のグラフィカルモデル
全結合 • 𝐾個の変数を持つ同時分布𝑝 𝑥! , … , 𝑥" を考える． • これも，乗法定理を適⽤することで次のように書ける． • 𝑝 𝑥! , … , 𝑥" = 𝑝 𝑥" 𝑥! , … , 𝑥"#! … 𝑝 𝑥$ 𝑥! 𝑝 𝑥! • この同時分布のグラフィカルモデルは，𝐾個のノードを持つ． • さらに，すべての変数は右辺の因⼦のうちの1つの条件付き分布に対応し， その条件は変数に割り振られた番号より⼩さい番号が割り振られた変数と なる． • この場合，⾃⾝の割り振られた番号より⼩さい番号が割り振られたすべて のノードと有向エッジにより接続する． • このグラフはすべてのノードの組に対しエッジを持つので全結合であると いう．
グラフから同時分布を読み取る • 図のグラフから同時分布を読み取る． • ⽮印は条件付き分布を表されることに注意し読み取ると，同時分布は その条件付き分布の積だから • 𝑝 𝑥! 𝑝 𝑥" 𝑝 𝑥# 𝑝 𝑥$ 𝑥! , 𝑥" , 𝑥# 𝑝 𝑥% 𝑥! , 𝑥# 𝑝 𝑥& 𝑥$ 𝑝 𝑥' 𝑥$ , 𝑥% x1 • となる． x2 x3 x4 x5 x6 x7
分解 • グラフによって定義される同時分布は，グラフ上で親に対応する変数 により条件付けられる． • したがって，𝐾個のノードを持つグラフに対応する同時分布は次のよ うに書ける． • 𝑝 𝑥 = ∏* ()! 𝑝 𝑥( pa( • pa( はノード𝑘の親ノード集合を表し，𝑥 = {𝑥! , … , 𝑥* }である． • これは同時確率を分解することが出来ることを⽰す重要な式である． • ノードに対し1つ変数が対応するとしてきたが，ノードに対して変数集 合を対応させても良い．
有向⾮循環グラフ • ここで考えている有向グラフは，有向閉路を持たない成約を満たして いる． • このようなグラフを有向⾮循環（巡回）グラフという． 𝑎 𝑎 𝑏 𝑐 ⾮循環グラフ 𝑏 𝑐 循環グラフ
条件付き独⽴
条件付き独⽴性 • 3変数𝑎, 𝑏, 𝑐を考える．𝑎の条件付き分布が𝑏に依存しないとする． • すなわち，𝑝 𝑎 𝑏, 𝑐 = 𝑝 𝑎 𝑐 を仮定する． • このとき，𝑐が与えられた元では𝑎は𝑏に対して条件付き独⽴であると いう． • ここで，𝑐で条件付けられた𝑎と𝑏同時分布を考える． • 𝑝 𝑎, 𝑏 𝑐 = 𝑝 𝑎 𝑏, 𝑐 𝑝 𝑏 𝑐 = 𝑝 𝑎 𝑐 𝑝 𝑏 𝑐 • 同時分布はこのように表される． • 𝑐が与えられたとき，𝑎と𝑏の同時分布は𝑎と𝑏の周辺分布の積となる． • すなわち，𝑐が与えられたとき，𝑎と𝑏は統計的独⽴である．
例1 • 図のグラフの同時分布は • 𝑝 𝑎, 𝑏, 𝑐 = 𝑝 𝑎 𝑐 𝑝 𝑏 𝑐 𝑝 𝑐 • と書ける．この場合，𝑎と𝑏が独⽴かどうかは，両辺を𝑐で周辺化すれ ば分かる． • 𝑝 𝑎, 𝑏 = ∑+ 𝑝 𝑎 𝑐 𝑝 𝑏 𝑐 𝑝 𝑐 • この式は𝑝 𝑎 と𝑝 𝑏 の積に分解できないので， 𝑎と𝑏は独⽴ではない． c a b
例2 • 図のように𝑐が観測値で固定化されている状態では，同時分布は 𝑐 によ り条件付されている．この時，グラフが表す同時分布は c • 𝑝 𝑎, 𝑏 ∣ 𝑐 = , -,/,+ , + = , 𝑎𝑐 , 𝑏 , + 𝑐 , + =𝑝 𝑎 𝑐 𝑝 𝑏 𝑐 a • と書ける．よって，𝑎と𝑏は独⽴である． • 例1と例2は，ノード𝑐がノード𝑎からノード𝑏への経路に対して，tailto-tailであると⾔われる． • この例では𝑐が条件付けることで，𝑎から𝑏への経路が遮断され，それ らを条件づき独⽴にする． b
例3 • 図のグラフの同時分布は • 𝑝 𝑎, 𝑏, 𝑐 = 𝑝 𝑎 𝑝 𝑐 𝑎 𝑝 𝑏 𝑐 • である．これを𝑐で周辺化すると • 𝑝 𝑎, 𝑏 = ∑+ 𝑝 𝑎 𝑝 𝑐 𝑎 𝑝 𝑏 𝑐 = 𝑝 𝑎 ∑+ 𝑝 𝑏, 𝑐 𝑎 = 𝑝 𝑎 𝑝 𝑏 𝑎 • この式は𝑝 𝑎 と𝑝 𝑏 の積に分解できないので， 𝑎と𝑏は独⽴ではない． a c b
例4 • 同時分布が 𝑐 により条件付されている時，グラフが表す同時分布は • 𝑝 𝑎, 𝑏 𝑐 = , -,/,+ , + = , - , 𝑐𝑎 , + , 𝑏𝑐 = , 𝑎𝑐 , + , , + 𝑏𝑐 = 𝑝 𝑎 𝑐 𝑝 𝑏 𝑐 • と書ける．よって，𝑎と𝑏は独⽴である． • 例3と例4は，ノード𝑐がノード𝑎からノード𝑏への経路に対して，headto-tailであると⾔われる． • この例でも𝑐が条件付けることで，𝑎から𝑏への経路が遮断され，それ らを条件づき独⽴にする． a c b
例5 • 図のグラフの同時分布は • 𝑝 𝑎, 𝑏, 𝑐 = 𝑝 𝑎 𝑝 𝑏 𝑝 𝑐 𝑎, 𝑏 • である．これを𝑐で周辺化すると • 𝑝 𝑎, 𝑏 = ∑+ 𝑝 𝑎 𝑝 𝑏 𝑝 𝑐 𝑎, 𝑏 = 𝑝 𝑎 𝑝 𝑏 • この式は𝑝 𝑎 と𝑝 𝑏 の積に分解できるので， 𝑎と𝑏は独⽴である． a b c
例6 • 同時分布が 𝑐 により条件付されている時，グラフが表す同時分布は • 𝑝 𝑎, 𝑏 𝑐 = , -,/,+ , + = , - , / , , + 𝑐 𝑎, 𝑏 • と書ける．これは，𝑝 𝑎 𝑐 と 𝑝 𝑏 𝑐 の積に分解できないので，𝑎 と𝑏は条件付き独⽴ではない． • 例5と例6は，ノード𝑐がノード𝑎からノード𝑏への経路に対して，headto-teadであると⾔われる． • この例は，𝑐が観測されていないとき，𝑎から𝑏への経路が遮断され， a それらを独⽴にする． • 𝑐が観測されると，遮断が解かれ 𝑎と𝑏に依存関係をもたらす． c b
条件付き独⽴のまとめ • Tail-to-tailノードあるいはhead-to-tailノードは観測されていないとき には経路を遮断せず，観測されると遮断する． • Head-to-headノードは観測されていないとき経路を遮断し，そのノー ドか，あるいはその⼦孫のうち少なくとも1つが観測された時，経路の 遮断が解かれる． • 𝑥から𝑦への⽮印に従う経路があるとき， 𝑦は𝑥の⼦孫という． 図ではdはcの⼦孫である．この図が表す同時分布は 𝑝 𝑎, 𝑏, 𝑐, 𝑑 = 𝑝 𝑎 𝑝 𝑏 𝑝 𝑐 𝑎, 𝑏 𝑝 𝑑 𝑐 𝑐と𝑑を周辺化により消去すると 𝑝 𝑎, 𝑏 = 𝑝 𝑎 𝑝 𝑏 ∑!" 𝑝 𝑐, 𝑑 𝑎, 𝑏 = 𝑝 𝑎 𝑝 𝑏 で 𝑎と𝑏は独⽴である． ⼦孫𝑑が観測されると 𝑝 𝑎, 𝑏, 𝑐, 𝑑 𝑝 𝑎 𝑝 𝑏 𝑝 𝑐 𝑎, 𝑏 𝑝 𝑑 𝑐 𝑝 𝑎 𝑝 𝑏 𝑝 𝑐, 𝑑 𝑎, 𝑏 𝑝 𝑎, 𝑏, 𝑐 𝑑 = = = 𝑝 𝑑 𝑝 𝑑 𝑝 𝑑 # ! # " # 𝑑 𝑎, 𝑏 𝑐を周辺化により消去すると 𝑝 𝑎, 𝑏 𝑑 = で𝑎と𝑏は独⽴ではなくなる． # $ 𝑎 𝑏 𝑐 𝑑
⽣成モデル
⽣成モデル • 物体認識問題を考える． • この問題は，物体の像（画像）が各観測データ点に対応し，この観測 データから物体の種類を推論することが⽬的となる． • 観測される画像は，物体とその位置と向きによって変わると考えられ る． • つまり，物体(Object)，位置(Position)，向き(Orientation)が画像(𝑥)の 潜在変数と⾒なせる． • 𝑝 𝑥 ∣ 𝑜𝑏𝑗，𝑝，𝑜𝑟𝑖𝑒𝑛𝑡
⽣成モデル • 画像が与えられた時，全ての位置と向きについてそれらの変数を積分 消去すれば物体の種類に関する事後分布が求まる． • 画像𝑥が観測されたとして，物体が何であるかの確率は次のように位置と向 きについて積分消去すれば良い． • 𝑝 𝑜𝑏𝑗 ∣ 𝑥 = ∑! ∑"#$%&' 𝑝 𝑜𝑏𝑗, 𝑝, 𝑜𝑟𝑖𝑒𝑛𝑡 𝑥 • この画像認識の問題は図のようなグラフィカルモデルで表すことがで きる． Object Position Orientation Image
⽣成モデル • このグラフィカルモデルは，観測データが⽣成される因果過程を表し ている． • このため，このようなモデルは，しばしば⽣成モデルと呼ばれる． • 確率分布が分かっていれば，潜在変数を決めれば⼈⼯的なデータが⽣成で きる． • 潜在変数は必ずしも物理的解釈を持つ必要はなく，単に複雑な同時分布を 単純な要素から構成するためだけに導⼊しても良い． Object Position Orientation 確率分布 𝑝 𝑥 𝑜𝑏𝑗, 𝑝, 𝑜𝑟𝑖𝑒𝑛𝑡 を知っていれば， 𝑜𝑏𝑗, 𝑝, 𝑜𝑟𝑖𝑒𝑛𝑡を決めれば画像𝑥を作れる． Image 変分オートエンコーダなどの画像⽣成⼈⼯知能では， 𝑝 𝑥 𝑜𝑏𝑗, 𝑝, 𝑜𝑟𝑖𝑒𝑛𝑡 をニューラルネットワークで作り 画像を⽣成する．
有向分離
例 • 例1 f a • 上の図のようなグラフを考える．𝑐は観測値とする． • このとき，𝑎から𝑏への経路は遮断されていない． e b • 𝑓はtail-to-tail接続であり，かつ観測されていないので遮断しない． • 𝑒はhead-to-head接続であるが，⼦孫である𝑐が観測されているため 経路を遮断しない． c • 例2 • 下の図のようなグラフを考える．𝑓は観測値とする． f a • このとき，𝑎から𝑏への経路は遮断されている． • 𝑓はtail-to-tail接続であり，かつ観測されているので遮断する． • さらに，𝑒はhead-to-head接続であり，𝑒および⼦孫である𝑐が観測 されていないため経路を遮断する． e c b
有向分離 • 𝐴，𝐵，𝐶がそれぞれ重複しないノード集合とする．ただし，すべての集合 をあわせてもグラフ全体とならなくて良い． • 与えられた有向⾮循環グラフが条件付き独⽴性 うかを調べたい． を⽰唆するかど • 以下の条件のうち，いずれかを満たすノードを含む経路は遮断されている という． 1. 集合𝐶に含まれるノードであって，経路に含まれる⽮印がそこでheadto-tailあるいはtail-to-tailである． 2. 経路に含まれる⽮印がそのノードでhead-to-headであり，⾃⾝あるい はそのすべての⼦孫のいずれもが集合𝐶に含まれない． • すべての経路が遮断されていれば，𝐴は𝐶によって𝐵から有向分離されてい るといい，グラフの全変数上の同時分布は を満たす．
マルコフブランケット
マルコフブランケット • 𝐷個のノードを持つ有向グラフで表現される同時分布𝑝 𝑥! , … , 𝑥3 と， たのすべての変数𝑥456 で条件付された条件付き分布を考える． • すべての変数𝑥()$ で条件付されたということは，すべての変数𝑥()$ は決まっ ている（観測されている）． • 条件付き分布は次の形で書ける． • 𝑝 𝑥6 ∣ 𝑥 456 = , 7, ,…,7∫ , 7, ,…,7- :7. = ∏/ , 𝑥( pa( ∫ ∏/ , 𝑥( pa( :7. • 分⺟の積分は𝑥6 に依存しない任意の因⼦𝑝 𝑥( pa( は𝑥6 に関する積分 の外に出る． • 外に出た因⼦の積と分⼦とがキャンセルされ，分⼦も𝑥6 に依存する因 ⼦だけが残る．
マルコフブランケット • 𝑝 𝑥% ∣ 𝑥 &'% は，𝑥% ⾃⾝の条件付き分布𝑝 𝑥% pa% と，𝑥% を条件付け変数集合に含む（𝑥% を親に持つ）任意のノー ド𝑥( の条件付き分布𝑝 𝑥( pa) で構成される． • 𝑝 𝑥% pa% はノード𝑥% の親に依存する． 親 共同親 • 条件付き確率𝑝 𝑥( pa) は𝑥% の⼦とその共同親に依存す る． • 共同親とは，ノード𝑥0 のうちノード𝑥1 以外のものを指す． • 𝑥1 はtail-to-tailで𝑥1 は観測されていないから，⼦同⼠は条件 付き独⽴になっていない． • 親，⼦および共同親からなるノード集合をマルコフブラ ンケットという． • ノード𝑥1 のマルコフブランケットは，𝑥1 を残りのグラフから 孤⽴させるためのノードの最⼩集合と考えられる． 親 共同親 xi ⼦ ⼦
マルコフ確率場
マルコフ確率場 • マルコフ確率場（マルコフネットワーク）とは，無向グラフィカルモ デルである． C B A
条件付き独⽴性 • 無向グラフにおいて図のようなノード集合A, B, Cがあるとする． • Cが観測されているとする． • Aに含まれるノードとBに含まれるノードを結ぶすべての経路を考える． • もし，それらの経路の全てがCに含まれるノードを少なとも1回通過するな ら，それらは遮断され条件付き独⽴が成り⽴つ． • もし，それらの経路のうち，⼀つでもCに含まれるノードを通過しないので あれば，必ずしも条件付き独⽴性を満たさない． • AのノードとBのノードのペアのうちのいずれかが条件付き独⽴性を満たさない． C B A
マルコフブランケット • 隣接ノードにより条件付けられれば，残りの他のノードに対して条件 付き独⽴となる． • マルコフブランケットは隣接ノード集合からなる．
分解特性 • ⼀つのリンクによって直接接続されていない2つのノード𝑥6 と𝑥4 を考え る． • これらのノード以外が全て観測されているとすると，𝑥6 と𝑥4 は条件付 き独⽴である． • 𝑝 𝑥$ , 𝑥( 𝑥\{$,(} = 𝑝 𝑥$ 𝑥\{$,(} 𝑝 𝑥( 𝑥\{$,(} • ここで𝑥\{6,4} は 𝑥6 と𝑥4 以外のノードを指す．
クリーク • クリークとはグラフのノード集合であり，そのノード集合は全結合し ている． • クリークにノードを⾜してもクリークになる（全結合している）場合 がある．クリークに，さらにノードを⾜してもクリークにならないク リークを極⼤クリーク(maximal clique)と呼ぶ． • 極⼤クリークは，ノード数が最⼤である必要はない．例えば，ノード数3の 極⼤クリークとノード数4の極⼤クリークが共存する場合もある． • 図のグラフにおいては，2つのノードからなるクリーク ( 𝑥! , 𝑥" , 𝑥" , 𝑥# , 𝑥# , 𝑥$ , 𝑥$ , 𝑥" , 𝑥! , 𝑥# )と，2つの極⼤クリーク ( 𝑥! , 𝑥" , 𝑥# , 𝑥" , 𝑥# , 𝑥$ )がある． x1 x2 x3 x4
クリークと因数分解 • クリーク𝐶 ⊆ 𝑉（𝑉は全ノードの集合）とすると，全確率変数の同時分 布は次のように書ける． ! • 𝑝 𝑥 = ? ∏@ 𝜓@ 𝑥@ • ここで，𝑥@ はクリーク𝐶に含まれる確率変数集合で，𝜓@ はクリーク𝐶の ポテンシャル関数である． • 𝑍は規格化定数で，分配関数とも呼ばれる． • 𝑍は𝑍 = ∑7 ∏@ 𝜓@ 𝑥@ である． • ポテンシャル関数は確率的なものである必要はない．
ポテンシャル関数 • ポテンシャル関数を指数関数で表現すると便利なので，次の式で表す とする． • 𝜓@ 72 = exp −𝐸 𝑋@ • ここで𝐸 𝑋@ はエネルギー関数と呼ばれる．また，この指数関数表現 はボルツマン分布と呼ばれる． • 同時分布はポテンシャル関数の積で表されるので，全エネルギーは極 ⼤クリークのエネルギーの総和である． • この表現に興味がある⼈はカノニカル分布を勉強する必要があるだろ う．
マルコフ確率場の例
画像のノイズ除去 • マルコフ確率場の例として画像のノイズ除去を挙げる． • ノイズを含む観測画像の各ピクセルは𝑦6 ∈ −1, +1 の値をとる． • この画像はノイズを含まない画像（各ピクセルの値は 𝑥6 ∈ −1, +1 ） を各ピクセルに⼩さな確率で符号反転させて得られたものとする． • ⽬的はノイズあり画像から元画像を復元することにある． 元画像 10%ノイズを加えたもの
マルコフ確率場による表現 • ノイズレベルが⼗分に低いため，元画像のピクセル𝑥% とノイズ画像のピク セル𝑦% との間に強い相関があるとする． • 隣接ピクセル間にも強い相関があるとする． • これらは図のようなマルコフ確率場で表現することが出来る． • 完全な部分グラフ（クリーク）は2種類しか無い． • 𝑥1 , 𝑦1 𝑦% はノイズあり画像のピクセルで観測 されている． 𝑦% は元画像のピクセルx& から⽣じてい るから𝑦% と𝑥% は繋がっている． 𝑥% は隣接ピクセルと相関があるから， 隣接ピクセルは繋がっている． • ノイズ画像の画素と元画像の画素の接続 • このクリークのエネルギー関数は−𝜂𝑥! 𝑦" とする．ただし𝜂 > 0． yi • {𝑥1 , 𝑦3 } • 隣接するピクセル𝑖と𝑗の接続 • このクリークのエネルギー関数は−𝛽𝑥! 𝑥" とする．ただし，𝛽 > 0． xi
ポテンシャル関数 • ポテンシャル関数であるためには，極⼤クリーク上の任意の⾮負関数でさ えあれば良い． • クリークの部分集合上の任意の⾮負関数をかけることが出来る． • ポテンシャル関数は𝜓4 5. = exp −𝐸 𝑋4 だから，更にポテンシャル関数をか けるということは， 𝜓4 5. 𝜓4 / 5 / = exp −𝐸 𝑋4 exp −𝐸 6 𝑋4 / = . exp − 𝐸 𝑋4 + 𝐸 6 𝑋4 / となり，エネルギーを加えることと等価である． • 今回のノイズ除去の例では，エネルギーにノイズなし画像のピクセル値𝑥1 の関 数であるℎ𝑥1 を加える． • よって，このモデルの全エネルギー関数は • 𝐸 𝒙, 𝒚 = ℎ ∑1 𝑥1 − 𝛽 ∑ 1,3 𝑥1 𝑥3 − 𝜂 ∑1 𝑥1 𝑦1 • また，𝒙と𝒚の同時分布は 7 • 𝑝 𝒙, 𝒚 = exp −𝐸 𝒙, 𝒚 8
元画像の求め⽅ • 反復条件付きモード(ICM)と呼ばれる簡単な繰り返し法を⽤いる． • 始めに変数 𝑥$ を初期化する．例えば全ての𝑖について𝑥$ = 𝑦$ とする． • 次に，ノード𝑥( を1つづつ選んで，その他のノード変数の値を固定したまま 𝑥( の可能な2つの状態（𝑥( = 1および𝑥( = −1）における全エネルギーを計算 し，そのエネルギーがより低くなる𝑥( の⽅値に更新する． • この更新を繰り返し⾏い，ある適切な停⽌規準が満たされた時点で終了す る． ノイズ除去後の画像 • この計算をし，その変数値も更新されなくなったとき，エネルギー関 数は局所最⼤に収束している．
有向グラフから無向グラフへ の変換
有向グラフから無向グラフへの変換例 • 有向グラフで記述されるモデルを無向グラフに変換する問題を考える． • 図に⽰される有向グラフの場合は簡単に無向グラフに変換できる． • 有向グラフの同時分布は • 𝑝 𝑥 = 𝑝 𝑥. 𝑝 𝑥/ 𝑥. 𝑝 𝑥0 𝑥/ … 𝑝 𝑥1 𝑥12. • 図の無向グラフを考えてみる．このグラフの最⼤クリークは隣接ノード 対{𝑥JK! , 𝑥J }である．つまり，それぞれのノード対に対応したポテンシ ャル関数の積から同時分布が求まる． . • 𝑝 𝑥 = 3 𝜓.,/ 𝑥. , 𝑥/ 𝜓/,0 𝑥/ , 𝑥0 … 𝜓12.,1 (𝑥12. , 𝑥1 ) x1 xN x2 有向グラフ 1 xN x1 x2 xN 1 左の有向グラフと等価な無向グラフ xN
有向グラフから無向グラフへの変換例 • 有向グラフの同時分布 • 𝑝 𝑥 = 𝑝 𝑥. 𝑝 𝑥/ 𝑥. 𝑝 𝑥0 𝑥/ … 𝑝 𝑥1 𝑥12. • 無向グラフの同時分布 . • 𝑝 𝑥 = 3 𝜓.,/ 𝑥. , 𝑥/ 𝜓/,0 𝑥/ , 𝑥0 … 𝜓12.,1 (𝑥12. , 𝑥1 ) • この2つの同時分布から，次のようなポテンシャル関数と分布との対応 ができる． • 𝜓.,/ 𝑥. , 𝑥/ = 𝑝 𝑥. 𝑝 𝑥/ 𝑥. • 𝜓/,0 𝑥/ , 𝑥0 = 𝑝 𝑥0 𝑥/ • 𝜓12.,1 𝑥12. , 𝑥1 = 𝑝 𝑥1 𝑥12. • この場合𝑍 = 1である．
⼀般的な有向グラフを無向グラフへ変換 • 有向グラフの無向グラフへの変換は，有向グラフ上の因数分解によっ て規定される分布つまり有向グラフの条件付き確率を⽤い，無向グラ フのポテンシャル関数を表現することである． • 先の例のように，親ノードが1つしか無いグラフであれば，単純にエッ ジを無効化するだけで無向グラフに変換できる． • しかし，下図のように親ノードが複数ある場合はそう簡単ではない． x1 x3 x2 x4
⼀般的な有向グラフを無向グラフへ変換 • 左図の有向グラフの同時分布は • 𝑝 𝑥 = 𝑝(𝑥0 ) 𝑝(𝑥1 ) 𝑝(𝑥2 ) 𝑝(𝑥3 ∣ 𝑥0 , 𝑥1 , 𝑥2 ) • である．条件付き分布𝑝(𝑥9 ∣ 𝑥7, 𝑥:, 𝑥;)は4変数持っている．つまり， この条件付き分布 をクリークポテンシャルに吸収させるためには，クリークはノード𝑥7, 𝑥:, 𝑥;, 𝑥9を含む必 要がある． • 今回の例では，全てのノードをつなぐことで無向グラフにできる． • この無向グラフの同時分布は 0 • 𝑝 𝑥 = 4 𝜓5! ,5" ,5# ,5$ 𝑥0 , 𝑥1 , 𝑥2 , 𝑥3 = 𝑝(𝑥0 ) 𝑝(𝑥1 ) 𝑝(𝑥2 ) 𝑝(𝑥3 ∣ 𝑥0 , 𝑥1 , 𝑥2 ) • これにより有向グラフを無向グラフに変換できたが，この無向グラフは元々の有向グラ x1 x3 フと異なり何の条件付き独⽴性を表現しない． x1 x2 x2 有向グラフ x4 無向グラフ x4 x3
⼀般的な有向グラフを無向グラフへ変換のまとめ • グラフの各ノードに対して，その全ての親同⼠の対に無向エッジを追 加する． • 親同⼠をつなぐ過程をモラル化(moralization)という． • 元々の有向エッジを無向エッジにする． • この結果できあがったグラフをモラルグラフという． • モラルグラフの全てのクリークポテンシャル関数を1に初期化する． • 元々の有向グラフの条件付き分布因⼦を1つずつ取ってきて，それぞれ に対応するクリークポテンシャルの1つにかける． • モラル化されているため，各条件付き分布因⼦の変数全てを含む極⼤クリ ークが少なくとも1つ存在する． 有向グラフを無向グラフに完全に変換できない場合があることに注意する．無向グ ラフに変換する時，いくつかの条件付き独⽴性は捨てることになるかもしれない．
グラフィカルモデルにおける 推論
ベイズ定理とグラフ x x x y y y • 2変数𝑥, 𝑦の同時分布を次の形に因数分解する． • 𝑝 𝑥, 𝑦 = 𝑝 𝑥 𝑝 𝑦 𝑥 • これは図aのグラフで表現される． (a) (b) • いま，𝑦が観測されたとするとグラフは図bの様になる． • この場合，𝑥は潜在変数と⾒ることができ，周辺分布𝑝 𝑥 は事前分布と考えて良い ．つまり，⽬的は，この事前分布に対する𝑥の事後分布を推論することにある． • 事後分布はベイズ定理より，𝑝 𝑥 𝑦 = < 5 < 𝑦𝑥 < = • ただし𝑝 𝑦 = ∑# ! 𝑝 𝑥 $ , 𝑦 = ∑# ! 𝑝 𝑦 ∣ 𝑥 $ 𝑝 𝑥 $ • これらを⽤い同時分布を再び書くと， 𝑝 𝑥, 𝑦 = 𝑝 𝑦 𝑝 𝑥 𝑦 • これは図cで表現される．この推論はグラフの⽮印の向きを反転させていることに 対応する． (c)
連鎖における推論 • 図に⽰されるノードの連鎖を考える． • 図の無向グラフは，図の有向グラフと等価である． • 図の無向グラフの同時分布は ( ) • 𝑝 x = 𝜓(,* 𝑥( , 𝑥* 𝜓*,+ 𝑥* , 𝑥+ … 𝜓,-(,, 𝑥,-( , 𝑥, • と書ける． • ここで，𝐾個の状態を持つ𝑁個ノードからなる連鎖を考える． • この同時分布は 𝑁 − 1 𝐾 / 個のパラメタを持つ(ポテンシャル関数１つにつ き𝐾 / 個の変数)． x1 xN x2 有向グラフ 1 xN x1 x2 xN 1 左の有向グラフと等価な無向グラフ xN
推論 • 各ノード𝑥. の周辺分布𝑝 𝑥. を推論する． • 周辺分布𝑝 𝑥. は同時確率を𝑥. 以外の変数について周辺化したものだか ら • 𝑝 𝑥. = ∑/, … ∑/>?, ∑/>@, … ∑/A 𝑝(𝑥) • 単に周辺化すれば良いので計算⾃体は単純だが，全ての場合について 同時分布を計算して⾜し合わせることは場合の数を考えると膨⼤な計 算量が必要になると考えられる． • それぞれのノードが𝐾の状態を取りうるとすれば計算量は𝑂(𝐾 1 )となる．
ポテンシャル関数を⽤いた効率の良い推論 • ポテンシャル関数を⽤いた周辺分布は ! 3 • 𝑝 𝑥2 = ∑4% … ∑4&'% ∑4&(% … ∑4) 𝜓!,$ 𝑥! , 𝑥$ 𝜓$,5 𝑥$ , 𝑥5 … 𝜓6#!,6 𝑥6#! , 𝑥6 • まず，𝑥6 が関わる部分に注⽬する． 𝑝 𝑥 = 1 : … : : … : 𝜓0,1 𝑥0 , 𝑥1 𝜓1,2 𝑥1 , 𝑥2 … 𝜓670,6 𝑥670 , 𝑥6 Z 5! 5%&! 5%'! 5( • 𝑥6 が関わるものだけ後ろにまとめると 𝑝 𝑥8 = 1 : … : : … : 𝜓0,1 𝑥0 , 𝑥1 𝜓1,2 𝑥1 , 𝑥2 … 𝜓671,670 𝑥671 , 𝑥670 : 𝜓670,6 𝑥670 , 𝑥6 Z 5! 5%&! 5%'! 5(&! 5( • 𝑥6 の総和に着⽬すると，∑4) 𝜓6#!,6 𝑥6#! , 𝑥6 は𝑥6#! の関数になっている． これを𝜇7 (𝑥6#! )とする．
グラフィカルモデルによる周辺分布の推論 • 𝜇0 (𝑥,-( )を⽤いた周辺分布は 𝑝 𝑥8 = 1 : … : : … : 𝜓0,1 𝑥0 , 𝑥1 𝜓1,2 𝑥1 , 𝑥2 … 𝜓671,670 𝑥671 , 𝑥670 𝜇9 (𝑥670 ) Z 5! 5%&! 5%'! 5(&! • 𝑥,-( が関わる部分に注⽬し，𝑥,-( が関わるものだけ後ろにまとめると 𝑝 𝑥8 = 1 : … : : … : 𝜓0,1 𝑥0 , 𝑥1 𝜓1,2 𝑥1 , 𝑥2 … 𝜓671,670 𝑥671 , 𝑥670 𝜇9 (𝑥670 ) Z 5! = 5%&! 5%'! 5(&! 1 : … : : … : 𝜓0,1 𝑥0 , 𝑥1 𝜓1,2 𝑥1 , 𝑥2 … 𝜓672,671 𝑥672 , 𝑥671 : 𝜓671,6 𝑥671 , 𝑥670 𝜇9 (𝑥670 ) Z 5! 5%&! 5%'! 5(&" 5(&! • 同様に𝑥,-( の総和に着⽬すると ∑/A?, 𝜓,-*,,-( 𝑥,-* , 𝑥,-( 𝜇0 (𝑥,-( )も 𝑥,-( の関数となっている．これも𝜇0 (𝑥,-* )とする．
グラフィカルモデルによる周辺分布の推論 • 前後から同様の計算を⾏うと周辺分布は最終的に次の形で書ける． ( 1 • 𝑝 𝑥. = 𝜇2 𝑥. 𝜇0 𝑥. • 𝜇2 𝑥. = ∑/>?, 𝜓.-(,. 𝑥.-( , 𝑥. 𝜇2 (𝑥.-( ) • 𝜇0 𝑥. = ∑/>@, 𝜓.,.3( 𝑥. , 𝑥.3( 𝜇0 (𝑥.3( )
計算量はどうなっているか？ • 𝜇9 𝑥670,: = ∑5( 𝜓670,6 𝑥670,: , 𝑥6 に着⽬する． 𝜇9 𝑥670 𝑘 は𝐾個の値を取るので，まとめて𝐾次 元ベクトルとして書くと • 𝝁9,670 = 𝜇9,670 𝑥670,0 , 𝜇9,670 𝑥670,1 , … , 𝜇9,670 𝑥670,; < • また，それぞれの要素は • 𝜇9,670 𝑥670,: = 𝜓670,6 𝑥670,: , 𝑥6,0 , … , 𝜓670,6 𝑥670,: , 𝑥670,; 1, . . , 1 < 総和を⾏列の式で書いているだけ • つまり 𝝁EB,CD7= 𝜓CD7,C 𝑥CD7 1 , 𝑥C 1 ⋮ 𝜓CD7,C 𝑥CD7 𝐾 , 𝑥C 1 … 𝜓CD7,C 𝑥CD7 1 , 𝑥C 𝐾 ⋱ ⋮ … 𝜓CD7,C 𝑥CD7 𝐾 , 𝑥C 𝐾 1 ⋮ 1 • これを⾒ると，𝝁9,670 を求めるためには𝐾 1 回 𝜓670,6 𝑥670 (𝑘), 𝑥6 𝑘 を計算しなければならない． • 同時分布の式に∑は𝑁 − 1個あるので，同時分布の計算に必要な計算量は𝑂(𝑁𝐾 1 )である． • ポテンシャル関数を使うことで同時分布を効率よく計算できる． • 𝑁に対し指数的に増加していた計算コスト𝑂 𝐾 " が線形増加 𝑂(𝑁𝐾 # ) に削減できた．
メッセージパッシング • 𝜇2 𝑥. = ∑/>?, 𝜓.-(,. 𝑥.-( , 𝑥. 𝜇2 (𝑥.-( )に着⽬する． • 𝜇2 𝑥. はノード𝑥.-( で計算されノード𝑥. に送られる．このことから， 𝑥.-( から𝑥. メッセージと⾒なすことができる． • 𝜇2 𝑥. は𝜇2 (𝑥.-( )を⽤い計算され，𝜇2 (𝑥.-( )は𝜇2 (𝑥.-* )から計算され るというように，メッセージは再帰的に計算される． • メッセージの流れに着⽬すると，メッセージはグラフの端からノード 𝑥. まで伝播していると考えることができる．このメッセージの伝播の ことをメッセージパッシングパッシングという． µ↵ (xn x1 1) xn µ (xn ) µ↵ (xn ) 1 xn µ (xn+1 ) xn+1 xN
全てのノードの周辺分布を求める ( • 全てのノードの周辺分布を求めるには，𝑝 𝑥. = 1 𝜇2 𝑥. 𝜇0 𝑥. を𝑁ノ ード分計算すれば良い． • 単純に考えれば計算量は，１ノードあたり 𝑂(𝑁𝐾 * ) なので𝑁ノードで は 𝑂(𝑁 * 𝐾 * )となる． µ↵ (xn x1 1) xn µ (xn ) µ↵ (xn ) 1 xn µ (xn+1 ) xn+1 xN 周辺分布を求めるには，このメッセージパッシングをノード𝑥0 から 𝑥6 について⾏えば良い．
全てのノードの周辺分布を求める • ここで，メッセージは 𝑝 𝑥. に依存しないことを利⽤する． • 各メッセージは 𝑝 𝑥. を計算しても変わらない． • つまり，メッセージ𝜇2 𝑥. と 𝜇0 𝑥. は１度だけ計算すれば良い． • 𝑛 = 1から𝑛 = 𝑁までの伝播されるメッセージ𝜇9 𝑥& と𝑛 = 𝑁から𝑛 = 1まで の伝播されるメッセージ𝜇: 𝑥& を１度だけ計算する． = 𝑥 µ↵𝜇(x n870 1) x1 xn 9 𝑥 µ↵𝜇(x n871 1) x1 xn 𝜇=↵ (x 𝑥8n ) µ 1 𝜇µ= (x 𝑥8>0 n) xn 𝜇µ9↵𝑥(x 870 n) 1 xn+1 µ𝜇9(x𝑥n8) xn 𝜇µ= (x 𝑥8>1 n+1 ) xN 𝜇µ9 (x 𝑥8>0 n+1 ) xn+1 xN
全てのノードの周辺分布を求める ( • よって，𝑝 𝑥. = 1 𝜇2 𝑥. 𝜇0 𝑥. を𝑁ノード分計算するのに必要な算量 は𝑂 𝑁𝐾 * となる． • 分配関数𝑍は都合の良いノードで１回計算するだけで良い． • いくつかのノードが観測されている場合は，それらの変数は観測値に 固定化すれば良い． • 図のような形をしたグラフはマルコフ連鎖と呼ばれる． • この場合のメッセージパッシングの等式はマルコフ過程におけるチャップ マン-コルモゴロフの等式の例である． µ (xn ) µ (xn+1 ) µ↵ (xn 1 ) µ↵ (xn ) x1 xn 1 xn xn+1 xN
隣接する２つのノードの同時分布 • 隣接する２つのノードの同時分布𝑝 𝑥.-( , 𝑥. は𝑥.-( と𝑥. 以外のノード について周辺化すれば良いので， • ポテンシャル関数を⽤いた周辺分布は 𝑝 𝑥$%& , 𝑥$ 1 = J … J J … J 𝜓&,# 𝑥& , 𝑥# 𝜓#,) 𝑥# , 𝑥) … 𝜓$%#,$%& 𝑥$%# , 𝑥$%& 𝜓$%&,$ 𝑥$%& , 𝑥* 𝜓$,$+& 𝑥$ , 𝑥$+& … 𝜓"%&," 𝑥"%& , 𝑥" Z '' '()* '(+' ', • これをメッセージを⽤いて書くと ( • 𝑝 𝑥.-( , 𝑥. = 1 𝜇2 𝑥.-( 𝜓.-(,. 𝑥.-( , 𝑥4 𝜇0 𝑥. • 𝜇2 𝑥.-( = ∑/>?F 𝜓.-*,.-( 𝑥.-* , 𝑥.-( 𝜇2 (𝑥.-* ) • 𝜇0 𝑥. = ∑/>@, 𝜓.,.3( 𝑥. , 𝑥.3( 𝜇0 (𝑥.3( )
因⼦グラフ
因⼦グラフ • 次のような因数分解で表現される分布を考える． • 𝑝 𝑥 = 𝑓5 𝑥( , 𝑥* 𝑓6 𝑥( , 𝑥* 𝑓7 𝑥* , 𝑥+ 𝑓8 𝑥+ • この分布は図のような因⼦グラフで表される． • 円で書かれるノード：変数 • ⼩さい正⽅形で書かれるノード：因⼦ x1 fa x2 fb x3 fc fd
無向グラフと因⼦グラフ • 無向グラフを因⼦グラフに変換するのは容易である． • 無向グラフでは極⼤クリークに対しポテンシャル関数が1つ割り当てられ た． • つまり，無向グラフを因⼦グラフに変換するときは，左図のように極⼤ク リークをそれに対応するポテンシャル関数を因⼦ノードにすれば良い． • ただし，右図のように極⼤クリークを複数の因⼦で表現出来ることには注 意する必要がある． ポテンシャル関数𝜓 𝑥 , 𝑥 , 𝑥 = 𝑓 ポテンシャル関数𝜓 𝑥 , 𝑥 , 𝑥 = 𝑓 𝑓 ) x1 x2 x1 x2 * + ) x1 x2 x1 * + x2 fa f fb x3 無向グラフ x3 因⼦グラフ x3 無向グラフ x3 因⼦グラフ , -
有向グラフを因⼦グラフに変換する • 有向グラフを因⼦グラフに変換する． • 左図の有向グラフの同時分布は次のとおりである． • 𝑝 𝑥. , 𝑥/ , 𝑥0 = 𝑝 𝑥0 𝑥. , 𝑥/ 𝑝 𝑥. 𝑝 𝑥/ • 因⼦を𝑓 = 𝑝 𝑥( , 𝑥* , 𝑥+ とすると，因⼦グラフは中央図となる． • 更に因⼦を 𝑓5 𝑥( = 𝑝 𝑥( ， 𝑓6 𝑥* = 𝑝 𝑥* ， 𝑓7 𝑥( , 𝑥* , 𝑥+ = 𝑝 𝑥+ 𝑥( , 𝑥* とした場合の因⼦グラフは右図のようになる． x1 x2 x1 x1 x2 x2 𝑝 𝑥! 𝑥", 𝑥# fc f 𝑝 𝑥0 , 𝑥1 , 𝑥2 x3 x3 fa fb 𝑝 𝑥- 𝑝 𝑥. x3
因⼦グラフ表現は1つに定まらないので好みで作る • 無向・有向グラフから因⼦グラフへの変換は1つではない． • モデルの設計者は必要に応じ因⼦を増減させることが可能である． x1 x2 x2 fa f x1 x1 x2 fb x3 x3 因⼦グラフへ変換 x3 すべての因⼦グラフが元の無向グラフを表す．
積和アルゴリズム
⽬的 • 積和 (sum-product) アルゴリズムはグラフの構造を利⽤し2つのこと を実現する． • 周辺分布を求めるための効率の⽤意厳密推論アルゴリズムを得る． • 複数の周辺分布を計算したい場合，計算の重複をなくして効率化する． • 積和アルゴリズムは⽊構造グラフにおける効率の良い厳密な推論の枠 組みを与える．
⽊ • 無向グラフにおける⽊（無向⽊） • 任意のノードの組の間に唯⼀の経路が存在するグラフ • 有向グラフにおける⽊（有向⽊） • ルートノードを1つだけ持ち，他のすべてのノードはそれぞれ親をひつずつ 持つグラフ • 多重⽊(polytree) • 2つ以上の親を持つノードが存在するが，任意の2ノード間の経路が⼀つし かない有向グラフ 無向⽊ 有向⽊ 多重⽊
⽊構造の維持 • 積和アルゴリズムは⽊構造における厳密な推論をするための⼿法であ る．つまり，⽊構造である必要がある． • 左図の有向グラフを無向グラフに変換すると，モラル化により親ノー ド同⼠にリンクが発⽣する（中央図）．これにより，グラフはループ を持つ． • 左図を右図の因⼦グラフに変換する場合は，⽊構造を維持することが 出来る． 有向グラフ 左の有向グラフを無向グ ラフに変換したもの 有向グラフを因⼦グラフに 変換したもの
周辺分布と積和アルゴリズム • 𝑥の周辺分布は𝑥を除く全ての変数に対し同時分布の和を取ることで得られ る．つまり • 𝑝 𝑥 = ∑E\4 𝑝(x) • である．ここで，x\𝑥は変数集合xから𝑥を取り除いたものである． • 積和アルゴリズムの基本的な考え⽅は，因⼦グラフ表現 • 𝑝 x = ∏G 𝑓G xG 同時分布は因⼦の総積 • を𝑝(x)に代⼊して得られた式 • 𝑝 𝑥 = ∑E\4 ∏G 𝑓G xG 同時分布を𝑥以外の変数で周辺化すれば𝑥の周辺分布が求まる． • の和演算と積演算を交換して効率的なアルゴリズムを得ることである．
積和アルゴリズム • まず図に⽰すようなグラフの⼀部について考える． • グラフは⽊構造だから，同時分布の因⼦を変数ノード𝑥に隣接する各因 ⼦ノードごとにグループ分けることが出来る． • 𝑝 x = ∏9∈4;(/) 𝐹9 𝑥, 𝑋9 Fs (x, Xs ) • 図のグラフの同時分布は次のように書ける． µfs !x (x) fs x • xは変数集合 • ne 𝑥 は変数ノード𝑥に隣接する因⼦ノード集合 • 𝑋; は因⼦ノード𝑓; を通し変数ノード𝑥に接続される部分⽊に属する変数集合 • 𝐹; 𝑥, 𝑋; は因⼦𝑓; に関連するグループのすべての因⼦の積
よく分からないので具体的に考える x1 右の無向グラフの場合 1 𝑝 x = 𝜓 𝑥0 , 𝑥1 , 𝑥2 = 𝑓(𝑥0 , 𝑥1 , 𝑥2 ) 𝑍 x1 x2 x2 f 𝜓 𝑥0 , 𝑥1 , 𝑥2 x3 x3 𝑥- 右の無向グラフの場合 1 𝑝 x = 𝜓0 𝑥0 , 𝑥1 , 𝑥2 𝜓# 𝑥) , 𝑥. , 𝑥/ 𝑍 𝑥. 𝑥- 𝑥. 𝜓- 𝑥- , 𝑥. , 𝑥/ 𝑥0 = 𝑓& 𝑥& , 𝑥# , 𝑥) 𝑓# 𝑥) , 𝑥. , 𝑥/ = 𝐹& 𝑥) , 𝑋& 𝐹# 𝑥) , 𝑋# 𝑓- 𝑥/ 𝐹1 𝑥2 , 𝑋1 𝑓. 𝑥1 𝑥) 𝐹0 𝑥2 , 𝑋0 右の因⼦グラフの場合 𝑝 x = 𝑓& 𝑥& , 𝑥# , 𝑥) , 𝑥. , 𝑥/ 𝑓# 𝑥) , 𝑥0 , 𝑥1 𝑓) 𝑥0 , 𝑥2 𝑥/ 𝑥0 𝜓. 𝑥/ , 𝑥0 , 𝑥1 𝑥1 = 𝐹& 𝑥& , 𝑥# , 𝑥) , 𝑥. , 𝑥/ 𝐹# 𝑥) , 𝑥0 , 𝑥1 , 𝑥2 = 𝐹& 𝑥) , 𝑋& 𝐹# 𝑥) , 𝑋# 𝐹0 𝑥2 , 𝑋0 𝑥* 𝑓) 𝑥1 𝑥2 𝑥+ 𝑥3 𝑓* 𝑓+ 𝑥4 𝐹1 𝑥2 , 𝑋1 𝑥5
積和アルゴリズム • 𝑥の周辺分布は𝑝 𝑥 = ∑>\/ 𝑝(x)だから 𝑝 𝑥 = / 0 𝐹S 𝑥, 𝑋S Q\5 S∈UV(5) = 0 / 𝐹S 𝑥, 𝑋S Fs (x, Xs ) • 同時分布は𝑝 x = ∏9∈4;(/) 𝐹9 𝑥, 𝑋9 である． µfs !x (x) fs x 積と和が⼊れ替わる． 式の詳細は次のスライドに． S∈UV(5) YA = 0 𝜇ZA→5 𝑥 S∈UV(5) • 𝜇@P →/ 𝑥 ≡ ∑BP 𝐹9 𝑥, 𝑋9 と定義した． • これは因⼦ノード𝑓9 から𝑥へのメッセージと解 釈できる． xは変数集合 ne 𝑥 は変数ノードxに隣接する因⼦ノード集合 𝑋2 は因⼦ノード𝑓2 を通し変数ノード𝑥に接続される部 分⽊に属する変数集合 𝐹2 𝑥, 𝑋2 は因⼦𝑓2 に関連するグループのすべての因⼦ の積
よく分からないので具体的に考える 右図のグラフの同時分布は 𝑝 x = 𝑓& 𝑥& , 𝑥# , 𝑥) , 𝑥. , 𝑥/ 𝑓# 𝑥) , 𝑥0 , 𝑥1 = 𝐹& 𝑥& , 𝑥# , 𝑥) , 𝑥. , 𝑥/ 𝐹# 𝑥) , 𝑥0 , 𝑥1 𝐹0 𝑥1 , 𝑋0 = 𝐹& 𝑥) , 𝑋& 𝐹# 𝑥) , 𝑋# = ] 𝐹3 𝑥) , 𝑋3 𝑥* 34&,# 𝑥) の周辺分布は 𝑝 𝑥) = 𝑥) 𝑓) 𝑥1 J ] 𝐹3 𝑥) , 𝑋3 = J '' ,'* ,'3 ,'4 ,'5 ,'6 34&,# 5' ,5* = J 𝐹& 𝑥) , 𝑋& J 𝐹# 𝑥) , 𝑋# 5' 5* ] 𝐹3 𝑥) , 𝑋3 = J J 𝐹& 𝑥) , 𝑋& 𝐹# 𝑥) , 𝑋# 34&,# = J 𝐹& 𝑥) , 𝑋& 5' 5' J 𝐹# 𝑥) , 𝑋# 5* 𝑥2 𝑥+ 𝑓* 5* 34&,# 57 𝐹1 𝑥2 , 𝑋1 34&,# ⼀般的な式 𝑝 𝑥 = J ] 𝐹3 𝑥, 𝑋3 = J J … J 𝐹& 𝑥, 𝑋& 𝐹# 𝑥, 𝑋# … 𝐹= 𝑥, 𝑋= 5' 5* 58 = J J … J 𝐹& 𝑥, 𝑋& 𝐹# 𝑥, 𝑋# … 𝐹=%& 𝑥, 𝑋=%& J 𝐹= 𝑥, 𝑋= 5' 5* 58)' 58 = J J … J 𝐹& 𝑥, 𝑋& 𝐹# 𝑥, 𝑋# … 𝐹=%& 𝑥, 𝑋=%& 5' 5* = J 𝐹& 𝑥, 𝑋& 5' 𝑋:以外は𝑋:の集合に⼊っていないので 𝐹: 𝑥, 𝑋: 以外は ∑9! の外にだす． ∑9! 𝐹: 𝑥, 𝑋: は𝑥のみの関数なのでSumの外に出せる J 𝐹= 𝑥, 𝑋= 58)' 58 J 𝐹# 𝑥, 𝑋# 5* … J 𝐹=%& 𝑥, 𝑋=%& 58)' 𝑥4 = ] J 𝐹3 𝑥) , 𝑋3 = ] 𝜇3→' ) (𝑥) ) 7\' 3∈*:(') 𝑥3 J 𝐹= 𝑥, 𝑋= 58 = ] J 𝐹3 𝑥, 𝑋3 3∈*:(') 57
積和アルゴリズム Fs (x, Xs ) • 各因⼦𝐹G 𝑥, 𝑋G も因⼦（部分）グラフで記述されるので，因数分解可能で ある．よって • 𝐹G 𝑥, 𝑋G = 𝑓G 𝑥, 𝑥! , … , 𝑥M 𝐺! 𝑥! , 𝑋G! … 𝐺M 𝑥M , 𝑋GM = 𝑓G 𝑥, 𝑥! , … , 𝑥M ∏N∈PQ R/ \4 𝐺N 𝑥N , 𝑋GN xM • この集合は𝑝 x = ∏G 𝑓G xG のxG である． • 灰⾊雲は⽔⾊雲𝑀個で構成される． x 𝐹F 𝑥, 𝑋F µxM !fs (xM ) • 𝑥! , … , 𝑥M は因⼦ノード𝑓G が依存する変数集合である． • 図では灰⾊雲が𝐹G 𝑥, 𝑋G を表す． µfs !x (x) fs fs µfs !x (x) xm Gm (xm , Xsm ) • それぞれの⽔⾊雲からメッセージが送られる． • 𝑚 ∈ ne 𝑓G \𝑥は因⼦ノード 𝑓G とつながる𝑥を除く変数ノード集合である． x
積和アルゴリズム
• よってメッセージ𝜇G6 →5 𝑥 は
𝐹F 𝑥, 𝑋F
𝜇A7 →' 𝑥 ≡ J 𝐹3 𝑥, 𝑋3
57
= J
J
𝑓3 𝑥, 𝑥& , … , 𝑥C
'' ,…,'; 57' ,…,57;
= J
𝑓3 𝑥, 𝑥& , … , 𝑥C
'' ,…,';
= J
𝑓3 𝑥, 𝑥& , … , 𝑥C
D∈*: A7 \'
J
]
J 𝐺& 𝑥& , 𝑋3&
𝑓3 𝑥, 𝑥& , … , 𝑥C
]
xM
µxM !fs (xM )
fs
𝐺D 𝑥D , 𝑋3D
… J 𝐺C 𝑥C , 𝑋3C
57'
'' ,…,';
= J
𝐺D 𝑥D , 𝑋3D
57' ,…,57; D∈*: A7 \'
'' ,…,';
= J
]
𝑋2=に𝑥=は含ま
れないため
∑9"# ,…,9"$ を
移動できる．
57;
J 𝐺D 𝑥D , 𝑋3D
𝑋2=に含まれる
ノードにがぶり
がないため，総
和の積になる．
µfs !x (x)
xm
Gm (xm , Xsm )
D∈*: A7 \' 57<
𝑓3 𝑥, 𝑥& , … , 𝑥C
'' ,…,';
]
𝜇'< →A7 𝑥D
D∈*: A7 \'
• ここで，変数ノードから因⼦ノードへのメッセージ
• 𝜇57 →G6 𝑥I ≡ ∑J67 𝐺I 𝑥I , 𝑋FI
• を定義した．
𝑋S = 𝑥7, … , 𝑥a , 𝑋S7, … , 𝑋Sa
𝑋F には𝑓F に直接つながる変数ノード𝑥I と，𝑥I か
らleaf側にあるの変数ノード 𝑋FI が含まれる．
x
よく分からないので具体的に計算してみる 図のグラフの同時分布は 𝑝 x = 𝑓& 𝑥& , 𝑥# , 𝑥) , 𝑥. , 𝑥/ 𝑓# 𝑥) , 𝑥0 , 𝑥1 𝑓) 𝑥0 , 𝑥2 , 𝑥E 𝑓. 𝑥1 , 𝑥&F , 𝑥&& 𝑓/ 𝑥E , 𝑥&# , 𝑥&) = 𝐹& 𝑥& , 𝑥# , 𝑥) , 𝑥. , 𝑥/ 𝐹# 𝑥) , 𝑥0 , 𝑥1 , 𝑥2 , 𝑥E , 𝑥&F , 𝑥&& , 𝑥&# , 𝑥&) = 𝐹& 𝑥) , 𝑋& 𝐹# 𝑥) , 𝑋# = ] 𝐹3 𝑥) , 𝑋3 34&,# 因⼦𝐹# は 𝐹# 𝑥) , 𝑋# = 𝑓# 𝑥) , 𝑥0 , 𝑥1 𝑓) 𝑥0 , 𝑥2 , 𝑥E 𝑓. 𝑥1 , 𝑥&F , 𝑥&& 𝑓/ 𝑥E , 𝑥&# , 𝑥&) = 𝑓# 𝑥) , 𝑥0 , 𝑥1 𝐺#,& 𝑥0 , 𝑥2 , 𝑥E , 𝑥&# , 𝑥&) 𝐺#,# 𝑥1 , 𝑥&F , 𝑥&& = 𝑓# 𝑥) , 𝑥0 , 𝑥1 𝐺#,& 𝑥0 , 𝑋#,& 𝐺#,# 𝑥1 , 𝑋#,# 因⼦ノード𝑓# から𝑥) へのメッセージは 𝜇A* →'@ 𝑥) ≡ J 𝐹# 𝑥) , 𝑋# 𝐹0 𝑥2 , 𝑋0 5* = J J J J J J J J 𝑓# 𝑥) , 𝑥0 , 𝑥1 𝑓) 𝑥0 , 𝑥2 , 𝑥E 𝑓. 𝑥1 , 𝑥&F , 𝑥&& 𝑓/ 𝑥E , 𝑥&# , 𝑥&) 𝑥* '5 '6 'A 'B ''C ''' ''* ''@ = J J J J J J J J 𝑓# 𝑥) , 𝑥0 , 𝑥1 𝐺#,& 𝑥0 , 𝑥2 , 𝑥E , 𝑥&# , 𝑥&) 𝐺#,# 𝑥1 , 𝑥&F , 𝑥&& 𝑥1 '5 '6 'A 'B ''C ''' ''* ''@ = J J 𝑓# 𝑥) , 𝑥0 , 𝑥1 J J J J J J 𝐺#,& 𝑥0 , 𝑥2 , 𝑥E , 𝑥&# , 𝑥&) 𝐺#,# 𝑥1 , 𝑥&F , 𝑥&& '5 '6 'A 'B ''C ''' ''* ''@ = J J 𝑓# 𝑥) , 𝑥0 , 𝑥1 J J J J 𝐺#,& 𝑥0 , 𝑥2 , 𝑥E , 𝑥&# , 𝑥&) '5 '6 = J J 𝑓# 𝑥) , 𝑥0 , 𝑥1 '5 '6 'A 'B ''C ''' J J 𝐺#,# 𝑥1 , 𝑥&F , 𝑥&& ''* ''@ J 𝐺#,& 𝑥0 , 𝑋#,& J 𝐺#,# 𝑥1 , 𝑋#,# 5*,' 5*,* 𝑥5 𝑥) 𝑥2 𝑓) 𝑓+ 𝑥+ 𝑓* 𝐺1,1 𝑥L , 𝑋1,1 𝐺1,0 𝑥K , 𝑋1,0 𝑥9 𝑥3 𝑥4 𝑓1 𝑓2 𝑥)* 𝑥)+ 𝑥)8 𝑥)) 𝐹1 𝑥2 , 𝑋1
周辺分布とメッセージ • 周辺分布 𝑝 𝑥 = ∏9∈4;(/) 𝜇@P →/ 𝑥 • これは，変数ノード𝑥に⼊ってくるメッセージの積で周辺分布が求まる ことを意味する． • メッセージは • 𝜇@P →/ 𝑥 = ∑/,,…,/b 𝑓9 𝑥, 𝑥( , … , 𝑥D ∏E∈4; @P \/ 𝜇/c →@P 𝑥E • である．つまり因⼦ノード𝑓9 が𝑥に送るメッセージは，因⼦ノードが接続 する𝑥以外の変数ノードに⼊ってくるメッセージと因⼦の積をかけて， それをすべての関係する変数について周辺すれば良い．
もう⼀度メッセージ • 変数ノード𝑥d から因⼦ノード𝑓S に伝わるメッセージを考える． • もちろん，ノード𝑥d も多数の因⼦ノード𝑓e が繋がっていることが想定される． • つまりノード𝑥d に関係する項𝐺d 𝑥d , 𝑋Sd は各因⼦ノード𝑓e に対応する項 𝐹e 𝑥d , 𝑋ed の積で与えられる．よって， • 𝐺d 𝑥d , 𝑋Sd = ∏e∈UV fL 5M \ZA 𝐹e 𝑥d , 𝑋ed 𝐹F 𝑥, 𝑋F 𝐺I 𝑥I , 𝑋FI xM µxM !fs (xM ) fs xm fl 𝐹N m𝑥,IX, 𝑋 NI Fl (x ) ml fs µfs !x (x) ⾚線の囲みの部分に注⽬ xm Gm (xm , Xsm ) x
もう⼀度メッセージ • 先の計算と同様にメッセージを求めると， fL 𝐺I 𝑥I , 𝑋FI 𝜇57 →G6 𝑥I ≡ : 𝐺I 𝑥I , 𝑋FI J67 = :…:… : J!7 J:7 J!7 U xm 𝐹N 𝑥I , 𝑋NI J;7 N∈PQ 57 \G6 = : 𝐹0 𝑥I , 𝑋0I = U … : 𝐹N 𝑥I , 𝑋NI … : 𝐹S 𝑥I , 𝑋SI J:7 : 𝐹N 𝑥I , 𝑋NI N∈PQ 57 \G6 J:7 J;7 = U fl 𝐹N m𝑥,IX, 𝑋 NI Fl (x ) ml 𝜇G: →57 𝑥I N∈PQ 57 \G6 • つまり，ある変数ノードから，それに隣接するある因⼦ノードをリン クを通じ伝わるメッセージを計算するには，そのリンク以外から来る メッセージの積を計算すれば良い．
⽬的を思い出す • 積和アルゴリズムの⽬的は変数ノード𝑥に関する周辺分布を計算することにある． • 周辺分布はすべてのリンクを伝わってノード𝑥に到達するメッセージの積で与えら れる． • メッセージはノード𝑥をrootとする⽊のleafノードから順番に計算すれば良い． • Leafノードが変数ノードであるならば，このノードが送るメッセージは µx!f (x) = 1 • 𝜇5→Z 𝑥 = 1 • となる． x f • また，leafノードが因⼦ノードであるならば，このノードが送るメッセージは • 𝜇Z→5 𝑥 = 𝑓(𝑥) • となる． µf !x (x) = f (x) f x
積和アルゴリズムのまとめ • 変数ノード𝑥を因⼦グラフのrootノードと⾒なし，𝜇4→R 𝑥 = 1， 𝜇R→4 𝑥 = 𝑓(𝑥)を⽤いleafノードを初期化する． • 次の式を再帰的に適⽤する．メッセージがすべてのリンクを伝播し，root ノードがすべての隣接ノードからのメッセージを受け取るまで計算が続け られる． • 𝜇5M →ZA 𝑥d = ∏e∈UV 5M \ZA 𝜇ZT →5M 𝑥d • 𝜇ZA →5 𝑥 = ∑5U ,…,5V 𝑓S 𝑥, 𝑥7 , … , 𝑥a ∏d∈UV ZA \5 𝜇5M →ZA 𝑥d • 各ノードは，rootノードへ向かう唯⼀の経路上のリンクを除く全ての隣接 ノードからメッセージを受け取った後，メッセージをrootノードに送る． • Rootノードがすべての隣接ノードからメッセージを受け取れば，求める周 辺分布は次の式から計算される． • 𝑝 𝑥 = ∏S∈UV(5) 𝜇ZA →5 𝑥
すべての変数ノードの周辺分布を求めるには • 任意の(変数もしくは因⼦)ノードを選んで，それをrootノードとする． • すべてのleafノードからrootノードに向けてメッセージを伝播させる． • この時点で，すべてのメッセージを受け取るため，rootノードはすべての隣 接ノードにメッセージを送ることができる． • Rootノードからメッセージをleafノードへメッセージを伝達する． • 以上でメッセージは双⽅向に伝達され，すべてのメッセージは計算さ れたので，グラフ上の変数ノードに対する周辺分布がすべて計算でき る．
具体的なグラフで確かめる 𝜇>'→<@ 𝑥+ = 2 𝑓) 𝑥) , 𝑥* , 𝑥1 , 𝑥2 <',<*,<3,<4 = 2 3 𝑥5 𝑥) 図のグラフでは，メッセージは18リンク*2=32個ある．これらのリンクで伝 達されるメッセージを計算する．まず，𝑥+ をrootノードとする． 𝜇<'→>' 𝑥) = 𝜇<*→>' 𝑥* = 𝜇<3→>' 𝑥1 = 𝜇<4→>' 𝑥2 = 𝜇<A→>@ 𝑥5 = 𝜇<'C→>3 𝑥)8 = 𝜇<''→>3 𝑥)) = 𝜇<'*→>6 𝑥)* = 𝜇<'@→>6 𝑥)+ = 1 𝑓+ 𝑥* 𝑓) 𝑥1 𝜇<<→>' 𝑥? 𝑓* 𝑥2 ?∈AB >' \<* 𝑓1 <',<*,<3,<4 <A 3 𝜇<<→>@ 𝑥? <A 3 <'C,<'' ?∈AB >3 \<6 𝜇<<→>3 𝑥? 𝑥)8 𝑥)) 𝜇>4→<5 𝑥3 = 2 𝑓2 𝑥3 , 𝑥9 <B 3 𝜇<<→>4 𝑥? ?∈AB >4 \<5 <B <'C,<'' 𝜇>6→<B (𝑥9 ) = 2 𝑓4 𝑥9 , 𝑥)* , 𝑥)+ 3 <'*,<'@ ?∈AB >6 \<B 𝜇>@→<5 = 2 𝑓+ 𝑥, 𝑥5 3 <A ?∈AB >@ \<5 𝜇<<→>6 𝑥? = 2 𝑓4 𝑥9 , 𝑥)* , 𝑥)+ 𝜇<5→>* (𝑥3 ) = 3 𝜇<<→>@ 𝑥? = 2 𝑓+ 𝑥, 𝑥5 <A 𝜇>D→<5 𝑥3 = 𝜇>@→<5 𝑥3 𝜇>4→<5 𝑥3 D∈AB <5 \>* <'*,<'@ 3 𝜇>D→<6 𝑥4 = 𝜇>3→<6 𝑥4 D∈AB <6 \>* 𝜇<B→>4 𝑥9 = 𝑥)+ = 2 𝑓2 𝑥3 , 𝑥9 𝜇<B→>4 𝑥9 = 2 𝑓1 𝑥4 , 𝑥)8 , 𝑥)) 𝜇<6→>* 𝑥4 = 𝑥)* = 2 𝑓+ 𝑥3 , 𝑥5 ?∈AB >@ \<5 𝜇>3→<6 𝑥4 = 2 𝑓1 𝑥4 , 𝑥)8 , 𝑥)) 𝑓4 𝑓2 𝑥4 𝑓) 𝑥) , 𝑥* , 𝑥1 , 𝑥2 𝜇>@→<5 𝑥3 = 2 𝑓+ 𝑥3 , 𝑥5 𝑥9 𝑥+ 𝑥3 3 D∈AB <B \>4 𝜇>D→<B 𝑥9 = 𝜇>6→<B 𝑥9 𝜇>*→<@ 𝑥+ = 2 𝑓* 𝑥+ , 𝑥3 , 𝑥4 3 <5,<6 ?∈AB >* \<@ = 2 𝑓* 𝑥, 𝑥3 , 𝑥4 𝜇<5→>* 𝑥3 𝜇<6→>* 𝑥4 <5,<6 以上で𝑥+ に向かうメッセージが全て計算できた． 𝜇<<→>* 𝑥?
具体的なグラフで確かめる つぎに，𝑥/ からメッセージを逆伝播させる． 𝜇E$ →G% 𝑥/ = X 𝜇G&→E$ 𝑥/ = 𝜇G' →E$ 𝑥/ Y 𝑓) 𝑓- 𝑥- , 𝑥. , 𝑥/ , 𝑥0 , 𝑥1 E ' ,E $ ,E ( ,E ) = Y X 𝜇E*→G% 𝑥= =∈JK G% \E % 𝑓- 𝑥- , 𝑥. , 𝑥/ , 𝑥0 , 𝑥1 𝜇E' →G% 𝑥- 𝜇E$ →G% 𝑥/ 𝜇E( →G% 𝑥0 𝜇E) →G% 𝑥1 E ' ,E $ ,E ( ,E ) = Y 𝑓- 𝑥- , 𝑥. , 𝑥/ , 𝑥0 , 𝑥1 𝜇E$ →G% 𝑥/ Y 𝑥1 𝑥2 𝑥9 𝑥+ 𝑥3 𝑓* 𝑓2 𝑥4 𝑓1 E ' ,E $ ,E ( ,E ) 𝜇G% →E' 𝑥. = 𝑓+ 𝑥* H∈JK E $ \G% 𝜇G% →E% 𝑥- = 𝑥5 𝑥) 𝑓4 𝑥)8 𝑥)) 𝑓- 𝑥. , 𝑥- , 𝑥/ , 𝑥0 , 𝑥1 𝜇E$ →G% 𝑥/ E % ,E $ ,E ( ,E ) 𝜇G% →E( 𝑥0 = Y 𝑓- 𝑥0 , 𝑥- , 𝑥. , 𝑥/ , 𝑥1 𝜇E$ →G% 𝑥/ E % ,E ' ,E $ ,E ) 𝜇G% →E) 𝑥1 = Y 𝑓- 𝑥1 , 𝑥- , 𝑥. , 𝑥/ , 𝑥0 𝜇E$ →G% 𝑥/ E % ,E $ ,E ( ,E ( 𝜇E$ →G' 𝑥/ = X 𝜇G&→E$ 𝑥/ = 𝜇G% →E$ 𝑥/ H∈JK E $ \G' 𝜇G' →E+ 𝑥M = Y 𝑓. 𝑥M , 𝑥/ , 𝑥N X E $ ,E , =∈JK G' \E + 𝜇E*→G' 𝑥= = Y 𝑓. 𝑥M , 𝑥/ , 𝑥N 𝜇E$ →G' 𝑥/ 𝜇E, →G' 𝑥N E $ ,E , 𝜇G' →E, 𝑥N = Y 𝑓. 𝑥N , 𝑥/ , 𝑥M 𝜇E$ →G' 𝑥/ 𝜇E+ →G' 𝑥M E $ ,E + こんな感じでrootノードからメッセー ジを逆伝播させれば，すべてのメッセ ージが計算できる． 𝑥)* 𝑥)+
1つの因⼦に関連する変数の周辺分布 • 1つの因⼦に関連する変数集合全体上の周辺分布𝑝 x9 を計算する． • x; は変数集合である． • 周辺分布𝑝 x9 は同時分布の周辺化により求まるから • 𝑝 x9 = ∑>\>P 𝑝(x) • x\x; はx; を除く変数集合である． 𝑓3 x x;
1つの因⼦に関連する変数の周辺分布 • まず同時分布を求める． x3 に含まれる任意の変数ノード𝑥G に注⽬ 𝑝 x = U 𝐹F E 𝑥\ , 𝑋F E xF に関連する項だけ外に出す F E ∈PQ(5F ) = 𝐹F 𝑥\ , xF \𝑥\ U 𝐹F E 𝑥\ , 𝑋F E F E ∈PQ 5G \G6 = 𝑓F 𝑥\ , xF \𝑥\ U 𝐺I 𝑥I , 𝑋FI U U 𝐹N 𝑥I , 𝑋NI I∈PQ G6 \5F N∈PQ 57 \G6 = 𝑓F xF U U I∈PQ G6 N∈PQ 57 \G6 U 𝐹F E 𝑥\ , 𝑋F E 𝐺I を変換 F E ∈PQ 5F \G6 I∈PQ G6 \5F = 𝑓F xF 𝐹F を変換 𝐹N 𝑥I , 𝑋NI U 𝐹F E 𝑥\ , 𝑋F E F E ∈PQ 5F \G6 𝑚を𝑓H の隣接ノードとす ることで， ∏HO∈AB <P \>7 𝐹HO 𝑥I , 𝑋HO を ∏D∈AB << \>7 𝐹D 𝑥?, 𝑋D? に 吸収できる． 𝐹F (xF ) 𝐺I 𝑥] , 𝑋FI 𝐺0 𝑥0 , 𝑋F0 𝑥0 𝑓3 x 𝑥\ 𝑥I x; 𝐹FE x\ , 𝑋FE
1つの因⼦に関連する変数の周辺分布 • 同時分布を周辺化する． 𝑝 xF = : 𝑝(x) = : 𝑓F xF ^\^6 = 𝑓F xF U ^\^6 : I∈PQ G6 ^\^6 = 𝑓F xF U U U U U 𝐹N 𝑥I , 𝑋NI x3 については周辺化しないので 𝑓3 x3 外に出す． x\x3 を 𝑋HD に分解する N∈PQ 57 \G6 : U I∈PQ G6 N∈PQ 57 \G6 = 𝑓F xF 𝐹N 𝑥I , 𝑋NI I∈PQ G6 N∈PQ 57 \G6 U I∈PQ G6 J!7 ,…,J:7 ,…,J;7 = 𝑓F xF U 𝜇57 →G6 𝑥I 𝐹N 𝑥I , 𝑋NI N∈PQ 57 \G6 𝑋HD に含まれる変数にかぶりがないため，積と和 を交換できる． : 𝐹N 𝑥I , 𝑋NI J:7 𝜇<<→>7 𝑥? = 3 2 𝐹D 𝑥?, 𝑋D? D∈AB << \>7 JD< I∈PQ G6 • よって， 1つの因⼦に関連する変数集合全体上の周辺分布𝑝 x9 は • 𝑝 x9 = 𝑓9 x9 ∏E∈4; @P 𝜇/c →@P 𝑥E
その他 • 積和アルゴリズムは次のように考えることが出来る． • ⻘⽮印で⽰す因⼦ノード𝑓S から発せられるメッセージは，緑⽮印で⽰す 𝑓S に⼊ ってくるメッセージの積を取り，それに更に𝑓S をかけ変数𝑥7 と𝑥: に関し周辺化 したものと⾔える． x1 x3 x2 fs • 企画化の必要性 • 因⼦グラフが有向グラフから導出されたのならば，同時分布は元々正しく規格 化されている． • 因⼦グラフが無向グラフから導出されたのならば，分配関数を求める必要があ る． • 分配関数は，積和アルゴリズムを実⾏し，規格化されていない周辺分布𝑝B 𝑥1 を 計算し，それを規格化することで，分配関数は簡単に計算できる．
Max-sum，max-productアル ゴリズム
Max-sumアルゴリズム • 積和アルゴリズムを⽤いると周辺分布を効率的に計算できる． • さらに，確率が最⼤となる変数の組を⾒つけ，その確率を求める必要があ る場合がある． • このとき⽤いられる⼿法の⼀つに，max-sumアルゴリズムがある． • ⾼い確率をもつ潜在変数を⾒つける単純な⽅法 • 積和アルゴリズムで周辺分布𝑝 𝑥1 を計算する． • それぞれの周辺分布 𝑝 𝑥1 を最⼤にする変数値𝑥1⋆ を周辺分布ごとに探す． • しかし，これは周辺分布を個別に最⼤化しているだけ． • 同時に最⼤になるとは⾔っていない． • 最⼤確率を同時に達成する変数集合を⾒つけたい． • ⾔い換えれば，同時分布を最⼤化する変数ベクトルを求めたい．
同時分布の最⼤ • 同時分布を最⼤にする変数ベクトルx FG> を求めたい． • x FG> = arg max 𝑝 x > • つまり，𝑝 x FG> = max 𝑝 x > • ⼀般に， x FG> と𝑥H⋆ の値の集合とは異なる． • x FG> と𝑥H⋆ の値の集合とは異なる例 • 表で与えられる2つの2値変数𝑥, 𝑦 ∈ {0,1}の同時分布 𝑝 𝑥, 𝑦 を考える． • 同時分布𝑝 𝑥, 𝑦 を最⼤化する𝑥と𝑦は1,0である． • ⼀⽅，それぞれの周辺分布𝑝 𝑥 , 𝑝 𝑦 を最⼤化する𝑥と𝑦は0,0である．
最⼤値と積の⼊れ替え • 𝑝 x FG> = max 𝑝 x = max 𝑝 x > /, ,…,/b • 同時分布は因⼦の積である．積の⼊れ替えが⾏えれば効率的に計算が ⾏われることが予想される． • 最⼤値の積は𝑎 ≥ 0のとき，次の法則が成り⽴つ． • max 𝑎𝑏, 𝑎𝑐 = 𝑎 max 𝑏, 𝑐 • これを使い，maxと積の⼊れ替え⾏う．
簡単な例 • 図の単純なノード連鎖の例について考える．同時分布は接続する変数 ノードの因⼦の積だから同時分布は ( ) • 𝑝 x = 𝜓(,* 𝑥( , 𝑥* 𝜓*,+ 𝑥* , 𝑥+ … 𝜓,-(,, 𝑥,-( , 𝑥, x1 • これの最⼤をとると • max 𝑝 x = > ( max ) /, ( max ) /, ,…,/b xN x2 𝜓(,* 𝑥( , 𝑥* 𝜓*,+ 𝑥* , 𝑥+ … 𝜓,-(,, 𝑥,-( , 𝑥, 1 = max[𝜓(,* 𝑥( , 𝑥* max 𝜓*,+ 𝑥* , 𝑥+ … max 𝜓,-(,, 𝑥,-( , 𝑥, /F /g /A • この式から，ノード𝑥, からメッセージ（最⼤値）が𝑥( に伝播すると解 釈することも出来る． xN
Max-productアルゴリズム • ⼀般的な因⼦グラフでは • 𝑝 x FG> = max 𝑝 x = max 𝑝 x = max ∏9 𝑓9 x9 > /, ,…,/b /, ,…,/b • と書ける．これも，適切にmaxと積を⼊れ替えれば，先の例と同じよ うに 𝑝 x FG> を求めることが出来る． • 任意の変数ノードをrootとする． • Leafノードからrootノードに向かうメッセージを伝播させる． • メッセージはrootノードへ向かうものを除く全てのメッセージを受け取った時点 で送ることが出来る． • Rootノードに到達したすべてのメッセージの積に対し，最後の最⼤化を⾏ えば 𝑝 x <=> を求めることが出来る． • この⽅法をmax-productアルゴリズムという．
Max-sumアルゴリズム • Max-productアルゴリズムでは，⼩さな値を持つ確率値の積がたくさん⽣ じる． • 実際の数値計算では，⼩さな値の積をたくさんとるとアンダーフロー問題 が⽣じる． • そこで，同時分布の対数を⽤いる．対数は単調増加関数なので arg max 𝑝 x = arg max ln 𝑝 x である． E E • 同時分布の最⼤値の対数は，確率の対数の最⼤値と同じである． • ln max 𝑝 x = max ln 𝑝 x E E • また，次のような分配則も成り⽴つ． • max ln 𝑎𝑏 , ln 𝑎𝑐 = max ln 𝑎 + ln 𝑏 , ln 𝑎 + ln 𝑐 = ln 𝑎 + max ln 𝑏 , ln 𝑐
Max-sumアルゴリズム • 確率の対数をとるとmaxと積の交換が • max 𝑎𝑏, 𝑎𝑐 = 𝑎 max 𝑏, 𝑐 から • max ln 𝑎𝑏 , ln 𝑎𝑐 = ln 𝑎 + max ln 𝑏 , ln 𝑐 のようになる． • この maxと積の交換を利⽤するため，確率の対数をとるとmaxproductアルゴリズムの積が和に変わる． • 確率の対数をとりmax-productアルゴリズムの積を和に変えたものを max-sumアルゴリズムという．
Max-sumアルゴリズムの導出
• 同時分布の対数の最⼤値を積和アルゴリズムの結果を⽤い導く．
x = x% , … , x& = 𝑥, 𝑋% , … , 𝑋&
K
<',…,<;
Sumに𝑥が含まれていないので分ける．
= max max
<
J',…,J8
K',…,K8
H
max ln 3 𝐹H 𝑥, 𝑋H = max
<,J',…,J8
𝑋!にかぶりが無いから，Sumとmaxを⼊れ替える．
2 ln 𝐹H 𝑥, 𝑋H
<
H∈AB(<)
J7
<
𝜇>7→< 𝑥 = max ln 𝐹H 𝑥, 𝑋H = max ln 𝑓H 𝑥, 𝑥) , … , 𝑥O
= max
<',…,<;
<',…,<;
ln 𝑓H 𝑥, 𝑥) , … , 𝑥O +
3
µfs !x (x)
fs
𝐺? 𝑥? , 𝑋H?
xM
𝑋) = 𝑥% , … , 𝑥*
µxM !fs (xM )
?∈AB >7 \<
2
fs
ln 𝐺? 𝑥? , 𝑋H?
<',…,<;
= max ln 𝑓H 𝑥, 𝑥) , … , 𝑥O
<',…,<;
+ max
<',…,<;
+
2
ln 𝐺? 𝑥? , 𝑋H?
<<
<',…,<;
𝜇<<→>7 𝑥? = max ln 𝐺? 𝑥? , 𝑋H? = max ln
<',…,<;
2
D∈AB << \>7
max ln 𝐹D 𝑥? , 𝑋D? =
<<
xm
𝑋!" にかぶりが無いから，Sumとmaxを⼊れ替える．
max ln 𝐺? 𝑥? , 𝑋H? = max ln 𝑓H 𝑥, 𝑥) , … , 𝑥O
?∈AB >7 \<
<',…,<;
2
D∈AB << \>7
x
µfs !x (x)
Gm (xm , Xsm )
?∈AB >7 \<
2
x
H∈AB(<)
?∈AB >7 \<
= max ln 𝑓H 𝑥, 𝑥) , … , 𝑥O
=
2 ln 𝐹H 𝑥, 𝑋H
H∈AB(<)
= max 2 max ln 𝐹H 𝑥, 𝑋H = max 2 𝜇>7→< 𝑥
H∈AB <
J7
<,J',…,J8
H∈AB(<)
Fs (x, Xs )
max ln 𝑝 x = max ln 𝑝 x = max ln 3 𝑓H xH =
3
D∈AB << \>7
𝜇>D→<< 𝑥?
+
2
𝜇<<→>7 𝑥?
fL
?∈AB >7 \<
𝐹D 𝑥? , 𝑋D? = max
<',…,<;
2
ln 𝐹D 𝑥? , 𝑋D?
xm
D∈AB << \>7
fl
Fl (xm , Xml )
このsumは周辺化しているから定数である．よってmaxの中に⼊れても良い．
fs
Max-sumアルゴリズム • よってmax-sumアルゴリズムは • 𝑝]`^ = max ∑F∈PQ 5 5 𝜇G6 →5 𝑥 • 𝜇G→5 𝑥 = max5! ,…,5P ln 𝑓 𝑥, 𝑥0 , … , 𝑥I + ∑I∈PQ(G)\5 𝜇57 →G 𝑥I • 𝜇5→G 𝑥 = ∑N∈PQ(5)\G 𝜇G: →5 𝑥 • leafノードから送られるメッセージは • 𝜇G→5 𝑥 = ln 𝑓 𝑥 • 𝜇5→G 𝑥 = 0 • 𝑥 ]`^ = arg max ∑F∈PQ 5 5 𝜇G6 →5 𝑥 • しかし，このアルゴリズムは同時分布𝑝 x の最⼤値を与える変数ベクトル x が複数ある 場合失敗する． • 各ノードにおけるメッセージの積を最⼤化して得られるそれぞれのノードの状態は，それぞれ異 なる最⼤値を与える変数ベクトル xに属する可能性がある． • 複数ある最⼤値を与える変数ベクトル xの要素を適当に組み合わせても，同時分布は最⼤になら ないだろう．
改善⼿法 • この問題はrootノードからleafノードへの少し異なる種類のメッセージを送ること で解決できる． • 図のような簡単な連鎖を考える． • 𝑥C をrootノードに決めたとする．Leafノード𝑥7 からrootノードに向かい次のような メッセージが送られる． • 𝜇5a →Za,abU 𝑥h = 𝜇ZacU →5a 𝑥h • 𝜇ZacU,a →5a 𝑥h = max ln 𝑓 𝑥hD7 , 𝑥h + 𝜇5acU →ZacU,a 𝑥hD7 5acU • Leafノードからのメッセージは 𝜇5U →ZU,d 𝑥7 = 0である． • ここで最も確からしい𝑥C の値は • 𝑥CijQ = argmax 𝜇ZecU →5e 𝑥C 5e 𝜇5% →G%,%'! 𝑥8 𝜇G%&!,% →5% 𝑥8 𝑥870 𝑓870,8 𝑥8 𝑓8,8>0 𝑥8>0
Back-tracking • ここで必要なのは，この最⼤値に対応する他の変数の状態を決めるこ とである． • この⽬的を達するには，各変数がどの値で最⼤状態を与えたか保存し ておけば良い．つまり，次の式で与えられる値を保存しておく． • 𝜙 𝑥. = arg max/>?, ln 𝑓 𝑥.-( , 𝑥. + 𝜇/>?,→@>?,,> 𝑥.-( • この操作は，最⼤値を与える𝑥.FG> が決まった後，その最⼤値を与える FG> 𝑥.-( を求める．つまり FG> • 𝑥.-( = 𝜙 𝑥.FG> • である．この操作はrootノードから逆向きに計算する．この逆向き計 算は逆伝播するメッセージに相当し，back-trackingと呼ばれる．
注意 • 𝜙 𝑥.FG> を満たす𝑥.-( が複数存在する可能性がある． • バックトラックの際，それらの値のうちのいずれかを選ぶことにすれ ば，⼤域的に整合する最⼤点が得られることが保証される． • 整合性のある解を得るためには，前向きメッセージパッシングを⾏う 際に関数𝜙 𝑥. を最⼤にする状態を記録しておき，後でバックトラッ クを⾏う必要がある． 𝜙 𝑥 連鎖モデルの講師図（トレリス図）．この図で は，𝑥& の状態3から出発する．メッセージは⿊ 線に沿って伝播される．この線が結ぶ各変数の 状態が同時分布を最⼤化する．また，破線で表 される同時分布を最⼤化する別の状態の組み合 わせも存在する． 可能な状態 UVW 0 1 1 1 2 2 2 𝜙 𝑥0UVW 2 3 𝜇 3 3 𝜙 𝑥.UVW 4 𝜇 𝑥0 3 4 𝑥1 𝜙 𝑥/UVW 𝜇 1 4 4 𝑥2 𝑥3