New outer bounds on the marginal polytope

David Sontag, Tommi Jaakkola

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

Abstract

We give a new class of outer bounds on the marginal polytope, and propose a cutting-plane algorithm for efficiently optimizing over these constraints. When combined with a concave upper bound on the entropy, this gives a new variational inference algorithm for probabilistic inference in discrete Markov Random Fields (MRFs). Valid constraints on the marginal polytope are derived through a series of projections onto the cut polytope. As a result, we obtain tighter upper bounds on the log-partition function. We also show empirically that the approximations of the marginals are significantly more accurate when using the tighter outer bounds. Finally, we demonstrate the advantage of the new constraints for finding the MAP assignment in protein structure prediction.

Original languageEnglish (US)
Title of host publicationAdvances in Neural Information Processing Systems 20 - Proceedings of the 2007 Conference
StatePublished - 2009
Event21st Annual Conference on Neural Information Processing Systems, NIPS 2007 - Vancouver, BC, Canada
Duration: Dec 3 2007Dec 6 2007

Publication series

NameAdvances in Neural Information Processing Systems 20 - Proceedings of the 2007 Conference

Other

Other21st Annual Conference on Neural Information Processing Systems, NIPS 2007
CountryCanada
CityVancouver, BC
Period12/3/0712/6/07

ASJC Scopus subject areas

  • Information Systems

Fingerprint Dive into the research topics of 'New outer bounds on the marginal polytope'. Together they form a unique fingerprint.

  • Cite this

    Sontag, D., & Jaakkola, T. (2009). New outer bounds on the marginal polytope. In Advances in Neural Information Processing Systems 20 - Proceedings of the 2007 Conference (Advances in Neural Information Processing Systems 20 - Proceedings of the 2007 Conference).