Convex Combination Belief Propagation Algorithms
This addresses a fundamental limitation in probabilistic inference for researchers and practitioners in machine learning and AI, offering a more robust method for difficult inference tasks.
The paper tackles the problem of non-convergence in belief propagation for graphical models with complex topology by introducing new message passing algorithms that guarantee convergence to unique solutions on arbitrary graphs and potential functions.
We present new message passing algorithms for performing inference with graphical models. Our methods are designed for the most difficult inference problems where loopy belief propagation and other heuristics fail to converge. Belief propagation is guaranteed to converge when the underlying graphical model is acyclic, but can fail to converge and is sensitive to initialization when the underlying graph has complex topology. This paper describes modifications to the standard belief propagation algorithms that lead to methods that converge to unique solutions on graphical models with arbitrary topology and potential functions.