Grid search on k-fold cross validation

Question

I've a dataset of 120 samples in a 10-fold cross validation setting. Currently, I pick the training data of the first holdout and do a 5-fold cross-validation on it to pick the values of gamma and C by grid search. I'm using SVM with RBF kernel. Since I'm doing a ten 10 cross-validation to report precision,recall, do I perform this grid search in the training data of each holdout (there are 10 holdouts, each having 10% test and 90% training data) ? Wouldn't that be too time consuming ?

If I use the gamma and C of the first holdout and use it for the rest of 9 holdouts of the k-fold cross-validation, is that a violation because I would have used the train data to get gamma and C and again use the portion of train data as test in second holdout ?

Answer 1

Yes, this would be a violation as the test data for folds 2-10 of the outer cross-validation would have been part of the training data for fold 1 which were used to determine the values of the kernel and regularisation parameters. This means that some information about the test data has potentially leaked into the design of the model, which potentially gives an optimistic bias to the performance evaluation, that is most optimistic for models that are very sensitive to the setting of the hyper-parameters (i.e. it most stongly favours models with an undesirable feature).

This bias is likely to be strongest for small datasets, such as this one, as the variance of the model selection criterion is largest for small datasets, which encourages over-fitting the model selection criterion, which means more information about the test data can leak through.

I wrote a paper on this a year or two ago as I was rather startled by the magnitude of the bias deviations from full nested cross-validation can introduce, which can easily swamp the difference in performance between classifier systems. The paper is "On Over-fitting in Model Selection and Subsequent Selection Bias in Performance Evaluation" Gavin C. Cawley, Nicola L. C. Talbot; JMLR 11(Jul):2079−2107, 2010.

Essentially tuning the hyper-parameters should be considered an integral part of fitting the model, so each time you train the SVM on a new sample of data, independently retune the hyper-parameters for that sample. If you follow that rule, you probably can't go too far wrong. It is well worth the computational expense to get an unbiased performance estimate, as otherwise you run the risk of drawing the wrong conclusions from your experiment.

Answer 2

After doing the grid search for each surrogate model, you can and should check a few things:

• variation of the optimized parameters (here $\gamma$ and $C$).
  Are the optimal parameters stable? If not, you're very likely in trouble.
• Compare the reported performance of the inner and outer cross validation.
  If the inner (i.e. tuning) cross validation looks much better than the outer (validation of the final model), then you're in trouble, too: you are overfitting. There is a substantial risk, that the tuned parameters are not optimal at all. However, if the outer cross validation is done properly (all test sets are truly independent of the respective surrogate models), then at least you still have an unbiased (!) estimate of the model's performance. But you cannot be sure that it is optimal.
• How pronounced is the optimum? Does the performance degrade quickly for suboptimal parameters? How good is the optimal performance?

There's a whole lot to say about overfitting by model selection. However, it is good to keep in mind that both variance and optimistic bias can really hurt

