スライド 1

ベイジアンネットワーク概説
第4章 ベイジアンネットワークの確率推論
4.1 ベイジアンネットワークによる確率推論
4.2 確率推論のアルゴリズム
4.2.1 列挙法・変数除去法
4.2.2 確率伝搬法
岩崎唯史
4. ベイジアンネットワークの確率推論
■ ベイジアンネットワーク
不確実性を含む対象を、確率変数の集合とそ
の間の条件付き確率として表現
■ 確率推論
一部の変数を観測したときに、その他の変数
の確率分布を計算すること
4.1 ベイジアンネットワークによる確率推論 (1)
■ 各変数が離散的な値をとる場合の条件付き
確率分布(ノンパラメトリックな表現)
表4.1 条件付き確率表(CPT)
→ 親ノードが取り得る状態
→
り子
得ノ
ー
るド
状が
態取
pa(Xi)=y1
…
pa(Xi)=yj
Xi=1
θi11
…
θij1
⋮
Xi=k
⋮
θi1k
⋱
…
⋮
θijk
Xi:i番目の変数(取り得る値はk通りの離散状態)
y:親ノード群の値の取り得るパターン( j通り)
4.1 ベイジアンネットワークによる確率推論 (2)
■ モデルの近似精度は、条件付き確率表の離
散化の細かさに依存
■ 親ノードを固定し、子ノードについて値を見る
⇒ 親ノードがpa(Xi)であるときの子ノードXiに
関する条件付確率
 k

p( X i | pa( X i ))   p( X i  l | pa( X i ))  1
 l 1

■ 条件付き確率表+グラフ構造+観測情報
⇒ 予測対象の変数が取り得る状態の確率を
計算(1.4節)
4.2 確率推論のアルゴリズム
■ 確率推論
1. 観測された変数の情報(e)が与えられたと
きの求めたい変数(X)の事後確率分布
P(X|e)を求める
2. P(X|e)からXの期待値や事後確率最大の
値(MAP値)、仮説の信頼度を評価
■ 確率推論のアルゴリズム
ベイジアンネットワークモデルと観測情報を与
えたとき、観測されていない変数に関する確
率分布を計算する手順
4.2.1 列挙法・変数除去法 (1)
■ ベイジアンネットワークによる確率的推論
(1) 親ノードも観測値もないノードに事前確率
分布を与える
(2) 観測された変数Xeの値eをノードにセット
P(Xe=e)=1
P(Xe≠e)=0
(3) 知りたい対象の変数Xの事後確率分布
(1) p(X1)
P(X|e)を計算する
X
(2)
1
X2=e
X3
X4
(3) p(X4|e)
4.2.1 列挙法・変数除去法 (2)
■ 列挙法
計算例:図4.1(Xi={0,1})
1
p ( X 2  1) 
X1
p(X1)
知りたい変数
p(X3|X2)
  P( X , X
1
X 1 0 X 3 0
1
1
1
1

図4.1
 1, X 3 )
