Lexical Semantic Relatedness with Random Graph Walks

Proceedings of the 2007 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning, pp. 581–589, Prague, June 2007. c⃝2007 Association for Computational Linguistics Lexical Semantic Relatedness with Random Graph Walks Thad Hughes and Daniel Ramage Computer Science Department Stanford University Stanford, CA 94305 {thughes, dramage}@cs.stanford.edu Abstract Many systems for tasks such as question answer- ing, multi-document summarization, and infor- mation retrieval need robust numerical measures of lexical relatedness. Standard thesaurus-based measures of word pair similarity are based on only a single path between those words in the thesaurus graph. By contrast, we propose a new model of lexical semantic relatedness that incor- porates information from every explicit or im- plicit path connecting the two words in the en- tire graph. Our model uses a random walk over nodes and edges derived from WordNet links and corpus statistics. We treat the graph as a Markov chain and compute a word-specific sta- tionary distribution via a generalized PageRank algorithm. Semantic relatedness of a word pair is scored by a novel divergence measure, ZKL, that outperforms existing measures on certain classes of distributions. In our experiments, the resulting relatedness measure is the WordNet-based mea- sure most highly correlated with human similar- ity judgments by rank ordering at ρ = .90. 1 Introduction Several kinds of Natural Language Processing systems need measures of semantic relatedness for arbitrary word pairs. For example, document summarization and ques- tion answering systems often use similarity scores to evaluate candidate sentence alignments, and information retrieval systems use relatedness scores for query expan- sion. Several popular algorithms calculate scores from information contained in WordNet (Fellbaum, 1998), an electronic dictionary where word senses are explicitly connected by zero or more semantic relationships. The central challenge of these algorithms is to compute rea- sonable relatedness scores for arbitrary word pairs given that few pairs are directly connected. Most pairs in WordNet share no direct semantic link, and for some the shortest connecting path can be surprising—even pairs that seem intuitively related, such “furnace” and “stove” share a lowest common ancestor in the hypernymy taxonomy (is-a links) all the way up at “artifact” (a man-made object). Several existing algo- rithms compute relatedness only by traversing the hyper- nymy taxonomy and find that “furnace” and “stove” are relatively unrelated. However, WordNet provides other types of semantic links in addition to hypernymy, such as meronymy (part/whole relationships), antonymy, and verb entailment, as well as implicit links defined by over- lap in the text of definitional glosses. These links can provide valuable relatedness information. If we assume that relatedness is transitive across a wide variety of such links, then it is natural to follow paths such as furnace– crematory–gas oven–oven–kitchen appliance–stove and find a higher degree of relatedness between “furnace” and “stove.” This paper presents the application of random walk Markov chain theory to measuring lexical semantic re- latedness. A graph of words and concepts is constructed from WordNet. The random walk model posits the exis- tence of a particle that …

Content truncated to 500 words