確率モデルによる画像処理技術入門

物理フラクチュオマティクス論
Physical Fluctuomatics
第11回確率推論におけるベイジアンネットと確率伝搬法
11th Bayesian network and belief propagation in
statistical inference
東北大学大学院情報科学研究科応用情報科学専攻
田中和之(Kazuyuki Tanaka)
[email protected]
http://www.smapip.is.tohoku.ac.jp/~kazu/
19 June, 2008
物理フラクチュオマティクス論(東北大)
1
今回の本講義の講義ノート
1. 田中和之編著: 数理科学臨時別冊 SCG ライブラリ「確率的情
報処理と統計力学 ---様々なアプローチとそのチュートリアル--」，pp.92-100，サイエンス社，2006．
2. 田中和之: ［チュートリアル講演］確率的情報処理と確率伝搬
アルゴリズムの基礎, 電子情報通信学会技術研究報告，
Vol.104, No.338, pp.25-32, October 2004.
3. 田中和之: ［チュートリアル講演］ベイジアンネットと確率推論 --変分原理からの再帰的確率推論アルゴリズムの解説---, 電
子情報通信学会技術研究報告, Vol.104, No.348, pp.35-42,
October 2004.
19 June, 2008
物理フラクチュオマティクス論(東北大)
2
ベイジアンネットと確率推論
ベイズの公式
確率モデル
グラフィカルモデル
確率推論
医療診断
故障診断
ベイジアンネット
不確実性を伴うデータに耐えうる推論システム
たくさんのノードが関連しあって集まっている．
計算困難を打破する高性能の近似アルゴリズムの必要性
19 June, 2008
物理フラクチュオマティクス論(東北大)
3
確率の知識（１）
事象Ａの起こる確率
Pr{A}
事象Aと事象Bの結合確率
PrA, B  PrA  B
条件付き確率と結合確率
PrA, B
PrB A 
PrA
 PrA, B  PrB APrA
19 June, 2008
物理フラクチュオマティクス論(東北大)
A
B
4
確率の知識（２）
事象 B の周辺確率
PrB   PrA, B, C, D
A
C
D
A
B
C
D
周辺化
19 June, 2008
物理フラクチュオマティクス論(東北大)
5
確率推論に使う数学
P rA, B, C  P rC A, BP rA, B
 P rC A, BP rB AP rA
 P rC BP rB AP rA
PrB A
PrC A, B PrC B
因果独立の仮定
19 June, 2008
A
P rA, C
P rA C 
P rC
B
 P rA, B, C
 B
C
物理フラクチュオマティクス論(東北大)
 P rA, B, C
A, B
6
簡単なベイジアンネットの例
問題
芝生がぬれているのは何故でしょうか？雨が降ったせいでしょうか？
それともスプリンクラーを動かしたせいでしょうか？

P rAR  T AW  T P rAS  T AW  T?

19 June, 2008
物理フラクチュオマティクス論(東北大)
7
簡単なベイジアンネットの例
P rAC , AS , AR , AW 
 P rAW AC , AS , AR P rAC , AS , AR 
 P rAW AC , AS , AR P rAR AC , AS P rAC , AS 
 P rAW AC , AS , AR P rAR AC , AS P rAS AC P rAC 
 P rAW AS , AR P rAR AC P rAS AC P rAC 
19 June, 2008
物理フラクチュオマティクス論(東北大)
8
簡単なベイジアンネットの例
P rAR  T , AW  T
P rAR  T AW  T 
P rAW  T
P rAS  T , AW  T
P rAS  T AW  T 
P rAW  T
19 June, 2008
物理フラクチュオマティクス論(東北大)
9
簡単なベイジアンネットの例
P rAR  T, AW  T 
P rAS  T, AW  T 
PrAW  T 
19 June, 2008

 P rAC , AS , AR  T, AW  T  0.4581

 P rAC , AS  T, AR , AW  T  0.2781
AC  T,F AS  T,F
AC  T,F AR  T,F
   PrA , A , A
