# Bonferroni Correction & machine learning

In psychology studies I learned that we should use the Bonferroni method to adjust the significance level when testing several hypothesis on a single dataset.

Currently I am working with machine learning methods such as Support Vector Machines or Random Forest for classification. Here I have a single dataset which is used in crossvalidation to find the best parameters (such as kernel parameters for SVM) yielding the best accuracy.

My intuition says (and maybe is completely off) that it is a similiar issue. If I am testing too many possible parameter combinations, the chance is high that I find one which yields great results. Yet this could be just chance.

To sum up my question:

In machine learning we use crossvalidation for finding the right parameters of a classifier. The more parameter combinations we use, the higher the chance to find a great one by accident (overfitting?). Does the concept that is behind bonferroni correction also apply here? Is it a different issue? If so, why?

• Yes, it is the same issue, sometimes called "data dredging." – dsaxton Oct 19 '16 at 19:21
• you must torture data until it confesses – Soren Havelund Welling Oct 20 '16 at 9:08

There is a degree to which what you are talking about with p-value correction is related, but there are some details that make the two cases very different. The big one is that in parameter selection there is no independence in the parameters you are evaluating or in the data you are evaluating them on. For ease of discussion, I will take choosing k in a K-Nearest-Neighbors regression model as an example, but the concept generalizes to other models as well.

Lets say we have a validation instance V that we are predicting to get an accuracy of the model in for various values of k in our sample. To do this we find the k = 1,...,n closest values in the training set which we will define as T1, ... ,Tn. For our first value of k = 1 our prediction P11 will equal T1, for k=2, prediction P2 will be (T1 + T2)/2 or P1/2 + T2/2, for k=3 it will be (T1 + T2 + T3)/3 or P2*2/3 + T3/3. In fact for any value k we can define the prediction Pk = Pk-1(k-1)/k + Tk/k. We see that the predictions are not independant of each other so therefore the accuracy of the predictions won't be either. In fact, we see that the value of the prediction is approaching the mean of the sample. As a result, in most cases testing values of k = 1:20 will select the same value of k as testing k = 1:10,000 unless the best fit you can get out of your model is just the mean of the data.

This is why it is ok to test a bunch of different parameters on your data without worrying too much about multiple hypothesis testing. Since the impact of the parameters on the prediction isn't random, your prediction accuracy is much less likely to get a good fit due solely to chance. You do have to worry about over fitting still, but that is a separate problem from multiple hypothesis testing.

To clarify the difference between multiple hypothesis testing and over fitting, this time we will imagine making a linear model. If we repeatedly resample data for to make our linear model (the multiple lines below) and evaluate it, on testing data (the dark points), by chance one of the lines will make a good model (the red line). This is not due to it actually being a great model, but rather that if you sample the data enough, some subset will work. The important thing to note here is that the accuracy looks good on the held out testing data because of all the models tested. In fact since we are picking the "best" model based on the testing data, the model may actually fit the testing data better than the training data. Over fitting on the other hand is when you build a single model, but contort the parameters to allow the model to fit the training data beyond what is generalizeable. In the example below the the model (line) perfectly fits the training data (empty circles) but when evaluated on the testing data (filled circles) the fit is far worse. • Nice argument for this particular situation of choosing k – Soren Havelund Welling Oct 20 '16 at 8:56
• This isn't specific to K-Nearest-Neighbors, I just picked that model because the math is easier to see. In every model the validation errors produced by a range parameters (which is what cross-validation is about) are not independent of each other. This means that the idea of a Bonferroni correction which seeks to correct p-values in multiple testings of independent samples does not apply. – Barker Oct 20 '16 at 16:38
• In the case of performing a huge grid search with numerous of combinations of hyper parameters, a slightly over fitted model is most likely to come out best, defined by some squared residuals loss function, at it happen to explain the validation set well + being lucky. A slightly over regularized model is unlikely to be as lucky because of bias. Unlike kNN, some models as decision trees, can yield very different fits by small changes in the hyper parameters, and if testing many different trees... Therefore over fitted models and multiple parameter testing can be related in practice. – Soren Havelund Welling Nov 1 '16 at 9:24
• Decision tree models that get very different results based on small parameter changes generally indicate that the model is not stable and that a different choice of random seed could be equally well to blame as the parameters themselves. I would consider this more an issue of stability than fit per say. – Barker Nov 1 '16 at 18:59
• Exactly. For many model algorithms for given data set a range of parameters settings yield unstable models. A small subset of these unstable models are likely to get a better prediction score on one specific validation set, than the reasonable regularized models. This is why you do have to consider the implications of multiple testing in machine learning also, and cannot simply rely on conclusion of the kNN example, where it is not much of a problem. – Soren Havelund Welling Nov 2 '16 at 12:33

I agree with Barker to some extend, however model selection is not only kNN. You should use cross-validation scheme, with both a validation and a test set. You use the validation set for model selection and the test set for final estimation of the model error. It could be nested k-fold CV or simple split of the training data. The measured performance by the validation set of the best performing model will be biased, as you cherry picked the best performing model. The measured performance of the test set is not biased, as you honestly only tested one model. Whenever in doubt, wrap you entire data processing and modeling in an outer cross validation to get the least biased estimation of future accuracy.

As I know of, there are no reliable simple math correction that would suit any selection between multiple non-linear models. We tend to rely on brute force bootstrapping to simulate, what would be the future model accuracy. By the way when estimating future prediction error, we assume the training set was sampled randomly from a population, and that future test predictions are sampled from the same population. If not, well who knows...

If you e.g. use an inner 5-fold CV to select model and an outer 10-fold CV repeated 10 times to estimate error, then you're unlikely to fool yourself with an overconfident model accuracy estimate.

• some times the validation set may be named calibration set, and the test set named validation set. A little confusing... – Soren Havelund Welling Oct 20 '16 at 9:16