Streaming for large scale NLP: Language Modeling

Human Language Technologies: The 2009 Annual Conference of the North American Chapter of the ACL, pages 512–520, Boulder, Colorado, June 2009. c⃝2009 Association for Computational Linguistics Streaming for large scale NLP: Language Modeling Amit Goyal, Hal Daum´e III, and Suresh Venkatasubramanian University of Utah, School of Computing {amitg,hal,suresh}@cs.utah.edu Abstract In this paper, we explore a streaming al- gorithm paradigm to handle large amounts of data for NLP problems. We present an efficient low-memory method for construct- ing high-order approximate n-gram frequency counts. The method is based on a determinis- tic streaming algorithm which efficiently com- putes approximate frequency counts over a stream of data while employing a small mem- ory footprint. We show that this method eas- ily scales to billion-word monolingual corpora using a conventional (8 GB RAM) desktop machine. Statistical machine translation ex- perimental results corroborate that the result- ing high-n approximate small language model is as effective as models obtained from other count pruning methods. 1 Introduction In many NLP problems, we are faced with the chal- lenge of dealing with large amounts of data. Many problems boil down to computing relative frequen- cies of certain items on this data. Items can be words, patterns, associations, n-grams, and others. Language modeling (Chen and Goodman, 1996), noun-clustering (Ravichandran et al., 2005), con- structing syntactic rules for SMT (Galley et al., 2004), and finding analogies (Turney, 2008) are examples of some of the problems where we need to compute relative frequencies. We use language modeling as a canonical example of a large-scale task that requires relative frequency estimation. Computing relative frequencies seems like an easy problem. However, as corpus sizes grow, it becomes a highly computational expensive task. Cutoff Size BLEU NIST MET Exact 367.6m 28.73 7.691 56.32 2 229.8m 28.23 7.613 56.03 3 143.6m 28.17 7.571 56.53 5 59.4m 28.33 7.636 56.03 10 18.3m 27.91 7.546 55.64 100 1.1m 28.03 7.607 55.91 200 0.5m 27.62 7.550 55.67 Table 1: Effect of count-based pruning on SMT per- formance using EAN corpus. Results are according to BLEU, NIST and METEOR (MET) metrics. Bold #s are not statistically significant worse than exact model. Brants et al. (2007) used 1500 machines for a day to compute the relative frequencies of n-grams (summed over all orders from 1 to 5) from 1.8TB of web data. Their resulting model contained 300 million unique n-grams. It is not realistic using conventional computing re- sources to use all the 300 million n-grams for ap- plications like speech recognition, spelling correc- tion, information extraction, and statistical machine translation (SMT). Hence, one of the easiest way to reduce the size of this model is to use count-based pruning which discards all n-grams whose count is less than a pre-defined threshold. Although count- based pruning is quite simple, yet it is effective for machine translation. As we do not have a copy of the web, we will use a portion of gigaword i.e. EAN (see Section 4.1) to show the effect of count-based pruning on performance of SMT (see …

Content truncated to 500 words