Loop series for discrete statistical models on graphs
- 1 June 2006
- journal article
- Published by IOP Publishing in Journal of Statistical Mechanics: Theory and Experiment
- Vol. 2006 (6), P06009
- https://doi.org/10.1088/1742-5468/2006/06/p06009
Abstract
In this paper we present the derivation details, logic, and motivation for the three loop calculus introduced in Chertkov and Chernyak (2006 Phys. Rev. E 73 065102(R)). Generating functions for each of the three interrelated discrete statistical models are expressed in terms of a finite series. The first term in the series corresponds to the Bethe–Peierls belief–propagation (BP) contribution; the other terms are labelled by loops on the factor graph. All loop contributions are simple rational functions of spin correlation functions calculated within the BP approach. We discuss two alternative derivations of the loop series. One approach implements a set of local auxiliary integrations over continuous fields with the BP contribution corresponding to an integrand saddle-point value. The integrals are replaced by sums in the complementary approach, briefly explained in Chertkov and Chernyak (2006 Phys. Rev. E 73 065102(R)). Local gauge symmetry transformations that clarify an important invariant feature of the BP solution are revealed in both approaches. The individual terms change under the gauge transformation while the partition function remains invariant. The requirement for all individual terms to be nonzero only for closed loops in the factor graph (as opposed to paths with loose ends) is equivalent to fixing the first term in the series to be exactly equal to the BP contribution. Further applications of the loop calculus to problems in statistical physics, computer and information sciences are discussed.Keywords
Other Versions
This publication has 20 references indexed in Scilit:
- Constructing Free-Energy Approximations and Generalized Belief Propagation AlgorithmsIEEE Transactions on Information Theory, 2005
- Survey propagation as local equilibrium equationsJournal of Statistical Mechanics: Theory and Experiment, 2004
- The renaissance of gallager's low-density parity-check codesIEEE Communications Magazine, 2003
- Random-satisfiability problem: From an analytic solution to an efficient algorithmPhysical Review E, 2002
- Analytic and Algorithmic Solution of Random Satisfiability ProblemsScience, 2002
- Good error-correcting codes based on very sparse matricesIEEE Transactions on Information Theory, 1999
- Cluster Variation Method for Non-Uniform Ising and Heisenberg Models and Spin-Pair Correlation FunctionProgress of Theoretical Physics, 1991
- Spin-glass models as error-correcting codesNature, 1989
- A Theory of Cooperative PhenomenaPhysical Review B, 1951
- On Ising's model of ferromagnetismMathematical Proceedings of the Cambridge Philosophical Society, 1936