Overfitting the validation set

Question

I am referring to the Training / Validation / Test set for choosing a model while taking care of overfitting.

Here is how the argument goes:-

1. We train various models on the Training set. (This one is easy) Clearly if there is any noise in this data set, as we add features to the different models we will overfit to the noise in the Training set. This is clear to me.

2. Then we choose the best model on the Validation set. This will overfit the Validation set. This is not clear to me.

3. Because we have overfit the best model on the Validation set, to get a sense of the true error which the best model makes we should evaluate the best model on the test set.

My query is : When we are doing (2) we may overfit the validation set only if the validation set has the same noise as the Training set. However, we randomly shuffled the points and put them in the Training / Validation / Test set. It's very unlikely that the Training and Validation set have the same noise ( I think this phenomenon is called twinning). That is why I think we will not overfit the Validation set.

Also another instance when the Validation set can be overfit is if we have a HUGE number of high variance models, then when we choose the best one on the validation set, it will overfit to the noise in the validation set. Suppose I have only say 10 models, then this is also unlikely.

That is why I think that we don't need a test set. I think I have misunderstood this topic. Can someone please clarify where I am wrong?

My apologies for the delay in responding. I would like to clarify my query. We may aim to find the global optimum when using the validation set, however the contours of the functions which have been fit to the training set are not free to learn the noise in the validation set. That is what I am not convinced about. Can you please give me an example, where we overfit the training set and then overfit the validation set ? I'll give you one example. Suppose we are doing k-Nearest neighbours and every item in the training/validation set occurs exactly 2 times. Then we will overfit the training and validation sets and get k=1. The nearest neighbour will perfectly predict any chosen point. However, in this example, we have "twinning". The SAME noise exists in the training and validation set. Can you show me an example where we overfit the training and validation sets but without twinning.

Answer 1

One thing that is not widely appreciated is that over-fitting the model selection criteria (e.g. validation set performance) can result in a model that over-fits the training data or it can result in a model that underfits the training data.

This example is from my paper (with Mrs Marsupial)

Gavin C. Cawley, Nicola L. C. Talbot, "On Over-fitting in Model Selection and Subsequent Selection Bias in Performance Evaluation", Journal of Machine Learning Research, 11(70):2079−2107, 2010. (www)

Here is a heat-map for the model selection criteria for tuning the hyper-parameters of a Least-Squares Support Vector Machine (or Kernel Ridge Regression model) with different training & validation samples. The training set of 256 patterns is identical each time, but a new sample of 64 patterns is used for each validation set. The criterion is a smoothed error rate on the validation set. You can see there is considerable variation between splits in the optimal hyper-parameters (yellow crosses)

Here are the corresponding models, as you can see there is large variation in whether the models over- or under-fit the data.

If you set the hyper-parameters in the position shown in (d) you tend to get a sensible model for all training-test splits, which suggest the problem is in over-fitting the model selection criterion. In this case, as it is only the validation set that changes, we know this is purely due to over-fitting the validation set during model selection.

Consider a classification task, where there are 1000 binary features and one binary response variable, but they are all generated by flipping a fair coin. We then make ten models, each of which is given a disjoint set of 100 of the attributes. We form a training set of 10 patterns, a validation set of 10 patterns and a test set of 1,000,000 patterns. Note that the validation, test and training sets are entirely independent because all of the data is generated at random with no underlying structure.

• Each model generates it's output by picking the attribute that is most similar to the response variable for the training set out of the 100 attributes it has to choose from. If it is predicting a sequence of 10 random binary values using 100 similar sequences of 10 random variables, then it is highly likely to have an accuracy on the training set greater than 0.5, just by random chance. But we know the true optimal error rate of 0.5, so we know it is overfitting the training set.

• We then use the validation set to pick the best model. We will be picking the model that has the highest accuracy on the validation set. Now in this case, it is rather less likely that the best validation set accuracy will be greater than 0.5, but I would still say it is over-fitting the validation set because you would be choosing the model purely on the basis that the randomness of one of the models was a better match than the others for the randomness of the validation data.

• So what we will end up with is a model that obviously over-fits the training data (many degrees of freedom in selecting the attribute, so accuracy > 0.5), one that probably over-fits the validation data in the sense of accuracy > 0 (fewer degrees of freedom, only 10 models to choose from), but definitely overfits in the sense of the choice being dominated by the noise. But whatever the choice, the test set will show us that the final model is just guessing (which is why you need the test set or nested cross-validation)

The basic point is that if data has been used to optimise the model in any way, then it will give an optimistically biased performance estimate. How biased it is depends on how hard you try to optimise the model (how many feature choices, how many hyper-parameters, how fine a grid you use in gridsearch etc.) and the characteristics of the dataset. In some cases it is fairly benign:

Jacques Wainer, Gavin Cawley, "Nested cross-validation when selecting classifiers is overzealous for most practical applications", Expert Systems with Applications, Volume 182, 2021. (www)

Unfortunately, sometimes it can be as large as the difference in performance between a state of the art classifier and an average one (see Cawley and Talbot).

Answer 2

Choosing the best model is nothing but like hyper parameter optimization. We’re using training set to learn the parameters and validation set to learn the hyper parameters. In HPO, we typically evaluate the model on the candidate configurations and choose the best. In training, we use fancier stuff like gradient descent, adam optimizer etc. But still, they all aim to find the global optimum. What if we don’t use any of these fancier algorithms and just be able to iterate over the space of possible parameters? How is it different than what we do for the validation set? Thus, during the whole process we actually have a look at the training and validation sets and tune our model/algorithm. Any evaluation over these sets is not an unbiased estimation of the test performance.