Feature Selection: Filter, Wrapper and Embedded Methods

Generate 50 samples with 5,000 features of pure Gaussian noise and random binary labels. Pick the 100 features most correlated with the label, then estimate the accuracy of a 1-nearest-neighbour classifier on them with 5-fold cross-validation. Averaged over 20 repetitions, the estimated error is 1%. Move the selection step inside each cross-validation fold and the estimated error is 52%, which is the truth: there is nothing to learn. (Both numbers come from a small scikit-learn simulation.) The first procedure is not a toy mistake. It was common enough in published microarray studies that Ambroise and McLachlan wrote a paper showing how badly it inflated reported accuracy (Ambroise and McLachlan, 2002, Selection bias in gene extraction on the basis of microarray gene-expression data, PNAS 99(10)).

Why select at all

Fewer features can mean lower variance on small data, cheaper inference, fewer upstream pipelines to maintain and monitor, and a model a regulator can read. The standard taxonomy sorts methods by how much they consult the learning algorithm (Guyon and Elisseeff, 2003, An Introduction to Variable and Feature Selection, JMLR 3).

Filters: score each feature alone

A filter ranks features by a statistic computed without any model: Pearson correlation, an ANOVA \(F\) statistic, \(\chi^2\) for counts, or mutual information \(I(X_j; Y)\). Cost is linear in the number of features, which is why filters are the only option at genomic scale.

The weakness is structural. A univariate score cannot see interactions. If \(Y = X_1 \oplus X_2\) for two independent fair binary features, each feature alone has zero mutual information with \(Y\), yet together they determine it exactly. Guyon and Elisseeff make the same point: a feature useless on its own can be useful in combination, and two nearly identical features ranked first and second add almost nothing beyond the first. Filters select redundancy happily.

Wrappers: search subsets with the model

A wrapper evaluates candidate subsets by training the model and measuring validation performance. Exhaustive search over \(p = 30\) features is \(2^{30} \approx 1.07 \times 10^9\) fits, so wrappers search greedily. Forward selection adds the best feature at each step, needing at most \(p(p+1)/2 = 465\) fits for \(p = 30\); recursive feature elimination fits the full model and repeatedly drops the least important features.

Wrappers see the interactions the model can represent and optimise the metric you care about. They cost many fits, and because they choose among many subsets using noisy validation scores, they overfit the validation data, for the same reason the best of many hyperparameter settings has an optimistic score.

Embedded: selection inside the fit

The lasso solves

and the corners of the \(\ell_1\) ball set some coefficients exactly to zero, so selection and fitting are one optimisation. Tree ensembles provide importances as a by-product.

Neither is a clean selector. With correlated features the lasso tends to keep one and zero the others, and which one survives flips between resamples. Impurity-based random forest importance is biased toward continuous features and categorical features with many levels, which offer more candidate split points (Strobl, Boulesteix, Zeileis and Hothorn, 2007, Bias in random forest variable importance measures, BMC Bioinformatics 8). Stability selection attacks instability directly: run the lasso on many half-size subsamples and keep features selected in more than a fraction \(\pi_{\text{thr}}\) of runs. Under exchangeability assumptions the expected number of false selections is bounded by \(\mathbb{E}[V] \le q^2 / \bigl((2\pi_{\text{thr}} - 1)\,p\bigr)\), where \(q\) is the average number of features selected per run, and the procedure can be consistent where the plain lasso's conditions fail (Meinshausen and Bühlmann, 2010, Stability selection, JRSS-B 72(4)).

When it breaks

Selection outside cross-validation is leakage. Any selection that looks at labels, whether a filter score, a lasso path or a wrapper search, is part of fitting and must be repeated within every training fold. For a wrapper that means nested cross-validation: an inner loop to select, an outer loop to evaluate.

The selected set is not the true set. Bootstrap a selection procedure on real data and many "important" features appear in only a minority of runs. Reading a lasso's non-zero coefficients as causal drivers is a claim the method does not support.

Inference after selection is invalid. Refitting least squares on the selected features and reporting its p-values ignores that the features were chosen for looking significant. The intervals are too narrow, and honest ones need post-selection inference methods.

Selecting may not help prediction. Whether to select at all is contested. Regularised linear models and gradient-boosted trees usually lose little from irrelevant features and can lose real signal when weak ones are removed, so many practitioners select only for cost, latency or interpretability. Others counter that every production feature carries its own pipeline, drift and leakage risk, which a leaner model avoids.