Paper: Exact Sampling and Decoding in High-Order Hidden Markov Models

ACL ID D12-1103
Title Exact Sampling and Decoding in High-Order Hidden Markov Models
Venue Conference on Empirical Methods in Natural Language Processing
Session Main Conference
Year 2012
Authors

We present a method for exact optimization and sampling from high order Hidden Markov Models (HMMs), which are generally han- dled by approximation techniques. Motivated by adaptive rejection sampling and heuris- tic search, we propose a strategy based on sequentially refining a lower-order language model that is an upper bound on the true model we wish to decode and sample from. This allows us to build tractable variable-order HMMs. The ARPA format for language mod- els is extended to enable an efficient use of the max-backoff quantities required to compute the upper bound. We evaluate our approach on two problems: a SMS-retrieval task and a POS tagging experiment using 5-gram mod- els. Results show that the same approach can be used for exact optimization and sampling, while explicitly c...