Greedy Incremental Feature Selection

254 concepts235 papers1 proposal

When building machine learning models, we often face an overwhelming number of potential input features. To maximize accuracy and avoid overfitting, we want to find the smallest, most informative subset of these features.

The naive approach is an exhaustive search: evaluate every possible combination of features to find the absolute best performer. However, if a dataset contains $d$ features, there are $2^d$ possible subsets. As $d$ grows, this combinatorial explosion quickly makes exhaustive evaluation computationally impossible.

Greedy incremental feature selection solves this bottleneck by replacing a global, exponential search with a sequence of local, polynomial choices. Instead of evaluating entire subsets simultaneously, the algorithm starts with an empty set and builds the optimal subset one feature at a time.


The Mechanics of Marginal Gain

The core intuition behind greedy forward selection is that we do not need to know the perfect final combination to make immediate progress. Instead, we can make a series of locally optimal decisions by evaluating the marginal utility of each remaining feature.

[Empty Set] 
   │
   ├── + Feature A (Gives +5% accuracy)  <-- Max Marginal Gain
   ├── + Feature B (Gives +2% accuracy)
   └── + Feature C (Gives +1% accuracy)
   │
[Selected: {A}]
   │
   ├── + Feature B (Gives +3% accuracy)  <-- Max Marginal Gain
   └── + Feature C (Gives +0.5% accuracy)
   │
[Selected: {A, B}] ... (Repeat until stopping criterion met)

As Howard Hua Yang et al. demonstrate in Data Visualization and Feature Selection: New Algorithms for Nongaussian Data, this iterative process scales down the computational complexity from exponential ($2^d$) to polynomial ($O(d^2)$ or $O(k \cdot d)$, where $k$ is the number of selected features).

To execute this search, the algorithm requires an objective function to measure the value of adding a feature. In Instance Based Learning with Automatic Feature Selection Applied to Word Sense Disambiguation, Rada Mihalcea utilizes cross-validation accuracy directly as the objective function. The algorithm evaluates every unselected feature by adding it to the current subset, running cross-validation, and permanently keeping the single feature that yields the highest performance boost. The process repeats, building the subset step-by-step, until no further statistical improvement is observed.


Defeating Redundancy and Diminishing Returns

A major flaw of simple "one-shot" feature ranking methods—where features are evaluated independently and the top $k$ are chosen—is that they ignore feature interactions. If two features are highly correlated (for example, a house's square footage in square feet versus square meters), a one-shot ranker will select both because they are individually highly predictive. This introduces redundant noise into the model.

Greedy incremental selection naturally avoids this pitfall because it evaluates features conditionally based on the current state of the selection pool.

Consider an information-theoretic framework like the one explored by Dekai Wu et al. in An Information-Theoretic Empirical Analysis of Dependency-Based Feature Types for Word Prediction Models. By ranking and adding features based on their incremental information gain rather than their absolute information content, the system accounts for diminishing returns. Once the first highly predictive feature is added to the subset, the marginal information gain of any redundant feature drops to near zero. The algorithm will bypass the redundant feature in favor of a weaker, but complementary, feature that provides entirely new information.

Similarly, Stefan Riezler et al. leverage this property in Incremental Feature Selection and l1 Regularization for Relaxed Maximum-Entropy Modeling. By starting with an empty set and iteratively incorporating features that provide the greatest improvement to the model's objective function, the authors demonstrate that models can achieve state-of-the-art accuracy with significantly fewer features, bypassing the need to optimize over a massive, high-dimensional space all at once.


Modern Extensions: Attribution and Leakage Prevention

The utility of greedy incremental selection extends beyond traditional model training and into model interpretability and feature attribution.

Deep neural networks are notoriously difficult to interpret because their internal features are highly entangled. To explain a model's prediction, we need to know which input features truly drove the decision. Kyriakos Axiotis et al. address this in Greedy PIG: Adaptive Integrated Gradients by framing feature attribution as an iterative subset selection problem. By selecting features in sequential rounds and dynamically updating the model's internal state, their method successfully maps out feature importance while accounting for complex dependencies and redundancies that one-shot attribution methods miss.

[Hidden Inputs] ──> [Sequential Unmasking (SUWR)] ──> [Visible Inputs Only]
                           │
                           └─── Decision to unmask next feature 
                                relies *only* on what is already visible 
                                (Zero Leakage of Hidden Labels)

Furthermore, this sequential framework can be used to guarantee the integrity of explanations. A common issue in local feature selection is "leakage," where the selection process accidentally encodes hidden information about the target label or unselected features into the final explanation.

To solve this, Harrie Oosterhuis et al. developed the Sequential Unmasking Without Reversion (SUWR) framework in Local Feature Selection without Label or Feature Leakage for Interpretable Machine Learning Predictions. By revealing features one by one, where each step's decision is strictly constrained to the information already made visible, the authors mathematically eliminate leakage. The greedy, forward-only nature of the selection ensures that the final mask cannot act as a covert communication channel for hidden data.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 233 papers
  2. Version 1 · 2026-10-04 · 351 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_greedy_feature_selection_19657254,
  title = {greedy feature selection},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/greedy-feature-selection/rdr_196572549902429cbb8056ffba23f640},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 2, frozen text):

@misc{lacuna_greedy_feature_selection_19657254_v2,
  title = {greedy feature selection},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/greedy-feature-selection/rdr_196572549902429cbb8056ffba23f640/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake