Uncertainty in Artificial Intelligence
First Name   Last Name   Password   Forgot Password   Log in!
    Proceedings         Authors   Author's Info   Article details         Search    
Probabilistic Structured Predictors
Shankar Vembu, Thomas Gartner, Mario Boley
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.
Keywords: null
Pages: 557-564
PS Link:
PDF Link: /papers/09/p557-vembu.pdf
AUTHOR = "Shankar Vembu and Thomas Gartner and Mario Boley",
TITLE = "Probabilistic Structured Predictors",
BOOKTITLE = "Proceedings of the Twenty-Fifth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-09)",
ADDRESS = "Corvallis, Oregon",
YEAR = "2009",
PAGES = "557--564"

hosted by DSL   •   site info   •   help