{"id":184610,"date":"2009-12-14T00:00:00","date_gmt":"2010-01-11T23:01:26","guid":{"rendered":"https:\/\/www.microsoft.com\/en-us\/research\/msr-research-item\/beyond-trees-mrf-inference-via-outer-planar-decomposition\/"},"modified":"2016-09-09T09:54:02","modified_gmt":"2016-09-09T16:54:02","slug":"beyond-trees-mrf-inference-via-outer-planar-decomposition","status":"publish","type":"msr-video","link":"https:\/\/www.microsoft.com\/en-us\/research\/video\/beyond-trees-mrf-inference-via-outer-planar-decomposition\/","title":{"rendered":"Beyond Trees: MRF Inference via Outer-Planar Decomposition"},"content":{"rendered":"
\n

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).<\/p>\n

I will first present a unifying perspective of these approximate techniques \u2013 called \u201cDecomposition Methods\u201d. 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 \u2013 OPD outperforms current state- of-art inference methods on hard non-submodular synthetic problems and is competitive on real vision applications.<\/p>\n