Optimization and Sampling for NLP from a Unified Viewpoint

Open Access
Authors
  • M. Dymetman
  • G. Bouchard
  • S. Carter
Publication date 2012
Host editors
  • B. Bhattacharyya
  • A. Ekbal
  • S. Saha
  • M. Johnson
  • D. Molla-Aliod
  • M. Dras
Book title Proceedings of the First International Workshop on Optimization Techniques for Human Language Technology: 24th International Conference on Computational Linguistics: COLING 2012: 9 December 2012
Event First International Workshop on Optimization Techniques for Human Language Technology
Pages (from-to) 79-94
Publisher Mumbay: Indian Institute of Technology Bombay
Organisations
  • Faculty of Science (FNWI) - Informatics Institute (IVI)
Abstract 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.
Document type Conference contribution
Language English
Published at
Downloads
W12-6106 (Final published version)
Permalink to this page
Back