Exemplar-Based Word Sense Disambiguation: Some Recent Improvements

Hwee Tou Ng

Abstract: In this paper, we report recent improvements to the exemplar-based learning approach for word sense disambiguation (WSD) that have achieved higher disambiguation accuracy. By using a larger value of $k$, the number of nearest neighbors used to determine the class of a test example, and through 10-fold cross-validation to automatically determine the best $k$, we have obtained improved disambiguation accuracy on a large sense-tagged corpus. The accuracy achieved by our improved exemplar-based classifier is comparable to the accuracy on the same data set obtained by the Naive-Bayes algorithm, which was previously reported to have the highest disambiguation accuracy among several state-of-the-art machine learning algorithms.

Introduction

In the late 1990s, the field of Natural Language Processing (NLP) underwent a significant shift toward corpus-based, statistical methods. One of the central challenges in this era was Word Sense Disambiguation (WSD)—the task of computationally determining the correct meaning of a word based on its context.

At the time, "eager learning" algorithms like Naive-Bayes were considered the gold standard. A prominent 1996 study by Mooney suggested that Naive-Bayes outperformed seven other major machine learning algorithms, including neural networks and decision trees. In contrast, "lazy learning" or exemplar-based methods, such as $k$-Nearest Neighbors ($k$-NN), were often dismissed as less accurate. This paper, authored by Hwee Tou Ng, challenges that consensus by demonstrating that the perceived inferiority of $k$-NN was largely due to sub-optimal hyperparameter selection rather than inherent algorithmic limitations.

The Exemplar-Based Approach

Exemplar-based learning is founded on the principle that new examples should be classified based on their similarity to previously encountered examples stored in memory. In the context of WSD, this means a target word in a new sentence is assigned the sense of the most similar examples in a sense-tagged corpus.

Technical Framework: PEBLS

The authors utilized the Parallel Exemplar-Based Learning System (PEBLS). Because WSD features are typically symbolic (words) rather than numeric, the system employs a Modified Value Difference Metric (MVDM). MVDM calculates the distance between two symbolic values by examining their conditional probabilities across different word senses, allowing the system to determine similarity in a statistically grounded way.

Optimizing the Neighborhood ($k$)

A common pitfall in earlier $k$-NN applications for WSD was the arbitrary use of $k=1$. This paper introduces a more robust methodology: automatic $k$ selection. For every ambiguous word, the system performs 10-fold cross-validation on the training data, testing 21 different values of $k$ (ranging from 1 to 100). The value of $k$ that minimizes the error rate for that specific word is then selected for the final classification task.

Experimental Setup

Feature Representation

The study focused on local collocations—the immediate lexical environment of the target word. Specifically, the system examined the sequence of two words to the left and two words to the right ($l_2 l_1 w r_1 r_2$). Unlike other models that pruned features to remove noise, the authors found that the exemplar-based model performed better when retaining all features, effectively utilizing the "long tail" of linguistic data.

Dataset

The evaluation was conducted on a massive sense-tagged corpus containing 192,800 occurrences of the 191 most frequent ambiguous English words (121 nouns and 70 verbs). Senses were defined according to WordNet. The performance was measured across two distinct evaluation sets:

  • BC50: 7,119 occurrences from the Brown Corpus.
  • WSJ6: 14,139 occurrences from the Wall Street Journal corpus.

Results and Discussion

The results demonstrated that optimizing $k$ provided a substantial performance boost, typically between 4% and 5% over the $k=1$ baseline. More importantly, the optimized PEBLS model achieved parity with Naive-Bayes.

Algorithm BC50 Accuracy WSJ6 Accuracy
Most Frequent Sense (Baseline) 47.1% 63.7%
PEBLS ($k=1$) 55.0% 70.2%
PEBLS (Optimized $k$) 58.7% 75.2%
Naive-Bayes 58.2% 74.5%

One interesting observation was the "fallback to frequency" effect. For words where contextual features were uninformative, the cross-validation process naturally selected a very large $k$. This effectively caused the classifier to default to the most frequent sense, a highly robust baseline strategy in WSD.

Conclusion

This research proves that exemplar-based learning is a top-tier contender for WSD when hyperparameters are tuned per-task. While $k$-NN remains more computationally intensive during the testing phase than probabilistic models, its ability to match the state-of-the-art performance of Naive-Bayes suggests that "lazy" algorithms are a powerful tool for linguistic disambiguation. Future improvements may involve incorporating richer feature sets, such as part-of-speech tags and syntactic relations, to further enhance accuracy.

Summary updated

Abstract

In this paper, we report recent improvements to the exemplar-based learning approach for word sense disambiguation that have achieved higher disambiguation accuracy. By using a larger value of $k$, the number of nearest neighbors to use for determining the class of a test example, and through 10-fold cross validation to automatically determine the best $k$, we have obtained improved disambiguation accuracy on a large sense-tagged corpus first used in \cite{ng96}. The accuracy achieved by our improved exemplar-based classifier is comparable to the accuracy on the same data set obtained by the Naive-Bayes algorithm, which was reported in \cite{mooney96} to have the highest disambiguation accuracy among seven state-of-the-art machine learning algorithms.
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