| 1 Mean-field theory of phase transitions 1 |
| 1.1 Ising model 1 |
| 1.2 Order parameter and phase transition 3 |
| 1.3 Mean-field theory 4 |
| 1.3.1 Mean-field Hamiltonian 4 |
| 1.3.2 Equation of state 5 |
| 1.3.3 Free energy and the Landau theory 6 |
| 1.4 Infinite-range model 7 |
| 1.5 Variational approach 9 |
| 2 Mean-field theory of spin glasses 11 |
| 2.1 Spin glass and the Edwards-Anderson model 11 |
| 2.1.1 Edwards-Anderson model 12 |
| 2.1.2 Quenched system and configurational average 12 |
| 2.1.3 Replica method 13 |
| 2.2 Sherrington-Kirkpatrick model 13 |
| 2.2.1 SK model 14 |
| 2.2.2 Replica average of the partition function 14 |
| 2.2.3 Reduction by Gaussian integral 15 |
| 2.2.4 Steepest descent 15 |
| 2.2.5 Order parameters 16 |
| 2.3 Replica-symmetric solution 17 |
| 2.3.1 Equations of state 17 |
| 2.3.2 Phase diagram 19 |
| 2.3.3 Negative entropy 21 |
| 3 Replica symmetry breaking 23 |
| 3.1 Stability of replica-symmetric solution 23 |
| 3.1.1 Hessian 24 |
| 3.1.2 Eigenvalues of the Hessian and the AT line 26 |
| 3.2 Replica symmetry breaking 27 |
| 3.2.1 Parisi solution 28 |
| 3.2.2 First-step RSB 29 |
| 3.2.3 Stability of the first-step RSB 31 |
| 3.3 Full RSB solution 31 |
| 3.3.1 Physical quantities 31 |
| 3.3.2 Order parameter near the critical point 32 |
| 3.3.3 Vertical phase boundary 33 |
| 3.4 Physical significance of RSB 35 |
| 3.4.1 Multivalley structure 35 |
| 3.4.2 qEA and q 35 |
| 3.4.3 Distribution of overlaps 36 |
| 3.4.4 Replica representation of the order parameter 37 |
| 3.4.5 Ultrametricity 38 |
| 3.5 TAP equation 38 |
| 3.5.1 TAP equation 39 |
| 3.5.2 Cavity method 41 |
| 3.5.3 Properties of the solution 43 |
| 4 Gauge theory of spin glasses 46 |
| 4.1 Phase diagram of finite-dimensional systems 46 |
| 4.2 Gauge transformation 47 |
| 4.3 Exact solution for the internal energy 48 |
| 4.3.1 Application of gauge transformation 48 |
| 4.3.2 Exact internal energy 49 |
| 4.3.3 Relation with the phase diagram 50 |
| 4.3.4 Distribution of the local energy 51 |
| 4.3.5 Distribution of the local field 51 |
| 4.4 Bound on the specific heat 52 |
| 4.5 Bound on the free energy and internal energy 53 |
| 4.6 Correlation functions 55 |
| 4.6.1 Identities 55 |
| 4.6.2 Restrictions on the phase diagram 57 |
| 4.6.3 Distribution of order parameters 58 |
| 4.6.4 Non-monotonicity of spin configurations 61 |
| 4.7 Entropy of frustration 62 |
| 4.8 Modified ±J model 63 |
| 4.8.1 Expectation value of physical quantities 63 |
| 4.8.2 Phase diagram 64 |
| 4.8.3 Existence of spin glass phase 65 |
| 4.9 Gauge glass 67 |
| 4.9.1 Energy, specific heat, and correlation 67 |
| 4.9.2 Chirality 69 |
| 4.9.3 XY spin glass 70 |
| 4.10 Dynamical correlation function 71 |
| 5 Error-correcting codes 74 |
| 5.1 Error-correcting codes 74 |
| 5.1.1 Transmission of information 74 |
| 5.1.2 Similarity to spin glasses 75 |
| 5.1.3 Shannon bound 76 |
| 5.1.4 Finite-temperature decoding 78 |
| 5.2 Spin glass representation 78 |
| 5.2.1 Conditional probability 78 |
| 5.2.2 Bayes formula 79 |
| 5.2.3 MAP and MPM 80 |
| 5.2.4 Gaussian channel 81 |
| 5.3 Overlap 81 |
| 5.3.1 Measure of decoding performance 81 |
| 5.3.2 Upper bound on the overlap 82 |
| 5.4 Infinite-range model 83 |
| 5.4.1 Infinite-range model 84 |
| 5.4.2 Replica calculations 84 |
| 5.4.3 Replica-symmetric solution 86 |
| 5.4.4 Overlap 87 |
| 5.5 Replica symmetry breaking 88 |
| 5.5.1 First-step RSB 88 |
| 5.5.2 Random energy model 89 |
| 5.5.3 Replica solution in the limit γ→∞ 91 |
| 5.5.4 Solution for finite γ 93 |
| 5.6 Codes with finite connectivity 95 |
| 5.6.1 Sourlas-type code with finite connectivity 95 |
| 5.6.2 Low-density parity-check code 98 |
| 5.6.3 Cryptography 101 |
| 5.7 Convolutional code 102 |
| 5.7.1 Definition and examples 102 |
| 5.7.2 Generating polynomials 103 |
| 5.7.3 Recursive convolutional code 104 |
| 5.8 Turbo code 106 |
| 5.9 CDMA multiuser demodulator 108 |
| 5.9.1 Basic idea of CDMA 108 |
| 5.9.2 Conventional and Bayesian demodulators 110 |
| 5.9.3 Replica analysis of the Bayesian demodulator 111 |
| 5.9.4 Performance comparison 114 |
| 6 Image restoration 116 |
| 6.1 Stochastic approach to image restoration 116 |
| 6.1.1 Binary image and Bayesian inference 116 |
| 6.1.2 MAP and MPM 117 |
| 6.1.3 Overlap 118 |
| 6.2 Infinite-range model 119 |
| 6.2.1 Replica calculations 119 |
| 6.2.2 Temperature dependence of the overlap 121 |
| 6.3 Simulation 121 |
| 6.4 Mean-field annealing 122 |
| 6.4.1 Mean-field approximation 123 |
| 6.4.2 Annealing 124 |
| 6.5 Edges 125 |
| 6.6 Parameter estimation 128 |
| 7 Associative memory 131 |
| 7.1 Associative memory 131 |
| 7.1.1 Model neuron 131 |
| 7.1.2 Memory and stable fixed point 132 |
| 7.1.3 Statistical mechanics of the random Ising model 133 |
| 7.2 Embedding a finite number of patterns 135 |
| 7.2.1 Free energy and equations of state 135 |
| 7.2.2 Solution of the equation of state 136 |
| 7.3 Many patterns embedded 138 |
| 7.3.1 Replicated partition function 138 |
| 7.3.2 Non-retrieved patterns 138 |
| 7.3.3 Free energy and order parameter 140 |
| 7.3.4 Replica-symmetric solution 141 |
| 7.4 Self-consistent signal-to-noise analysis 142 |
| 7.4.1 Stationary state of an analogue neuron 142 |
| 7.4.2 Separation of signal and noise 143 |
| 7.4.3 Equation of state 145 |
| 7.4.4 Binary neuron 145 |
| 7.5 Dynamics 146 |
| 7.5.1 Synchronous dynamics 147 |
| 7.5.2 Time evolution of the overlap 147 |
| 7.5.3 Time evolution of the variance 148 |
| 7.5.4 Limit of applicability 150 |
| 7.6 Perceptron and volume of connections 151 |
| 7.6.1 Simple perceptron 151 |
| 7.6.2 Perceptron learning 152 |
| 7.6.3 Capacity of a perceptron 153 |
| 7.6.4 Replica representation 154 |
| 7.6.5 Replica-symmetric solution 155 |
| 8 Learning in perceptron 158 |
| 8.1 Learning and generalization error 158 |
| 8.1.1 Learning in perceptron 158 |
| 8.1.2 Generalization error 159 |
| 8.2 Batch learning 161 |
| 8.2.1 Bayesian formulation 162 |
| 8.2.2 Learning algorithms 163 |
| 8.2.3 High-temperature and annealed approximations 165 |
| 8.2.4 Gibbs algorithm 166 |
| 8.2.5 Replica calculations 167 |
| 8.2.6 Generalization error at T=0 169 |
| 8.2.7 Noise and unlearnable rules 170 |
| 8.3 On-line learning 171 |
| 8.3.1 Learning algorithms 171 |
| 8.3.2 Dynamics of learning 172 |
| 8.3.3 Generalization errors for specific algorithms 173 |
| 8.3.4 Optimization of learning rate 175 |
| 8.3.5 Adaptive learning rate for smooth cost function 176 |
| 8.3.6 Learning with query 178 |
| 8.3.7 On-line learning of unlearnable rule 179 |
| 9 Optimization problems 183 |
| 9.1 Combinatorial optimization and statistical mechanics 183 |
| 9.2 Number partitioning problem 184 |
| 9.2.1 Definition 184 |
| 9.2.2 Subset sum 185 |
| 9.2.3 Number of configurations for subset sum 185 |
| 9.2.4 Number partitioning problem 187 |
| 9.3 Graph partitioning problem 188 |
| 9.3.1 Definition 188 |
| 9.3.2 Cost function 189 |
| 9.3.3 Replica expression 190 |
| 9.3.4 Minimum of the cost function 191 |
| 9.4 Knapsack problem 192 |
| 9.4.1 Knapsack problem and linear programming 192 |
| 9.4.2 Relaxation method 193 |
| 9.4.3 Replica calculations 193 |
| 9.5 Satisfiability problem 195 |
| 9.5.1 Random satisfiability problem 195 |
| 9.5.2 Statistical-mechanical formulation 196 |
| 9.5.3 Replica-symmetric solution and its interpretation 199 |
| 9.6 Simulated annealing 201 |
| 9.6.1 Simulated annealing 202 |
| 9.6.2 Annealing schedule and generalized transition probability 203 |
| 9.6.3 Inhomogeneous Markov chain 204 |
| 9.6.4 Weak ergodicity 206 |
| 9.6.5 Relaxation of the cost function 209 |
| 9.7 Diffusion in one dimension 211 |
| 9.7.1 Diffusion and relaxation in one dimension 211 |
| A Eigenvalues of the Hessian 214 |
| A.1 Eigenvalue 1 214 |
| A.2 Eigenvalue 2 215 |
| A.3 Eigenvalue 3 216 |
| B Parisi equation 217 |
| C Channel coding theorem 220 |
| C.1 Information, uncertainty, and entropy 220 |
| C.2 Channel capacity 221 |
| C.3 BSC and Gaussian channel 223 |
| C.4 Typical sequence and random coding 224 |
| C.5 Channel coding theorem 226 |
| D Distribution and free energy of K-SAT 228 |
| References 232 |
| Index 241 |
| 1 Mean-field theory of phase transitions 1 |
| 1.1 Ising model 1 |
| 1.2 Order parameter and phase transition 3 |
| 1.3 Mean-field theory 4 |
| 1.3.1 Mean-field Hamiltonian 4 |
| 1.3.2 Equation of state 5 |
電子ブック
Statistical physics of spin glasses and information processing : an introduction ((ebook) :)
