Source-linked AI summary
Toward Optimal Feature Selection in Naive Bayes for Text Categorization
Bo Tang, Steven Kay, Haibo He
TL;DR
Text categorization requires feature reduction because high-dimensional vocabularies increase computational burden and irrelevant or redundant features may impair classification. The paper develops information-theoretic feature ranking for naive Bayes, introducing JMH divergence and the MD and MD-χ2 methods. Experiments on benchmark datasets report improved performance for the proposed approaches, while the paper notes computational and theoretical limitations.
Problem
High-dimensional text features burden learning, and existing filter methods do not account for the learning algorithm’s discrimination behavior.
Method
The paper introduces JMH divergence and uses it to rank features for naive Bayes through maximum discrimination and MD-χ2 methods.
Results
The proposed approaches commonly outperform other methods on 20-NEWSGROUPS and ALT-COMP benchmark results.
Takeaways & Limitations
The approaches provide a theoretical way to analyze feature-selection optimality while incorporating the learning model into feature filtering.
Takeaways & Limitations
The greedy approach has O(M^2/2) computational complexity, and further theoretical study is needed to determine when MD-χ2 outperforms MD.
Abstract
from arXiv · showhide
Automated feature selection is important for text categorization to reduce the feature size and to speed up the learning process of classifiers. In this paper, we present a novel and efficient feature selection framework based on the Information Theory, which aims to rank the features with their discriminative capacity for classification. We first revisit two information measures: Kullback-Leibler divergence and Jeffreys divergence for binary hypothesis testing, and analyze their asymptotic properties relating to type I and type II errors of a Bayesian classifier. We then introduce a new divergence measure, called Jeffreys-Multi-Hypothesis (JMH) divergence, to measure multi-distribution divergence for multi-class classification. Based on the JMH-divergence, we develop two efficient feature selection methods, termed maximum discrimination ($MD$) and $MD-χ^2$ methods, for text categorization. The promising results of extensive experiments demonstrate the effectiveness of the proposed approaches.
1 INTRODUCTION
Text categorization must handle high-dimensional document representations, where irrelevant and redundant terms increase computational burden and may reduce classification performance. The paper therefore develops information-theoretic feature ranking methods tailored to naive Bayes discrimination.
- 1 INTRODUCTION: High-dimensional text representations create computational burden, while irrelevant and redundant features may hurt classifier performance.Feature reduction is used to mitigate the curse of dimensionality and speed learning.
- 1 INTRODUCTION: Feature selection keeps a subset of original features as input to learning algorithms and is commonly implemented through filter or wrapper approaches.Filter methods use data characteristics without involving the eventual learning algorithm, whereas wrappers retrain and evaluate classifiers during subset search.
- 1 INTRODUCTION: Filter methods are simple and efficient but may select features without accounting for the learning algorithm’s discrimination behavior.For a specific classifier, identifying the theoretically best filter approach is difficult.
- 1 INTRODUCTION: The paper ranks features for maximum discriminative performance when naive Bayes is used, without explicitly training a classifier.Feature goodness is evaluated using a new divergence measure.
- 1 INTRODUCTION: The authors introduce JMH divergence, an efficient approximate ranking procedure, and a χ2-based ranking approach derived from asymptotic analysis.The theoretical analysis states that JMH divergence increases monotonically as more features are selected.
2 PREVIOUS WORK
Previous work represents documents with bag-of-words features and commonly applies naive Bayes or feature-selection methods to reduce vocabulary size. Existing approaches include multinomial and binary modeling, frequency-based filters, wrappers, and information-theoretic scores, while the paper emphasizes term-occurrence information.
- 2.1 Document Representation: Bag-of-words represents each document as a feature vector whose elements correspond to vocabulary terms or phrases.Feature values encode term importance according to a chosen measurement.
- 2.1 Document Representation: Binary features encode term presence or absence, whereas term-frequency features encode occurrence counts and are commonly modeled with Bernoulli or multinomial distributions.The paper’s multinomial naive Bayes formulation uses integer-valued term-frequency vectors.
- 2.2 Naive Bayes: Naive Bayes is widely used in text categorization because of its simplicity and efficiency, and the paper focuses on the multinomial formulation.The proposed methods can be extended to binary and Poisson naive Bayes classifiers.
- 2.2 Naive Bayes: Multinomial naive Bayes models documents through term counts over independent trials and estimates class-specific term probabilities, with Laplace smoothing used to avoid zero probabilities.Document vectors contain one component per vocabulary term.
- 2.3 Feature Selection: Feature selection reduces dimensionality by retaining a predetermined number of terms; prior work reported removal of 98% of unique terms without greatly harming classification performance.Filter methods rank features by importance at low computational cost, while wrappers search subsets through repeated classifier training and validation.
- 2.3 Feature Selection: Common filters include document frequency and TF-IDF, while the proposed approaches use term occurrence rather than only binary presence or absence.The paper motivates term occurrence as containing richer information than the binary variables used by many information-theoretic filters.
3 THEORETICAL FRAMEWORK OF FEATURE SELECTION
The framework uses information-theoretic divergences to quantify discriminative capacity in binary and multi-class classification. It extends Jeffreys divergence to multiple hypotheses through JMH divergence, using one-vs-all comparisons across class distributions.
- Binary hypothesis testing: KL-divergence measures mean information for discriminating one class against another, while Jeffreys divergence combines both directional divergences.The framework relates larger divergences to lower asymptotic classification errors.
- Binary hypothesis testing: A larger KL-divergence indicates a lower type I error asymptotically, while a larger J-divergence may lead to smaller type I and type II errors.These relationships hold for large or infinite numbers of observations.
- Binary hypothesis testing: Feature selection is formulated as maximizing discriminative capacity, because the J-divergence is linked to classification difficulty and capacity for binary hypotheses.The paper extends this binary measure because J-divergence is defined only for binary hypothesis testing.
- Multi-class hypothesis testing: JMH divergence sums KL-divergences between each class distribution P_i and a mixture of the remaining class distributions.The mixture coefficients are prior coefficients over the other N−1 classes.
- Multi-class hypothesis testing: The multi-class construction uses N one-vs-all detectors and measures discrimination across all classes; for N = 2, JMH divergence equals J-divergence.The measure is symmetric and nonnegative, with equality when all class-conditional multinomial parameters are identical.
4 SELECTING THE MAXIMUM DISCRIMINATIVE FEATURES
The paper selects features by their discriminative capacity for naive Bayes rather than by feature relevance alone. It develops greedy and efficient ranking procedures, with monotonic discrimination, reduced computational cost, and practical comparisons with χ^2 selection.
- Objective: The feature-selection objective is to choose the most discriminative features for classification rather than merely score feature relevance to classes.For a predetermined number r of features, the goal is to find the subset with maximum discriminative capacity.
- Efficient ranking: The efficient approach ranks features by calculating each feature score once, replacing greedy search with a sorted feature index set.Its motivation is to assign importance scores while reducing the computational burden of the greedy procedure.
- Greedy selection: The greedy two-class algorithm selects the feature producing the maximum J-divergence at each step and then repeats over the remaining features.It forms distributions for the selected features plus a pooled variable representing the remaining features.
- Greedy selection: The maximum J-divergences in the greedy algorithm monotonically increase as more features are selected.The algorithm makes locally optimal choices to approximate the global optimum under the multinomial term-occurrence assumption.
- Greedy selection: The greedy approach avoids validation-set retraining because a closed-form KL-divergence measures naive Bayes discriminative capacity, but its complexity is O(M^2/2).This complexity can impose a heavy computational load for high-dimensional data.
- χ^2 comparison: The χ^2 approach is asymptotically equivalent to the corresponding algorithm with infinite training documents, but may lose discriminative capacity with limited data.Experiments generally bound χ^2 discrimination by the alternative, although χ^2 performs better on some real-life text datasets.
5 EXPERIMENTAL RESULTS AND ANALYSIS
Experiments across 20-NEWSGROUPS, ALT-COMP, REUTERS, and TDT2 compare MD and MD-χ2 with established feature-ranking methods for naive Bayes and SVM. The proposed methods generally deliver stronger performance with fewer selected features, although their relative advantage varies by dataset and method.
- Experimental setup: The experiments evaluate MD and MD-χ2 against DF, CET, χ2, and GSS using accuracy and F1 across feature sizes from 10 to 2,000.The study uses three benchmarks: 20-NEWSGROUPS, REUTERS, and TDT2, with naive Bayes and SVM classifiers.
- Naive Bayes results: On 20-NEWSGROUPS, performance improves with more selected features, while MD commonly outperforms the comparison methods.DF is reported as the worst method on this dataset.
- Naive Bayes results: On ALT-COMP, MD-χ2 is best overall, and MD and MD-χ2 are the top two methods for F1 measure.The reported accuracy exceeds 80% even with a small feature subset, unlike the 20-NEWSGROUPS result, which is below 20% in that setting.
- Naive Bayes results: With the first 200 selected features on REUTERS, MD and MD-χ2 achieve performance similar to the other methods using the first 1,000 features.Their performance improvement relative to the other methods increases as more categories are included.
- Naive Bayes results: On TDT2, MD and MD-χ2 outperform the other methods in accuracy; with 100 features, MD reaches 96.46% and MD-χ2 reaches 95.76%.GSS and χ2 require 1,000 features to reach the same classification accuracy.
- SVM results: For SVM on REUTERS, MD and MD-χ2 perform at least as well as existing methods at small feature sizes and are consistently better as feature size increases.The SVM comparisons are reported on the three REUTERS datasets.
6 CONCLUSIONS AND FUTURE WORKS
The paper introduces information-theoretic feature selection approaches for naive Bayes that target maximum discriminative capacity and reports promising improvements over existing methods. Future work will address feature dependence and extend the approaches to other learning settings.
- The proposed feature selection approaches use information measures to select features with maximum discriminative capacity for text classification.
- The approaches incorporate the learning model into feature filtering, enabling theoretical analysis of the optimality of selected features.
- Experiments on several benchmarks demonstrate promising performance improvements compared with previously existing feature selection approaches.
- Future work: Future work will analyze feature dependence and weight individual features to maximize discriminative capacity.
- Future work: Future work will also incorporate the approaches into imbalanced and partial learning models to enhance learning for rare categories.