Belief propagation and loop series on planar graphs

摘要: We discuss a generic model of Bayesian inference with binary variables defined on edges planar graph. The Loop Calculus approach 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 partition function. show that, graphs, truncating at single-connected loops reduces, via map reminiscent Fisher transformation (Fisher 1961 124 1664), evaluating function dimer-matching an auxiliary Thus, truncated can be easily re-summed, using Pfaffian formula Kasteleyn (1961 Physics 27 1209). This allows us identify big class computationally tractable models reducible dimer Belief Propagation (gauge) transformation. representation also extended full Series, in which case becomes sum contributions, each associated matchings extension subgraph original Algorithmic consequences representation, as well relations quantum non-planar models, are discussed.