On the Bethe approximation

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

• Adrian Weller (Columbia University)
• Monday 11 August 2014, 11:00-12:00
• Engineering Department, CBL Room BE-438..

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.

This talk is included in these lists:

• Seminar
• All Talks (aka the CURE list)
• Biology
• CBL important
• Cambridge Centre for Data-Driven Discovery (C2D3)
• Cambridge Forum of Science and Humanities
• Cambridge Language Sciences
• Cambridge Neuroscience Seminars
• Cambridge talks
• Chris Davis' list
• Creating transparent intact animal organs for high-resolution 3D deep-tissue imaging
• Engineering Department, CBL Room BE-438.
• Featured lists
• Guy Emerson's list
• Hanchen DaDaDash
• Inference Group Summary
• Information Engineering Division seminar list
• Interested Talks
• Joint Machine Learning Seminars
• Life Science
• Life Sciences
• ML
• Machine Learning @ CUED
• Machine Learning Summary
• Neuroscience
• Neuroscience Seminars
• Neuroscience Seminars
• Required lists for MLG
• Simon Baker's List
• Stem Cells & Regenerative Medicine
• Trust & Technology Initiative - interesting events
• bld31
• dh539
• kt532's list
• ndk22's list
• ob366-ai4er
• rp587
• yk373's list

Note that ex-directory lists are not shown.