1
1
  P( X
X 1 0 X 3 0
1
1
3
2
, X3)
| X 2  1) P( X 2  1 | X 1 ) P( X 1 )
1
   P( X
X 1  0 X 2  0X 3  0
X3
2
   P( X , X
X 1  0 X 2  0X 3  0
p(X2|X1)
X2
1
あり得る全ての
状態で平均化
(周辺化)
計算量はO(23)
3
| X 2 ) P( X 2 | X 1 ) P( X 1 )
(4.1)
4.2.1 列挙法・変数除去法 (3)
一般化
m状態変数 Xi={1,2,・・・,m}がn個(i=1,2,・・・,n)
m
p( X 2  1) 
m
m
   P( X , X
X 1 1 X 3 1
X n 1
m
m
m
m
1
2
 1, X 3 ,, X n )
    P( X , X
X 1 1 X 2 1X 3 1
X n 1
1
2
, X 3 , , X n )
計算量はO(mn)
(4.2)
全変数について計算すると計算量はO(nmn)
⇒ 列挙法はネットワークの構造の性質を利用し
ていないので計算時間がかかり、非効率的
4.2.1 列挙法・変数除去法 (4)
■ 変数除去法
親を持たない最上位の変数X1は他の変数の
影響を受けないので、総和計算の外側に出す
1
p ( X 2  1) 
1
  P( X
X 1 0 X 3 0
1
1
3
| X 2  1) P ( X 2  1 | X 1 ) P ( X 1 )
1
   P( X
X 1  0 X 2  0X 3  0
1

3
1
 P( X )  P( X
X1 0
1
| X 2 ) P( X 2 | X 1 ) P( X 1 )
1
X 3 0
1
3
| X 2  1) P ( X 2  1 | X 1 )
 P( X )   P( X
X1 0
1
(4.3)
1
X 2  0X 3  0
3
| X 2 ) P( X 2 | X 1 )
計算量はO(23-1)
4.2.1 列挙法・変数除去法 (5)
■ m状態変数がn個の場合(式(4.2))、全変数
について計算する際の計算量はO(nmn-1)
ー変数除去法ー
ネットワーク構造の性質と変数間の独立性を利
用し、他の変数によらない部分の総和計算を再
帰計算の内側から外に出し、計算効率を上げる
※ 局所的な計算結果を保存し、総和計算時に
再利用することでさらに効率を上げる
⇒ 確率伝搬法
4.2.2 確率伝搬法 (1)
■ 確率伝搬法(belief propagation)
観測された情報から確率伝搬(変数間の局所計
算)によって各変数の確率分布を更新
・ 観測情報:e=(e+,e‐)
上流の観測
・ 計算したい事後確率:P(X2|e)
X 情報:e+
‐にベイズの定理
X
とe
π(X2)
2
1
X2
知りたい変数
λ(X2)
X3
下流の観測
情報:e-
図4.1
P ( X 2 | e)  P ( X 2 | e  , e  )
P (e  | X 2 , e  ) P ( X 2 | e  )

P (e  | e  )
 P ( e  | X 2 , e  ) P ( X 2 | e  )
  1 / P (e  | e  )
≡λ(X2)
≡π(X2)
(4.4)
4.2.2 確率伝搬法 (2)
■ 上流の観測情報e+からのX2への寄与
 ( X 2 )  P( X 2 | e )   P( X 2 | X1 ) P( X1 | e ) (4.5)
X1
X1についての周辺化
条件付き確率表より
≡π(X1)
(1) 観測値が与えられいる
 ( X1 )  その値
(2) 観測値がなく、最上流のノード
 ( X1 )  事前確率
(3) 観測値がなく、上流に親ノードをもつ
 ( X 1 )   P ( X 1 | X upper ) ( X upper )
X upper
π(Xupper)
Xupper
(1)or(2)まで再帰
π(X1)
X1
π(X2)
X2
4.2.2 確率伝搬法 (3)
■ 下流の観測情報e‐からのX2への寄与
 ( X 2 )  P (e  | X 2 )   P (e  | X 2 , X 3 ) P ( X 3 | X 2 )
X3
X3についての周辺化
e-はX2によらない
  P(e | X 3 ) P( X 3 | X 2 ) (4.6)

X3
≡λ(X3)
条件付き確率表より
(1) 観測値が与えられいる
 ( X 3 )  その値
(2) 観測値がなく、最下流のノード
 ( X 3 )  一様確率(無情報)
(3) 観測値がなく、下流に子ノードをもつ
 ( X 3 )    ( X lower ) P( X lower | X 3 )
X lower
(1)or(2)まで再帰
X2
λ(X2)
X3
λ(X3)
Xlower
λ(Xlower)
4.2.2 確率伝搬法 (4)
■ 任意のノード(Xi)の事後確率
(式(4.4)の一般化)
P( X j | e)  ( X j ) ( X j )
e  (e  , e  )
  1 / P (e  | e  )
 ( X j )  P( X j | e )
( X j )  P(e | X j )

4.2.2 確率伝搬法 (5)
■ 親ノードi個、子ノードj個の場合
P r(X  x)   ( x) ( x)
U1
 ( x)   P( x | U  u )  U X (u )
Ui
X
Yj
 XY ( x)   ( x) Y X ( x)
Y1
k
・・・
 XU (u )    ( x) P( x | U )  U X (uk )
i
x
k i
k i
λ(x)
λYX(x)
To X
πXY(x)
From X
j
k j
λXU(u)
From X
π(x)
 ( x)   Y X ( x)
j
Ui
πUX(u)
To X
i
u
・・・
k
図4.2 確率伝搬アルゴリズム
Yj
4.2.2 確率伝搬法 (6)
■ 単純結合ネットワーク(グラフにループなし)の
場合、計算量はグラフの辺の数に比例
■ アルゴリズム(全ての状態を列挙しない)
(1) P(Xi|e)、 π(Xi)、λ(Xi)の値を設定
(2) CPTと(1)の各値から新しいP(Xi|e)、 π(Xi)、
λ(Xi) を再計算
*確率が収束するまで(2)を繰り返す
■ 複結合ネットワーク(グラフにループあり)の場
合、確率が収束する保障なし