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: (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. |
Biography |