電気・通信・電子・情報工学実験D
確率的情報処理の基礎技術
Part 5 (2016年4月)
本実験DのWebpage:
http://www.smapip.is.tohoku.ac.jp/~kazu/ECEI-ExperimentD/2016/
東北大学 大学院情報科学研究科
田中 和之
[email protected]
http://www.smapip.is.tohoku.ac.jp/~kazu/
April, 2016
電気・通信・電子・情報工学実験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.
April, 2016
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 5]
2
Contents
1.
2.
3.
4.
5.
6.
April, 2016
序論：確率的情報処理とベイジアンネットワーク
確率の基礎知識
確率的計算技法の基礎
---マルコフ連鎖モンテカルロ法と確率伝搬法--確率的画像処理とベイジアンネットワーク
---マルコフ確率場と確率伝搬法--確率推論とベイジアンネットワーク---グラフィカルモ
デルと確率伝搬法--まとめ
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 5]
3
ベイジアンネットと確率推論
ベイズの公式
確率モデル
グラフィカルモデル
確率推論
医療診断
故障診断
ベイジアンネット
不確実性を伴うデータに耐えうる推論システム
たくさんのノードが関連しあって集まっている．
計算困難を打破する高性能の近似アルゴリズムの必要性
April, 2016
電気・通信・電子・情報工学実験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, 2016
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 5]
A
B
5
確率の知識（２）
事象 B の周辺確率
PrB   PrA, B, C , D
A
C
D
A
B
C
D
周辺化
April, 2016
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 5]
6
確率推論に使う数学
PrA, B, C  PrC A, BPrA, B
 PrC A, BPrB APrA
 PrC BPrB APrA
PrB A
PrC A, B  PrC B
因果独立の仮定
April, 2016
A
PrA, C 
PrA C  
PrC 
B
 PrA, B, C
 B
C
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 5]
 PrA, B, C
A, B
7
簡単なベイジアンネットの例
問題
芝生がぬれているのは何故でしょうか？雨が降ったせいでしょうか？
それともスプリンクラーを動かしたせいでしょうか？

PrAR  T AW  T PrAS  T AW  T ?

April, 2016
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 5]
8
簡単なベイジアンネットの例
PrAC , AS , AR , AW 
 PrAW AC , AS , AR PrAC , AS , AR 
 PrAW AC , AS , AR PrAR AC , AS PrAC , AS 
 PrAW AC , AS , AR PrAR AC , AS PrAS AC PrAC 
 PrAW AS , AR PrAR AC PrAS AC PrAC 
April, 2016
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 5]
9
簡単なベイジアンネットの例
PrAR  T, AW  T
PrAR  T AW  T 
PrAW  T
PrAS  T, AW  T
PrAS  T AW  T 
PrAW  T
April, 2016
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 5]
10
簡単なベイジアンネットの例
PrAR  T, AW  T 
PrAS  T, AW  T 
PrAW  T 
April, 2016

 PrAC , AS , AR  T, AW  T  0.4581

 Pr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
簡単なベイジアンネットの例
PrAR  T AW  T 
PrAR  T, AW  T 0.4581

 0.7079
PrAW  T
0.6471
PrAS  T AW  T 
PrAS  T, AW  T 0.2781

 0.4298
PrAW  T
0.6471
回答：芝生がぬれているのは雨が降ったせいだと考えられます．
April, 2016
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 5]
12
より複雑なベイジアンネット
P1 ( x1 )   Px1 , x2 , x3 ,, xL 
x2
x3
xL
定義に基づいて厳密に計算す
るプログラム
xi  True or False
ノード数とともに指数関数的
L
に計算量が増加 Oe 
2 L1  exp L  1ln 2
April, 2016
P x1   0;
2
L 1
重ループ
for( x2  T or F){
for( x2  T or F){

for( xL  T or F){
P x1   P x1   P x1 , x2 ,  , xL ;
}

}
}
このプログラムでは
L=10個のノードで1秒かかるとしたら
L=20個で約17分，L=30個で約12日，
L=40個で約34年かかる．
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 5]
13
確率伝搬法
1. 閉路を持たないグラフ上の確率モデルに対して厳密な結果を与える．
2. 閉路を持つグラフ上の確率モデルでは近似アルゴリズムとなる．
PrX   PrX 8 X 5 , X 6 PrX 7 X 6 


 Pr X 6 X 3 , X 4 PrX 5 X 2 
 PrX 4 X 2 PrX 3 X 1
 PrX 1PrX 2 
