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

物理フラクチュオマティクス論
Physical Fluctuomatics
第9回確率伝搬法
9th Belief propagation
東北大学大学院情報科学研究科応用情報科学専攻
田中和之(Kazuyuki Tanaka)
[email protected]
http://www.smapip.is.tohoku.ac.jp/~kazu/
11 June, 2009
物理フラクチュオマティクス論(東北大)
1
今回の講義の講義ノート
田中和之著：確率モデルによる画像処理技術入門，
第8章，森北出版，2006．
参考文献
J. Pearl: Probabilistic Reasoning in Intelligent Systems:
Networks of Plausible Inference, Morgan Kaufmann,
1988.
汪金芳, 田栗正章, 手塚集, 樺島祥介, 上田修功: 統計
科学のフロンティア/計算統計 I ---確率計算の新しい手
法, 岩波書店, 2003.
11 June, 2009
物理フラクチュオマティクス論(東北大)
2
計算困難のポイントは何か
2L 通りの和が計算できるか？


x1  T, F x 2  T, F

 f x1 , x2 ,, x L 
a  0;
for(x1  T or F){
for(x2  T or F){

for(x L  T or F){
x L  T, F
a  a  f x1 , x2 ,, x L ;
このプログラムでは
L=10個のノードで1秒かかるとしたら
L=20個で約17分，
L=30個で約12日，
L=40個で約34年かかる．
厳密に計算するのは一部の特殊な例を
除いて難しい．
マルコフ連鎖モンテカルロ法
確率伝搬法
11 June, 2009
}

}
}
L 重ループ
今回
次回
物理フラクチュオマティクス論(東北大)
3
確率モデルと確率伝搬法
ベイジアンネットワーク
ベイズの公式
確率モデル
確率的情報処理
確率伝搬法
（Belief Propagation）
J. Pearl: Probabilistic Reasoning in Intelligent Systems:
Networks of Plausible Inference (Morgan Kaufmann, 1988).
C. Berrou and A. Glavieux: Near optimum error correcting
coding and decoding: Turbo-codes, IEEE Trans. Comm., 44
(1996).
11 June, 2009
物理フラクチュオマティクス論(東北大)
4
確率伝搬法の定式化
確率伝搬法と平均場理論の類似性の指摘
Y. Kabashima and D. Saad, Belief propagation vs. TAP for decoding
corrupted messages, Europhys. Lett. 44 (1998).
M. Opper and D. Saad (eds), Advanced Mean Field Methods
---Theory and Practice (MIT Press, 2001).
一般化された確率伝搬法の提案
S. Yedidia, W. T. Freeman and Y. Weiss: Constructing free-energy
approximations and generalized belief propagation algorithms,
IEEE Transactions on Information Theory, 51 (2005).

