Greedy Sequential Feature Selection for High Dimensional Data

You are reading version 1 of this direction, frozen 2026-10-04. The latest version is version 2.

Version 1 of 2351 papers380 conceptsfrozen 2026-10-04

In modern machine learning, we are often drowning in data but starving for information. Whether we are looking at thousands of gene expressions in a microarray, millions of pixels in a medical scan, or hundreds of potential sensors on a wearable device, we face the "curse of dimensionality."

The goal of feature selection is to find the smallest subset of inputs that preserves—or even improves—a model's predictive power. While the "gold standard" is Best Subset Selection (evaluating every possible combination), this is a combinatorial nightmare. For $p$ features, there are $2^p$ possible subsets. If $p=100$, there are more subsets than there are atoms in the observable universe.

Greedy sequential selection provides a way to bypass this wall by making locally optimal choices at each step.

The Intuition of Marginal Utility

The core logic of greedy selection is simple: start small and grow only when necessary.

In Sequential Forward Selection (SFS), we begin with an empty set. We test every individual feature and pick the one that performs best. Then, we look at the remaining features and ask: "Which single addition, when combined with what I already have, provides the greatest boost?"

This "marginal utility" approach is powerful because it captures dependencies. A feature might be useless on its own but revolutionary when paired with another. For example, Steven McDonagh and colleagues found that adding 3D topographical data to 2D images improved skin lesion classification by 6% in Using 3D information for classification of non-melanoma skin lesions. The 3D data wasn't just "more data"; it provided a specific structural context that the 2D data lacked.

Similarly, Hirotaka Hachiya and Masashi Sugiyama demonstrated in Feature Selection for Reinforcement Learning that by using Conditional Mutual Information (CMI), a greedy algorithm can identify state variables that don't yield immediate rewards but are essential for long-term strategy.

Managing the Search Space

To make this process efficient, researchers use different "wrappers" and "filters" to evaluate features:

  1. The Wrapper Approach: This treats the underlying model (like an SVM or k-NN) as a black box. Rowena Chin used this to identify schizophrenia from MRI scans with 90% accuracy in Recognition of Schizophrenia with Regularized Support Vector Machine, iteratively adding brain regions that maximized the SVM's performance.
  2. The Analytical Shortcut: Some models allow us to calculate the impact of adding a feature without retraining the whole system. E. K. Tang and Ke Tang developed a method for Least Squares SVMs that uses a mathematical shortcut to estimate "leave-one-out" error, making gene selection in high-dimensional microarrays computationally feasible in Gene selection algorithms for microarray data.
  3. Sequential Forward-Backward Selection: Sometimes a feature that was useful in Step 2 becomes redundant by Step 10. Mohammad Sadeghi and colleagues addressed this in Colour Feature Selection for Face Authentication by allowing the algorithm to "reconsider" and remove previously selected features if they no longer contribute to the group's performance.

Scaling to Big Data

When the number of features reaches the millions—common in astronomy or genomics—even a simple greedy search can be slow.

Fabian Gieseke and Christian Igel tackled this in Speedy greedy feature selection by offloading the evaluation of feature subsets to GPUs. By parallelizing the cross-validation steps, they achieved a 100x speedup, making it possible to estimate the distance of millions of galaxies in minutes.

Another strategy is the Active Set or Adaptive Sieving method. Instead of looking at all features, the algorithm maintains a small "active" pool. Shaogang Ren and Ping Li showed in Best Subset Selection with Efficient Primal-Dual Algorithm that by dynamically updating this set based on screening criteria, one can achieve the statistical accuracy of $\ell_0$ regularization (the "gold standard") with the speed of much simpler methods.

Interpretability as a First-Class Citizen

Beyond performance, greedy selection is often used to make "black box" models explainable. If a model uses 1,000 features, a human cannot understand its logic. If it uses seven, they can.

In Valid Explanations for Learning to Rank Models, Jaspreet Singh and Avishek Anand used a greedy set coverage approach to find the minimal set of features that explain why a search engine ranked one item over another. Similarly, Louenas Bounia and Frédéric Koriche demonstrated in Approximating probabilistic explanations via supermodular minimization that greedy descent/ascent strategies can find near-optimal, human-readable explanations in high-dimensional spaces where exact solvers fail.

This trend has even reached Large Language Models. The BLINDER framework, described in Selective Perception: Learning Concise State Descriptions for Language Model Actors, uses an iterative selection process to strip away 99% of the "noise" in a text description. By feeding the LLM only the most critical features, the researchers not only saved on computation but actually made the AI more successful at its tasks.

Papers in this version

Showing 60 of 351 papers.

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 1, frozen text):

@misc{lacuna_greedy_sequential_feature_selection_for__19657254_v1,
  title = {Greedy Sequential Feature Selection for High Dimensional Data},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/greedy-sequential-feature-selection-for-high-dimensional-data/rdr_196572549902429cbb8056ffba23f640/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}