nips nips2010 nips2010-165 nips2010-165-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Sashank J. Reddi, Sunita Sarawagi, Sundar Vishwanathan
Abstract: We propose a new LP relaxation for obtaining the MAP assignment of a binary MRF with pairwise potentials. Our relaxation is derived from reducing the MAP assignment problem to an instance of a recently proposed Bipartite Multi-cut problem where the LP relaxation is guaranteed to provide an O(log k) approximation where k is the number of vertices adjacent to non-submodular edges in the MRF. We then propose a combinatorial algorithm to efficiently solve the LP and also provide a lower bound by concurrently solving its dual to within an approximation. The algorithm is up to an order of magnitude faster and provides better MAP scores and bounds than the state of the art message passing algorithm of [1] that tightens the local marginal polytope with third-order marginal constraints. 1
[1] David Sontag, Talya Meltzer, Amir Globerson, Tommi Jaakkola, and Yair Weiss. Tightening LP Relaxations for MAP using Message Passing. In UAI, 2008.
[2] D. Koller and N. Friedman. Probabilistic Graphical Models: Principles and Techniques. MIT Press, 2009.
[3] M.I. Schlesinger. Syntactic analysis of two-dimensional visual signals in noisy conditions. Kybernetica, 1976.
[4] Chandra Chekuri, Sanjeev Khanna, Joseph (Seffi) Naor, and Leonid Zosin. Approximation Algorithms for the Metric Labeling Problem via a New Linear Programming Formulation. In SODA, 2001.
[5] Jon Kleinberg and Eva Tardos. Approximation Algorithms for Classification Problems with Pairwise Relationships: Metric Labeling and Markov Random Fields. J. ACM, 49(5):616–639, 2002.
[6] M. Wainwright, T. Jaakkola, and A. Willsky. MAP Estimation Via Agreement on Trees: Message-Passing and Linear Programming. IEEETIT: IEEE Transactions on Information Theory, 51, 2005.
[7] Tom´ s Werner. A Linear Programming Approach to Max-Sum Problem: A Review. IEEE Trans. Pattern a Anal. Mach. Intell., 29(7):1165–1179, 2007.
[8] Nic Schraudolph. Polynomial-Time Exact Inference in NP-Hard Binary MRFs via Reweighted Perfect Matching. In AISTATS, 2010.
[9] Vladimir Kolmogorov. Convergent Tree-Reweighted Message Passing for Energy Minimization. IEEE Trans. Pattern Anal. Mach. Intell., 28(10):1568–1583, 2006.
[10] Talya Meltzer, Amir Globerson, and Yair Weiss. Convergent message passing algorithms - a unifying view. In UAI, 2009.
[11] Pradeep Ravikumar, Alekh Agarwal, and Martin J. Wainwright. Message-passing for Graph-structured Linear Programs: Proximal Methods and Rounding Schemes. JMLR, 11:1043–1080, 2010.
[12] David Sontag and Tommi Jaakkola. Tree Block Coordinate Descent for MAP in Graphical Models. In AI-STATS, volume 9, pages 544–551, 2009.
[13] Endre Boros and Peter L. Hammer. Pseudo-Boolean Optimization. Discrete Applied Mathematics, 123(13):155–225, 2002.
[14] Carsten Rother, Vladimir Kolmogorov, Victor S. Lempitsky, and Martin Szummer. Optimizing Binary MRFs via Extended Roof Duality. In CVPR, 2007.
[15] Francisco Barahona and Ali Ridha Mahjoub. On the cut polytope. Math. Program., 36(2):157–173, 1986.
[16] Uri Zwick. Outward Rotations: A Tool for Rounding Solutions of Semidefinite Programming Relaxations, with Applications to MAX CUT and Other Problems. In STOC, 1999.
[17] David Sontag and Tommi Jaakkola. New Outer Bounds on the Marginal Polytope. In NIPS, 2007.
[18] M. Pawan Kumar, Vladimir Kolmogorov, and Philip H. S. Torr. An Analysis of Convex Relaxations for MAP Estimation of Discrete MRFs. JMLR, 10:71–106, 2009.
[19] Nikos Komodakis and Nikos Paragios. Beyond Loose LP-Relaxations: Optimizing MRFs by Repairing Cycles. In ECCV, 2008.
[20] Tom´ s Werner. High-arity interactions, polyhedral relaxations, and cutting plane algorithm for soft cona straint optimisation (map-mrf). In CVPR, 2008.
[21] Sreyash Kenkre and Sundar Vishwanathan. Approximation algorithms for the Bipartite Multicut problem. Information Processing Letters, 110(8-9):282 – 287, 2010.
[22] Naveen Garg, Vijay V. Vazirani, and Mihalis Yannakakis. Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications. SIAM J. Comput., 25(2):235–251, 1996.
[23] Naveen Garg and Jochen Knemann. Faster and Simpler Algorithms for Multicommodity Flow and Other Fractional Packing Problems. SIAM J. Comput. 37(2): (2007), 37(2):630–652, 2007.
[24] Amir Globerson and Tommi Jaakkola. Approximate inference using planar graph decomposition. In NIPS, 2006.
[25] Lisa Fleischer. Approximating Fractional Multicommodity Flow Independent of the Number of Commodities. SIAM J. Discrete Math., 13(4):505–520, 2000.
[26] D Batra, A C Gallagher, D Parikh, and T Chen. Beyond trees: Mrf inference via outer-planar decomposition. In CVPR, 2010.
[27] Kyomin Jung, Pushmeet Kohli, and Devavrat Shah. Local Rules for Global MAP: When Do They Work? In NIPS. 2009.
[28] David Sontag. Cutting plane algorithms for variational inference in graphical models. Master’s thesis, MIT, Department of Electrical Engineering and Computer Science, 2007. 9