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

物理フラクチュオマティクス論
Physical Fluctuomatics
第7回物理モデルと統計モデル
7th Physical models and statistical models
東北大学大学院情報科学研究科応用情報科学専攻
田中和之(Kazuyuki Tanaka)
[email protected]
http://www.smapip.is.tohoku.ac.jp/~kazu/
本講義のWebpage:
http://www.smapip.is.tohoku.ac.jp/~kazu/PhysicalFluctuomatics/2007/
22 May, 2007
物理フラクチュオマティクス論（東北大）
1
今回の講義ノート
田中和之著: 確率モデルによる画像処理技術入門,
第5章, 森北出版, 2006.
参考図書
西森秀稔：相転移・臨界現象の統計物理学，
培風館，2005．
宮下精二：熱・統計物理学，培風館，1993．
22 May, 2007
物理フラクチュオマティクス論（東北大）
2
たくさんが関連して集まり構成されたシステム：
情報と物理が扱う対象に共通する概念
ビットが集まってデータを形成し，コトとなる．
主な研究対象
情報工学：コト
データ
物理：モノ
０,1
ビット
101101
110001
01001110111010
10001111100001
10000101000000
11101010111010
1010
コト（データ）
物質・自然現象
並びをきちんと決めることによって意味のある文章になる．
共通点：たくさんが関連
分子が集まって物質を形成し，モノになる．
分子
分子同士は引っ張り合っている．
22 May, 2007
物理フラクチュオマティクス論（東北大）
モノ（物質）
3
確率的情報処理における計算の壁
不確実性を確率・統計を用いて表現することの代償
起こりやすいことも起こりづらいこともまじめ
に考慮して計算
計算量的困難
近似アルゴリズムの導入による計算困難の打破
22 May, 2007
物理フラクチュオマティクス論（東北大）
4
ポイントは何か
2N 通りの和が計算できるか？
    f x , x ,, x 
x1 T,F x2 T,F
xN T,F
1
2
このプログラムでは
N=10個のノードで1秒かかるとしたら
N=20個で約17分，
N=30個で約12日，
N=40個で約34年かかる．
N
a  0;
for(x1  T or F){
for(x2  T or F){

for(x N  T or F){
a  a  f  x1 , x2 , , xL ;
}

}
}
22 May, 2007
物理フラクチュオマティクス論（東北大）
N 重ループ
5
何故，確率的情報処理に物理的視点が有効なのか？
物質はたくさんの分子から構成されている
（1 mol の中に約N=1023個の分子）
分子と分子の間には分子間力が働いている．
 f x , x ,, x 
1
x1
x2
2
N
xN
のような多重和の大規模計算が宿命（厳密計算は断念）
近似理論によるアプローチ
統計科学による情報処理も同じ多重和の計算が要請される．
物理学的計算手法の情報処理への使い回しが可能
22 May, 2007
物理フラクチュオマティクス論（東北大）
6
確率的情報処理の要約
問題設定：社会的・工学的要請
情報通信技術，像情報処理，人工知能
モデル化：統計科学にもとづく定式化
評価関数，事後確率としての確率モデル化
アルゴリズム設計：物理的計算技法の転用
平均場理論をはじめとする近似理論の活用
性能評価：できれば統計的かつ解析的に行いたい!!
性能限界の導出
物理的手法の
転用が可能
アルゴリズム動作の統計的解析
22 May, 2007
物理フラクチュオマティクス論（東北大）
7
モノの理とコトの技の学術的循環
コトの技を通して
モノの理を鍛える
モノの理による
新たなコトの技の創出
共通の数理
情報統計力学
確率的情報処理
学術的循環
学術的循環
統計科学
物質の性質・自然現象の理解・予言
データからの情報の抽出・加工
モノの理
物理学
22 May, 2007
コトの技
情報工学
物理フラクチュオマティクス論（東北大）
8
自然現象と物理モデル
水はなぜ氷になるのだろう？
冬になると何故，結露が起こるのだろう？
鉄は何故，磁石になるのだろう?
鉄や銅は何故，電流は流すのだろう?
低温になると電気抵抗がなくなる物質があるらしい!!
高温になると鉄は磁石にならなくなるらしい!!
・
・
・
22 May, 2007
物理フラクチュオマティクス論（東北大）
9
強磁性体と確率モデル


