Bias induced from model selection

Question

I am trying to understand the following sentence

Cross-validation and information criteria make a correction for using the data twice (in constructing the posterior and in model assessment) and obtain asymptotically unbiased estimates of predictive performance for a given model. However, when these methods are used to choose a model selection, the predictive performance estimate of the selected model is biased due to the selection process.

Are they saying that because the sample may not be representative, the methods above may over/under-estimate the true model performance, and so we will tend to choose those who perform better under the selected data, but not for out-of-sample data?

Answer 1

I believe what they are saying is if you use a hold out data for cross validation to estimate the generalization error of your model then you land up with the unbiased estimate of generalization error of the model.

But once you use that data set for selection process for a model, which I believe is tuning the model and minimizing the error on that particular data set and then you choose one model out of numerous others, then the error estimate you get is not an unbiased generalization error estimate. This is because the model has been optimized to perform well on the data set used for cross validation and in a way model has 'seen' the data. So there are good chances that the estimate you will get underestimates the true error.

To avoid this and get the unbiased generalization error estimate one must evaluate the model on a 'test' set that has not not been used for training or validation (model-selection).

Answer 2

When you evaluate a model it is assumed that your model is given apriori any seen data. As such model evaluation is fine considering the sample is representative. However when you choose a model based on data, the model fitting becomes a random variable estimation. Assessing performance on the same data is not unbiased anymore, usually more optimistic than is the case. As such to avoid this bias in evaluation you need fresh data.

[Later edit]

I really well written and involved discussion on this topic you can find in Advanced Data Analysis from an Elementary Point of View by Cosma Rohilla Shalizi. It's free and it is one of the best books no deeper understanding those kind of intricacies. For this discussion see section 3.5.1 Inference after selection.

Regarding you comment I do not completely understand what do you mean by 'relative' fit. If relative performance means the evaluated performance of one model against other, for model selection purposes and you care about prediction, I think that you can go without additional data set. It's like choosing the best you have at hand, but without knowing really how well will perform your best model.

Answer 3

Below is my understanding of the paragraph (without having the context):

Start:

Cross-validation and information criteria make a correction for using the data twice (in constructing the posterior and in model assessment).

Cross-validation helps to avoid the so called "double-dipping" problem - when one uses the same data to estimate the model and to check how well it does.

Continues:

and obtain asymptotically unbiased estimates of predictive performance for a given model.

When sample size grows to infinity cross validation will generate unbiased estimates for predictive performance. With small sample sizes it will be more biased because in each cross-validation fold we will not be using all of the training data - but only a part of it (like 9/10 in 10-fold CV).

Continues:

However, when these methods are used to choose a model selection

That is when cross-validation is used multiple times, not only once. For example when selecting between multiple models we might have an idea to run all of those models through cross validation and select the best one.

Continues:

the predictive performance estimate of the selected model is biased due to the selection process.

Then the final predictive performance (the very thing we used in selecting our model) will be biased. This is because each model has some variability or randomness in them. When estimated on final data (with cross validation) performance estimates do not give us the exact true performance of those models on the population. Instead there is always some error associated with this performance measure.

And because of this error - we will end up picking the model whose error (difference between true performance and estimated cross-validation performance) is optimistically biased. And the more models we try on cross-validation - the worse it will be.

Bottom line:

Cross-validation is unbiased (asymptotically) when used once. But it is not panacea for overfitting and will become biased once we start comparing different models on the same cross-validation data.

Answer 4

Cross validation (applied solely for validation/verification purposes) avoids the double use of cases being in the training set and in the test set for the same model. However, performance estimates that are used to select the apparently best of a variety of models are in fact part of model training. So cross validation used for model selection or optimization is part of the training and then a separate test using data that is unknown to the whole training process (including model selection) is needed.

The reason for this is that the cross validation results are only estimates (or measurements) of model performance: they are subject to bias and variance, i.e. systematic and random errors.

because the sample may not be representative, the methods above may over/under-estimate the true model performance,

That's another way of saying, there's variance on the performance estimate in addition to possible bias. This is true for any kind of performance measurement (estimate based on testing cases): the test sample (whether held back by cross validation or obtained in any other way) may accidentally contain more easy cases or more difficult cases. So you'll have to expect some variance when testing the same model with different test sets. In resampling validation (including cross validation) you have an additional source of variance: you are actually testing surrogate models that are assumed to be sufficiently similar to the model trained on the whole data (for which the performance estimate is used) to be considered equivalent for practical purposes. However, if your training procedure is not stable, you'll see variance among the surrogate models, which will also add to the variance of your cross validation estimate.

So we end up with an almost unbiased but somewhat noisy estimate of performance ...

and so we will tend to choose those who perform better under the selected data,

So yes, when picking the apparently best performing model, we'll "skim off the noise", i.e. models that accidentally look good with the cross validation split we did will be favored.

The risk of skimming variance (= overfitting, selecting the wrong model) increases with

• increasing number of compared models
• increasing variance uncertainty on the performance estimates, and
• decreasing true difference in performance among the considered models
  (although one may argue that this is less of a problem as the mistake here is only to select a not totally perfect model from a number of almost equally good models)

but not for out-of-sample data?

While the out-of-sample test set will may accidentally contain more easy cases than the population, it is unlikely that we're (un*)lucky here as well.

Side note: this may happen of course. But we can estimate the likelihood/extent of such random (bad) luck with the usual tools to estimate uncertainty on our point estimate.
My impression, however, is that in practice overoptimistic assessment of models more frequently happens due to biased sampling, such as cases being excluded for which no labels can be obtained (possibly because they are hard/borderline cases).

---

* I consider it bad luck if a model appears better than it actually is as I've had to deal a lot with data where unwarranted overoptimism may lead to harm.