Simple MAP inference via low-rank relaxations

Roy Frostig, Sida I. Wang, Percy Liang, Christopher D. Manning

Research output: Contribution to journalConference article

7 Scopus citations

Abstract

We focus on the problem of maximum a posteriori (MAP) inference in Markov random fields with binary variables and pairwise interactions. For this common subclass of inference tasks, we consider low-rank relaxations that interpolate between the discrete problem and its full-rank semidefinite relaxation. We develop new theoretical bounds studying the effect of rank, showing that as the rank grows, the relaxed objective increases but saturates, and that the fraction in objective value retained by the rounded discrete solution decreases. In practice, we show two algorithms for optimizing the low-rank objectives which are simple to implement, enjoy ties to the underlying theory, and outperform existing approaches on benchmark MAP inference tasks.

Original languageEnglish (US)
Pages (from-to)3077-3085
Number of pages9
JournalAdvances in Neural Information Processing Systems
Volume4
Issue numberJanuary
StatePublished - Jan 1 2014
Event28th Annual Conference on Neural Information Processing Systems 2014, NIPS 2014 - Montreal, Canada
Duration: Dec 8 2014Dec 13 2014

All Science Journal Classification (ASJC) codes

  • Computer Networks and Communications
  • Information Systems
  • Signal Processing

Cite this

Frostig, R., Wang, S. I., Liang, P., & Manning, C. D. (2014). Simple MAP inference via low-rank relaxations. Advances in Neural Information Processing Systems, 4(January), 3077-3085.