Elamur Research
☰
home / papers / 2009 / Personalizing PageRank for Word Sense Disambiguation

Personalizing PageRank for 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/E09-1005.pdf

Summary

The paper addresses word sense disambiguation (WSD) without training data. To do so, it uses only a lexical knowledge base (LKB) built on WordNet. Classical approaches compare word senses pairwise and process words one at a time. Graph-based methods mostly build a small subgraph for each context. The authors instead run Personalized PageRank over the full WordNet graph. The random-jump probability is concentrated on the nodes of the context words. This way importance propagates through the graph, and the senses most closely connected to the surrounding context receive the highest rank. The authors also propose a variant, Ppr_w2w. For each target word, only the neighboring words receive the initial mass, so the senses of the word itself do not reinforce one another. On English all-words datasets the method outperformed previous graph-based systems. An experiment with Spanish showed that the method can be easily ported to another language if a wordnet exists for it. For both languages, performance approaches the MFS baseline. The implementation is released as the UKB tool, and it can be applied to other sense inventories.

Key points

  • Three algorithms are compared. Spr is standard PageRank on the context subgraph, Ppr is Personalized PageRank on the full graph, and Ppr_w2w is a separate run for each word. Parameters: damping 0.85, 30 iterations, a context of at least 20 content words.
  • Three LKBs are used. MCR16 + Xwn has 99,632 vertices and 637,290 relations, WNet17 + Xwn has 109,359 vertices and 620,396 edges, and WNet30 + gloss has 117,522 vertices and 525,356 relations. The authors stress that performance depends heavily on the choice of WordNet version and relation types.
  • Speed was measured on Senseval-2 (2473 word occurrences in 476 sentences). Ppr takes about 27 min (about 82 occurrences per minute), Spr about 2 h, and Ppr_w2w almost 3 h (about 15 per minute). The code is written in C++ with the Boost Graph Library.
  • The algorithm converges quickly. A single iteration already gives decent performance, and 20 iterations are enough for full convergence. Hence the number of iterations can be reduced to speed things up.
  • For Spanish, the Spanish WordNet and the SemEval-2007 Task 09 dataset were used. The dataset contains examples for the 150 most frequent nouns of the CESS-ECE corpus.

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

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

Cite

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

@inproceedings{agirre2009personalizing,
  title = {{Personalizing PageRank for Word Sense Disambiguation}},
  author = {Agirre, Eneko and Soroa, Aitor},
  booktitle = {Proceedings of the 12th Conference of the European Chapter of the ACL (EACL 2009)},
  year = {2009},
  url = {https://aclanthology.org/E09-1005/}
}

References

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

  1. E. Agirre and G. Rigau. 1996. Word sense disambiguation using conceptual density. In In Proceedings of the 16th International Conference on Computational Linguistics, pages 16–22. http://ixa2.si.ehu.es/ukb ↗
  2. E. Agirre and A. Soroa. 2008. Using the multilingual central repository for graph-based word sense 3 disambiguation. In Proceedings of LREC ’08, Marrakesh, Morocco. find
  3. J. Atserias, G. Rigau, and L. Villarejo. 2004a. Spanish wordnet 1.6: Porting the spanish wordnet across princeton versions. In In Proceedings of LREC ’04. find
  4. J. Atserias, L. Villarejo, G. Rigau, E. Agirre, J. Carroll, B. Magnini, and P. Vossen. 2004b. The meaning multilingual central repository. In In Proceedings of 30 GWC, Brno, Czech Republic. find
  5. S. Brin and L. Page. 1998. The anatomy of a large-scale hypertextual web search engine. Computer Networks and ISDN Systems, 30(1-7). find our card
  6. J. Cowie, J. Guthrie, and L. Guthrie. 1992. Lexical disambiguation using simulated annealing. In HLT ’91: Proceedings of the workshop on Speech and Natural Language, pages 238–242, Morristown, NJ, USA. find
  7. J. Daude, L. Padro, and G. Rigau. 2000. Mapping WordNets using structural information. In Proceedings of ACL’2000, Hong Kong. find
  8. T. H. Haveliwala. 2002. Topic-sensitive pagerank. In WWW ’02: Proceedings of the 11th international conference on World Wide Web, pages 517–526, New York, NY, USA. ACM. find
  9. A. N. Langville and C. D. Meyer. 2003. Deeper inside pagerank. Internet Mathematics, 1(3):335–380. find
  10. M. Lesk. 1986. Automatic sense disambiguation using machine readable dictionaries: how to tell a pine cone from an ice cream cone. In SIGDOC ’86: Proceedings of the 5th annual international conference on Systems documentation, pages 24–26, New York, NY, USA. ACM. find
  11. L. Màrquez, L. Villarejo, M. A. Martı́, and M. Taulé. 2007. Semeval-2007 task 09: Multilevel semantic annotation of catalan and spanish. In Proceedings of SemEval-2007, pages 42–47, Prague, Czech Republic, June. find
  12. D. McCarthy, R. Koeling, J. Weeds, and J. Carroll. 2004. Finding predominant word senses in untagged text. In ACL ’04: Proceedings of the 42nd Annual Meeting on Association for Computational Linguistics, page 279, Morristown, NJ, USA. Association for Computational Linguistics. find our card
  13. R. Mihalcea and D. I. Moldovan. 2001. eXtended WordNet: Progress report. In in Proceedings of NAACL Workshop on WordNet and Other Lexical Resources, pages 95–100. find
  14. R. Mihalcea. 2005. Unsupervised large-vocabulary word sense disambiguation with graph-based algorithms for sequence data labeling. In Proceedings of HLT05, Morristown, NJ, USA. find
  15. R. Navigli and M. Lapata. 2007. Graph connectivity measures for unsupervised word sense disambiguation. In IJCAI. find
  16. R. Navigli and P. Velardi. 2005. Structural semantic interconnections: A knowledge-based approach to word sense disambiguation. IEEE Trans. Pattern Anal. Mach. Intell., 27(7):1075–1086. find
  17. M. Palmer, C. Fellbaum, S. Cotton, L. Delfs, and H.T. Dang. 2001. English tasks: All-words and verb lexical sample. In Proc. of SENSEVAL-2: Second International Workshop on Evaluating Word Sense Disambiguation Systems, Tolouse, France, July. find
  18. S. Pradhan, E. Loper, D. Dligach, and M.Palmer. 2007. Semeval-2007 task-17: English lexical sample srl and all words. In Proceedings of SemEval-2007, pages 87–92, Prague, Czech Republic, June. find
  19. R. Sinha 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), Irvine, CA, USA. find
  20. B. Snyder and M. Palmer. 2004. The English all-words task. In ACL 2004 Senseval-3 Workshop, Barcelona, Spain, July. find
  21. G. Tsatsaronis, M. Vazirgiannis, and I. Androutsopoulos. 2007. Word sense disambiguation with spreading activation networks generated from thesauri. In IJCAI. find