University of Cambridge > > Machine Learning @ CUED > On the Bethe approximation

On the Bethe approximation

Add to your list(s) Download to your calendar using vCal

If you have a question about this talk, please contact Zoubin Ghahramani.

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.

This talk is part of the Machine Learning @ CUED series.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.


© 2006-2024, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity