クラスター変分法と線形応答理論を用いた
ベイジアンネットワークの
確率伝搬アルゴリズム
Belief Propagation Algorithm for Bayesian Network
by means of Cluster Variation Method and
Linear Response Theory
東北大学大学院情報科学研究科
田中和之
1
序論
ベイズの公式
確率モデル
グラフィカルモデル
確率推論
信念
周辺確率分布
ループのある
グラフィカルモデル
=>厳密ではないが良い
結果が得られる．
確率伝搬法
木構造のある
グラフィカルモデル
=>厳密な結果
クラスター変分法を
用いた一般論
2
確率推論
確率推論とグラフィカルモデル
P( x1 , x2 , x3 , x4 , x5 , x6 , x7 , x8 )
1 W568 ( x5 , x6 , x8 )W346 ( x3 , x4 , x5 )W67 ( x6 , x7 )

Z
W6 ( x6 ) 2W5 ( x5 )W4 ( x4 )
W25 ( x2 , x5 )W24 ( x2 , x4 )W13 ( x1 , x3 )

W3 ( x3 )W2 ( x2 )
X1
X2
W24
W13
X3
W3
W6
W67
X7
W346
X6
W25
X4
W4
W568
X8
X5
W5
3
確率推論
確率推論と周辺確率分布
Pi ( xi )   P( x1 , x2 , x3 , x4 , x5 , x6 , x7 , x8 )
x \ xi
(i  1,2,3,4,5,6,7,8)
X1
X2
W24
W13
X3
W3
W6
W67
X7
W346
X6
W25
X4
W4
W568
統計学：周辺確率分布
統計力学：一体分布関数
X5
W5
確率推論：信念
X8
4
クラスター変分法
Kullback-Leibler Divergence とクラスター変分法
 Q x  
 Q x   0 
  0 

DQ P   Q( x) ln
  Q( x )  1
x
 P x  
X1
X3
W3
 D3  D4  D5  2D6  ln Z
X6
W67
W4
W3
X2
W24
X4
X3
X3
W346
W2
W67
X6
W25
X5
X4
X6
X2
W4
W5
X6
X7
W5
X2
X4
X3
X5
W568
X8
X1
W13
W25
X4
X7
Q( x1 , x2 , x3 , x4 , x5 , x6 , x7 , x8 )
D f P  D13  D346  D24  D25  D67  D568
W346
W6
x \ x
Q25 ( x2 , x5 )Q24 ( x2 , x4 )Q13 ( x1 , x3 )

Q3 ( x3 )Q2 ( x2 )
W24
W13
 x

Q ( x )   Q ( x ) : Marginal Probabilit y of Q ( x )
Q568 ( x5 , x6 , x8 )Q346 ( x3 , x4 , x5 )Q67 ( x6 , x7 )

Q6 ( x6 ) 2 Q5 ( x5 )Q4 ( x4 )
X2
X6
W6
W568
X5
X5
X8
5
クラスター変分法




{P |   C}  arg minD[Q | P] Q ( x )   Q ( x ),  Q ( x )  1
{Q | C } 
x \ x
x



DQ P   DQ13 | W13   DQ346 | W346 
 DQ24 | W24   DQ25 | W25 
 DQ67 | W67   DQ568 | W568 
X1
W13
X4
X3
X3
 DQ3 | W3   DQ4 | W4 
X2
W2
X4
X3
W3
X2
W24
W346
 DQ5 | W5   2 DQ6 | W6   ln Z
X5
W5
X6
X7
X6
W25
W4
X4
X6
X2
X6
W6
W568
X5
X5
X8
Q2 ( x2 )   Q24 ( x2 , x4 )   Q25 ( x2 , x5 ),
x4
x5
Q3 ( x3 )   Q13 ( x1 , x3 )   Q346 ( x3 , x4 , x6 ), 
x1
x4
x6
6
確率伝搬法
Kullback-Leibler Divergence の極値条件
 W
346
m6346 ( x6 ) 
x3
( x3 , x4 , x6 )m313 ( x3 )m424 ( x4 ) 
x4
 W
346
x3
x4
( x3 , x4 , x6 )m313 ( x3 )m424 ( x4 ) 
x6
X1
X2
m313 ( x3 )
m424 ( x4 )
X3
X4
m6346 ( x6 )
X6
Message Passing Algorithm
7
確率伝搬法
Message を用いた周辺確率分布の近似表式
W346 ( x3 , x4 , x6 )m313 ( x3 )m424 ( x4 ) 


 m667 ( x6 )m6568 ( x6 ) 

P346 ( x3 , x4 , x6 ) 
W346 ( x3 , x4 , x6 )m313 ( x3 )m424 ( x4 ) 



 m667 ( x6 )m6568 ( x6 ) 
x3 x 4 x 6 
X1
X2
m313 ( x3 )
X3
m667 ( x6 )
X7
W346
m424 ( x4 )
X4
X6
X5
X8
m6568 ( x6 )
8
線形応答定理
  ( j ) xi
xi x j  xi x j  lim 
 h j 0
hj
Covariantin P ( x )
~




~
 ( j ) xi   xi P ( j ) ( x )   xi P ( x )   xi Pi ( j ) ( xi )   xi Pi ( xi )
x
x
xi
xi







Deviationof Averageat Nodei with respect toExternalField at Node j
1
~( j)
P ( x )  ~ P( x ) exp( h j x j )
Z
xi x j   xi x j P( x)
x
xi   xi P( x)
x
9
数値実験
周辺確率分布
Pi ( xi )   P( x1 , x2 , x3 , x4 , x5 , x6 , x7 , x8 )
x\ xi
P3 (1)  0.9896 P3 (1)  0.0104
Cluster Variation
Method
P5 (1)  0.5500 P5 (1)  0.4500
P8 (1)  0.5607 P8 (1)  0.4393
P3 (1)  0.9896 P3 (1)  0.0104
P5 (1)  0.5500 P5 (1)  0.4500
Exact
P8 (1)  0.5640 P8 (1)  0.4360
X1
X2
W24
W13
X3
W3
W6
W67
X7
W346
X6
W25
X4
W4
W568
X5
W5
X8
10
数値実験
相関関数
xi x j   xi x j P( x )   xi x j Pij ( xi , x j )
x
xi
xj
x1x6  0.8544
x2 x6  0.0890
x2 x7  0.0828
x3 x8  0.1334
x1x6  0.8544
x2 x6  0.0890
x2 x7  0.0828
x3 x8  0.1402
Cluster Variation
Method
Exact
X1
X2
W24
W13
X3
W3
W6
W67
X7
W346
X6
W25
X4
W4
W568
X5
W5
X8
11
Concluding Remarks
Summary
•確率伝搬法とクラスター変分法の概説
•線形応答定理とクラスター変分法を用いた相関
関数計算アルゴリズムの提案
Future Problem
•最尤推定・ＥＭアルゴリズムをもちいたモデル
パラメータのデータからの学習
12