Sketch Algorithms for Estimating Point Queries in NLP

Proceedings of the 2012 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning, pages 1093–1103, Jeju Island, Korea, 12–14 July 2012. c⃝2012 Association for Computational Linguistics Sketch Algorithms for Estimating Point Queries in NLP Amit Goyal and Hal Daum´e III University of Maryland {amit,hal}@umiacs.umd.edu Graham Cormode AT&T Labs–Research graham@research.att.com Abstract Many NLP tasks rely on accurate statis- tics from large corpora. Tracking com- plete statistics is memory intensive, so recent work has proposed using compact approx- imate “sketches” of frequency distributions. We describe 10 sketch methods, including ex- isting and novel variants. We compare and study the errors (over-estimation and under- estimation) made by the sketches. We evaluate several sketches on three important NLP prob- lems. Our experiments show that one sketch performs best for all the three tasks. 1 Introduction Since the emergence of the World Wide Web, so- cial media and mobile devices, we have ever larger and richer examples of text data. Such vast cor- pora have led to leaps in the performance of many language-based tasks: the concept is that simple models trained on big data can outperform more complex models with fewer examples. However, this new view comes with its own challenges: prin- cipally, how to effectively represent such large data sets so that model parameters can be efficiently ex- tracted? One answer is to adopt compact summaries of corpora in the form of probabilistic “sketches”. In recent years, the field of Natural Language Pro- cessing (NLP) has seen tremendous growth and in- terest in the use of approximation, randomization, and streaming techniques for large-scale problems (Brants et al., 2007; Turney, 2008). Much of this work relies on tracking very many statistics. For ex- ample, storing approximate counts (Talbot and Os- borne, 2007; Van Durme and Lall, 2009a; Goyal and Daum´e III, 2011a), computing approximate as- sociation scores like Pointwise Mutual Information (Li et al., 2008; Van Durme and Lall, 2009b; Goyal and Daum´e III, 2011a), finding frequent items (like n-grams) (Goyal et al., 2009), building streaming language models (Talbot and Brants, 2008; Leven- berg and Osborne, 2009), and distributional similar- ity (Ravichandran et al., 2005; Van Durme and Lall, 2010). All these problems ultimately depend on ap- proximate counts of items (such as n-grams, word pairs and word-context pairs). Thus we focus on solving this central problem in the context of NLP applications. Sketch algorithms (Charikar et al., 2004; Cor- mode, 2011) are a memory- and time-efficient so- lution to answering point queries. Recently in NLP, we (Goyal and Daum´e III, 2011a) demonstrated that a version of the Count-Min sketch (Cormode and Muthukrishnan, 2004) accurately solves three large- scale NLP problems using small bounded memory footprint. However, there are several other sketch al- gorithms, and it is not clear why this instance should be preferred amongst these. In this work, we con- duct a systematic study and compare many sketch techniques which answer point queries with focus on large-scale NLP tasks. While sketches have been evaluated within the database …

Content truncated to 500 words