Model Selection

Choosing among candidate models by their estimated performance on new data. Best subset and forward stepwise selection on the diabetes data, the optimism of training error derived and turned into Mallows' Cp, AIC as its likelihood generalization, BIC from the Bayesian approximation with posterior model probabilities, adjusted R squared, cross-validation with the search inside the folds, the one-standard-error rule and its standard error, a seeded simulation comparing every rule against a known truth, and the limits of inference after selection.

The diabetes study records ten baseline variables for each of 442 patients: age, sex, body mass index (BMI), blood pressure (BP) and six serum measurements, S1 to S6. A linear regression of disease progression on all ten explains 51.8% of its variation; on BMI, BP and S5 alone, 48.0%. Which model should be used? Adding inputs always improves the fit to the 442 patients, so the fit cannot decide. The question is which model will predict best for new patients, and how to estimate that from the data at hand.

Model selection is the task of choosing, among candidate models, the one expected to predict best (Hastie, Tibshirani and Friedman, 2009, §7.2). The candidates may differ in their inputs, as here, or in a tuning parameter, such as the degree of a polynomial, the size of a pruned tree or the number of neighbors in nearest-neighbor regression, or they may be different kinds of model altogether. This article covers the two ingredients every method needs: a set of candidates, and an estimate of each one's prediction error that does not reward complexity for its own sake. The estimates come in two kinds. Analytic criteria (Mallows' $C_p$, AIC, BIC, adjusted $R^2$) correct the training error by a formula. Resampling (Cross-Validation, the bootstrap) measures the error directly on held-out data.

Generating candidates: subset selection

With $p$ candidate inputs there are $2^p$ possible linear models. For the diabetes data, $p = 10$ gives 1,024, few enough to fit them all.

Best subset selection fits every model and keeps, for each size $k = 0, 1, \dots, p$, the one with the smallest residual sum of squares (RSS). This reduces $2^p$ candidates to $p + 1$, one per size, among which the final choice is made by one of the methods below (James, Witten, Hastie and Tibshirani, 2021, Algorithm 6.1). The search is feasible up to about $p = 40$ with branch-and-bound algorithms (Hastie et al., 2009, §3.3.1), and impossible well before $p$ reaches the hundreds.

Forward stepwise selection builds the sequence greedily: start with the intercept alone, and at each step add the input that most reduces the RSS. It fits $1 + p(p + 1)/2$ models, 56 for the diabetes data, and can be used even when $p$ exceeds $n$. Because each model must contain the one before it, it can miss the best subset of a given size (James et al., 2021, §6.1.2). Backward stepwise selection starts from the full model and removes one input at a time.

On the diabetes data, the best subsets of each size are:

Size Best subset RSS $R^2$ Adjusted $R^2$
1 BMI 1,719,582 0.3439 0.3424
2 BMI, S5 1,416,694 0.4595 0.4570
3 BMI, BP, S5 1,362,709 0.4801 0.4765
4 BMI, BP, S1, S5 1,331,431 0.4920 0.4874
5 sex, BMI, BP, S3, S5 1,287,881 0.5086 0.5030
6 sex, BMI, BP, S1, S2, S5 1,271,494 0.5149 0.5082
7 sex, BMI, BP, S1, S2, S4, S5 1,267,808 0.5163 0.5085
8 sex, BMI, BP, S1, S2, S4, S5, S6 1,264,715 0.5175 0.5086
10 all ten 1,263,986 0.5177 0.5066

(The best subset of 9 drops age and has adjusted $R^2$ 0.5077.) The RSS falls at every size, and $R^2$ rises, so neither can choose a size: both always prefer all ten inputs (James et al., 2021, §6.1.1). The subsets are not nested. The best five inputs include S3 but not S1, which is in the best four and the best six. Forward stepwise selection, which has to keep S1 once it has added it, finds the same models as best subset at every size except five, where it gives sex, BMI, BP, S1 and S5 instead. That is typical: the two methods often agree, and where they differ, the difference in fit is small (Hastie et al., 2009, §3.3.2). The serum measurements are strongly correlated with one another, as the variance inflation factors in Multiple Linear Regression showed, so several of them can stand in for each other.

