Sketching Techniques for Large Scale NLP

Amit Goyal, Jagadeesh Jagarlamudi, Hal Daumé Iii, Suresh VenkatasubramanianWAC @ NAACL 2010 · OpenReview

Abstract

Amit Goyal, Jagadeesh Jagarlamudi, Hal Daumé III, Suresh Venkatasubramanian. Proceedings of the NAACL HLT 2010 Sixth Web as Corpus Workshop.

2010.

Introduction: The Big Data Bottleneck

In Natural Language Processing (NLP), the availability of massive datasets has historically driven performance improvements. However, this "more is better" approach faces a significant technical hurdle: the vocabulary explosion. While the number of unique words in a corpus grows relatively slowly, the number of unique word pairs (bigrams) grows exponentially. For instance, a 577 MB corpus containing 63,000 unique words can generate over 118 million unique word pairs.

Growth of unique words vs. unique word-pairs as corpus size increases on a log scale.

Storing exact counts for these billions of items in traditional hash maps quickly exceeds the RAM capacity of standard workstations. Researchers typically solve this by using distributed clusters (e.g., MapReduce) or by discarding low-frequency events. This paper explores an alternative: using probabilistic "sketches" to store approximate frequencies in a fraction of the memory.

Methodology: Count-Min and Conservative Updates

The authors utilize the Count-Min (CM) Sketch, a sub-linear space data structure designed for frequency estimation. A CM Sketch consists of a 2D array of counters ($d$ rows by $w$ columns), where each row is associated with a unique hash function. When an item is processed, it is hashed $d$ times, and the corresponding counter in each row is incremented. To query an item's frequency, one takes the minimum value across the $d$ hashed locations. This minimum provides an upper bound on the true frequency, as collisions only cause overestimation.

The Conservative Update (CU) Heuristic

The core innovation presented is the application of a Conservative Update (CU) to the CM Sketch. In a standard update, all $d$ counters are incremented. In a CU update, the system first queries the current minimum value among the $d$ counters. Only the counters that currently hold this minimum value are incremented.

Comparison of update mechanisms for Count-Min (CM) and Conservative Update (CU) sketches.

This heuristic significantly slows down the "inflation" of counters caused by collisions, particularly for rare items that might otherwise be overshadowed by frequent ones. The authors found that this simple change could halve the average relative error.

Key Results and Insights

The approach was evaluated using the Gigaword Corpus and massive web crawls (up to 31 GB). The experiments yielded several critical findings:

  • Memory Efficiency: The authors successfully stored frequency counts from 37 GB of web data using only 2 billion counters, requiring approximately 8 GB of RAM. This represents a 30x reduction compared to the raw data stream.
  • High Accuracy: In a Semantic Orientation task (calculating Pointwise Mutual Information to determine sentiment), the CU-Sketch achieved 76.96% accuracy, nearly matching the 77.11% achieved by exact counting.
  • Sketch Geometry: For NLP data, "shallow" sketches (e.g., 3 rows) with high width were found to be more effective than deeper sketches, provided the rows were wide enough to minimize collisions.

Conclusion

Sketching techniques, particularly when enhanced with conservative updates, allow for sophisticated NLP tasks to be performed on commodity hardware. While the CU heuristic prevents item deletion, its benefits in memory efficiency and accuracy make it a powerful tool for processing the "Web as Corpus." Future work includes applying these methods to word sense disambiguation and large-scale language modeling for machine translation.

Summary updated

BibTeX
@inproceedings{goyal2010sketching,
  author = {Amit Goyal and Jagadeesh Jagarlamudi and Hal Daumé III and Suresh Venkatasubramanian},
  title = {{Sketching Techniques for Large Scale NLP}},
  booktitle = {WAC @ NAACL},
  year = {2010},
  url = {https://openreview.net/forum?id=Tvp3kC4zOhe},
}
Figure