Efficient Subsampling for Training Complex Language Models

Proceedings of the 2011 Conference on Empirical Methods in Natural Language Processing, pages 1128–1136, Edinburgh, Scotland, UK, July 27–31, 2011. c⃝2011 Association for Computational Linguistics Efficient Subsampling for Training Complex Language Models Puyang Xu puyangxu@jhu.edu Asela Gunawardana# aselag@microsoft.com Sanjeev Khudanpur khudanpur@jhu.edu Department of Electrical and Computer Engineering Center for Language and Speech Processing Johns Hopkins University Baltimore, MD 21218, USA #Microsoft Research Redmond, WA 98052, USA Abstract We propose an efficient way to train maximum entropy language models (MELM) and neural network language models (NNLM). The ad- vantage of the proposed method comes from a more robust and efficient subsampling tech- nique. The original multi-class language mod- eling problem is transformed into a set of bi- nary problems where each binary classifier predicts whether or not a particular word will occur. We show that the binarized model is as powerful as the standard model and allows us to aggressively subsample negative training examples without sacrificing predictive per- formance. Empirical results show that we can train MELM and NNLM at 1% ∼ 5% of the standard complexity with no loss in perfor- mance. 1 Introduction Language models (LM) assign probabilities to se- quences of words. They are widely used in many natural language processing applications. The prob- ability of a sequence can be modeled as a product of local probabilities, as shown in (1), where wi is the ith word, and hi is the word history preceding wi. P(w1, w2, ..., wl) = l� i=1 P(wi|hi) (1) Therefore the task of language modeling reduces to estimating a set of conditional distributions {P(w|h)}. The n-gram LM is a dominant way to parametrize P(w|h), where it is assumed that w only depends on the previous n−1 words. More complex models have also been proposed–MELM (Rosen- feld, 1996) and NNLM (Bengio et al., 2003) are two examples. Modeling P(w|h) can be seen as a multi-class classification problem. Given the history, we have to choose a word in the vocabulary, which can eas- ily be a few hundred thousand words in size. For complex models such as MELM and NNLM, this poses a computational challenge for learning, be- cause the resulting objective functions are expensive to normalize. In contrast, n-gram LMs do not suf- fer from this computational challenge. In the web era, language modelers have access to virtually un- limited amounts of data, while the computing power available to process this data is limited. Therefore, despite the demonstrated effectiveness of complex LMs, the n-gram is still the predominant approach for most real world applications. Subsampling is a simple solution to get around the constraint of computing resources. For the pur- pose of language modeling, it amounts to taking only part of the text corpus to train the LM. For complex models such as NNLM, it has been shown that subsampling can speed up training greatly, at the cost of some degradation in predictive perfor- mance (Schwenk, 2007), allowing for trade-off be- tween computational cost and LM quality. Our contribution is a novel way to …

Content truncated to 500 words