線分で結ばれたノード対の
スピン同士が同じ向きを向
くほど確率が高くなるよう
に確率モデルを設計
22 May, 2007

スピンがいくつか集まると周りのスピンの状
態をよく見ながら自分の状態を決めないとい
けなくなるもっとたくさん集まったらどうなるか?
物理フラクチュオマティクス論（東北大）
10
強磁性体の確率モデルと More is different
p
p
p


マルコフ連鎖モン
テカルロ法による
サンプリング
p




p が小さい
p が大きい
無秩序状態
秩序状態
More is different.
ある p の値の付近で
ゆらぎが大きくなる．
量が増えれば質が変わる
22 May, 2007
物理フラクチュオマティクス論（東北大）
11
外場をもつ簡単な磁性体のモデル
exp(ha)
P( a ) 
 exp(ha)
a  1
e
h
h0
e

+1
-h
-1
a  1
h が正値なので白（下向きスピン）の確率が高くなる．
平均
m
 aP (a)  tanh( h)
h ：外場
a  1
分散
V a 
2
2
(
a
m
)
P
(
a
)

1
tanh
( h)

a  1
22 May, 2007
物理フラクチュオマティクス論（東北大）
12
相互作用をもつ簡単な磁性体のモデル
P(a1 , a 2 ) 

exp(Ja1a 2 )
 exp(Ja1a2 )
a1  1 a 2  1
a1  1
a2  1
J ：相互作用
J 0
eJ

e-J
-1
J が正値なので白白と黒黒の
確率が高くなる．
平均
m1 
分散
22 May, 2007
  a1P(a1 , a2 )  0
a1  1 a 2  1
V a1  

-1
+1
+1

eJ

+1
-1
e-J
-1
+1



2
(
a
m
)
 1 1 P(a1, a2 )  1
a1  1 a 2  1
物理フラクチュオマティクス論（東北大）
13
強磁性体の基本的な確率モデル

a  (a1, a2 ,, a N )


1
P(a )  exp - E (a ) 
Z
ai  1

Z   exp( - E ( a ))

a

E ( a )  - h  ai - J
i
B：すべての最近接ノード対の集合
 ai a j
ijB
エネルギーの役割を果たし，エネルギーが低い
状態ほど確率が高くなるようにデザインされる．

1 N
ai P(a ) を計算せよ．
問題： m 
N i 1 a

22 May, 2007
ai  -1
物理フラクチュオマティクス論（東北大）
h
J
h
J

どのノードから周りを
見回しても同じにみえる
14
イジングモデルと平均場近似

a  (a1, a2 ,, a N )
h
J
ai  1


1
P(a )  exp - E (a ) 
Z

E ( a )  - h  ai - J
i
h
 ai a j
J

どのノードから周りを
見回しても同じにみえる
ijB

1 N
ai P (a ) を計算せよ．
問題： m  lim lim

h  0 N   N i 1 a
自発磁化 (Spontaneous Magnetization)
22 May, 2007
物理フラクチュオマティクス論（東北大）
15
イジングモデルと平均場近似

E a   -h  ai - J  ai a j
i
ijB
(ai - m)(a j - m)  0
のとき確率が非常に大きくなると仮定
h
ai a j  m a j  m ai - m 2

E ( a )  -  ( h  4 Jm ) ai
Jm
Jm
i
Jm
Jm
i
22 May, 2007
物理フラクチュオマティクス論（東北大）
16
イジングモデルと平均場近似


1
P(a )  exp(- E (a ))   Pi (ai )
Z
i

