Scaling Distributional Similarity to Large Corpora

Proceedings of the 21st International Conference on Computational Linguistics and 44th Annual Meeting of the ACL, pages 361–368, Sydney, July 2006. c⃝2006 Association for Computational Linguistics Scaling Distributional Similarity to Large Corpora James Gorman and James R. Curran School of Information Technologies University of Sydney NSW 2006, Australia {jgorman2,james}@it.usyd.edu.au Abstract Accurately representing synonymy using distributional similarity requires large vol- umes of data to reliably represent infre- quent words. However, the na¨ıve nearest- neighbour approach to comparing context vectors extracted from large corpora scales poorly (O(n2) in the vocabulary size). In this paper, we compare several existing approaches to approximating the nearest- neighbour search for distributional simi- larity. We investigate the trade-off be- tween efficiency and accuracy, and find that SASH (Houle and Sakuma, 2005) pro- vides the best balance. 1 Introduction It is a general property of Machine Learning that increasing the volume of training data increases the accuracy of results. This is no more evident than in Natural Language Processing (NLP), where massive quantities of text are required to model rare language events. Despite the rapid increase in computational power available for NLP systems, the volume of raw data available still outweighs our ability to process it. Unsupervised learning, which does not require the expensive and time- consuming human annotation of data, offers an opportunity to use this wealth of data. Curran and Moens (2002) show that synonymy extraction for lexical semantic resources using distributional similarity produces continuing gains in accuracy as the volume of input data increases. Extracting synonymy relations using distribu- tional similarity is based on the distributional hy- pothesis that similar words appear in similar con- texts. Terms are described by collating informa- tion about their occurrence in a corpus into vec- tors. These context vectors are then compared for similarity. Existing approaches differ primarily in their definition of “context”, e.g. the surrounding words or the entire document, and their choice of distance metric for calculating similarity between the context vectors representing each term. Manual creation of lexical semantic resources is open to the problems of bias, inconsistency and limited coverage. It is difficult to account for the needs of the many domains in which NLP tech- niques are now being applied and for the rapid change in language use. The assisted or auto- matic creation and maintenance of these resources would be of great advantage. Finding synonyms using distributional similar- ity requires a nearest-neighbour search over the context vectors of each term. This is computation- ally intensive, scaling to O(n2m) for the number of terms n and the size of their context vectors m. Increasing the volume of input data will increase the size of both n and m, decreasing the efficiency of a na¨ıve nearest-neighbour approach. Many approaches to reduce this complexity have been suggested. In this paper we evaluate state-of-the-art techniques proposed to solve this problem. We find that the Spatial Approximation Sample Hierarchy (Houle and Sakuma, 2005) pro- vides the best accuracy/efficiency trade-off. 2 Distributional Similarity Measuring distributional similarity first requires the …

Content truncated to 500 words