Will cross validation performance be an accurate indication for predicting the true performance on an independent data set?

I feel that this question is related to the theory behind cross-validation. I present my empirical finding here and wrote a question related to the theory of cross-validation at there.

I have two models M1 and M2, I use the same data set to train them and perform cross validation using that same data set to find the optimal parameters for each model. Say eventually I found that M1 under its optimal parameter, performs better than M2 under its optimal parameter in terms of the 10-fold cross validation score. Now if I have another independent test data set with both predictors and labels and this test data set is generated from the same distribution of my training data set, then before I apply these 2 well-tuned model on that new test data set, can I claim or should I expect to see that M1 will still perform better than M2 over that new test data set?

I was playing Kaggle Titanic example. I have 2 xgboost model, M1 is well-tuned and M2 is less well-tuned in the sense that M1 has a better 10 fold cross validation performs on the training data set. But then when I submit both, I found that the less well-tuned model actually has a better scores on the test data set. How could that be? And if it is true, then what should we looking for when we fit the data to different models and tune the model parameters?

Here are my specific submission results: I did a random grid search

params_fixed = {'silent': 1,'base_score': 0.5,'reg_lambda': 1,
'objective': 'binary:logistic'}
params_grid = {'max_depth': list(np.arange(1,10)),
'gamma': [0,0.05,0.1,0.3, 0.5,0.7,0.9],
'n_estimators':[1,2,5,7,10,15,19,25,30,50],
'learning_rate': [0.01,0.03,0.05,0.1,0.3,0.5,0.7,0.9,1],
'subsample': [0.5,0.7,0.9], 'colsample_bytree': [0.5,0.7,0.9],
'min_child_weight': [1,2,3,5], 'reg_alpha': [1e-5, 1e-2, 0.1, 0.5,1,10]
}
rs_grid = RandomizedSearchCV(
estimator=XGBClassifier(**params_fixed, seed=seed),
param_distributions=params_grid,
n_iter=5000,
cv=10,
scoring='accuracy',
random_state=seed
)


Each time I change the variable n_iter. First, I set n_iter=10, it gives me a set of values of those hyper parameters, let's call this vector $\alpha_1$ and the cv score (accuracy rate) is 0.83389, then I use $\alpha_1$ to train my model and generate prediction on the independent test data set, and when I submit to Kaggle it generates true accuracy on the test data set 0.79426

Second, I set n_iter=100, it gives me $\alpha_2$ and the cv score is 0.83614, i.e., higher than the first one, makes sense, but when I submit to Kaggle, 0.78469, lower than the first one.

Third, I set n_iter = 1000, it gives me $\alpha_3$ and the cv score is 0.83951, i.e., higher than the second one, makes sense, but when I submit to Kaggle, 0.77990, lower than the second one.

Fourth, I set n_iter = 5000, it gives me $\alpha_4$ and the cv score is 0.84512, i.e., higher than the third one, makes sense, but when I submit to Kaggle, 0.72249, lower than the third one.

This is really frustrated. The model is getting better and better on the cross-validation score but when performed on an actual independent data set, its performance is getting worse and worse. Did I interpret the CV scores in the exactly opposite way? I see some paper mentioned that the CV score can be too optimistic for inferring the true test score. However, even if that is true, then I think the CV scores for all of my 4 models should be all optimistic about their own true test score, i.e., the order should preserve. But when applying on the real test data set, the order reversed.

The only reason I can imagine would be, that test data set has a different distribution than the training data set. However, if it is indeed the case, then I believe there is no method under then sun that can cure this problem.

First off, a pragmatic answer: don't discount the possibility that the test set comes from a somewhat different distribution than the data set you're using for training and cross-validation. You might think that shouldn't happen, but in practice it does seem to occur.

That said, let's go with your hypothetical and assume that the test set comes from exactly the same distribution as the rest of your data. In that case, it is possible for cross-validation to lead you astray about which model is better, if you're using cross-validation to select hyper-parameters.

You can use cross-validation to either (a) select hyper-parameters, or (b) estimate the accuracy of your model -- but not both at the same time.

