A New Perspective for Information Theoretic Feature Selection

Gavin BrownAISTATS 2009

Abstract

Information-theoretic feature selection has long been characterized by a diverse array of heuristic criteria. This paper introduces a unifying theoretical framework that analytically expands Shannon’s Mutual Information into a sum of multivariate interactions. By truncating this expansion to pairwise terms, we derive a two-parameter $(\beta, \gamma)$ space that encompasses dozens of existing criteria, such as mRMR, MIFS, and JMI, as specific instances. This perspective allows for a principled comparison of algorithms and reveals the critical role of conditional redundancy in handling feature synergies.

Introduction

In machine learning, feature selection is the process of identifying the most relevant variables within a dataset to enhance model performance and interpretability. "Filter" methods are particularly popular due to their computational efficiency and model-agnostic nature, typically leveraging Mutual Information (MI) to rank features. However, the field has historically been saturated with a "confusing flurry" of heuristic criteria, each manually designed to balance relevance against redundancy without a clear theoretical link between them. This work addresses this fragmentation by proposing a single theoretical framework that unifies these disparate approaches.

Methods: The $\beta$-$\gamma$ Framework

Rather than constructing heuristics from the bottom up, this paper adopts a top-down analytical approach based on the expansion of multivariate mutual information. By utilizing Interaction Information, the total mutual information between a feature set and a target label is decomposed into a sum of interactions of varying orders (pairs, triples, etc.).

Due to the computational complexity of high-order interactions, the expansion is truncated to include only pairwise terms. This results in a generalized criterion parameterized by two variables:

  • $\beta$ (Redundancy): Penalizes features highly correlated with those already selected.
  • $\gamma$ (Conditional Redundancy): Rewards features that provide synergistic information when combined with existing selections.
The $\beta$-$\gamma$ unit square mapping various information-theoretic feature selection criteria.

As shown in Figure 1, existing algorithms like MIFS, mRMR, and JMI can be mapped as specific coordinates within this continuous $(\beta, \gamma)$ unit square. This mapping reveals that feature selection exists on a spectrum, allowing practitioners to move between "aggressive" and "conservative" criteria based on data characteristics.

Results and Key Insights

The framework was evaluated using synthetic challenges like the Noisy Multiplexer—a boolean problem with strong interdependencies—and real-world high-dimensional gene expression datasets (Lung and SRBCT).

Handling Feature Synergy

A significant insight is the importance of the $\gamma$ term. Early criteria like mRMR primarily focused on penalizing redundancy ($\beta$). However, results on the Multiplexer problem demonstrate that criteria incorporating conditional redundancy (like JMI and the proposed FOU) significantly outperform those that ignore it. These synergistic features may appear useless in isolation but become powerful when paired.

Comparison of test error across different feature selection criteria as the number of features increases.

Overfitting and Dataset Specificity

The study also highlights that feature selection criteria can overfit. While complex criteria using both $\beta$ and $\gamma$ excel on large datasets, they may struggle on small-sample datasets (like gene expression data) due to the difficulty of accurately estimating multiple correlation terms. Exploration of the $(\beta, \gamma)$ space revealed that the "optimal" criterion is often dataset-specific, with some datasets favoring points that do not correspond to any previously published heuristic.

Conclusion

By retrofitting 12 different criteria into a single mathematical framework, this work provides a "Grand Unified Theory" for information-theoretic feature selection. The transition from discrete heuristics to a continuous parameter space paves the way for "data-driven feature selection," where $\beta$ and $\gamma$ can be optimized for specific tasks rather than selected from a static list of named algorithms. Future work will look to extend this framework beyond pairwise interactions to capture higher-order synergies.

Summary updated

BibTeX
@article{brown2009new,
  author = {Gavin Brown},
  title = {{A New Perspective for Information Theoretic Feature Selection}},
  journal = {AISTATS},
  year = {2009},
}
Figure