確率伝搬法の情報幾何的解釈
S. Ikeda, T. Tanaka and S. Amari: Stochastic reasoning, free energy,
and information geometry, Neural Computation, 16 (2004).
11 June, 2009
物理フラクチュオマティクス論(東北大)
5
統計物理学による確率伝搬法の一般化
一般化された確率伝搬法
J. S. Yedidia, W. T. Freeman and Y. Weiss: Constructing free-energy
approximations and generalized belief propagation algorithms,
IEEE Transactions on Information Theory, 51 (2005).
クラスター変分法という統計物理学の手法
がその一般化の鍵
R. Kikuchi: A theory of cooperative phenomena, Phys. Rev., 81
(1951).
T. Morita: Cluster variation method of cooperative phenomena and
its generalization I, J. Phys. Soc. Jpn, 12 (1957).
11 June, 2009
物理フラクチュオマティクス論(東北大)
6
確率伝搬法の統計物理学的位置付け
木構造を持つグラフィカルモデルではベーテ近似
は転送行列法と等価である．
閉路を持つグラフィカルモデル上のベイジアンネットでの確率伝
搬法はベーテ近似またはその拡張版であるクラスター変分法に
等価である（Yedidia, Weiss and Freeman, NIPS2000）．
転送行列法
||（木構造）
もともとの確率伝搬法
ベーテ近似
クラスター変分法
（菊池近似）
一般化された確率伝搬法
11 June, 2009
物理フラクチュオマティクス論(東北大)
7
一般化された確率伝搬法の応用範囲
Image Processing
K. Tanaka: Statistical-mechanical approach to image processing (Topical Review), J.
Phys. A, 35 (2002).
A. S. Willsky: Multiresolution Markov Models for Signal and Image Processing,
Proceedings of IEEE, 90 (2002).
Low Density Parity Check Codes
Y. Kabashima and D. Saad: Statistical mechanics of low-density parity-check codes
(Topical Review), J. Phys. A, 37 (2004).
S. Ikeda, T. Tanaka and S. Amari: Information geometry of turbo and low-density paritycheck codes, IEEE Transactions on Information Theory, 50 (2004).
CDMA Multiuser Detection Algorithm
Y. Kabashima: A CDMA multiuser detection algorithm on the basis of belief propagation,
J. Phys. A, 36 (2003).
T. Tanaka and M. Okada: Approximate Belief propagation, density evolution, and
statistical neurodynamics for CDMA multiuser detection, IEEE Transactions on
Information Theory, 51 (2005).
Satisfability Problem
O. C. Martin, R. Monasson, R. Zecchina: Statistical mechanics methods and phase
transitions in optimization problems, Theoretical Computer Science, 265 (2001).
M. Mezard, G. Parisi, R. Zecchina: Analytic and algorithmic solution of random
satisfability problems, Science, 297 (2002).
11 June, 2009
物理フラクチュオマティクス論(東北大)
8
確率的情報処理における計算困難の打破の戦略
P1 x1  
    Px , x ,, x 
x2 T,F x3 T,F
xL T,F
1
2
L
を厳密に計算するのは一部の特殊な例を除いて難しい．
一部の特殊な例とは何か？
一部の特殊な例に適用できるアルゴリズムを一般
の場合に近似アルゴリズムとして適用できるか．
→ アルゴリズム化できるか？動くか？
精度はどの程度か？
11 June, 2009
物理フラクチュオマティクス論(東北大)
9
確率伝搬法 (Belief Propagation)
閉路のないグラフ上の確率モデル
どの枝もそれぞれで独立に和がとれる．
 Aa, x B(b, x)C (c, x) D(d , x)
a
b
x
a b c d





   A(a, x)   B(b, x)   C (c, x)   D(d , x) 





a
b
c
d





c
d
閉路のあるグラフ上の確率モデル
それぞれで独立に和をとることが困難．
a
b
d
x c
11 June, 2009
 W a, b, c, d , x 
a b c d
物理フラクチュオマティクス論(東北大)
10
確率伝搬法 (Belief Propagation)
閉路のないグラフ上の確率モデル
Pa, b, c, d , x1 , x2 
 WA a, x1 WB b, x1 W12 x1 , x2 WC c, x2 W d , x2 
a
4b
3
2
1
6
d
11 June, 2009
5
x3  a
x5  c
x4  b
x6  d
c
物理フラクチュオマティクス論(東北大)
11
確率伝搬法 (Belief Propagation)
閉路のないグラフ上の確率モデル
WA a, x1 
a
WB b, x1 
a
3
1
6
d
WC c, x2 
11 June, 2009
4b
1 1
2
W12 x1 , x2 
2
2
4b
3
2
5
c
1
6
d
5
c
Pa, b, c, d , x1 , x2 
 WA a, x1 WB b, x1 
WD d , x2   W x , x W c, x W d , x 
12 1
2
C
2
2
物理フラクチュオマティクス論(東北大)
12
閉路のないグラフ上の確率モデル
P12 x1 , x2  
 Pa, b, c, d , x , x 
1
2
a,b,c,d
 M 31 x1 M 41 x1 W12 x1 , x2 M 62 x2 M 52 x2 
M 31 x1   WA a, x1  M 41 x1   WB b, x1 
a
a
4 b M 52 x2   WC c, x2  M 62 x2   WD d , x2 
3
2
6
d
11 June, 2009
b
c
1
5
c
d
ノード１と２の周辺確率分布は
それぞれ隣接するノードから伝搬され
るメッセージの積により表される．
物理フラクチュオマティクス論(東北大)
13
確率伝搬法 (Belief Propagation)
閉路のないグラフ上の確率モデル
M 12 x2   W12 x1 , x2 WA a, x1 WB b, x1 
x1
a
b
 W12 x1 , x2 M 31 x1 M 41 x1 
