Using Sketches to Estimate Associations

Proceedings of Human Language Technology Conference and Conference on Empirical Methods in Natural Language Processing (HLT/EMNLP), pages 708–715, Vancouver, October 2005. c⃝2005 Association for Computational Linguistics Using Sketches to Estimate Associations Ping Li Department of Statistics Stanford University Stanford, California 94305 pingli@stat.stanford.edu Kenneth W. Church Microsoft Research One Microsoft Way Redmond, Washington 98052 church@microsoft.com Abstract We should not have to look at the en- tire corpus (e.g., the Web) to know if two words are associated or not.1 A powerful sampling technique called Sketches was originally introduced to remove duplicate Web pages. We generalize sketches to estimate contingency tables and associa- tions, using a maximum likelihood esti- mator to find the most likely contingency table given the sample, the margins (doc- ument frequencies) and the size of the collection. Not unsurprisingly, computa- tional work and statistical accuracy (vari- ance or errors) depend on sampling rate, as will be shown both theoretically and empirically. Sampling methods become more and more important with larger and larger collections. At Web scale, sampling rates as low as 10−4 may suffice. 1 Introduction Word associations (co-occurrences) have a wide range of applications including: Speech Recogni- tion, Optical Character Recognition and Information Retrieval (IR) (Church and Hanks, 1991; Dunning, 1993; Manning and Schutze, 1999). It is easy to compute association scores for a small corpus, but more challenging to compute lots of scores for lots of data (e.g. the Web), with billions of web pages (D) and millions of word types (V ). For a small corpus, one could compute pair-wise associations by multiplying the (0/1) term-by-document matrix with its transpose (Deerwester et al., 1999). But this is probably infeasible at Web scale. 1This work was conducted at Microsoft while the first author was an intern. The authors thank Chris Meek, David Hecker- man, Robert Moore, Jonathan Goldstein, Trevor Hastie, David Siegmund, Art Own, Robert Tibshirani and Andrew Ng. Approximations are often good enough. We should not have to look at every document to de- termine that two words are strongly associated. A number of sampling-based randomized algorithms have been implemented at Web scale (Broder, 1997; Charikar, 2002; Ravichandran et al., 2005).2 A conventional random sample is constructed by selecting Ds documents from a corpus of D doc- uments. The (corpus) sampling rate is Ds D . Of course, word distributions have long tails. There are a few high frequency words and many low fre- quency words. It would be convenient if the sam- pling rate could vary from word to word, unlike con- ventional sampling where the sampling rate is fixed across the vocabulary. In particular, in our experi- ments, we will impose a floor to make sure that the sample contains at least 20 documents for each term. (When working at Web scale, one might raise the floor somewhat to perhaps 104.) Sampling is obviously helpful at the top of the frequency range, but not necessarily at the bottom (especially if frequencies fall below the floor). The question is: how about “ordinary” words? To …

Content truncated to 500 words