Kazuyuki Tanaka ECEI Experiment D (2013 Part 1)

電気・通信・電子・情報工学実験D
確率的情報処理の基礎技術
Part 3 (2013年4月)
本実験DのWebpage:
http://www.smapip.is.tohoku.ac.jp/~kazu/ECEI-ExperimentD/2013/
東北大学大学院情報科学研究科
田中和之
[email protected]
http://www.smapip.is.tohoku.ac.jp/~kazu/
April, 2013
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 3]
1
本講義の参考文献
田中和之著: 確率モデルによる画像処理技術入門, 森北出版, 2006.
田中和之著: ベイジアンネットワークの統計的推論の数理, コロナ社, 2009.
田中和之編著: 臨時別冊・数理科学SGCライブラリ「確率的情報処理と統計
力学 ---様々なアプローチとそのチュートリアル」, サイエンス社，2006.
安田宗樹, 片岡駿，田中和之共著 (分担執筆): ---CVIMチュートリアルシリー
ズ--- コンピュータビジョン最先端ガイド3(八木康史，斎藤英雄編), 第6章．大
規模確率場と確率的画像処理の深化と展開，pp.137-179, アドコム・メディア
株式会社, December 2010.
Kazuyuki Tanaka: Statistical-mechanical approach to image processing
(Topical Review), Journal of Physics A: Mathematical and General, vol.35,
no.37, pp.R81-R150, 2002.
C. M. Bishop: Pattern Recognition and Machine Intelligence, Springer, 2007.
M. Opper and D. Saad: Advanced Mean Field Method, MIT Press, 2001.
H. Nishimori: Statistical Physics of Spin Glasses and Information Processing, --An Introduction---, Oxford University Press, 2001.
M. J. Wainwright and M. Jordan: Graphical Models, Exponential Families, and
Variational Inference (Foundations and Trends® in Machine Learning), Now
Publishers, 2008.
M. Mezard and A. Montanari: Information, Physics, and Computation, Oxford
University Press, 2009.
April, 2013
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 3]
2
Contents
1.
2.
3.
4.
5.
6.
April, 2013
序論：確率的情報処理とベイジアンネットワーク
確率の基礎知識
確率的計算技法の基礎
---マルコフ連鎖モンテカルロ法と確率伝搬法--確率的画像処理とベイジアンネットワーク ---マルコ
フ確率場と確率伝搬法--確率推論とベイジアンネットワーク---グラフィカルモ
デルと確率伝搬法--まとめ
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 3]
3
計算困難のポイントは何か
a  0;
for(x1  0,1){
2L 通りの和が計算できるか？
    f x , x ,, x 
x1 0,1 x2 0,1
xL 0,1
1
2
for(x2  0,1){

for(xL  0,1){
L
a  a  f  x1 , x2 , , xL ;
このプログラムでは
L=10個のノードで1秒かかるとしたら
L=20個で約17分，
L=30個で約12日，
L=40個で約34年かかる．
厳密に計算するのは一部の特殊な例を
除いて難しい．
マルコフ連鎖モンテカルロ法
確率伝搬法
April, 2013
}

}
}
L 重ループ
今回
次回
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 3]
4
乱数による円周率の計算（モンテカルロ法）
1
n0 m0
nn+1
-1
区間[-1,1]において2個の
一様乱数a,bを発生
a2+b2≤1
No
緑の四角の枠の中に
ランダムに点をプロットし，
赤い円の内部の点の個数
をカウントする．
円周率
S  R 2
R 1
April, 2013
1
-1
Yes
mm+1
0
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 3]
 S
4m
n
試行回数 n が大きいほど
精度が上がる
5
乱数による円周率の計算（モンテカルロ法）
1
1個1個の点をランダムにプロットする
という試行を行った時の x 座標，y 座
標の平均 0, 分散は 1/2．
ランダムに n 個プロットした標本
平均は平均が 0, 分散が 1/2n
(中心極限定理)なので，その確
率密度関数の幅は 1/n1/2 で減少
する．
円周率の推定誤差は O(1/n1/2)
0
1
-1
緑の四角の枠の中に
ランダムに点を n 個プロットし，
赤い円の内部の点の個数 m を
カウントする．
円周率
S  R 2
R 1
April, 2013
-1
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 3]
 S
4m
n
試行回数 n が大きいほど
精度が上がる
6
積分の計算（モンテカルロ法）
1
n0 m0
I 
1 1

1 1
f ( x, y)dxdy
nn+1
-1
区間[-1,1]において2個の
一様乱数a,bを発生
April, 2013
4m
n
1
-1
緑の四角の枠の中に
ランダムに点をプロットし，
その点の被積分関数の
値を求める操作を繰り返す．
mm + f(a,b)
I
0
試行回数 n が大きいほど
精度が上がる
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 3]
推定誤差は O(1/n1/2)
積分が高次元でも同様
7
確率推論でよく必要となる計算
周辺確率
P1 x1  
    Px , x ,, x 
x2 0,1 x3 0,1
P{1,2} x1 , x2  
P{1,3} x1 , x3  
April, 2013
xL 0,1
1
2
L
    Px , x , x ,, x 
x3 0,1 x4 0,1
xL 0,1
1
2
3
L
    Px , x , x ,, x 
x2 0,1 x4 0,1
xL 0,1
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 3]
1
2
3
L
8
計算のポイントは
与えられた確率分布
P x   Px1 , x2 ,, xL 
に従うN個の独立なサンプル x を生成するアル
ゴリズムが作れるか?
但し，1個のサンプルを生成するための計算量は
L の多項式オーダーでなければならない．
April, 2013
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 3]
9
簡単な確率過程：マルコフ連鎖
推移確率 w(x|y)≥0 (x,y=0,1) が与えられたとき
 wz x   1
任意の P0(x) を初期値として
Pt ( x) 
1
 w( x | z ) Pt 1 ( z )
z 0
( x  0,1; t  1,2, )
z 0
 Pt (0)   w(0 | 0) w(0 | 1)  Pt 1 (0) 

  


 Pt (1)   w(1 | 0) w(1 | 1)  Pt 1 (1) 
推移確率行列
April, 2013
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 3]
10
簡単な確率過程：マルコフ連鎖
Pt ( x) 

1
 w( x | z[t  1])Pt 1 ( z[t  1])
z[t 1]  0
1

1

z[t 1]  0 z[t  2]  0
1

 w( x | z[t  1])w( z[t  1] | z[t  2]) w( z[1] | z[0])P0 ( z[0])
z[t 1]  0
 Pt (0) 
 P0 (0) 
t

  W 

 Pt (1) 
 P0 (1) 
 Pt (0) 
 1 0  1  P0 (0) 

  U 

t U 
0  
 Pt (1) 
 P0 (1) 
遷移確率行列は
 1 0  1
U
W  U 
(   1)
0  
と対角化可能
April, 2013
 Pt (0) 
 P(0) 
 1 0  1  P0 (0) 
  U 


  lim 
U 
 P(1)  t   Pt (1) 
 0 0
 P0 (1) 
極限分布
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 3]
11
簡単な確率過程：マルコフ連鎖
Pt ( x) 
P( x) 
1
 w( x | z[t  1])Pt 1 ( z[t  1])
z[t 1]  0
1
 w( x | z[t  1])P( z[t  1])
z[t 1]  0
 P(0) 
 P(0) 

  W 

 P(1) 
 P(1) 
定常分布または平衡分布
 Pt (0) 
 P(0) 
 が存在すれば定常分布は存在する


 lim 
極限分布 

 P(1)  t   Pt (1) 
定常分布が存在しても極限分布が存在するとは限らない．
0 1
 P(0)  1 / 2 
Example

W  

  
 は定常分布
1
0


 P(1)  1 / 2 
April, 2013
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 3]
12
マルコフ連鎖の定常分布と詳細釣り合い
Pt x  
1
 wx y Pt 1 ( y)
ただし
y 0
1
 wy x   1
y 0
P1(x), P2(x), P3(x),…: マルコフ連鎖
wy xP( x)  wx y P( y)
詳細釣り合い
を満たすように推移確率 w(x|y) を選ぶと
その定常分布は P(x) になる．
P x  
1
 wx y P y 
マルコフ連鎖の定常分布
y 0
April, 2013
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 3]
13
マルコフ連鎖モンテカルロ法

確率分布P( x )  P( x1 , x2 ,, x L ) が与えられたとき

任意の P0 ( x ) を初期値として



Pt ( x )   wx y Pt 1 ( y ) (t  1,2,3,)

