Gauge-free cluster variational method by maximal messages and moment matching
arXiv:1611.05068 · doi:10.1103/PhysRevE.95.043308
Abstract
We present a new implementation of the Cluster Variational Method (CVM) as a message passing algorithm. The kind of message passing algorithms used for CVM, usually named Generalized Belief Propagation, are a generalization of the Belief Propagation algorithm in the same way that CVM is a generalization of the Bethe approximation for estimating the partition function. However, the connection between fixed points of GBP and the extremal points of the CVM free-energy is usually not a one-to-one correspondence, because of the existence of a gauge transformation involving the GBP messages. Our contribution is twofold. Firstly we propose a new way of defining messages (fields) in a generic CVM approximation, such that messages arrive on a given region from all its ancestors, and not only from its direct parents, as in the standard Parent-to-Child GBP. We call this approach maximal messages. Secondly we focus on the case of binary variables, re-interpreting the messages as fields enforcing the consistency between the moments of the local (marginal) probability distributions. We provide a precise rule to enforce all consistencies, avoiding any redundancy, that would otherwise lead to a gauge transformation on the messages. This moment matching method is gauge free, i.e. it guarantees that the resulting GBP is not gauge invariant. We apply our maximal messages and moment matching GBP to obtain an analytical expression for the critical temperature of the Ising model in general dimensions at the level of plaquette-CVM. The values obtained outperform Bethe estimates, and are comparable with loop corrected Belief Propagation equations. The method allows for a straightforward generalization to disordered systems.
arXiv commentCorrected some Affiliation and references
References in corpus (13)
- The Bethe lattice spin glass revisited
- How to Compute Loop Corrections to Bethe Approximation
- Scaling above the upper critical dimension in Ising Models
- Region graph partition function expansion and approximate free energy landscapes: Theory and some numerical results
- Partition function loop series for a general graphical model: free energy corrections and message-passing equations
- Replica Cluster Variational Method
- Belief Propagation Reconstruction for Discrete Tomography
- Replica Cluster Variational Method: the Replica Symmetric solution for the 2D random bond Ising model
- Characterizing and Improving Generalized Belief Propagation Algorithms on the 2D Edwards-Anderson Model
- A very fast inference algorithm for finite-dimensional spin glasses: Belief Propagation on the dual lattice
- Statistical Analysis of Loopy Belief Propagation in Random Fields
- Simplifying Generalized Belief Propagation on Redundant Region Graphs
- Cycle-based Cluster Variational Method for Direct and Inverse Inference