Can you overfit by training machine learning algorithms using CV/Bootstrap?

This question may well be too open ended to get a definitive answer, but hopefully not.

Machine learning algorithms, such as SVM, GBM, Random Forest etc, generally have some free parameters that, beyond some rule of thumb guidance, need to be tuned to each data set. This is generally done some kind of re-sampling technique (bootstrap, CV etc) in order to fit the set of parameters that give the best generalisation error.

My question is, can you go too far here? People talk about doing grid searches as so forth, but why not simply treat this as an optimisation problem and drill down to the best possible set of parameters? I asked about some mechanics of this in this question, but it hasn't received much attention. Maybe the question was badly asked, but perhaps the question itself represents a bad approach that people generally do not do?

What bothers me is the lack of regularisation. I might find by re-sampling that that best number of trees to grow in a GBM for this data set is 647 with an interaction depth of 4, but how sure can I be that this will be true of new data (assuming the new population is identical to the training set)? With no reasonable value to 'shrink' to (or if you will, no informative prior information) re-sampling seems like the best we can do. I just don't hear any talk about this, so it makes me wonder if there is something I'm missing.

Obviously there is a large computational cost associated with doing many many iterations to squeeze every last but of predictive power out of a model, so clearly this is something you would do if you've got the time/grunt to do the optimisation and every bit of performance improvement is valuable.

-

There is a definitive answer to this question which is "yes, it is certainly possible to overfit a cross-validation based model selection criterion and end up with a model that generalises poorly!". In my view, this appears not to be widely appreciated, but is a substantial pitfall in the application of machine learning methdos, and is the main focus of my current research; I have written two papers on the subject so far

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

which demonstrates that over-fitting in model selection is a substantial problem in machine learning (and you can get severly biased performance estimates if you cut corners in model selection during performance exvaluation) and

G. C. Cawley and N. L. C. Talbot, Preventing over-fitting in model selection via Bayesian regularisation of the hyper-parameters, Journal of Machine Learning Research, volume 8, pages 841-861, April 2007. (www)

where the cross-validation based model selection criterion is regularised to try an ameliorate over-fitting in model selection (which is a key problem if you use a kernel with many hyper-parameters).

I am writing up a paper on gid-search based model selection at the moment, which shows that it is certainly possible to use a grid that is too fine where you end up with a model that is statistically inferior to a model selected by a much coarser grid (it was a question on StackExchange that inspired me to look into grid-search).

Hope this helps.

P.S. Unbiased performance evaluation and reliable model selection can indeed be computationally expensive, but in my experience it is well worthwhile. Nested cross-validation, where the outer cross-validation is used for performance estimation and the inner crossvalidation for model selection is a good basic approach.

-
Perfect! Looks like those papers are exactly what I was after. Thanks for that. – Bogdanovist May 29 '12 at 12:07
Do let me know if you have any questions about the papers (via email - I am the first author and my email address is on the paper). – Dikran Marsupial May 29 '12 at 13:22
@DikranMarsupial How do you distinguish overfitting due to model selection and that due to sampling mismatch between train and test sets ? – image_doctor May 29 '12 at 13:41
In principle, using a synthetic dataset where ground truth is available, then it is straight-forward, as there is then no sampling mismatch; the training set is just a random sample from the underlying distribution and you can estimate the error from the distribution itself, rather than a finite sample. For real-word datasets, however AFAICS the best you can manage is to use resampling and determine the effects of over-fitting the model selection criterion over many random test/training splits. – Dikran Marsupial May 29 '12 at 13:53
Good question and good answer. Model selection always creates a problem because of repeated testing if nothing else. Penalized likelihood methods can be used to deal with the overfitting problem. As far as multiple testing goes methods that control FWER or FDR can be applied. – Michael Chernick May 29 '12 at 14:11

Yes, the parameters can be „overfitted” onto training and test set during crossvalidation or bootstrapping. However, there are some methods to prevent this. First simple method is, you divide your dataset into 3 partitions, one for testing (~20%), one for testing optimized parameters (~20%) and one for fitting the classifier with set parameters. It is only possible if you have quite large dataset. In other cases double crossvalidation is suggested.

Romain François and Florent Langrognet, "Double Cross Validation for Model Based Classification", 2006

-

It strongly depends on the algorithm, but you certainly can -- though in most cases it will be just a benign waste of effort.