x1
a
4b
3
2
1
6
d
11 June, 2009
5
c
ノード１から隣接ノード２に伝搬するメッセージは（ノー
ド２を除く）ノード１の隣接ノードからノード１に伝搬され
るメッセージの積により表される．
 
  
M  M
メッセージに対する固定点方程式
(Message Passing Rule)
物理フラクチュオマティクス論(東北大)
14
転送行列法＝確率伝搬法（1）
1次元鎖
 
1 N 1
P r X  x  Wi, i 1 xi , xi 1 
Z i 1


 k 1


Lk 1 k xk     Wi, i 1 xi , xi 1 


x1 x 2
x k 1  i 1

 N 1


Rk 1 k xk       Wi, i 1 xi , xi 1 


x k 1 x k  2
x N 1  i  k

11 June, 2009
物理フラクチュオマティクス論(東北大)
Lk 1k xk 
k
Rk 1k xk 
k
15
転送行列法＝確率伝搬法（2）
パスはひ
とつ
Lk 1k xk  Lk k 1 xk 1 
漸化式
Lk  k 1 xk 1    Lk 1 k xk Wk , k 1 xk , xk 1 
k
xk
k 1
Rk  k 1 xk 1   Wk 1, k xk 1 , xk Rk 1 k xk 
k 1 k
Rk k 1 xk 1  Rk 1k xk 
xk
P rX m  xm    
x1 x 2
  

 
 Pr X  x
x m 1 x m 1 x m  2

x N 1
Lm 1 m x m Rm 1 m x m 

 Lm 1 m xm Rm 1 m xm 
xm
11 June, 2009
物理フラクチュオマティクス論(東北大)
16
閉路のないグラフ上の確率伝搬法
 
1 N 1
P r X  x  Wi, i 1 xi , xi 1 
Z i 1


X1
X2
X3
X k 1
X k 3
閉路が無い
ことが重要!!
Xk
X k 1
X k 2
同じノードは２度通らない
 k


M k  k 1 xk 1     Wi, i 1 xi , xi 1 


x1 x 2
x k  i 1

  M k 1 k xk M k  2  k xk M k  3 k xk Wk , k 1 xk , xk 1 
xk
11 June, 2009
物理フラクチュオマティクス論(東北大)
17
確率伝搬法
閉路のあるグラフ上の確率モデル

Px   Px1 , x2 ,, x L  
  ij xi , x j 
ijB
B：すべてのリンクの集合
P1 x1      P x1 , x2 , x3 ,  , xL 
x2
３
４
１
２
x3
xL
M 21  x1 M 31  x1 M 41  x1 M 51  x1 

 M 21 z1 M 31 z1 M 41 z1 M 51 z1 
z1
５
11 June, 2009
物理フラクチュオマティクス論(東北大)
18
閉路のあるグラフ上の確率モデル
M 1 2  x 2  
W12 z1 , x2 M 31 z1 M 4 1 z1 M 5 1 z1 
z1
W12 z1 , z 2 M 31 z1 M 4 1 z1 M 5 1 z1 
z1 z 2
３
４
１
５
２
閉路のあるグラフ上でも局所的な
構造だけに着目してアルゴリムを
構成することは可能．
ただし，得られる結果は厳密では
なく近似アルゴリズム
 
  
M  M
11 June, 2009
メッセージに対する固
定点方程式
物理フラクチュオマティクス論(東北大)
19
固定点方程式と反復法
固定点方程式
反復法
 
*  *
M  M
繰り返し出力を入力に入れることにより，
固定点方程式の解が数値的に得られる．
 
 
 

 
M1   M 0

 
M 2   M1

 
M3   M2
yx
y
M1
0
y  (x)
M * M1
M0
x

11 June, 2009
物理フラクチュオマティクス論(東北大)
20
確率伝搬法の情報論的解釈(1)
Kullback-Leibler Divergence
 Q x  
  0
