PageRank on Semantic Networks, with Application to Word Sense Disambiguation

PageRank on Semantic Networks, with Application to Word Sense Disambiguation Rada Mihalcea, Paul Tarau, Elizabeth Figa University of North Texas Dallas, TX, USA rada@cs.unt.edu, tarau@unt.edu, efiga@unt.edu Abstract This paper presents a new open text word sense disambiguation method that combines the use of logical inferences with PageRank-style algo- rithms applied on graphs extracted from natu- ral language documents. We evaluate the ac- curacy of the proposed algorithm on several sense-annotated texts, and show that it consis- tently outperforms the accuracy of other pre- viously proposed knowledge-based word sense disambiguation methods. We also explore and evaluate methods that combine several open-text word sense disambiguation algorithms. 1 Introduction Google’s PageRank link-analysis algorithm (Brin and Page, 1998), and variants like Kleinberg’s HITS algorithm (Kleinberg, 1999), have been used for an- alyzing the link-structure of the World Wide Web to provide global, content independent ranking of Web pages. Arguably, PageRank can be singled out as a key element of the paradigm-shift Google has triggered in the field of Web search technol- ogy, by providing a Web page ranking mechanism that relies on the collective knowledge of Web ar- chitects rather than content analysis of individual Web pages. In short, PageRank is a way of decid- ing on the importance of a vertex within a graph, by taking into account global information recursively computed from the entire graph, rather than relying only on local vertex-specific information. Apply- ing a similar line of thinking to lexical and semantic knowledge graphs like WordNet (Miller, 1995) sug- gests using the implicit knowledge incorporated in their link structure for language processing applica- tions, where knowledge drawn from an entire text can be used in making local ranking/selection deci- sions. In this paper, we explore the applicability of PageRank to semantic networks, and show that such graph-based ranking algorithms can be successfully used in language processing applications. In partic- ular, we propose and experiment with a new unsu- pervised knowledge-based word sense disambigua- tion algorithm, which succeeds in identifying the sense of all words in open text with a precision significantly higher than other previously proposed knowledge-based algorithms. The paper is organized as follows. Section 2 re- views the problem of word sense disambiguation, and surveys related work. Section 3 briefly describes the PageRank algorithm, and shows how this algo- rithm can be adapted to the WordNet graph. Sec- tion 4 introduces the PageRank-based word sense disambiguation algorithm. Combinations with other known algorithms are explored in Section 5. thorough empirical evaluation of the proposed algo-A rithms on several sense-annotated texts is provided in section 6. 2 Open Text Word Sense Disambiguation The task of word sense disambiguation consists of assigning the most appropriate meaning to a poly- semous word within a given context. Applications such as machine translation, knowledge acquisition, common sense reasoning, and others, require knowl- edge about word meanings, and word sense disam- biguation is considered essential for all these appli- cations. Most of the efforts in solving this problem were concentrated so far toward targeted supervised learning, …

Content truncated to 500 words