Hastie et al. (2009, §3.3.2) also point to a statistical reason to prefer the more constrained search: choosing the best of many subsets of each size adds variance, and forward stepwise, which searches less, may have lower variance at the cost of some bias. A larger search can overfit the selection itself.

Correcting the training error

Optimism, derived

Training error is too small as an estimate of prediction error because each observation helps fit its own prediction. For least squares, the size of the shortfall can be computed exactly. Fix the inputs, and suppose the outcomes are $y = f + \varepsilon$, where $f$ holds the true means and the errors $\varepsilon_i$ are independent with variance $\sigma^2$. Imagine new outcomes $y^0$ at the same inputs, with independent errors. The in-sample error is the expected squared error of the fitted values on these new outcomes, $\mathrm{Err}_{\text{in}} = \frac{1}{n} \sum_i \mathbb{E}\bigl[(y_i^0 - \hat{y}_i)^2\bigr]$, and the training error is $\overline{\mathrm{err}} = \frac{1}{n} \sum_i (y_i - \hat{y}_i)^2$.

Expand both around the true mean $f_i$. For the new outcome, $y_i^0 - \hat{y}_i = (y_i^0 - f_i) - (\hat{y}_i - f_i)$, and $y_i^0$ is independent of $\hat{y}_i$, so $\mathbb{E}[(y_i^0 - \hat{y}_i)^2] = \sigma^2 + \mathbb{E}[(\hat{y}_i - f_i)^2]$. For the training outcome, $y_i - \hat{y}_i = (y_i - f_i) - (\hat{y}_i - f_i)$, but now $y_i$ and $\hat{y}_i$ are not independent:

$$\mathbb{E}\bigl[(y_i - \hat{y}_i)^2\bigr] = \sigma^2 + \mathbb{E}\bigl[(\hat{y}_i - f_i)^2\bigr] - 2\operatorname{Cov}(y_i, \hat{y}_i).$$

Subtracting, averaging over $i$, and calling the difference the optimism (Hastie et al., 2009, eq. 7.22),

$$\mathbb{E}[\mathrm{Err}_{\text{in}}] - \mathbb{E}[\overline{\mathrm{err}}] = \frac{2}{n} \sum_{i=1}^{n} \operatorname{Cov}(y_i, \hat{y}_i).$$

The harder a method fits the data, the more each $\hat{y}_i$ moves with its own $y_i$, and the larger the optimism. For least squares, $\hat{y} = H y$ with the hat matrix $H$ of Cross-Validation, so $\operatorname{Cov}(\hat{y}, y) = H \sigma^2$ and the sum of the diagonal covariances is $\sigma^2 \operatorname{trace}(H) = d \sigma^2$, where $d$ is the number of coefficients. The optimism is therefore

$$\frac{2 d \sigma^2}{n},$$

growing with the number of coefficients and shrinking with the sample size. The Bias-Variance Tradeoff checked a special case by simulation.

Mallows' Cp

Adding an estimate of the optimism to the training error gives an estimate of the in-sample error. With $\hat{\sigma}^2$ estimated from a low-bias model, usually the one with all the inputs, this is Mallows' $C_p$ (Mallows, 1973; Hastie et al., 2009, eq. 7.26):

$$C_p = \overline{\mathrm{err}} + \frac{2 d \hat{\sigma}^2}{n} = \frac{1}{n}\bigl(\mathrm{RSS} + 2 d \hat{\sigma}^2\bigr).$$

The model with the smallest $C_p$ is chosen. For the diabetes data, $\hat{\sigma}^2 = 1{,}263{,}986 / 431 = 2{,}932.7$ from the ten-input model, and $C_p$ is 3,136.1 for the best three inputs, 2,993.4 for five, 2,969.6 for six, 2,974.5 for seven and 3,005.7 for all ten. It chooses six inputs. ($C_p$ is also commonly defined as $\mathrm{RSS}/\hat{\sigma}^2 + 2d - n$, which ranks the models identically.)