E ( a )  -  ( h  4 Jm ) ai
i
確率変数 ax,y は互いに独立

1 N
m   ai P(a )  tanh(h  4 Jm)
N i 1 a
に対する固定点方程式
22 May, 2007
m  (m)
物理フラクチュオマティクス論（東北大）
17
固定点方程式と反復法
*
反復法
繰り返し出力を入力に入れることにより，
固定点方程式の解が数値的に得られる．
x1  ( x0 )
y
x2  ( x1 )
x1
x3  ( x2 )

22 May, 2007
*
m  (m )
固定点方程式
* x
m
1
0
物理フラクチュオマティクス論（東北大）
yx
y  (x)
x0
x
18
イジングモデルと平均場近似のまとめ
Pi (ai ) 
 
a1 a 2



P
(
a
  )
a i -1 a i 1
aN
1
exp((h  4 Jm)ai )
Zi
m
h
 ai Pi (ai )
Jm
Jm
i
Jm
Jm
a i  1
m  tanh((h  4 J )m)
22 May, 2007
物理フラクチュオマティクス論（東北大）
Jm：平均場
19
平均場近似の拡張
h
Bethe 近似
：有効場

1
Pi (ai ) 
exp((h  4 )ai )
Zi
1
Pij (ai , a j ) 
exp((h  3 )(ai  a j )  Jai a j )
Zi
Pi (ai ) 
 Pij (ai , a j )
h
a j  1
  arctanh(tanh(J ) tanh(h  3 ))
J 

h
 についての固定点方程式
Kikuchi 近似（クラスター変分法）
22 May, 2007
更なる拡張
物理フラクチュオマティクス論（東北大）
20
イジングモデルの確率変数の期待値


1
Pa  
exp h  ai  J  ai a j

Z
ijB
 i
lim




h
J
h
J


lim  ai P (a )
h  0 N   a
(a)
(b)
(c)
(d)
平均場近似（ワイス近似）
ベーテ近似
クラスター変分法（菊池近似）
厳密解（L. Onsager，C.N.Yang）
h=0 の場合は厳密解が1940年代
に得られている．
22 May, 2007
物理フラクチュオマティクス論（東北大）
1/ J
21
統計物理学におけるモデルの表現
Pr{A1  a1, A2  a2 ,, AN  a N }  P(a1, a2 ,, a N )
 

Pr{A  a}  P(a)
ギブス分布
分配関数
エネルギー関数


1
P(a )  exp( - E (a ))
Z
自由エネルギー
22 May, 2007

A  ( A1, A2 ,, AN )

Z   exp( - E ( a ))

a

F  - ln Z  - ln(  exp( - E ( a )) )

a
物理フラクチュオマティクス論（東北大）
22
統計物理学における基本原理


1
ギブス分布 P(a )  exp( - E (a ))
Z
は自由エネルギー最小の変分原理を満たし，
その最小値が – ln Z となる．

min{F [Q ] |  P (a )  1}  F [ P ]  - ln Z

a
Q




F [Q ]   E ( a )Q (a )   Q (a ) ln Q ( a )

a
22 May, 2007

a
物理フラクチュオマティクス論（東北大）
23
自由エネルギー最小の変分原理の具体的計算

min{F [Q ] |  Q (a )  1}  F [ P ]  - ln Z
Q

a











LQ  F Q -   Q(a) - 1   ( E (a )  ln Q(a ))Q(a ) -   Q(a ) - 1
 
 
 

 a
 a
 a



LQ
  E (a )  ln Q(a )  1 -   0
Q(a )




exp
E
(
a
)


ˆ
Q(a ) 
  P( a )
Qˆ (a)  exp- E(a)   - 1
 exp- E(a)
規格化条件
22 May, 2007
物理フラクチュオマティクス論（東北大）

a
24
カルバック・ライブラー情報量
と自由エネルギー

  Q( a ) 
DQ P    Q(a ) ln    0

 P(a ) 
