A Simple Approach to Building Ensembles of Naive Bayesian Classifiers for Word Sense Disambiguation

Ted PedersenNAACL 2000

TL;DR

This paper proposes a simple yet effective method for word sense disambiguation (WSD) by building an ensemble of Naive Bayesian classifiers. By combining the outputs of multiple classifiers, each trained on different window sizes of surrounding words, the authors achieve state-of-the-art accuracy on the challenging "line" and "interest" word datasets.

What Problem Does This Paper Address?

Word Sense Disambiguation (WSD) is the task of identifying the correct meaning of a word in a given context. This is crucial for many Natural Language Processing (NLP) tasks, such as machine translation and information retrieval. Traditional approaches often involve complex feature engineering and sophisticated machine learning models. However, previous research has shown that simple lexical features, like words that co-occur with the ambiguous word, are surprisingly effective. The challenge is to best leverage these simple features to achieve high disambiguation accuracy. This paper tackles this by exploring the power of ensemble methods with a focus on simple, yet robust, Naive Bayesian classifiers.

Methods

The core of this paper is an ensemble approach using Naive Bayesian (NB) classifiers. Here's a breakdown:

  • Naive Bayesian Classifier: This is a probabilistic classifier based on Bayes' theorem with a strong (naive) assumption of conditional independence between features. For WSD, features represent the presence of words within a defined context window around the ambiguous word.
  • Context Representation: The context is represented by binary features indicating whether a specific word appears within a certain number of words to the left or right of the ambiguous word. Punctuation and capitalization are removed, and words are kept in their original form (no stemming).
  • Ensemble Construction:
    • Individual Classifiers: Eighty-one individual NB classifiers are trained. Each classifier uses a unique combination of left and right context window sizes (ranging from 0 to 50 words).
  • Categorization: These 81 classifiers are grouped into nine "range categories" based on the general size of their context windows (narrow, medium, wide for both left and right).
  • Member Selection: The most accurate classifier from each of the nine range categories is selected to be a member of the final ensemble. This ensures diversity in the ensemble's context representations.
  • Majority Vote: The ensemble disambiguates by taking a majority vote from its nine member classifiers.

Datasets

The paper evaluates its approach on two well-studied WSD datasets:

  • Line: Originally created by Leacock et al. (1993), this dataset consists of occurrences of the word "line" tagged with one of six WordNet senses. For this study, a subset was used where each sense was uniformly distributed (349 instances per sense), resulting in a training corpus of 2094 sense-tagged sentences.
  • Interest: Created by Bruce and Wiebe (1994), this dataset tags occurrences of "interest" with senses from the Longman Dictionary of Contemporary English. This study used the entire corpus of 2368 sense-tagged sentences. The distribution of senses is skewed, with the majority sense appearing in 53% of sentences.

Key Insights and Ideas

  • Simplicity Wins (with Ensemble Power): The paper strongly suggests that a simple classifier like Naive Bayes, combined with basic co-occurrence features and an ensemble strategy, can rival more complex methods. This challenges the notion that advanced features are always necessary for high performance.
  • Diversity is Key for Ensembles: Simply averaging the predictions of all possible classifiers didn't work well. The success of the ensemble hinges on selecting members that represent differently sized windows of context. This diversity helps the ensemble "complement" errors made by individual classifiers.
  • Window Size Matters (and Grouping Helps): The authors found that classifiers with very similar window sizes offered little improvement. Grouping classifiers by general window size (narrow, medium, wide) and selecting the best from each group was a crucial step in building a robust ensemble.
  • Majority Vote is Sufficient: While weighted voting is a common ensemble technique, the paper found that a simple majority vote performed better for their specific ensemble of Naive Bayes classifiers.

Key Results

The proposed ensemble approach achieved impressive results:

  • Line: The ensemble achieved an accuracy of 88%, rivaling the best previously published results.
  • Interest: The ensemble achieved an accuracy of 89%, also comparable to top-performing methods.
  • The increase in accuracy achieved by the ensembles over the best individual classifier was statistically significant (p = .01) according to McNemar's test.

Limitations and Future Work

  • Parameter Explosion: Using wide context windows can lead to a large number of parameters in the Naive Bayesian model, potentially impacting the quality of parameter estimates. The authors suggest that stop-list usage and stemming could mitigate this.
  • Collocation Features: While co-occurrence features were effective, the paper notes that "collocation features" (words occurring in statistically significant proximity) could be further explored.
  • Handling Ties: The current majority vote mechanism doesn't specify how to handle situations where no sense receives a majority of votes. This is a potential issue for larger ensembles.
  • Optimal Window Size Determination: The current window sizes were chosen based on a combination of intuition and empirical study. The authors suggest developing an algorithm to automatically determine optimal window sizes.

Summary updated

BibTeX
@inproceedings{pedersen2000simple,
  author = {Ted Pedersen},
  title = {{A Simple Approach to Building Ensembles of Naive Bayesian Classifiers for Word Sense Disambiguation}},
  booktitle = {Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2000},
}
Figure