Word Sense Induction: Triplet-Based Clustering and Automatic Evaluation

Word Sense Induction: Triplet-Based Clustering and Automatic Evaluation Stefan Bordag Natural Language Processing Department University of Leipzig Germany sbordag@informatik.uni-leipzig.de Abstract In this paper a novel solution to auto- matic and unsupervised word sense induc- tion (WSI) is introduced. It represents an instantiation of the ‘one sense per colloca- tion’ observation (Gale et al., 1992). Like most existing approaches it utilizes clus- tering of word co-occurrences. This ap- proach differs from other approaches to WSI in that it enhances the effect of the one sense per collocation observation by using triplets of words instead of pairs. The combination with a two-step cluster- ing process using sentence co-occurrences as features allows for accurate results. Ad- ditionally, a novel and likewise automatic and unsupervised evaluation method in- spired by Sch¨utze’s (1992) idea of evalu- ation of word sense disambiguation algo- rithms is employed. Offering advantages like reproducability and independency of a given biased gold standard it also en- ables automatic parameter optimization of the WSI algorithm. 1 Introduction The aim of word sense induction1 (WSI) is to find senses of a given target word (Yarowski, 1995) automatically and if possible in an unsupervised manner. WSI is akin to word sense disambiguation (WSD) both in methods employed and in prob- lems encountered, such as vagueness of sense dis- tinctions (Kilgarriff, 1997). The input to a WSI al- gorithm is a target word to be disambiguated, e.g. 1Sometimes called word sense discovery (Dorow and Widdows, 2003) or word sense discrimination (Purandare, 2004; Velldal, 2005) space, and the output is a number of word sets rep- resenting the various senses, e.g. (3-dimensional, expanse, locate) and (office, building, square). Such results can be at the very least used as empir- ically grounded suggestions for lexicographers or as input for WSD algorithms. Other possible uses include automatic thesaurus or ontology construc- tion, machine translation or information retrieval. But the usefulness of WSI in real-world applica- tions has yet to be tested and proved. 2 Related work A substantial number of different approaches to WSI has been proposed so far. They are all based on co-occurrence statistics, albeit using differ- ent context representations such as co-occurrence of words within phrases (Pantel and Lin, 2002; Dorow and Widdows, 2003; Velldal, 2005), bi- grams (Sch¨utze, 1998; Neill, 2002; Udani et al., 2005), small windows around a word (Gauch and Futrelle, 1993), or larger contexts such as sen- tences (Bordag, 2003; Rapp, 2004) or large win- dows of up to 20 words (Ferret, 2004). Moreover they all employ clustering methods to partition the co-occurring words into sets describing concepts or senses. Some algorithms aim for a global clus- tering of words into concepts (Yarowski, 1995; Pantel and Lin, 2002; Velldal, 2005). But the ma- jority of algorithms are based on a local cluster- ing: Words co-occurring with the target word are grouped into the various senses the target word has. It is not immediately clear which approach to favor, however aiming at global senses has the inherent property to produce a uniform …

Content truncated to 500 words