Tree-Based Reparameterization Framework for Approximate Estimation of Stochastic Processes on Graphs With Cycles

We present a tree-based reparameterization framework for the approximate estimation of stochastic processes on graphs with cycles. This framework provides a new conceptual view of a large class of iterative algorithms for computing approximate marginals in graphs with cycles. Among them is belief propagation (BP), otherwise known as the sum-product algorithm, which can be reformulated as a very local form of reparameterization. More generally, this class includes algorithms in which updates are more global, and involve performing exact computations over spanning trees of the full graph. On the practical side, we nd that such tree reparameterization (TRP) algorithms typically converge more quickly than belief propagation with equivalent or lower cost per iteration; moreover, TRP often converges on harder problems for which BP fails. The reparameterization perspective also provides new theoretical insights into approximate estimation. In particular, it leads to a novel probabilistic characterization of the set of xed points. We develop the geometry of tree-based reparameterization, and use it to develop sucient conditions for convergence in the case of two spanning trees. A fundamental property of reparameterization updates is that they leave invariant the distribution on the full graph. This invariance, in conjunction with our xed point characterization, enables us to derive an exact relation between the true marginals on an arbitrary graph with cycles, and the approximations provided by TRP or BP. We also develop bounds on this approximation error, which illuminate the conditions that govern performance of such techniques. Our results also have natural extensions to approximations (e.g., Kikuchi) that involve clustering nodes. MW was supported in part by a 1967 Fel..