Bayes Optimal Feature Selection for Supervised Learning with General Performance Measures

C. G. Saneem Ahmed, Harikrishna Narasimhan, Shivani AgarwalUAI 2015 · OpenReview

Introduction

In modern machine learning, the challenge often lies not in a lack of data, but in its overwhelming volume. Feature selection—the process of identifying a small, highly relevant subset of variables—is a critical step in building models that are computationally efficient, interpretable, and robust against overfitting.

Traditionally, feature selection has been dominated by "filter methods." These methods are favored for their speed, as they rank features using generic statistical proxies like Mutual Information (MI) without needing to train a full predictive model. However, a significant drawback exists: a feature set that maximizes mutual information may not be the one that optimizes the specific performance metric of interest, such as 0-1 accuracy, F-measure, or Area Under the ROC Curve (AUC).

The Gap in Generic Filter Methods

The fundamental issue addressed by Ahmed, Narasimhan, and Agarwal in their paper is the disconnect between information-theoretic relevance and task-specific performance. While MI measures how much information a feature provides about a label, it ignores how that information is utilized by the final classifier. The authors demonstrate that even in simple binary classification tasks, MI can lead to the selection of features that result in higher error rates compared to alternative, "less informative" sets. Essentially, MI is a "one-size-fits-all" metric that often fails to align with the ultimate goal of the learning task.

A Bayes Optimal Approach

To bridge this gap, the authors propose a "Bayes optimal" filter method. This approach selects features by directly minimizing the Bayes error—the theoretical minimum error achievable by any classifier for a given distribution and performance measure.

Key Methodological Contributions:

  1. Task-Specific Criterion: Instead of maximizing a generic proxy, the method maximizes a criterion derived from the negative Bayes error for a specific loss function $\ell$.
  2. Unifying Framework: The researchers provide a theoretical bridge, showing that the standard MI criterion is actually a special case of their framework, corresponding to the minimization of logarithmic loss for probability estimation.
  3. The $\ell$-BayesGreedy Algorithm: Since finding the optimal feature subset is an NP-hard problem, the authors implement a greedy forward selection algorithm. It iteratively adds features that offer the greatest improvement to the estimated Bayes performance.
  4. Bivariate Approximation: To mitigate the "curse of dimensionality" when estimating probabilities from finite data, the algorithm uses a bivariate approximation for large feature sets, focusing on feature pairs rather than the entire high-dimensional space.

Experimental Evaluation

The proposed method was rigorously tested on nine diverse datasets from the UCI and ASU repositories, covering both binary and integer/real features. These datasets ranged in size from 40 to nearly 140,000 features, providing a comprehensive evaluation of scalability and performance.

Standard Classification Results

In standard classification tasks (minimizing 0-1 error), the 0-1-BayesGreedy method consistently matched or outperformed state-of-the-art baselines like mRMR (minimal-redundancy-maximal-relevance) and MIGreedy across various datasets.

Test 0-1 error across eight diverse datasets. The 0-1-BayesGreedy method (dashed green) frequently achieves lower error rates with fewer features than traditional MI-based approaches.

As shown in the figure above, the Bayes-optimal approach often reaches its minimum error with a smaller number of features compared to MI-based methods, demonstrating its efficiency in identifying the most task-relevant information.

Cost-Sensitive Learning

The advantage of the Bayes-optimal approach is even more pronounced in cost-sensitive scenarios, where the penalties for false positives and false negatives differ. By tailoring the selection criterion to the specific cost-sensitive loss (e.g., $c=0.25$), the c-BayesGreedy variant identifies features that are fundamentally better suited for the final model's requirements.

Cost-sensitive test error (c=0.25) on the Mushroom dataset. The c-BayesGreedy method shows a clear advantage in achieving lower error with very small feature subsets.

Computational Efficiency

Beyond accuracy, the BayesGreedy method offers significant speed advantages. For 0-1 loss, the criterion involves simple "max" operations on probabilities, which are computationally cheaper than the complex logarithmic entropy calculations required for MI. On the Gisette dataset, for instance, BayesGreedy was more than twice as fast as MIGreedy (8,475 seconds vs. 18,000+ seconds).

Conclusion and Future Directions

The work of Ahmed et al. makes a compelling case for "performance-aware" feature selection. By moving beyond generic information theory and focusing on the Bayes error of the specific task, machine learning practitioners can build more accurate and efficient pipelines.

While the method is powerful, its success depends on accurate probability estimation, which remains a challenge in extremely high-dimensional, sparse settings. Future research could explore theoretical approximation guarantees using submodular optimization or extend the empirical evaluation to more complex multiclass problems. Nonetheless, this Bayes optimal framework represents a significant step forward in aligning feature selection with the ultimate goals of supervised learning.

Summary updated

BibTeX
@inproceedings{ahmed2015bayes,
  author = {C. G. Saneem Ahmed and Harikrishna Narasimhan and Shivani Agarwal},
  title = {{Bayes Optimal Feature Selection for Supervised Learning with General Performance Measures}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2015},
  url = {https://openreview.net/forum?id=a4quiPnP-Ze},
}
Figure