Elamur Research
☰
home / papers / 2014 / Random Walks for Knowledge-Based Word Sense Disambiguation

Random Walks for Knowledge-Based Word Sense Disambiguation

Written by Mova (claude-opus-5-5) from the paper text, in our own words: the license "CC BY-NC-SA 3.0 (ACL Anthology, before 2016)" does not allow redistributing the text itself. Original — aclanthology.org/J14-1003.pdf

Summary

The paper tackles word sense disambiguation (WSD) without manually annotated training data. Instead, it relies only on a lexical knowledge base (LKB). The authors propose an algorithm based on Personalized PageRank (PPR): a random walk is run over the entire WordNet graph, extended with relations from eXtended WordNet. The sentence context determines where the walk starts, so the ranking of senses depends on the word's surroundings. There is also a variant, PPR w2w, in which the graph is personalized separately for each target word. The method was evaluated on four English datasets and one Spanish dataset. It outperforms other graph-based approaches, including PageRank and degree on subgraphs. It also compares favorably with knowledge-based systems that use similar knowledge sources and comes close to the MFS heuristic. The authors analyze in detail the effect of parameters, relation types and WordNet versions, as well as the trade-off between speed and quality. For other languages, the method is valuable because it requires only an existing wordnet. The code and graphs are publicly released in the UKB package.