y


を繰り返し計算して， lim Pt ( x )  P( x ) となるように

wx y 
April, 2013
t  
を選ぶにはどうしたらよいか？
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 3]
14
マルコフ連鎖モンテカルロ法



Pt x    wx y Pt 1 ( y )

y

ただし  w y x   1

y
P1(x), P2(x), P3(x),…: マルコフ連鎖
 
 
詳細釣り合い wy x Px   wx y P y 

wx y  を選ぶとその推移確率
を満たすように推移確率

の定常分布は P (x ) になる．


 

w
x
y の
推移確率
P x    wx y P y 

マルコフ連鎖の定常分布
y
極限分布がただ一つ存在するとしたら定常分布のひとつが極限分布である．
April, 2013
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 3]
15
マルコフ連鎖モンテカルロ法

xt  1
 
wxt  xt  1

x t 
無駄弾

x[1]

x[t  1]


x[2]

x[t  2]





x[t ]

x[2t ]




x[(N  1)t  1] x[(N  2)t  1]  x[ Nt  1]
精度は
1/2
O(1/t )
April, 2013

P (x ) からのサンプリング
ランダムに生成
τ が十分大きい
ときサンプルx[t],
x[2t], x[3t], …,
x[Nt] は独立
独立とみ
なせるか
t をどれだけ大き
くとるべきか→緩
和時間
とみなすことができる
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 3]
16
マルコフ連鎖モンテカルロ法

x[1]

x[2]

x[t  1]


x[t  2]






x[(N  1)t  1] x[(N  1)t  2] 
P1  X 1  

x[t ]

x[2t ]


x[ Nt ]
    P X 1 , X 2 , X 3 ,, X L 
X2 X3
XL
頻度
N
1

 x1 nt , X 1

N n 1
Xi
ヒストグラムから周辺確率も計算できる
April, 2013
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 3]
17
マルコフ連鎖モンテカルロ法

x (1)

x (2)

x (t  1)


x ((N  1)t  1)
Pi  X i  

x (t  2)





x ((N  1)t  2) 
 P X , X
1
2
,, X i ,, X L 
X \ Xi
1

N

x (t )

x (2t )


x ( Nt )
頻度
N

n 1
xi  nt , X i
Xi
ヒストグラムから周辺確率も計算できる
April, 2013
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 3]
18
マルコフ連鎖モンテカルロ法
P x   Px1 , x2 ,, xL  
 x , x 
{i , j}
i
j
{i , j}E
Px1 , x2 ,, xi 1 , xi , xi 1 ,, xN 
Pxi x1 , x2 ,, xi 1 , xi 1 ,, xN  
Px1 , x2 ,, xi 1 , xi 1 ,, xN 
Px1 , x2 ,, xi 1, xi 1,, xN    Px1 , x2 ,, xi 1 , zi , xi 1 ,, xN 
zi
V：すべてのノードの集合
E：すべてのリンクの集合
April, 2013
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 3]
19
マルコフ連鎖モンテカルロ法

P( x)  P( x1 , x2 ,, xL ) 

{i , j}
( xi , x j )
{i , j}E
Pxi x1 , x2 , , xi 1 , xi 1 , , xL
  x , x 

 P x x
  z , x 
{i , j }
i
zi
リンクの集合
April, 2013
i
j

j  i
j
ji
マルコフ確率場
E：すべての
j
ji
{i , j }
(V , E )
i
(V , E )
i ：ノード i とリンクで結ば
れたすべてノードの集合
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 3]
20
マルコフ連鎖モンテカルロ法

P( x)  P( x1 , x2 ,, xL ) 

{i , j}
( xi , x j )
{i , j}E
wx1, x2 , , xL x1 , x2 , , xL
xk  xk k  i 
(V , E )
 x, x 




      ( x , x ) 

   z , x 
i
j
ji
iV
k
k
kV / i
{i , j }
zi
i
j
ji
  


wx' x Px   wx x' Px' 

xt  1
April, 2013
{i , j }
 
wxt  xt  1
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 3]

x t 
21
マルコフ連鎖モンテカルロ法
w(x(t+1)|x(t))
x(t)
x(t+1)
True
xi = ○ or
False
●

x

