Randomized Algorithms and NLP: Using Locality Sensitive Hash Functions for High Speed Noun Clustering

Proceedings of the 43rd Annual Meeting of the ACL, pages 622–629, Ann Arbor, June 2005. c⃝2005 Association for Computational Linguistics Randomized Algorithms and NLP: Using Locality Sensitive Hash Function for High Speed Noun Clustering Deepak Ravichandran, Patrick Pantel, and Eduard Hovy Information Sciences Institute University of Southern California 4676 Admiralty Way Marina del Rey, CA 90292. {ravichan, pantel, hovy}@ISI.EDU Abstract In this paper, we explore the power of randomized algorithm to address the chal- lenge of working with very large amounts of data. We apply these algorithms to gen- erate noun similarity lists from 70 million pages. We reduce the running time from quadratic to practically linear in the num- ber of elements to be computed. 1 Introduction In the last decade, the field of Natural Language Pro- cessing (NLP), has seen a surge in the use of cor- pus motivated techniques. Several NLP systems are modeled based on empirical data and have had vary- ing degrees of success. Of late, however, corpus- based techniques seem to have reached a plateau in performance. Three possible areas for future re- search investigation to overcoming this plateau in- clude: 1. Working with large amounts of data (Banko and Brill, 2001) 2. Improving semi-supervised and unsupervised al- gorithms. 3. Using more sophisticated feature functions. The above listing may not be exhaustive, but it is probably not a bad bet to work in one of the above directions. In this paper, we investigate the first two avenues. Handling terabytes of data requires more efficient algorithms than are currently used in NLP. We propose a web scalable solution to clustering nouns, which employs randomized algorithms. In doing so, we are going to explore the literature and techniques of randomized algorithms. All cluster- ing algorithms make use of some distance similar- ity (e.g., cosine similarity) to measure pair wise dis- tance between sets of vectors. Assume that we are given n points to cluster with a maximum of k fea- tures. Calculating the full similarity matrix would take time complexity n2k. With large amounts of data, say n in the order of millions or even billions, having an n2k algorithm would be very infeasible. To be scalable, we ideally want our algorithm to be proportional to nk. Fortunately, we can borrow some ideas from the Math and Theoretical Computer Science community to tackle this problem. The crux of our solution lies in defining Locality Sensitive Hash (LSH) functions. LSH functions involve the creation of short signa- tures (fingerprints) for each vector in space such that those vectors that are closer to each other are more likely to have similar fingerprints. LSH functions are generally based on randomized algorithms and are probabilistic. We present LSH algorithms that can help reduce the time complexity of calculating our distance similarity atrix to nk. Rabin (1981) proposed the use of hash func- tions from random irreducible polynomials to cre- ate short fingerprint representations for very large strings. These hash function had the nice property that the fingerprint of two identical …

Content truncated to 500 words