Unsupervised Word Sense Disambiguation Using Markov Random Field and Dependency Parser

Devendra Singh Chaplot, Pushpak Bhattacharyya, Ashwin ParanjapeAAAI 2015 · OpenReview

Abstract

Word Sense Disambiguation is a difficult problem to solve in the unsupervised setting. This is because in this setting inference becomes more dependent on the interplay between different senses in the context due to unavailability of learning resources. Using two basic ideas, sense dependency and selective dependency, we model the WSD problem as a Maximum A Posteriori (MAP) Inference Query on a Markov Random Field (MRF) built using WordNet and Link Parser or Stanford Parser. To the best of our knowledge this combination of dependency and MRF is novel, and our graph-based unsupervised WSD system beats state-of-the-art system on SensEval-2, SensEval-3 and SemEval-2007 English all-words datasets while being over 35 times faster.

Introduction

Word Sense Disambiguation (WSD) is the task of determining which "sense" of a word is being used in a specific context (e.g., distinguishing between "bank" as a financial institution versus a river edge). While supervised models perform well, they require massive amounts of hand-labeled data, which is expensive to produce.

Unsupervised, graph-based methods are a popular alternative, but they face two major hurdles: exponential complexity and "sense drift." In dense graphs, words that are syntactically unrelated can misguide each other. This paper introduces a highly efficient approach that combines the structural insights of dependency parsers with the probabilistic framework of Markov Random Fields (MRFs) to eliminate noise and reduce computational complexity.

Methods

The core innovation of this work is Selective Dependency. The authors argue that a word's sense depends only on a few other words in a sentence, and these relationships are best captured by a dependency parser rather than a fully connected graph.

System workflow diagram showing the integration of dependency parsing and MRF for WSD.

The workflow is as follows:

  1. Graph Construction: Each content word (noun, verb, adjective, adverb) becomes a node in an MRF. The possible states for each node are its senses in WordNet.
  2. Edge Pruning: Instead of a fully connected graph, edges are only drawn between words that have a direct syntactic relationship (determined by the Link Parser or Stanford Parser). This reduces the number of edges by approximately 91%.
  3. Potentials: Node potentials are based on the frequency of senses in WordNet, while edge potentials represent the "relatedness" of two senses, calculated using standard measures like Lesk or Path similarity.
  4. MAP Inference: The problem is solved as a Maximum A Posteriori (MAP) query. Because the dependency-based graph has a very small treewidth, the authors can use exact inference algorithms rather than the approximate methods required by denser models.

Results

The system was evaluated on three standard English all-words benchmarks: SensEval-2 (S2AW), SensEval-3 (S3AW), and SemEval-2007 (S07AW), using WordNet 3.0 as the sense inventory.

Comparison of the proposed MRF-based system against state-of-the-art unsupervised WSD methods.

Key findings include:

  • State-of-the-Art Accuracy: The system (MRF-LP) achieved an F1 score of 60.5 on SensEval-2 and 58.6 on SensEval-3, outperforming previous top-tier unsupervised systems.
  • Massive Speedup: The system processed the entire SensEval-2 dataset in just 55 seconds. This equates to roughly 2700 instances per minute, compared to approximately 70 instances per minute achieved by previous state-of-the-art systems.
  • Parser Agnostic: Results were consistently high regardless of whether the Link Parser or Stanford Parser was used, suggesting the method is robust to different syntactic modeling choices.

Conclusion

By using syntactic structure as a filter, the proposed MRF model avoids the "noise" that causes sense drift and enables exact, high-speed inference. While dependency parsers may miss some purely semantic links, the dramatic gains in efficiency make this approach highly viable for real-time NLP pipelines. Future work will investigate techniques to add semantic edges that dependency parsers might miss to further increase accuracy.

Summary updated

Abstract

Word Sense Disambiguation is a difficult problem to solve in the unsupervised setting. This is because in this setting inference becomes more dependent on the interplay between different senses in the context due to unavailability of learning resources. Using two basic ideas, sense dependency and selective dependency, we model the WSD problem as a Maximum A Posteriori (MAP) Inference Query on a Markov Random Field (MRF) built using WordNet and Link Parser or Stanford Parser. To the best of our knowledge this combination of dependency and MRF is novel, and our graph-based unsupervised WSD system beats state-of-the-art system on SensEval-2, SensEval-3 and SemEval-2007 English all-words datasets while being over 35 times faster.
BibTeX
@inproceedings{chaplot2015unsupervised,
  author = {Devendra Singh Chaplot and Pushpak Bhattacharyya and Ashwin Paranjape},
  title = {{Unsupervised Word Sense Disambiguation Using Markov Random Field and Dependency Parser}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2015},
  url = {https://openreview.net/forum?id=H1-ou6gO-H},
}
Figure