確率的情報処理における確率伝搬型アルゴリズムと

統計力学と情報処理
---自由エネルギーの生み出す新しい情報処理技術--２００３年８月１４日後半
東北大学大学院情報科学研究科
田中和之
[email protected]
http://www.statp.is.tohoku.ac.jp/~kazu/
第48回物性若手夏の学校
1
この時間の主な内容
ベイジアンネットとクラスター変分法を
用いた確率推論の概説
線形応答定理を用いた高次の推論シ
ステムへの発展
第48回物性若手夏の学校
2
前の時間のポイント
ベイジアンネットは磁性体の物理モデルと
対応づけられる．
１次元鎖および木構造を持つベイジアンネ
ットは確率伝搬法（＝転送行列法）
で計算できる．
A1
1
2
3
N 1
N
A3
A2
A4
第48回物性若手夏の学校
A5
A6
3
より複雑なベイジアンネット
A2
A1
W24
W13
A3
W3
W6
W67
A7
第48回物性若手夏の学校
A4
W346 W
4
A6
W568
W25
A5
W5
A8
4
より複雑なベイジアンネット
Pa   PrA1  a1, A2  a2 ,, A8  a8 
1 W568(a5 , a6 , a8 )W346(a3 , a4 , a5 )W67 (a6 , a7 )W25(a2 , a5 )

Z
W6 (a6 )2W5 (a5 )W4 (a4 )
W24(a2 , a4 )W13(a1, a3 )

A2
A1
W3 (a3 )W2 (a2 )
W
W13
a  ai i  1,2,,8
24
A3
W3
W6
W67
A7
第48回物性若手夏の学校
W346
A6
W25
A4
W4
W568
A5
W5
A8
5
周辺確率分布
Pa  PrA1  a1, A2  a2 ,, A8  a8 
Pi (ai ) 
 Pa
a \ai 
Pij (ai , a j ) 
信念
（Belief）
W24
W13
 Pa
a \ai ,a j 
Pijk (ai , a j , ak ) 
A2
A1
 Pa
a \ai ,a j ,ak 
第48回物性若手夏の学校
A3
W3
W6
W67
A7
A4
W346 W
4
A6
W568
W25
A5
W5
A8
6
クラスター変分法の基本方針
P6 a6    P346a3, a4 , a6 
a3 a4
A2
A1
M313( A3 )
M 6346( A6 )
A3
A3
A4
W346
M667 ( A6 )
A7
A5
A6
A8
M 6568( A6 )
M667 ( A6 )
A7
第48回物性若手夏の学校
W346
M 424( A4 )
A4
A5
A6
A8
M 6568( A6 )
7
クラスター変分法の固定点方程式
W346(a3, a4 , a6 )M313(a3)M424(a4 )
M 6346(a6 ) 
a3 a4
W346(a3, a4 , a6 )M313(a3)M424(a4 )
a3 a4 a6
A2
A1
M313( A3 )
A3
A4
M 424 ( A4 )
A2
A1
W24
W13
A3
W3
M 6346( A6 )
W6
A6
W67
確率伝搬アルゴリズム
第48回物性若手夏の学校
A7
A4
W346 W
4
A6
W568
W25
A5
W5
A8
8
固定点方程式と反復法
固定点方程式
反復法
 
*  *
M  M
繰り返し出力を入力に入れることにより，
固定点方程式の解が数値的に得られる．
 
 
 


M1   M 0


M 2   M1


M3   M 2

y
M1
*
M1
M
0
第48回物性若手夏の学校
yx
y  (x)
M0
x
9
クラスター変分法
 Q x  
 Q x   0 
  0 

DQ P  Q( x) ln
  Q( x)  1
x
 P x  

Q ( x ) 
x
Q( x) : Q(x) の周辺確率分布
X1
X2
W24
W13

