Nested Cross Validation: Choosing between different best hyperparameters

Question

I know this sort of question has been asked many times, and several answers have been already provided on this platform too (e.g., here, here, and here). Still, there is something about the idea behind nested cross validation that I don't quite get.

Let me first start with the problem setting, which by the way I think is quite common across machine learning practitioners. Apologize in advance for the long message and for the notation/terminology I'm gonna use in the following, as this might be somewhat sloppy or inaccurate.

Suppose we need to solve a classical supervised learning task, and to this end we are given with a labeled dataset $\mathcal{D}$. At this stage, I am assuming $|\mathcal{D}| = n$ is "large enough" for achieving our prediction task, whatever "large enough" might mean (first sloppiness, I know!)

Suppose also that we want to evaluate in terms of some metric a set of learning models $\mathcal{M} = \{M_1, M_2, \ldots, M_{|\mathcal{M}|}\}$. Think of each $M_i$ as one among Logistic Regression, SVM, Decision Tree, etc. Moreover, each $M_i$ has also its own set of hyperparameters, e.g., let $\mathcal{P}(M_i) = \{P_{i,1}, P_{i,2}, \ldots, P_{i,|\mathcal{P}(M_i)|}\}$ be the set of all the possible combinations of hyperparameters we want to test for the learning model $M_i$. For example, if $M_i$ = Logistic Regression a possible set of hyperparameters we may want to tune is a set of different values for the regularization hyperparameter $C$.

Clearly, in a setting like the one above there are 3 things we want to achieve:

1. For each learning model $M_i$, select the actual model whose hyperparameters (specific to that model) lead to the best performance
2. Among all the best $M_i$, select the one with the best performance overall
3. Once we select the best (of the best) model - let's call this $M^*$ - we want to evaluate it, i.e., provide a less biased estimate of the generalization error.

Now, as far as I understand, the scenario above is exactly the one where nested cross validation comes into play. The thing that is not totally clear to me is the following. Suppose that I have split the original dataset $\mathcal{D}$ in two datasets: $\mathcal{D}_{train}$ and $\mathcal{D}_{test}$ (e.g., 80÷20). Let's now focus on $\mathcal{D}_{train}$, and suppose we run nested cross validation only on that portion.

$\mathcal{D}_{train}$ will be therefore used for a $k_{out}$-fold outer cross validation run, and each of the $k_{out}$-folds will be in turn used for a grid search $k_{in}$-fold inner cross validation to test every possible hyperparameter combination of a given learning model $M_i$. This also means that on each run of the $k_{out}$-fold outer cross validation, I will use a different hyperparameter set. Therefore, at the end of the $k_{out}$-fold outer cross validation I would have an estimate of the model performance, which results from the average of $k_{out}$ estimates of generalization error (each one assumed to be obtained with the best hyperparameters found).

My question is: How could I use the information above (i.e., the outer cross validation error) to select the best hyperparameters (of a single $M_i$)? Should I go back to each individual $k_{out}$ error and pick the smallest one? But if that's the case, what's the point of having a cross validation run?

According to this, it seems that "If your model is stable, these m models should all have the same hyperparameter values, and you report the average performance of this model based on the outer test folds". Is there any theoretical result which support this claim? (i.e., that all the "best" hyperparameters turn out to be the same, and therefore each $k_{out}$ fold will be actually training $M_i$ with the same hyperparameters?). What if that doesn't hold?

Again, apologize for the extremely long message. I hope, though, that my question is clear enough. To put it in the simplest way possible, I guess this would be: Given a set of learning models and their associated hyperparameters, how would you perform nested cross validation in order to:

1. Perform hyperparameter selection on each single learning model (e.g., the best value of $C$ for Logistic Regression, the best value of $K$ for K-NN, etc.)
2. Perform learning model selection (i.e., among the best models found at step 1., should I pick Logistic Regression or K-NN?)
3. Estimate the generalization error of the best learning model as chosen at step 2.

Thanks in advance.

Answer 1

As I understand, performing nested CV means that you have two layers of CV, and you use each layer for one and only one thing:

• The outer layer, for estimating the quality of the models trained on the inner layer.
• The inner layer for selecting the best model (including parameters, hyperparameters and so on).

One important distinction: in fact, you are not assessing the quality of the model, but of the procedure of model selection. What you are evaluating in the outer folds is that the procedure for model selection is consistent, so it does not mind that the hyperparameters are different (it should be better if they didn't differ much, but if the quality is comparable, it does not matter much).

So, for each k-outer-fold, you will select one (and only one) inner model (the best one), trained on the training set for this k-outer-fold, and this model will be evaluated on the validation set for this k-outer-fold. After you vary the outer k, you will have k-outer estimates and you can average them to assess better the quality of the models.

Another important thing: once you find the best hyperparameters for a particular loop, how can you select the model, if you have k-inner-folds models? You can do two things: create a new instance of the model with this parameters and fit it on the whole inner fold, or create an ensemble of all k-inner-fold models. Both can be ok.

I have developed a Python package for practising nested cross validation. You might want to take a look. If you find it interesting, please tell me! Thanks in advance:

https://github.com/JaimeArboleda/nestedcvtraining/blob/master/README.md