１回の更新にかか
る計算量は変数の
次元 L に対して
O(1)
x’
April, 2013
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 3]
22
マルコフ連鎖モンテカルロ法
伊庭幸人, 種村正美: 統計科学のフロンティア/計算
統計 II ---マルコフ連鎖モンテカルロ法とその周辺,
岩波書店, 2005.
April, 2013
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 3]
23
確率伝搬法 (Belief Propagation)
P1 x1  
    Px , x ,, x 
x2 0,1 x3 0,1
xL 0,1
1
2
L
を厳密に計算するのは一部の特殊な例を除いて難しい．
一部の特殊な例とは何か？
一部の特殊な例に適用できるアルゴリズムを一般
の場合に近似アルゴリズムとして適用できるか．
→ アルゴリズム化できるか？動くか？
精度はどの程度か？
April, 2013
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 3]
24
扱いやすい確率モデルのグラフ表現
April, 2013
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 3]
25
扱いやすい確率モデルのグラフ表現

A
B
C
D
E
A B C D E
April, 2013
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 3]
26
扱いやすい確率モデルのグラフ表現

A
B
C
D
E
A B C D E
 
A
B
X
B
C
D
E
A B C D E
April, 2013
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 3]
27
扱いやすい確率モデルのグラフ表現

A
B
C
D
E
A B C D E
 
A
B
X
B
C
D
E
A B C D E

   

B C D E  A
April, 2013
A

B 


B
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 3]
C
D
E
28
扱いやすい確率モデルのグラフ表現

A
B
C
D
E
A B C D E
 
A
B
X
B
C
D
E
A B C D E

   

B C D E  A
April, 2013
A

B 


A
B
B
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 3]
C
D
E
29
扱いやすい確率モデルのグラフ表現

A
B
C
D
E
A B C D E
 
A
B
X
B
C
D
E
A B C D E

   

B C D E  A
 
A
A

B 


A
B
B
C
B
C
D
D
E
E
B C D E
April, 2013
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 3]
30
扱いやすい確率モデルのグラフ表現

A
B
C
D
E
B C D E
April, 2013
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 3]
31
扱いやすい確率モデルのグラフ表現

A
B
C
D
E
B C D E
 
A
B
C
X
C
D
E
B C D E
April, 2013
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 3]
32
扱いやすい確率モデルのグラフ表現

A
B
C
D
E
B C D E
 
A
X
B
C
B

C X


C
D
E
B C D E

    A

C D E  B
April, 2013
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 3]
C
D
E
33
扱いやすい確率モデルのグラフ表現

A
B
C
D
E
B C D E
 
A
X
B
C
B

C X


C
D
E
B C D E

    A

C D E  B
B
April, 2013
C
D
E
C
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 3]
34
扱いやすい確率モデルのグラフ表現

A
B
C
D
E
B C D E
 
A
X
B
C
B

C X


C
D
E
B C D E

    A

C D E  B
B
 
B
C
D
E
C
C
D
E
C D E
April, 2013
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 3]
35
扱いやすい確率モデルのグラフ表現

A
B
C
D
E
A B C D E
April, 2013
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 3]
36
扱いやすい確率モデルのグラフ表現

A
B
C
D
E
A
B
C
D
E
A B C D E
 
B C D E
April, 2013
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 3]
37
扱いやすい確率モデルのグラフ表現

A
B
C
D
E
A
B
C
D
E
C
D
E
A B C D E
 
B C D E
  B
C D E
April, 2013
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 3]
38
扱いやすい確率モデルのグラフ表現

A
B
C
D
E
A
B
C
D
E
C
D
E
C
D
E
A B C D E
 
B C D E
  B
C D E
 
D E
April, 2013
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 3]
39
扱いやすい確率モデルのグラフ表現

A
B
C
D
E
A
B
C
D
E
C
D
E
C
D
E

D
E
A B C D E
 
B C D E
  B
C D E
 
D E
E
April, 2013
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 3]
40
扱いやすい確率モデルのグラフ表現
A

D
C
E
A B C D E F
B
April, 2013
F
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 3]
41
扱いやすい確率モデルのグラフ表現
A

D
C
 
E
A B C D E F
D
C
E
B C D E F
B
April, 2013
A
F
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 3]
B
F
42
扱いやすい確率モデルのグラフ表現
A

D
C
 
E
A B C D E F
D
C
E
B C D E F
B
F
A
 
