A Dynamic Programming Algorithm for Computing N-gram Posteriors from Lattices

Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing, pages 2388–2397, Lisbon, Portugal, 17-21 September 2015. c⃝2015 Association for Computational Linguistics. A Dynamic Programming Algorithm for Computing N-gram Posteriors from Lattices Do˘gan Can Department of Computer Science University of Southern California Los Angeles, CA, USA dogancan@usc.edu Shrikanth S. Narayanan Department of Electrical Engineering University of Southern California Los Angeles, CA, USA shri@sipi.usc.edu Abstract Efficient computation of n-gram posterior probabilities from lattices has applications in lattice-based minimum Bayes-risk de- coding in statistical machine translation and the estimation of expected document frequencies from spoken corpora. In this paper, we present an algorithm for com- puting the posterior probabilities of all n- grams in a lattice and constructing a mini- mal deterministic weighted finite-state au- tomaton associating each n-gram with its posterior for efficient storage and retrieval. Our algorithm builds upon the best known algorithm in literature for computing n- gram posteriors from lattices and lever- ages the following observations to signifi- cantly improve the time and space require- ments: i) the n-grams for which the poste- riors will be computed typically comprises all n-grams in the lattice up to a certain length, ii) posterior is equivalent to ex- pected count for an n-gram that do not re- peat on any path, iii) there are efficient al- gorithms for computing n-gram expected counts from lattices. We present exper- imental results comparing our algorithm with the best known algorithm in literature as well as a baseline algorithm based on weighted finite-state automata operations. 1 Introduction Many complex speech and natural language processing (NLP) pipelines such as Automatic Speech Recognition (ASR) and Statistical Ma- chine Translation (SMT) systems store alternative hypotheses produced at various stages of process- ing as weighted acyclic automata, also known as lattices. Each lattice stores a large number of hypotheses along with the raw system scores as- signed to them. While single-best hypothesis is typically what is desired at the end of the pro- cessing, it is often beneficial to consider a large number of weighted hypotheses at earlier stages of the pipeline to hedge against errors introduced by various subcomponents. Standard ASR and SMT techniques like discriminative training, rescoring with complex models and Minimum Bayes-Risk (MBR) decoding rely on lattices to represent in- termediate system hypotheses that will be fur- ther processed to improve models or system out- put. For instance, lattice based MBR decoding has been shown to give moderate yet consistent gains in performance over conventional MAP decoding in a number of speech and NLP applications in- cluding ASR (Goel and Byrne, 2000) and SMT (Tromble et al., 2008; Blackwood et al., 2010; de Gispert et al., 2013). Most lattice-based techniques employed by speech and NLP systems make use of posterior quantities computed from probabilistic lattices. In this paper, we are interested in two such posterior quantities: i) n-gram expected count, the expected number of occurrences of a particular n-gram in a lattice, and ii) n-gram posterior probability, the total probability of accepting paths that …

Content truncated to 500 words