Solved – Use of nested cross-validation

cross-validationmachine learningscikit learn

Scikit Learn's page on Model Selection mentions the use of nested cross-validation:

>>> clf = GridSearchCV(estimator=svc, param_grid=dict(gamma=gammas),
  ...                    n_jobs=-1)  
>>> cross_validation.cross_val_score(clf, X_digits, y_digits)
Two cross-validation loops are performed in parallel: one by the GridSearchCV estimator to set gamma and the other one by cross_val_score to measure the prediction performance of the estimator. The resulting scores are unbiased estimates of the prediction score on new data.

From what I understand, clf.fit will use cross-validation natively to determine the best gamma. In that case, why would we need to use nested cv as given above? The note mentions that nested cv produces "unbiased estimates" of the prediction score. Isn't that also the case with clf.fit?

Also, I was unable to get the clf best estimates from the cross_validation.cross_val_score(clf, X_digits, y_digits) procedure. Could you please advise how that can be done?

Best Answer

Nested cross-validation is used to avoid optimistically biased estimates of performance that result from using the same cross-validation to set the values of the hyper-parameters of the model (e.g. the regularisation parameter, $C$, and kernel parameters of an SVM) and performance estimation. I wrote a paper on this topic after being rather alarmed by the magnitude of the bias introduced by a seemingly benign short cut often used in the evaluation of kernel machines. I investigated this topic in order to discover why my results were worse than other research groups using similar methods on the same datasets, the reason turned out to be that I was using nested cross-validation and hence didn't benefit from the optimistic bias.

