Augmenting Approximate Similarity Searching with Lexical Information

Proceedings of the Australasian Language Technology Workshop 2005, pages 49–56, Sydney, Australia, December 2005. Augmenting Approximate Similarity Searching with Lexical Information 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 distribu- tional similarity requires large volumes of data to reliably represent infrequent words. However, the na¨ıve nearest-neighbour approach to compare con- text vectors extracted from large corpora scales poorly. The Spatial Approximation Sample Hier- archy (SASH) is a data-structure for performing ap- proximate nearest-neighbour queries, and has been previously used to improve the scalability of dis- tributional similarity searches. We add lexical se- mantic information from WordNet to the SASH in an attempt to improve the accuracy and efficiency of similarity searches. 1 Introduction Lexical semantic resources and electronic thesauri are regularly used to solve NLP problems, includ- ing collocation discovery (Pearce, 2001), smooth- ing and estimation (Brown et al., 1992; Clark and Weir, 2001) and question answering (Pasca and Harabagiu, 2001). These use similarity relation- ships between words, as given in the resources, to enhance corpus-based statistics. It is difficult to account for the needs of the many domains in which NLP techniques are now being ap- plied and for rapid change in language use. Manual creation is expensive and time consuming, and open to the problems of bias, inconsistency and limited coverage. The assisted or automatic creation and maintenance of these resources would be of great advantage. Much of the existing work on automatically ex- tracting lexical semantic resources is based on the distributional hypothesis that similar words appear in similar contexts. Terms are described by collat- ing information about their contexts in a corpus into a vector. These context vectors are then compared for similarity. Existing approaches differ primarily in their definition of “context”, e.g. the surround- ing words or the entire document, and their choice of distance metric for calculating similarity between the context vectors representing each term. Finding synonyms using distributional similarity requires a nearest-neighbour search over the context vectors of each term. This is computationally in- tensive, scaling to the number of terms and the size of their context vectors. Curran and Moens (2002) have demonstrated that dramatically increasing the volume of raw input text used to extract context in- formation significantly improves the quality of ex- tracted synonyms. This will increase the size of the vocabulary, decreasing the efficiency of a na¨ıve nearest-neighbour approach. Using a data-structure such as the Spatial Ap- proximation Sample Hierarchy (SASH; Houle and Sakuma, 2005) allows us to reduce the original � � � � complexity (for an � term vocabulary) to � � � � � � � (Gorman and Curran, 2005). The SASH represents the distributional space as a hierarchical directed graph in which each node is connected to several near-neighbour children, deriv- ing its structure from the distribution of the space it represents. The SASH is searched by traversing these edges. WordNet (Fellbaum, 1998) is an electronic lexi- cal database. The main …

Content truncated to 500 words