# Grid search on k-fold cross validation

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 ?

• This question needs more information. What model are you fitting? What is gamma and C in this model? Further, could you give this information by editting the question, and not with comments. – probabilityislogic Aug 20 '12 at 0:30

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.

• My personal experience made me also very cautious about such sources of overfitting. – cbeleites unhappy with SX Aug 20 '12 at 10:56

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.

• sorry to have to downvote this answer, but using pre-specified values for the hyper-parameters is not good practice as optimal generalisation depends on appropriate settings for these parameters, which will vary from dataset to datset (and for problems will little data from sample to sample). A pre-experiment grid search is even worse as it results in exactly the same form of bias discussed in my paper. For SVMs the problem of spliting the data twice does not apply as you can use virtual leave-one-out cross-validation as the model selection criterion in the inner CV, almost for free. – Dikran Marsupial Aug 20 '12 at 11:54
• Checking for the variation in the optimised parameters however is an excellent suggestion. If you have enough data that the parameters and hyper-parameters can be reliably estimated from the data then the kinds of bias I mention in my paper probably won't be too much of an issue. However, if there is a lot of variability in the optimised hyper-parameter values, due to a small dataset, that is the sort of situation where nested cross-validation and other such rigorous approaches are really necessary to avoid substantial biases in performance estimation. – Dikran Marsupial Aug 20 '12 at 12:08
• @DikranMarsupial: I explained my background a bit more clearly, have a look. Also, I read your paper more thoroughly. I think our points are not that far apart. If you like, let's meet in the chat - I have a bunch of questions about your paper... – cbeleites unhappy with SX Aug 20 '12 at 19:26
• @DikranMarsupial: (unfortunately, for most of my data, I cannot use the analytical leave one out as I have nested/hierarachical data structures). Also, I've met some ugly surprises with leave-one-out so I do iterated k-fold or out-of-bootstrap validation. However, that's off-topic for this question. – cbeleites unhappy with SX Aug 20 '12 at 19:29
• @DikranMarsupial: If the optimized parameters are not stable, I'm in trouble anyways. Of course, then I cannot conclude that I can use these parameters for the new data. But also, I'd not call them (which of the many parameter sets?) optimal for the final model... I've seen optimization going completely wild but that always came along with very overoptimistic results of the inner (tuning) validation. And that I can measure by comparing the outer cross validation with the inner cross validation estimate of the optimal model. Updated the answer accordingly. – cbeleites unhappy with SX Aug 20 '12 at 19:35

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).

• So, let's say I've a dataset with 120 samples. Should I find gamma and C initially using 120 samples. Then do 10-fold cross validation using the same gamma and C for the k holdouts when using 90% of the data to train and 10% of the data to test ? Wouldn't it mean that I used the same training set to get gamma and C and part of the samples are also on test set ? – user13420 Aug 20 '12 at 3:47
• I don't understand what you mean by find gamma and C, these are tuning parameters. With Gaussian kernel SVMs you need to specify $\gamma$ and $C$ then solve for the weights. If you want to do 10-fold CV you should sample a 108 sample training set and 12 sample test set. Get your matrix of test errors then repeat with new train/test sets. This will result in 10 error estimates for each matrix value which you can average. – muratoa Aug 20 '12 at 3:59
• You have a choice in varying $(\gamma,C)$ per fixed train/test split, or varying the train/test splits per fixed $(\gamma,C)$. I suggest you vary $(\gamma,C)$ over fixed data because that will be computationally more efficient. Then you can just average the 10 matrices to get a final test error matrix. – muratoa Aug 20 '12 at 4:01
• There is a distinction; tuning parameters are reserved for data that must be input for a model to be fit. The "weights" are what the fitting procedure produces. In lasso/ridge for example $\lambda$ is a tuning parameter and $\beta$ are the weights. You are correct that all values are data derived, but the distinction is important for CV purposes. Tuning parameters are not random, weights are. That is the statistical reasoning behind test error for their selection. – muratoa Aug 20 '12 at 17:48
• In lasso/ridge $\lambda$ governs the variance of the prior distribution on $\beta$. For fixed $\lambda$ you hone in on the possible distribution for $\beta$. Each CV train set for fixed tuning parameter yields a point estimate of that $\beta(\lambda)$. By the end of the CV procedure you have an estimate of test error given that prior. You then vary the tuning parameters selecting the one with best test error properties. – muratoa Aug 20 '12 at 17:52