Belief Propagation and Loop Series on Planar Graphs

Simple item page
dc.creatorChertkov, Michael
dc.creatorChernyak, Vladimir Y.
dc.creatorTeodorescu, Razvan
dc.date2008-02-27
dc.date2008-04-11
dc.date.accessioned2026-07-07T09:39:48Z
dc.date.available2026-07-07T09:39:48Z
dc.descriptionWe discuss a generic model of Bayesian inference with binary variables defined on edges of a planar graph. The Loop Calculus approach of [1, 2] 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 [3], 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 [4]. This allows 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.
dc.descriptionAccepted for publication in Journal of Statistical Mechanics: theory and experiment
dc.identifierhttps://arxiv.org/abs/0802.3950
dc.identifierhttp://arxiv.org/abs/0802.3950
dc.identifierJ. Stat. Mech. (2008) P05003
dc.identifierdoi:10.1088/1742-5468/2008/05/P05003
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/161308
dc.subjectStatistical Mechanics
dc.subjectArtificial Intelligence
dc.subjectInformation Theory
dc.titleBelief Propagation and Loop Series on Planar Graphs
dc.typetext

Files

Collections

arXiv