Step-by-step explanation of K-fold cross-validation with grid search to optimise hyperparameters

Question

I'm well aware of the advantages of k-fold (and leave-one-out) cross-validation, as well as of the advantages of splitting your training set to create a third holdout 'validation' set, which you use to assess model performance based on choices of hyperparameters, so you can optimise and tune them and pick the best ones to finally be evaluated on the real test set. I've implemented both of these independently on various datasets.

However I'm not exactly sure how to integrate these two processes. I'm certainly aware it can be done (nested cross-validation, I think?), and I have seen people explaining it, but never in enough detail that I have actually understood the particulars of the process.

There are pages with interesting graphics that allude to this process (like this) without being clear on the exact execution of the splits and loops. Here, the fourth one is clearly what I want to be doing, but the process is unclear:

There are previous questions on this site, but while those outline the importance of separating validation sets from test sets, none of them specify the exact procedure by which this should be done.

Is it something like: for each of k folds, treat that fold as a test set, treat a different fold as a validation set, and train on the rest? This seems like you'd have to iterate over the whole dataset k*k times, so that each fold gets used as training, test and validation at least once. Nested cross-validation seems to imply that you do a test/validation split inside each of your k folds, but surely this cannot be enough data to allow for effective parameter tuning, especially when k is high.

Could someone help me by providing a detailed explanation of the loops and splits that allow k-fold cross-validation (such that you can eventually treat every datapoint as a test case) while also performing parameter tuning (such that you do not pre-specify model parameters, and instead choose those that perform best on a separate holdout set)?

Answer 1

Here's the "default" nested cross-validation procedure to compare between a fixed set of models (e.g. grid search):

• Randomly split the dataset into $K$ folds.
• For $i$ from 1 to $K$:
  • Let test be fold $i$.
  • Let trainval be all the data except that which is in test.
  • Randomly split trainval into $L$ subfolds $(i, 1), (i, 2), \dots, (i, L)$ . So, each subfold $(i, j)$ has some elements from outer fold 1, some from outer fold 2, ..., but none of them has any from outer fold $i$.
  • For $j$ from 1 to $L$:
    • Let val be fold $(i, j)$.
    • Let train be all the data which is not in either test or val.
    • Train each proposed parameter set on train, and evaluate it on val, keeping track of classification accuracy, RMSE, whatever criterion you want to use.
  • Look at the average score for each set of parameters over the $L$ folds, and choose the best one.
  • Train a model with that best set of parameters on trainval.
  • Evaluate it on test, and save the accuracy / RMSE / whatever.
• Report the mean / mean + std / boxplot / whatever of the $K$ accuracies.

Answer 2

Inline with the Dougal answer, you can check the article from D. Krstajic et al. "Cross-validation pitfalls when selecting and assessing regression and classification models", 2014 (doi: 10.1186/1758-2946-6-10 https://www.researchgate.net/publication/261217711_Cross-validation_pitfalls_when_selecting_and_assessing_regression_and_classification_models). There they use nested cross validation for model assessment and grid search cross-validation to select the best features and hyperparameters to employ in the final selected model. Basically they present different algorithms to apply cross-validation with repetitions and also using the nested technique, which aim to provide better error estimates. In the end they elaborate on the experiments done employing the different algorithms for model assessment and selection. As mentioned by the authors in the Discussion section of the article: "As far as we are aware, nested cross-validation is the best non-parametric approach for model assessment when cross-validation is used for model selection.". I could provide you with more information but after reading the article I think you will get a good insight on how to perform grid search cross validation properly and other important aspects associated with these methods.

Answer 3

The first step is dividing the whole dataset into training set and testing set. And then for the training set, you could apply k-fold cross validation. Each time you use k-1 fold to train the model and use another one fold as validation set to evaluate the model performance. In this step, you could get a model with best performance in training set. Finally, you could apply this model to testing set to evaluate the performance of the model fitted in the second step. Here's a link which you may find useful in understanding the difference between validation set and testing set. What is the difference between test set and validation set?