G. C. Cawley and N. L. C. Talbot, Over-fitting in model selection and subsequent selection bias in performance evaluation, Journal of Machine Learning Research, 2010. Research, vol. 11, pp. 2079-2107, July 2010. (http://jmlr.org/papers/volume11/cawley10a/cawley10a.pdf)

The reasons for the bias with illustrative examples and experimental evaluation can be found in the paper, but essentially the point is that if the performance evaluation criterion is used in any way to make choices about the model, then those choices are based on (i) genuine improvements in generalisation performance and (ii) the statistical peculiarities of the particular sample of data on which the performance evaluation criterion is evaluated. In other words, the bias arises because it is possible (all too easy) to over-fit the cross-validation error when tuning the hyper-parameters.

Related Solutions

Solved – Having trouble understanding cross-validation results from scikit-learn

From section 7.10.2 of Elements of Statistical Learning(free online, and it's great):

Consider a classification problem with a large number of predictors, as may arise, for example, in genomic or proteomic applications. A typical strategy for analysis might be as follows:

Screen the predictors: find a subset of “good” predictors that show fairly strong (univariate) correlation with the class labels
Using just this subset of predictors, build a multivariate classifier.
Use cross-validation to estimate the unknown tuning parameters and to estimate the prediction error of the final model.

Is this a correct application of cross-validation? Consider a scenario with N = 50 samples in two equal-sized classes, and p = 5000 quantitative predictors (standard Gaussian) that are independent of the class labels. The true (test) error rate of any classifier is 50%. We carried out the above recipe, choosing in step (1) the 100 predictors having highest correlation with the class labels, and then using a 1-nearest neighbor classifier, based on just these 100 predictors, in step (2). Over 50 simulations from this setting, the average CV error rate was 3%. This is far lower than the true error rate of 50%.

What has happened? The problem is that the predictors have an unfair advantage, as they were chosen in step (1) on the basis of all of the samples. Leaving samples out after the variables have been selected does not cor-rectly mimic the application of the classifier to a completely independent test set, since these predictors “have already seen” the left out samples.

We selected the 100 predictors having largest correlation with the class labels over all 50 samples. Then we chose a random set of 10 samples, as we would do in five-fold cross-validation, and computed the correlations of the pre-selected 100 predictors with the class labels over just these 10 samples (top panel). We see that the correlations average about 0.28, rather than 0, as one might expect

Solved – How to get hyper parameters in nested cross validation

(I'm sure I wrote most of this already in some answer - but can't find it right now. If anyone stumbles across that answer, please link it). I see 2 slightly different approaches here, which I think are both sensible.

But first some terminology:

Coming from an applied field, a (fitted/trained) model for me is a ready-to-use. I.e. the model contains all information needed to generate predictions for new data. Thus, the model contains also the hyperparameters. As you will see, this point of view is closely related to approach 2 below.
OTOH, training algorithm in my experience is not well defined in the following sense: in order to get the (fitted) model, not only the - let's call it "primary fitting" - of the "normal" model parameters needs to be done, but also the hyperparameters need to be fixed. From my application perspective, there isn't really much difference between parameters and hyperparamers: both are part of the model, and need to be estimated/decided during training.
I guess the difference between them is related to the difference between someone developing new training algorithms who'd usually describe a class of training algorithms together with some steering parameters (the hyperparameters) which are difficult/impossibe to fix (or at least to fix how they should be decided/estimated) without application/domain knowledge.

Approach 1: require stable optimization results

With this approach, "model training" is the fitting of the "normal" model parameters, and hyperparameters are given. An inner e.g. cross validation takes care of the hyperparameter optimization.

The crucial step/assumption here to solve the dilemma of whose hyperparameter set should be chosen is to require the optimization to be stable. Cross validation for validation purposes assumes that all surrogate models are sufficiently similar to the final model (obtained by the same training algorithm applied to the whole data set) to allow treating them as equal (among themselves as well as to the final model). If this assumption breaks down and

the surrogate models are still equal (or equivalent) among themselves but not to the final model, we are talking about the well-known pessimistic bias of cross validation.
If also the surrogate model are not equal/equivalent to each other, we have problems with instability.

For the optimization results of the inner loop this means that if the optimization is stable, there is no conflict in choosing hyperparameters. And if considerable variation is observed across the inner cross validation results, the optimization is not stable. Unstable training situations have far worse problems than just the decision which of the hyperparameter sets to choose, and I'd really recommend to step back in that case and start the modeling process all over.

There's an exception, here, though: there may be several local minima in the optimization yielding equal performance for practical purposes. Requiring also the choice among them to be stable may be an unnecessary strong requirement - but I don't know how to get out of this dilemma.

Note that if not all models yield the same winning parameter set, you should not use outer loop estimates as generalization error here:

If you claim generalization error for parameters $p$, all surrogate models entering into the validation should actually use exactly these parameters.
(Imagine someone told you they did a cross validation on model with C = 1 and linear kernel and you find out some splits were evaluated with rbf kernel!)
But unless there is no decision involved as all splits yielded the same parameters, this will break independence in the outer loop: the test data of each split already entered the decision which parameter set wins as it was training data in all other splits and thus used to optimize the parameters.

Approach 2: treat hyperparameter tuning as part of the model training

This approach bridges the perspectives of the "training algorithm developer" and applied user of the training algorithm.

The training algorithm developer provides a "naked" training algorithm model = train_naked (trainingdata, hyperparameters). As the applied user needs tunedmodel = train_tuned (trainingdata) which also takes care of fixing the hyperparameters.

train_tuned can be implemented e.g. by wrapping a cross validation-based optimizer around the naked training algorithm train_naked.

train_tuned can then be used like any other training algorithm that does not require hyperparameter input, e.g. its output tunedmodel can be subjected to cross validation. Now the hyperparameters are checked for their stability just like the "normal" parameters should be checked for stability as part of the evaluation of the cross validation.

This is actually what you do and evaluate in the nested cross validation if you average performance of all winning models regardless of their individual parameter sets.

What's the difference?

We possibly end up with different final models taking those 2 approaches:

the final model in approach 1 will be train_naked (all data, hyperparameters from optimization)
whereas approach 2 will use train_tuned (all data) and - as that runs the hyperparameter optimization again on the larger data set - this may end up with a different set of hyperparameters.

But again the same logic applies: if we find that the final model has substantially different parameters from the cross validation surrogate models, that's a symptom of assumption 1 being violated. So IMHO, again we do not have a conflict but rather a check on whether our (implicit) assumptions are justified. And if they aren't, we anyways should not bet too much on having a good estimate of the performance of that final model.

I have the impression (also from seeing the number of similar questions/confusions here on CV) that many people think of nested cross validation doing approach 1. But generalization error is usually estimated according to approach 2, so that's the way to go for the final model as well.

Iris example

Summary: The optimization is basically pointless. The available sample size does not allow distinctions between the performance of any of the parameter sets here.

From the application point of view, however, the conclusion is that it doesn't matter which of the 4 parameter sets you choose - which isn't all that bad news: you found a comparatively stable plateau of parameters. Here comes the advantage of the proper nested validation of the tuned model: while you're not able to claim that the it is the optimal model, your're still able to claim that the model built on the whole data using approach 2 will have about 97 % accuracy (95 % confidence interval for 145 correct out of 150 test cases: 92 - 99 %)

Note that also approach 1 isn't as far off as it seems - see below: your optimization accidentally missed a comparatively clear "winner" because of ties (that's actually another very telltale symptom of the sample size problem).

While I'm not deep enough into SVMs to "see" that C = 1 should be a good choice here, I'd go with the more restrictive linear kernel. Also, as you did the optimization, there's nothing wrong with choosing the winning parameter set even if you are aware that all parameter sets lead to practically equal performance.

In future, however, consider whether your experience yields rough guesstimates of what performance you can expect and roughly what model would be a good choice. Then build that model (with manually fixed hyperparameters) and calculate a confidence interval for its performance. Use this to decide whether trying to optimize is sensible at all. (I may add that I'm mostly working with data where getting 10 more independent cases is not easy - if you are in a field with large independent sample sizes, things look much better for you)

long version:

As for the example results on the iris data set. iris has 150 cases, SVM with a grid of 2 x 2 parameters (2 kernels, 2 orders of magnitude for the penalty C) are considered.

The inner loop has splits of 129 (2x) and 132 (6x) cases. The "best" parameter set is undecided between linear or rbf kernel, both with C = 1. However, the inner test accuracies are all (including the always loosing C = 10) within 94 - 98.5 % observed accuracy. The largest difference we have in one of the splits is 3 vs. 8 errors for rbf with C = 1 vs. 10.

There's no way this is a significant difference. I don't know how to extract the predictions for the individual cases in the CV, but even assuming that the 3 errors were shared, and the C = 10 model made additional 5 errors:

> table (rbf1, rbf10)
         rbf10
rbf1      correct wrong
  correct     124     5
  wrong         0     3

> mcnemar.exact(rbf1, rbf10)

    Exact McNemar test (with central confidence intervals)

data:  rbf1 and rbf10
b = 5, c = 0, p-value = 0.0625
alternative hypothesis: true odds ratio is not equal to 1

Remember that there are 6 pairwise comparisons in the 2 x 2 grid, so we'd need to correct for multiple comparisons as well.

Approach 1

In 3 of the 4 outer splits where rbf "won" over the linear kernel, they actually had the same estimated accuracy (I guess min in case of ties returns the first suitable index).

Changing the grid to params = {'kernel':['linear', 'rbf'],'C':[1,10]} yields

({'kernel': 'linear', 'C': 1}, 0.95238095238095233, 0.97674418604651159)
({'kernel': 'rbf', 'C': 1}, 0.95238095238095233, 0.98449612403100772)
({'kernel': 'linear', 'C': 1}, 1.0, 0.97727272727272729)
({'kernel': 'linear', 'C': 1}, 0.94444444444444442, 0.98484848484848486)
({'kernel': 'linear', 'C': 1}, 0.94444444444444442, 0.98484848484848486)
({'kernel': 'linear', 'C': 1}, 1.0, 0.98484848484848486)
({'kernel': 'linear', 'C': 1}, 1.0, 0.96212121212121215)

Approach 2:

Here, clf is your final model. With random_state = 2, rbf with C = 1 wins:

In [310]: clf.grid_scores_
[...snip warning...]
Out[310]: 
[mean: 0.97333, std: 0.00897, params: {'kernel': 'linear', 'C': 1},
 mean: 0.98000, std: 0.02773, params: {'kernel': 'rbf', 'C': 1},
 mean: 0.96000, std: 0.03202, params: {'kernel': 'linear', 'C': 10},
 mean: 0.95333, std: 0.01791, params: {'kernel': 'rbf', 'C': 10}]

(happens about 1 in 5 times, 1 in 6 times linear and rbf with C = 1 are tied on rank 1)