Prediction Error and Model Choice

How well a fitted model will predict, and how to choose among models of different size, with every result proved or cited. The optimism of the training error as a covariance and the effective degrees of freedom of linear smoothers, ridge regression and thresholding; Mallows' Cp and Stein's unbiased risk estimate; Akaike's information criterion derived from the Kullback–Leibler divergence, exactly for the normal linear model with its small-sample correction, and its tendency to choose too large a model; the Bayesian information criterion from Laplace's approximation, its consistency, and the trade-off with AIC; and what cross-validation estimates, with the leave-one-out shortcut for linear smoothers. Worked on NHANES blood pressure by age and the diabetes data.

A model fitted to data describes those data better than it will describe new ones. A polynomial of degree six fits fifty blood pressures more closely than a straight line, and a ten-input regression explains more of the diabetes data than a five-input one, but neither advantage survives a fresh sample in full. Prediction error is the error a fitted model makes on data it has not seen, and model choice is the decision, made from the data at hand, about which of several fitted models to use. This unit asks how far the error on the training data understates the prediction error, how the understatement can be estimated by a formula or by holding data out, and what each of the standard criteria actually estimates.

The site's data science pages already use these tools. Model Selection compares Mallows' $C_p$, AIC, BIC and cross-validation on the diabetes data and in a simulation with a known truth; Cross-Validation introduces the leverage shortcut and generalized cross-validation; The Bias-Variance Tradeoff and Training, Validation and Test Sets explain why the training error is too small and what selection on a validation set costs. This unit is the theory beneath them: each criterion is derived from the quantity it estimates, and the conditions under which the derivation holds are stated.

What it assumes. The Linear Models unit, especially The Geometry of Least Squares (the hat matrix and its trace), The Normal Linear Model (the chi-squared laws of the fit and the residuals) and Ridge and Lasso Regression; the Likelihood and Estimation unit, especially Asymptotics of the Maximum Likelihood Estimator and Likelihood Ratio, Wald and Score Tests; Cross-Entropy and Kullback–Leibler Divergence from Information Theory; and Bayes Factors and Posterior Model Probabilities, which derives Laplace's approximation of the marginal likelihood.

What is proved and what is cited. Proved across the unit: that the expected optimism of the training error of any fitting rule is twice the average covariance between fitted values and their own responses; that the degrees of freedom of a linear smoother are its trace, with a leverage-weighted form for unequal variances; that $C_p$ is unbiased for the in-sample error whenever its variance estimate is; Stein's lemma and Stein's unbiased risk estimate, with the exact degrees of freedom of soft and hard thresholding and of choosing the best of several inputs; the exact bias of the maximized log-likelihood in the normal linear model, which gives AICc, and the limit in distribution of its bias variable for one parameter, whose mean is the penalty of two per parameter for a correct model and Takeuchi's penalty for a wrong one; the probability that AIC adds useless parameters and its positive limit, and AIC's limiting choices over a nested sequence; Laplace's method in one dimension, the consistency of BIC for a finite family of normal linear models, and the exact chances that any penalty over- or underfits between two nested models; the leave-one-out identity for linear smoothers, the Golub–Heath–Wahba bound on the expectation of generalized cross-validation, the expectation of $K$-fold cross-validation, its independence given the inputs from the error of the fitted least-squares model under normal errors, and the variance of the estimate. Assumed or stated without proof: the uniform integrability that turns limits in distribution into limits of means, and the asymptotic normality of a vector of maximum likelihood estimates under a wrong model, which gives Takeuchi's penalty with several parameters. Cited rather than proved: the asymptotic normality of a vector of maximum likelihood estimates under a correct model; the $d$-dimensional Laplace approximation (through Kass and Raftery, 1995); Wilks's theorem for several restrictions; Fubini's theorem; Bengio and Grandvalet's result that no estimator of the variance of $K$-fold cross-validation from a single run is unbiased in general (as Bates et al. report it), and Theorem 2 of Bates, Hastie and Tibshirani; and the published results on efficiency and on the trade-off between consistency and efficiency, which the articles report as their authors state them.

Notation. The inputs are fixed unless said otherwise. Responses are $\mathbf{y} = \boldsymbol\mu + \boldsymbol\varepsilon$ with true mean vector $\boldsymbol\mu$ and errors of mean zero and variance $\sigma^2$ (or $\sigma_i^2$ where the variances differ); $\hat{\mathbf{y}}$ are fitted values and $\mathbf{y}^0$ a fresh response vector at the same inputs. The training error is $\overline{\mathrm{err}} = \frac1n\lVert\mathbf{y} - \hat{\mathbf{y}}\rVert^2$, the in-sample error $\mathrm{Err}_{\mathrm{in}}$ is the expected squared error on $\mathbf{y}^0$, and $\mathrm{Err}$ is the expected error at new inputs. A linear smoother is $\hat{\mathbf{y}} = S\mathbf{y}$, with degrees of freedom $\operatorname{df} = \operatorname{tr}S$; $H$ is the hat matrix of least squares with $p$ columns, the intercept counted. For likelihood criteria, $k$ is the number of estimated parameters, the error variance included, $\hat\ell$ the maximized log-likelihood (natural logarithms), $\mathrm{AIC} = -2\hat\ell + 2k$ and $\mathrm{BIC} = -2\hat\ell + k\ln n$.