A
B
F
D
C
E
C D E F
B
April, 2013
F
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 3]
43
扱いやすい確率モデルのグラフ表現
A

D
C
A
 
E
A B C D E F
F
A
E
B
D
C
F
D
  C
E
C D E F
E
D E F
B
April, 2013
C
B C D E F
B
 
D
F
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 3]
F
44
扱いやすい確率モデルのグラフ表現
A

D
C
A
 
E
A B C D E F
D
C
E
B C D E F
B
F
A
B
D
 
C
D
  C
E
C D E F
F
E
D E F
B
F
F
D
 
C
E
E F
F
April, 2013
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 3]
45
扱いやすい確率モデルのグラフ表現
A

D
C
A
 
E
A B C D E F
D
C
E
B C D E F
B
F
A
B
D
 
C
D
  C
E
C D E F
F
E
D E F
B
F
F
D
 
C

E
E F
F
April, 2013
F
E
F
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 3]
46
扱いやすい確率モデルのグラフ表現
周辺確率のメッセージを用いた表現
A
Pr{E}  
A
B
C
D
C
E
F
B
April, 2013
D
F
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 3]
47
扱いやすい確率モデルのグラフ表現
周辺確率のメッセージを用いた表現
A
Pr{E}  
A
B
C
D
D
C
E
F
B
F
A
＝

A
B
C
C
D

D
B
April, 2013
E
E

E
F
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 3]
F
48
扱いやすい確率モデルのグラフ表現
周辺確率のメッセージを用いた表現
A
D
Pr{E}  
A
B
C
D
C
E
F
B
F
A
＝

A
B
C
E
C

D
B
＝
C
D
E
E
April, 2013
D
E

E
F
F
E
F
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 3]
49
扱いやすい確率モデルのグラフ表現
周辺確率のメッセージを用いた表現
A
D
Pr{E}  
A
B
C
D
C
E
F
B
F
A
＝

A
B
C
E
C
D

D
B

E
F
E
F
D
＝
C
D
E
E
April, 2013
E
＝
C
E
F
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 3]
F
50
扱いやすい確率モデルのグラフ表現
周辺確率のメッセージを用いた表現
A
D
Pr{C, E}  
A
B
D
C
E
F
B
＝

A

B
C
A
F
C
C
E

D
B
D

E
F
E
F
A
＝
C
A
C
C
April, 2013
B
D
E
E
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 3]
E
＝
F
D
C
E
B
F
51
扱いやすい確率モデルのグラフ表現
周辺確率のメッセージを用いた表現
A
D
Pr{E}
＝
C
Pr{C , E} ＝
E
C
B
F
Pr{E}   Pr{C, E}
D
C
C
E
F
C
E

C

C
April, 2013
D
A
E
F
D
C
E
B
F
A
C
E
メッセージに
対する漸化式
B
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 3]
52
扱いやすい確率モデルのグラフ表現
A
周辺確率のメッセージを用いた表現
C

C
A
C
C
A
E
B
Step 1
A
D
B

B
D
C
E
B

D
F
D
E
E
F

E
F
F
Step 2
C
E

C
A
C
C
E
E
D
 C
E
E
B
F
Step 3
A
C

C
C
A
C
B
April, 2013
E
B

C
A
D
C
B
E
E
C
E
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 3]
D
E
E
F
F
C
D
E
F
E
53
扱いやすい確率モデルのグラフ表現
周辺確率のメッセージを用いた表現
Step 1
A
D
C
Step 2
B
F
A
D
C
Step 3
E
B
F
A
D
C
B
April, 2013
E
E
F
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 3]
54
確率伝搬法 (Belief Propagation)
閉路のないグラフ上の確率モデル
Pa, b, c, d , x1 , x2 
 WA a, x1 WB b, x1 W{1, 2} x1 , x2 WC c, x2 W d , x2 
a
3
4
1
2
6
d
April, 2013
5
b
x3  a
x5  c
x4  b
x6  d
c
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 3]
55
確率伝搬法 (Belief Propagation)
閉路のないグラフ上の確率モデル
WA a, x1 
a
WB b, x1 
3
a
4 b
3
1
1
6
2
6
d
WC c, x2 
April, 2013
5
c
WD d , x2 
d
b
1
2
W{1, 2} x1 , x2 
2
2
1
4
5
c
Pa, b, c, d , x1 , x2 
 WA a, x1 WB b, x1 
 W{1, 2} x1 , x2 WC c, x2 W d , x2 
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 3]
56
閉路のないグラフ上の確率モデル
P{1, 2} x1 , x2  
 Pa, b, c, d , x , x 
