Fast Computation of Lexical Affinity Models

Fast Computation of Lexical Affinity Models Egidio Terra Charles L.A. Clarke School of Computer Science University of Waterloo Canada � elterra,claclark � @plg2.uwaterloo.ca Abstract We present a framework for the fast compu- tation of lexical affinity models. The frame- work is composed of a novel algorithm to effi- ciently compute the co-occurrence distribution between pairs of terms, an independence model, and a parametric affinity model. In compari- son with previous models, which either use ar- bitrary windows to compute similarity between words or use lexical affinity to create sequential models, in this paper we focus on models in- tended to capture the co-occurrence patterns of any pair of words or phrases at any distance in the corpus. The framework is flexible, allowing fast adaptation to applications and it is scalable. We apply it in combination with a terabyte cor- pus to answer natural language tests, achieving encouraging results. 1 Introduction Modeling term co-occurrence is important for many natural language applications, such as topic seg- mentation (Ferret, 2002), query expansion (Vech- tomova et al., 2003), machine translation (Tanaka, 2002), language modeling (Dagan et al., 1999; Yuret, 1998), and term weighting (Hisamitsu and Niwa, 2002). For these applications, we are in- terested in terms that co-occur in close proxim- ity more often than expected by chance, for exam- ple, � “NEW”,“YORK” � , � “ACCURATE”,“EXACT” � and � “GASOLINE”,“CRUDE” � . These pairs of terms represent distinct lexical-semantic phenomena, and as consequence the terms have an affinity for each other. Examples of such affinities include syn- onyms (Terra and Clarke, 2003), verb similari- ties (Resnik and Diab, 2000) and word associa- tions (Rapp, 2002). Ideally, a language model would capture the pat- terns of co-occurrences representing the affinity be- tween terms. Unfortunately, statistical models used to capture language characteristics often do not take contextual information into account. Many models incorporating contextual information use only a se- lect group of content words and the end product is a model for sequences of adjacent words (Rosenfeld, 1996; Beeferman et al., 1997; Niesler and Wood- land, 1997). Practical problems exist when modeling text sta- tistically, since we require a reasonably sized cor- pus in order to overcome sparseness problems, but at the same time we face the difficulty of scal- ing our algorithms to larger corpora (Rosenfeld, 2000). Attempts to scale language models to large corpora, in particular to the Web, have often used general-purpose search engines to generate term statistics (Berger and Miller, 1998; Zhu and Rosen- feld, 2001). However, many researchers are rec- ognizing the limitations of relying on the statistics provided by commercial search engines (Zhu and Rosenfeld, 2001; Keller and Lapata, 2003). ACL 2004 features a workshop devoted to the problem of scaling human language technologies to terabyte- scale corpora. Another approach to capturing lexical affinity is through the use of similarity measures (Lee, 2001; Terra and Clarke, 2003). Turney (2001) used statis- tics supplied by the Altavista search engine to com- pute word similarity measures, solving a set of syn- …

Content truncated to 500 words