Probabilistic Structured Predictors
This work addresses a computational bottleneck in probabilistic structured prediction, which is incremental as it builds on existing methods but provides new theoretical insights and approximations for specific settings.
The paper tackles the problem of computing partition functions in structured prediction with exponential family models, showing that exact computation remains hard but efficient approximations are possible when uniform sampling from the output space is feasible, with results including an MCMC-based approximation scheme.
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.