TL;DR
This paper introduces a novel, highly efficient feature selection algorithm called CMIM that leverages conditional mutual information to select features that are both individually informative and weakly dependent on each other. CMIM significantly outperforms existing methods in terms of speed and achieves competitive classification accuracy, making it a powerful tool for high-dimensional datasets.
What Problem Does This Paper Address?
In machine learning, especially with high-dimensional data, selecting a relevant subset of features is crucial. This process, known as feature selection, helps to reduce overfitting, improve model interpretability, and speed up computation. Traditional methods often fall into two categories: "filters" that are classifier-agnostic but may select redundant features, and "wrappers" that are highly dependent on a specific classifier and can be computationally expensive. The challenge is to find a feature selection method that is both statistically sound (capturing predictive power and avoiding redundancy) and computationally efficient, especially when dealing with tens of thousands of features.
Methods
The core of this paper is the Conditional Mutual Information Maximization (CMIM) criterion. CMIM iteratively selects features by maximizing their mutual information with the class label, conditional on the features already selected. This approach ensures that each newly selected feature adds new information about the class that hasn't been captured by previously chosen features, thus promoting both discriminative power and feature independence.
The paper also proposes a fast implementation of CMIM that significantly reduces computation time. This is achieved through a "lazy evaluation" strategy, where the computation of conditional mutual information is optimized by avoiding unnecessary calculations for features that are unlikely to be selected. This optimization is crucial for handling the massive number of features.
Datasets
The paper evaluates CMIM on two main datasets:
- Image Classification: A face vs. background recognition task using small grayscale patches. The dataset was constructed from a large collection of scenes, resulting in 14,268 faces and 14,800 background images for training (and corresponding smaller sets for testing). The features used are binary "edge features" derived from edge detectors, totaling 43,904 features.
- Molecular Bio-activity Prediction: A drug-design task predicting the bio-activity of compounds. This dataset contains 1,909 compounds with a binary class (active/inactive) and initially 139,351 binary features. For computational feasibility, the number of features was reduced to 2,500 through random sampling.
Key Insights and Ideas
- Conditional Mutual Information as a Dual Criterion: CMIM elegantly balances two crucial aspects of feature selection: individual predictive power and pairwise independence. By conditioning on already selected features, it avoids selecting redundant features that offer little new information.
- Computational Efficiency is Key: The paper highlights that even statistically sound methods are impractical if they are too slow. The proposed fast implementation of CMIM is a significant contribution, enabling its use on datasets with tens of thousands of features.
- Naive Bayes as a Strong Baseline: The paper demonstrates that a simple Naive Bayes classifier, when combined with CMIM-selected features, can achieve performance comparable to more complex state-of-the-art methods like SVMs and AdaBoost. This suggests that effective feature selection can compensate for simpler classifiers.
- Robustness to Noise: CMIM shows robustness to noisy training data, outperforming other methods in scenarios with mislabeled examples.
Key Results
- Speed: The fast CMIM implementation achieved a speedup of 73x for the image classification task (selecting 50 out of 43,904 features) and 110x for the thrombin dataset (selecting 10 out of 139,351 features) compared to the naive implementation.
- Classification Accuracy: For the image classification task, CMIM combined with SVM achieved the lowest error rates, closely followed by AdaBoost with SVM. CMIM with Naive Bayes also performed very well, ranking fourth. In general, CMIM as a feature selection method consistently ranked among the best for various classifiers.
- Noisy Data Performance: In experiments with 5% of training labels flipped, CMIM remained a top-performing feature selection method, demonstrating its resilience to outliers.
- Thrombin Dataset: CMIM with Naive Bayes achieved the lowest error rate on the thrombin dataset, outperforming SVM in most cases.
Limitations and Future Work
- Sub-population Dominance: The paper acknowledges that CMIM might struggle in situations where the positive population is a mixture of distinct sub-populations, and one sub-population statistically dominates. In such cases, CMIM might overlook features informative about the minority sub-population. The authors suggest that weighting challenging examples could address this.
- Multi-class and Continuous Features: The paper discusses extensions to multi-class problems and continuous-valued features as areas for future work. These extensions are noted to increase computational cost and data requirements.
- Regression: Extending CMIM to regression tasks is also mentioned as an area of ongoing research.
Summary updated