Poster
Simple MAP Inference via Low-Rank Relaxations
Roy Frostig · Sida Wang · Percy Liang · Christopher D Manning

Mon Dec 8th 07:00 -- 11:59 PM @ Level 2, room 210D #None

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, followed by randomized rounding. 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.

Author Information

Roy Frostig (Google Research)
Sida Wang (Facebook AI Research)
Percy Liang (Stanford University)
Christopher D Manning (Stanford University)

More from the Same Authors