1
2
a,b,c,d
 M 31 x1 M 41 x1 W{1, 2} 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
3
4
2
d
April, 2013
5
M 52 x2   WC c, x2  M 62 x2   WD d , x2 
c
1
6
b
c
b
d
ノード１と２の周辺確率分布は
それぞれ隣接するノードから伝搬されるメッセージ
の積により表される．
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 3]
57
確率伝搬法 (Belief Propagation)
閉路のないグラフ上の確率モデル
M 12 x2   W{1, 2} x1 , x2 WA a, x1 WB b, x1 
x1
a
b
 W{1, 2} x1 , x2 M 31 x1 M 41 x1 
x1
a
6
d
April, 2013
 
1
  
M  M
c
5
メッセージに対する固定点方程式
(Message Passing Rule)
3
2
ノード１から隣接ノード２に伝搬するメッセージは（ノー
ド２を除く）ノード１の隣接ノードからノード１に伝搬され
るメッセージの積により表される．
4
b
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 3]
58
閉路のないグラフ上の確率伝搬法


  1
Pr X  x  W{i , j} xi , x j 
Z {i , j}
X1
X2
X3
X k 1
X k 3
Xk
閉路が無いこと
が重要!!
X k 1
X k 2
同じノードは２度通らない
April, 2013
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 3]
59
確率的画像処理における
確率伝搬法(Belief Propagation)

Px   Px1 , x2 ,, xL  
 x , x 
{i , j}
i
j
{i , j}E
E：すべてのリンクの集合
April, 2013
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 3]
60
正方格子によるグラフ表現をもつ
確率モデルの確率伝搬法(Belief Propagation)
着目画素とその近傍画素だけを残すと木構造になる．
April, 2013
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 3]
61
正方格子によるグラフ表現をもつ
確率モデルの確率伝搬法(Belief Propagation)
着目画素とその近傍画素だけを残すと木構造になる．
確率伝搬法(Belief Propagation)の統計的近似アルゴリズムとしての転
用
April, 2013
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 3]
62
周辺確率(Marginal Probability)
P2 x2     Px1 , x2 , x3 , x4 ,, x N 
x1 x3 x 4
April, 2013
xN
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 3]
63
周辺確率(Marginal Probability)
P2 x2     Px1 , x2 , x3 , x4 ,, x N 
x1 x3 x 4
   
x1 x 3 x 4
April, 2013
xN
2
xN
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 3]
64
周辺確率(Marginal Probability)
P2 x2     Px1 , x2 , x3 , x4 ,, x N 
x1 x3 x 4
   
x1 x 3 x 4
April, 2013
xN
2
xN
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 3]

2
65
周辺確率(Marginal Probability)
P{1,2} x1, x2    Px1 , x2 , x3 , x4 ,, xN 
x3
April, 2013
x4
xN
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 3]
66
周辺確率(Marginal Probability)
P{1,2} x1, x2    Px1 , x2 , x3 , x4 ,, xN 
x3
  
x3 x 4
April, 2013
x4
1
xN
2
xN
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 3]
67
周辺確率(Marginal Probability)
P{1,2} x1, x2    Px1 , x2 , x3 , x4 ,, xN 
x3
  
x3 x 4
April, 2013
xN
x4
1
xN
2

電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 3]
1
2
68
正方格子によるグラフ表現をもつ
確率モデルの確率伝搬法(Belief Propagation)
P2 x2    P{1, 2} x1 , x2 
x1
April, 2013
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 3]
69
正方格子によるグラフ表現をもつ
確率モデルの確率伝搬法(Belief Propagation)
P2 x2    P{1, 2} x1 , x2 
x1
4
3
8
1
2
5
April, 2013
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 3]
7
6
70
正方格子によるグラフ表現をもつ
確率モデルの確率伝搬法(Belief Propagation)
P2 x2    P{1, 2} x1 , x2 
x1
8
2
1
6
April, 2013
7
4
3
8
1
2
5
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 3]
7
6
71
正方格子によるグラフ表現をもつ
確率モデルの確率伝搬法(Belief Propagation)
3
P2 x2    P{1, 2} x1 , x2 
1 
2

