Home Page

Papers

Submissions

News

Editorial Board

Special Issues

Open Source Software

Proceedings (PMLR)

Data (DMLR)

Transactions (TMLR)

Search

Statistics

Login

Frequently Asked Questions

Contact Us



RSS Feed

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

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

Abstract

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.

[abs][pdf][bib]       
© JMLR 2013. (edit, beta)

Mastodon