Feature Selection in SVM Text Categorization

AAAI 1999

TL;DR

This paper investigates how feature selection impacts Support Vector Machine (SVM) text categorization. They found that while SVMs can handle a large number of features, they struggle to automatically discard irrelevant ones. A simple, rough filtering method like part-of-speech tagging proved more effective than sophisticated methods like mutual information for SVMs, suggesting a practical strategy for building robust text classifiers.

What Problem Does This Paper Address?

Automatic text categorization is crucial for managing the explosion of online information. Machine learning algorithms are used for this, but they face a significant challenge: the sheer volume of words (features) in text data. This "curse of dimensionality" can hinder performance. Furthermore, the optimal set of words for classification can vary greatly depending on the specific learning algorithm used. This paper specifically tackles how to best select features (words) for SVMs, a powerful algorithm known for its good generalization performance, especially in high-dimensional spaces. They question whether sophisticated feature selection methods are necessary or if simpler approaches suffice, particularly for languages like Japanese where word segmentation can be complex.

Methods

The core of this research lies in comparing two distinct feature selection strategies applied to SVM text categorization:

  • Mutual Information (MI) Filtering: This method selects words that have a high mutual information score with a specific category. The intuition is that words with high MI are more representative of that category.
  • Part-of-Speech (POS) Filtering: This approach uses linguistic information by selecting words based on their grammatical category (e.g., common nouns, proper nouns, verbs). This leverages a natural language processing (NLP) technique for initial filtering.

They also used a decision tree algorithm, C4.5, as a baseline for comparison. The SVMs were tested with polynomial kernels of degree 1 and 2. The feature values were binary, indicating the presence or absence of a word in a document.

Datasets

The experiments were conducted using the RWCP corpus, a collection of 30,207 Japanese newspaper articles from the Mainichi Shinbun published in 1994. The study focused on ten categories that appeared most frequently in the corpus: sports, criminal law, government, education, traffic, military affairs, international relations, communications, theater, and agriculture. A total of 1,000 articles were used for training and testing across these categories. The articles were pre-processed using the Chasen morphological analysis system, resulting in approximately 20,490 distinct words.

Key Insights and Ideas

  • SVMs are Feature-Rich Learners, But Not Feature Selectors: The most striking finding is that SVMs perform well even with a very large number of features. However, they don't seem to effectively discard irrelevant features on their own. This means that while SVMs can handle a lot of data, they don't inherently select the best subset.
  • Simplicity Wins for SVMs: Contrary to what one might expect, a simple, rough filtering method like POS tagging outperformed the more theoretically grounded MI filtering for SVMs. This suggests that for SVMs, getting rid of obviously irrelevant word types (like conjunctions or prepositions) is more beneficial than trying to precisely rank words by their relevance to a specific category.
  • Category-Specific Optimal Features: The "optimal" number of features for best performance varied significantly across different categories, even when using the same filtering method. This highlights the challenge of finding a universal feature set.
  • POS Tagging as a Practical Strategy: The paper proposes a simple, practical strategy: use a rough filtering technique like POS tagging to create a manageable set of features, and then feed this entire set to the SVM. This avoids the complexity of fine-grained feature selection.

Key Results

  • Average Performance: For both MI and POS filtering, the average performance across all categories was generally best when a large number of features were used (e.g., 15,000 for MI filtering, and all words from the selected POS categories for POS filtering).
  • MI Filtering vs. POS Filtering: POS filtering consistently outperformed MI filtering on SVMs. For example, with 15,000 features from MI filtering, SVMs achieved an average recall/precision of 75.5%/74.8%, while with all selected POS features (Feature Set 5), the average was 78.1%/77.2%.
  • SVMs vs. C4.5: SVMs significantly outperformed the C4.5 decision tree algorithm across the board, especially when using a large number of features. C4.5 achieved its best performance at much smaller feature sets and showed abrupt performance drops with more features, whereas SVMs showed more stable or improving performance.
  • POS Contributions: Common nouns alone provided near-optimal performance in many categories, demonstrating their significant value. Adding other POS categories generally improved performance, with unknown words contributing the least, likely due to noise.

Limitations and Future Work

  • SVMs' Inability to Detect Irrelevant POS: A key limitation identified is that SVMs, even with a large number of features, struggle to automatically discard irrelevant parts of speech. This is why POS filtering is so effective – it pre-emptively removes less useful word types.
  • Kernel Function Influence: The paper notes that changing the polynomial kernel order (1 vs. 2) had no distinct difference in performance for text categorization, unlike in some lower-level tasks like image processing.
  • Future Work: The authors suggest that SVMs and other large-margin classifiers are well-suited for handling complex NLP tasks and that further research could explore their role in such applications. The findings strongly support the practical strategy of using rough filtering techniques like POS tagging for SVM text categorization.

Summary updated

BibTeX
@inproceedings{1999feature,
  title = {{Feature Selection in SVM Text Categorization}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1999},
}
Figure