Stochastic Belief Propagation: A Low-Complexity Alternative to the Sum-Product Algorithm
Nima Noorshams, Martin J. Wainwright · IEEE Transactions on Information Theory · 2012
The belief propagation (BP) or sum-product algorithm is a widely used message-passing method for computing marginal distributions in graphical models. At the core of the BP message updates, when applied to a graphical model involving discrete variables with pairwise interactions, lies a matrix-vector product with complexity that is quadratic in the state dimensiond, and requires transmission of a (d-1)-dimensional vector of real numbers (messages) to its neighbors. Since various applications involve very large state dimensions, such computation and communication complexities can be prohibitively complex. In this paper, we propose a low-complexity variant of BP, referred to as stochastic belief propagation (SBP). As suggested by the name, it is an adaptively randomized version of the BP message updates in which each node passes randomly chosen information to each of its neighbors. The SBP message updates reduce the computational complexity (per iteration) from quadratic to linear ind, without assuming any particular structure of the potentials, and also reduce the communication complexity significantly, requiring only log2dbits transmission per edge. Moreover, we establish a number of theoretical guarantees for the performance of SBP, showing that it converges almost surely to the BP fixed point for any tree-structured graph, and for any graph with cycles satisfying a contractivity condition. In addition, for these graphical models, we provide nonasymptotic upper bounds on the convergence rate, showing that thel∞norm of the error vector decays no slower thanO(1/√t) with the number of iterationston trees and the normalized mean-squared error decays asO(1/t) for general graphs. This analysis, also supported by experimental results, shows that SBP can provably yield reductions in computational and communication complexities for various classes of graphical models.