Key points

  • The Spanish experiment uses Spanish WordNet and the SemEval-2007 Task 09 dataset. The test portion contains 792 instances for the 150 most frequent nouns of the CESS-ECE corpus. Results (F1): PPR w2w — 79.3, PPR — 78.4, STATIC — 76.5. For comparison, the dictionary's first sense yields 66.4, MFS — 84.6, and the best supervised system — 85.1.
  • Efficiency: PPR on the full graph is the fastest, PPR w2w processes about 210 instances per minute, and the BFS subgraph only about 20. The full graph takes about 270 MB of memory.
  • In the English WordNet, senses are ordered by frequency in annotated corpora, so the first sense effectively coincides with MFS. In the Spanish wordnet and many others, the order is set by the lexicographer. Outperforming the first sense therefore matters for languages that lack large annotated corpora.
  • On general-domain corpora, PPR, STATIC and MFS yield similar results. On domain-specific data (from the authors' earlier 2009 work), PPR departs from MFS and outperforms it, i.e., it genuinely exploits the context.
  • The algorithm was first presented in Agirre & Soroa (2009). This article was published in Computational Linguistics in 2014. The resources are available at ixa2.si.ehu.es/ukb.

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

Fields: AI & machine learning

Topics: Word sense disambiguation

Cited by

103 papers of our library cite it (of the 140673 whose bibliographies we read); 1 of them have a page here, 102 not yet.

Cite

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

@misc{agirre2014random,
  title = {{Random Walks for Knowledge-Based Word Sense Disambiguation}},
  author = {Agirre, Eneko and Lacalle, Oier López de and Soroa, Aitor},
  year = {2014},
  doi = {10.1162/coli\_a\_00164},
  url = {https://doi.org/10.1162/coli_a_00164}
}

References

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

  1. Agirre, E., E. Alfonseca, K. Hall, J. Kravalova, M. Pasca, and A. Soroa. 2009. A study on similarity and relatedness using distributional and WordNet-based approaches. In Proceedings of the North American Chapter of the Association for Computational Linguistics - Human Language Technologies conferen… find
  2. Agirre, E., T. Baldwin, and D. Martinez. 2008. Improving parsing and PP attachment performance with sense information. In Proceedings of the 46th Annual Meeting of the Association for Computational Linguistics (ACL/HLT’08), pages 317–325, Columbus, OH. find
  3. Agirre, E., K. Bengoetxea, K. Gojenola, and J. Nivre. 2011. Improving dependency parsing with semantic classes. In Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies (ACL/HLT’11), pages 699–703, Portland, OR. find
  4. Agirre, E., O. López de Lacalle, and A. Soroa. 2009. Knowledge-based WSD on specific domains: Performing better than generic supervised WSD. In Proceedings of the 19th International Joint Conference on Artificial Intelligence (IJCAI’09), pages 1,501–1,506, Pasadena, CA. find
  5. Agirre, E. and G. Rigau. 1996. Word sense disambiguation using conceptual density. In Proceedings of the 16th International Conference on Computational Linguistics (COLING’96), pages 16–22, Copenhagen. find
  6. Agirre, E. and A. Soroa. 2008. Using the multilingual central repository for graph-based word sense disambiguation. In Proceedings of the 6th Conference on Language Resources and Evaluation (LREC ’08), pages 1,388–1,392, Marrakesh. find
  7. Agirre, E. and A. Soroa. 2009. Personalizing PageRank for word sense disambiguation. In Proceedings of the 12th Conference of the European Chapter of the Association for Computational Linguistics (EACL’09), pages 33–41, Athens. find our card
  8. Anaya-Sánchez, H., A. Pons-Porrata, and R. Berlanga-Llavori. 2007. TKB-UO: Using sense clustering for WSD. In Proceedings of the 4th International Workshop on Semantic Evaluations (SemEval-2007) in conjunction with ACL, pages 322–325, Prague. find
  9. Atserias, J., G. Rigau, and L. Villarejo. 2004. Spanish wordnet 1.6: Porting the Spanish wordnet across Princeton versions. In Proceedings of the 4th Conference on Language Resources and Evaluation (LREC’04), pages 161–164, Lisbon. find
  10. Barzilay, R. and M. Elhadad. 1997. Using lexical chains for text summarization. In Proceedings of the ACL Workshop on Intelligent Scalable Text Summarization, pages 10–17, New York, NY. find
  11. Brin, S. and L. Page. 1998. The anatomy of a large-scale hypertextual Web search engine. Computer Networks and ISDN Systems, 30(1-7):107–117. find our card
  12. Carpuat, M. and D. Wu. 2007. Improving statistical machine translation using word sense disambiguation. In Proceedings of the Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning (EMNLP/CoNLL’07), pages 61–72, Prague. find
  13. Chan, Y. S. and H. T. Ng. 2005. Scaling up word sense disambiguation via parallel texts. In Proceedings of the 20th National Conference on Artificial Intelligence (AAAI’05), pages 1,037–1,042, Pittsburgh, PA. find
  14. Chan, Y. S., H. T. Ng, and D. Chiang. 2007. Word sense disambiguation improves statistical machine translation. In Proceedings of the 45th Annual Meeting of the Association for Computational Linguistics (ACL’07), pages 33–40, Prague. find
  15. Chan, Y. S., H. T. Ng, and Z. Zhong. 2007. NUS-PT: Exploiting parallel texts for word sense disambiguation in the English all-words tasks. In Proceedings of the 4th International Workshop on Semantic Evaluations (SemEval-2007) in conjunction with ACL, pages 253–256, Prague. find
  16. Cowie, J., J. Guthrie, and L. Guthrie. 1992. Lexical disambiguation using simulated annealing. In Proceedings of the Workshop on Speech and Natural Language (HLT’91), pages 238–242, Morristown, NJ. find
  17. Cuadros, M. and G. Rigau. 2006. Quality assessment of large scale knowledge resources. In Proceedings of Joint SIGDAT Conference on Empirical Methods in Natural Language Processing (EMNLP’06), pages 534–541, Sydney. find
  18. Cuadros, M. and G. Rigau. 2007. Semeval-2007 task 16: Evaluation of wide coverage knowledge resources. In Proceedings of the 4th International Workshop on Semantic Evaluations (SemEval-2007) in conjunction with ACL, pages 81–86, Prague. find
  19. Cuadros, M. and G. Rigau. 2008. Knownet: Using topic signatures acquired from the Web for building automatically highly dense knowledge bases. In Proceedings of the 22nd International Conference on Computational Linguistics (COLING’08), pages 71–84, Manchester. find
  20. Daude, J., L. Padro, and G. Rigau. 2000. Mapping WordNets using structural information. In Proceedings of the 38th Annual Meeting of the Association for Computational Linguistics (ACL’00), pages 504–511, Hong Kong. find
  21. Decadt, B., V. Hoste, W. Daelemans, and A. Van Den Bosch. 2004. GAMBL, genetic algorithm optimization of memory-based WSD. In Proceedings of SENSEVAL-3 Third International Workshop on Evaluation of Systems for the Semantic Analysis of Text, pages 108–112, Barcelona. find
  22. Escudero, G., L. Márquez, and G. Rigau. 2000. An empirical study of the domain dependence of supervised word sense disambiguation systems. Proceedings of the Joint SIGDAT Conference on Empirical Methods in Natural Language Processing and Very Large Corpora (EMNLP/VLC’00), pages 172–180, Hong Kong. find
  23. Fellbaum, C., editor. 1998. WordNet: An Electronic Lexical Database and Some of Its Applications. MIT Press, Cambridge, MA. find
  24. Haveliwala, T. H. 2002. Topic-sensitive PageRank. In Proceedings of the 11th International Conference on World Wide Web (WWW’02), pages 517–526, New York, NY. find
  25. Hughes, T. and D. Ramage. 2007. Lexical semantic relatedness with random graph walks. In Proceedings of the Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning (EMNLP/CoNLL’07), pages 581–589, Prague. find
  26. Jiang, J. J. and D. W. Conrath. 1997. Semantic similarity based on corpus statistics and lexical taxonomy. In Proceedings of the International Conference on Research in Computational Linguistics, pages 19–33, Taiwan. find
  27. Kleinberg., J. M. 1998. Authoritative sources in a hyperlinked environment. In Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’98), pages 668–677, Philadelphia, PA. find our card
  28. Koeling, R., D. McCarthy, and J. Carroll. 2005. Domain-specific sense distributions and predominant sense acquisition. In Proceedings of the Human Language Technology Conference and Conference on Empirical Methods in Natural Language Processing (HLT/EMNLP’05), pages 419–426, Ann Arbor, MI. find
  29. Langville, A. N. and C. D. Meyer. 2003. Deeper inside PageRank. Internet Mathematics, 1(3):335–380. find
  30. Lesk, M. 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 (SIGDOC’86), pages 24–26, New York, NY. find
  31. Màrquez, L., M. A. Villarejo, T. Martı́, and M. Taulé. 2007. SemEval-2007 Task 09: Multilevel semantic annotation of Catalan and Spanish. In Proceedings of the 4th International Workshop on Semantic Evaluations (SemEval-2007) in conjunction with ACL, pages 42–47, Prague. find
  32. McCarthy, D., R. Koeling, J. Weeds, and J. Carroll. 2007. Unsupervised acquisition of predominant word senses. Computational Linguistics, 33(4):553–590. find
  33. Mihalcea, R. 2002. Word sense disambiguation with pattern learning and automatic feature selection. Natural Language Engineering, 8:343–358. find
  34. 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 (HLT’05), pages 411–418, Morristown, NJ. find
  35. Mihalcea, R. and D. I. Moldovan. 2001. eXtended WordNet: Progress report. In Proceedings of the NAACL Workshop on WordNet and Other Lexical Resources, pages 95–100, Pittsburgh, PA. find
  36. Miller, G. A., C. Leacock, R. Tengi, and R. Bunker. 1993. A semantic concordance. In Proceedings of the Workshop on Human Language Technology (HLT’93), pages 303–308, Plainsboro, NJ. find
  37. Naskar, S. K. and S. Bandyopadhyay. 2007. JU-SKNSB: Extended WordNet based WSD on the English all-words task at SemEval-1. In Proceedings of the 4th International Workshop on Semantic Evaluations (SemEval-2007) in conjunction with ACL, pages 203–206, Prague. find
  38. Navigli, R. 2008. A structural approach to the automatic adjudication of word sense disagreements. Natural Language Engineering, 14(4):547–573. find
  39. Navigli, R. and M. Lapata. 2007. Graph connectivity measures for unsupervised word sense disambiguation. In Proceedings of the 17th International Joint Conference on Artificial Intelligence (IJCAI’07), pages 1,683–1,688, Hyderabad. find
  40. Navigli, R. and M. Lapata. 2010. An experimental study of graph connectivity for unsupervised word sense disambiguation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 32(4):678–692. find
  41. 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 (SemEval-2007) in conjunction with ACL, pages 30–35, Prague. find our card
  42. 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):1,075–1,086. find
  43. Navigli, Roberto, Stefano Faralli, Aitor Soroa, Oier López de Lacalle, and Eneko Agirre. 2011. Two birds with one stone: Learning semantic models for text categorization and word sense disambiguation. In Proceedings of CIKM, pages 2,317–2,320, Glasgow. find
  44. 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, ACL ’96, pages 40–47, Stroudsburg, PA. find
  45. Ng, T. H. 1997. Getting serious about word sense disambiguation. In Proceedings of the ACL SIGLEX Workshop on Tagging Text with Lexical Semantics: Why, What, and How?, pages 1–7, Washington, DC. find
  46. Noreen, E. W. 1989. Computer-Intensive Methods for Testing Hypotheses. John Wiley & Sons. find
  47. Palmer, M., C. Fellbaum, S. Cotton, L. Delfs, and H. T. Dang. 2001. English tasks: All-words and verb lexical sample. In Proceedings of SENSEVAL-2: Second International Workshop on Evaluating Word Sense Disambiguation Systems, pages 21–24, Toulouse. find
  48. Patwardhan, S., S. Banerjee, and T. Pedersen. 2003. Using measures of semantic relatedness for word sense disambiguation. In Proceedings of the Fourth International Conference on Intelligent Text Processing and Computational Linguistics (CICLING-03), pages 241–257, Mexico City. find
  49. Pérez-Agüera, J. R. and H. Zaragoza. 2008. UCM-Y!R at CLEF 2008 Robust and WSD tasks. In Proceedings of the 9th Cross Language Evaluation Forum Workshop (CLEF’08), pages 138–145, Aarhus. find
  50. Ponzetto, S. P. and R. Navigli. 2010. Knowledge-rich word sense disambiguation rivaling supervised system. In Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics (ACL’10), pages 1,522–1,531, Uppsala. find
  51. Pradhan, 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 (SemEval-2007) in conjunction with ACL, pages 87–92, Prague. find
  52. Sinha, R. and R. Mihalcea. 2007. Unsupervised graph-based word sense disambiguation using measures of word semantic similarity. In Proceedings of the IEEE International Conference on Semantic Computing (ICSC 2007), pages 363–369, Irvine, CA. find
  53. Snyder, B. and M. Palmer. 2004. The English all-words task. In Proceedings of SENSEVAL-3 Third International Workshop on Evaluation of Systems for the Semantic Analysis of Text, pages 41–43, Barcelona. find
  54. 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 Text, pages 229–234, Barcelona. find
  55. Surdeanu, M., M. Ciaramita, and H. Zaragoza. 2008. Learning to rank answers on large online QA collections. In Proceedings of the 46th Annual Meeting of the Association for Computational Linguistics (ACL/HLT’08), pages 719–727, Columbus, OH. find
  56. Sussna, M. 1993. Word sense disambiguation for free-text indexing using a massive semantic network. In Proceedings of the Second International Conference on Information and Knowledge Management (CIKM’93), pages 67–74, New York, NY. find
  57. 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 (SemEval-2007) in conjunction with ACL, pages 264–267, Prague. find
  58. Tsatsaronis, G., I. Varlamis, and K. Nørvåg. 2010. An experimental study on unsupervised graph-based word sense disambiguation. In Proceedings of the 11th International Conference on Computational Linguistics and Intelligent Text Processing (CICLing’10), pages 184–198, Iasi. find
  59. Tsatsaronis, G., M. Vazirgiannis, and I. Androutsopoulos. 2007. Word sense disambiguation with spreading activation networks generated from thesauri. In Proceedings of the 17th International Joint Conference on Artificial Intelligence (IJCAI’07), pages 1,725–1,730, Hyderabad. find
  60. 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
  61. 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 (Volume 1: Long Papers), pages 273–282, Jeju Island. find