Tree block coordinate descent for MAP in graphical models

David Sontag, Tommi Jaakkola

Research output: Contribution to journalConference articlepeer-review


A number of linear programming relaxations have been proposed for finding most likely settings of the variables (MAP) in large probabilistic models. The relaxations are often succinctly expressed in the dual and reduce to different types of reparameterizations of the original model. The dual objectives are typically solved by performing local block coordinate descent steps. In this work, we show how to perform block coordinate descent on spanning trees of the graphical model. We also show how all of the earlier dual algorithms are related to each other, giving transformations from one type of reparameterization to another while maintaining monotonicity relative to a common objective function. Finally, we quantify when the MAP solution can and cannot be decoded directly from the dual LP relaxation.

Original languageEnglish (US)
Pages (from-to)544-551
Number of pages8
JournalJournal of Machine Learning Research
StatePublished - 2009
Event12th International Conference on Artificial Intelligence and Statistics, AISTATS 2009 - Clearwater, FL, United States
Duration: Apr 16 2009Apr 18 2009

ASJC Scopus subject areas

  • Software
  • Artificial Intelligence
  • Control and Systems Engineering
  • Statistics and Probability


Dive into the research topics of 'Tree block coordinate descent for MAP in graphical models'. Together they form a unique fingerprint.

Cite this