2012/12/16 by Nima Noorshams, Martin J. Wainwright, Noorshams, Nima +1
Computer Science · Mathematics · #FOS: Computer and information sciences #Information Theory (cs.IT) #Machine Learning (cs.LG) #Machine Learning (stat.ML) #cs.IT #cs.LG #math.IT #stat.ML
paper · pdf · doi:10.48550/arxiv.1212.3850
Portions of the results were presented at the International Symposium on Information Theory 2012. The results were also submitted to the Journal of Machine Learning Research on December 16th 2012
arxiv created 2012/12/16 · arxiv updated 2012/12/18
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 expansion, and a stochastic approximation via Monte Carlo estimates of the integral updates of the basis coefficients. We prove that the SOSMP iterates converge to a δ-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 δand smoothness of the compatibility functions. We illustrate our theory with both simulated examples and in application to optical flow estimation.