Document

Report
Propagating beliefs in spinglass models
Yoshiyuki Kabashima
Dept. of Compt. Intel. & Syst. Sci.
Tokyo Institute of Technology
[email protected]
@ 15/7/2003
Tokyo Institute of Technology
1
Background and Motivation


Active research on belief propagation (BP) in
information sciences (IS)
Similarity to methods in physics


TMM & Bethe approx.
Difference in interest


Physics ⇒ obtained solutions
IS ⇒ dynamics of the algorithm
may cause unexpected developments in both
fields
Hayashibara&SMAPIP
@15/7/2003
Tokyo Institute of Technology
2
Purpose and Results


Purpose:analyze dynamics of BP when
employed in spin-glass models
Results:


Macro. dyn. of BP ⇒ RS solution
Micro. stability of BP ⇔ AT condition
Hayashibara&SMAPIP
@15/7/2003
Tokyo Institute of Technology
3
Outline





SG model in Bayesian framework
Belief propagation
Macro. dyn. and RS solution
Micro. stability and AT condition
Summary
Hayashibara&SMAPIP
@15/7/2003
Tokyo Institute of Technology
4
Spin-glass models

SG models on a random (Bethe) lattice
M
H S | J    J 
 1



 S
l
lL
K-body interaction
C-bonds/spin
Randomly constructed for other aspects





1 J0 / C J
1 J0 / C J
PJ   
 J  J / C 
 J  J / C
2
2
Hayashibara&SMAPIP
@15/7/2003
Tokyo Institute of Technology

5
SM and Bayesian Statistics

Boltzmann dist. = Bayes formula
 PJ  | S
M
exp H S | J 

Z J 
 1
PJ  | S 


M
S



exp J   Sl 
lL    

P J  | S  
2 coshJ  
 PS | J 
1
Magnetization = Posterior average
ml 
Hayashibara&SMAPIP
@15/7/2003
 S exp H S | J 
l
S
Z J 
  Sl PS | J 
S
Tokyo Institute of Technology
6
Graph Expression

Expression by a bipartite graph
K 3
J1
J2
J3
J4
JM
…
P J 1 | S 
…
…
S1
Hayashibara&SMAPIP
@15/7/2003
S2
C4
S3
PS 2 | J 
Tokyo Institute of Technology
SN
7
Belief Propagation

Iterative inference by passing beliefs
J1
J2
J4
J3
JM
…
…
t
ml
mˆ l
t
…
S1
Hayashibara&SMAPIP
@15/7/2003
S2
S3
Tokyo Institute of Technology
SN
8
More Precisely
mˆ t l 1  tanh J    mt k

kL   \ l
 t

1
t
ml  tanh  tanh mˆ l

  M l \ 




 



t
ml :Posterior average when J  is left out.
 
ˆ t l
tanh1 m
: Effective field when

t
1
t 
ml  tanh  tanh mˆ l 
 M l 

Hayashibara&SMAPIP
@15/7/2003
 
J
comes in.
:Estimator
Tokyo Institute of Technology
9
Macro. Dyn. vs. RS Solution

Distribution (histogram) of beliefs
 x  m , ˆ xˆ   (1 / NC )  xˆ  mˆ t l 



l 1 M l 
Known result for finite C:
N
 x   (1 / NC )
t
l 1



N
t
M l
t
l
Tree approximation (resampling graph/update)
Density evolution ⇒ RS solution
K 1
K 1
 t 1


t
ˆ
ˆ
ˆ







x

dx

x

x

tanh

J
x




l
l
l



l 1
l 1

 J


C 1

 C 1

t
1
 t x  


dxˆ xˆ   x  tanh  tanh xˆ  







1


1





Richardson & Urbanke (2001) Vicente, Saad, YK (2000)
Hayashibara&SMAPIP
@15/7/2003
Tokyo Institute of Technology
10
Novel Result for Infinite C

Central limit theorem for infinite C

Evolution of average and variance

 h  Et
exp 
t

C 1
C 1
2
F



 t h     dxˆˆ t xˆ   h   tanh1 xˆ  
 1
 1
2F t




2




Natural iteration of RS SP eqs.
 
 
2
t 1
t K 1
t 1
t K 1

, F  J  Q
 E  J 0 M
 t
