MMR-based Feature Selection for Text Categorization

Changki Lee, Gary Geunbae LeeNAACL 2004

TL;DR

This paper introduces a novel feature selection method called MMR-based feature selection for text categorization. It aims to reduce redundancy among selected features while preserving their information gain, outperforming traditional methods like Information Gain and a greedy approach in empirical tests.

What Problem Does This Paper Address?

Text categorization, the task of automatically assigning categories to documents, faces two major challenges: high dimensionality of the feature space (thousands of unique terms) and significant feature redundancy. High dimensionality makes machine learning algorithms computationally expensive and can degrade performance. Feature redundancy, where multiple terms convey similar information, can also negatively impact model accuracy, especially for algorithms that assume feature independence. Existing feature selection methods often focus on dimensionality reduction but don't adequately address redundancy.

Methods

The paper proposes MMR-based feature selection, a method that combines two criteria for selecting features:

  1. Information Gain (IG): Measures how much a feature helps predict the correct class label. This is a standard approach.
  2. Novelty of Information (Maximal Marginal Relevance - MMR): Measures the dissimilarity between a candidate feature and features already selected. This is the novel contribution, inspired by information retrieval techniques for ranking documents.

The MMR-based method selects features greedily, choosing the feature that maximizes a weighted combination of information gain and novelty. The weight, denoted by λ, allows tuning the balance between these two criteria. A λ of 1 favors pure information gain, while a λ of 0 favors maximal diversity (novelty).

Datasets

The authors evaluated their method on two standard text categorization datasets:

  • Reuters-21578: A large corpus of news articles.
  • WebKB: A collection of World Wide Web pages from computer science departments.

Key Insights and Ideas

  • Redundancy is a key problem: The paper highlights that simply reducing the number of features isn't enough; managing redundancy is crucial for better performance.
  • MMR offers a principled way to manage redundancy: By incorporating a measure of dissimilarity to already selected features, MMR-based selection actively avoids picking features that are too similar to those already chosen.
  • Balancing act with λ: The parameter λ provides a flexible way to tune the feature selection process, allowing a trade-off between maximizing information and maximizing feature diversity.
  • Potential to boost standard algorithms: The method not only improves feature selection but can also lead to better performance for conventional machine learning algorithms, sometimes even surpassing Support Vector Machines (SVMs), which are known for their high accuracy.

Key Results

  • Superior performance: MMR-based feature selection consistently outperformed conventional Information Gain (IG) and a greedy feature selection method (Koller & Sahami's) on both Reuters and WebKB datasets.
  • Significant improvements: For example, on the WebKB dataset with Naïve Bayes, MMR-based selection reduced the vocabulary from 41,763 terms to 200 (a 99.5% reduction) and improved accuracy from 85.26% to 90.49%. In contrast, greedy methods and IG only improved accuracy to around 87%.
  • Competitive with SVM: In some cases, MMR-based feature selection, when applied to conventional algorithms, achieved performance comparable to or even better than SVMs using all features.
  • Quadratic complexity: The method's computational cost is quadratic with respect to the number of features due to the pairwise information gain calculation. To mitigate this, the authors suggest applying MMR-based selection after an initial aggressive feature reduction using IG.

Limitations and Future Work

  • Computational Cost: The quadratic complexity of calculating pairwise information gain is a significant limitation. The authors propose using IG for initial reduction as a workaround.
  • Tuning λ: The method requires tuning the parameter λ, which necessitates a held-out validation set. The paper mentions testing 11 values of λ and selecting the best one.
  • Future Work: The paper implicitly suggests further research into more efficient ways to compute pairwise information gain or alternative novelty measures. Exploring more sophisticated tuning strategies for λ could also be a direction.

Summary updated

BibTeX
@inproceedings{lee2004mmr,
  author = {Changki Lee and Gary Geunbae Lee},
  title = {{MMR-based Feature Selection for Text Categorization}},
  booktitle = {Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2004},
}
Figure