20  Hyperparameter Tuning

Hyperparameters control which functions a learning procedure can produce: the penalty of a regularized model, the depth of a tree, the number of neighbors in a nearest-neighbor model. They are not estimated by minimizing the training loss, which would always choose the most flexible setting (Section 4.5). They are chosen by comparing estimates of performance on held-out data. This chapter describes how the comparison is organized, and why the performance of the selected setting must be assessed on data that played no part in the selection.

20.1 The search space

A search space assigns to each tuned hyperparameter a set of candidate values, for example \(\lambda \in \{0.001, 0.01, 0.1, 1\}\) and \(\alpha \in \{0, 0.5, 1\}\). Continuous hyperparameters whose effect spans orders of magnitude, such as penalties and learning rates, are searched on a logarithmic scale.

  • Grid search evaluates every combination of the candidate values. Its cost is the product of the numbers of candidates, which grows exponentially with the number of hyperparameters.
  • Random search evaluates a random sample of combinations. When only a few hyperparameters matter, random search explores the values of those few more densely than a grid with the same number of evaluations (Bergstra and Bengio 2012).
  • Sequential methods, such as Bayesian optimization, choose each new combination using the results of the previous ones.

Some algorithms compute the solutions for an entire sequence of values of one hyperparameter at the cost of a single fit, as glmnet does for \(\lambda\) (Section 18.4); the search over that hyperparameter is then nearly free.

20.2 Selection by resampling

For each candidate combination \(\theta\), the training data are resampled, a model with hyperparameters \(\theta\) is fitted on each training part, and its error is measured on the held-out part. The combination with the best aggregate error, typically the mean across resamples, is selected:

\[ \hat\theta = \arg\min_{\theta \in \Theta} \frac{1}{K}\sum_{k=1}^{K} \widehat{\mathrm{Err}}_k(\theta). \tag{20.1}\]

A final model is then fitted with \(\hat\theta\) on all the training data. The selection metric is chosen in advance and reflects the use of the model (Section 8.7): mean squared error or \(R^2\) for regression, and for classification a proper scoring rule, AUC or balanced accuracy.

When the selected value lies at the boundary of the search space, the optimum may lie beyond it, and the space is extended. Extending it on the basis of results on the final test data, rather than on the internal resampling, makes the test data part of the selection.

20.3 The optimism of the selected estimate

The resampling error of the selected combination is not an unbiased estimate of its performance. Each candidate’s estimate contains random error, and the selection favors the candidate whose random error happened to be favorable. The minimum of several noisy estimates is lower, on average, than the error of the candidate it belongs to (Varma and Simon 2006; Cawley and Talbot 2010).

Figure 20.1 illustrates the effect for candidates that all have the same true AUC of 0.70, each estimated with a standard error of 0.03. The expected value of the largest estimate rises with the number of candidates, although no candidate is better than any other.

Figure 20.1: Expected optimism of the best of \(M\) estimates, when \(M\) candidates have the same true AUC of 0.70 and each estimate has a standard error of 0.03 (2000 simulations per \(M\)).

With 100 candidates, the best estimate exceeds the true value by 0.075 on average. With real candidates of differing quality the effect is smaller, since the best candidate is more often selected for its quality than for its noise, but it does not vanish.

20.4 Nested resampling

An unbiased estimate of the performance of a tuned model requires that the data used to assess it played no part in its tuning. Nested resampling achieves this with two levels:

  • an outer resampling divides the data into training and test sets for assessment;
  • within each outer training set, an inner resampling selects the hyperparameters, and a model with the selected values is fitted to the whole outer training set and evaluated on the outer test set.

The outer estimate assesses the complete procedure, including the search, as Section 10.10 requires. Each outer training set may select different hyperparameters; the outer estimate describes the expected performance of the procedure, not of one particular setting. After assessment, the procedure is applied once more, to all the data, to obtain the final model and its hyperparameters.

Outer resampling with replacement, such as the bootstrap, is not combined with inner resampling: duplicated cases in an outer training set can fall on both sides of an inner split, and the inner estimates become optimistic (Section 10.6).

20.5 Computational cost

Nested resampling multiplies the number of model fits. With \(|\Theta|\) candidate combinations, \(K_{\text{in}}\) inner resamples and \(K_{\text{out}}\) outer resamples, the number of fits is

\[ K_{\text{out}} \left( |\Theta| \, K_{\text{in}} + 1 \right), \tag{20.2}\]

plus the final tuning on all data. A grid of 20 combinations with 5 inner and 10 outer folds requires 1010 fits for assessment. The fits are independent, and can run in parallel.

20.6 Summary

  • Hyperparameters are chosen by comparing resampled estimates of performance over a search space, by grid, random or sequential search.
  • The resampling estimate of the selected setting is optimistic, because selection favors favorable noise.
  • Nested resampling assesses the tuned procedure with outer resamples that play no part in the inner selection.
  • The final model is obtained by applying the same tuning procedure to all the data.

20.7 Further reading