Feature Selection (FS)

Definition

Feature selection is deciding which of your input columns to keep and which to discard, and then discarding them. What comes out is a subset of the columns you started with — age, days_since_signup, postcode — still carrying their original names and units. That is the whole difference between it and dimensionality reduction, which builds new coordinates out of weighted combinations of every column at once: reduction usually preserves more information per dimension, but nobody can tell a customer what "component 3" was. Select when a human has to name the reasons; reduce when only another algorithm will ever read the output.

One number governs every practical method: a table with n columns has 2ⁿ possible subsets. Twenty columns gives 1,048,576 candidate subsets; forty gives 1,099,511,627,776. At an optimistic one millisecond per model fit, evaluating all of them takes 17 minutes at twenty columns and 35 years at forty. Exhaustive search is not something anyone does, and optimal subset selection is NP-hard in general — so every technique below is a heuristic that gives up part of the search space in exchange for finishing.

And here is what breaks if you get it wrong. Score your features on the whole dataset, keep the top ones, then cross-validate, and the resulting accuracy is fiction. On 100 samples of pure Gaussian noise with 10,000 meaningless features and coin-flip labels, that procedure reports 8.2% error — apparent 92% accuracy on data containing no signal whatsoever. Do the selection inside each fold instead and the same code reports 47.9%, which is the truth. Both figures come from the code example at the end of this page, which you can run in about twenty seconds.

How It Works

Any feature-selection method is three decisions in a trench coat: a score that says how good a feature or a set of features is, a search that decides which candidates get scored, and a stopping rule that says when to quit. Most of the differences between named techniques are differences in one of those three.

Scoring one feature at a time

The cheapest score asks how much knowing a feature reduces your uncertainty about the label — the mutual information, which for classification is the same quantity as information gain. Take 1,000 emails, exactly 500 of them spam, so the label alone carries 1 bit of uncertainty. Now consider a candidate feature: does the message contain the phrase wire transfer?

Among the 400 messages that contain it, 75% are spam, and a 75/25 split carries 0.811 bits of uncertainty. Among the 600 that do not, the split is 1/3 to 2/3, worth 0.918 bits. Weighting those by how often each case occurs gives 0.4 × 0.811 + 0.6 × 0.918 = 0.875 bits of uncertainty remaining, so the feature bought you 1 − 0.875 = 0.125 bits. Run the same arithmetic on a word that appears in 450 spam and 440 ham messages and it buys 0.0007 bits — three orders of magnitude less, and in practice indistinguishable from zero. That gap is the entire content of a filter method: compute one such number per column, sort, keep the top k.

Searching over subsets

Scoring features one at a time is cheap because it dodges the 2ⁿ problem entirely. The moment you want to score combinations, you need a search, and the standard one is greedy. Forward selection starts from nothing, tries adding each remaining feature, keeps whichever helps most, and repeats; backward elimination starts from everything and removes the least useful. Either way the cost of ranking all n features is n + (n−1) + … + 1 = n(n+1)/2 model fits: 210 fits at twenty columns instead of 1,048,576, and 820 instead of 1.1 trillion at forty. That is the trade the whole field is built on — greedy search is roughly quadratic where exhaustive search is exponential, and it buys that by never reconsidering a decision, so it can and does miss subsets that only work as a group.

The floor set by multiple comparisons

Filter methods have a failure mode that has nothing to do with your data and everything to do with counting. Test 10,000 features for association with the label at the conventional α = 0.05 and you expect 500 features to pass by chance alone, even if not one of them is related to anything. The same arithmetic in correlation terms: the correlation between a random feature and a random binary label over n samples has a standard deviation of about 1/√(n−1), which is 0.101 at n = 100, and the largest of p such draws lands near √(2 ln p) standard deviations out — about 0.43 for p = 10,000. Simulating it, the largest absolute correlation among 10,000 pure-noise features averages 0.385 across twenty random datasets. A correlation of 0.39 looks like a finding. It is the expected maximum of noise.

The defences are ordinary multiple-testing corrections: Bonferroni divides the threshold by the number of tests (0.05 / 10,000 = 5 × 10⁻⁶, which is severe), while the Benjamini–Hochberg procedure controls the false discovery rate instead and is what genomics actually uses.

Selecting outside the cross-validation loop

This is the most consequential mistake in the topic and it survives code review constantly, because the offending line looks innocent: rank the features on X, y, keep the top 20, then hand the reduced matrix to cross_val_score. The reduced matrix was built using the labels of every fold, including the ones being held out. The selector has seen the test set.