• variance means that you may accidentally end up quite far away from the truly optimal hyper-parameters.
• but also bias can hurt: if you are overfitting, you can run into situations where many models look perfect to the inner cross validation (but they aren't really). In that case, the tuning can go astray because it doesn't recognize the differences between the models.
• If the bias depends on the hyper-parameters, you are in big trouble.

If you are interested in an example and you can read German, I could put my Diplom thesis online.

In my experience, tuning hyperparameters is an extremely effective idea for overfitting...

Now, if you realize that you are overfitting, you have mainly two options:

• report that the optimization had a problem with overfitting but that you did a proper outer validation which resulted in ... (outer cross validation results).
• restrict the complexity of the model. One way of doing this is fixing hyper-parameters:

As an alternative to tuning the hyper-parameters to each training set, you could pre-specify (hyper)parameters (i.e. fix them beforehand). I do that as much as possible for my models as I usually have even fewer cases than you have, see below.
However, this fixing must really and honestly be done beforehand: e.g. I asked a colleague for his optimized parameters on a similar data set (independent experiment) or do a pre-experiment, including grid search on the parameters. That first experiment is then used to fix some experimental parameters as well as model parameters for the real experiment and data analysis. See below for further explanations.

Of course it is possible to do proper testing on automatically optimized models (double or nested validation), but your sample size may not allow splitting the data twice.
In that situation, it is IMHO much better to report an honest estimate for a model that was built using professional experience on how to choose modeling parameters than reporting an overoptimistic estimate on some kind of automatically optimized model.
Another point of view on the situation is that you have to trade off

• worse performance due to setting aside yet another bunch of cases for parameter optimization (smaller training sample size => worse model, but "optimal" parameters)
• worse performance due to suboptimal parameter fixing by the expert (but on larger training data).

Some similar thoughts on a similar question: https://stats.stackexchange.com/a/27761/4598

---

On the fixing of parameters and Dikran Marsupial's comments

I'm using the term hyper-parameters as Dikran Marsupial uses it in his paper (link in his answer)

I work with spectroscopic data. This is a kind of measurement where the data analysis and modelling often includes quite a bit of pre-processing. This can be seen as hyper-parameters (e.g. what order of polynomial should be used for the baseline? What measurement channels should be included?). There are other decisions that are closer to your svm parameters, e.g. how many principal components to use if a PCA is done for dimensionality reduction before the "real" model is trained? And sometimes I also use SVM classification, so I have to decide on SVM parameters.

Now, IMHO the best way to fix hyper-parameters is if you have reasons that come from the application. E.g. I usually decide on what kind of baseline to use by physical/chemical/biological reasons (i.e. knowledge about the specimen and the spectroscopic behaviour that follows from that). However, I'm not aware of such an argumentation which helps with SVM parameters...

The case of pre-experiments I mentioned above looks as follows:

• we take data of a bunch of cells (want to distinguish different cell lines).

• Spectra are analysed, iterated double cross validation SVM is run (spent a night or two on the computation server).

  • I observed that in the vast majoritiy of cases the same $\gamma$ and $C$ are selected as optimal. The remaining cases are a neighbour combination. This and other neighbour hyper-parameter combinations have very similar performance (one or two additional misclassifications)
  • I also observe a certain overfitting: the outer cross validation isn't quite as good as the tuning results. That is as expected.
  • Still, there are differences in performance over the tuning range of the hyper-parameters, and the performance over the tuning grid looks reasonably smooth. Good.

• My conclusion is: while I cannot be sure that the final hyper-parameters are optimal, the outer cross validation gives me a proper estimate of the performance of the surrogate models.

• During the experimental part, we decided on some changes in the experimental set-up (things that don't affect the signal to noise of the data, but that go one step further in automatization of the instrument)

• We improve the experimental settings and acquire new spectra. As cells are, they need to be grown freshly. I.e. the new data set are even independent culture batches.

Now I face the decision: Should I "skip" the inner cross validation and just go with the hyper-parameters I determined with the old data?

• As mentioned above, I run the risk that these pre-determined hyper-parameters are not optimal.
• But neither can I be sure to get truly optimal hyper-parameters by doing the inner (tuning) cross validation.
• However, the tuning on the old data was stable.
• Doing the optimization I'll train on less samples: As I have anyways Too Few Samples(TM) I have to expect to obtain worse models if I set more samples aside for a second round of cross validation.

So in that case, I decided to go with fixed parameters (by experience on similar data and knowing that in the future we'll have to do our "homework" including among other things re-checking these decisions with large data).

Note that the important thing is that I skip the inner (tuning cross validation), not the outer one. With fixed hyper-parameters I get an unbiased estimate of the performance of a possibly suboptimal model. It is true that this estimate is subject to high variance, but this variance is basically the same whether I do the inner tuning or not.
Skipping the outer cross vaidation I'd get an optimistically biased estimate of a tuned model - which depending on the application and data can be worthless (if very much overoptimistic) and optimistic bias may be plainly inacceptable.

Answer 3

You should fix $\gamma$ and $C$ initially. Then do $k$-fold cross validation to get a single test error estimate, $terr(\gamma,C)$. Then do a two-dimensional grid search, varying $\gamma$ and $C$ separately to generate a test error matrix. To speed things up people typically use a logarithmic grid, $\gamma,C \in \{ 2^{-n_l}, 2^{-n_l+1}, \dots, 2^{n_u}\}$ (usually $\gamma$ is on a smaller scale).

The key I think is to look for some smoothness in the surface around the local minimums (or each 1-dim projection) and not just take the global minimum.

Remember for Gaussian kernel SVMs $\gamma$ is like $(p\sigma)^{-1}$ parameter for Multivariate Normal data with $p$ independent components. So if you have an understanding of the variability of predictor distances it can help determine a grid for $\gamma$, especially if feature correlation is not too strong. $C$ is how much slack you get if there is no perfect separating plane so the weaker the relationship between the predictors and class labels the smaller in theory $C$ should be (less penalization for missclassification).