A Game-Theoretic Approach to Word Sense Disambiguation

A Game-Theoretic Approach to Word Sense Disambiguation Rocco Tripodi∗ Ca’ Foscari University of Venice Marcello Pelillo∗∗ Ca’ Foscari University of Venice This article presents a new model for word sense disambiguation formulated in terms of evolu- tionary game theory, where each word to be disambiguated is represented as a node on a graph whose edges represent word relations and senses are represented as classes. The words simultane- ously update their class membership preferences according to the senses that neighboring words are likely to choose. We use distributional information to weigh the influence that each word has on the decisions of the others and semantic similarity information to measure the strength of compatibility among the choices. With this information we can formulate the word sense disambiguation problem as a constraint satisfaction problem and solve it using tools derived from game theory, maintaining the textual coherence. The model is based on two ideas: Similar words should be assigned to similar classes and the meaning of a word does not depend on all the words in a text but just on some of them. The article provides an in-depth motivation of the idea of modeling the word sense disambiguation problem in terms of game theory, which is illustrated by an example. The conclusion presents an extensive analysis on the combination of similarity measures to use in the framework and a comparison with state-of-the-art systems. The results show that our model outperforms state-of-the-art algorithms and can be applied to different tasks and in different scenarios. 1. Introduction Word Sense Disambiguation (WSD) is the task of identifying the intended meaning of a word based on the context in which it appears (Navigli 2009). It has been studied since the beginnings of Natural Language Processing (NLP) (Weaver 1955) and today it is still a central topic of this discipline. This because it is important for many NLP tasks such as text understanding (Kilgarriff 1997), text entailment (Dagan and Glickman 2004), machine translation (Vickrey et al. 2005), opinion mining (Smrˇz 2006), sentiment ∗ European Centre for Living Technology, Ca’ Minich, S. Marco 2940 30124 Venezia, Italy. E-mail: rocco.tripodi@unive.it. ∗∗ Dipartimento di Scienze Ambientali, Informatica e Statistica, Via Torino 155 - 30172 Venezia, Italy. E-mail: pelillo@unive.it. Submission received: 8 June 2015; revised submission received: 25 January 2016; accepted for publication: 24 March 2016. doi:10.1162/COLI a 00274 © 2017 Association for Computational Linguistics Published under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0) license Computational Linguistics Volume 43, Number 1 analysis (Rentoumi et al. 2009), and information extraction (Zhong and Ng 2012). All these applications can benefit from the disambiguation of ambiguous words, as a pre- liminary process; otherwise they remain on the surface of the word, compromising the coherence of the data to be analyzed (Pantel and Lin 2002). To solve this problem, over the past few years, the research community has pro- posed several algorithms based on supervised (Tratz et al. 2007; Zhong and Ng 2010), semi-supervised (Navigli and Velardi 2005; Pham, Ng, and Lee 2005), …

Content truncated to 500 words