It appears you're using cross-validation to select the optimal hyper-parameters: you try many different choices for the hyper-parameters, for each choice estimate accuracy of that choice using cross-validation, and select the best choice. When you do that, there's no guarantee that the resulting accuracy (with the best parameter) will be predictive of performance on the test set -- it might be an overestimate (due to overfitting). If it's more of an overestimate for M1 than M2, then you might see what you saw.

If you want to both select hyper-parameters and estimate accuracy, I suggest that you have a separate held-out validation set for estimating accuracy, or use nested cross-validation. See https://stats.stackexchange.com/q/65128/2921 and http://scikit-learn.org/stable/auto_examples/model_selection/plot_nested_cross_validation_iris.html.

• Do you know other more theoretical reference (from probability theory side) that explains why a nested CV is necessary than a plain CV for model selection? I want to understand the underlying mechanism that leads to the problem I had encountered – KevinKim Mar 25 '17 at 14:30
• I also suggest using nested cross-validation. if you're doing a 3-fold outer CV and a 10-fold inner CV, you'll get to test the 3 models you train during the inner CVs on three different datasets; that'll give you a better understanding of how your model building process will end up performing when it encounters different datasets. – darXider Mar 27 '17 at 13:43
• @darXider I've read some of the nested CV, it seems that it is used to compare 2 classes of models, e.g., RF and GBT such that in the inner CV, it chooses the "best" (lowest CV error) hyperparameters of RF and GBT respectively, then in the outer CV, it computes the generalzation error of RF and GBT with the hyperparameters chosen by the inner CV. In my case, I just have one class of model, GBT, I want to perform hyperparameter tunning. How does nested cv help me to do that? – KevinKim Mar 27 '17 at 15:42
• @KevinKim AFAIK, the goal of nested CV is to give an idea of how the model building process will generalize and not to compare different classes of models. As your ultimate goal is to use your trained model (whether RF or XGB) on future/unseen data, you might get a better understanding of its performance if you use nested CV. Of course, you also do hyperparameter tuning in your 3x10 nested CV; in the end, you'll get, say, 3 XGB models which are equivalent to each other (note that you should not choose one of three, but you can combine them, say, using various ensembling method). – darXider Mar 29 '17 at 14:28

can I claim or should I expect to see that M1 will still perform better than M2 over that new test data set?

Yes you should. Of course under the conditions that

1. the test data comes from the same generating process as the training and validation data, and
2. you have enough data in each set to make statistical fluctuations unlikely.

The model is getting better and better on the cross-validation score but when performed on an actual independent data set, its performance is getting worse and worse.

I can think of two reasons:

1. The test data set is indeed not generated in the same way. Therefore, it is better to not rely on the Kaggle test set to which you do not have access. Use the data that you do have.

2. You are over fitting, which means that you are not executing the cross validation correctly. Make really sure that the training of parameters happens on the training data and, at the same time, that the validation happens on the data that you did not use for the training. Compare the histograms of the training losses and the validation losses. The training losses should be consistently smaller than the validation losses. Do the same for the losses on the test data to get a consistent picture.

As and end note: It is to be expected, that the performance on the test set is lower than that on the validation set. This is because the model is chosen based on the validation set. So it is biased to that data set.