Data. The running data are the 5,176 adults of the National Health and Nutrition Examination Survey (NHANES) of 2017 to 2018 used by the Linear Models unit: the adults with at least one systolic reading and a body mass index (5,176 of the 5,247 with a systolic reading), aged 18 to 80 with 80 standing for 80 and over, with systolic pressure as the mean of the available readings. All four articles use this population; as in the other units they are treated as a finite population, the survey weights ignored. Pressure rises with age and so does its spread, from a standard deviation of 11.1 mm Hg at 18 to 22.2 at 80, so the population supplies both a near-linear truth and a realistic departure from equal variances. Polynomials in age are the candidate models throughout. The diabetes data of the data science pages (442 patients, ten inputs) carry ridge regression and subset selection. Every number is computed by a script in tools/experiments/statistics/.

Articles

Correcting the training error

  • Optimism and Effective Degrees of Freedom: the expected optimism of the training error proved, for any fitting rule, to be twice the average covariance between each fitted value and its own response; effective degrees of freedom as that covariance, equal to the trace for ridge regression and every other linear smoother and weighted by leverage when variances differ; Mallows' $C_p$ proved unbiased under the single condition that its variance estimate is unbiased; Stein's lemma and Stein's unbiased risk estimate, giving the exact degrees of freedom of soft thresholding, the extra cost of the jump in hard thresholding, and the 3.80 degrees of freedom of one input chosen as the best of ten; measured on polynomial fits to NHANES pressures over 30 seeds and on ridge regression of the diabetes data.

Likelihood criteria

  • Akaike's Information Criterion, Derived: the criterion derived as an estimate of an expected Kullback–Leibler divergence; exactly for the normal linear model, which gives AICc and proves it unbiased when the model contains the truth; in general for one parameter, where the bias variable converges in distribution to a limit whose mean is twice a ratio of two information quantities, 2 for a correct model and Takeuchi's penalty otherwise; what the criterion does not estimate; and its tendency to choose too large a model, proved through the F distribution and measured on polynomial fits to NHANES pressures at sizes from 25 to 1,600, where AIC chose too large a degree in 26.5% to 28.4% of samples at every size from 100 up.
  • The Bayesian Information Criterion and the Laplace Approximation: Laplace's method proved in one dimension with a relative error of order $1/n$ and checked on the binomial marginal likelihood; BIC proved consistent for choosing the smallest correct normal linear model from a finite family, with underfitting and overfitting both ruled out; the exact chances that a penalty of any size, AIC's or BIC's, over- or underfits between two nested models, through the central and noncentral F distributions; AIC's limiting choices over a nested sequence proved to be those of a random walk; and the trade-off between consistency and efficiency in prediction as Shao and Yang state it, with seeded simulations on NHANES pressures with the truth inside and outside the candidate set.

Holding data out

  • What Cross-Validation Estimates: the leave-one-out shortcut, the residual divided by $1 - S_{ii}$, proved for every linear smoother whose leave-one-out fit renormalizes its weights, which covers least squares, ridge, penalized splines and kernel smoothers but not nearest neighbors; generalized cross-validation as a weighted leave-one-out error, with the Golub–Heath–Wahba bound on its expectation; the expectation of $K$-fold cross-validation as the expected error of a model fitted to $n(1 - 1/K)$ points; its independence, given the inputs, from the error of the particular fitted model for least squares under normal errors (Bates, Hastie and Tibshirani); and the variance of the estimate, with the reason its usual standard error is too small, measured on NHANES pressures and the diabetes data.

Where the unit leads

The criteria of this unit choose among models fitted to the same data. When the candidates are many, the chosen model's own estimate of its error is optimistic, the selection problem treated by Selective Inference and the Garden of Forking Paths and, for a held-out set, by Training, Validation and Test Sets. Comparing models that are already fixed, such as two language models on a benchmark, is the subject of Statistics of Model Evaluation. The degrees of freedom of ridge regression and the lasso return wherever a penalty is tuned: in Ridge and Lasso Regression, in the smoothing parameter of a spline, and in the number of components of a mixture in Gaussian Mixture Models, which chooses it by BIC.

References

Each article lists its own references. The sources on which the unit draws throughout: record · 2 pages