Optimization and Sampling for NLP from a Unified Viewpoint
Marc Dymetman, Guillaume Bouchard, Carter, S., B. Bhattacharyya, A. Ekbal, S Saha, Johnson, M., D. Molla-Aliod, M. Dras · UvA-DARE (University of Amsterdam) · 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. 1