Sparse Non-negative Matrix Language Modeling

Sparse Non-negative Matrix Language Modeling Joris Pelemans Google Inc. ESAT, KU Leuven joris@pelemans.be Noam Shazeer Google Inc. noam@google.com Ciprian Chelba Google Inc. ciprianchelba@google.com Abstract We present Sparse Non-negative Matrix (SNM) estimation, a novel probability estima- tion technique for language modeling that can efficiently incorporate arbitrary features. We evaluate SNM language models on two cor- pora: the One Billion Word Benchmark and a subset of the LDC English Gigaword cor- pus. Results show that SNM language models trained with n-gram features are a close match for the well-established Kneser-Ney models. The addition of skip-gram features yields a model that is in the same league as the state- of-the-art recurrent neural network language models, as well as complementary: combin- ing the two modeling techniques yields the best known result on the One Billion Word Benchmark. On the Gigaword corpus further improvements are observed using features that cross sentence boundaries. The computational advantages of SNM estimation over both max- imum entropy and neural network estimation are probably its main strength, promising an approach that has large flexibility in combin- ing arbitrary features and yet scales gracefully to large amounts of data. 1 Introduction A statistical language model estimates probability values P(W) for strings of words W in a vocabu- lary V whose size can be in the tens or hundreds of thousands and sometimes even millions. Typically the string W is broken into sentences, or other seg- ments such as utterances in automatic speech recog- nition, which are often assumed to be conditionally independent; we will assume that W is such a seg- ment, or sentence. Estimating full sentence language models (Rosen- feld et al., 2001) is computationally hard if one seeks a properly normalized probability model1 over strings of words of finite length in V∗. A simple and sufficient way to ensure proper normalization of the model is to decompose the sentence prob- ability according to the chain rule and make sure that the end-of-sentence symbol </S> is predicted with non-zero probability in any context. With W = wN 1 = w1, . . . , wN we get: P(wN 1 ) = N � k=1 P(wk|wk−1 1 ) (1) Since the parameter space of P(wk|wk−1 1 ) is too large, the language model is forced to put the con- text wk−1 1 into an equivalence class determined by a function Φ(wk−1 1 ). As a result, P(wN 1 ) ∼= N � k=1 P(wk|Φ(wk−1 1 )) (2) Research in language modeling consists of find- ing appropriate equivalence classifiers Φ and meth- ods to estimate P(wk|Φ(wk−1 1 )). Arguably the most successful paradigm in language modeling uses the n-gram equivalence classification, that is, defines Φn-gram(wk−1 1 ) .= wk−n+1, wk−n+2, . . . , wk−1 Once the form Φ(wk−1 1 ) is specified, only the prob- lem of estimating P(wk|Φ(wk−1 1 )) from training data remains. In order to outperform the n-gram equivalence class, one must find a way to leverage long-distance context. This can be done explicitly, e.g. by combin- ing …

Content truncated to 500 words