AC T,F AS T,F AR T,F
C
S
R
, AW  T  0.6471
物理フラクチュオマティクス論(東北大)
10
簡単なベイジアンネットの例
P rAR  T AW  T 
P rAR  T , AW  T 0.4581

 0.7079
P rAW  T
0.6471
PrAS  T AW  T 
PrAS  T , AW  T 0.2781

 0.4298
PrAW  T
0.6471
回答：芝生がぬれているのは雨が降ったせいだと考えられます．
19 June, 2008
物理フラクチュオマティクス論(東北大)
11
ベイジアンネットと物理モデル（Ⅰ）
PrA1  a1, A2  a2   W a1, a2 
A1
一言でいえば公式
A2
a1  1, a2  1
z=exp(ln z) を使うということ．
PrA1  a1 , A2  a2   explnPrA1  a1 , A2  a2 
 expF  h1a1  h2 a2  J12 a1a2 
具体的には
W (1,1)  expF  h1  h2  J12 
W (1,1)  expF  h1  h2  J12 
を満たすように係数を決めると確かめられる．
ベイジアンネットで扱われるグラフィカルモデルは多体力
を持つ磁性体の物理モデルに対応づけられる．
19 June, 2008
物理フラクチュオマティクス論(東北大)
12
ベイジアンネットと物理モデル（Ⅱ）
PrA1  a1 , A2  a2 , A3  a3   W12 a1 , a2 W23 a2 , a3 
a1  1, a2  1, a3  1
P rA1  a1 , A2  a 2 , A3  a3 
A1
A2

 expF
 exp F12  h112 a1  h212 a 2  J 12 a1 a 2
23
A3

 h223 a 2  h323 a3  J 23 a 2 a3

 expF  h1 a1  h2 a 2  h3 a3  J 12 a1 a 2  J 23 a 2 a3 
ベイジアンネットで扱われるグラフィカルモデルは多体力
を持つ磁性体の物理モデルに対応づけられる．
19 June, 2008
物理フラクチュオマティクス論(東北大)
13
ベイジアンネットと物理モデル（Ⅲ）
PrA1  a1, A2  a2 , A3  a3  W a1, a2 , a3 
A2
A1
A3
a1  1, a2  1, a3  1
P rA1  a1 , A2  a2 , A3  a3 
 F  h1a1  h2 a2  h3 a3  J12 a1a2 

 exp
  J 23 a2 a3  J13 a1a3  Ka1a2 a3 
ベイジアンネットで扱われるグラフィカルモデルは多体力
を持つ磁性体の物理モデルに対応づけられる．
19 June, 2008
物理フラクチュオマティクス論(東北大)
14
ベイジアンネットと物理モデル（Ⅳ）
AC
AR
AS
AW
ベイジアンネットで扱われるグラフィカルモデルは多体力
を持つ磁性体の物理モデルに対応づけられる．
P rAC  aC , AS  aS , AR  aR , AW  aW 
 F  hC aC  hS aS  hR aR  hW aW  J CSaC aS  J CRaC aR 

 exp
  J SR aS aR  J SW aS aW  J RW aR aW  KRSW aR aS aW 
19 June, 2008
物理フラクチュオマティクス論(東北大)
15
より複雑なベイジアンネット
P1 ( x1 )   Px1, x2 , x3 ,, xL 
x2
x3
xL
定義に基づいて厳密に計算す
るプログラム
xi  T rue or False
P  x1   0;
for(x2  T or F){
for(x2  T or F){

for(xL  T or F){
ノード数とともに指数関数的
に計算量が増加 OeL 
2L1  expL 1ln 2
P  x1   P  x1   P  x1 , x2 ,  , xL ;
}
このプログラムでは
 L=10個のノードで1秒かかるとしたら
} L=20個で約17分，L=30個で約12日，
}
19 June, 2008
L 重の for 文
L=40個で約34年かかる．
物理フラクチュオマティクス論(東北大)
16
確率伝搬法
1. 閉路を持たないグラフ上の確率モデルに対して厳密な結果を与える．
2. 閉路を持つグラフ上の確率モデルでは近似アルゴリズムとなる．
P rX   P rX 8 X 5 , X 6 P rX 7 X 6 


 P r X 6 X 3 , X 4 P rX 5 X 2 
 P rX 4 X 2 P rX 3 X 1
 P rX 1P rX 2 
