Event Location: NSH 1507

Abstract: MAP inference in MRFs (or energy minimization) is known to be NP-hard in
general, and thus research has focussed on either finding efficiently
solvable subclasses (eg trees via BP), or approximate inference algorithms
(eg Loopy BP and Tree-reweighted message passing).

In this talk, I will first present a unifying perspective of these
approximate techniques — called “Decomposition Methods”. These are
methods that decompose the given problem over a graph into tractable
subproblems over subgraphs and then employ message passing over these
subgraphs to get a global solution. This provides a new way of thinking
about BP and TRW as successive steps in a hierarchy of decomposition
methods. Using this framework, we take the first step towards extending
this hierarchy beyond trees. We leverage a new class of graphs amenable to
exact inference, called outer-planar graphs, and propose an approximate
inference algorithm called Outer- Planar Decomposition (OPD). OPD is a
strict generalization of BP and TRW, and contains both of them as special
cases. In fact, OPD is guaranteed to be a strictly better approximation
than TRW. Our experiments show that this extension beyond trees is indeed
very powerful — OPD outperforms current state- of-art inference methods
on hard non-submodular synthetic problems and is competitive on real
vision applications.

Joint work with Andrew Gallagher (Eastman Kodak), Devi Parikh (TTI-C) and
Tsuhan Chen (Cornell, CMU) (To appear at CVPR 2010)