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