2012/083 - Optimization and Sampling for NLP from a Unified Viewpoint
Marc Dymetman, Guillaume Bouchard, Simon Carter
24th International Conference on Computational Linguistics IIT Bombay, Mumbai, India, 8-15 December, 2012.
The OS* algorithm is a unified approach to exact optimization and sampling, based on incremental refinements of a functional upper bound, which combines ideas of adaptive rejection sampling and of A* optimization search. We first give a detailed description of OS*. We then explain how it can be applied to several NLP tasks, giving more details on two such applications: (i) decoding and sampling with a high-order HMM, and (ii) decoding and sampling with the intersection of a PCFG and a high-order LM.