Skip to Main content Skip to Navigation
Journal articles

Cycle-based Cluster Variational Method for Direct and Inverse Inference

Cyril Furtlehner 1 Aurélien Decelle 2, 1
1 TAO - Machine Learning and Optimisation
CNRS - Centre National de la Recherche Scientifique : UMR8623, Inria Saclay - Ile de France, UP11 - Université Paris-Sud - Paris 11, LRI - Laboratoire de Recherche en Informatique
Abstract : Large scale inference problems of practical interest can often be addressed with help of Markov random fields. This requires to solve in principle two related problems: the first one is to find offline the parameters of the MRF from empirical data (inverse problem); the second one (direct problem) is to set up the inference algorithm to make it as precise, robust and efficient as possible. In this work we address both the direct and inverse problem with mean-field methods of statistical physics, going beyond the Bethe approximation and associated belief propagation algorithm. 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.
Complete list of metadata

Cited literature [37 references]  Display  Hide  Download
Contributor : Cyril Furtlehner <>
Submitted on : Monday, October 24, 2016 - 3:07:51 PM
Last modification on : Wednesday, September 16, 2020 - 5:04:41 PM


Files produced by the author(s)




Cyril Furtlehner, Aurélien Decelle. Cycle-based Cluster Variational Method for Direct and Inverse Inference. Journal of Statistical Physics, Springer Verlag, 2016, 164 (3), pp.531-574. ⟨10.1007/s10955-016-1566-0⟩. ⟨hal-01214155v2⟩



Record views


Files downloads