Statistical Physics of Spin Glasses and Information Processing An Introduction

by Nishimori, Hidetoshi

• ISBN13: 9780198509417
• ISBN10: 0198509413
• Format: Paperback
• Copyright: 2001-09-27
• Publisher: Clarendon Press

Summary

Spin glasses are magnetic materials. Statistical mechanics, a subfield of physics, has been a powerful tool to theoretically analyse various unique properties of spin glasses. A number of new analytical techniques have been developed to establish a theory of spin glasses. Surprisingly, thesetechniques have turned out to offer new tools and viewpoints for the understanding of information processing problems, including neural networks, error-correcting codes, image restoration, and optimization problems. This book is one of the first publications of the past ten years that provide abroad overview of this interdisciplinary field. Most of the book is written in a self-contained manner, assuming only a general knowledge of statistical mechanics and basic probability theory. It provides the reader with a sound introduction to the field and to the analytical techniques necessary tofollow its most recent developments.

Author Biography

Hidetoshi Nishimori is Professor of Physics at Tokyo Institute of Technology

Table of Contents

Mean-field theory of phase transitions	p. 1
Ising model	p. 1
Order parameter and phase transition	p. 3
Mean-field theory	p. 4
Mean-field Hamiltonian	p. 4
Equation of state	p. 5
Free energy and the Landau theory	p. 6
Infinite-range model	p. 7
Variational approach	p. 9
Mean-field theory of spin glasses	p. 11
Spin glass and the Edwards-Anderson model	p. 11
Edwards-Anderson model	p. 12
Quenched system and configurational average	p. 12
Replica method	p. 13
Sherrington-Kirkpatrick model	p. 13
SK model	p. 14
Replica average of the partition function	p. 14
Reduction by Gaussian integral	p. 15
Steepest descent	p. 15
Order parameters	p. 16
Replica-symmetric solution	p. 17
Equations of state	p. 17
Phase diagram	p. 19
Negative entropy	p. 21
Replica symmetry breaking	p. 23
Stability of replica-symmetric solution	p. 23
Hessian	p. 24
Eigenvalues of the Hessian and the AT line	p. 26
Replica symmetry breaking	p. 27
Parisi solution	p. 28
First-step RSB	p. 29
Stability of the first-step RSB	p. 31
Full RSB solution	p. 31
Physical quantities	p. 31
Order parameter near the critical point	p. 32
Vertical phase boundary	p. 33
Physical significance of RSB	p. 35
Multivalley structure	p. 35
qEA and q	p. 35
Distribution of overlaps	p. 36
Replica representation of the order parameter	p. 37
Ultrametricity	p. 38
TAP equation	p. 38
TAP equation	p. 39
Cavity method	p. 41
Properties of the solution	p. 43
Gauge theory of spin glasses	p. 46
Phase diagram of finite-dimensional systems	p. 46
Gauge transformation	p. 47
Exact solution for the internal energy	p. 48
Application of gauge transformation	p. 48
Exact internal energy	p. 49
Relation with the phase diagram	p. 50
Distribution of the local energy	p. 51
Distribution of the local field	p. 51
Bound on the specific heat	p. 52
Bound on the free energy and internal energy	p. 53
Correlation functions	p. 55
Identities	p. 55
Restrictions on the phase diagram	p. 57
Distribution of order parameters	p. 58
Non-monotonicity of spin configurations	p. 61
Entropy of frustration	p. 62
Modified [plus or minus]J model	p. 63
Expectation value of physical quantities	p. 63
Phase diagram	p. 64
Existence of spin glass phase	p. 65
Gauge glass	p. 67
Energy, specific heat, and correlation	p. 67
Chirality	p. 69
XY spin glass	p. 70
Dynamical correlation function	p. 71
Error-correcting codes	p. 74
Error-correcting codes	p. 74
Transmission of information	p. 74
Similarity to spin glasses	p. 75
Shannon bound	p. 76
Finite-temperature decoding	p. 78
Spin glass representation	p. 78
Conditional probability	p. 78
Bayes formula	p. 79
MAP and MPM	p. 80
Gaussian channel	p. 81
Overlap	p. 81
Measure of decoding performance	p. 81
Upper bound on the overlap	p. 82
Infinite-range model	p. 83
Infinite-range model	p. 84
Replica calculations	p. 84
Replica-symmetric solution	p. 86
Overlap	p. 87
Replica symmetry breaking	p. 88
First-step RSB	p. 88
Random energy model	p. 89
Replica solution in the limit r [right arrow] [infinity]	p. 91
Solution for finite r	p. 93
Codes with finite connectivity	p. 95
Sourlas-type code with finite connectivity	p. 95
Low-density parity-check code	p. 98
Cryptography	p. 101
Convolutional code	p. 102
Definition and examples	p. 102
Generating polynomials	p. 103
Recursive convolutional code	p. 104
Turbo code	p. 106
CDMA multiuser demodulator	p. 108
Basic idea of CDMA	p. 108
Conventional and Bayesian demodulators	p. 110
Replica analysis of the Bayesian demodulator	p. 111
Performance comparison	p. 114
Image restoration	p. 116
Stochastic approach to image restoration	p. 116
Binary image and Bayesian inference	p. 116
MAP and MPM	p. 117
Overlap	p. 118
Infinite-range model	p. 119
Replica calculations	p. 119
Temperature dependence of the overlap	p. 121
Simulation	p. 121
Mean-field annealing	p. 122
Mean-field approximation	p. 123
Annealing	p. 124
Edges	p. 125
Parameter estimation	p. 128
Associative memory	p. 131
Associative memory	p. 131
Model neuron	p. 131
Memory and stable fixed point	p. 132
Statistical mechanics of the random Ising model	p. 133
Embedding a finite number of patterns	p. 135
Free energy and equations of state	p. 135
Solution of the equation of state	p. 136
Many patterns embedded	p. 138
Replicated partition function	p. 138
Non-retrieved patterns	p. 138
Free energy and order parameter	p. 140
Replica-symmetric solution	p. 141
Self-consistent signal-to-noise analysis	p. 142
Stationary state of an analogue neuron	p. 142
Separation of signal and noise	p. 143
Equation of state	p. 145
Binary neuron	p. 145
Dynamics	p. 146
Synchronous dynamics	p. 147
Time evolution of the overlap	p. 147
Time evolution of the variance	p. 148
Limit of applicability	p. 150
Perceptron and volume of connections	p. 151
Simple perceptron	p. 151
Perceptron learning	p. 152
Capacity of a perceptron	p. 153
Replica representation	p. 154
Replica-symmetric solution	p. 155
Learning in perceptron	p. 158
Learning and generalization error	p. 158
Learning in perceptron	p. 158
Generalization error	p. 159
Batch learning	p. 161
Bayesian formulation	p. 162
Learning algorithms	p. 163
High-temperature and annealed approximations	p. 165
Gibbs algorithm	p. 166
Replica calculations	p. 167
Generalization error at T = 0	p. 169
Noise and unlearnable rules	p. 170
On-line learning	p. 171
Learning algorithms	p. 171
Dynamics of learning	p. 172
Generalization errors for specific algorithms	p. 173
Optimization of learning rate	p. 175
Adaptive learning rate for smooth cost function	p. 176
Learning with query	p. 178
On-line learning of unlearnable rule	p. 179
Optimization problems	p. 183
Combinatorial optimization and statistical mechanics	p. 183
Number partitioning problem	p. 184
Definition	p. 184
Subset sum	p. 185
Number of configurations for subset sum	p. 185
Number partitioning problem	p. 187
Graph partitioning problem	p. 188
Definition	p. 188
Cost function	p. 189
Replica expression	p. 190
Minimum of the cost function	p. 191
Knapsack problem	p. 192
Knapsack problem and linear programming	p. 192
Relaxation method	p. 193
Replica calculations	p. 193
Satisfiability problem	p. 195
Random satisfiability problem	p. 195
Statistical-mechanical formulation	p. 196
Replica-symmetric solution and its interpretation	p. 199
Simulated annealing	p. 201
Simulated annealing	p. 202
Annealing schedule and generalized transition probability	p. 203
Inhomogeneous Markov chain	p. 204
Weak ergodicity	p. 206
Relaxation of the cost function	p. 209
Diffusion in one dimension	p. 211
Diffusion and relaxation in one dimension	p. 211
Eigenvalues of the Hessian	p. 214
Eigenvalue 1	p. 214
Eigenvalue 2	p. 215
Eigenvalue 3	p. 216
Parisi equation	p. 217
Channel coding theorem	p. 220
Information, uncertainty, and entropy	p. 220
Channel capacity	p. 221
BSC and Gaussian channel	p. 223
Typical sequence and random coding	p. 224
Channel coding theorem	p. 226
Distribution and free energy of K-SAT	p. 228
References	p. 232
Index	p. 241
Table of Contents provided by Syndetics. All Rights Reserved.