X3
W3
W6
W346 W
4
X6
W67
x\ x
W3
X3
X2
W2
X4
X4
X3
W346
W67
X6
W2 5
X5
X4
X6
X2
W4
W5
X6
X7
第48回物性若手夏の学校
X2
W24
X3
W5
X8
X1
W1 3
X5
W568
X7
Q( x1, x2 , x3 , x4 , x5 , x6 , x7 , x8 )
Q568( x5 , x6 , x8 )Q346( x3 , x4 , x5 )Q67 ( x6 , x7 )

Q6 ( x6 )2 Q5 ( x5 )Q4 ( x4 )
Q25( x2 , x5 )Q24( x2 , x4 )Q13( x1, x3 )

Q3 ( x3 )Q2 ( x2 )
W25
X4
X6
W6
W568
X5
X5
X8
10
クラスター変分法


{P |   C}  arg minD[Q | P] Q ( x )  Q ( x ), Q ( x )  1
{Q |C} 
x \ x
x


DQ P  DQ13 | W13  DQ346 | W346
 DQ24 | W24   DQ25 | W25 
 DQ67 | W67   DQ568 | W568
 DQ3 | W3   DQ4 | W4 
 DQ5 | W5   2DQ6 | W6   ln Z
X1
W13
W3
Q2 ( x2 )  Q24( x2 , x4 )  Q25( x2 , x5 ),
x4
X2
W24
X3
X4
X3
X4
X3
W346
X2
W2
X5
W5
X6
X7
X6
W25
W4
X4
X6
X2
X6
W6
W568
X5
X5
X8
x5
Q3 ( x3 )  Q13( x1, x3 )  Q346( x3 , x4 , x6 ), 
x1
x4
x6
第48回物性若手夏の学校
11
周辺確率分布の近似表式
W346(a3 , a4 , a6 )M 313(a3 )M 424 (a4 ) 


 M 667 (a6 )M 6568(a6 ) 

P346(a3 , a4 , a6 ) 
W346(a3 , a4 , a6 )M 313(a3 )M 424 (a4 ) 


 M 667 (a6 )M 6568(a6 ) 
a3 a4 a6
A2
A1
M313( A3 )
A3
M667 ( A6 )
A7
W346
M 424 ( A4 )
A4
A5
A6
A8
第48回物性若手夏の学校
M 6568( A6 )
12
数値実験
P3 (1)  0.9896 P3 (1)  0.0104
P5 (1)  0.5500 P5 (1)  0.4500
P8 (1)  0.5607 P8 (1)  0.4393
Cluster Variation
Method
P3 (1)  0.9896 P3 (1)  0.0104
P5 (1)  0.5500 P5 (1)  0.4500
P8 (1)  0.5640 P8 (1)  0.4360
Exact
X1
X2
W24
W13
Pi (ai )   P(a1, a2 , a3, a4 , a5 , a6 , a7 , a8 )
a \ai
X3
W3
W6
W67
X7
第48回物性若手夏の学校
W346
X6
W25
X4
W4
W568
X5
W5
X8
13
線形応答理論の応用
(K. Tanaka, IEICE, vol.E86-D, no.7, pp.1228-1242, 2003.)
（人為的に小さなゆらぎを与えてその応答を見ることで詳細を知ることができる．）
Pij (m, n)  Pi (m) Pj (n)
A2
A1
  Pj (n) 

 lim 

hi 0
h
i


A3
(i )
A4
A5
A6
a  ai i  1,2,,8
A8
A7
~
~
 Pj (n)  Pj (n)  Pj (n)   n,a j P(a)   n,a j P(a)
aa

(i )
Deviation of Average at Node j with respect to External Field at Node i

1
~
P(a)  ~ P(a)exp hi ai ,m
Z
第48回物性若手夏の学校

14
数値実験


Pr ATuberculosis  Present ADyspnea Present


Pr ATuberculosis  Present, ADyspnea Present 0.0082


 0.0187
Pr ADyspnea Present
0.4393


