Propagating beliefs in spin glass models

Abstract

We investigate dynamics of an inference algorithm termed the belief propagation (BP) when employed in spin glass (SG) models and show that its macroscopic behaviors can be traced by recursive updates of certain auxiliary field distributions whose stationary state reproduces the replica symmetric solution offered by the equilibrium analysis. We further provide a compact expression for the instability condition of the BP's fixed point which turns out to be identical to that of instability for breaking the replica symmetry in equilibrium when the number of couplings per spin is infinite. This correspondence is extended to a SG model of finite connectivity to determine the phase diagram, which is numerically supported.

References in corpus (6)

• The Bethe lattice spin glass revisited
• Statistical mechanics of image restoration and error-correcting codes
• Typical Performance of Gallager-type Error-Correcting Codes
• The statistical mechanics of turbo codes
• Error-correcting code on a cactus: a solvable model
• Statistical Physics of Irregular Low-Density Parity-Check Codes

Cited by in corpus (21)

• Statistical physics of inference: Thresholds and algorithms
• Cluster Variation Method in Statistical Physics and Probabilistic Graphical Models
• Learning by message-passing in networks of discrete synapses
• Sparsely-spread CDMA - a statistical mechanics based analysis
• Dynamical replica analysis of disordered Ising spin systems on finitely connected random graphs
• Replica symmetry breaking in the `small world' spin glass
• Statistical Mechanical Development of a Sparse Bayesian Classifier
• A Spatially Extended Model for Residential Segregation
• Replicated Bethe Free Energy: A Variational Principle behind Survey Propagation
• A very fast inference algorithm for finite-dimensional spin glasses: Belief Propagation on the dual lattice
• Random-field p-spin glass model on regular random graphs
• Distribution of partition function zeros of the $\pm J$ model on the Bethe lattice
• Survey propagation at finite temperature: application to a Sourlas code as a toy model
• Scaling Analysis of Affinity Propagation
• Equilibrium properties of disordered spin models with two scale interactions
• How could the replica method improve accuracy of performance assessment of channel coding?
• On composite systems of dilute and dense couplings
• Equivalence between algorithmic instability and transition to replica symmetry breaking in perceptron learning systems
• Quantum Cluster Variational Method and Message Passing Algorithms Revisited
• Survey propagation for the cascading Sourlas code
• Replica analysis of the lattice-gas Restricted Boltzmann Machine partition function