UCL ELLIS

Recent results on the Bethe approximation

Speaker	Adrian Weller
Affiliation	University of Cambridge
Date	Friday, 27 March 2015
Time	13:00-14:00
Location	Zoom
Link	Roberts G06 (Sir Ambrose Fleming lecture theatre)
Event series	DeepMind/ELLIS CSML Seminar Series
Abstract	Belief propagation is widely used for approximate inference in undirected graphical models, and rapidly returns an exact solution for a model with no cycles. If cycles are present, however, ‘loopy belief propagation’ (LBP) still often performs well but may not converge at all. It was shown previously that stable fixed points of LBP correspond to local minima of a function termed the Bethe free energy. The global minimum of the Bethe free energy defines the Bethe partition function. In this seminar, we shall cover two aspects of recent work on the Bethe approximation, focusing on the class of binary pairwise (Ising) models: (i) It was proved using graph covers (Ruozzi, 2012) that the Bethe partition function is upper bounded by the true partition function for a binary pairwise model that is attractive. Here we provide a new, arguably simpler proof from first principles. We make use of the idea of clamping a variable to a particular value. For an attractive model, we show that summing over the Bethe partition functions for each sub-model obtained after clamping any variable can only raise (and hence improve) the approximation. In fact, we derive a stronger result that may have other useful implications. Repeatedly clamping until we obtain a model with no cycles, where the Bethe approximation is exact, yields the result. We also provide a related lower bound on a broad class of approximate partition functions of general pairwise multi-label models that depends only on the topology. We demonstrate that clamping a few wisely chosen variables can be of practical value by dramatically reducing approximation error. (ii) We describe a method that is guaranteed to return an epsilon-approximation to the (global optimum) Bethe partition function - to our knowledge, the first such method. For an attractive model, we demonstrate a fully polynomial-time approximation scheme (FPTAS). This addresses an open theoretical question, has practical value for small problems and allows the merits of other approaches to be tested. Slides and papers are available at the speaker website Part (i) relates to Weller and Jebara, Clamping variables and approximate inference, NIPS 2014 (oral). Part (ii) relates to Weller and Jebara, Approximating the Bethe partition function, UAI 2014. Dr Adrian Weller completed a PhD in 2014 at Columbia University, advised by Prof Tony Jebara, and is now a researcher in the Machine Learning Group at the University of Cambridge, working with Prof Zoubin Ghahramani.
Biography