t
t
2
M

Dz
tanh
F
z

E
,
Q

Dz
tanh





Hayashibara&SMAPIP
@15/7/2003

Tokyo Institute of Technology
 F z  E
t
11
Experimental Validation

SK model(N=1000,J=1,T=0.5)
J 0  1.5
(AT stable)
Hayashibara&SMAPIP
@15/7/2003
J 0  0.5

(AT unstable)
N
1
D t   mlt  mlt 1
N l 1
Tokyo Institute of Technology

2
12
Microscopic Instability


Possible microscopic instability while BP
seems to macroscopically converge
Stability analysis of the fixed point
ht l 1 
  
 M l \
tanhJ 
 m
kL
k
\l


1   tanhJ   mk 
kL   \ l


Hayashibara&SMAPIP
@15/7/2003

2
 
jL
Tokyo Institute of Technology
\l
1  m2j
mj
 htj
13
Evolution of Perturbation
Dist. of Perturb. f t  y   1 / NC   y  ht l 
l 1 M l 
Perturbation Evolution
N



f  y     y  is attractive
⇔ the fixed point(=RS solution) is stable
f
t 1
C 1, K 1
 y     dyl f t yl 
 1,l 1
Hayashibara&SMAPIP
@15/7/2003
K 1




tanhJ   xl
2
C

1
K

1


1  xk
l 1
 y 

 yk 
2
K 1
 1

 k 1 xk




1

tanh

J
x





l




l 1




Tokyo Institute of Technology
J  , xl
14
Pictorial Expression

What is performed?
(t  1)th update
tth update:
J1
J2
S1
h
S2
t
21
J4
J3
S3
JM
…
…
…S
J1
J1
J2
S1
J4
J3
S2
S3
h
…
…
…
SN
S1
h24t
Hayashibara&SMAPIP
@15/7/2003
J4
J3
JM
N
t
23
J2
h
t 1
21
Tokyo Institute of Technology
S2
S3
h
JM
…
…
…S
t 1
23
N
h
t 1
24
15
Meaning of P. Evolution


Link to known results for infinite C
Central limit theorem:

t

1
y

a
f t y 
exp 
t

2
b
2bt



2

 :Gaussian dist.


P. Evolution → Update of average & variance
t 1
K 2
t



a

(
K

1
)

J
M
1

Q
a
0

 t 1
2
K 2
2


b

(
K

1
)

J
Q
Dz
1

tanh




Hayashibara&SMAPIP
@15/7/2003

Tokyo Institute of Technology

2
  
Fz  E b O a
t
t 2
16
Meaning of P. Evolution

Critical conditions for growth of
fluctuation
K 2

1  Q  1 :Average
(
K

1
)

J
M
0


2
K 2
2


(
K

1
)

J
Q
Dz
1

tanh
FzE






  1 :Variance
2
For K=2 (SK model)


Average → Tf: Para-Ferro transition
Variance → TAT: AT condition
Hayashibara&SMAPIP
@15/7/2003
Tokyo Institute of Technology
17
Analysis for finite C


Is P. evolution equivalent to AT analysis even
for finite C?

AT analysis for finite C is complicated.

But, P. evolution is (numerically) possible.
K=2 (Wong-Sherrington model)

Paramagnetic solution
Known result
Average→T





C

1
tanh

J

1
f

J
•Klein et al (1979)

2

C  1 tanh J   1 Variance→TAT •Mezard & Parisi

J

(1987)
Hayashibara&SMAPIP
@15/7/2003
Tokyo Institute of Technology
18
Analysis for Finite C

Ferromagnetic solution
Numerical evaluation of Tpevol: New result!
N=2000, K=2, C=4,
20000MCS/Spin
D: Tpevol in Ferro phase
Hayashibara&SMAPIP
@15/7/2003
Tokyo Institute of Technology
19
Summary

Close relationship between BP and the replica
analysis




Macro. dyn. ⇒ RS solution
Micro. stability ⇔AT condition
This correspondence may be useful for AT
analysis for SG models of finite connectivity.
Application to CDMA multiuser detection
(Kabashima, to appear in J. Phys. A, 2003)
Hayashibara&SMAPIP
@15/7/2003
Tokyo Institute of Technology
20

similar documents