Probabilistic structured predictors

Shankar Vembu, Thomas Gärtner, Mario Boley

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

5 Citations (Scopus)


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.

Original languageEnglish
Title of host publicationProceedings of the 25th Conference on Uncertainty in Artificial Intelligence, UAI 2009
PublisherAUAI Press
Number of pages8
Publication statusPublished - 2009
EventConference in Uncertainty in Artificial Intelligence 2009 - Montreal, Canada
Duration: 18 Jun 200921 Jun 2009
Conference number: 25th (Proceedings)


ConferenceConference in Uncertainty in Artificial Intelligence 2009
Abbreviated titleUAI 2009
Internet address

Cite this