Belief propagation and loop series on planar graphs

Michael Chertkov, Vladimir Y. Chernyak, Razvan Teodorescu

Research output: Contribution to journalArticlepeer-review

15 Citations (Scopus)

Abstract

We discuss a generic model of Bayesian inference with binary variables defined on edges of a planar graph. The Loop Calculus approach of Chertkov and Chernyak (2006 Phys. Rev. E 73 065102(R) [cond-mat/0601487]; 2006 J. Stat. Mech. P06009 [cond-mat/0603189]) is used to evaluate the resulting series expansion for the partition function. We show that, for planar graphs, truncating the series at single-connected loops reduces, via a map reminiscent of the Fisher transformation (Fisher 1961 Phys. Rev. 124 1664), to evaluating the partition function of the dimer-matching model on an auxiliary planar graph. Thus, the truncated series can be easily re-summed, using the Pfaffian formula of Kasteleyn (1961 Physics 27 1209). This allows us to identify a big class of computationally tractable planar models reducible to a dimer model via the Belief Propagation (gauge) transformation. The Pfaffian representation can also be extended to the full Loop Series, in which case the expansion becomes a sum of Pfaffian contributions, each associated with dimer matchings on an extension to a subgraph of the original graph. Algorithmic consequences of the Pfaffian representation, as well as relations to quantum and non-planar models, are discussed.

Original languageEnglish
Article numberP05003
JournalJournal of Statistical Mechanics: Theory and Experiment
Volume2008
Issue number5
DOIs
Publication statusPublished - 1 May 2008
Externally publishedYes

Keywords

  • Analysis of algorithms
  • Error correcting codes
  • Heuristics

Fingerprint

Dive into the research topics of 'Belief propagation and loop series on planar graphs'. Together they form a unique fingerprint.

Cite this