# Cross Validation (error generalization) after model selection

Note: Case is n>>p

I am reading Elements of Statistical Learning and there are various mentions about the "right" way to do cross validation( e.g. page 60, page 245). Specifically, my question is how to evaluate the final model (without a separate test set) using k-fold CV or bootstrapping when there has been a model search? It seems that in most cases (ML algorithms without embedded feature selection) there will be

1. A feature selection step
2. A meta parameter selection step (e.g. the cost parameter in SVM).

My Questions:

1. I have seen that the feature selection step can be done where feature selection is done on the whole training set and held aside. Then, using k-fold CV, the feature selection algorithm is used in each fold (getting different features possibly chosen each time) and the error averaged. Then, you would use the features chosen using all the data (that were set aside) to train the final mode, but use the error from the cross validation as an estimate of future performance of the model. IS THIS CORRECT?
2. When you are using cross validation to select model parameters, then how to estimate model performance afterwards? IS IT THE SAME PROCESS AS #1 ABOVE OR SHOULD YOU USE NESTED CV LIKE SHOWN ON PAGE 54 (pdf) OR SOMETHING ELSE?
3. When you are doing both steps (feature and parameter setting).....then what do you do? complex nested loops?
4. If you have a separate hold out sample, does the concern go away and you can use cross validation to select features and parameters (without worry since your performance estimate will come from a hold out set)?
• @user2040 (+1) Those questions are very good ones, indeed! A somewhat related question can be found here: Feature selection for “final” model when performing cross-validation in machine learning.
– chl
Jan 3, 2011 at 19:02
• @chi Thank you, I had seen that post. Do you think I am on the right track with my thought process at least? It seems that an independent test set allows us to be more liberal in our use of CV for feature selection and model tuning / selection. Otherwise, nested loops appear required to train, tune and estimate error generalization all using the same training data. Jan 4, 2011 at 13:25

The key thing to remember is that for cross-validation to give an (almost) unbiased performance estimate every step involved in fitting the model must also be performed independently in each fold of the cross-validation procedure. The best thing to do is to view feature selection, meta/hyper-parameter setting and optimising the parameters as integral parts of model fitting and never do any one of these steps without doing the other two.

The optimistic bias that can be introduced by departing from that recipe can be surprisingly large, as demonstrated by Cawley and Talbot, where the bias introduced by an apparently benign departure was larger than the difference in performance between competing classifiers. Worse still biased protocols favours bad models most strongly, as they are more sensitive to the tuning of hyper-parameters and hence are more prone to over-fitting the model selection criterion!

The procedure in step 1 is valid because feature selection is performed separately in each fold, so what you are cross-validating is whole procedure used to fit the final model. The cross-validation estimate will have a slight pessimistic bias as the dataset for each fold is slightly smaller than the whole dataset used for the final model.

For 2, as cross-validation is used to select the model parameters then you need to repeat that procedure independently in each fold of the cross-validation used for performance estimation, you you end up with nested cross-validation.

For 3, essentially, yes you need to do nested-nested cross-validation. Essentially you need to repeat in each fold of the outermost cross-validation (used for performance estimation) everything you intend to do to to fit the final model.

For 4 - yes, if you have a separate hold-out set, then that will give an unbiased estimate of performance without needing an additional cross-validation.

• re your answer to Q1. That's the problem isn't it? Very often we think we are cross-validating the model, when in fact we are cross-validating the modelling procedure. The difference might be philosophical, because when you write down the math, the f could stand for the model or the modelling procedure. But then one could ask, is cross-validating the procedure what we want, or cross-validating the model. What's your thought? Mar 5, 2014 at 0:39
• You can't cross-validate a model as the model depends on the sample of data on which it was trained, as soon as you fit it to a different sample of data it is a different model. The point I was really making there is that if you tune the model in any way on the whole sample of data (e.g. by performing feature selection), cross-validation will give an optimistic estimate of generalisation as the test partitions have been used to tune aspects of the model (i.e. the feature set used). HTH. Mar 5, 2014 at 10:59
• Thanks @Dikran and all your answers on nested cross validation. I just have one other question. Say our outer loop error is poor (because of overfitting as you say), and we decide to change the model building procedure and not perform feature selection. If we rerun nested cross validation, i believe our generalization error is now optimistically biased because we "learnt" from our initial attempt. So unless you really are the very first person working on a brand new data set no one else has seen for before, the generalization error should always be recognized as optimistically biased? Aug 30, 2021 at 13:22
• Yes, these "researcher degrees of freedom" are very difficult to account for an arguably do affect the value of benchmark datasets as ideas develop in the literature. I think at the moment the best you can do is to fully document your model/feature selection procedure (most papers I review do not document this in sufficient detail for replication) so that the reader can at least see the "methodological degrees of freedome" Aug 30, 2021 at 13:42
• The ML community is very interested in AutoML (as am I), but most practitioners still use a lot of "CyborgML" where in addition to the AutoML techniques, like grid search, they still to a lot of manual experimentation. In that case, they are also an (undocumented) part of the model selection procedure and they can over-fit the selection criterion very easily! Aug 30, 2021 at 13:43

I have been doing an extensive cross-validation analysis on a data set that cost millions to acquire, and there is no external validation set available. In this case, I performed extensive nested cross validation to ensure validity. I selected features and optimized parameters only from the respective training sets. This is computationally expensive for large data sets, but it's what I had to do to maintain validity. However, there are complications that come with it...for example, different features are selected in each training set.

So my answer is that in cases where you don't have feasible access to an external data set, this is a reasonable way to go. When you do have an external data set, you can pretty much go to town however you want on the main data set and then test once on the external data set.

• @user2643: Do you have any references to share on how you created the nested CV? Was it along the same lines as the pdf I linked to in my question? Also.....is this data marketing data by chance? Jan 4, 2011 at 18:50
• @user2643 The problem with that approach (which is correct) is that it only yields a single criterion for accuracy (classification) or precision (regression); you won't be able to say "those are the features that are the most interesting ones" since they vary from one fold to the other, as you said. I've been working with genetic data (600k variables) where we used 10-fold CV with embedded feature selection, under a permutation scheme (k=1000, to be comfortable at a 5% level) to assess reliability of the findings. This way, we are able to say: "our model generalizes well or not", nothing more.
– chl
Jan 4, 2011 at 19:09
• If features vary from fold to fold it means that there isn't enough information to confidently identify the useful features, so I'd view that as an advantage of cross-validation (as just looking at the results from a single model is likely to have over-fit the feature selection criterion and hence be misleading). For problems with many features and few observations, ridge regression often gives better performance, so unless identifying features is a key goal, it is often better not to do any feature selection. Jan 4, 2011 at 21:08
• @Dikran I should have give more precision about my study: Yes, the objectives was feature selection (in an $n\ll p$ context, as commonly found in genome-wide association studies). When the outcome is univariate, I still prefer the elasticnet criterion, but anyway it's not the purpose of the question. I like your response (+1).
– chl
Jan 5, 2011 at 7:54
• @user2040: Sorry for the late reply. I created my own software implementation of the nested CV approach. Because my research is related to bioinformatics, I'm planning to submit a description of the software soon to a bioinformatics journal. But it can be used in any research domain. If you're interested in trying it out, please let me know. goldfish1434 at yahoo dot com Jan 12, 2011 at 16:29