Source-linked AI summary
A Review of Feature Selection Methods Based on Mutual Information
Jorge R. Vergara, Pablo A. Estévez
TL;DR
Feature selection requires selecting compact, informative subsets while addressing relevance, redundancy, complementarity, and computational constraints. The paper reviews mutual-information filtering, defines the associated concepts and optimal-selection problem, and develops a unified framework for interpreting heuristic criteria. The review concludes that context-sensitive methods must include complementarity and that the framework exposes each method's approximations and limitations.
Problem
Feature selection must identify compact subsets with acceptable generalization while accounting for relevance, redundancy, complementarity, and high-dimensional search limitations.
Method
The paper reviews information-theoretic filter methods and develops a unified framework connecting heuristic criteria to maximal dependency, conditional mutual information, and search strategies.
Results
The framework explains successful heuristic criteria and identifies the approximations, advantages, and limitations associated with different mutual-information feature-selection methods.
Takeaways & Limitations
Effective modern feature selection must assess features in context and include complementarity alongside relevance and redundancy.
Takeaways & Limitations
The review is limited by assumptions and approximations that can introduce errors, including independence assumptions in sequential selection and backward elimination.
Abstract
from arXiv · showhide
In this work we present a review of the state of the art of information theoretic feature selection methods. The concepts of feature relevance, redundance and complementarity (synergy) are clearly defined, as well as Markov blanket. The problem of optimal feature selection is defined. A unifying theoretical framework is described, which can retrofit successful heuristic criteria, indicating the approximations made by each method. A number of open problems in the field are presented.
1 Introduction
The introduction frames feature selection as finding a compact subset that controls generalization error, while reviewing mutual-information filters through a unified framework. It also situates the review within the computational trade-offs among wrapper, embedded, and filter methods.
- Feature selection seeks the smallest subset achieving a specified generalization error or the best subset of k features.
- Additional objectives include better generalization, robustness and speed on unseen data, and simpler understanding of the data-generating process.
- Wrapper methods evaluate subsets with the learning algorithm but can become prohibitively expensive on high-dimensional datasets.
- The paper reviews mutual-information filter methods, traces their evolution, and unifies their advantages, drawbacks, and approximations.
2 Background on MI
The background establishes discrete-variable notation and introduces entropy, mutual information, conditional mutual information, and multi-information as tools for characterizing uncertainty and feature interactions. Examples show that joint information can reveal complementarity even when individual features are irrelevant, while multi-information distinguishes complementary, redundant, and noninteracting feature pairs.
- 2.1 Notation: The paper assumes discrete random variables, with uppercase symbols denoting variable sets and lowercase symbols denoting individual variables.
- 2.2.1 Entropy: Entropy measures uncertainty, while conditional entropy measures the uncertainty remaining in one variable after another is known.
- 2.2.2 Mutual Information: Mutual information measures information shared by variables and quantifies a feature subset's relevance to the output vector C.
- 2.2.2 Mutual Information: Conditional mutual information measures the information between two variables in the context of a third, whereas multi-information measures interaction among more than two variables.
- 2.2.2 Mutual Information: When individual relevance is zero but joint information is positive, features x2 and x3 interact positively to predict C.
- 2.2.2 Mutual Information: Negative multi-information indicates redundancy, while zero multi-information indicates that the feature interaction provides no new information about C.
3 Relevance, Redundancy and Complementarity
The section distinguishes relevance, redundancy, and complementarity as information-theoretic bases for selecting compact feature subsets. It also introduces Markov blankets as a formal redundancy concept and explains limits of relevance criteria and complementarity analysis.
- Feature selection seeks a minimum-cardinality subset preserving information about the class variable C.
- Relevance: Strongly relevant features provide unique information about C, whereas weakly relevant features provide information that may be replaceable by other features.
- Relevance: Relevance definitions face dimensionality and selection problems because testing irrelevance can require evaluating all subsets, while strong relevance may discard redundant informative features.
- Redundancy: Weak relevance alone cannot determine whether a feature belongs in the optimal subset, motivating distinctions between redundant and non-redundant weakly relevant features.
- Markov blankets: A Markov blanket M of feature fi subsumes all information fi provides about C and the remaining features, under the stated conditional-independence condition.
- Complementarity: Complementarity, or synergy, is measured by I(fi; S|C), while multi-information indicates whether complementarity or redundancy dominates their interaction.
4 Optimal Feature Subset
The section reviews competing definitions of an optimal feature subset and the search strategies used to obtain it. It contrasts distribution-based filter criteria with classifier-based objectives and emphasizes computational limits and modeling caveats.
- Definitions: An optimal subset maximizes a performance metric subject to minimum cardinality, whereas filter methods define relevance from the data distribution without a learning machine or performance metric.
- Definitions: A sufficient feature subset makes C conditionally independent of the excluded features, so the excluded variables add no information given the selected subset.
- Optimization: The feature-selection objective can be expressed as finding the smallest subset that maximizes I(S; C), but discrete cardinality makes optimization difficult.
- Markov blankets: Markov blankets provide an alternative elimination basis, but exact induction grows exponentially with blanket size and heuristic approximations may miss multivariate associations such as XOR.
- Caveats: Sufficient-subset and Markov-blanket approaches depend on estimating posterior probabilities, which is harder than classification under a 0/1-loss objective.
- Search strategies: Exhaustive and other optimal searches are impractical in high dimensions, so sub-optimal strategies such as sequential forward selection and backward elimination are used.
5 A Unified Framework for Mutual Information Feature Selection
The framework formulates mutual-information feature selection through conditional mutual information or maximal dependency, connecting sequential searches and common heuristic criteria. It also exposes the approximations, computational difficulties, and modeling assumptions behind these methods.
- Heuristic criteria: Low-order approximations of the framework recover MIFS, CIFE, mRMR, JMI, and CMIFS, while some nonlinear criteria require different treatment.The framework identifies these criteria as approximations, but initially does not derive min- or max-based CMIM, Informative Fragments, and ICAP.
- Unified objective: Mutual-information feature selection can be framed as maximizing I(S; C) or minimizing I(¬S; C|S), because I(F; C) is constant.These are the maximal dependency and conditional-mutual-information perspectives.
- Sequential search: Sequential forward selection and backward elimination are derived in parallel under maximal dependency and conditional mutual information.Forward selection adds a candidate using I(fi; C|St), while backward elimination evaluates I(fi; C|St\fi).
- Information terms: Expanding conditional mutual information separates candidate relevance, redundancy with selected features, and complementarity in the target context.The expansion is difficult to estimate in high-dimensional spaces because selected-feature sets appear in multiple terms.
- Approximations and limitations: Approximations that omit complement-feature terms assume independence and can introduce errors during sequential selection or backward elimination.ICAP additionally penalizes redundant interactions but neglects complementarity when the interaction is positive; CMIM neglects multi-information terms.
- Heuristic criteria: CMIM detects complementary relevant-feature pairs, while CMIM-2 exactly retains the first term of the expanded criterion and generally outperformed CMIM in reported artificial and benchmark experiments.The comparison is reported for experiments using artificial and benchmark datasets.
6 Open Problems
The review identifies open problems in making information-theoretic feature selection more unified, scalable, and broadly grounded in dependence measures. It emphasizes high-dimensional computation, stronger theoretical links, and dependence measures beyond correlation and mutual information.
- Framework development: The unifying framework should derive efficient criteria that include relevance, redundancy, and complementarity, while connecting more strongly to Markov blankets.Hybrid methods combining maximal dependency with minimal conditional mutual information are also proposed.
- High-dimensional scalability: Feature selection must become faster and mutual-information estimation more efficient for settings with millions of features and billions of samples.The review links this challenge to search strategy and evaluation-criterion computational costs.
- Dependence measurement: Dependence measures beyond correlation and mutual information remain an open problem, including normalization across different kinds of random variables.The review notes that no standard theory of mutual-information normalization exists.
7 Conclusions
The review concludes that information-theoretic feature selection must account for relevance, redundancy, and complementarity, with features assessed in context. Its unified framework relates successful heuristics to explicit approximations and limitations, while motivating further work.
- Conclusions: Feature selection methods should go beyond relevance and redundancy to include complementarity, or synergy, when assessing features in context.The conclusion presents contextual assessment as necessary for new feature-selection methods.
- Conclusions: The unified theoretical framework retrofits successful heuristic criteria and identifies the approximations and limitations associated with each method.The review also reports new results and derivations extending the framework.
- Conclusions: The paper ends by presenting open problems as challenges for future information-theoretic feature-selection research.