Skip to Main content Skip to Navigation

Modélisation probabiliste et inférence par l'algorithme Belief Propagation

Victorin Martin 1, 2, 3 
3 TAO - Machine Learning and Optimisation
LRI - Laboratoire de Recherche en Informatique, UP11 - Université Paris-Sud - Paris 11, Inria Saclay - Ile de France, CNRS - Centre National de la Recherche Scientifique : UMR8623
Abstract : In this work, we focus on the design and estimation - from partial observations - of graphical models of real-valued random variables. These models should be suited for a non-standard regression problem where the identity of the observed variables (and therefore of the variables to predict) changes from an instance to the other. The nature of the problem and of the available data lead us to model the network as a Markov random field, a choice consistent with Jaynes' maximum entropy principle. For the prediction task, we turn to the Belief Propagation algorithm - in its classical or Gaussian flavor - which simplicity and efficiency make it usable on large scale networks. After providing a new result on the local stability of the algorithm's fixed points, we propose an approach based on a latent Ising model, where dependencies between real-valued variables are encoded through a network of binary variables. To this end, we propose a definition of these variables using the cumulative distribution functions of the real-valued variables. For the prediction task, it is necessary to modify the Belief Propagation algorithm in order to impose Bayesian-like constraints on marginal distributions of the binary variables. Estimation of the model parameters can easily be performed using only pairwise observations. In fact, this approach is a way to solve the regression problem by working on quantiles.Furthermore, we propose a greedy algorithm for estimating both the structure and the parameters of a Gauss-Markov random field based on the Iterative Proportional Scaling procedure. At each iteration, the algorithm yields a new model which likelihood, or an approximation of it in the case of partial observations,is higher than the one of the previous model. Because of its local perturbation principle, this algorithm allows us to impose spectral constraints, increasing the compatibility with the Gaussian Belief Propagation algorithm. The performances of all approaches are empirically illustrated on synthetic data.
Document type :
Complete list of metadata

Cited literature [98 references]  Display  Hide  Download
Contributor : ABES STAR :  Contact
Submitted on : Friday, October 18, 2013 - 4:47:08 PM
Last modification on : Sunday, June 26, 2022 - 11:59:54 AM
Long-term archiving on: : Sunday, January 19, 2014 - 4:29:47 AM


Version validated by the jury (STAR)


  • HAL Id : tel-00867693, version 2


Victorin Martin. Modélisation probabiliste et inférence par l'algorithme Belief Propagation. Autre. Ecole Nationale Supérieure des Mines de Paris, 2013. Français. ⟨NNT : 2013ENMP0020⟩. ⟨tel-00867693v2⟩



Record views


Files downloads