Cycle-based cluster variational method for direct and inverse inference

DOI10.1007/S10955-016-1566-0zbMATH Open1351.82036arXiv1602.03102OpenAlexW3100818472MaRDI QIDQ330619FDOQ330619

Authors: Cyril Furtlehner, Aurélien Decelle 

Publication date: 26 October 2016

Published in: Journal of Statistical Physics (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1602.03102

Recommendations

• Pairwise MRF models selection for traffic inference
• Linear Response Algorithms for Approximate Inference in Graphical Models
• Adaptive cluster expansion for the inverse Ising problem: convergence, algorithm and tests
• Loop corrections for approximate inference on factor graphs
• Approximate inverse Ising models close to a Bethe reference point

zbMATH Keywords

inverse problemvariational methoddirect problemMarkov random fields

Mathematics Subject Classification ID

Linear regression; mixed models (62J05) Random fields (60G60) Combinatorial optimization (90C27) Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20) Exactly solvable models; Bethe ansatz (82B23)

Cites Work

• Graphical models, exponential families, and variational inference
• Estimation of sparse binary pairwise Markov networks using pseudo-likelihoods
• Title not available (Why is that?)
• Title not available (Why is that?)
• High-dimensional Ising model selection using \(\ell _{1}\)-regularized logistic regression
• Minimum weakly fundamental cycle bases are hard to find
• CCCP Algorithms to Minimize the Bethe and Kikuchi Free Energies: Convergent Alternatives to Belief Propagation
• Constructing Free-Energy Approximations and Generalized Belief Propagation Algorithms
• A Polynomial-Time Algorithm to Find the Shortest Cycle Basis of a Graph
• Cycle bases in graphs characterization, algorithms, complexity, and applications
• Statistical-mechanical approach to image processing
• Finding MAPs for belief networks is NP-hard
• Adaptive cluster expansion for the inverse Ising problem: convergence, algorithm and tests
• Approximate inference in Boltzmann machines
• The computational complexity of probabilistic inference using Bayesian belief networks
• Cluster variation method and Möbius inversion formula
• Loop series for discrete statistical models on graphs
• Message-passing algorithms for quadratic minimization
• Partition function loop series for a general graphical model: free-energy corrections and message-passing equations
• Loop corrections for approximate inference on factor graphs
• Approximate inverse Ising models close to a Bethe reference point
• MAP Estimation Via Agreement on Trees: Message-Passing and Linear Programming
• Approximate Learning Algorithm in Boltzmann Machines
• Latent binary MRF for online reconstruction of large scale systems
• Estimation and Marginalization Using the Kikuchi Approximation Methods
• Statistical theory of superlattices
• A Theory of Cooperative Phenomena

Cited In (2)

• Pairwise MRF models selection for traffic inference
• Parameter inference in a probabilistic model using clustered data

Uses Software

• mplp2

This page was built for publication: Cycle-based cluster variational method for direct and inverse inference

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q330619)