TL;DR
This paper introduces a novel feature selection score for text classification based on KL-divergence, aiming to improve Naive Bayes performance. The proposed method, KL-divergence based scoring, outperforms traditional mutual information, especially for smaller text categories, by better identifying words that are discriminative across classes.
What Problem Does This Paper Address?
Text classification, the task of assigning predefined categories to documents, is crucial for applications like email filtering and content organization. Naive Bayes is a popular and simple classifier for this task. However, to prevent overfitting and improve efficiency, feature selection is often employed to choose the most informative words. While mutual information is a well-established feature selection metric, this paper argues that it might not be optimal for all scenarios, particularly for smaller categories. The authors propose a new scoring function that aims to capture a more nuanced understanding of word relevance by considering the distribution of words within and across classes.
Methods
The core of this paper is the introduction of a new feature selection score based on the Kullback-Leibler (KL) divergence. The authors interpret Naive Bayes classification through an information-theoretic lens, showing that it essentially seeks to minimize the KL-divergence between a document's word distribution and the word distribution of a class.
Their proposed score, denoted as $KL(w_t) = K_t(S) - KL_t(S)$, is derived from two components:
- $K_t(S)$: An approximation of the average divergence of a word's distribution in individual training documents from the global distribution of that word across all documents.
- $KL_t(S)$: An approximation of the average KL-divergence of a word's distribution in individual training documents from its distribution within its true class.
The intuition is that words with a low score are those that are either too common across all documents or too uniformly distributed within a class, making them less discriminative. By removing such words, the remaining words are expected to have a more distinct distribution across different classes, leading to more homogeneous classes and improved classification. A variant, $dKL$, is also proposed, using a slightly different estimation for word probabilities.
Datasets
The authors evaluate their proposed methods on two standard text classification datasets:
- 20 Newsgroups: A collection of documents from 20 different newsgroups.
- Reuters 21578: A widely used dataset for text categorization.
For 20 Newsgroups, they used 5-fold cross-validation, with 80% of data for training and 20% for testing. For Reuters 21578, they used the ModApte split and focused on the 10 largest classes, building binary classifiers for each topic.
Key Insights and Ideas
- Naive Bayes as KL-Divergence Minimization: The paper elegantly reframes Naive Bayes classification as minimizing the KL-divergence between a document's word distribution and a class's word distribution. This provides a strong theoretical foundation for exploring information-theoretic feature selection.
- Beyond Simple Word Frequency: The proposed KL-divergence based scores go beyond simply counting word occurrences or their presence/absence across classes. They consider how uniformly or unevenly a word is distributed within a class and across the entire corpus.
- Effectiveness for Smaller Categories: The most significant insight is that the KL-divergence based scores, particularly $dKL$, show a notable improvement over mutual information for smaller categories. This suggests that traditional metrics might overlook subtle but important discriminative power in less frequent classes.
- Trade-off Between Homogeneity and Discriminability: The paper highlights a potential trade-off: making classes more homogeneous by removing less discriminative words can, in some cases, reduce the ability to distinguish between classes. The proposed scores aim to strike a balance.
Key Results
- 20 Newsgroups: The $dKL$ scoring function slightly outperformed mutual information, especially for smaller vocabulary sizes. The difference was statistically significant for certain vocabulary ranges.
- Reuters 21578:
- Microaveraged Recall: Both $KL$ and $dKL$ achieved higher microaveraged recall than mutual information across most vocabulary sizes. $dKL$ showed the largest improvement at 100 words.
- Macroaveraged Recall: For smaller categories (indicated by macroaveraged recall), the difference was more pronounced. $KL$ and $dKL$ showed significant improvements over mutual information, particularly at larger vocabulary sizes. The largest improvements were observed at 5000 words.
Limitations and Future Work
- Approximation Error: The paper uses an approximation for the KL-divergence calculation to reduce computational cost. The authors acknowledge that assessing the error introduced by this approximation is a topic for future work.
- Computational Cost: While the approximation aims to reduce cost, the exact KL-divergence calculation for feature selection can still be computationally intensive.
- Further Experiments: The authors suggest that additional experiments are certainly required to fully validate the effectiveness of their proposed scores, especially across a wider range of datasets and class distributions.
- Simultaneous Computation: The paper notes that the exact KL-divergence score cannot be computed simultaneously with the Naive Bayes model parameters in a single pass over the data, which is a practical consideration.
Summary updated