DQ P   Q( x) ln
x
 P x  

 Q x   0,


x Q( x)  1
1
Q x   P x   D Q P  0 Px1 , x2 ,, xL   Z Wij xi , x j 
ijN
 
D[Q | P]   Q( x )  ln Wij xi , x j    Q( x ) ln Q x   ln Z
x
ijN


x
F [Q ]
 F [Q]  ln Z
Free Energy
Z  Wij xi , x j 
x ijN


minF[Q]  Q x   1  F[ P]   ln Z
Q
x


11 June, 2009
物理フラクチュオマティクス論(東北大)
21
確率伝搬法の情報論的解釈（２）

 Q x  
  0
DQ P   Q( x) ln
x
 P x  
1
P x   Wij xi , x j
Z ijB

Free Energy
KL Divergence
DQ P  FQ lnZ 


F Q   Q( x )  ln Wij xi , x j   Q( x ) ln Q x 
x
ijB
x




     Q( x )  ln Wij xi , x j   Q( x ) ln Q x 
Qij ( xi , x j )
ijB x i x j  x \ x i , x j  
x

Q( x )    Qij xi , x j ln Wij xi , x j   Q( x ) ln Q x 
x \xi , x j 
ijB x i x j
x


11 June, 2009



物理フラクチュオマティクス論(東北大)


22
確率伝搬法の情報論的解釈（３）
KL Divergence
F Q 
Free Energy
DQ P  FQ lnZ 
  Qij  ,  ln Wij  ,  
ijB  
  Q( x ) ln Q x 
x



1
P x   Wij xi , x j
Z ijB
Qi ( xi )   Q( x)
x\ xi
 Qij  ,  ln Wij  ,  
Qij ( xi , x j ) 
Q( x )

 
x \ xi , x j
ijB  

  Qi  ln Qi  
i 
Bethe Free
Energy


    Qij  ,   ln Qij  ,     Qi   ln Qi     Q j   ln Q j  


ijB   



11 June, 2009
物理フラクチュオマティクス論(東北大)
23

確率伝搬法の情報論的解釈（４）


DQ P  FBethe Qi , Qij   ln Z

   Qij  ,  lnWij  ,      Qi  ln Qi  
FBethe Qi , Qij 
ijB  
i 
arg min DQ P  arg min F


    Qij  ,   ln Qij  ,     Qi   ln Qi     Q j   ln Q j  


ijB   



Q
Q


arg min DQ P  arg min FBethe Qi , Qij 
Qi ,Qij 
Q
Q     Q  ,    1


 
i
11 June, 2009
ij
Qi     Qij  ,  
物理フラクチュオマティクス論(東北大)

24
確率伝搬法の情報論的解釈（５）


arg min FBethe Qi , Qij  Qi     Qij  ,  ,  Qi     Qij  ,    1
Qi ,Qij  



 


Lagrange Multipliers to ensure the constraints



LBethe Qi , Qij  FBethe Qi , Qij




    i, j   Qi     Qij  ,  


i jBi 







   i   Qi    1    ij   Qij  ,    1




i  
 ijB   

11 June, 2009
物理フラクチュオマティクス論(東北大)
25
確率伝搬法の情報論的解釈（６）



LBethe Qi , Qij  FBethe Qi , Qij     i, j   Qi     Qij  ,  


i jBi 














   i  Qi    1    ij  Qij  ,    1




i  
 ijB   

   Qij  ,   ln Wij  ,      Qi   ln Qi  
ijB  
i 



   Qij  ,   ln Qij  ,     Qi   ln Qi     Q j   ln Q j  


ijB   














    i, j   Qi     Qij  ,      i  Qi    1    ij  Qij  ,    1






i jBi 


 i  
 ijB   

Extremum Condition



LBethe Qi , Qij   0
Qi xi 
11 June, 2009



LBethe Qi , Qij   0
Qij xi , x j 
物理フラクチュオマティクス論(東北大)
26
確率伝搬法の情報論的解釈（７）



LBethe Qi , Qij   0
Qi xi 
M 31
4
M 41

