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

物理フラクチュオマティクス論
Physical Fluctuomatics
応用確率過程論
Applied Stochastic Process
第6回 グラフィカルモデルと物理モデル
6th Graphical model and physical model
東北大学 大学院情報科学研究科 応用情報科学専攻
田中 和之(Kazuyuki Tanaka)
[email protected]
http://www.smapip.is.tohoku.ac.jp/~kazu/
物理フラクチュオマティクス論(東北大)
1
今回の講義ノート
田中和之著: 確率モデルによる画像処理技術入門,
第5章, 森北出版, 2006.
参考図書
西森秀稔:相転移・臨界現象の統計物理学,
培風館,2005.
宮下精二:熱・統計物理学,培風館,1993.
物理フラクチュオマティクス論(東北大)
2
たくさんが関連して集まり構成されたシステム:
情報と物理が扱う対象に共通する概念
ビットが集まってデータを形成し,コトとなる.
主な研究対象
情報工学:コト
データ
物理:モノ
0,1
ビット
101101
110001
01001110111010
10001111100001
10000101000000
11101010111010
1010
コト(データ)
物質・自然現象
並びをきちんと決めることによって意味のある文章になる.
共通点:たくさんが関連
分子が集まって物質を形成し,モノになる.
分子
分子同士は引っ張り合っている.
物理フラクチュオマティクス論(東北大)
モノ(物質)
3
何故,確率的情報処理に物理的視点が有効なのか?
物質はたくさんの分子から構成されている
(1 mol の中に 約N=1023個の分子)
分子と分子の間には分子間力が働いている.
 f x , x ,, x 
1
x1
x2
2
N
xN
のような多重和の大規模計算が宿命(厳密計算は断念)
近似理論によるアプローチ
統計科学による情報処理も同じ多重和の計算が要請される.
物理学的計算手法の情報処理への使い回しが可能
物理フラクチュオマティクス論(東北大)
4
強磁性体と確率モデル
P(1,1)  P(1.  1)  p
P(1,1)  P(1.  1)
1
 p
2
p
p
p

a1  1 a2  1


p


1
1

1
1
1
1
P(1.  1)  P(1.  1)  P(1,1)  P(1,1)
物理フラクチュオマティクス論(東北大)
5
強磁性体と確率モデル
p
a1  1 a2  1
p

1
1


1
1
1
1

# of BlueLines 1
P(a )  p
(  p) # of Red Lines
2
=
>
赤い線が少ないほど確率
が高くなるように確率モデ
ルは設計されている
>
スピンがいくつか集まると周りのスピンの状
態をよく見ながら自分の状態を決めないとい
けなくなる もっとたくさん集まったらどうなるか?
物理フラクチュオマティクス論(東北大)
6
強磁性体の確率モデルと More is different
p
p
p


マルコフ連鎖モン
テカルロ法による
サンプリング
p



1
p
2

1
p
2
p が小さい
p が大きい
無秩序状態
秩序状態
More is different.
ある p の値の付近で
ゆらぎが大きくなる.
量が増えれば質が変わる
物理フラクチュオマティクス論(東北大)
7
外場をもつ簡単な磁性体のモデル
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
物理フラクチュオマティクス論(東北大)
8
相互作用をもつ簡単な磁性体のモデル
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 
分散
  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
物理フラクチュオマティクス論(東北大)
9
強磁性体の基本的な確率モデル

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V
ai  1
E:すべての最近接ノード対の集合
a a
{i , j}E
i
h
j
エネルギーの役割を果たし,エネルギーが低い
状態ほど確率が高くなるようにデザインされる.

1 N
ai P(a ) を計算せよ.
問題: m 
N i 1 a

物理フラクチュオマティクス論(東北大)
J
(V , E )
h
J
どのノードから周りを
見回しても同じにみえる
10
イジングモデルと平均場近似

a  (a1, a2 ,, a N )
h
h
J
ai  1
J


1
P(a )  exp  E (a ) 
Z

E(a )  h ai  J
iV
(V , E )
a a
{i , j}E
i
j
どのノードから周りを
見回しても同じにみえる

1 N
ai P (a ) を計算せよ.
問題: m  lim lim

h  0 N   N i 1 a
自発磁化 (Spontaneous Magnetization)
物理フラクチュオマティクス論(東北大)
11
イジングモデルと平均場近似