2
1
4
x1
5
x1
Message Update Rule
8
2
1
6
April, 2013
7
4
3
8
1
2
5
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 3]
7
6
72
閉路のあるグラフ上の確率モデル
の確率伝搬法(Belief Propagation)
3
2
M 12
M 31
1 

2
1
M 41
4
M 51
x1
5
３
４
１
２
閉路のあるグラフ上でも局所的な構造だけに
着目してアルゴリムを構成することは可能．
ただし，得られる結果は厳密ではなく近似ア
ルゴリズム
５
April, 2013
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 3]
73
閉路のあるグラフ上の確率モデル
の確率伝搬法(Belief Propagation)
3
2
M 12
M 31
1 

2
1
M 41
4
M 51
x1
5
３
４
１
２
閉路のあるグラフ上でも局所的な構造だけに
着目してアルゴリムを構成することは可能．
ただし，得られる結果は厳密ではなく近似ア
ルゴリズム
５
 
  
M  M
April, 2013
メッセージに対する固定点方
程式
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 3]
74
閉路のあるグラフ上の確率モデル
の確率伝搬法(Belief Propagation)
3
2
M 12
M 31
1 

2
1
M 41
4
M 51
x1
5
３
４
１
２
閉路のあるグラフ上でも局所的な構造だけに
着目してアルゴリムを構成することは可能．
ただし，得られる結果は厳密ではなく近似ア
ルゴリズム
５
 
  
M  M
メッセージに対する固定点方
程式
平均，分散,共分散はこのメッセージを使ってあらわされる
April, 2013
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 3]
75
Fixed Point Equation and
Iterative Method
Fixed Point Equation
April, 2013
 
*  *
M  M
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 3]
76
Fixed Point Equation and
Iterative Method
Fixed Point Equation
 
*  *
M  M
Iterative Method
yx
y
y  (x)
0
April, 2013
M*
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 3]
x
77
Fixed Point Equation and
Iterative Method
Fixed Point Equation
 
*  *
M  M
Iterative Method
yx
y
y  (x)
0
April, 2013
M*
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 3]
M0
x
78
Fixed Point Equation and
Iterative Method
Fixed Point Equation
 
*  *
M  M
Iterative Method
 


M1   M 0
yx
y
M1
0
April, 2013
y  (x)
M*
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 3]
M0
x
79
Fixed Point Equation and
Iterative Method
Fixed Point Equation
 
*  *
M  M
Iterative Method
 
 


M1   M 0


M 2   M1
M1
0
April, 2013
yx
y
y  (x)
M * M1
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 3]
M0
x
80
Fixed Point Equation and
Iterative Method
Fixed Point Equation
 
*  *
M  M
Iterative Method
 
 


M1   M 0


M 2   M1
M1
M2
0
April, 2013
yx
y
y  (x)
M * M1
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 3]
M0
x
81
Fixed Point Equation and
Iterative Method
Fixed Point Equation
 
*  *
M  M
Iterative Method
 
 
 


M1   M 0


M 2   M1


M3   M2
yx
y
M1
M2
0
y  (x)
M * M1
M0
x

April, 2013
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 3]
82
確率的画像処理における
確率伝搬アルゴリズムの基本構造
４近傍の場合は3入力1出力の更新式
ひとつの画素ごとに４種類の更新パターン
画素上での
動作の様子
の一例
April, 2013
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 3]
83
閉路のあるグラフ上の確率モデル
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
April, 2013
メッセージに対する固定点方
程式
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 3]
84
確率伝搬法の参考文献
田中和之著: 確率モデルによる画像処理技術入門, 森北出版,
2006.
田中和之著: ベイジアンネットワークの統計的推論の数理, コロ
ナ社, 2009.
M. J. Wainwright and M. Jordan: Graphical Models, Exponential
Families, and Variational Inference (Foundations and Trends® in
Machine Learning), Now Publishers, 2008.
M. Mezard and A. Montanari: Information, Physics, and
Computation, Oxford University Press, 2009.
April, 2013
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 3]
85
まとめ
確率的計算技法の基礎
 マルコフ連鎖モンテカルロ法
 確率伝搬法
April, 2013
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 3]
86

Download Report