Belief Propagation for Continuous State Spaces: Stochastic Message-Passing with Quantitative Guarantees

Nima Noorshams, Martin J. Wainwright; 14(Sep):2799−2835, 2013.


The sum-product or belief propagation (BP) algorithm is a widely used message-passing technique for computing approximate marginals in graphical models. We introduce a new technique, called stochastic orthogonal series message-passing (SOSMP), for computing the BP fixed point in models with continuous random variables. It is based on a deterministic approximation of the messages via orthogonal series basis expansion, and a stochastic estimation of the basis coefficients via Monte Carlo techniques and damped updates. We prove that the SOSMP iterates converge to a $\delta$-neighborhood of the unique BP fixed point for any tree-structured graph, and for any graphs with cycles in which the BP updates satisfy a contractivity condition. In addition, we demonstrate how to choose the number of basis coefficients as a function of the desired approximation accuracy $\delta$ and smoothness of the compatibility functions. We illustrate our theory with both simulated examples and in application to optical flow estimation.


Home Page




Editorial Board



Open Source Software




Contact Us

RSS Feed