Abstract

Belief propagation is a remarkably effective tool for inference in graphical models, even when applied to networks with cycles. A variational perspective shows that it may be viewed as a way to seek the minimum of the Bethe free energy, though it may converge only to a local optimum or may not converge at all.

We shall cover a brief introduction to these ideas, then go on to describe a recent algorithm we developed for any binary pairwise model which, to our knowledge, is the first to guarantee to return an epsilon-approximation to the global minimum of the Bethe free energy. The approach involves discretizing to yield a discrete optimization problem, which may be viewed as multi-label MAP inference. If the initial model is fully attractive, this yields a fully polynomial-time approximation scheme (FPTAS).

If time, we can also discuss work that further explores the Bethe approximation and tries to tease apart the two ways it differs from exact inference: (i) the true entropy is approximated by the Bethe (pairwise) entropy, and (ii) the minimization is performed over a relaxation of the marginal polytope (which enforces a globally consistent probability distribution) termed the local polytope (which enforces only pairwise consistency).

This is joint work with Tony Jebara at Columbia University.

Related papers: A. Weller and T. Jebara, “Approximating the Bethe Partition Function” . Uncertainty in Artificial Intelligence (UAI), 2014. A. Weller, K. Tang, D. Sontag and T. Jebara, “Understanding the Bethe Approximation: When and How can it go Wrong?” . Uncertainty in Artificial Intelligence (UAI), 2014.