Ea   h ai  J  ai a j
iV
{i , j }E
(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V
物理フラクチュオマティクス論(東北大)
12
イジングモデルと平均場近似


1
P(a )  exp( E (a ))   Pi (ai )
Z
iV

E (a )   (h  4 Jm)ai
iV
確率変数 ai は互いに独立

1 N
m   ai P(a )  tanh(h  4 Jm)
N i 1 a
に対する固定点方程式
m  (m)
物理フラクチュオマティクス論(東北大)
13
Fixed Point Equation and
Iterative Method
•Fixed Point Equation
14 January, 2010
 
*  *
M  M
Hokkaido University GCOE Tutorial
(Sapporo)
14
Fixed Point Equation and
Iterative Method
•Fixed Point Equation
 
*  *
M  M
•Iterative Method
yx
y
y  (x)
0
14 January, 2010
M*
Hokkaido University GCOE Tutorial
(Sapporo)
x
15
Fixed Point Equation and
Iterative Method
•Fixed Point Equation
 
*  *
M  M
•Iterative Method
yx
y
y  (x)
0
14 January, 2010
M*
Hokkaido University GCOE Tutorial
(Sapporo)
M0
x
16
Fixed Point Equation and
Iterative Method
•Fixed Point Equation
 
*  *
M  M
•Iterative Method
 


M1   M 0
yx
y
M1
0
14 January, 2010
y  (x)
M*
Hokkaido University GCOE Tutorial
(Sapporo)
M0
x
17
Fixed Point Equation and
Iterative Method
•Fixed Point Equation
 
*  *
M  M
•Iterative Method
 
 


M1   M 0


M 2   M1
M1
0
14 January, 2010
yx
y
y  (x)
M * M1
Hokkaido University GCOE Tutorial
(Sapporo)
M0
x
18
Fixed Point Equation and
Iterative Method
•Fixed Point Equation
 
*  *
M  M
•Iterative Method
 
 


M1   M 0


M 2   M1
M1
M2
0
14 January, 2010
yx
y
y  (x)
M * M1
Hokkaido University GCOE Tutorial
(Sapporo)
M0
x
19
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

14 January, 2010
Hokkaido University GCOE Tutorial
(Sapporo)
20
平均場近似による周辺確率分布
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)
物理フラクチュオマティクス論(東北大)
Jm:平均場
21
平均場近似の拡張
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
イジングモデルの確率変数の期待値


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年代
に得られている.
物理フラクチュオマティクス論(東北大)
1/ J
23
統計物理学におけるモデルの表現
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
自由エネルギー

A  ( A1, A2 ,, AN )

Z   exp(  E ( a ))

a

F   ln Z   ln(  exp(  E ( a )) )

a
物理フラクチュオマティクス論(東北大)
24
統計物理学における基本原理


1
ギブス分布 P(a )  exp(  E (a ))
Z
は自由エネルギー最小の変分原理を満たし,
その最小値が – ln Z となる.

min{F [Q ] |  Q (a )  1}  F [ P ]   ln Z

a
Q




F [Q ]   E ( a )Q (a )   Q (a ) ln Q ( a )

a

a
物理フラクチュオマティクス論(東北大)
25
自由エネルギー最小の変分原理の具体的計算

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)
規格化条件
物理フラクチュオマティクス論(東北大)

a
26
カルバック・ライブラー情報量
と自由エネルギー

  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
自由エネルギーが最小になるとき,カルバック・ライブラー情報量も最小となる.
物理フラクチュオマティクス論(東北大)
27
平均場近似の情報論的理解

Q(a ) 
 Qi (ai )
i
と


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
a1 a 2
物理フラクチュオマティクス論(東北大)
ai 1 ai 1
aN
28
平均場近似における
カルバックライブラー情報量

  Q(a ) 
DQ P    Q(a ) ln  

 P(a ) 
a

Q(a ) 

Qi (ai )   Q(a )

 Qi (ai )
a \ ai
   
i
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
  1
物理フラクチュオマティクス論(東北大)
i   1
29
カルバック・ライブラー情報量の最小化
と平均場方程式
{Qˆ i ( )}  arg min{D[Q | P] | Qi ( )  1, i V }
{Qi }
ノード i のすべての最近接
ノードの集合
i  j {i, j} E
i

条件付き変分


1
ˆ
ˆ
Qi    exp  (h  J   Q j ( )) 
Zi
ji   1




ˆ
Z i   exp  (h  J   Q j ( )) 
  1
ji   1


{Qi} に対する固定点方程式
物理フラクチュオマティクス論(東北大)
30
イジングモデルにおける
周辺確率分布の直交関数展開

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
a i  1
物理フラクチュオマティクス論(東北大)
a i  1
31
通常の平均場方程式へ

E(a )  h ai  J
iV
 ai a j
h
h
J
{i , j}E
J
m1  m2    mN  m
1 1
1 1
ˆ
Qi (ai )   mi ai   ma i
2 2
2 2
V
どのノードから周りを
見回しても同じにみえる

 1
1
Qˆ i (ai )  exp (h  J   Qˆ j ( ))ai   exp((h  4 Jm)ai )
Zi
ji   1

 Zi
m  tanh(h  4 Jm)
固定点方程式
N

1
ai P ( a )  m

N i 1 a
物理フラクチュオマティクス論(東北大)
32
今回のまとめ
統計物理学と情報処理の不思議な共通点
強磁性体の確率モデル
平均場理論
ギブス分布と自由エネルギー.
自由エネルギーとカルバックライブラー情報量.
平均場近似の情報論的理解.
物理フラクチュオマティクス論(東北大)
33