3
1
M 31
M 21
2
4
M 41
3
1
8M
W12
M 51
M 51
5


LBethe Qi , Qij   0
Qij xi , x j 
2
Extremum
Condition
82
M 72
7
M 62
5
6
Q1 x1  
1
1
M 21 x1 M 31 x1  Q12 x1 , x2  
M 31 x1 M 41 x1 M 51 x1 
Z1
Z12
 M 41 x1 M 51 x1 
 W12 x1 , x2 M 62 x2 M 72 x2 M 82 x2 
11 June, 2009
物理フラクチュオマティクス論(東北大)
27
確率伝搬法の情報論的解釈（８）
Q1     Q12  ,  

M 12  
  W12  ,  M 31  

 M 41  M 51  
Message Update Rule
M 31
4
M 41
3
M 31
M 21
1
2
4
M 41
3
1
8M
W12
M 51
M 51
5
2
82
M 72
7
M 62
5
6
Q1 x1  
1
1
M 21 x1 M 31 x1  Q12 x1 , x2  
M 31 x1 M 41 x1 M 51 x1 
Z1
Z12
 M 41 x1 M 51 x1 
 W12 x1 , x2 M 62 x2 M 72 x2 M 82 x2 
11 June, 2009
物理フラクチュオマティクス論(東北大)
28
確率伝搬法の情報論的解釈（９）
M 12   
W12  ,  M 31  M 41  M 51  

W12  ,  M 31  M 41  M 51  


Message Passing Rule of
Belief Propagation
M 31
4
M 41
M12
2
1
2
5
6
7
3
M 51
5
これはクラスター変分法のなかでも
ベーテ近似になる．
11 June, 2009

8
a2
4
3
1
3
=
4
物理フラクチュオマティクス論(東北大)
1
2
5
29
イジング模型の確率変数の期待値
1 N N


exp
( a x, y a x 1, y  a x , y a x , y 1 ) 


T

x

1
y

1



P(a ) 
1 N N



exp
(
a
a

a
a
)

x , y x , y 1 
 T   x, y x 1, y

a
x 1 y 1


(a)
(b)
(c)
(d)

lim  a x, y P (a )
N   a
平均場近似（ワイス近似）
ベーテ近似
クラスター変分法（菊池近似）
厳密解（L. Onsager）
a x, y  1
T
11 June, 2009
物理フラクチュオマティクス論(東北大)
30
本日のまとめ
確率伝搬法
転送行列法
ベーテ近似・クラスター変分法
反復法
次回
第11回物理モデルから見た確率的画像処理
第12回物理モデルから見た確率推論 ---ベイジアンネット
11 June, 2009
物理フラクチュオマティクス論(東北大)
31
演習問題１０-１
確率変数 a, b, c, d, x, y の確率分布 P(a,b,c,d,x,y) を考える．
Pa,b,c,d,x, x  WA a, xWB b, xWXY x, y WC c, y WD d , y 
確率変数 x, y の周辺確率分布 PXY(x,y) が次のように与え
られることを示せ．
PXY x, y    Pa,b,c,d,x, y 
a b c d
 M A  X x M B  X x W XY x, y M C  2  y M D  2  y 
M A  X  x    W A a, x 
M B  X  x    W B b, x 
a
M C Y  y    WC c, y 
c
11 June, 2009
b
M D Y  y    W D d , y 
d
物理フラクチュオマティクス論(東北大)
32
演習問題１０-２
以下の形に与えられる２つの周辺確率分布
Q1 x1  
1
M 2 1 x1 M 31 x1 M 4 1 x1 M 5 1 x1 
Z1
Q12 x1 , x2  
1
M 31 x1 M 4 1 x1 M 5 1 x1 W12 x1 , x2 M 6  2 x2 M 7  2 x2 M 8  2 x2 
Z12

を Q1 x1    Q12 x1 , x2 に代入することにより次の等式
x2
を導出せよ．
Z1
M 1 2 x 2  
W12  x1 , x 2 M 3 1  x1 M 4 1 x1 M 5 1 x1 

Z12 x
1
11 June, 2009
物理フラクチュオマティクス論(東北大)
33

Download Report