Can SVM overfit even with cross-validation?

Question

I am using SVM regressor models to fit some chemical data related to spectroscopy (I cannot say exactly what data because it is an ongoing research in my group). To combat overfitting, I have used 5-fold cross validation to optimise the hyperparameters with SVM (and other models). The best result is given by SVM.

However, if you look at the plot of SVM predictions vs true values, it looks suspiciously like a case of overfitting.

The hyperparameters that I got after optimizing the average 5-fold cross-validation error are C=1000 and gamma=0.0001 for SVM (I am using scikit-learn). From what I can understand, high value of C and low value of gamma means SVM is going to learn every minute detail from the dataset.

I also had an additional holdout test set (apart from the cross-validation) where I got slightly higher error.

I have two related questions:

1. Does this look like a case of overfitting? Are there additional tests I can do to check?
2. Can overfitting happen even with using cross-validation for hyperparameter optimisation?

Answer 1

Yes, it certainly is possible because you can over-fit the cross-validation statistic when optimising the hyper-parameters. See

GC Cawley, NLC Talbot, "On over-fitting in model selection and subsequent selection bias in performance evaluation", The Journal of Machine Learning Research 11, 2079-2107 (pdf)

[Full disclosure, this paper was written by Mrs Marsupial and I]

For different samples of data, the cross-validation error as a function of the hyper-parameters will be different, due to random variations in the sampling, and have different minima:

Which can give rise to models that either under- or over-fit the training data (or give good fits):

The best solution is to have more data. That makes the variance of the cross-validation estimator lower and improves estimation of the hyper-parameters.

This example uses the Least-Squares Support Vector Machine, for convenience, but the standard SVM does pretty much the same thing. The same thing also happens in a regression setting. I haven't tried it for SVM regression (because I don't like it very much), but it has been demonstrated for Gaussian Processes, which are likely to be a better option if the dataset isn't too large.

Rekar O Mohammed, Gavin C Cawley, "Over-fitting in model selection with Gaussian process regression", International Conference on Machine Learning and Data Mining in Pattern Recognition, Pages 192-205, 2015 (pdf)

Answer 2

Does this look like a case of overfitting?

yes: your training data for the final (optimized) model is fit well, but the generalization performance as estimated by the holdout set is substantially worse.

 Are there additional tests I can do to check?

yes.

• @DikranMarsupial mentioned nested CV
• an alternative is repeated CV already during your hyperparameter optimization since that allows you to detect instability in the predictions already during your hyperparameter optimization.
  (See e.g. our paper Beleites, C. & Salzer, R.: Assessing and improving the stability of chemometric models in small sample size situations, Anal Bioanal Chem, 390, 1261-1271 (2008). DOI: 10.1007/s00216-007-1818-6)
• you can combine these approaches and do nested repeated CV

Can overfitting happen even with using cross-validation for hyperparameter optimisation?

Yes.

The reason behind this is typically what I call variance skimming: The performance estimate you get via the CV (or any other test-set-based procedure) has variance uncertainty due to testing only a limited number of cases. (This variance is particularly bad for some widely used figures of merit such as classification accuracy, regression figures of merit such as MSE or RMSE typically do better, but are still affected by this)

So, the figure of merit you compute differs by some random amount from the true performance of the model in question. If you now compare a large number of models (with varying hyperparameters), you run into what is essentially a multiple-comparison problem: the chances increase that some CV split/hyperparameter combination accidentally looks much better than it actually is.

You'll want to avoid this, i.e. you need a more sophisticated optimization heuristic than just "pick the apparently best". An improved heuristic would be "fit the least complex model that is not too much worse than the apparent optimium". The one-standard-deviation rule (see e.g. the Elements of Statistical Learning) is one such heuristic.

This is particularly helpful when the "error landscape" for the training algorithm in question basically has the minimum open towards high complexity, such as seen in @DikranMarsupial's figure 5.