My machine learning finds patterns in literally random (generated) data, how to fix?

Question

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.

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.