• I have the code in my post, I don't think I misused the CV procedure (did you find anything wrong with my code?). And I indeed saw that the training error is much less and stable (with small std) than the validation error. I understand that the true test error will be higher than the validation error but I expect this will also happen to all of my model (I mean XBGT with different value of the hyperparameters). From what I saw, it seems that some models this happens less than other models, which creates this "reverse phenomenon". So I don't know what direction I am searching to tune hyperpara – KevinKim Mar 29 '17 at 13:05
• I've seen many people suggest to break the $D$ into 3 parts, train, validation and test, and after tuning hyperP in the validation set, then apply the model on the test set to see how this model will perform on a real test (as the validation step also has some bias). Then after the test, stop tune the hyperP, as if you do, it will also starts to get bias (like in validation set). I get it. But if after the test set, I am still unsatisfied with the performance of my model, then what should I do? – KevinKim Mar 29 '17 at 13:09
• I think in practice, even though we are live in a "big data" world, the number of features is also increasing. As we have the curse of dimensional, it is very likely even we have a huge number of rows, still for each part of the feature space, we still have not enough data points. Then the statistical fluctuation is always there. Then I am questioning, whether this tune hyperP procedure is still correct or useful to get a model with good performance on real test data set? If CV is not useful to do this task, then what is the correct procedure? – KevinKim Mar 29 '17 at 13:14
• Verify if the training losses in your validation procedure are comparable with each other, i.e. consistent. If not, try another model/feature selection. Do not continue until you have this right. Then do the same thing for your validation losses. If these are not comparable, then try another model/feature selection/validation method. When they are, proceed to the test set. If the loss does not satisfy you there, then reject the complete procedure and try something else. If you start optimising using the test set, you cannot rely on the live performance, since it will be biased to the test set. – Ytsen de Boer Mar 30 '17 at 10:42

It is possible. Think of a simple scenario where model M1 has learnt the variance of the training dataset D better than model M2 since it's parameters are better tuned. This means M1 performs better at D than M2.

But when we test them at test set T, it is possible that M2 performs better as M1 might be overfitting D while M2 was not. Hence M1 performs worse at T than M2.

This might be due to the fact that you performed your cross validation on the same dataset instead of a validation set. If you train and validate at the same set, you are likely to miss the fact that it might be overfitting. Thus it is always better to train, validate and test at different sets of data. So flow should be

1. Train different models at same training set
2. Validated at validation set
3. Choose the best performing model basis performance at validation set
4. Use it to score your test set.
• I though the Cross validation on the data set D has already taken account the overfitting issues. I understand that if you don't do Cross validation at all, i.e., you just fit the model on the data set D and solve that optimization problem and get the optimal parameters, then this model will have the least train error and it is very likely an overfitting. In this case, I agree that this optimized model will tend perform bad on an independent test data set. But I think this issue has been taken cared of by cross validation on data set D, isn't it? – KevinKim Mar 23 '17 at 13:30
• Specifically, when you do a 10-fold CV on D, first you randomly chop D into roughly 10 equal size pieces, then in each iteration, you fit both M1 and M2 on the same 9/10 of D, then you applied them the same 1/10 of D to get your test error, then you repeat this process 10 times and each time, the train set and test set is different from the previous iteration. Then after 10 iterations, you average the test error for M1 and M2, then you find M1 has less test error, then isn't it enough to conclude that M1 is better than M2 and this procedure seems have already taken care of overfit – KevinKim Mar 23 '17 at 13:34
• Yes, it is enough to conclude that "M1 is better than M2". But, if your model selection procedure comes down to selecting M1 based on the validation performance, then your pick of best model (M1 in this case) is biased to the validation set. Hence the need for a final check on the test set, to get an indication of how well it will perform on live data. – Ytsen de Boer Mar 30 '17 at 10:45
• @YtsendeBoer I finally convinced myself about what you said. I agree. But then if on another independent test set, I found M1 is worse than M2 (recall M1 is better than M2 on the validation set), then in this case, should I choose M1 or M2 as my final model to do real prediction in the future? If I choose M1, then clearly the test result against M1. But if I choose M2, wouldn't it just M2 also overfitting on this specific test data set? i.e., the same way as M1 overfitting on the specific validation set? – KevinKim Apr 12 '17 at 2:45
• Yes, that is exactly why you should not do model selection on the test set. You have chosen M1 in your model selection procedure using the validation set. Then you run M1 on the test set and decide whether the result is good enough. Forget about M2 at this point, even if it happens to perform better on another test set. If, however, you have doubts about your results, then you should add your "other independent test set" to the the rest of your data (more data is better), start the procedure again and stick to it. – Ytsen de Boer Apr 12 '17 at 6:35

The theory behind cross validation ( v-fold cross validation) has been addressed in many papers. There is a proof for that in a set papers published from 2003-2007. Please refer to : - oracle selector. 2006 - super learner 2007 - super learner in prediction 2010 - unified cross validation 2003