Beyond trees: MRF inference via outer-planar decomposition
Batra D. Gallagher A.C. Parikh D. Chen T.
Batra D.
Gallagher A.C.
Parikh D.
Citations
Altmetric:
Alternative Title
Abstract
Maximum a posteriori (MAP) inference in Markov Random Fields (MRFs) is an NP-hard problem, and thus research has focussed on either finding efficiently solvable subclasses (e.g. trees), or approximate algorithms (e.g. Loopy Belief Propagation (BP) and Tree-reweighted (TRW) methods). This paper presents 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 merge the solutions of the subproblems into 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 a principled first step towards extending this hierarchy beyond trees. We leverage a new class of graphs amenable to exact inference, called outerplanar 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 computer vision applications.
Keywords
Source Title
Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition
Publisher
Series/Report No.
Collections
Rights
Date
2010
DOI
10.1109/CVPR.2010.5539951
Type
Conference Paper