Random-Walk-based Natural Language Processing Algorithm

A Random-Walk-based Natural Language Processing Algorithm is a NLP Algorithm that is based on a Random Walk Algorithm.

• AKA: Random Walk Natural Language Processing (RW-NLP) Algorithm.
• Example(s):
  • a Random-Walk-based Sense Disambiguation Algorithm (e.g.Pilehvar et al., 2013),
  • a Random-Walk-based Text Semantic Similarity Algorithm (e.g. Ramage et al., 2009)
• Counter-Example(s):
  • an Alignment-based Linguistic Sense Disambiguation Algorithm,
• See: Word Sense Disambiguation Algorithm, Align-Disambiguate-Walk (ADW) Semantic Similarity System, Random Walk Probabilistic Model, Semantic Word Similarity, Semantic Textual Similarity.

---

---

References

2013

• (Pilehvar et al., 2013) ⇒ Mohammad Taher Pilehvar, David Jurgens, and Roberto Navigli. (2013). “Align, Disambiguate and Walk: A Unified Approach for Measuring Semantic Similarity.” In: Proceedings of the 51st Annual Meeting of the Association for Computational Linguistics (ACL 2013) Volume 1: Long Papers.
  • QUOTE: Given a particular node (sense) in the network, repeated random walks beginning at that node will produce a frequency distribution over the nodes in the graph visited during the walk. To extend beyond a single sense, the random walk may be initialized and restarted from a set of senses (seed nodes), rather than just one; this multi-seed walk produces a multinomial distribution over all the senses in WordNet with higher probability assigned to senses that are frequently visited from the seeds.

2009

• (Ramage et al., 2009) ⇒ Daniel Ramage, Anna N. Rafferty, and Christopher D. Manning. (2009). “Random Walks for Text Semantic Similarity.” In: Proceedings of the 2009 Workshop on Graph-based Methods for Natural Language Processing.

---