One caution comes with it. The derivation assumed that the model was fixed in advance. When the subset itself was chosen as the best of many, the optimism is larger than $2 d \sigma^2 / n$: in effect, more than $d$ parameters were fitted (Hastie et al., 2009, §7.5). Applied to the winners of a best subset search, $C_p$ is itself somewhat optimistic about the larger subsets.

AIC

Akaike's information criterion (Akaike, 1974) generalizes the same correction to any model fitted by maximum likelihood:

$$\mathrm{AIC} = -2 \log \hat{L} + 2 d',$$

where $\hat{L}$ is the maximized likelihood and $d'$ the number of estimated parameters. It estimates, up to constants, the expected log-likelihood loss on new data, and like $C_p$ its penalty is twice the number of parameters (Hastie et al., 2009, §7.5). For a linear model with normal errors whose variance is also estimated, $-2\log \hat{L} = n \log(\mathrm{RSS}/n) + n(1 + \log 2\pi)$, and dropping the constant,

$$\mathrm{AIC} = n \log\frac{\mathrm{RSS}}{n} + 2(d + 1),$$

counting the variance as a parameter. When the variance is treated as known and fixed at $\hat{\sigma}^2$, AIC is equivalent to $C_p$ (Hastie et al., 2009, §7.5). For logistic regression, $-2 \log \hat{L}$ is the deviance, and AIC is the deviance plus $2d$.

BIC

The Bayesian information criterion of Schwarz (1978) has the same form with a heavier penalty:

$$\mathrm{BIC} = -2 \log \hat{L} + (\log n)\, d' = n \log\frac{\mathrm{RSS}}{n} + (\log n)(d + 1).$$

Its motivation is different. In a Bayesian comparison of models, each model's posterior probability is proportional to its prior probability times the probability of the data under the model, averaged over the model's parameters. A Laplace approximation to that average gives, for large $n$ (Hastie et al., 2009, eq. 7.40),

