Elamur Research⌕
☰
home / papers / 2017 / A Game-Theoretic Approach to Word Sense Disambiguation

A Game-Theoretic Approach to Word Sense Disambiguation

Paper · 2017 · Rocco Tripodi and Marcello Pelillo

Summary

Tripodi and Pelillo address word sense disambiguation (WSD) by treating it as a non-cooperative game drawn from evolutionary game theory. Each target word becomes a player, which is a node in a graph containing only words, not senses. Its possible senses act as strategies. Edge weights come from distributional similarity and proximity, so a word is mainly influenced by a few closely related neighbours rather than the whole text. Payoffs between sense pairs are semantic similarity scores computed from a knowledge base such as WordNet, or from BabelNet with NASARI vectors. Replicator dynamics update all players' sense preferences at the same time until they reach a coherent, consistent labeling. The model runs fully unsupervised. A semi-supervised variant can add priors from sense-tagged corpora or the most frequent sense. The authors also test many combinations of similarity measures. The approach matters because it keeps the text coherent and resists misleading context, unlike centrality-based or word-by-word methods.

Key points

  • The graph links only words, and interactions are weighted so that collocated or proximate words count most. In "river bank", for example, river outweighs financial.
  • On SemEval-2013 (S13), WSD games reached 70.8 F1. Babelfy scored 69.2, MFS 66.5, SUDOKU 66.3, PPR w2w 60.8 and GETALP 58.3.
  • On the KORE50 entity-linking set, WSD games reached 75.7 accuracy, compared with 71.5 for Babelfy and 63.9 for KORE. Recall was much lower, reported as 55.5%, because the sentences are short and cryptic.
  • The authors partly credit the gains to the rich NASARI/BabelNet representations, which add Wikipedia coverage beyond WordNet.
  • The work extends earlier semi-supervised graph-transduction research by the same authors (Tripodi, Pelillo, and Delmonte 2015).

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Institutions

🎓Ca' Foscari University of VeniceVenice · Italy12 works · 328 citations

 Fields, topics and concepts

📚 Shelves 4The field of science this work belongs to (OpenAlex fields).Computer Science · 18,614 worksArtificial Intelligence · 17,965 worksArts and Humanities · 17,450 worksLanguage and Linguistics · 17,296 works

🧭 Topics 1Research subjects and languages the work is about.Word sense disambiguation · 87 works

Cite

Cite as Rocco Tripodi and Marcello Pelillo. 2017. A Game-Theoretic Approach to Word Sense Disambiguation. Computational Linguistics.

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.1162/coli_a_00274

