Scalable semidefinite relaxation for maximum a posterior estimation

Qixing Huang, Yuxin Chen, Leonidas Guibas

Research output: Chapter in Book/Report/Conference proceedingConference contribution

6 Scopus citations

Abstract

Maximum a posteriori (MAP) inference over discrete Markov random fields is a fundamental task spanning a wide spectrum of real-world applications, which is known to be NP-hard for general graphs. In this paper, we propose a novel semidefinite relaxation formulation (referred to as SDR) to estimate the MAP assignment. Algorithmically, we develop an accelerated variant of the alternating direction method of multipliers (referred to as SDPAD-LR) that can effectively exploit the special structure of the new relaxation. Encouragingly, the proposed procedure allows solving SDR for large-scale problems, e.g., problems on a grid graph comprising hundreds of thousands of variables with multiple states per node. Compared with prior SDP solvers, SDPAD-LR is capable of attaining comparable accuracy while exhibiting remarkably improved scalability, in contrast to the commonly held belief that semidefinite relaxation can only been applied on small-scale MRF problems. We have evaluated the performance of SDR on various benchmark datasets including OPENGM2 and PIC in terms of boththe quality of the solutions and computation time. Experimental results demonstrate that for a broad class of problems, SDPAD-LR outperforms state-of-the-art algorithms in producing better MAP assignments in an efficient manner.

Original languageEnglish (US)
Title of host publication31st International Conference on Machine Learning, ICML 2014
PublisherInternational Machine Learning Society (IMLS)
Pages1227-1241
Number of pages15
ISBN (Electronic)9781634393973
StatePublished - Jan 1 2014
Externally publishedYes
Event31st International Conference on Machine Learning, ICML 2014 - Beijing, China
Duration: Jun 21 2014Jun 26 2014

Publication series

Name31st International Conference on Machine Learning, ICML 2014
Volume2

Other

Other31st International Conference on Machine Learning, ICML 2014
CountryChina
CityBeijing
Period6/21/146/26/14

All Science Journal Classification (ASJC) codes

  • Artificial Intelligence
  • Computer Networks and Communications
  • Software

Fingerprint Dive into the research topics of 'Scalable semidefinite relaxation for maximum a posterior estimation'. Together they form a unique fingerprint.

  • Cite this

    Huang, Q., Chen, Y., & Guibas, L. (2014). Scalable semidefinite relaxation for maximum a posterior estimation. In 31st International Conference on Machine Learning, ICML 2014 (pp. 1227-1241). (31st International Conference on Machine Learning, ICML 2014; Vol. 2). International Machine Learning Society (IMLS).