８個程度のノードの簡単ではあるが
閉路を含むグラフ上の確率モデルで
確率伝搬法の構造を説明し，得られ
る近似結果と厳密な結果を比較して
みる．
19 June, 2008
物理フラクチュオマティクス論(東北大)
17
閉路を持つグラフ上の確率モデルの
結合確率
PrX 1  x1 , X 2  x2 ,, X 8  x8 
 W568 (x5 , x6 , x8 )W346 ( x3 , x4 , x5 )W67 ( x6 , x7 )
W25 ( x2 , x5 )W24 ( x2 , x4 )W13 ( x1 , x3 )
X1
X2
W24
W13
有向
グラフ
X3
W346
W67
X7
19 June, 2008
W25
X4
物理フラクチュオマティクス論(東北大)
X6
無向
グラフ
W568
X5
X8
18
周辺確率分布
Pi ( X i )

X1
X , X , X , X , X , X , X , X 
 Pr

1
2
3
4
5
6
7
8

PrX , X , X , X , X , X , X , X 

 
1
2
3
4
5
6
7
8
W24
W13
X3
X \ Xi
Pij ( X i , X j )
X2
W25
X4
W346
W67
X7
X6
W568
X5
X8
X \ Xi ,X j
Pijk ( X i , X j , X k ) 
PrX , X



1
2
, X 3, X 4 , X 5 , X 6 , X 7 , X 8
X \ Xi ,X j ,Xk
19 June, 2008
物理フラクチュオマティクス論(東北大)
19
この場合の確率伝搬法の基本方針
P6 x6    P346 x3 , x4 , x6 
x3
X1
M 6346 ( X 6 )
X3
M 667 ( X 6 )
X7
X2
M 313 ( X 3 )
X4
X3
X6
X5
X8
 M 6568 x6 M 667 x6 
W346
M 667 ( X 6 )
M 6568 ( X 6 )
1
P6 x6  
M 6346 x6 
Z6
19 June, 2008
x4
X7
P346 x3 , x4 , x6  
M 424 ( X 4 )
X4
X6
X5
X8
M 6568 ( X 6 )
1
W346 x3 , x4 , x6 
Z 346
 M 313 x3 M 424 x4 
 M 6568 x6 M 667 x6 
物理フラクチュオマティクス論(東北大)
20
確率伝搬法の固定点方程式
 W
346
M 6346 ( x6 ) 
x3
( x3 , x4 , x6 ) M 313 ( x3 ) M 424 ( x4 ) 
x4
 W
346
x3
x4
( x3 , x4 , x6 ) M 313 ( x3 ) M 424 ( x4 ) 
x6
A2
A1
M 313 ( X 3 )
X1
W24
W13
M 424 ( X 4 )
A3
X2
X3
A4
W346
M 6346 ( X 6 )
W67
A6
確率伝搬アルゴリズム
19 June, 2008
物理フラクチュオマティクス論(東北大)
W25
X4
X7
X6
W568
X5
X8
21
Message を用いた周辺確率分布の近似表式
W346 ( X 3 , X 4 , X 6 ) M 313 ( X 3 ) M 424 ( X 4 ) 


 M 667 ( X 6 ) M 6568 ( X 6 ) 

P346 ( X 3 , X 4 , X 6 ) 
W346 ( X 3 , X 4 , X 6 ) M 313 ( X 3 ) M 424 ( X 4 ) 



 M 667 ( X 6 ) M 6568 ( X 6 ) 
X3 X4 X6 
X1
M 313 ( X 3 )
X2
X3
M 667 ( X 6 )
X7
19 June, 2008
W346
M 424 ( X 4 )
X4
X6
X5
X8
M 6568 ( X 6 )
物理フラクチュオマティクス論(東北大)
22
Message Passing Algorithm
 W
346
M 6346 ( X 6 ) 
( X 3 , X 4 , X 6 ) M 313 ( X 3 ) M 424 ( X 4 ) 
X3 X4
 W
