# How to avoid overfitting bias when both hyperparameter tuning and model selecting?

Say I have 4 or more algorithm types (logistic, random forest, neural net, svm, etc) each of which I want to try out on my dataset, and each of which I need to tune hyperparameters on.

I would typically use cross validation to try and tune my hyperparameters, but once tuned, how do I avoid generalization error from selecting the model family?

It would seem to me that the scores for each family would now have information leakage as the averaged tuned cv score has in a way seen the whole train set.

What is good practice here then? And how would it look differently between say a nested cross validation run or a simple cross validation with a final holdout?

Thanks!

• Use nested cross-validation jmlr.org/papers/volume11/cawley10a/cawley10a.pdf Simple cross-valiudation with a final holdout would be fine if you had a large dataset, but otherwise would give a high variance performance estimate (different result if you split the data differently). Nov 3 '20 at 14:28
• I don't see how simply doing nested cross-validation instead of cross-validation with a holdout set solves the problem of OP. In the OP problem they suggest that they run through the cross-validation plus a holdout set 4 times and obtain 4 estimates of generalization error for 4 different model families. Then when you choose the best performing family, the error rate you have for it from the cross-validation plus the holdout is biased because you have used it to select between the 4 models. Nested cross-validation doesn't solve this it just makes the original 4 estimates less variant correct? Nov 4 '20 at 18:24
• @astel: OP's problem is that they move too early to the outer loop: the model family is a hyperparameter like any other hyperparameter. The point is that they need to finish all their model optimization before moving to the outer loop with their one final model in order to estimate generalization error. Nov 4 '20 at 20:03
• Yeah I agree, and I also like the explanation of model family as a hyper parameter. Just thinking that simply suggesting to switch to nested CV isn’t enough. Possible OP would just do 4 separate nested CVS and end up with the same issue but just better estimates of generalization error Nov 4 '20 at 20:07
• @astel I agree with you and disagree with cbeleties given my current knowledge. My as-is practice would not have me "moving too early to the outer" I do not believe. My argument is that doing both of these in the inner produces an optimistic bias and that perhaps tripple nesting or somesuch is appropriate.
– Josh
Nov 4 '20 at 22:11

As @DikranMarsupial say, you need a nested validation procedure. In the inner e.g. cross validation, you do all the tuning of your model - that includes both choosing hyperparameters and model family.

In principle, you could also have a triply nested validation structure, with the innermost tuning the respective model family hyperparameters, the middle one choosing the model family and the outer as usual to obtain a generalization error estimate for the final model.
The disadvantage with this, however, is that splitting more often than necessary means that the data partitions become rather small and thus the whole procedure may become more unstable (small optimization/validation/test set mean uncertain performance estimates).

## Update:

Nesting vs. cross validation or hold-out

Nesting is independent of the question what splitting scheme you employ at each level of the nested set-up. You can do cross validation at each level, single split at each level or any mixture you deem suitable for your task.
2 nested levels and both CV is what is often referred to as nested cross validation, 2 nested levels and both single split is equivalent to the famous train - validation [optimization] - test [verification] setup. Mixes are less common, but are a perfectly valid design choice as well.

If you have sufficient data so that single splits are a sensible option, you may also have sufficient data to do three such splits, i.e. work with 4 subsets of your data.

One thing you need to keep in mind, though, is: a single split in the optimization steps* you deprive yourself of a very easy and important means of checking whether your optimization is stable which cross validation (or doing several splits) provides.

* whether combined hyperparameter with model family or model family choice plus "normal" hyperparameter optimization

Triply nested vs. "normal" nested

This would be convenient in that it is easy to implement in a way that guards against accidental data leaks - and which I suspect is what you were originally after with your question:

• estimate_generalization_error() which splits the data into test and train and on its train data calls
• choose_model_family() which employs another internal split to guide the choice and calls and on its training split calls the various
• optimize_model_*() which implement another internal split to optimize the usual hyperparameters for each model family (*), and on its training split calls the respective low-level model fitting function.

Here, choose_model_family() and optimize_model_*() are an alternative to a combined tuning function that does the work of both in one split. Since both are training steps, it is allowed to combine them. If you do grid search for hyperparameter tuning, you can think of this as a sparse grid with model family x all possible hyperparameters where evaluate only combinations that happen to exist (e.g. skip mtry for SVM).
Or you look at the search space as a list of plausible hyperparamter combinations that you check out:

- logistic regression
- SVM with cost = 1, gamma = 10
- SVM with cost = 0.1, gamma = 100
...
- random forest with ...


to find the global optimum across model families and model family specific hyperparameters.

There is nothing special about model_family - it is a hyperparameter for the final model like cost or gamma are for SVMs.

In order to wrap your head around the equivalence, consider optimizing gamma and cost for an SVM.

