Tree Block Coordinate Descent for MAP in Graphical Models

David Sontag, Tommi Jaakkola
Proceedings of the Twelfth 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 = {Sontag, David and Jaakkola, Tommi}, booktitle = {Proceedings of the Twelfth International Conference on Artificial Intelligence and Statistics}, pages = {544--551}, year = {2009}, editor = {van Dyk, David and Welling, Max}, 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 = {https://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 Twelfth 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 %P 544--551 %U https://proceedings.mlr.press/v5/sontag09a.html %V 5 %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 Twelfth International Conference on Artificial Intelligence and Statistics DA - 2009/04/15 ED - David van Dyk ED - Max Welling ID - pmlr-v5-sontag09a PB - PMLR DP - Proceedings of Machine Learning Research VL - 5 SP - 544 EP - 551 L1 - http://proceedings.mlr.press/v5/sontag09a/sontag09a.pdf UR - https://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 Twelfth International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 5:544-551 Available from https://proceedings.mlr.press/v5/sontag09a.html.

Related Material