Intermediate28 min

Feature Selection

Filter, wrapper and embedded methods; mutual information, RFE and stability selection.

Assumes you know

Feature Engineering

Feature Selection

Intuition first

Every feature costs something. It enlarges the hypothesis space, adds variance, dilutes distance metrics, and in production becomes a pipeline dependency that can break or drift. A feature that contributes nothing is not neutral — it is a liability.

Selection removes them. The difficulty is that "contributes nothing" is not a property of a feature in isolation. Two features can each be useless alone and jointly perfectly predictive. Another can be strongly predictive alone and redundant once a correlated partner is present.

So there are two families of method: cheap ones that score features individually and miss interactions, and expensive ones that evaluate subsets and catch them. Both are prone to the same failure — selecting using the labels is a search, and searching with the labels leaks.

The three families

Family	How it works	Cost	Catches interactions
Filter	Score each feature against the target, keep the top $k$	Very low	No
Wrapper	Search subsets, evaluating a model on each	Very high	Yes
Embedded	Selection falls out of model fitting	Low	Partly

Filter methods

Score each feature independently, then threshold.

Correlation — Pearson for linear relationships; misses non-monotone ones entirely.
Mutual information — captures any dependence, monotone or not:

I(X; Y) = \sum_{x}\sum_{y} p(x,y) \log \frac{p(x,y)}{p(x)p(y)}

Chi-squared — for categorical features against a categorical target.
ANOVA F-test — continuous feature, categorical target.
Variance threshold — drop near-constant features. Cheap and safe, since it ignores the target and therefore cannot leak.

Wrapper methods

Treat selection as a search over subsets, scoring each with cross-validated model performance.

Forward selection — start empty, repeatedly add the feature that most improves the score.
Backward elimination — start full, repeatedly remove the least useful.
Recursive feature elimination (RFE) — fit, drop the weakest by model-reported importance, refit, repeat.

Exhaustive search over $d$ features requires $2^d$ subsets — 1,024 for ten features, about $10^{30}$ for a hundred. Greedy variants are the only practical option, and they can miss the optimum.

Embedded methods

Selection as a by-product of fitting, which is usually the best value for effort.

L1 / lasso — drives coefficients to exactly zero. Selection and fitting in one step.
Tree importances — impurity reduction or, better, permutation importance.
Elastic net — lasso's selection with ridge's stability across correlated groups.

Solved problem 1 · Permutation importance with correlated features

A model is fitted with four features. Validation $R^2 = 0.80$ . Permuting each feature individually gives:

Permuted feature	$R^2$ after permutation	Drop
$x_1$	0.62	0.18
$x_2$	0.78	0.02
$x_3$	0.79	0.01
$x_4$	0.80	0.00

Additionally, $x_2$ and $x_3$ have correlation 0.97. Permuting $x_2$ and $x_3$ together gives $R^2 = 0.55$ .

What should be dropped?

Step 1 — the unambiguous cases

$x_1$ has a drop of 0.18 — by far the largest single contribution. Keep.

$x_4$ has a drop of 0.00. The model's performance is unchanged when its values are scrambled, so it relies on it not at all. Drop.

Step 2 — the trap

Individually, $x_2$ and $x_3$ look nearly worthless: drops of 0.02 and 0.01. A naive threshold of "drop anything below 0.05" removes both.

Step 3 — why the individual drops are misleading

Because $x_2$ and $x_3$ are 0.97 correlated, permuting one leaves the other carrying almost the same information. The model simply reads the signal from the surviving twin, so performance barely falls. Each appears redundant only because the other is present.

Step 4 — the joint test settles it

Permuting both together:

0.80 - 0.55 = 0.25

A drop of 0.25 — larger than $x_1$ 's. The pair carries the most information in the model; neither member is individually necessary because either can substitute for the other.

Step 5 — decide

Drop $x_4$ only. Keep $x_1$ . Keep at least one of $x_2$ and $x_3$ — and since the pair contributes 0.25 while one alone appears to contribute 0.01–0.02, test explicitly whether keeping just one preserves performance. If it does, keep the cheaper or more stable of the two.

Answer

Drop $x_4$ . Retain $x_1$ and at least one of the correlated pair. Deleting both $x_2$ and $x_3$ on their individual scores would cost 0.25 of $R^2$ — the single most common error when reading permutation importance.

