A Fast Re-scoring Strategy to Capture Long-Distance Dependencies

Proceedings of the 2011 Conference on Empirical Methods in Natural Language Processing, pages 1116–1127, Edinburgh, Scotland, UK, July 27–31, 2011. c⃝2011 Association for Computational Linguistics A Fast Re-scoring Strategy to Capture Long-Distance Dependencies Anoop Deoras HLT-COE and CLSP Johns Hopkins University Baltimore MD 21218, USA adeoras@jhu.edu, Tom´aˇs Mikolov Brno University of Technology Speech@FIT Czech Republic imikolov@fit.vutbr.cz, Kenneth Church HLT-COE and CLSP Johns Hopkins University Baltimore MD 21218, USA kenneth.church@jhu.edu Abstract A re-scoring strategy is proposed that makes it feasible to capture more long-distance de- pendencies in the natural language. Two pass strategies have become popular in a num- ber of recognition tasks such as ASR (au- tomatic speech recognition), MT (machine translation) and OCR (optical character recog- nition). The first pass typically applies a weak language model (n-grams) to a lattice and the second pass applies a stronger lan- guage model to N best lists. The stronger lan- guage model is intended to capture more long- distance dependencies. The proposed method uses RNN-LM (recurrent neural network lan- guage model), which is a long span LM, to re- score word lattices in the second pass. A hill climbing method (iterative decoding) is pro- posed to search over islands of confusability in the word lattice. An evaluation based on Broadcast News shows speedups of 20 over basic N best re-scoring, and word error rate reduction of 8% (relative) on a highly compet- itive setup. 1 Introduction Statistical Language Models (LMs) have received considerable attention in the past few decades. They have proved to be an essential component in many statistical recognition systems such as ASR (au- tomatic speech recognition), MT (machine trans- lation) and OCR (optical character recognition). The task of a language model is to assign prob- ability to any word sequence possible in the lan- guage. The probability of the word sequence W ≡ w1, . . . , wm ≡ wm 1 is typically factored using the chain rule: P(wm 1 ) = m � i=1 P(wi|wi−1 1 ) (1) In modern statistical recognition systems, an LM tends to be restricted to simple n-gram models, where the distribution of the predicted word depends on the previous (n − 1) words i.e. P(wi|wi−1 1 ) ≈ P(wi|wi−1 i−n+1). Noam Chomsky argued that n-grams cannot learn long-distance dependencies that span over more than n words (Chomsky, 1957, pp.13). While that might seem obvious in retrospect, there was a lot of ex- citement at the time over the Shannon-McMillan- Breiman Theorem (Shannon, 1948) which was inter- preted to say that, in the limit, under just a couple of minor caveats and a little bit of not-very-important fine print, n-gram statistics are sufficient to capture all the information in a string (such as an English sentence). Chomsky realized that while that may be true in the limit, n-grams are far from the most parsi- monious representation of many linguistic facts. In a practical system, we will have to truncate n-grams at some (small) fixed n (such as trigrams or perhaps 5-grams). Truncated n-gram …

Content truncated to 500 words