８個程度のノードの簡単ではあるが
閉路を含むグラフ上の確率モデルで
確率伝搬法の構造を説明し，得られ
る近似結果と厳密な結果を比較して
みる．
April, 2016
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 5]
14
閉路を持つグラフ上の
確率モデルの結合確率
PrX 1  x1 , X 2  x2 ,, X 8  x8 
 W568 (x 5 , x6 , x8 )W346 ( x3 , x4 , x5 )W67 ( x6 , x7 )
 W25 ( x2 , x5 )W24 ( x2 , x4 )W13 ( x1 , x3 )
X1
W24
W13
有向
グラフ
X3
W67
April, 2016
W25
X4
W346
X7
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 5]
無向
グラフ
X2
X6
W568
X5
X8
15
周辺確率分布
Pi ( X i )

X1
 Pr X , X , X , X , X , X , X , X 
1
2
3
4
5
6
7
W24
W13
8
X3
X \ Xi
W25
X4
W346
Pij ( X i , X j )

X2
W67
PrX , X , X , X , X , X , X , X 

 
1
2
3
4
5
6
7
X6
W568
X7
8
X5
X8
X \ Xi ,X j
Pijk ( X i , X j , X k ) 
PrX , X , X , X , X , X , X , X 



1
2
3
4
5
6
7
8
X \ Xi ,X j ,Xk
April, 2016
電気・通信・電子・情報工学実験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
P6  x6  
X2
M 313 ( X 3 )
X4
X3
X6
X5
X8
1
M 6346  x6 
Z6
W346
M 667 ( X 6 )
M 6568 ( X 6 )
 M 6568  x6 M 667  x6 
April, 2016
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
X3
A4
W67
確率伝搬アルゴリズム
April, 2016
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 5]
W25
X4
W346
M 6346 ( X 6 )
A6
X2
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, 2016
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
X1
X3
W3
W6
W67
Message Passing Algorithm
April, 2016
W24
W13
M 6346 ( X 6 )
X6
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 5]
X2
X7
W346
X6
W25
X4
W4
W568
X5
W5
X8
20
固定点方程式と反復法
 
*  *
M  M
固定点方程式
反復法
繰り返し出力を入力に入れることにより，
固定点方程式の解が数値的に得られる．
 
 
 

 
M1   M 0

 
M 2   M1

 
M3   M2

April, 2016
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
P58 (1,1)  0.4736
P58 (1,0)  0.0764
P58 (0,1)  0.0871
P58 (0,0)  0.3629
Belief Propagation
P8 (1)  0.5640 P8 (0)  0.4360
P58 (1,1)  0.4776
P58 (1,0)  0.0724
P58 (0,1)  0.0864
P58 (0,0)  0.3636
P8 ( x8 ) 
Exact
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



1
2
, x3 , x4 , x5 , x6 , x7 , x8 )
x \ x5 , x8
April, 2016
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 5]
X2
W67
X7
W346
X6
W25
X4
W568
X5
X8
22
数値実験
確率伝搬法

Pr X Bronchitis  Present X 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, 2016
電気・通信・電子・情報工学実験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 )
Deviation of Average at Node j with respect to External Field at Node i

1
~
P ( x )  ~ P ( x )exp hi xi ,m
Z
April, 2016
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 5]

24

数値実験
Pr X Tuberculos is  Present X Dy spnea  Present


PrX Tuberculos is  Present , X Dy spnea  Present 
PrX Dy spnea  Present 
0.0082

 0.0187
0.4393
X1
X2
W24
W13
X3
W3
W6
W67
X7
April, 2016
電気・通信・電子・情報工学実験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, 2016
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Part 5]
26

自殺者0人の社会を目指してpart.5

3位 3位