Selection must live inside cross-validation

This is the same point as the leakage lesson, and it is worth repeating because selection is the worst offender.

python

import numpy as np
from sklearn.pipeline import Pipeline
from sklearn.feature_selection import SelectKBest, f_classif
from sklearn.linear_model import LogisticRegression
from sklearn.model_selection import cross_val_score, StratifiedKFold

rng = np.random.default_rng(0)
n, d = 100, 5000
X = rng.normal(size=(n, d))          # pure noise
y = rng.integers(0, 2, size=n)       # independent labels

cv = StratifiedKFold(n_splits=5, shuffle=True, random_state=0)

# WRONG: selection sees all 100 labels before any split.
X_leaky = SelectKBest(f_classif, k=10).fit_transform(X, y)
leaky = cross_val_score(LogisticRegression(max_iter=1000), X_leaky, y, cv=cv)

# RIGHT: selection refitted inside every fold.
honest = cross_val_score(
    Pipeline([("sel", SelectKBest(f_classif, k=10)),
              ("clf", LogisticRegression(max_iter=1000))]),
    X, y, cv=cv,
)

print(f"leaky  {leaky.mean():.3f}   <- on data with NO signal whatsoever")
print(f"honest {honest.mean():.3f}   <- correct, near 0.5")

The leaky number typically lands between 0.75 and 0.90 on pure noise. The honest number sits near 0.50, where it belongs.

A practical order of operations

Drop the obviously dead — zero variance, near-constant, duplicated columns, identifiers. Target-free, so no leakage risk.
Drop leaking features — decided by reasoning about timing, not by any score.
Handle correlation — for each cluster of highly correlated features, keep the one that is cheapest to compute and most stable in production.
Fit with L1 or elastic net and inspect what survives at a cross-validated $\lambda$ .
Check with permutation importance on held-out data, using grouped permutation for correlated blocks.
Only then consider a wrapper, if the cost is justified.

Exercise 1

You have 500 features and 2,000 rows. Forward selection with 5-fold CV is proposed. Estimate the cost, and suggest an alternative.

Show solution

Forward selection evaluates every remaining feature at each step. Selecting $k$ features from $d = 500$ requires approximately

\sum_{j=0}^{k-1} (500 - j) \approx k \times 500 \quad \text{model fits, each} \times 5 \text{ folds}

For $k = 20$ :

20 \times 500 \times 5 = 50{,}000 \text{ model fits}

At one second per fit that is about 14 hours, and the search is greedy so it may still miss the best subset. It also compounds selection optimism across 10,000 comparisons.

Better alternative: L1-regularised fitting with cross-validated $\lambda$ . LassoCV or LogisticRegressionCV with an L1 penalty explores the whole regularisation path in the cost of roughly one model fit per $\lambda$ value — perhaps 100 fits total, three orders of magnitude cheaper. Selection emerges from the optimisation rather than from a search over subsets, and there is a single hyperparameter rather than 10,000 comparisons.

Follow up with grouped permutation importance on the survivors to check nothing important was eliminated through correlation, and use elastic net rather than pure lasso if the features come in correlated blocks.

If a wrapper is genuinely required, RFE with step size 10 reduces the fit count by roughly an order of magnitude at little cost in quality.

Exercise 2

Explain why removing a feature sometimes improves validation performance, even though it carries genuine information.

Show solution

Because a feature contributes both signal and estimation cost, and the second can exceed the first.

Including a feature adds a parameter to estimate from the same finite data. That raises variance. If the feature's true coefficient is small, the variance added in estimating it outweighs the bias it removes, and total expected error rises. The bias–variance decomposition makes this precise: dropping the feature increases bias² a little and decreases variance more.

Three further mechanisms:

Dilution of distance. For kNN, k-means or RBF kernels, a weakly informative feature still contributes fully to the distance computation, degrading neighbour quality.

Redundancy plus instability. A feature highly correlated with another adds little signal while making the coefficient estimates unstable — both coefficients become poorly determined, and predictions swing with small data changes.

Noise in measurement. A feature that is informative in principle but noisily measured can contribute more noise than signal at the sample size available.

This is precisely what regularisation exploits: lasso sets small-coefficient features to zero because the variance saved exceeds the bias incurred. Feature selection is regularisation applied as a discrete decision rather than a continuous penalty.

Next: Hyperparameter Search.