Probabilistic Structured Predictors

Shankar Vembu, Thomas Gärtner, Mario Boley
Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence, PMLR R7:565-572, 2009.

Abstract

We consider MAP estimators for structured prediction with exponential family models. In particular, we concentrate on the case that efficient algorithms for uniform sampling from the output space exist. We show that under this assumption (i) exact computation of the partition function remains a hard problem, and (ii) the partition function and the gradient of the log partition function can be approximated efficiently. Our main result is an approximation scheme for the partition function based on Markov Chain Monte Carlo theory. We also show that the efficient uniform sampling assumption holds in several application settings that are of importance in machine learning.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR7-vembu09a, title = {Probabilistic Structured Predictors}, author = {Vembu, Shankar and G{\"a}rtner, Thomas and Boley, Mario}, booktitle = {Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence}, pages = {565--572}, year = {2009}, editor = {Bilmes, Jeff and Ng, Andrew Y.}, volume = {R7}, series = {Proceedings of Machine Learning Research}, month = {18--21 Jun}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r7/main/assets/vembu09a/vembu09a.pdf}, url = {https://proceedings.mlr.press/r7/vembu09a.html}, abstract = {We consider MAP estimators for structured prediction with exponential family models. In particular, we concentrate on the case that efficient algorithms for uniform sampling from the output space exist. We show that under this assumption (i) exact computation of the partition function remains a hard problem, and (ii) the partition function and the gradient of the log partition function can be approximated efficiently. Our main result is an approximation scheme for the partition function based on Markov Chain Monte Carlo theory. We also show that the efficient uniform sampling assumption holds in several application settings that are of importance in machine learning.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Probabilistic Structured Predictors %A Shankar Vembu %A Thomas Gärtner %A Mario Boley %B Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2009 %E Jeff Bilmes %E Andrew Y. Ng %F pmlr-vR7-vembu09a %I PMLR %P 565--572 %U https://proceedings.mlr.press/r7/vembu09a.html %V R7 %X We consider MAP estimators for structured prediction with exponential family models. In particular, we concentrate on the case that efficient algorithms for uniform sampling from the output space exist. We show that under this assumption (i) exact computation of the partition function remains a hard problem, and (ii) the partition function and the gradient of the log partition function can be approximated efficiently. Our main result is an approximation scheme for the partition function based on Markov Chain Monte Carlo theory. We also show that the efficient uniform sampling assumption holds in several application settings that are of importance in machine learning. %Z Reissued by PMLR on 04 October 2026.
APA
Vembu, S., Gärtner, T. & Boley, M.. (2009). Probabilistic Structured Predictors. Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R7:565-572 Available from https://proceedings.mlr.press/r7/vembu09a.html. Reissued by PMLR on 04 October 2026.

Related Material