I'm working on a binary classification task, and I've been running into problems generalizing from my cross-validation to my test set (model does great on cross validation, very poorly on test set).

I decided to try using some synthetic data to see if my tuning and validation procedure was reasonable. I thought that I should generate some fake, completely random data and if my methodology is sound, the cross-validation should NOT find any good models because, well, the data is random. So, I:

  1. Created a set of randomly generated data, 1 binary target variable, 10 features (from a normal distribution)
  2. Ran cross validation using k-NN (K-nearest neighbors) algorithm. I did grid-search hyperparameter tuning and feature selection simultaneously in cross validation (again, all columns of data are randomly generated from normal distribution)
  3. Compared best model found in CV to the baseline model (which predicts the same class every time).

What I found is that even though the data is totally randomly generated, I find that the "best" model that gives an accuracy of 60% on cross validation, when the baseline accuracy (on CV) is 55%.

How can I avoid this? I can't possibly rely on a cross validation if the model finds "patterns" in completely random data.

I would greatly appreciate any ideas or advice on this issue!

EDIT: My real dataset is about 700 rows, so I created my synthetic data to also have 700 rows. I decided to increase this dramatically to see if the problem persists, so I created a synthetic dataset of 10,000 rows and tried the above procedure again. The cross validation error was much closer to the baseline (52% vs. 51%). So it looks like initially, I really did try too many things on too little data and got lucky.

My question then becomes this: on my smaller dataset, what could I do to keep cross-validation useful? I mean, if it's going to overfit every time, how can I combat that to give a more reasonable model or error estimation?

Is the answer nested cross validation?

EDIT: I tried nested cross validation, and that's exactly what I needed to do. I forgot about the separation of model selection and model evaluation. K-fold cross validation provides a best model (model selection), but can't give an accurate estimation of that model's out-of-sample performance. So, with nested cross validation, I saw that no models selected through cross validation on this dataset was able to generalize to the test-sets, which is exactly what I expected.

Thank you all for your advice, discussions and responses.

  • $\begingroup$ How exactly do you create "randomly generated" data? $\endgroup$
    – whuber
    Feb 1, 2021 at 21:00
  • $\begingroup$ @whuber I used the R function rnorm() to draw 700 samples from a normal dist. with mean=0, sd=0.01. I then took shorter, slightly offset sets from those 700 points to create features. So, to be more clear: target_variable=setof_random_numbers[10:700] (converted to a binary 0/1 depending on if it's positive or negative), feature1=setof_random_numbers[9:699], feature2=setof_random_numbers[8:698] etc.. I don't see this being problematic, since a single sample/draw never appears twice in a row (since the sets are "offset" by 1). $\endgroup$ Feb 1, 2021 at 21:04
  • 1
    $\begingroup$ The features are definitely not independent! Why didn't you just draw independent random values for every entry in your data table? $\endgroup$
    – whuber
    Feb 1, 2021 at 21:47
  • 1
    $\begingroup$ +1 for the fact that you sanity-checked your approach to completely random data. That is a great idea! Also, part of the problem stems from well-known weaknesses of accuracy as an evaluation criterion. $\endgroup$ Feb 2, 2021 at 7:13
  • 1
    $\begingroup$ People speak of "probabilistic predictions", which they assess using proper scoring rules, one of which the log-loss is. $\endgroup$ Feb 2, 2021 at 14:31

1 Answer 1


From your description, everything seems to work "as designed".

  • Machine learning algorithms work by finding patterns in the data. The patterns are used to make such classifications that achieve the best value of cost function on the training data. If your data is random*, the better the performance on training set, the more your algorithm is finding spurious patterns and overfits it.
  • When you are using validation set for finding hyperparameters, this means that you are comparing performance of different models on validation set, and picking the one with best value of the validation set cost function. If in previous step you were choosing the model that potentially overfits the training data, here you are prone to choosing the model that overfits the validation set.
  • In the end, you are testing your model on the hold-out test set. This measures the overfitting, since the data was "not seen" by the model on either of the steps. If your model overfits, and on random data it can only perform poorly on training set, or overfit to it, test set metrics would help you with identifying it. If after looking at the test set metrics you decide to make improvements in your model, this can easily lead to cherry-picking and overfiting to test set.

There is no way of "fixing" this. The solution are standard machine learning procedures and tricks, like using cross validation, regularization, picking reasonable models for the task (e.g. not using neural networks when your data is small etc.). Other than that, you should always worry about overfitting and make sure it is not the case.

* - I assume in here, that by "random data" you mean that the values of features are random and unrelated to the classes, otherwise the answer it be more complicated.

  • $\begingroup$ So, are you saying that what is happening is simply that I am overfitting the validation sets? As in, I tried enough different things enough times that some of it happened to work considerably better than chance throughout my validation folds? (That's correct, my features are randomly generated numbers that are not in any way connected to my target variable). $\endgroup$ Feb 1, 2021 at 20:45
  • 1
    $\begingroup$ @VladimirBelik what else would you expect? If the data is "random" there's nothing to learn, you can only overfit. So the more models & hyperparametrs you try, the greater chance of finding some combination that overfits the validation set. $\endgroup$
    – Tim
    Feb 1, 2021 at 20:49
  • $\begingroup$ As mentioned in my question, my expectation was that cross validation would not find a model that performs considerably better than chance. I guess I'm just confused because this means that in cross validation, I literally can't distinguish a useful feature/feature-set from a completely irrelevant one. $\endgroup$ Feb 1, 2021 at 20:54
  • $\begingroup$ Maybe I don't understand the purpose of cross-validation - I thought the point was to provide a method to test different features/hyperparameters that was relatively robust to overfitting (since I'm not just using a single validation set). $\endgroup$ Feb 1, 2021 at 20:56
  • 1
    $\begingroup$ I understand, thank you. I forgot about the concept of separating model selection and evaluation - cross validation selects the best model, but doesn't provide an accurate estimate of its out-of-sample performance. I'm sorry I didn't make it clear in my question, but k-fold cross validation is exactly what I tried. $\endgroup$ Feb 2, 2021 at 14:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.