Distributed Language Modeling for N-best List Re-ranking

Proceedings of the 2006 Conference on Empirical Methods in Natural Language Processing (EMNLP 2006), pages 216–223, Sydney, July 2006. c⃝2006 Association for Computational Linguistics Distributed Language Modeling for N-best List Re-ranking Ying Zhang Almut Silja Hildebrand Stephan Vogel Language Technologies Institute, Carnegie Mellon University 5000 Forbes Ave. Pittsburgh, PA 15213, U.S.A. {joy+, silja+, vogel+}@cs.cmu.edu Abstract In this paper we describe a novel dis- tributed language model for N-best list re-ranking. The model is based on the client/server paradigm where each server hosts a portion of the data and provides information to the client. This model al- lows for using an arbitrarily large corpus in a very efficient way. It also provides a natural platform for relevance weighting and selection. We applied this model on a 2.97 billion-word corpus and re-ranked the N-best list from Hiero, a state-of-the- art phrase-based system. Using BLEU as a metric, the re-ranked translation achieves a relative improvement of 4.8%, signifi- cantly better than the model-best transla- tion. 1 Introduction Statistical language modeling has been widely used in natural language processing applications such as Automatic Speech Recognition (ASR), Statistical Machine Translation (SMT) (Brown et al., 1993) and Information Retrieval (IR) (Ponte and Croft, 1998). Conventional n-gram language modeling counts the frequency of all the n-grams in a corpus and calculates the conditional probabilities of a word given its history of n − 1 words P(wi|wi−1 i−n+1). As the corpus size increases, building a high order language model offline becomes very expensive if it is still possible (Goodman, 2000). In this paper, we describe a new approach of language modeling using a distributed comput- ing paradigm. Distributed language modeling can make use of arbitrarily large training corpora and provides a natural way for language model adap- tation. We applied the distributed LM to the task of re- ranking the N-best list in statistical machine trans- lation and achieved significantly better translation quality when measured by the BLEU metric (Pap- ineni et al., 2001). 2 N-best list re-ranking When translating a source language sentence f into English, the SMT decoder first builds a trans- lation lattice over the source words by applying the translation model and then explores the lattice and searches for an optimal path as the best translation. The decoder uses different models, such as the translation model, n-gram language model, fertil- ity model, and combines multiple model scores to calculate the objective function value which favors one translation hypothesis over the other (Och et al., 2004). Instead of outputting the top hypothesis e(1) based on the decoder model, the decoder can out- put N (usually N = 1000) alternative hypotheses {e(r)|r = 1, . . . , N} for one source sentence and rank them according to their model scores. Figure 1 shows an example of the output from a SMT system. In this example, alternative hypoth- esis e(2) is a better translations than e(1) according to the reference (Ref) although its model score is lower. SMT models are not perfect, it is unavoidable to …

Content truncated to 500 words