@article{tripodi2017game,
  title = {{A Game-Theoretic Approach to Word Sense Disambiguation}},
  author = {Rocco Tripodi and Marcello Pelillo},
  journal = {Computational Linguistics},
  year = {2017},
  doi = {10.1162/coli\_a\_00274},
  url = {https://doi.org/10.1162/coli_a_00274}
}

References

104 references, 20 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Agirre, E., O. L. De Lacalle, C. Fellbaum, A. Marchetti, A. Toral, and P. Vossen. 2009. SemEval-2010 task 17: All-words word sense disambiguation on a specific domain. In Proceedings of the Workshop on Semantic Evaluations: Recent Achievements and Future Directions, pages 123-128, Boulder, CO. find
  2. Agirre, E., O. Lopez de Lacalle, and A. Soroa. 2014. Random walks for knowledge-based word sense disambiguation. Computational Linguistics, 40(1):57–84.
  3. Agirre, E., O. Lopez De Lacalle, A. Soroa, and I. Fakultatea. 2009. Knowledge-based WSD and specific domains: Performing better than generic supervised WSD. In Proceedings of IJCAI, pages 1501–1506. find
  4. Agirre, E. and P. G. Edmonds. 2007. Word Sense Disambiguation: Algorithms and Applications, volume 33. Springer Science & Business Media. Agirre, E., D. Martı́nez, O. L. de Lacalle, and A. Soroa. 2006. Two graph-based algorithms for state-of-the-art WSD. In Proceedings of the 2006 Conference on Empi… find
  5. Araujo, L. 2007. How evolutionary algorithms are applied to statistical natural language processing. Artificial Intelligence Review, 28(4):275–303. find
  6. Bird, S. 2006. NLTK: The natural language toolkit. In Proceedings of the COLING/ACL on Interactive Presentation Sessions, pages 69–72, Sydney.
  7. Blaheta, D. and M. Johnson. 2001. Unsupervised learning of multi-word verbs. In Proceedings of the ACL/EACL 2001 Workshop on the Computational Extraction, Analysis and Exploitation of Collocations, pages 54–60. find
  8. Brants, T. and A. Franz. 2006. { Web 1T 5-gram Version 1 } . Burrows, J. 2002. Delta: A measure of stylistic difference and a guide to likely authorship. Literary and Linguistic Computing, 17(3):267–287. find
  9. Camacho-Collados, J., M. T. Pilehvar, and R. Navigli. 2015. NASARI: A novel approach to a semantically-aware representation of items. In Proceedings of NAACL, pages 567–577, Denver, CO. find
  10. Carpineto, C. and G. Romano. 2012. A survey of automatic query expansion in information retrieval. ACM Computing Surveys (CSUR), 44(1):1–50. find
  11. Chan, Y. S. and H. T. Ng. 2005. Scaling up word sense disambiguation via parallel texts. In AAAI, volume 5, pages 1037–1042. find
  12. Chaplot, D. S., P. Bhattacharyya, and A. Paranjape. 2015. Unsupervised word sense disambiguation using Markov random field and dependency parser. In AAAI, pages 2217–2223. find
  13. Church, K. W. and P. Hanks. 1990. Word association norms, mutual information, and lexicography. Computational Linguistics, 16(1):22–29.
  14. Cong, J. and H. Liu. 2014. Approaching human language with complex networks. Physics of life Reviews, 11(4):598–618. find
  15. Curran, J. R, T. Murphy, and B. Scholz. 2007. Minimising semantic drift with mutual exclusion bootstrapping. In Proceedings of the 10th Conference of the Pacific Association for Computational Linguistics, volume 6, pages 172–180, Bali. find
  16. Dagan, I. and O. Glickman. 2004. Probabilistic textual entailment: Generic applied modeling of language variability. Learning Methods for Text Understanding and Mining, pages 26–29, Grenoble. find
  17. Dang, H. T. 1975. Investigations into the Role of Lexical Semantics in Word Sense Disambiguation. Ph.D. thesis, University of Pensylvania. find
  18. De Cao, D., R. Basili, M. Luciani, F. Mesiano, and R. Rossi. 2010. Robust and efficient page rank for word sense disambiguation. In Proceedings of the 2010 Workshop on Graph-based Methods for Natural Language Processing, pages 24–32, Uppsala. find
  19. DeGroot, M. H., M. J. Schervish, X. Fang, Ligang L., and D. Li. 1986. Probability and Statistics, volume 2. find
  20. Addison-Wesley, Reading, MA. Dice, L. R. 1945. Measures of the amount of ecologic association between species. Ecology, 26(3):297–302. find
  21. Erdem, A. and M. Pelillo. 2012. Graph transduction as a noncooperative game. Neural Computation, 24(3):700–723. find
  22. Evert, S. 2008. Corpora and collocations. Corpus Linguistics. An International Handbook, 2:223–233. find
  23. Firth, J. R. 1957. A synopsis of linguistic theory 1930–1955. Studies in Linguistic Analysis, Oxford: Blackwell. find
  24. Fkih, F. and M. N. Omri. 2012. Learning the size of the sliding window for the collocations extraction: A ROC-based approach. In Proceedings of the 2012 International Conference on Artificial Intelligence (ICAI’12), pages 1071–1077. find
  25. Gale, W. A., K. W. Church, and D. Yarowsky. 1992. A method for disambiguating word senses in a large corpus. Computers and the Humanities, 26(5-6):415–439. find
  26. Haveliwala, T. H. 2002. Topic-sensitive pagerank. In Proceedings of the 11th International Conference on the World Wide Web, pages 517–526.
  27. Maui, HI. Hoffart, J., S. Seufert, D. B. Nguyen, M. Theobald, and G. Weikum. 2012. KORE: Keyphrase overlap relatedness for entity disambiguation. In Proceedings of the 21st ACM International Conference on Information and Knowledge Management, pages 545–554. find
  28. Hoffart, J., F. M. Suchanek, K. Berberich, and G. Weikum. 2013. YAGO2: A spatially and temporally enhanced knowledge base from Wikipedia. In Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence, pages 3161–3165, Beijing. find
  29. Holland, J. H. 1975. Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence. University of Michigan Press. find
  30. Hummel, R. A. and S. W. Zucker. 1983. On the foundations of relaxation labeling processes. IEEE Transactions on Pattern Analysis and Machine Intelligence, (3):267–287. find
  31. Jiang, J. J. and D. W Conrath. 1997. Semantic similarity based on corpus statistics and lexical taxonomy. In International Conference Research on Computational Linguistics, pages 970–985. find
  32. Jordan, M. I. and Y. Weiss. 2002. Graphical models: Probabilistic inference. In M. A. Arbib, editor, The Handbook of Brain Theory and Neural Networks. MIT Press, pages 490–496. find
  33. Kelly, E. F. and P. J. Stone. 1975. Computer Recognition of English Word Senses, volume 13. find
  34. North-Holland. Kilgarriff, A. 1997. I don’t believe in word senses. Computers and the Humanities, 31(2):91–113.
  35. Kitamura, W. and Y. Matsumoto. 1996. Automatic extraction of word sequence correspondences in parallel corpora. In Proceedings of the 4th Workshop on Very Large Corpora, pages 79–87, Copenhagen. find
  36. Kleinberg, J. and E. Tardos. 2002. Approximation algorithms for classification problems with pairwise relationships: Metric labeling and Markov random fields. Journal of the ACM (JACM), 49(5):616–639. find
  37. Koeling, R., D. McCarthy, and J. Carroll. 2005. Domain-specific sense distributions and predominant sense acquisition. In Proceedings of the Conference on Human Language Technology and Empirical Methods in Natural Language Processing, pages 419–426, Vancouver. find
  38. Lafon, P. 1980. Sur la variabilité de la fréquence des formes dans un corpus. Mots, 1(1):127–165. find
  39. Larsen-Freeman, D. and L. Cameron. 2008. find
  40. Complex Systems and Applied Linguistics. Oxford University Press. Leech, G. 1992. 100 million words of English: The British National Corpus (BNC). Language Research, 28(1):1–13. find
  41. Lesk, Michael. 1986. Automatic sense disambiguation using machine readable dictionaries: How to tell a pine cone from an ice cream cone. In Proceedings of the 5th Annual International Conference on Systems Documentation, pages 24–26, Toronto. find
  42. Leyton-Brown, K. and Y. Shoham. 2008. Essentials of game theory: A concise multidisciplinary introduction. Synthesis Lectures on Artificial Intelligence and Machine Learning, 2(1):1–88. find
  43. Manion, S. L. and R. Sainudiin. 2014. An iterative sudoku style approach to subgraph-based word sense disambiguation. In Proceedings of the Third Joint Conference on Lexical and Computational Semantics (* SEM 2014), pages 40–50, Dublin. find
  44. McCarthy, D., R. Koeling, J. Weeds, and J. Carroll. 2007. Unsupervised acquisition of predominant word senses. Computational Linguistics, 33(4):553–590. find
  45. Menai, M. 2014. Word sense disambiguation using evolutionary algorithms— Application to Arabic language. Computers in Human Behavior, 41:92–103. find
  46. Mihalcea, R. 2005. Unsupervised large-vocabulary word sense disambiguation with graph-based algorithms for sequence data labeling. In Proceedings of the Conference on Human Language Technology and Empirical Methods in Natural Language Processing, pages 411–418, Vancouver.
  47. Mihalcea, R. 2006. Knowledge-based methods for WSD. In E. Agirre and P. Edmonds, editors, Word Sense Disambiguation: Algorithms and Applications. Springer, pages 107–131. find
  48. Mihalcea, R. and D. I. Moldovan. 2001. eXtended WordNet: progress report. In Proceedings of NAACL Workshop on WordNet and Other Lexical Resources, pages 95–100, Pittsburgh, PA. find
  49. Mihalcea, R., P. Tarau, and E. Figa. 2004. Pagerank on semantic networks, with application to word sense disambiguation. In Proceedings of the 20th International Conference on Computational Linguistics, page 1126, Geneva.
  50. Miller, D. A. and S. W. Zucker. 1991. Copositive-plus Lemke algorithm solves polymatrix games. Operations Research Letters, 10(5):285–290. find
  51. Miller, G. A. 1995. WordNet: A lexical database for English. Communications of the ACM, 38(11):39–41.
  52. Miller, G. A., C. Leacock, R. Tengi, and R. T. Bunker. 1993. A semantic concordance. In Proceedings of the Workshop on Human Language Technology, pages 303–308, Princeton, NJ.
  53. Moro, A. and R. Navigli. 2015. SemEval-2015 Task 13: Multilingual All-Words Sense Disambiguation and Entity Linking. In Proceedings of SemEval-2015, pages 288–297. find
  54. Moro, A., A. Raganato, and R. Navigli. 2014. Entity linking meets word sense disambiguation: A unified approach. Transactions of the Association for Computational Linguistics, 2:231–244.
  55. Moscato, P. 1989. On evolution, search, optimization, genetic algorithms and martial arts: Towards memetic algorithms. Caltech Concurrent Computation Program, C3P Report, 826:1989. find
  56. Nash, J. 1951. Non-cooperative games. Annals of Mathematics, 54(2):286–295. find
  57. Navigli, R. 2006. Meaningful clustering of senses helps boost word sense disambiguation performance. In Proceedings of the 21st International Conference on Computational Linguistics and the 44th Annual Meeting of the Association for Computational Linguistics, pages 105–112, Sydney.
  58. Navigli, R. 2009. Word sense disambiguation: A survey. ACM Computing Surveys (CSUR), 41(2):10. find
  59. Navigli, R., D. Jurgens, and D. Vannella. 2013. Semeval-2013 task 12: Multilingual word sense disambiguation. In Second Joint Conference on Lexical and Computational Semantics (* SEM), volume 2, pages 222–231. find
  60. Navigli, R. and M. Lapata. 2007. Graph connectivity measures for unsupervised word sense disambiguation. In IJCAI, pages 1683–1688.
  61. Navigli, R. and M. Lapata. 2010. An experimental study of graph connectivity for unsupervised word sense disambiguation. In IEEE Transactions on Pattern Analysis and Machine Intelligence, 32(4):678–692. find
  62. Navigli, R., K. C. Litkowski, and O. Hargraves. 2007. SemEval-2007 task 07: Coarse-grained English all-words task. In Proceedings of the 4th International Workshop on Semantic Evaluations, pages 30–35, Prague.
  63. Navigli, R. and S. P. Ponzetto. 2012a. BabelNet: The automatic construction, evaluation and application of a wide-coverage multilingual semantic network. Artificial Intelligence, 193:217–250. find
  64. Navigli, R. and S. P. Ponzetto. 2012b. Joining forces pays off: Multilingual joint word sense disambiguation. In Proceedings of the 2012 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning, pages 1399–1410, Jeju Island. find
  65. Navigli, R. and P. Velardi. 2005. Structural semantic interconnections: a knowledge-based approach to word sense disambiguation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 27(7):1075–1086. find
  66. Ng, H. T. and H. B. Lee. 1996. Integrating multiple knowledge sources to disambiguate word sense: An exemplar-based approach. In Proceedings of the 34th Annual Meeting of the Association for Computational Linguistics, pages 40–47, Santa Cruz, CA.
  67. Nowak, M. A, N. L. Komarova, and P. Niyogi. 2001. Evolution of universal grammar. Science, 291(5501):114–118. find
  68. Okasha, Samir and Ken Binmore. 2012. find
  69. Evolution and Rationality: Decisions, Co-operation and Strategic Behaviour. Cambridge University Press. Page, L., S. Brin, R. Motwani, and T. Winograd. 1999. The PageRank citation ranking: Bringing order to the Web, Technical Report.
  70. Stanford Infolab. Palmer, M., C. Fellbaum, S. Cotton, L. Delfs, and H. T. Dang. 2001. English tasks: All-words and verb lexical sample. In Proceedings of the Second International Workshop on Evaluating Word Sense Disambiguation Systems, pages 21–24, Toulouse. find
  71. Pantel, P. and D. Lin. 2002. Discovering word senses from text. In Proceedings of the Eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 613–619, Edmonton. find
  72. Patwardhan, S. and T. Pedersen. 2006. Using WordNet-based context vectors to estimate the semantic relatedness of concepts. In Proceedings of the EACL 2006 Workshop Making Sense of Sense-Bringing Computational Linguistics and Psycholinguistics Together, volume 1501, pages 1–8, Trento. find
  73. Patwardhan, Siddharth, Satanjeev Banerjee, and T. Pedersen. 2003. Using measures of semantic relatedness for word sense disambiguation. In Computational Linguistics and Intelligent Text Processing, pages 241–257. find
  74. Pedersen, T. 2012. Duluth: Measuring degrees of relational similarity with the gloss vector measure of semantic relatedness. In First Joint Conference on Lexical and Computational Semantics (*SEM), pages 497–501. find
  75. Pelillo, M. 1997. The dynamics of nonlinear relaxation labeling processes. Journal of Mathematical Imaging and Vision, 7(4):309–323. find
  76. Pham, T. P., H. T. Ng, and W. S. Lee. 2005. Word sense disambiguation with semi-supervised learning. In Proceedings of the National Conference on Artificial Intelligence, volume 20, pages 1093–1098, Ann Arbor, MI. Pietarinen, A. (editor). 2007. find
  77. Game Theory and Linguistic Meaning. Elsevier. Pilehvar, M. T. and R. Navigli. 2014. A large-scale pseudoword-based evaluation framework for state-of-the-art word sense disambiguation. Computational Linguistics, 40(4):837–881.
  78. Ponzetto, S. P. and R. Navigli. 2010. Knowledge-rich word sense disambiguation rivaling supervised systems. In Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics, pages 1522–1531, Uppsala. find
  79. Pradhan, S. S., E. Loper, D. Dligach, and M. Palmer. 2007. SemEval-2007 task 17: English lexical sample, SRL and all words. In Proceedings of the 4th International Workshop on Semantic Evaluations, pages 87–92, Prague.
  80. Rao, C. R. 2002. Karl Pearson chi-square test—the dawn of statistical inference. In C. Huber-Carol et al., editors, Goodness-of-fit Tests and Model Validity. Springer, pages 9–24. find
  81. Rentoumi, V., G. Giannakopoulos, V. Karkaletsis, and G. A. Vouros. 2009. Sentiment analysis of figurative language using a word sense disambiguation approach. In Proceedings of RANLP, pages 370-375. find
  82. Resnik, P. 1995. Using information content to evaluate semantic similarity in a taxonomy. In Proceedings of the 14th International Joint Conference on Artificial Intelligence - Volume 1, pages 448–453, Montreal. Rota Buló, S., M. Pelillo, and I. M. Bomze. 2011. Graph-based quadratic optimization: A…
  83. Sandholm, W. H. 2010. Population Games and Evolutionary Dynamics. MIT Press. Schwab, Didier, Andon Tchechmedjiev, Jérôme Goulian, Mohammad Nasiruddin, Gilles Sérasset, and Hervé Blanchon. 2013. GETALP System: Propagation of a Lesk Measure through an Ant Colony Algorithm. In Second Joint Conferen… find
  84. Sinha, R. Som and R. Mihalcea. 2007. Unsupervised graph-based word sense disambiguation using measures of word semantic similarity. In Proceedings of ICSC, volume 7, pages 363–369. find
  85. Skyrms, B. 2010. Signals: Evolution, Learning, and Information. find
  86. Oxford University Press. Smith, J. M. and G. R. Price. 1973. The logic of animal conflict. Nature, 246:15. Smrž, P. 2006. Using WordNet for opinion mining. In Proceedings of the Third International WordNet Conference, pages 333–335, Jeju Island. find
  87. Snyder, B. and M. Palmer. 2004. The English all-words task. In Senseval-3: Third International Workshop on the Evaluation of Systems for the Semantic Analysis of Text, pages 41–43. find
  88. Søgaard, A., A. Johannsen, B. Plank, D. Hovy, and H. M. Alonso. 2014. What’s in a p-value in NLP? In Proceedings of the Eighteenth Conference on Computational Natural Language Learning (CONLL14), pages 1–10, Baltimore, MD. find
  89. Steinwart, I. and A. Christmann. 2008. find
  90. Support Vector Machines. Springer Science. Strapparava, C., A. Gliozzo, and C. Giuliano. 2004. Pattern abstraction and term similarity for word sense disambiguation: Irst at Senseval-3. In Proceedings of SENSEVAL-3 Third International Workshop on Evaluation of Systems for the Semantic Analysis of Te… find
  91. Taylor, P. D. and L. B. Jonker. 1978. Evolutionary stable strategies and game dynamics. Mathematical Biosciences, 40(1):145–156. find
  92. Tong, H., C. Faloutsos, and J. Pan. 2006. Fast random walk with restart and its applications. In Proceedings of the Sixth International Conference on Data Mining, pages 613–622, Hong Kong. find
  93. Tratz, S., A. Sanfilippo, M. Gregory, A. Chappell, C. Posse, and P. Whitney. 2007. PNNL: A supervised maximum entropy approach to word sense disambiguation. In Proceedings of the 4th International Workshop on Semantic Evaluations, pages 264–267, Prague. find
  94. Tripodi, R. and M. Pelillo. 2015. WSD-games: A game-theoretic algorithm for unsupervised word sense disambiguation. In Proceedings of SemEval-2015, pages 329–334, Denver, CO. find
  95. Tripodi, R., M. Pelillo, and Rodolfo Delmonte. 2015. An evolutionary game theoretic approach to word sense disambiguation. In Proceedings of Natural Language Processing and Cognitive Science 2014, pages 39–48, Venice. find
  96. Tsang, E. 1995. Foundations of Constraint Satisfaction. Academic Press. Véronis, J. 2004. Hyperlex: lexical cartography for information retrieval. Computer Speech & Language, 18(3):223–252. find
  97. Vickrey, D., L. Biewald, M. Teyssier, and D. Koller. 2005. Word-sense disambiguation for machine translation. In Proceedings of the Conference on Human Language Technology and Empirical Methods in Natural Language Processing, pages 771–778, Vancouver.
  98. Von Neumann, J. and O. Morgenstern. 1944. Theory of Games and Economic Behavior. find
  99. Princeton University Press. Weaver, W. 1955. Translation. Machine Translation of Languages, 14:15-23. find
  100. Evolutionary Game Theory. MIT Press. Wu, Z. and M. Palmer. 1994. Verbs, semantics, and lexical selection. In Proceedings of the 32nd Annual Meeting of the Association for Computational Linguistics, pages 133–138, Las Cruces, NM. find
  101. Yarowsky, D. 1993. One sense per collocation. In Proceedings of the Workshop on Human Language Technology, pages 266–271, Princeton, NJ.
  102. Yarowsky, D. and R. Florian. 2002. Evaluating sense disambiguation across diverse parameter spaces. Natural Language Engineering, 8(04):293–310. find
  103. Zhong, Z. and H. T. Ng. 2010. It makes sense: A wide-coverage word sense disambiguation system for free text. In Proceedings of the ACL 2010 System Demonstrations, pages 78–83, Uppsala. find
  104. Zhong, Z. and H. T. Ng. 2012. Word sense disambiguation improves information retrieval. In Proceedings of the 50th Annual Meeting of the Association for Computational Linguistics: Long Papers-Volume 1, pages 273–282, Jeju Island. find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/tripodi-2017-game-theoretic-approach-word-sense/