Ambroise and McLachlan measured exactly how bad this is in PNAS in 2002, on colon-cancer microarray data — 62 tissue samples, 2,000 genes. They randomly permuted the class labels, destroying any real relationship, then ran support-vector recursive feature elimination and scored it with an internal leave-one-out cross-validation. On this no-information data the rule achieved an average apparent error of zero and an internal cross-validated error close to zero at 128 selected genes, and about 10% at only eight genes. The same data scored with an external cross-validation, where gene selection is redone inside each fold, gave 0.40 to 0.45 — which is what a coin flip should look like. On the real, unpermuted colon data the gap was equally decisive: a forward-selected Fisher rule reported 6.5% error with three genes internally, and about 15% once the selection was moved inside the loop.

The mechanism is the one from the previous section. With 2,000 candidate genes and 62 samples, some genes correlate with the labels by luck; picking the luckiest ones using all the data and then "validating" on a subset of that same data measures how well luck reproduces itself. The fix is a single sentence long: the selector is part of the model, so it belongs inside the cross-validation loop and must be refitted on every training fold. Ambroise and McLachlan also recommend 10-fold cross-validation over leave-one-out here, because leave-one-out is nearly unbiased but so variable that it is unreliable on samples this small.

There is a second, quieter consequence. Because the winning subset is partly luck, it is not stable: the authors note that redoing selection inside each fold generally yields a subset with "at most only a few genes in common" with the one chosen on the full data. If your selected feature list changes completely when you drop 10% of the rows, that list is not a finding.

Types

The three families are a real taxonomy that practitioners use by name, and the axis they vary along is a single trade: how much does scoring a candidate cost, and how closely does that score resemble the model you will actually ship? Those two move in opposite directions.

Filter methods — variance thresholds, correlation, chi-squared, mutual information, ANOVA F-tests — score each column independently and never build the downstream model. That independence is what makes them fast and what makes them blind. The clean demonstration is XOR: let two binary features be independent coin flips and let the label be their exclusive-or. Knowing feature 1 alone tells you nothing at all — the label is still 50/50 — so its mutual information with the label is exactly 0, and the same for feature 2. Together they determine the label perfectly. Every univariate filter ranks both features dead last and discards them. Use filters as a first pass to get from 20,000 columns to 500, not as the final word.

Wrapper methods fit the model you actually intend to use and judge a subset by its cross-validated score. Recursive feature elimination is the common one: train, rank the features by the model's own coefficients or importances, drop the worst slice, retrain, repeat. Because the score comes from the real model, interactions are visible and the answer is tailored to that model — change from logistic regression to gradient boosting and you should expect a different subset. Because every candidate costs a full fit, wrappers are what you reach for after a filter has already cut the problem down.

Embedded methods perform selection as a side effect of training. L1 regularization — the LASSO — penalises the sum of absolute coefficient values, and the geometry of that penalty drives coefficients exactly to zero rather than merely shrinking them, so the fit is the selection. Two limits are worth knowing before you rely on it: when p > n the LASSO can select at most n features before it saturates, and among a group of strongly correlated predictors it picks one more or less arbitrarily and zeroes the rest (Zou and Hastie, 2005 — the elastic net exists to fix both). Tree ensembles such as random forests and gradient boosting supply impurity or permutation importances for free, with the same correlated-feature caveat: the credit for a shared signal gets split between the columns that carry it, so each looks half as important as it is.

Real-World Applications

MammaPrint, and why a diagnostic has to be short. Van 't Veer and colleagues (Nature, 2002) profiled breast tumours on microarrays carrying about 25,000 genes, filtered down to roughly 5,000 that varied meaningfully across samples, found 231 correlated with metastasis within five years, and kept the 70 with the highest absolute correlation. That 70-gene signature became MammaPrint, FDA-cleared in 2007 and used in the MINDACT trial to identify patients who can safely skip chemotherapy. The reduction from 25,000 to 70 is not a compute optimisation — it is what makes a manufacturable assay and a clinically defensible decision possible. It is also the exact literature in which the selection-bias correction above was worked out, because the first generation of these signatures reported cross-validated errors that had never been corrected for the selection step.

Credit underwriting, where the law requires nameable inputs. Under the US Equal Credit Opportunity Act and Regulation B, a lender who denies an application must state the specific principal reasons. CFPB Circular 2023-03 made the implication explicit: a creditor may not use a model so opaque that it cannot produce specific and accurate reasons, and generic checklist entries do not discharge the obligation. A model whose inputs are principal components has no such reason to give. This is the sharpest practical case where feature selection wins over feature extraction outright, and it connects directly to explainable AI — although selection is the cheaper move, since a feature you never selected needs no post-hoc explanation.