The core of this problem is that this is not a strict optimization -- you don't have any $f(\mathbf{x})$ defined on some domain which simply has an extremum for at least one value of $\mathbf{x}$, say $\mathbf{x}_{\text{opt}}$, and all you have to do is to find it. Instead, you have $f(\mathbf{x})+\epsilon$, where $\epsilon$ has some crazy distribution, is often stochastic and depends not only on $\mathbf{x}$, but also your training data and CV/bootstrap details. This way, the only reasonable thing you can search for is some subspace of $f$s domain, say $X_\text{opt}\ni \textbf{x}_\text{opt}$, on which all the values of $f+\epsilon$ are insignificantly different (statistically speaking, if you wish).

Now, while you can't find $\textbf{x}_\text{opt}$, in practice any value from $X_\text{opt}$ will do -- and usually it is just a search grid point from $X_\text{opt}$ selected at random, to minimize computational load, to maximize some sub-$f$ performance measure, you name it.

The serious overfitting can happen if the $f$ landscape has a sharp extrema -- yet, this "shouldn't happen", i.e. it is a characteristic of very badly selected algorithm/data pair and a bad prognosis for the generalization power.

Thus, well, (based on a practices present in good journals) full, external validation of parameter selection is not something you rigorously have to do (unlike validating feature selection), but only if the optimization is cursory and the classifier is rather insensitive to the parameters.

-

I suspect one answer here is that, in the context of optimisation, what you are trying to find is a global minimum on a noisy cost function. So you have all the challenges of a multi-dimensional global optimistation plus a stochastic component added to the cost function.

Many of the approaches to deal with challenges of local minima and an expensive search space themselves have parameters which may need tuning, such as simulated annealing or monte carlo methods.

In an ideal, computationally unbounded universe, I suspect you could attempt to find a global minimum of your parameter space with suitably tight limits on the bias and variance of your estimate of the error function. Is this scenario regularisation wouldn't be an issue as you could re-sample ad infinitum.

In the real world I suspect you may easily find yourself in a local minimum.

As you mention, it is a separate issue, but this still leaves you open to overfitting due to sampling issues associated with the data available to you and it's relationship to the real underlying distribution of the sample space.

-

Cross validation and bootstrap have been shown to give estimates of error rate that are nearly unbiased and in some cases more accurately by the bootstrap over cross-validation. The problem with other methods like resubstitution is that by estimating error on the same data set that you fit the classifier with you can grossly underestimate the error rate and may be led to algorithms that include too many parameters and will not predict future values as accurately as an algorithm fit to a small set of parameters. The key to the use of statistical methods is that the data you have totrain the classifier is typical of the data you will see in the future where the classes are missing and must be predicted by the classifier. If you think that the future data could be very different then statistical methods can't help and I don't know what could.

-
Thanks for the answer. I've edited the question to make it clear that I'm not asking about changes in the population between train and test sets. I realise that is a whole different question that I am not interested in for this question. – Bogdanovist May 29 '12 at 3:29
+1 In this case unbiaseness is essentially irrelevant. The variance of the cross-validation estimate can be much more of a problem. For a model selection criterion you need the minimum of the criterion to be reliably close to the minimum of the generalisation error (as a function of the hyper-parameters). It is of no use if on average it is in the right place, but the spread of the minima fror different finite samples of data is all over the place. – Dikran Marsupial May 29 '12 at 11:40
Of course accuracy is a combination of bias and variance and an unbiased estimate with a large variance is not as good as a slightly biased estimator with a small variance. The niave estimate of error rate is resubstitution and it has a large bias. The bootstrap 632 and 632+ work so well because they do a good job adjusting for the bias without much increase in variance. That is why for linear discriminant functions and quadratic discriminant functions they work much better than the leave-one-out version of cross-validation. – Michael Chernick May 29 '12 at 14:05
With classification tree ensembles the bootstrap has not been demonstrated to do better. – Michael Chernick May 29 '12 at 14:05
Perhaps one of the difficulties is that over-fitting often means different things in machine learning and statistics. It seems to me that statisticians sometimes use over-fitting to mean a model with more parameters than necessary is being used, rather than it being fit too closesly to the observations (as measured by the training criterion). I would normally use "over-parameterised" in that situation, and use "over-fit" to mean a model has been fitted too closely to the observations at the expense of generalisation performance. Perhaps this is where we may be talking at cross-purposes? – Dikran Marsupial May 29 '12 at 16:15