$$\log \Pr(\text{data} \mid \text{model}) \approx \log \hat{L} - \frac{d'}{2} \log n,$$

which is $-\mathrm{BIC}/2$. Choosing the model with the smallest BIC is therefore choosing, approximately, the model with the largest posterior probability when all models are equally probable beforehand. The approximation also gives the probabilities themselves (Hastie et al., 2009, eq. 7.41):

$$\Pr(\text{model } m \mid \text{data}) \approx \frac{e^{-\mathrm{BIC}_m/2}}{\sum_{\ell} e^{-\mathrm{BIC}_\ell/2}}.$$

With $\log 442 = 6.09$ in place of 2, BIC charges about three times as much per parameter as AIC on the diabetes data; it penalizes more heavily whenever $n > e^2 \approx 7.4$ (Hastie et al., 2009, §7.7).

The criteria on the diabetes data

Size $C_p$ AIC BIC BIC probability
3 3,136.1 3,560.88 3,581.34 0.001
4 3,078.6 3,552.62 3,577.17 0.007
5 2,993.4 3,539.92 3,568.56 0.526
6 2,969.6 3,536.26 3,568.99 0.424
7 2,974.5 3,536.98 3,573.80 0.038
8 2,980.8 3,537.90 3,578.81 0.003
10 3,005.7 3,541.64 3,590.74 0.000
AIC, BIC and Cp (rescaled to AIC's units) for the best subset of each size, as differences from their minima; circles mark each minimum. AIC and Cp agree closely and choose six inputs. BIC's heavier penalty makes the curve rise faster to the right, and it chooses five, though five and six are nearly tied.
AIC, BIC and Cp (rescaled to AIC's units) for the best subset of each size, as differences from their minima; circles mark each minimum. AIC and Cp agree closely and choose six inputs. BIC's heavier penalty makes the curve rise faster to the right, and it chooses five, though five and six are nearly tied.

AIC and $C_p$ choose six inputs; BIC chooses five. The BIC probabilities show that the choice is close: 0.526 for the best five-input model and 0.424 for the best six, with everything else below 0.04. These are probabilities among the eleven best-of-size models only, under equal prior probabilities and the large-sample approximation, so they are a rough guide, but they say plainly that the data do not distinguish five inputs from six.

Adjusted R squared

Adjusted $R^2$, defined in Multiple Linear Regression, replaces RSS and the total sum of squares by their unbiased variance estimates:

$$R^2_{\text{adj}} = 1 - \frac{\mathrm{RSS}/(n - k - 1)}{\mathrm{TSS}/(n - 1)},$$

with $k$ the number of inputs. Maximizing it amounts to minimizing $\mathrm{RSS}/(n - k - 1)$, the estimated error variance. It penalizes complexity much more lightly than the other criteria: an input raises adjusted $R^2$ whenever its $t$ statistic exceeds 1 in absolute value, while AIC, for large $n$, requires roughly $|t| > \sqrt{2}$. On the diabetes data it chooses eight inputs, by a margin in the fourth decimal place (0.5086 against 0.5085 for seven). James et al. (2021, §6.1.3) note that it is popular but not as well motivated in statistical theory as $C_p$, AIC and BIC.

Which penalty?

AIC and BIC answer different questions. AIC aims at prediction: it estimates expected loss on new data, and is chosen to make that loss small. BIC aims at identification: if one of the candidates is the true model, the probability that BIC selects it approaches 1 as $n$ grows, a property called consistency, which AIC lacks; AIC tends to choose models that are too complex as $n$ grows. In finite samples, BIC often chooses models that are too simple (Hastie et al., 2009, §7.7). Hastie et al. conclude that "there is no clear choice between AIC and BIC." The simulation below shows the difference in a case where the truth is known.

All of these criteria need the number of parameters, which is clear for least squares on fixed inputs and unclear for trees, forests, boosted models and anything chosen by an adaptive search. For such methods only resampling remains (Hastie et al., 2009, §7.11.1).

Selecting by cross-validation

Cross-validation estimates prediction error directly, makes no assumption about the form of the model or its errors, and works with any loss and any method. For subset selection there is one requirement that is easy to miss. The search for the best subset uses the outcome, so it must be repeated inside each training part; using the subsets found on all the data would let the held-out patients influence which inputs were chosen, the leakage described before. The procedure for each size $k$ (James et al., 2021, §6.5.1) is:

  1. For each fold, find the best subset of size $k$ using only the other nine folds, fit it, and compute its MSE on the held-out fold.
  2. Average over the folds to estimate the error for size $k$.
  3. Choose a size $\hat{k}$, then find the best subset of that size on all the data.

The method selects a size, not a particular set of inputs. Here the inputs mostly agree across folds anyway: the five-input search found sex, BMI, BP, S3 and S5 in all ten training parts, and the three-input search found BMI, BP and S5 in nine of ten.

With the ten folds of Multiple Linear Regression:

Size 1 2 3 4 5 6 7 8 9 10
CV MSE 3,915.9 3,239.7 3,203.8 3,123.4 2,974.0 2,978.7 2,987.4 2,956.9 2,980.9 2,985.2
SE 227.1 133.6 158.7 142.2 138.1 158.6 161.3 159.6 159.0 157.5

The intercept-only model has a cross-validated MSE of 5,944.6. The minimum is at eight inputs, 2,956.9, but every size from five to ten is within 31 of it, while the standard errors are about 160. The curve is flat; which point on a flat curve is lowest is decided mostly by noise.

The one-standard-error rule

The one-standard-error rule turns that observation into a procedure: choose the simplest model whose estimated error is within one standard error of the minimum (Hastie et al., 2009, §7.10.1; James et al., 2021, §6.1.3). Its rationale is that models whose errors cannot be told apart might as well be chosen for simplicity, which brings stability, interpretability and a smaller chance that the complexity is fitting noise.

The standard error in the rule is that of the cross-validation estimate at the minimum: the standard deviation of the $K$ fold errors divided by $\sqrt{K}$. For eight inputs this is $504.7 / \sqrt{10} = 159.6$, so the threshold is $2{,}956.9 + 159.6 = 3{,}116.5$. The smallest size below it is five, with 2,974.0, and the rule chooses five inputs: sex, BMI, BP, S3 and S5, the model BIC chose.

Ten-fold cross-validated MSE of the best subset of each size, with bars of one standard error, the search repeated within each training part. The minimum is at eight inputs; the one-standard-error rule picks the smallest model under the dashed line, five inputs.
Ten-fold cross-validated MSE of the best subset of each size, with bars of one standard error, the search repeated within each training part. The minimum is at eight inputs; the one-standard-error rule picks the smallest model under the dashed line, five inputs.

The distinction between standard deviation and standard error matters here. Using the standard deviation of the fold errors, 504.7, as the margin would set the threshold at 3,461.6 and choose two inputs, a model whose cross-validated error is 10% higher than the minimum. The standard deviation measures how much a single fold's error varies; the standard error measures how uncertain the average is, which is what the rule needs. Since the fold errors are correlated, even the standard error understates that uncertainty, as Cross-Validation explains, so the rule is a heuristic with a reasonable scale rather than a test of significance. The same rule chose a three-leaf tree over the four-leaf minimum in Regression Trees.

Comparing the rules against a known truth

On real data the right answer is unknown. In a simulation it can be fixed in advance. The simulation draws $n = 60$ cases with ten normally distributed inputs, correlated with correlation $0.5^{|i - j|}$ between inputs $i$ and $j$, and an outcome

$$y = 3 x_1 + 1.5 x_2 + 2 x_5 + \varepsilon, \qquad \varepsilon \sim N(0, 3^2).$$

The true model has three inputs; the other seven are irrelevant, though correlated with the relevant ones. For each of 1,000 datasets (seed 742), best subset selection was run and a size chosen by each rule. Each chosen model's expected squared prediction error on new cases was computed exactly from the known distribution. The noise variance, 9, is the floor.

Rule Mean size Exactly the true model Mean prediction error
$C_p$ 4.15 31.0% 10.48
AIC 4.32 26.3% 10.53
BIC 3.27 59.7% 10.21
Adjusted $R^2$ 5.37 7.8% 10.77
10-fold CV, minimum 3.73 49.1% 10.42
10-fold CV, one-SE rule 2.57 44.6% 10.75
All ten inputs 10 11.03
The true three inputs 3 9.63
How often each rule chose each model size over 1,000 simulated datasets in which the true model has three inputs (green bar). Adjusted R squared, AIC and Cp lean toward too many inputs; the one-standard-error rule often drops the weakest true input and stops at two; BIC is right most often. The title gives each rule's mean prediction error (noise variance 9).
How often each rule chose each model size over 1,000 simulated datasets in which the true model has three inputs (green bar). Adjusted R squared, AIC and Cp lean toward too many inputs; the one-standard-error rule often drops the weakest true input and stops at two; BIC is right most often. The title gives each rule's mean prediction error (noise variance 9).

The simulation bears out the theory and adds some texture.

  • The light penalties overfit. Adjusted $R^2$ averaged more than five inputs and found the true model in under 8% of datasets. AIC and $C_p$ averaged more than four, consistent with their tendency toward extra inputs.
  • BIC did best on every measure here. It found the true model most often and had the lowest prediction error. The truth is in the candidate set and is sparse, the situation BIC is designed for. With many small effects and no sparse truth, the comparison can come out the other way.
  • The one-standard-error rule underfit. Its models were the simplest, and in 44.7% of datasets it stopped at two inputs, in 418 of those 447 by dropping $x_2$, whose coefficient of 1.5 is half the noise standard deviation. Its prediction error, 10.75, was worse than that of the plain cross-validation minimum, 10.42. Simplicity is not free when a real but weak effect sits near the threshold.
  • Every rule beat the full model, and none came close to the true model fitted directly, 9.63. Selection costs something: with 60 cases, no rule can reliably separate a coefficient of 1.5 from noise with standard deviation 3.

Forward stepwise selection found a different model from best subset at some size in 39.3% of the datasets, so on correlated inputs the two searches disagree often, even when they agree on the diabetes data at all sizes but one.

After selection

The chosen model's standard errors

A model chosen from many candidates on the same data cannot be reported as if it had been specified in advance. Its coefficients, standard errors and $p$-values are computed as though the inputs had been fixed, but the inputs were chosen because they fit well on these data, and the reported standard errors "are not valid, since they do not account for the search process" (Hastie et al., 2009, §3.3.2). The coefficients of selected inputs are biased away from zero, for the same reason as the winner's curse, and their $p$-values are too small. Honest uncertainty requires repeating the selection inside a bootstrap, fitting the selected model to independent data, or methods designed for inference after selection.

Estimating the chosen model's error

The cross-validation curve's minimum is an optimistic estimate of the chosen model's error; nested cross-validation or a separate test set gives an honest one. The analytic criteria are no better: Hastie et al. (2009, §7.11.1) found that AIC overestimated the test error of its chosen models by 30% to 51% in their simulations, while cross-validation was within 4%. They are tools for ranking models, not for measuring them.

Choosing among model families

The same principles apply when the candidates are different methods. On the diabetes data, 10-fold cross-validated $R^2$ was 0.484 for the ten-input linear regression, 0.443 for a random forest and 0.342 for the best pruned regression tree, with the same folds. Here the simplest model also predicts best. Where several models are close, cross-validated error is one input to the choice; others are the cost of collecting the inputs, whether the predictions are plausible, and how the model will be explained and maintained. A model that predicts negative values for a quantity that cannot be negative, or relies on a measurement unavailable at prediction time, should be rejected whatever its score.

Selection versus shrinkage

Subset selection makes a discrete choice: each input is in or out. Small changes in the data can change that choice, which makes the selected model variable (Hastie et al., 2009, §3.4). Regularized methods such as ridge regression and the lasso keep the inputs and shrink their coefficients continuously, with a single tuning parameter chosen by the same tools: cross-validation, often with the one-standard-error rule. They are often more stable alternatives to subset selection, and the lasso performs a form of selection itself by setting some coefficients exactly to zero.

In Python

import itertools
import numpy as np
from sklearn.datasets import load_diabetes

data = load_diabetes(scaled=False)
X, y, names = data.data, data.target, data.feature_names
n, p = X.shape

def rss(cols):
    A = np.column_stack([np.ones(n), X[:, cols]])
    r = y - A @ np.linalg.lstsq(A, y, rcond=None)[0]
    return r @ r

for k in range(1, p + 1):
    best = min(itertools.combinations(range(p), k), key=lambda c: rss(list(c)))
    r, d = rss(list(best)), k + 1                  # d coefficients, including the intercept
    aic = n * np.log(r / n) + 2 * (d + 1)
    bic = n * np.log(r / n) + np.log(n) * (d + 1)
    print(k, [names[j] for j in best], round(aic, 2), round(bic, 2))
# 5 ['sex', 'bmi', 'bp', 's3', 's5'] 3539.92 3568.56   (lowest BIC)
# 6 ['sex', 'bmi', 'bp', 's1', 's2', 's5'] 3536.26 3568.99   (lowest AIC)

scikit-learn does not compute AIC or BIC for linear regression; the formulas above take a line each, and the statsmodels package reports both for fitted models (with its own constants, which shift every model's value equally and do not change the ranking). sklearn.feature_selection.SequentialFeatureSelector performs forward or backward stepwise selection, but it ranks inputs by cross-validated score rather than RSS, and it stops at a fixed number of inputs or a minimum improvement. For the one-standard-error rule, compute scores.mean() and scores.std(ddof=1) / np.sqrt(K) for each candidate from cross_val_score, and plot them with matplotlib's errorbar. The numbers in this article are computed by tools/experiments/data-science/model-selection.py in the site's repository.

References

  • Akaike, H. (1974). A new look at the statistical model identification. IEEE Transactions on Automatic Control, 19(6), 716–723. record
  • Hastie, T., Tibshirani, R., and Friedman, J. (2009). The Elements of Statistical Learning: Data Mining, Inference, and Prediction (2nd ed.). Springer. record · 23 pages
  • James, G., Witten, D., Hastie, T., and Tibshirani, R. (2021). An Introduction to Statistical Learning with Applications in R (2nd ed.). Springer. record · 30 pages
  • Mallows, C. L. (1973). Some comments on $C_p$. Technometrics, 15(4), 661–675. record
  • Schwarz, G. (1978). Estimating the dimension of a model. The Annals of Statistics, 6(2), 461–464. record