Language Modeling with Power Low Rank Ensembles

Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 1487–1498, October 25-29, 2014, Doha, Qatar. c⃝2014 Association for Computational Linguistics Language Modeling with Power Low Rank Ensembles Ankur P. Parikh School of Computer Science Carnegie Mellon University apparikh@cs.cmu.edu Avneesh Saluja Electrical & Computer Engineering Carnegie Mellon University avneesh@cs.cmu.edu Chris Dyer School of Computer Science Carnegie Mellon University cdyer@cs.cmu.edu Eric P. Xing School of Computer Science Carnegie Mellon University epxing@cs.cmu.edu Abstract We present power low rank ensembles (PLRE), a flexible framework for n-gram language modeling where ensembles of low rank matrices and tensors are used to obtain smoothed probability estimates of words in context. Our method can be understood as a generalization of n- gram modeling to non-integer n, and in- cludes standard techniques such as abso- lute discounting and Kneser-Ney smooth- ing as special cases. PLRE training is effi- cient and our approach outperforms state- of-the-art modified Kneser Ney baselines in terms of perplexity on large corpora as well as on BLEU score in a downstream machine translation task. 1 Introduction Language modeling is the task of estimating the probability of sequences of words in a language and is an important component in, among other applications, automatic speech recognition (Ra- biner and Juang, 1993) and machine translation (Koehn, 2010). The predominant approach to lan- guage modeling is the n-gram model, wherein the probability of a word sequence P(w1, . . . , wℓ) is decomposed using the chain rule, and then a Markov assumption is made: P(w1, . . . , wℓ) ≈ �ℓ i=1 P(wi|wi−1 i−n+1). While this assumption sub- stantially reduces the modeling complexity, pa- rameter estimation remains a major challenge. Due to the power-law nature of language (Zipf, 1949), the maximum likelihood estimator mas- sively overestimates the probability of rare events and assigns zero probability to legitimate word se- quences that happen not to have been observed in the training data (Manning and Sch¨utze, 1999). Many smoothing techniques have been pro- posed to address the estimation challenge. These reassign probability mass (generally from over- estimated events) to unseen word sequences, whose probabilities are estimated by interpolating with or backing off to lower order n-gram models (Chen and Goodman, 1999). Somewhat surprisingly, these widely used smoothing techniques differ substantially from techniques for coping with data sparsity in other domains, such as collaborative filtering (Koren et al., 2009; Su and Khoshgoftaar, 2009) or matrix completion (Cand`es and Recht, 2009; Cai et al., 2010). In these areas, low rank approaches based on matrix factorization play a central role (Lee and Seung, 2001; Salakhutdinov and Mnih, 2008; Mackey et al., 2011). For example, in recom- mender systems, a key challenge is dealing with the sparsity of ratings from a single user, since typical users will have rated only a few items. By projecting the low rank representation of a user’s (sparse) preferences into the original space, an es- timate of ratings for new items is obtained. These methods are attractive due to their computational efficiency and …

Content truncated to 500 words