WSD-games: a Game-Theoretic Algorithm for Unsupervised Word Sense Disambiguation

Proceedings of the 9th International Workshop on Semantic Evaluation (SemEval 2015), pages 329–334, Denver, Colorado, June 4-5, 2015. c⃝2015 Association for Computational Linguistics WSD-games: a Game-Theoretic Algorithm for Unsupervised Word Sense Disambiguation Rocco Tripodi Marcello Pelillo Ca’ Foscari University of Venice Via Torino 155 30172 Venezia, Italy {rocco.tripodi, pelillo}@unive.it Abstract In this paper we present an unsupervised ap- proach to word sense disambiguation based on evolutionary game theory. In our algorithm each word to be disambiguated is represented as a node on a graph and each sense as a class. The algorithm performs a consistent class as- signment of senses according to the similarity information of each word with the others, so that similar words are constrained to similar classes. The dynamics of the system are for- mulated in terms of a non-cooperative multi- player game, where the players are the data points to decide their class memberships and equilibria correspond to consistent labeling of the data. 1 Introduction Word sense disambiguation (WSD) is the task to identify the intended sense of a word in a compu- tational manner based on the context in which it appears (Navigli, 2009). It has been studied since the beginning of NLP (Weaver, 1955) and also to- day it is a central topic of this discipline. Many algorithms have been proposed during the years, based on supervised (Zhong and Ng, 2010; Tratz et al., 2007), semi-supervised (Pham et al., 2005) and unsupervised (Mihalcea, 2005; McCarthy et al., 2007) learning models. Nowadays, even if super- vised methods perform better in general domains, unsupervised and semi-supervised models are gain- ing attention from the research community with per- formances close to the state of the art (Ponzetto and Navigli, 2010). In particular Knowledge-based and graph based algorithms are emerging as interesting ways to face the problem (Agirre et al., 2009; Sinha and Mihalcea, 2007). The peculiarities of those al- gorithms are that they do not require any corpus evi- dence and use only the structural properties of a lex- ical database to perform the disambiguation task. An unsupervised algorithm which has been im- plemented in different ways by the community (Mi- halcea et al., 2004; Haveliwala, 2002; Agirre et al., 2014; De Cao et al., 2010) is the PageRank (Page et al., 1999). This algorithm is similar in spirit to ours but we instead of using the graph to compute the most important nodes (senses) in it, we use the network to model the geometry of the data and the interactions among the data points. In our system the nodes of the graph are interpreted as players, in the game theoretic sense (see Section 2), which play a game in order to maximize their utility. The con- cept of utility has been used in different ways in the game theory (GT) literature and in general it refers to the satisfaction that a player derives from the out- come of a game (Szab´o and Fath, 2007). From our point of view increasing the utility of a word means …

Content truncated to 500 words