.1.1.1 S H(S) T canonical distribution P (S) = e βh(s) Z(β) (1) β = (k B T ) 1 k B Z(β) = Tr S e βh(s) partition function free energy F = β 1 ln Z(β)

58 1 HAL9000 Google Amazon SF 1 [1, ] 1 E-mail: kaba@dis.titech.ac.jp

.1.1.1 S H(S) T canonical distribution P (S) = e βh(s) Z(β) (1) β = (k B T ) 1 k B Z(β) = Tr S e βh(s) partition function free energy F = β 1 ln Z(β) H(S)e βh(s) U = Tr H(S)P (S) = Tr S S Z(β) () U = ln Z(β) = (βf ) (3) β β U F S = 1 T (U F ) = k Bβ β ln Z(β) + k B ln Z(β) (4).1. V m N i(= 1,,..., N) q i p i S = {(q 1, p 1 ), (q, p ),..., (q N, p N )} H(S) = N ( pi ) m + Φ(q i) Φ(q) q 0 h Tr S h 3N (N!) 1 N (dq idp i ) Tr S (5) Z(β) = (πmk BT ) 3N/ V N h 3N N! (6) U = 3N ln Z(β) = β β = 3Nk BT Tr S (7)

C = U T = k Bβ ln Z(β) β = 3Nk B (8) p p = ( / V )F F = β 1 ln Z(β) pv = Nk B T (9).1.3 Ising model i S i {+1, 1} H(S) = J (ij) S i S j h N S i (10) J > 0 h (ij) J > 0 (1) T c M h lim M h 0 { > 0 T < T c = 0 T > T c (11) phase transtion (3) (7) (8) (10) Tr S h = 0 N [3, 4] N

...1 N x {0, 1} N x y y x x P (x) x P (y x) y P (x) P (y x) y x P (x) P (y x) [5] [ ] y ˆx(y) = (ˆx i (y)) BER(ˆx( )) = 1 N N Pr(ˆx i (y) x i ) (1) BER(ˆx( )) 1 N ( ) Tr min N {P y i(x i y)}p (y) x i {0,1} (13) P (y) = Tr x P (y x)p (x) (14) P (x y) = P (y x)p (x) P (y) (15) P i (x i y) = Tr x\xi P (x y) P (x y) x i x j i marginal posterior distribution A\a A a ˆx opt i (y) = argmax {P i (x i y)} (16) x i {0,1} argmax x {f(x)} f(x) x (16) [ ] x y P (x, y) = P (y x)p (x) = P (x y)p (y) x ˆx(y) N δ(ˆx i(y) x i ) δ( ) 1 0 P (x, y) = P (x y)p (y) N BER(ˆx( )) = 1 N N Pr(ˆx i (y) x i )

= 1 N Tr y Tr x = 1 N Tr y = 1 1 N = 1 N 1 1 N N N N δ(ˆx i (y) x i )P (x y)p (y) x i {0,1} (1 δ(ˆx i (y) = x i ))P i (x i y)p (y) N Tr P i (ˆx i (y) y)p (y) y N ( Tr y Tr y ( max x i {0,1} {P i(x i y)}p (y) min x i {0,1} {P i(x i y)}p (y) ) ) (17) y P i (ˆx i (y) y) max {P i(x i y)} (18) x i {0,1} (16) (16) (13).. P (y x) P (x) probabilistic model y x probabilistic inference.3 P (x y) x {0, 1} N N y x

y.4.4.1 0.1 10% S {+1, 1} N H(S J) = (ij) J ij S i S j h N S i (19) (19) (10) J ij (ij) P (J ij ) statistical mechanics of disordered systems P (J ij ) (π J ) 1/ exp ( (J ij J 0 ) /( J ) ) pδ(j ij 1)+ (1 p)δ(j ij + 1) (0 < p < 1) frustration.4. (19) J = (J ij ) J P (S J) = 1 exp ( βh(s J)) (0) Z(J, β) Z(J, β) = Tr S exp ( βh(s J)) J S i = Tr S S i P (S J) J [ S i m ] = Tr J ( Tr S S ip (S J) ) m P (J) (1) (i = 1,,..., N; m = 1,,...) J [ ]

.4.3 J S J infinite range model [, 6, 7] replica method (1) ( ) m [ S i m ] = lim Tr Tr S n 0 ip (S J) Z n (J, β)p (J) () J S P (S J) = exp( βh(s J))/Z(J, β) Z(J, β) = Tr S exp( βh(s J)) n m = 1,,... N ( ) m Tr Tr S ip (S J) Z n (J, β)p (J) J S ( ) n = Tr Tr J S1 S 1,S,...,S n i Si... Si m exp β H(S a J) P (J) (3) S 1, S,..., S n J repilica P (J) J ( ) ) H(S 1, S,..., S n ) = 1 β ln (Tr J exp β a=1 n H(S a J) a=1 P (J) n (3) n n N n R () (3) cavity method J N P (J) J cavity gauge theory P (J) Nishimori temperature (4).5

1..1 (13) performance evaluation approximate inference algorithm [8] 3 mean field approximation 3.1 molecular field approximation [9] h = 0 z 1(a) i S i S i i i j i S j S j S j 1(b) S k (k = 1,,..., N) S k = m S i Hi eff (S i ) = JS i S j = zjms i (5) j i (5) zjm zjm molecular field mean field S i (5) S i m S i = S i {+1, 1} S i e βzjms i cosh(βzjm) = tanh(βzjm) = m (6) m β c = (zj) 1 { > β c ±m (m > 0) β β c m = 0 (7)

(a) (b) (c) θ zjm θ θ θ 1: (a) S i {+1, 1} (b) zjm (c) θ (b) (c) m θ β = β c β > β c m 0 u u = 1 N H(S) = J S i S j J S i S j = zj N N m (8) c (ij) (ij) c = u T = k Bβ u β = k BzJβ m m β (6) T = T c = (k B β c ) 1 = zj/k B { 3k B /, T T c 0 c = 0, T T c + 0 (9) (30) 3. T c k B T c /J.7 k B T c /J = 4 T = T c Bethe approximation [10]

h = 0 i H(S) = J S i S j = JS i S j J S k S l (ij) j i (kl) k i,l i = JS i S j + H \i (S\S i ) (31) j i H \i (S\S i ) H(S) S i S i H \i (S\S i ) j i θ 1(c) S i θ cavity field H(S) i j i H eff (S i, {S j i }) = JS i S j (3) j i S j θ j i S i {S j i } (3) P (S i, {S j i }) exp ( βh eff (S i, {S j i }) ) x {+1, 1} A R e Ax e Ax = cosh(a) cosh(a) x 1 + x tanh(a) x {+1, 1} = cosh(a) 1 + x tanh(a) (33) = tanh(a) (34) P (S i, {S j i }) S i P (S i ) = P (S i, {S j i }) = 1 + S i tanh(βz ˆθ) {S j i } {+1, 1} z (35) ˆθ = 1 β tanh 1 (tanh(βj) tanh(βθ)) (36) ˆθ effective field cavity bias S i S i = m θ m = S i P (S i ) = tanh(βz ˆθ) (37) S i {+1, 1} θ θ H \i (S\S i ) S i i j i S j S i j z 1 S j {S k j\i } S i S j θ (37) z z 1 tanh(βθ) θ θ = (z 1)ˆθ = 1 β (z 1) tanh 1 (tanh(βj) tanh(βθ)) (38)

(38) θ (37) k B T c /J.886... cluster variation method [11, 1] 3.3 3.3.1 z d z = d N 1 infinite range model H(S) = J N N S i S j h S i (39) i>j N 1 O(N) m = N 1 S i (39) ( Jm H(S) = N + hm + 1 ) ( Jm = N N ) + hm + O(1) (40) ln N! N ln N N m [ 1, 1] S N! (N(1 + ( m)/)! ( (N(1 m)/)! ( ) 1 + m 1 + m = exp N ln + 1 m ln ( 1 m )) ) + O(1) (41) Z(β) = Tr S exp( βh(s)) = +1 1 dm exp ( Nβφ(m; β) + O(1)) (4) φ(m; β) = Jm hm + 1 ( ( ) 1 + m 1 + m ln + 1 m ( )) 1 m ln β (43) (4) N f = 1 ln Z(β) = Nβ min {φ(m; β)} (44) m [ 1,+1]

(a) (b) : (a) z = k + 1 = 3 (b) φ(m; β)/ m = 0 m = tanh (β(jm + h)) (45) 3 ( ( )) (N 1)J m = tanh β m + h N (46) N (45) (45) N 3.3. (1) z = k + 1 k Cayley tree (a) Bethe lattice (b) G 0 1 G g G g Z g θ g P (S) = exp(βθ g S)/( cosh (βθ g )) g 1 0 k g 1,,..., k S 0 S 1,..., S k g Z g Z g 1 θ g θ g 1 k k Z g 1 = Zg k β h + J S j S 0 exp(βθ g S j ) cosh (βθ g ) S 0,S 1,S,...,S k exp 3 (45) N 1 P N S i h O(1) φ(m; β) m N 1 P N S i h 0 β > J 1 m = ±m (m > 0) φ(m; β) N 1 P N S i h 0 [ m, +m ] j=1 j=1

= ( cosh(βj)) k Zg k ( ) 1 + S0 tanh(βj) tanh(βθ g ) k exp (βhs 0 ) S 0 {+1, 1} ( ) k cosh(βj)z g = cosh(β ˆθ cosh(β(h + kˆθ g )) (47) g ) θ g 1 = h + kˆθ g (48) ˆθ g = 1 β tanh 1 (tanh(βj) tanh(βθ g )) (49) g = 1 k k + 1 k+1 k+1 Z 0 = Z1 k+1 β h + J S j S 0 exp(βθ 1 S j ) cosh (βθ 1 ) S 0,S 1,S,...,S k+1 exp = ( cosh(βj)) k+1 Z1 k+1 ( ) 1 + S0 tanh(βj) tanh(βθ 1 ) k+1 exp (βhs 0 ) S 0 {+1, 1} ( ) k+1 cosh(βj)z 1 = cosh(β ˆθ cosh(β(h + (k + 1)ˆθ 1 )) (50) 1 ) θ 0 = h + (k + 1)ˆθ 1 (51) Z 0 tanh(βθ 0 ) G G (47) (48) (49) θ g ˆθ g j=1 ˆθ = 1 β tanh 1 (tanh(βj) tanh(βθ)) (5) θ = h + kˆθ (53) S c S c = tanh(β(h + (k + 1)ˆθ)) (54) z = k + 1 (5) (53) (38) (54) (37) 4 j=1 4

3.3.3 () z( O(1)) [13, 14] d 4 z O(1) O(ln N) N z O(1) L N L N L 1 + z + z(z 1) + z(z 1) +... + z(z 1) L 1 = 1 + z(z 1)L z N (55) z L ln N (N ) (56) ln(z 1) 4 4.1 V E G = (V, E) H(S) = h i S i (57) (ij) E J ij S i S j i V J ij h i (ij) i

i i S i S i H eff i (S i ) = S i h i + J ij S j = S i h i + J ij m j (58) j i j i S i (57) S j = m j (58) S i P (S i ) = exp( βhi eff (S i ))/( S i {+1, 1} exp( βheff i (S i ))) S i S i = m i e β(h P i+ j i J ijm j )S i m i = S i cosh β(h i + j i J ijm j ) = tanh β h i + J ij m j (59) j i S i {+1, 1} i = 1,,..., N (59) N m 1, m,..., m N N O( N ) naive mean field approximation 4.1.1 [15] x i {+1, 1} exp (β ) (ij) x ix j P (x) = (60) Z (β > 0) Z = Tr x exp (β ) (ij) x ix j (ij) p(< 1) α = (1/) ln((1 p)/p) x y P (y x) = N exp (αy i x i ) cosh(α) (61) (60) (61) y x P (y x)p (x) P (x y) = exp β N x i x j + α y i x i (6) P (y) (ij)

(a) (b) (c) BER 0.5 0. 0.15 0.1 0.05 (d) 0 0 5 10 15 0 5 30 t 3: β 1/.7 p α = (1/) ln((1 p)/p) (a) (b) 0% (c) (d) (63)..1 (6) x i {+1, 1} m i = tanh αy i + β m j (63) j i ˆx i = sign(m i ) = m i / m i 3 α β α β y P (y) = x P (y x)p (x) α β [16]

ψ a (.) x i 4: P (x) = (1/Z)ψ 1 (x 1 )ψ (x )ψ 3 (x 3 ) (x 1 = (x 1, x, x 4 ), x = (x, x 4 ), x 3 = (x 3, x 5 )) x 1, x,..., x 5 ψ 1 (x 1 ), ψ (x ), ψ 3 (x 3 ) 4. cavity method [6, 7] 4..1 N x = (x i ) P (x) = 1 ψ a (x a ) (64) Z a 5 ψ a (x a )( 0) x x a (ij) a exp(βjs i S j ) (S i, S j ) x a Z x i i x a a a a (64) factor graph 4 (64) graphical model = 5

4....1 (64) P i (x i ) = Tr x\xi P (x) a i P i (x i ) = ψ a(x a ) \x i Tr xi a i ψ a(x a ) (65) \x i \xi x i x i x\x i cavity distribution b/ i P \i (x\x i ) = ψ b(x b ) Tr x\xi b/ i ψ (66) b(x b ) (65) x i ψi eff (x i ) = a i ψ a(x a ) \x i x i [ ] x i P (x) = ψ a(x a ) b/ i ψ b(x b ) Tr x a i ψ a(x a ) b/ i ψ b(x b ) Tr x\xi b/ i ψ b(x b ) (66) ( a i P (x) = ψ a(x a ) ) P \i (x\x i ) Tr x ( a i ψ a(x a ) ) (68) P \i (x\x i ) Tr x\ Tr x ( ) = Tr xi { Trx\xi ( ) } (65) (67) 4..3 (65) ψi eff (x i ) = a i ψ a(x a ) P \x i i (x i ) P \i (x\x i ) ψi eff (x i ) P (x) hypertree 5(a) ψi eff (x i ) P i (x i ) a i ψ a (x a ) (a ) x a x j m j a (x j ) a, b, c,... i x a, x b, x c,... x i x i a, b, c,... i 5(b)

(a) (b) 5: (a) (b) ( ) ψi eff (x i ) = Tr ψ a (x a ) P \i (x\x i ) x\x i a i = Tr ψ a (x a ) m j a (x j ) (69) x a \x i a i j a\i i a i a O(1) (69) O(1) a ψi a eff (x i) ψ eff i a(x i ) = b i\a Tr ψ b (x b ) m j b (x j ) (70) x b \x i j b\i m i a (x i ) ψi a eff (x i) m i a (x i ) = b i\a Tr xi b i\a ( Tr xb \x i ψ b (x b ) ) j b\i m j b(x j ) ( Tr xb \x i ψ b (x b ) ) (71) j b\i m j b(x j ) m a i (x i ) = α a i Tr x a \x i ψ a (x a ) m i a (x i ) = α i a b i\a j a\i m j a (x j ) (7) m b i (x i ) (73)

(a) (b) a i i a 6: (a) (7) (b) (73) (a) (b) (m a i (x i ), m i a (x i )) α a i α i a m a i (x i ) m i a (x i ) m a i (x i ) x i P i (x i ) = α i m a i (x i ) (74) a i α i a j a m j a (x j ) (7) (73) m a i (x i ) m i a (x i ) a i a i O(1) (7) (73) O(1) a i i a (7) (73) (74) (7) (73) (74) belief propagation probability propagation (7) (73) a i (7) a m j a (x j ) Tr xa \x i i m a i (x i ) (73) i m b i (x i ) b i\a a m i a (x i ) 6 sum-product algorithm 3.3. 4..4 (7) (73) (74)

loopy belief propagation (7) (73) m a i (x i ) m i a (x i ) exp(βj ij S i S j ) exp(βhs i ) ˆθ θ m a i (S i ) = e β ˆθS i /( cosh(β ˆθ)) ψ a (x a ) exp(βj ij S i S j ) e βhs i /( cosh(βh)) ψ a (x a ) exp(βhs i ) m i a (S i ) = e βθs i /( cosh(βθ)) 3. 4..5 error correcting code low-density parity-check code [17] K m {0, 1} K N(> K) x {0, 1} N (N K) N 0 1 H Hx = 0 (mod ) (75) x mod m x H HG T = 0 (mod ) N K G T x = G T m (mod ) (76) Hx = HG T m = 0m = 0 (mod ) N > K x m 1 N, K H H H µ (µ = 1,,..., N K) 1 i µ i (i = 1,,..., N) 1 µ i S i = ( 1) x i x i = 1 S i (i = 1,,..., N) x {0, 1} N S {+1, 1} N (75) µ ψ µ (S µ ) = 1 + i µ S { i 1 ( ) = (78) 0 ( ) m {0, 1} K S µ=1 (77) P (S) = 1 N K ψ µ (S µ ) (79) Z H Z H = Tr N K S µ=1 ψ µ(s µ ) S 0 < p < 1/

ξ {+1, 1} N S ξ β p = (1/) ln((1 p)/p) P (ξ S) = N exp (β p ξ i S i ) cosh(β p ) = 1 ( cosh(β p )) N N ψ i (S i ) (80) ψ i (S i ) = exp(β p ξ i S i ) (79) (80) ξ S P (S ξ) = P (ξ S)P (S) P (ξ) = 1 Z N K µ=1 ψ µ (S µ ) N ψ i (S i ) (81) ξ S..1 (81) ψ µ (S µ ) ψ i (S i ) (81) 7 µ = 1,,..., N K i = 1,,..., N a m a i (S i ) = exp(θ a i S i )/( cosh(θ a i )) m i a (S i ) = exp(θ i a S i )/ ( cosh(θ i a )) (7) θ µ i = tanh 1 tanh(θ j µ ) (ψ µ (S µ ) ) (8) (73) j µ\i θ i i = β p ξ i (ψ i (S i ) ) (83) θ i µ = β p ξ i + ν i\µ θ ν i (84) { +1 if β p ξ i + µ i Ŝ i = θ µ i > 0 1 if β p ξ i + µ i θ µ i < 0 (85) 1 O(1) H 3.3.3 O(ln N) H N N 5

ψ µ (.) S i ψ(.) i 7: inverse Ising problem i S i {+1, 1} J ij h i J ij h i J ij h i [18, 19, 0] compressed sensing M N α = M/N 1 α < 1 [1] α [, 3] latent variable modeling M N X = (x 1, x,..., x M ) x µ z µ A x µ = Az µ +n µ n µ X A z µ Z = (z 1, z,..., z M ) N = (n 1, n,..., n M ) Z N X X = AZ + N [4, 5, 6] [1] (00) [] (1999) [3] E. Ising, Z. Phys. 31, 53 (195)

[4] L. Onsager, Phys. Rev. () 65, 117 (1944) [5] Y. Iba, J. Phys. A 3, 3875 (1999) [6] M. Mézard, G. Parisi and M. A. Virasoro, Spin glass theory and beyond, World Scientific (1987) [7] M. Mézard and A. Montanari, Information, Physics, and Computation, Oxford University Press (009) [8] T. H. L. Watkin, A. Rau and M. Biehl, Rev. Mod. Phys. 65, 499 (1993) [9] P. Weiss, J. Phys. Theor. Appl. 6, 661 (1907) [10] H. A. Bethe, Proc. Roy. Soc. London A 150, 55 (1935) [11] R. Kikuchi, Phys. Rev. 81, 988 (1951) [1] T. Morita, M. Suzuki, K. Wada and M. Kaburagi (eds), Foundations and Applications of Cluster Variation Method and Path Probability Method (Prog. Theor. Phys. Suppl. 115) (1994) [13] M. E. J. Newman, S. H. Strogatz and D. J. Watts, Phys. Rev. E 64, 06118 (001) [14] K. Nakagawa and H. Yamaguchi, IEICE Trans. Inf. Syst. E96-D, 433 (013) [15] (006) [16] R. Molina, A. K. Katsaggelos and J. Mateos, IEEE Trans. Image Processing 8, 31 (1999) [17], (00) [18] E. Schneidman, M. J. Berry, R. Segev and W. Bialek, Nature 440, 1007 (006) [19] S. Cocco and R. Monasson, Phys. Rev. Lett 106, 090601 (011) [0] H. Huang and Y. Kabashima, Phys. Rev. E 87, 0619 (013) [1] D. L. Donoho, IEEE Trans. on Inf. Theor. 5, 189 (006) [] F. Krzakala, M. Mézard, F. Sausset, Y. F. Sun and L. Zdeborová, Phys. Rev. X, 01005 (01) [3] M. C. Angelini, F. Ricci-Tersenghi and Y. Kabashima, in Proc. 50th Annual Allerton Conference, pp. 808 814 (01); arxiv:107.853 [4] A. Sakata and Y. Kabashima, EPL (Europhysics Letters) 103, 8008 (013) [5] A. Sakata and Y. Kabashima, in Proc. 013 IEEE International Symposium on Information Theory (Istanbul, Turkey, July 7 1, 013), pp. 669 673 (013); arxiv:1301.6199 [6] F. Krzakala, M. Mézard and L. Zdeborová, in Proc. 013 IEEE International Symposium on Information Theory (Istanbul, Turkey, July 7 1, 013), pp. 659 663 (013); arxiv:1301.5898