A2
A1
W24
W13
A3
W3
W6
W67
A7
第48回物性若手夏の学校
A4
W346 W
4
A6
W568
W25
A5
W5
A8
15
ベイジアンネットの今後の動向
自動化が急務．
パラメータのデータからの学習
EM アルゴリズム
クラスター変分法の更なる拡張の試み
Region Graph Method
Max-Product Method
第48回物性若手夏の学校
16
確率推論と統計力学の言葉の対応
頂点(Node)
信念(Belief)
カルバック・ライ
ブラー情報量
確率伝搬法・
Belief
Propagation・
Junction Tree
Algorithm
第48回物性若手夏の学校
格子点(Site)
一体分布関数
自由エネルギー
転送行列法・
ベーテ近似
17
本講義を通してのまとめ
モノの理とコトの技の接点
たくさんが関連
キーワードは「ベイズの公式」
ゆらぎを巧みに扱えるシステムのデザイン
物理学のバージョンアップ
第48回物性若手夏の学校
18
確率推論についての参考文献
J. Pearl, “Probabilistic Reasoning in
Intelligent Systems: Networks of Plausible
Inference”, Morgan Kaufmann, 1988.
本村陽一, “ベイジアンネットソフトウェア”,人工
知能学会誌, vol.17, no.5, pp.559-565, 2002.
K. Tanaka, “Probabilistic Inference by means
of Cluster Variation Method and Linear
Response Theory”, IEICE Transactions on
Information and Systems, vol.E86-D, no.7,
pp.1228-1242, 2003
第48回物性若手夏の学校
19
本講義で取り上げなかったトピックス
(符号理論・移動体通信) の参考文献
樺島祥介 “物理の世界/学習と情報の平均
場理論”, 岩波書店, 2002.
樺島祥介 “コトの物理学 ---誤り訂正符号
を例として---”,日本物理学会誌, vol.58,
no.4, pp.239-246, 2003.
田中利幸, ``移動体通信技術とスピングラ
スとの意外な関係”, 日本物理学会誌,
vol.56, no.9, pp. 660-666, 2001.
第48回物性若手夏の学校
20
これから参入したい方のために
西森，樺島，田中他著, “特集/知識情報処理の統計力学的
アプローチ”, 数理科学1999 年 12 月号.
西森秀稔, “新物理学選書/スピングラス理論と情報統計力
学” 岩波書店, 1999.
H. Nishimori, “Statistical Physics of Spin Glasses and
Information Processing: An Introduction”, Oxford
University Press, 2001.
M. Opper and D. Saad (eds), “Advanced Mean Field
Methods --- Theory and Practice ---”, MIT Press, 2001.
田中・樺島編, “ミニ特集/ベイズ統計・統計力学と情報処理”,
計測自動制御学会誌「計測と制御」2003年8月号
第48回物性若手夏の学校
21
What is SMAPIP?
http://www.smapip.eei.metro-u.ac.jp./
文部科学省科学研究費補助金特定領域研究
２００２年４月－２００６年３月
第48回物性若手夏の学校
22
本講義の関連イベントのお知らせ
SMAPIP 講習会 “確率的アルゴリズムによる情報処理”
2003年11月10日 (ぱるるプラザ京都)
講師(敬称略): 福島孝治(東大)
渡辺治(東工大)
喜多一（京大）
http://www.statp.is.tohoku.ac.jp/~kazu/SMAPIP/2003/tutorial/


情報論的学習理論ワークショップ(IBIS2003)
2003 年11 月 11-12 日 (ぱるるプラザ京都)
http://www.ibis2003.org/
ベイジアンネットセミナー (BN2003)
2003 年11 月 13-14 日 (ぱるるプラザ京都)
http://www.bn2003.org/
第48回物性若手夏の学校
23
本講義の関連イベントのお知らせ
Satellite Meeting of STATPHYS 22
“Statistical Physics of Disordered Systems
and Its Applications (SPDSA2004)”
2004 年 7 月 12-15 日, 湘南国際会議村, 葉山町
組織委員長：西森秀稔(東工大)
http://www.stat.phys.titech.ac.jp/~nishi/SPDSA/
第48回物性若手夏の学校
24

Download Report