a




 Q(a )  0,  Q(a )  1



a




Q(a)  P(a)  DQ P  0


1
P(a )  exp( - E (a ))
Z
 


D[Q | P]   Q(a )E (a )   Q(a ) ln Q(a )  ln Z


a
a

F [Q ]
 F [Q]  ln Z
自由エネルギーが最小になるとき，カルバック・ライブラー情報量も最小となる．
22 May, 2007
物理フラクチュオマティクス論（東北大）
25
平均場近似の情報論的理解


Q(s )    Qx , y s x , y  と
 ( x , y )



1
Pa   exp( - E (a ))
Z
の距離をカルバック・ライブラー情報量

  Q(a ) 
DQ P    Q(a ) ln  

 P(a ) 
a
で計って最小になるように周辺確率分布 Qi (ai )
を決定する Qi (ai )   Q(a )      Q(a )

a \ ai
22 May, 2007
a1 a 2
物理フラクチュオマティクス論（東北大）
ai -1 ai 1
aN
26
平均場近似における
カルバックライブラー情報量

  Q(a ) 
DQ P    Q(a ) ln  

 P(a ) 
a

Qi (ai )   Q(a )


 
Q(a )   Qi (ai ) 


 i

a \ ai
   
a1 a 2

   Q(a )
a i -1 a i 1
aN
DQ P  FMF Qi   lnZ 
FMF [{Q x, y }]  -h 
 Qi ( )
i   1
-J
 (  Qi ( ))(  Q j ( ))    Qi  ln Qi  
ijB   1
22 May, 2007
  1
i   1
物理フラクチュオマティクス論（東北大）
27
カルバック・ライブラー情報量の最小化
と平均場方程式
{Qˆ i ( )}  arg min{D[Q | P] |  Qi ( )  1, i  }
{Qi }

条件付き変分
頂点 i の最
近接ノード
の集合


1

Qˆ i   
exp  (h  J   Qˆ j ( )) 


Zi
j  Bi   1


Bi
i



Z i   exp  (h  J   Qˆ j ( )) 


  1
j

B



1
i


｛Qi} に対する固定点方程式
22 May, 2007
物理フラクチュオマティクス論（東北大）
28
イジングモデルにおける
周辺確率分布の直交関数展開

a  (a1, a2 ,, a N )
ai  1


Qi (ai )   Q(a )      Q(a )

a \ ai
a1 a 2
ai -1 ai 1

mi   ai Qa  

a
1 1
Qi (ai )   mi ai
2 2
 Qi (ai )  c  dai
aN
 ai Qi (ai )
a i  1
(ai 2  1)
1
1
 Qi (ai )   (c  dai ) 2c  c  2  Qi (ai )  2
a i  1
a i  1
a i  1
1
1
 ai Qi (ai )   ai (c  dai ) 2d  d  2  ai Qi (ai )  2 mi
a i  1
22 May, 2007
a i  1
物理フラクチュオマティクス論（東北大）
a i  1
29
通常の平均場方程式へ

E ( a )  - h  ai - J
i
 ai a j
h
h
J
ijB
J
m1  m2    mN  m
1 1
1 1
ˆ
Qi (ai )   mi ai   ma i
2 2
2 2

どのノードから周りを
見回しても同じにみえる

 1
1

Qˆ i (ai ) 
exp (h  J   Qˆ j ( ))ai  
exp((h  4 Jm)ai )


Zi
Zi
jBi   1


m  tanh(h  4 Jm)
固定点方程式
22 May, 2007
N

1
ai P ( a )  m

N i 1 a
物理フラクチュオマティクス論（東北大）
30
今回のまとめ
統計物理学と情報処理の不思議な共通点
強磁性体の確率モデル
平均場理論
ギブス分布と自由エネルギー．
自由エネルギーとカルバックライブラー情報量．
平均場近似の情報論的理解．
22 May, 2007
物理フラクチュオマティクス論（東北大）
31

Download Report