Cross validation procedure - is this right?

Just want to check that I am performing my cross validation procedures right. I'm using a non-linear svm. I do a five fold cross validation (5 splits of test/train on my original training data) and for each fold, run a grid search to find the optimal parameters for that train/test pair (e.g. best parameters where model is fitted on the training data then evaluated on the test data). After five iterations, for each parameter set (2 hyper-parameters), i have 5 fit measures. I just use the average of those 5 #s and find the parameter set with the best average. Does this sound correct? I'm pretty new to this so am not entirely aware of what other methods are there.

Additionally, was wondering a few more things: 1) Any way to make it faster? Cross validation + grid search is pretty computationally intensive. 2) Any other validation methods rather than k-fold (stratified I might add) cv? My data are timeseries so I was considering a moving window type validation, but wasn't sure. Any thoughts welcome.

I should add that I'm asking because my training fit (the average over the 5 cv folds) is still much better than my actual test data fit. I'm trying to figure out what might be causing this and the best way to reduce this difference. I realize increasing the # of folds may help though it also raises question 1) as well.

• Just to clarify, when you find the optimal parameters, are you taking the test data into account? If so, you shouldn't be. You should be optimizing the fit on your training sample, then calculating the fit on the test sample w/o any further optimization. Also, your training fit will typically be better, often much better, than your test fit, simply because the parameters optimize the fit on the training sample but not on the test sample. (Part of) the point of the cross-validation is to estimate how good the out-of-sample fit really is. Feb 10 '12 at 1:34
• I am not taking the test data into account. I hear what you're saying about the test vs train fit, it's just that difference is so wide (sometimes 4-5x better on the train data) i thought i might be doing something wrong. Feb 10 '12 at 14:27
• Wow, that's a lot, at least in my limited experience with SVM. What is your sample size? How many variables? Feb 10 '12 at 14:48
• My orig dataset is about 4700 examples. I use 700 for a test set so 4000 for my train. That 4000 is used in t5 fold x valid (so 800 test, 3200 train or so). I have a lot of features about 650. I'm wondering if I should use a few more folds for the validation because the optimal parameters for each fold can be quite different (so i think i have pretty large variance in the fit measure across folds). I haven't checked that specifically. I use python (scikits learn) so any speed up suggestions would also be great, esp if i increase the folds. Feb 10 '12 at 16:14
• 4-5x seems suspiciously large, I'd check the code very carefully. Another thing to consider is the partition of the data to form the test-training split. If there was originally some ordering in the dataset then you could end up with the training set full of "easy" samples and the test set full of "difficult" examples (random permutation of the data prior to partitioning should prevent that). I think a coding error (e.g. looking at the error on the training partition in each cross-validation fold rather than the test set? Made loads of errors of that sort over the years!). Jul 26 '16 at 8:52

Yes, the approach you are using is correct. As @halilpazarlama suggests the reason your cross-validation error is lower than the test error is indeed likely to be because you are over-fitting the cross-validation error. Essentially the cross-validation error is a performance estimator based on a finite same of data, and thus will have a (usually) non-negligible variance (i.e. if you ran the same experiment again with a different sample of data, you would get a slightly different minimum error and the minimum may well occur at different grid-point). Thus we can minimise the cross-validation error in two ways, ways that genuinely improve generalisation performance and ways that merely exploit the random sampling of the data to form the training data. I wrote a paper about this as it can be problematic if you have a large number of hyper-parameters to tune:

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

If you only have a few hyper-parameters to tune, this isn't usually too much of a problem, as long as you are aware that the minimum cross-validation error will be optimistically biased. If you need an unbiased (or at least less biased or pessimistically biased) estimate, then the thing to do is nested cross-validation, where the outer cross-validation estimates performance and the inner cross-validation is used to tune the hyper-parameters separately in each fold (see the paper for details). Basically tuning the hyper-parameters is part of the fitting of the model and needs to be cross-validated as well. Of course this is computationally even more expensive.

To reduce the computational expense, you could try using the Nelder-Mead simplex method for tuning the hyper-parameters instead of grid search, it is usually more efficient and doesn't need gradient information. Pattern search is another alternative. Another thing you can do to improve efficiency is to start the model for each grid point from the model found at the last grid point, instead of starting from scratch again (alpha seeding). Alternatively you could use a "regularisation path" type algorithm to learn each row (where the regularisation parameter is being changed with fixed kernel parameter) in one go.

If I understand you correctly, you are doing grid search for each test fold independently. If this is the case, your parameters might be (and probably are) overfitting to their respective test fold (let's call it the validation fold, since the 700 images are the test set), hence the big difference in your validation and test data.

One way to learn a more generalized model could be doing c.v. inside grid search (as opposed to grid search inside c.v.). In other words, you take one set of parameters, train and test your K models, measure the average performance, and select the best set of parameters, i.e. the one with smallest mean of K errors.

As you suggested in your comment, increasing K should make your model more accurate, but for the cost of increasing training time. Since in each set of parameters you will be doing K separate experiments. Usually 10 is considered a good compromise. Speeding up the training is depending on the computing platform you are using, and on the implementation of SVM. Maybe there are some parameters like an error threshold, or maximum number of iterations, needless to say using a coarser grid.

Hope it helps,

• I'm not sure I understand your second paragraph, how does it make a difference? Jul 26 '16 at 8:46
• @DikranMarsupial I just wanted to point out not to optimize the parameters for each fold separately, but I guess that would not be called cross validation anymore, so yes, it was unnecessary :)
– jeff
Jul 29 '16 at 21:47
• The parameters should be optimised separately for each fold as otherwise you end up with an optimistically biased performance estimate. Jul 30 '16 at 13:27
• But if you optimize parameters separately then you obtain with K different values of optimal parameters. How do you choose one model out of this?
– jeff
Jul 30 '16 at 13:45
• By fitting a model to the entire dataset. CV is a way of estimating the performance of a method for fitting a model, not of the model itself. Alternatively you could use an ensemble of the K cross-validated models. Jul 30 '16 at 13:46