Tree Block Coordinate Descent for MAP in Graphical Models

David Sontag, Tommi Jaakkola
; Proceedings of the Twelth International Conference on Artificial Intelligence and Statistics, PMLR 5:544-551, 2009.

Abstract

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.

Cite this Paper


BibTeX
@InProceedings{pmlr-v5-sontag09a, title = {Tree Block Coordinate Descent for MAP in Graphical Models}, author = {David Sontag and Tommi Jaakkola}, booktitle = {Proceedings of the Twelth International Conference on Artificial Intelligence and Statistics}, pages = {544--551}, year = {2009}, editor = {David van Dyk and Max Welling}, volume = {5}, series = {Proceedings of Machine Learning Research}, address = {Hilton Clearwater Beach Resort, Clearwater Beach, Florida USA}, month = {16--18 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v5/sontag09a/sontag09a.pdf}, url = {http://proceedings.mlr.press/v5/sontag09a.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T Tree Block Coordinate Descent for MAP in Graphical Models %A David Sontag %A Tommi Jaakkola %B Proceedings of the Twelth International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2009 %E David van Dyk %E Max Welling %F pmlr-v5-sontag09a %I PMLR %J Proceedings of Machine Learning Research %P 544--551 %U http://proceedings.mlr.press %V 5 %W PMLR %X 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.
RIS
TY - CPAPER TI - Tree Block Coordinate Descent for MAP in Graphical Models AU - David Sontag AU - Tommi Jaakkola BT - Proceedings of the Twelth International Conference on Artificial Intelligence and Statistics PY - 2009/04/15 DA - 2009/04/15 ED - David van Dyk ED - Max Welling ID - pmlr-v5-sontag09a PB - PMLR SP - 544 DP - PMLR EP - 551 L1 - http://proceedings.mlr.press/v5/sontag09a/sontag09a.pdf UR - http://proceedings.mlr.press/v5/sontag09a.html AB - 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. ER -
APA
Sontag, D. & Jaakkola, T.. (2009). Tree Block Coordinate Descent for MAP in Graphical Models. Proceedings of the Twelth International Conference on Artificial Intelligence and Statistics, in PMLR 5:544-551

Related Material