346
( X 3 , X 4 , X 6 ) M 313 ( X 3 ) M 424 ( X 4 ) 
X3 X4 X6
X1
X2
M 313 ( X 3 )
M 424 ( X 4 )
X3
X4
M 6346 ( X 6 )
X2
W24
W13
X3
W3
W6
X6
W67
Message Passing Algorithm
19 June, 2008
X1
物理フラクチュオマティクス論(東北大)
X7
W346
X6
W25
X4
W4
W568
X5
W5
X8
23
固定点方程式と反復法
固定点方程式
反復法
繰り返し出力を入力に入れることにより，
固定点方程式の解が数値的に得られる．
 
 
 

 
M1   M 0

 
M 2   M1

 
M3   M2

19 June, 2008
 
*  *
M  M
yx
y
M1
0
y  (x)
M * M1
物理フラクチュオマティクス論(東北大)
M0
x
24
数値実験
P8 (1)  0.5607 P8 (0)  0.4393
Belief Propagation
P58 (1,1)  0.4736 P58 (1,0)  0.0764
P58 (0,1)  0.0871 P58 (0,0)  0.3629
P8 (1)  0.5640 P8 (0)  0.4360
P58 (1,1)  0.4776 P58 (1,0)  0.0724
Exact
P58 (0,1)  0.0864 P58 (0,0)  0.3636
P8 ( x8 ) 
X1
P( x , x , x , x , x , x , x , x )

 
1
2
3
4
5
6
7
W24
W13
X3
8
x \ x8
P58 ( x5 , x8 ) 
P( x , x , x , x , x , x , x , x )



1
2
3
4
5
6
7
x \ x5 , x8
19 June, 2008
物理フラクチュオマティクス論(東北大)
X2
8
W67
X7
W346
X6
W25
X4
W568
X5
X8
25
数値実験
確率伝搬法


Pr X Bronchitis  PresentX Dyspnea  Present
PrX Bronchitis  Present, X Dyspnea  Present 0.3629


 0.8261
PrX Dyspnea  Present
0.4393
X1
X2
W24
W13
X3
W3
W6
W67
X7
19 June, 2008
物理フラクチュオマティクス論(東北大)
W346
X6
W25
X4
W4
W568
X5
W5
X8
26
線形応答理論
（人為的に小さなゆらぎを与えてその応答を見ることで詳細を知ることができる．）
X2
X1
Pij (m, n)  Pi (m) Pj (n)
  Pj (n) 

 lim

hi 0
h
i


X3
(i )
X4
X6
x  {xi | i  Ω}
X7
X5
X8
~
~
 Pj (n)  Pj ( n)  Pj ( n)    n, x j P( x )    n, x j P( x )

xx

(i )
Dev iationof Av erageat Node j with respect to ExternalField at Node i

1
~
P ( x )  ~ P ( x )exp hi xi , m
Z
19 June, 2008
物理フラクチュオマティクス論(東北大)

27
数値実験


P r X Tuberculos is  Present X Dyspnea  Present

P rX Tuberculos is  Present, X Dyspnea  Present
P rX Dyspnea  Present
0.0082

 0.0187
0.4393
X1
X2
W24
W13
X3
W3
W6
W67
X7
19 June, 2008
物理フラクチュオマティクス論(東北大)
W346
X6
W25
X4
W4
W568
X5
W5
X8
28
確率推論のまとめ
ベイジアンネットと確率伝搬法を用いた確率推論の概説
線形応答定理を用いた高次の推論システムへの発展
ベイジアンネットの最近の動向
繁桝算男, 本村陽一, 植野真臣：ベイジアンネットワーク概説，培風館，2006．
本村陽一, 岩崎弘利：ベイジアンネットワーク技術．東京電機大出版，2006．
Microsoft社，Intel社，Nokia社などが実用化への研究
http://excalibur.brc.uconn.edu/~baynet/
http://www.research.microsoft.com/research/dtg/
19 June, 2008
物理フラクチュオマティクス論(東北大)
29

Download Report