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)?
  • $\begingroup$ @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. $\endgroup$ – chl Jan 3 '11 at 19:02
  • $\begingroup$ @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. $\endgroup$ – B_Miner Jan 4 '11 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!

Answers to specific questions:

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.

  • $\begingroup$ 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? $\endgroup$ – qoheleth Mar 5 '14 at 0:39
  • $\begingroup$ 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. $\endgroup$ – Dikran Marsupial Mar 5 '14 at 10:59
  • $\begingroup$ I don't know if it is ok to continue our discussion in the comment section, but until someone says otherwise... Yes, I understand your point about CV needs to be done on the outermost level and I am not objecting it. In fact, I just gave the same advice to my colleague yesterday. I am just pointing out that we are often not sure what we are cross-validating. At the same time I wonder if getting evaluation on the model, rather than the modelling procedure, is what we actually want. A remedy might be one can think that he is using procedure error to estimate model error. Maybe this works. $\endgroup$ – qoheleth Mar 5 '14 at 13:58
  • $\begingroup$ We can't get a direct estimate of the performance of a particular model without having an external test set. The performance of the method for producing a model is however a reasonable proxy for the performance of the model itself, provided it is the whole method that is cross-validated. In other words, I agree with the summary in your last sentence! $\endgroup$ – Dikran Marsupial Mar 5 '14 at 17:10

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.

  • $\begingroup$ @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? $\endgroup$ – B_Miner Jan 4 '11 at 18:50
  • $\begingroup$ @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. $\endgroup$ – chl Jan 4 '11 at 19:09
  • 2
    $\begingroup$ 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. $\endgroup$ – Dikran Marsupial Jan 4 '11 at 21:08
  • $\begingroup$ @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). $\endgroup$ – chl Jan 5 '11 at 7:54
  • $\begingroup$ @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 $\endgroup$ – user2643 Jan 12 '11 at 16:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.