Exemplar-Based Word Sense Disambiguation" Some Recent Improvements

Hwee Tou Ng

Abstract: This study demonstrates that exemplar-based (k-Nearest Neighbor) learning can outperform the then-state-of-the-art Naive-Bayes algorithm for Word Sense Disambiguation (WSD). By moving away from a fixed $k=1$ and using 10-fold cross-validation to automatically select an optimal, often larger $k$, the researchers achieved significant accuracy gains on a massive sense-tagged corpus.

Introduction

Word Sense Disambiguation (WSD)—the task of determining which "sense" of a word is being used in a specific context—is a foundational challenge in Natural Language Processing. In the mid-90s, the Naive-Bayes classifier was considered the "gold standard," outperforming more complex algorithms. Previous exemplar-based approaches, which compare new words to specific stored examples, had lagged behind. This research investigates whether this performance gap was due to a fundamental flaw or suboptimal parameter tuning, specifically regarding the choice of $k$ (the number of neighbors considered).

Methods

The authors utilized the PEBLS (Parallel Exemplar-Based Learning System) algorithm, introducing key refinements:

  1. Distance Metric: A "value difference metric" was employed to calculate distances between symbolic feature values based on their conditional probabilities across classes, rather than simple Hamming distance.
  2. Automatic $k$ Selection: Moving beyond the default $k=1$, the system uses 10-fold cross-validation on the training data to test 21 different values of $k$ (ranging from 1 to 100). The value yielding the lowest error rate is selected for the final test.
  3. Feature Set: Each word occurrence is represented by seven local collocation features, focusing on the immediate linguistic context.

Datasets

The study utilized a substantial sense-tagged corpus consisting of approximately 192,800 occurrences of 191 frequent English words. Sentences were drawn from the Brown Corpus and the Wall Street Journal (WSJ). Evaluation was conducted on two subsets: BC50 (7,119 occurrences) and WSJ6 (14,139 occurrences).

Key Insights

  • The Smoothing Effect: Increasing $k$ (e.g., to $k=20$) provides a smoothing effect that mitigates the impact of noise or outliers present in $k=1$ models.
  • Fail-Safe Mechanism: For difficult words where the model struggles, cross-validation often selects a very large $k$, effectively defaulting to the "most frequent sense" baseline.
  • Feature Retention: Contrary to previous attempts at "feature pruning," keeping all collocations provided better results when paired with a higher $k$.

Key Results

The improvements were consistent across both test sets. As shown in Figure 1, the PEBLS algorithm with 10-fold cross-validation achieved the highest accuracy, slightly edging out the previously dominant Naive-Bayes algorithm.

Comparison of WSD algorithm accuracy on BC50 and WSJ6 datasets.

The results demonstrate that automatically selecting $k$ via cross-validation improves performance by ~4-5% over the $k=1$ baseline and establishes a new performance benchmark for the task. Specifically, PEBLS (10-fold c.v.) reached 58.7% on BC50 and 75.2% on WSJ6, compared to 58.2% and 74.5% for Naive-Bayes.

Limitations and Future Work

The primary drawback of exemplar-based learning is its linear testing time complexity. Future work may explore logarithmic-time indexing methods to improve efficiency. Additionally, incorporating broader knowledge sources—such as part-of-speech tags and syntactic relations—or automatically tuning feature weights could further enhance disambiguation accuracy.

Summary updated

Abstract

Hwee Tou Ng. Second Conference on Empirical Methods in Natural Language Processing. 1997.
BibTeX
@inproceedings{ng1997exemplar,
  author = {Hwee Tou Ng},
  title = {{Exemplar-Based Word Sense Disambiguation" Some Recent Improvements}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {1997},
  url = {https://openreview.net/forum?id=Vv_VA6b-xNG},
}
Figure