Convex Combination Belief Propagation Algorithms

Graphical models provide a natural framework for probabilistic modeling and for inference with a large number of random variables. The framework has numerous applications including in computer vision, artificial intelligence, error correcting codes, and statistical physics. Exact inference in graphical models is NP-hard so it is essential to develop approximate inference algorithms that are computationally tractable. Belief propagation is a widely used message passing algorithm that can be used to perform either exact or approximate inference in a graphical model depending on the topology of the graph. This algorithm was first introduced by Judea Pearl in the early 1980s as a method to perform exact inference on a tree-structured graph in polynomial time [15].