Optimization and Sampling for NLP from a Unified Viewpoint
Marc Dymetman, Guillaume Bouchard, Simon Carter
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.
24th International Conference on Computational Linguistics IIT Bombay, Mumbai, India, 8-15 December, 2012.
2012-083paper.pdf (1.14 MB)
2012-083slides.pdf (1.19 MB)