qSOFA, or selection as a deployment constraint. The full SOFA score for organ failure needs laboratory values across six organ systems — arterial oxygen, platelets, bilirubin, creatinine — which means a blood draw and a wait. Working from 1.3 million electronic-health-record encounters across twelve hospitals, Seymour and colleagues (JAMA, 2016) reduced it to three bedside criteria: respiratory rate at least 22, altered mental status, systolic blood pressure at most 100. qSOFA is less accurate than the full score and is used anyway, because a clinician can compute it at the bedside in ten seconds with no laboratory at all. This is the underrated argument for selection: a feature you do not select is one you never have to measure, transmit, store, pay for, or monitor for drift.

Challenges

Correlated features hide each other, and every importance measure lies about it. Take two columns correlated at r = 0.95 that both carry the same underlying signal. L1 regularization zeroes one of them essentially at random; permutation importance shakes each in turn, finds the model barely notices because the other still carries the signal, and reports both as unimportant. The correct reading of "not selected" is redundant given the rest of this set, never unpredictive. Drop such a column on the strength of its importance score and you may find the survivor is the one that stops being collected next quarter.

Univariate scores cannot see interactions, and the fix is expensive. The XOR case above is the extreme, but softer versions are everywhere: a feature that only matters within one segment, a ratio that predicts when neither numerator nor denominator does. Multivariate criteria such as mRMR (which rewards relevance to the label while penalising redundancy with already-selected features) or wrapper search will find these; the cost is that you are now searching subsets, with all the overfitting risk that entails.

Instability has a standard fix, and it doubles as an honesty check. Since the winning subset is partly determined by which rows you happened to sample, stability selection (Meinshausen and Bühlmann, 2010) runs the selector across many bootstrap subsamples and keeps only the features chosen in a high proportion of runs. If a feature list does not survive resampling, do not present it as a result.

Selection ranks association, not causation. A selected feature is whatever predicts best given the rest of the set, and a proxy predicts as well as a cause right up until the process generating the data shifts. This is why selected feature sets go stale: the columns did not stop existing, the relationship they were standing in for did.

The selection bias comes back one level up. How many features to keep, which score, which threshold — these are hyperparameters, and choosing them by the same cross-validated number you then report is the same overfitting mistake wearing a different hat. Tuning k honestly needs an outer loop that has never been used for tuning.

Code Example

This is the selection-bias demonstration, in NumPy only. The data is pure Gaussian noise and the labels are a shuffled 50/50 split, so the true error rate of any classifier is 50%. The only difference between the two numbers it prints is where the feature selection happens.

import numpy as np

n, p, k = 100, 10_000, 20        # 100 samples, 10,000 features, keep the top 20

def score(X, y):                 # a filter: |difference in class means| per feature
    return np.abs(X[y == 1].mean(0) - X[y == 0].mean(0))

def nearest_centroid(Xtr, ytr, Xte, cols):
    c0, c1 = Xtr[ytr == 0][:, cols].mean(0), Xtr[ytr == 1][:, cols].mean(0)
    return (((Xte[:, cols] - c1) ** 2).sum(1) < ((Xte[:, cols] - c0) ** 2).sum(1)).astype(int)

def one_dataset(seed):
    rng = np.random.default_rng(seed)
    X = rng.standard_normal((n, p))          # pure noise
    y = np.repeat([0, 1], n // 2)            # labels unrelated to X
    rng.shuffle(y)

    cheat = np.argsort(-score(X, y))[:k]     # chosen once, using every sample
    e_cheat = e_clean = 0
    for i in range(n):                       # leave-one-out cross-validation
        tr = np.arange(n) != i
        e_cheat += nearest_centroid(X[tr], y[tr], X[[i]], cheat)[0] != y[i]
        honest = np.argsort(-score(X[tr], y[tr]))[:k]
        e_clean += nearest_centroid(X[tr], y[tr], X[[i]], honest)[0] != y[i]
    return e_cheat / n, e_clean / n

r = np.array([one_dataset(s) for s in range(20)])
print(f"select first, then cross-validate : {r[:,0].mean():.1%} error")
print(f"select inside every fold          : {r[:,1].mean():.1%} error")

Output:

select first, then cross-validate : 8.2% error
select inside every fold          : 47.9% error

The two runs share a scoring function, a classifier and a cross-validation scheme. The only change is that cheat is computed once outside the loop while honest is recomputed on each training fold. Eight percent error on random noise is not a subtle bias — it is the difference between a result and a hallucination, and the same three lines appear in production pipelines wherever a SelectKBest call sits above the train/test split instead of inside the pipeline that gets fitted per fold.