Chap.8 グラフィカルモデル
項目
1.
2.
3.
4.
ベイジアンネットワーク
条件付き独立性
マルコフ確率場
グラフィカルモデルにおける推論
Chap.8 グラフィカルモデル
はじめに
• 確率論は、その基本である加法定理(sum rule)、乗法定理(product rule)で代数的
に考えられる。
• 解析のツールとして確率的グラフィカルモデルを用いる。
グラフィカルモデルの特徴
1. 確率モデルの構造を視覚化する簡単な方法、モデルの設計方針を決めるのに
役立つ
2. グラフの構造を調べることから、条件付き独立性等のモデルの性質に関する知
見が得られる
3. 精巧なモデルでは推論や学習を実行するためには複雑な計算が必要。
グラフではその操作で表現できる
グラフ： リンク(結線l(ink), 辺(edge), 弧(arc))、ノード(節(node)、頂点(vertex))の集合
• 先に、グラフのリンクの方向を持つ矢印で描かれるベイジアンネットワーク(Baysian
network)(有向グラフィカルモデル: directed graphical model)を考える
• もう一つはマルコフ確率場(Markov random field)(無向グラフィカルモデル: undirected
graphical model)
• 推論問題を解くときには有向、無向グラフを因子グラフ(factor graph)に変換すると便
利
Chap.8 グラフィカルモデル
1, ベイジアンネットワーク
• 3変数(a,b,c)の同時確率分布𝑝 𝑎, 𝑏, 𝑐
乗法定理より
𝑝 𝑎. 𝑏. 𝑐 = 𝑝 𝑐 𝑎, 𝑏 𝑝 𝑎, 𝑏 … (8.1)
𝑝 𝑎, 𝑏, 𝑐 = 𝑝 𝑐 𝑎, 𝑏 𝑝 𝑏 𝑎 𝑝 𝑎 … (8.2)
ノードaはノードbの親ノード(parent node)
ノードbはノードaの子ノード(child node)
K変数の同時分布𝑝 𝑥1 , … , 𝑥𝐾 のとき、
𝑝 𝑥1 , … , 𝑥𝐾 = 𝑝 𝑥𝐾 𝑥1 , … , 𝑥𝐾−1 … 𝑝 𝑥2 𝑥1 )𝑝(𝑥1 ) … (8.3)
• 自分よりも番号の小さい全てのノードからリンクが向かっている
… 全結合(fully connected)
cの条件：a,b
bの条件：a
となるグラフ
Chap.8 グラフィカルモデル
1, ベイジアンネットワーク
一般的な場合 … 例えば、右のような7変数の同時確率分布
𝑝 𝑥1 𝑝 𝑥2 𝑝 𝑥3 𝑝 𝑥4 𝑥1 , 𝑥2 , 𝑥3 𝑝 𝑥5 𝑥1 , 𝑥3 𝑝 𝑥6 𝑥4 𝑝 𝑥7 𝑥4 , 𝑥5
グラフで表される同時分布の一般形
𝐾
𝑝 𝒙 =
𝑝 𝑥𝑘 𝑝𝑎𝑘
𝑘=1
𝑝𝑎𝑘 : 𝑥𝑘 の親ノード集合
𝒙 = {𝑥1 , 𝑥2 , … , 𝑥𝐾 }
同時分布は各ノード変数での条件付き確率分布の積で表される。
この有向グラフは有向閉路(directed cycle)を持たない、有向非循環グラフ(DAG:
directed acyclic graph)である。
⇒ 大きい番号を持つノードから小さい番号を持つノードへのリンクは存在しない
Chap.8 グラフィカルモデル
1, ベイジアンネットワーク
1.1，(例)多項式曲線フィッティング
有向グラフの利用例として…
確率変数
• 係数ベクトル w
• 観測データ t
𝑁
𝑝 𝒕, 𝒘 = 𝑝 𝒘
𝑝 𝑡𝑛 𝒘
𝑛=1
モデルのパラメータ
• 入力データ x
• ノイズの分散 σ2
• wのガウス事前分布の精度 α
𝒘
𝑡1
モデルパラメータを明示的に扱うと…
𝑁
𝑝 𝑡, 𝑤 𝑥, 𝛼, 𝜎 2 = 𝑝 𝑤 𝛼
𝑝 𝑡𝑛 𝑤, 𝑥𝑛 , 𝜎 2
𝑛=1
N個のノードが入ったプレート
𝑡𝑛
Chap.8 グラフィカルモデル
1, ベイジアンネットワーク
1.1，(例)多項式曲線フィッティング
𝑁
𝑝 𝑡, 𝑤 𝑥, 𝛼, 𝜎 2 = 𝑝 𝑤 𝛼
𝑝 𝑡𝑛 𝑤, 𝑥𝑛 , 𝜎 2
𝑛=1
𝒘は潜在変数 … {tn}の値からwの事後確率がわかる
決定的パラメータ
観測変数
多項式フィッティングの最終目的 …
新しい入力(𝑥)に対する予測(𝑡)
𝑁
𝑝 𝑡, 𝒕, 𝑤|𝑥, 𝒙, 𝛼, 𝜎 2 =
𝑝 𝑡𝑛 𝑥𝑛 , 𝒘, 𝜎 2
𝑝 𝒘 𝛼 𝑝(𝑡|𝑥, 𝒘, 𝜎 2 )
𝑛=1
𝑤を積分消去すると、𝑡の予測分布が得られる
𝑝 𝑡 𝑥, 𝒙, 𝒕, 𝛼, 𝜎 2 ∝
𝑝 𝑡, 𝒕, 𝒘 𝑥, 𝒙, 𝛼, 𝜎 2 𝑑𝒘
Chap.8 グラフィカルモデル
1, ベイジアンネットワーク
1.2, 生成モデル
(サンプリング法の詳細は11章)
伝承サンプリング
K変数での同時分布: 𝑝(𝑥1 , … , 𝑥𝐾 ) … 有向非循環グラフ、親ノードは子ノードより番号が小さい
この同時分布に従うサンプル値𝑥1 , … , 𝑥𝐾 を発生させる
→ 1番目から順番に生成する
N番目では𝑝 𝑥𝑛 𝑝𝑎𝑛 に従う
観測データが生成される因果過程を表現する
生成モデル (generative model)
Chap.8 グラフィカルモデル
1, ベイジアンネットワーク
1.3, 離散変数
グラフィカルモデル … 親、子ノードが共に離散変数やガウス分布なら非常に便利な枠組み
→ 有向非循環グラフが構築できる
K個の状態を取る離散変数xの確率分布
𝐾
𝑥
𝜇𝑘 𝑘
𝑝 𝒙𝝁 =
パラメータ𝝁によって支配
規格化制約 𝑘 𝜇𝑘 = 1
𝑘=1
K-1個の𝜇を指定すると分布が決まる
2つの状態変数(𝒙1 , 𝒙2 )があるとき…
𝐾
𝐾
𝑥
𝜇𝑘𝑙1𝑘
𝑝 𝑥1 , 𝑥2 𝜇 =
𝑘=1 𝑙=1
𝑥2𝑙
規格化制約 𝑘 𝑙 𝜇𝑘𝑙 = 1
→ K2-1個のパラメータ
状態変数がM個のとき、
KM-1個のパラメータが必要！
Chap.8 グラフィカルモデル
1, ベイジアンネットワーク
1.3, 離散変数
(a)確率の乗法定理 … 𝑝 𝒙1 , 𝒙2 = 𝑝 𝒙2 𝒙1 𝑝(𝒙1 )
(b)𝒙1 , 𝒙2 が互いに独立のとき… リンクを除去
→ 必要なパラメータ数は2(K-1)個
M個の独立なK個の離散変数ではM(K-1)個
リンクの操作でパラメータ数を削減できた
パラメータの共有(sharing)(結合: tying)によっても、パラメータを減らすことができる。
パラメータにディリクレ事前分布を導入したネットワーク
Chap.8 グラフィカルモデル
1, ベイジアンネットワーク
1.4，線形ガウスモデル
線形ガウスモデルに対応する有向グラフで多変量ガウス分布を表現する
ノードi: ガウス分布に従う連続値確率変数𝑥𝑖
𝑝 𝑥𝑖 𝑝𝑎𝑖 = 𝑁 𝑥𝑖 |
𝑤𝑖𝑗 𝑥𝑗 + 𝑏𝑖 , 𝑣𝑖
𝑗∈𝑝𝑎𝑖
𝑤𝑖𝑗 , 𝑏𝑖 :平均を支配するパラメータ
𝑣𝑖 : 𝑥𝑖 の条件付き分布の分散
同時分布の対数は…
𝐷
ln 𝑝 𝒙 =
𝐷
=−
𝑖=1
D: 変数の個数
ln 𝑝(𝑥𝑖 |𝑝𝑎𝑖 )
𝑖=1
1
𝑥 −
2𝑣𝑖 𝑖
2
𝑤𝑖𝑗 𝑥𝑗 − 𝑏𝑖
+ 𝑐𝑜𝑛𝑠𝑡.
𝑗∈𝑝𝑎𝑖
𝑥𝑖 の2次関数 → 同時分布p(x)は多変量ガウス分布
Chap.8 グラフィカルモデル
1, ベイジアンネットワーク
1.4，線形ガウスモデル
𝑥𝑖 は、
𝑥𝑖 =
となる。
𝑤𝑖𝑗 𝑥𝑗 + 𝑏𝑖 +
𝑣𝑖 𝜖𝑖
𝑗∈𝑝𝑎𝑖
これより、xの成分の期待値と共分散は
𝐸 𝑥𝑖 =
𝑤𝑖𝑗 𝐸 𝑥𝑗 + 𝑏𝑖
𝑗∈𝑝𝑎𝑖
𝑐𝑜𝑣 𝑥𝑖 , 𝑥𝑗 = 𝐸 𝑥𝑖 − 𝐸 𝑥𝑖
𝑥𝑗 − 𝐸 𝑥𝑗
=
𝑤𝑗𝑘 𝑐𝑜𝑣 𝑥𝑖 , 𝑥𝑘 + 𝐼𝑖𝑗 𝑣𝑗
𝑘∈𝑝𝑎𝑗
どちらも番号の小さいノードから再帰的に計算できる
Chap.8 グラフィカルモデル
2，条件付き独立性(conditional independence)
3変数a,b,cにおいて、b,cが与えられたときaの条件付き確率がbに依存しない
𝑝 𝑎 𝑏, 𝑐 = 𝑝 𝑎 𝑐
このとき、cが与えられた下で、aはbに対して条件付き独立である
このとき、
𝑝 𝑎, 𝑏 𝑐 = 𝑝 𝑎 𝑏, 𝑐 𝑝 𝑏 𝑐 = 𝑝 𝑎 𝑐 𝑝(𝑏|𝑐)
c
c
a
b
a
b
条件付き独立性を示せると
リンクが減らせる
全ての条件付き独立性を調べるには膨大な計算が必要
→ グラフの形で独立かどうか判断可能(有向分離：d-separation)
Chap.8 グラフィカルモデル
2，条件付き独立性
3つのノードによる簡単な例3パターン
その1： tail-to-tail
𝑝 𝑎, 𝑏, 𝑐 = 𝑝 𝑎 𝑐 𝑝 𝑏 𝑐 𝑝 𝑐
cに対して周辺化(a,bが独立か調べる)
𝑝 𝑎, 𝑏 =
𝑝 𝑎𝑐 𝑝 𝑏𝑐 𝑝 𝑐
𝑐
これは、𝑝 𝑎 𝑝 𝑐 の形にならない(独立でない)
cで条件付け
𝑝 𝑎, 𝑏, 𝑐
=𝑝 𝑎𝑐 𝑝 𝑏𝑐
𝑝 𝑐
これは条件付き独立である
𝑝 𝑎, 𝑏 𝑐 =
Chap.8 グラフィカルモデル
2，条件付き独立性
その２： head-to-tail
𝑝 𝑎, 𝑏, 𝑐 = 𝑝 𝑎 𝑝 𝑐 𝑎 𝑝 𝑏 𝑐
cに対して周辺化
𝑝 𝑎, 𝑏 = 𝑝 𝑎
𝑝 𝑐𝑎 𝑝 𝑏𝑐 =𝑝 𝑎 𝑝 𝑏𝑎
𝑐
a,bは独立ではない
cで条件付け
𝑝 𝑎, 𝑏, 𝑐
𝑝 𝑎 𝑝 𝑐𝑎 𝑝 𝑏𝑐
=
𝑝 𝑐
𝑝 𝑐
=𝑝 𝑎𝑐 𝑝 𝑏𝑐
条件付き独立となる
𝑝 𝑎, 𝑏 𝑐 =
cが観測されれば、a,bのリンクを遮断できる
Chap.8 グラフィカルモデル
2，条件付き独立性
その3： head-to-head
𝑝 𝑎, 𝑏, 𝑐 = 𝑝 𝑎 𝑝 𝑏 𝑝 𝑐 𝑎, 𝑐
cに対して周辺化
𝑝 𝑎, 𝑏 = 𝑝 𝑎 𝑝 𝑏
a,bは独立
cで条件付け
𝑝 𝑎, 𝑏 𝑐 =
𝑝 𝑎, 𝑏, 𝑐
𝑝 𝑎 𝑝 𝑏 𝑝 𝑐 𝑎, 𝑏
=
𝑝 𝑐
𝑝 𝑐
cで条件付けられることで、a,bとcの間に依存
関係が生まれる
→ 「弁明(explaining away)」現象の発生
(ここでは省略…)
Chap.8 グラフィカルモデル
2，条件付き独立性
2, 有向分離
A,B,C：重複しないノード集合
これまでの話をノード集合へ拡張
(a)or(b)のとき、A,BはCの下で条件付き独立
(A,Bの経路は遮断される)
(a) 集合Cに含まれるノードで、経路に含まれる矢
印がhead-to-tailかtail-to-tailである
C
C
A
B
C
A
A
B
(b)経路に含まれる矢印がそのノードでhead-to-headで、
自身とその全ての子孫が集合Cに含まれない。
B
Chap.8 グラフィカルモデル
2，条件付き独立性
2, 有向分離
(a),(b)でノードa, bは集合Cで遮断できるか？
C
(a)
C
(b)
B
B
A
→遮断できない
fはtail-to-tailで観測されていない
eはhead-to-headだが、子孫cが条
件付け集合に含まれる
A
→遮断できる
fはtail-to-tailで観測
eはhead-to-headで子孫
が条件付け集合に含ま
れない
Chap.8 グラフィカルモデル
2，条件付き独立性
2, 有向分離
有向分離の特性
パラメータノード：観測済みノード
親ノードを持たず、経路は全てtail-to-tail
→ 他のノードの有向分離特性に影響しない
独立同時分布…パラメータ𝜇はtail-to-tail
→ 𝜇が与えられれば、観測値は独立
𝜇を積分消去したとき…
∞
𝑝 𝐷 =
𝑁
𝑝 𝐷 𝜇 𝑝 𝜇 𝑑𝜇 ≠
0
観測値は独立でない
𝑝 𝑥𝑛
𝑛=1
Chap.8 グラフィカルモデル
2，条件付き独立性
2, 有向分離
ベイズ多項式モデル
wが条件付けられたとき、tail-to-tailであるから、
つまり、𝑡の予測分布は訓練データ𝑡𝑛 に対して独立
→ wの事後分布を決めたら、訓練データは必要ない
Chap.8 グラフィカルモデル
2，条件付き独立性
2, 有向分離
マルコフブランケット(Markov blanket)(マルコフ境界: Markov boundary)
xiが起こる確率をxi以外の全てのノードで条件付ける
𝑝 𝑥1 , … , 𝑥𝐷
𝑝 𝑥𝑖 𝑥𝑖≠𝑗 =
𝑝 𝑥1 , … , 𝑥𝐷 𝑑𝑥𝑖
𝑘 𝑝 𝑥𝑘 𝑝𝑎𝑘
=
𝑘 𝑝 𝑥𝑘 𝑝𝑎𝑘 𝑑𝑥𝑖
𝑥𝑖 に関係ない因子はキャンセルされる。
→ 𝑥𝑖 をグラフから孤立させる最小集合
𝑥𝑖 の条件付き独立性を考えるには、
• 親、子ノード
• 共同親(子ノードの𝑥𝑖 以外の親)
を考える
Chap.8 グラフィカルモデル
3, マルコフ確率場
マルコフ確率場(Markov random field)(マルコフネットワーク: Markov network)
• 無向グラフィカルモデル(undirected graphical model)
• ノード集合とリンク集合から成る(リンクの向きは関係ない)
マルコフ確率場の例
確率変数同士の緩い束縛関係
ベイジアンネットワークの例
確率変数間の因果関係
Chap.8 グラフィカルモデル
3, マルコフ確率場
1，条件付き独立性
有向グラフ … head-to-headやtail-to-tail、有向分離
→ 「遮断」を考えるには複雑
無向グラフ … 親子ノード間の非対称性はない
(向きがない！)
集合A, Bを結ぶ全ての経路が集合Cのノードを通
る
→ Cで遮断できる
簡単に言えば、集合Cのノード・リンクを取り除い
て繋がらなければCの下でA, Bは条件付き独立
Chap.8 グラフィカルモデル
3, マルコフ確率場
2，分解特性
無向グラフの分解特性
𝑝 𝑥𝑖 , 𝑥𝑗 𝑥∖ 𝑖,𝑗 = 𝑝 𝑥𝑖 𝑥∖ 𝑖,𝑗 𝑝(𝑥𝑗 |𝑥∖ 𝑖,𝑗 )
𝑥∖ 𝑖,𝑗 : 𝑖, 𝑗以外の全ての変数
同時確率が𝑥𝑖 , 𝑥𝑗 が同じ因子に含まれないように因数分解できれば、条件付き独立
クリーク(clique)
全てのノードの組にリンクが存在するグラフの部分集合
(クリーク内のノードは全結合)
極大クリーク: ノードを1つ加えるとクリークではなくなる集合
(左図なら、 𝑥1 , 𝑥2 , 𝑥3 , 𝑥2 , 𝑥3 , 𝑥4 )
同時分布を因数分解したときの因子をクリークが含む変数
の集合の関数にすると良い
Chap.8 グラフィカルモデル
3, マルコフ確率場
2，分解特性
クリークC、C内の変数を𝑥𝐶 とする
ポテンシャル関数𝜓 𝑥𝐶 、𝑍を規格化定数
𝑝 𝑥 =
1
𝑍
𝜓 𝑥𝐶
𝐶
𝑍=
𝜓 𝑥𝐶
𝑥
𝐶
ポテンシャル関数は確率的に解釈可能なものに限定されない
規格化定数の必要性と計算が大変
ポテンシャル関数は𝜓𝐶 𝑥𝐶 > 0(狭義に正) (因数分解と条件付き独立の関係)
指数関数で表現する
𝜓𝐶 𝑥𝐶 = exp −𝐸 𝑥𝐶
𝐸 𝑥𝐶 はエネルギー関数、この関数形をボルツマン分布という
Chap.8 グラフィカルモデル
3, マルコフ確率場
3, 画像のノイズ除去
元画像
10%ランダム反転
ピクセルごとに色の有無: 𝑦𝑖 = −1, +1 (𝑖 ∈ 𝐷)
ノイズなしの画像𝑥𝑖 ∈ {−1. +1}からランダムに反転
この画像からノイズを除去するには…
ノイズレベルが低い…
• 𝑥𝑖 , 𝑦𝑖 に強い相関が期待 … −𝜂𝑥𝑖 𝑦𝑖
• 隣接ピクセルの強い相関も期待 … −𝛽𝑥𝑖 𝑥𝑗
これらの式は同符号で低エネルギー(高い確率)
異符号で高エネルギー(低い確率)
となる
これより、全エネルギー関数は
ICMによる復元
グラフカットアルゴリ
ズムによる復元
𝐸 𝑥, 𝑦 = ℎ
𝑥𝑖 − 𝛽
𝑖
𝑥𝑖 𝑥𝑗 − 𝜂
𝑖,𝑗
𝑥, 𝑦の同時分布は
ノイズ付き画像のピクセル
元画像のピクセル
𝑝 𝑥, 𝑦 =
1
exp −𝐸 𝑥, 𝑦
𝑍
𝑥𝑖 𝑦𝑖
𝑖
Chap.8 グラフィカルモデル
3, マルコフ確率場
4，有向グラフとの関係
簡単な例
有向グラフ
𝑝 𝑥 = 𝑝 𝑥1 𝑝 𝑥2 𝑥1 𝑝 𝑥3 𝑥2 … 𝑝(𝑥𝑁 |𝑥𝑁−1 )
無向グラフ(極大クリークは隣接ノード対)
1
𝑝 𝑥 = 𝜓1,2 𝑥1 , 𝑥2 𝜓2,3 𝑥2 , 𝑥3 … 𝜓𝑁−1,𝑁 (𝑥𝑁−1 , 𝑥𝑁 )
𝑍
次のように対応付けられる
𝜓1,2 𝑥1 , 𝑥2 = 𝑝 𝑥1 𝑝 𝑥2 𝑥1
𝜓2,3 𝑥2 , 𝑥3 = 𝑝 𝑥3 𝑥2
⋮
𝜓𝑁−1,𝑁 𝑥𝑁−1 , 𝑥𝑁 = 𝑝(𝑥𝑁 |𝑥𝑁−1 )
ポテンシャル関数 ⇔ 条件付き分布
Chap.8 グラフィカルモデル
3, マルコフ確率場
4，有向グラフとの関係
一般化して…
有向グラフ条件付き分布の変数集合の全て
→ 無向グラフの少なくとも一つのクリークのノード集合に含まれる
親が1つ：矢印を取る
親が2つ以上 … モラル化
左図の場合…
𝑝 𝑥 = 𝑝 𝑥1 𝑝 𝑥2 𝑝 𝑥3 𝑝(𝑥4 |𝑥1 , 𝑥2 , 𝑥3 )
𝑝(𝑥4 |𝑥1 , 𝑥2 , 𝑥3 )を1つのクリークポテンシャル関数へ
→ 親同士を結ぶ(モラル化)
Chap.8 グラフィカルモデル
4，グラフィカルモデルによる推論
グラフの観測ノードを固定したとき、残りのノードを効率よく推定する
例えば … ベイズの定理
変数yが観測されたとき(b)
p(x)は事前分布
加法、乗法定理より
𝑝 𝑦 𝑥′ 𝑝 𝑥′
𝑝 𝑦 =
𝑥′
ベイズの定理から
𝑝 𝑥𝑦 =
𝑝 𝑦𝑥 𝑝 𝑥
𝑝 𝑦
xの事後分布を求められる
Chap.8 グラフィカルモデル
4，グラフィカルモデルによる推論
1，連鎖における推論
N個のノードからの無向グラフ
グラフの同時分布は …
1
𝑝 𝒙 = 𝜓1,2 𝑥1 , 𝑥2 𝜓2,3 𝑥2 , 𝑥3 … 𝜓𝑁−1,𝑁 (𝑥𝑁−1 , 𝑥𝑁 )
𝑍
(8.49)
ノード𝑥𝑛 の周辺分布𝑝(𝑥𝑛 )を推論する
𝑝 𝑥𝑛 =
…
𝑥1
…
𝑥𝑛−1 𝑥𝑛
𝑝 𝑥
𝑥𝑁
(8.50)
K状態、それぞれN個変数を持つから、xは𝐾 𝑁 個！
→ 鎖の長さNに対して指数的に計算量、メモリ量が増大
Chap.8 グラフィカルモデル
4，グラフィカルモデルによる推論
1，連鎖における推論
N個のノードからの無向グラフ
グラフを使って効率化
(8.49)を(8.50)に代入して、 𝑥𝑁 𝜓𝑁−1,𝑁 𝑥𝑁−1 , 𝑥𝑁 を計算(𝑥𝑁 に関係するのは𝜓𝑁−1,𝑁 のみ)
次に、𝑥𝑁−1 … 次々と変数を消去できる
1
𝑝 𝑥𝑛 =
𝜓𝑛−1,𝑛 𝑥𝑛−1 , 𝑥𝑛 …
𝜓2,3 𝑥2 , 𝑥3
𝜓1,2 𝑥1 , 𝑥2 …
𝑍
𝑥𝑛 −1
𝜓𝑛,𝑛+1 𝑥𝑛 , 𝑥𝑛+1 …
𝑛+1
𝑥2
𝑥𝑁
𝑥1
𝜓𝑁+1,𝑁 𝑥𝑁−1 , 𝑥𝑁
𝜇𝛽 𝑥𝑛
積と和の演算順序を入れ替えることで演算の効率を良くする
…
𝜇𝛼 𝑥𝑛
Chap.8 グラフィカルモデル
4，グラフィカルモデルによる推論
1，連鎖における推論
局所的なメッセージの伝播と捉える…
1
𝑝 𝑥𝑛 = 𝜇𝛼 𝑥𝑛 𝜇𝛽 𝑥𝑛
𝑍
前へ伝わるメッセージ
𝜇𝛼 は…
𝜇𝛼 𝑥𝑛 =
𝜓𝑛−1,𝑛 𝑥𝑛−1 , 𝑥𝑛 𝜇𝛼 𝑥𝑛−1
𝑥𝑛−1
再帰的に計算できる。(メッセージパッシング)
𝜇𝛽 も同様。
マルコフ連鎖(Markov chain)と呼ばれる
後ろへ伝わるメッセージ
Chap.8 グラフィカルモデル
4，グラフィカルモデルによる推論
2，木(tree)
連鎖 → メッセージパッシングで効率よく推論
木構造 → 局所的にメッセージパッシングで推論可能
→ 積和(sum-product)アルゴリズム
木構造の例
無向木
ループなし
有向木
親なしノード1つと
親を1つだけ持つ子ノード
無向変換のときモラル化不要
有向多重木
親なしノード複数
モラル化するとループあり
Chap.8 グラフィカルモデル
4，グラフィカルモデルによる推論
3, 因子グラフ(factor graph)
○因子グラフ
因子そのものに対応するノードを付け加える
有向グラフなら
𝐾
ある変数集合の同時分布を因子の積の形で…
𝑝 𝒙 =
𝑓𝑠 (𝒙𝑠 )
𝑠
例えば、次のような分布
𝑝 𝑥 = 𝑓𝑎 𝑥1 , 𝑥2 𝑓𝑏 𝑥1 , 𝑥2 𝑓𝑐 𝑥2 , 𝑥3 𝑓𝑑 𝑥3
同変数の因子も残すことでより詳細な情報を
残す
因子グラフは2種類のノードが存在し、異種
ノードを接続する
𝑝 𝒙 =
無向グラフなら
𝑝 𝒙 =
𝑝 𝑥𝑘 𝑝𝑎𝑘
𝑘=1
1
𝑍
𝜓 𝐶 𝒙𝐶
𝐶
Chap.8 グラフィカルモデル
4，グラフィカルモデルによる推論
3, 因子グラフ(factor graph)
因子グラフによる様々なグラフの表現
木構造は維持される
局所的なループを回避することも
同じグラフでも因子によって異なる表現
Chap.8 グラフィカルモデル
4，グラフィカルモデルによる推論
4，積和アルゴリズム
ノード or ノードの部分集合の局所的な周辺分布計算する
木構造の因子グラフを利用して推論を効率的に
目的
i) 周辺分布を得るための効率良い厳密推論アルゴリズムを得る
ii)複数の周辺分布を計算するとき、計算の重複をなくす
元のグラフは無向木、有向木、多重木のいずれか
それを因子グラフに変換する
Chap.8 グラフィカルモデル
4，グラフィカルモデルによる推論
4，積和アルゴリズム
ある変数xの周辺分布p(x)を求める
𝑝 𝒙 =
𝑝(𝒙)
𝒙∖𝑥
(8.61)
(𝒙以外の同時分布の和)
グラフは木構造
→ 隣接ノードでグループ分け
𝑝 𝑥 =
𝐹𝑠 𝑥, 𝑋𝑠
𝑠∈𝑛𝑒 𝑥
(8.62)
𝑛𝑒 𝑥 : xに隣接する因子ノード集合
𝑋𝑠 : 因子ノード𝑓𝑠 を通してノードxにつながる部分木に属する
変数の集合
𝐹𝑠 (𝑥, 𝑋𝑠 ): 𝑓𝑠 に関係する因子の積
(8.62)へ(8.61)を代入し、和と積を入れ替え
𝑝 𝑥 =
𝐹𝑠 𝑥, 𝑋𝑠
𝑠∈𝑛𝑒 𝑥
𝑋𝑠
=
𝜇𝑓𝑠 →𝑥 𝑥
𝑠∈𝑛𝑒(𝑥)
𝑓𝑠 から𝑥へのメッセージ
Chap.8 グラフィカルモデル
4，グラフィカルモデルによる推論
4，積和アルゴリズム
さらに分解
𝐹𝑠 𝑥, 𝑋𝑠 = 𝑓𝑠 𝑥, 𝑥1 , … , 𝑥𝑀 𝐺1 𝑥1 , 𝑋𝑠1 … 𝐺𝑀 𝑥𝑀 , 𝑋𝑠𝑀
因子に隣接する変数たち
𝜇𝑓𝑠 →𝑥 𝑥 =
𝑋𝑠 𝐹𝑠
𝑥, 𝑋𝑠 から
𝜇𝑓𝑠 →𝑥 𝑥 =
…
𝑥1
=
𝑓𝑠 𝑥, 𝑥1 , … , 𝑥𝑀
𝑥𝑀
…
𝑥1
𝐺𝑚 𝑥𝑚 , 𝑋𝑠𝑚
𝑚∈𝑛𝑒 𝑓𝑠 ∖𝑥 𝑋𝑚
𝑓𝑠 𝑥, 𝑥1 , … , 𝑥𝑀
𝑥𝑀
𝜇𝑥𝑚 →𝑓𝑠 𝑥𝑚
𝑚∈𝑛𝑒 𝑓𝑠 ∖𝑥
(8.66)
さらに、Gを計算する
𝐺𝑚 𝑥𝑚 , 𝑋𝑠𝑚 =
𝐹𝑙 𝑥𝑚 , 𝑋𝑚𝑙
𝑙∈𝑛𝑒(𝑥𝑚 )∖𝑓𝑠
つまり、
𝜇𝑥𝑚 →𝑓𝑠 𝑥𝑚 =
𝐹𝑙 𝑥𝑚 , 𝑋𝑚𝑙
=
𝑙∈𝑛𝑒(𝑥𝑚 )∖𝑓𝑠 𝑋𝑚𝑙
𝜇𝑓𝑙 →𝑥𝑚 (𝑥𝑚 )
𝑙∈𝑛𝑒(𝑥𝑚 )∖𝑓𝑠
(8.69)
これにより、FとGが消去できる
Chap.8 グラフィカルモデル
4，グラフィカルモデルによる推論
4，積和アルゴリズム
積和アルゴリズムは葉ノードからのメッセージから始まる
葉ノードが変数ノードなら
𝜇𝑥→𝑓 𝑥 = 1
因数ノードなら
𝜇𝑓→𝑥 𝑥 = 𝑓 𝑥
𝜇𝑥→𝑓 𝑥 = 1
𝑥
𝜇𝑓→𝑥 𝑥 = 𝑓(𝑥)
𝑓
𝑓
𝑥
Chap.8 グラフィカルモデル
4，グラフィカルモデルによる推論
4，積和アルゴリズム
まとめ
•
•
•
•
目的の変数ノード𝑥を根ノードとする
葉ノードは前ページの形でメッセージを初期化
p37の式でメッセージパッシングを再帰的に適用
各ノードは根ノードへ向かうリンク以外の全ての隣接ノードからメッセージを受
け取り、メッセージを流す
• 根ノードが全ての隣接ノードからメッセージを受け取るまで繰り返す
© Copyright 2024 ExpyDoc
