Distributed Word Clustering for Large Scale Class-Based Language Modeling in Machine Translation

Proceedings of ACL-08: HLT, pages 755–762, Columbus, Ohio, USA, June 2008. c⃝2008 Association for Computational Linguistics Distributed Word Clustering for Large Scale Class-Based Language Modeling in Machine Translation Jakob Uszkoreit∗ Thorsten Brants Google, Inc. 1600 Amphitheatre Parkway Mountain View, CA 94303, USA {uszkoreit,brants}@google.com Abstract In statistical language modeling, one technique to reduce the problematic effects of data spar- sity is to partition the vocabulary into equiva- lence classes. In this paper we investigate the effects of applying such a technique to higher- order n-gram models trained on large corpora. We introduce a modification of the exchange clustering algorithm with improved efficiency for certain partially class-based models and a distributed version of this algorithm to effi- ciently obtain automatic word classifications for large vocabularies (>1 million words) us- ing such large training corpora (>30 billion to- kens). The resulting clusterings are then used in training partially class-based language mod- els. We show that combining them with word- based n-gram models in the log-linear model of a state-of-the-art statistical machine trans- lation system leads to improvements in trans- lation quality as indicated by the BLEU score. 1 Introduction A statistical language model assigns a probability P(w) to any given string of words wm 1 = w1, ..., wm. In the case of n-gram language models this is done by factoring the probability: P(wm 1 ) = m � i=1 P(wi|wi−1 1 ) and making a Markov assumption by approximating this by: m � i=1 P(wi|wi−1 1 ) ≈ m � i=1 p(wi|wi−1 i−n+1) Even after making the Markov assumption and thus treating all strings of preceding words as equal which ∗ Parts of this research were conducted while the author studied at the Berlin Institute of Technology do not differ in the last n − 1 words, one problem n- gram language models suffer from is that the training data is too sparse to reliably estimate all conditional probabilities P(wi|wi−1 1 ). Class-based n-gram models are intended to help overcome this data sparsity problem by grouping words into equivalence classes rather than treating them as distinct words and thus reducing the num- ber of parameters of the model (Brown et al., 1990). They have often been shown to improve the per- formance of speech recognition systems when com- bined with word-based language models (Martin et al., 1998; Whittaker and Woodland, 2001). However, in the area of statistical machine translation, espe- cially in the context of large training corpora, fewer experiments with class-based n-gram models have been performed with mixed success (Raab, 2006). Class-based n-gram models have also been shown to benefit from their reduced number of parameters when scaling to higher-order n-grams (Goodman and Gao, 2000), and even despite the increasing size and decreasing sparsity of language model training cor- pora (Brants et al., 2007), class-based n-gram mod- els might lead to improvements when increasing the n-gram order. When training class-based n-gram models on large corpora and large vocabularies, one of the prob- lems arising is the scalability of the typical cluster- …

Content truncated to 500 words