• Method one: set up a grid or a list of all plausible cost; gamma combinations and search that for the optimum. This is the analogue to the "normal" nested approach.

• Method two:

1. set up a list of all plausible cost values.
2. for each cost value, optimize gamma.
3. select the cost with best optimized gamma

This is the analogue to the triply nested approach.

In both cases, we can "flatten" the nested structure into a single loop iterating over a list or grid (I'm sorry, I lack the proper English terms - maybe someone can help?). This is also vaguely similar to "flattening" a recursive structure into an iterative one [though the triply nested is not recursive, since we have different functions f(g(h()))].

This flattening approach potentially has the further advantage that it may be better suited to advanced optimization heuristics. As an example, consider moving from "select the observed optimum" to the one-standard-deviation rule. With the flattened approach, you can now look across model families which model is least complex not more than 1 sd worse than the observed optimum.

• I do not see how nested cv as you describe is defacto the solution here. For a large sample, a representative holdout should be just as viable. That said the tripple nesting you mention is I believe more to the point.I would also be interested in what to do if you were going the hold out way (and maybe indeed a nesting, just of a different purpose is good here), and if additional nesting is common practice.
– Josh
Nov 4 '20 at 22:16
• @Josh: please check whether my update is more clear to you. Personally, I usually get data with small effective sample size, so triply nesting is no viable option for me. Nov 4 '20 at 23:17
• Apologies for the belated response. I think this all makes sense if we are explicitly noting that, if we treat the model family selection like a hyperparameter, the model family must also be either A) require an additional tier in nesting or train-test splits, or B) must be done along with each fold of the CV in a typical nest. I only want to clarify the later due to the fact that I think we otherwise have a tendency pick the model family after, say, a couple of grid searches over all of the training set.
– Josh
Nov 16 '20 at 21:31

Just to add to @cbeleites answer (which I tend to agree with), there is nothing inherently different about nested cross validation that it will stop the issue in the OP. Nested cross validation is simply the cross validated analog to a train/test split with cross validation performed on the training set. All this serves to do is reduce variance in your estimate of the generalization error by averaging splits. That said, obviously reducing variance in your estimate is a good thing, and nested CV should be done over a single train/test split if time allows.

For the OP as I see it there are two solutions (I will describe it under a single train/test split instead of nested CV but it could obviously be applied to nested CV as well).

The first solution would be to perform a train/test split and then split the training set into train/test again. You now have a training set and two sets. For each model family perform cross validation on the training set to determine hyper-parameters. For each model-family select the best performing hyper-parameters and obtain an estimate of generalization error from test set 1. Then compare the error rates of each model family to select the best and obtain its generalization error on test set 2. This would eliminate your issue of optimistic bias due to selecting the model using data that was used for training however would add more pessimistic bias as you have to remove data from training for test set 2.

The other solution as cbeleites described, is to simply treat model selection as hyper-paramters. When you are determining the best hyper-parameters, include model-family in this selection. That is, you aren't just comparing a random forest with mtry = 1 to a random forest with mtry = 2... you are comparing random forest with mtry = 1 to mtry = 2 and to SVM with cost = 1 etc.

Finally I suppose the other option is to live with the optimistic bias of the method in the OP. From what I understand one of the main reasons leading to the requirement of a test set is that as the hyper-parameter search space grows so to does the likelihood of selecting an over-fit model. If model selection is done using the test set but only between 3 or 4 model families I wonder how much optimistic bias this actually causes. In fact, I would not be surprised if this was the largely predominate method used in practice, particularly for those who use pre-built functionality a la sci-kit learn or caret. After all these packages allow a grid search of a single model-family, not multiple at the same time.

• I almost feel like this needs to be added to cbeleites answer above. It provides I think a nice contextual summary. My immediate question then becomes "what is standard practice then?" but I suppose that would require empirical polling
– Josh
Nov 16 '20 at 21:23
• If I understand you correctly, you need one more train/test split i.e. you did not describe the outermost train/test split to measure generalization error. "3 or 4 model families I wonder how much optimistic bias this actually causes" if it's really only 3 or 4 models/families, the bias is unlikely to be that heavy. But OTOH, it can easily be avoided. IMHO the more important advantage of the treat-as-hyperparameter approach is that it at the same time allows better heuristics against overfitting of the "traditional hyperparameters". Nov 19 '20 at 15:43
• I think we have enough tests sets. Basically train and two test sets. For each family train hyper-parameters on training set using cross validation and use first test set to estimate generalization error for the best set of hyper-parameters. So now you have an optimal set of hyper-parameters for each family and an estimate of error. Choose the best model family now using those error estimates and then get the real estimate of generalization error by applying it to test set two. Nov 19 '20 at 18:09