Beyond Trees: MRF Inference via Outer-Planar Decomposition

Опубликовано 7 сентября 2016, 18:00

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). 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. 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) (* Unpublished work)