Approximate Scalable Bounded Space Sketch for Large Data NLP

Proceedings of the 2011 Conference on Empirical Methods in Natural Language Processing, pages 250–261, Edinburgh, Scotland, UK, July 27–31, 2011. c⃝2011 Association for Computational Linguistics Approximate Scalable Bounded Space Sketch for Large Data NLP Amit Goyal and Hal Daum´e III Dept. of Computer Science University of Maryland College Park, MD 20742 {amit,hal}@umiacs.umd.edu Abstract We exploit sketch techniques, especially the Count-Min sketch, a memory, and time effi- cient framework which approximates the fre- quency of a word pair in the corpus without explicitly storing the word pair itself. These methods use hashing to deal with massive amounts of streaming text. We apply Count- Min sketch to approximate word pair counts and exhibit their effectiveness on three im- portant NLP tasks. Our experiments demon- strate that on all of the three tasks, we get performance comparable to Exact word pair counts setting and state-of-the-art system. Our method scales to 49 GB of unzipped web data using bounded space of 2 billion counters (8 GB memory). 1 Introduction There is more data available today on the web than there has ever been and it keeps increasing. Use of large data in the Natural Language Processing (NLP) community is not new. Many NLP problems (Brants et al., 2007; Turney, 2008; Ravichandran et al., 2005) have benefited from having large amounts of data. However, processing large amounts of data is still challenging. This has motivated NLP community to use com- modity clusters. For example, Brants et al. (2007) used 1500 machines for a day to compute the rela- tive frequencies of n-grams from 1.8TB of web data. In another work, a corpus of roughly 1.6 Terawords was used by Agirre et al. (2009) to compute pair- wise similarities of the words in the test sets using the MapReduce infrastructure on 2, 000 cores. How- ever, the inaccessibility of clusters to an average user has attracted the NLP community to use streaming, randomized, and approximate algorithms to handle large amounts of data (Goyal et al., 2009; Levenberg et al., 2010; Van Durme and Lall, 2010). Streaming approaches (Muthukrishnan, 2005) provide memory and time-efficient framework to deal with terabytes of data. However, these ap- proaches are proposed to solve a singe problem. For example, our earlier work (Goyal et al., 2009) and Levenberg and Osborne (2009) build approxi- mate language models and show their effectiveness in Statistical Machine Translation (SMT). Stream- based translation models (Levenberg et al., 2010) has been shown effective to handle large parallel streaming data for SMT. In Van Durme and Lall (2009b), a Talbot Osborne Morris Bloom (TOMB) Counter (Van Durme and Lall, 2009a) was used to find the top-K verbs “y” given verb “x” using the highest approximate online Pointwise Mutual Infor- mation (PMI) values. In this paper, we explore sketch techniques, especially the Count-Min sketch (Cormode and Muthukrishnan, 2004) to build a single model to show its effectiveness on three important NLP tasks: • Predicting the Semantic Orientation of words (Turney and Littman, 2003) • Distributional Approaches for word similarity (Agirre …

Content truncated to 500 words