Cycle-based Cluster Variational Method for Direct and Inverse Inference
arXiv:1602.03102 · doi:10.1007/s10955-016-1566-0
Abstract
We elaborate on the idea that loop corrections to belief propagation could be dealt with in a systematic way on pairwise Markov random fields, by using the elements of a cycle basis to define region in a generalized belief propagation setting. The region graph is specified in such a way as to avoid dual loops as much as possible, by discarding redundant Lagrange multipliers, in order to facilitate the convergence, while avoiding instabilities associated to minimal factor graph construction. We end up with a two-level algorithm, where a belief propagation algorithm is run alternatively at the level of each cycle and at the inter-region level. The inverse problem of finding the couplings of a Markov random field from empirical covariances can be addressed region wise. It turns out that this can be done efficiently in particular in the Ising context, where fixed point equations can be derived along with a one-parameter log likelihood function to minimize. Numerical experiments confirm the effectiveness of these considerations both for the direct and inverse MRF inference.
arXiv comment47 pages, 16 figures
References in corpus (13)
- High-dimensional Ising model selection using -regularized logistic regression
- Loop series for discrete statistical models on graphs
- Cluster Variation Method in Statistical Physics and Probabilistic Graphical Models
- Adaptive cluster expansion for the inverse Ising problem: convergence, algorithm and tests
- How to Compute Loop Corrections to Bethe Approximation
- Pseudolikelihood Decimation Algorithm Improving the Inference of the Interaction Network in a General Class of Ising Models
- Strong universality and algebraic scaling in two-dimensional Ising spin glasses
- Loop expansion around the Bethe-Peierls approximation for lattice models
- Partition function loop series for a general graphical model: free energy corrections and message-passing equations
- 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
- Computing loop corrections by message passing
- Using Latent Binary Variables for Online Reconstruction of Large Scale Systems