Word Sense Induction & Disambiguation Using Hierarchical Random Graphs

Proceedings of the 2010 Conference on Empirical Methods in Natural Language Processing, pages 745–755, MIT, Massachusetts, USA, 9-11 October 2010. c⃝2010 Association for Computational Linguistics Word Sense Induction & Disambiguation Using Hierarchical Random Graphs Ioannis P. Klapaftis Department of Computer Science University of York United Kingdom giannis@cs.york.ac.uk Suresh Manandhar Department of Computer Science University of York United Kingdom suresh@cs.york.ac.uk Abstract Graph-based methods have gained attention in many areas of Natural Language Processing (NLP) including Word Sense Disambiguation (WSD), text summarization, keyword extrac- tion and others. Most of the work in these ar- eas formulate their problem in a graph-based setting and apply unsupervised graph cluster- ing to obtain a set of clusters. Recent studies suggest that graphs often exhibit a hierarchi- cal structure that goes beyond simple flat clus- tering. This paper presents an unsupervised method for inferring the hierarchical group- ing of the senses of a polysemous word. The inferred hierarchical structures are applied to the problem of word sense disambiguation, where we show that our method performs sig- nificantly better than traditional graph-based methods and agglomerative clustering yield- ing improvements over state-of-the-art WSD systems based on sense induction. 1 Introduction A number of NLP problems can be cast into a graph- based framework, in which entities are represented as vertices in a graph and relations between them are depicted by weighted or unweighted edges. For in- stance, in unsupervised WSD a number of methods (Widdows and Dorow, 2002; V´eronis, 2004; Agirre et al., 2006) have constructed word co-occurrence graphs for a target polysemous word and applied graph-clustering to obtain the clusters (senses) of that word. Similarly in text summarization, Mihalcea (2004) developed a method, in which sentences are rep- resented as vertices in a graph and edges between them are drawn according to their common tokens or words of a given POS category, e.g. nouns. Graph-based ranking algorithms, such as PageRank (Brin and Page, 1998), were then applied in order to determine the significance of sentences. In the same vein, graph-based methods have been applied to other problems such as determining semantic sim- ilarity of text (Ramage et al., 2009). Recent studies (Clauset et al., 2006; Clauset et al., 2008) suggest that graphs exhibit a hierarchi- cal structure (e.g. a binary tree), in which vertices are divided into groups that are further subdivided into groups of groups, and so on, until we reach the leaves. This hierarchical structure provides addi- tional information as opposed to flat clustering by explicitly including organisation at all scales of a graph (Clauset et al., 2008). In this paper, we present an unsupervised method for inferring the hierarchi- cal structure (binary tree) of a graph, in which ver- tices are the contexts of a polysemous word and edges represent the similarity between contexts. The method that we use to infer that hierarchical struc- ture is the Hierarchical Random Graphs (HRGs) al- gorithm due to Clauset et al. (2008). The binary tree produced by our method groups the contexts of a polysemous word at …

Content truncated to 500 words