Exact Sampling and Decoding in High-Order Hidden Markov Models

Proceedings of the 2012 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning, pages 1125–1134, Jeju Island, Korea, 12–14 July 2012. c⃝2012 Association for Computational Linguistics Exact Sampling and Decoding in High-Order Hidden Markov Models Simon Carter∗ ISLA, University of Amsterdam Science Park 904, 1098 XH Amsterdam, The Netherlands s.c.carter@uva.nl Marc Dymetman Guillaume Bouchard Xerox Research Centre Europe 6, chemin de Maupertuis 38240 Meylan, France {first.last}@xrce.xerox.com Abstract 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 constructing only a fraction of the total implicit state-space. 1 Introduction In NLP, sampling is important for many real tasks, such as: (i) diversity in language generation or machine translation (proposing multiple alternatives which are not clustered around a single maximum); (ii) Bayes error minimization, for instance in Statis- tical Machine Translation (Kumar and Byrne, 2004); (iii) learning of parametric and non-parametric Bayesian models (Teh, 2006). However, most practical sampling algorithms are based on MCMC, i.e. they are based on local moves ∗This work was conducted during an internship at XRCE. starting from an initial valid configuration. Often, these algorithms are stuck in local minima, i.e. in a basin of attraction close to the initialization, and the method does not really sample the whole state space. This is a problem when there are ambiguities in the distribution we want to sample from: by hav- ing a local approach such as MCMC, we might only explore states that are close to a given configuration. The necessity of exact sampling can be ques- tioned in practice. Approximate sampling tech- niques have been developed over the last century and seem sufficient for most purposes. However, the cases where one actually knows the quality of a sampling algorithm are very rare, and it is com- mon practice to forget about the approximation and simply treat the result of a sampler as a set of i.i.d. data. Exact sampling provides a de-facto guarantee that the samples are truly independent. This is par- ticularly relevant when one uses a cascade of algo- rithms in complex NLP processing chains, as shown by (Finkel et al., 2006) in their work on linguistic annotation pipelines. In this paper, we present an approach for exact decoding and sampling with an HMM whose hid- den layer is a high-order language model …

Content truncated to 500 words