Kazuyuki Tanaka ECEI Experiment D (2013 Part 5)

電気・通信・電子・情報工学実験D
確率的情報処理の基礎技術
Part 5 (2015年4月)
本実験DのWebpage:
http://www.smapip.is.tohoku.ac.jp/~kazu/ECEI-ExperimentD/2015/
東北大学大学院情報科学研究科
田中和之
[email protected]
http://www.smapip.is.tohoku.ac.jp/~kazu/
April, 2014
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 5]
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.
K. P. Murphy: Machine Learning: A Probabilistic Perspective, MIT Press, 2012.
April, 2015
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 3]
2
Contents
1.
2.
3.
4.
5.
6.
April, 2014
序論：確率的情報処理とベイジアンネットワーク
確率の基礎知識
確率的計算技法の基礎
---マルコフ連鎖モンテカルロ法と確率伝搬法--確率的画像処理とベイジアンネットワーク
---マルコフ確率場と確率伝搬法--確率推論とベイジアンネットワーク---グラフィカルモ
デルと確率伝搬法--まとめ
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 5]
3
ベイジアンネットと確率推論
ベイズの公式
確率モデル
グラフィカルモデル
確率推論
医療診断
故障診断
ベイジアンネット
不確実性を伴うデータに耐えうる推論システム
たくさんのノードが関連しあって集まっている．
計算困難を打破する高性能の近似アルゴリズムの必要性
April, 2014
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 5]
4
確率の知識（１）
事象Ａの起こる確率
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
April, 2014
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 5]
A
B
5
確率の知識（２）
事象 B の周辺確率
PrB   PrA, B, C, D
A
C
D
A
B
C
D
周辺化
April, 2014
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 5]
6
確率推論に使う数学
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
因果独立の仮定
April, 2014
A
P rA, C
P rA C 
P rC
B
 P rA, B, C
 B
C
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 5]
 P rA, B, C
A, B
7
簡単なベイジアンネットの例
問題
芝生がぬれているのは何故でしょうか？雨が降ったせいでしょうか？
それともスプリンクラーを動かしたせいでしょうか？

P rAR  T AW  T P rAS  T AW  T?

April, 2014
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 5]
8
簡単なベイジアンネットの例
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 
April, 2014
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 5]
9
簡単なベイジアンネットの例
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
April, 2014
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 5]
10
簡単なベイジアンネットの例
P rAR  T, AW  T 
P rAS  T, AW  T 
PrAW  T 
April, 2014

 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
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 5]
, AW  T  0.6471
11
簡単なベイジアンネットの例
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
回答：芝生がぬれているのは雨が降ったせいだと考えられます．
April, 2014
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 5]
12
より複雑なベイジアンネット
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 
Px1   P x1   P x1 , x2 ,  , xL ;
}
2L1  expL 1ln 2

}
}
April, 2014
2
L 1
このプログラムでは
L=10個のノードで1秒かかるとしたら
L=20個で約17分，L=30個で約12日，
L=40個で約34年かかる．
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 5]
13
確率伝搬法
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 
８個程度のノードの簡単ではあるが
閉路を含むグラフ上の確率モデルで
確率伝搬法の構造を説明し，得られ
る近似結果と厳密な結果を比較して
みる．
April, 2014
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 5]
14
閉路を持つグラフ上の
確率モデルの結合確率
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
April, 2014
W25
X4
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 5]
X6
無向
グラフ
W568
X5
X8
15
周辺確率分布
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
April, 2014
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 5]
16
この場合の確率伝搬法の基本方針
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
April, 2014
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 
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 5]
17
確率伝搬法の固定点方程式
 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
確率伝搬アルゴリズム
April, 2014
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 5]
W25
X4
X7
X6
W568
X5
X8
18
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
April, 2014
W346
M 424 ( X 4 )
X4
X6
X5
X8
M 6568 ( X 6 )
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 5]
19
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
April, 2014
X1
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 5]
X7
W346
X6
W25
X4
W4
W568
X5
W5
X8
20
固定点方程式と反復法
 
*  *
M  M
固定点方程式
反復法
繰り返し出力を入力に入れることにより，
固定点方程式の解が数値的に得られる．
 
 
 

 
M1   M 0

 
M 2   M1

 
M3   M2

April, 2014
yx
y
M1
0
y  (x)
M * M1
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 5]
M0
x
21
数値実験
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
April, 2014
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 5]
X2
8
W67
X7
W346
X6
W25
X4
W568
X5
X8
22
数値実験
確率伝搬法


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
April, 2014
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 5]
W346
X6
W25
X4
W4
W568
X5
W5
X8
23
線形応答理論
（人為的に小さなゆらぎを与えてその応答を見ることで詳細を知ることができる．）
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
April, 2014
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 5]

24

数値実験

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
April, 2014
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 5]
W346
X6
W25
X4
W4
W568
X5
W5
X8
25
確率推論のまとめ
ベイジアンネットと確率伝搬法を用いた確率推論の概説
線形応答定理を用いた高次の推論システムへの発展
ベイジアンネットの最近の動向
繁桝算男, 本村陽一, 植野真臣：ベイジアンネットワーク概説，培風館，2006.
本村陽一, 岩崎弘利：ベイジアンネットワーク技術，東京電機大出版，2006.
田中和之著: ベイジアンネットワークの統計的推論の数理, コロナ社, 2009.
Microsoft社，Intel社，Nokia社などが実用化への研究
http://excalibur.brc.uconn.edu/~baynet/
http://www.research.microsoft.com/research/dtg/
April, 2014
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 5]
26

Download Report