Unit 6, lesson 38

Hyperparameter Search and Nested Evaluation

How grid search and random search tune hyperparameters within a stated search budget, why the best validation score is optimistic, and how nested cross-validation with inner and outer folds evaluates the whole search.

  • Video 38
  • Hyperparameter Search and Diagnostics

A team tries fifty penalty values for a ridge model, keeps the one with the lowest cross-validated error and reports that error as the performance to expect. The winner was picked because its score was the lowest, and part of what made it lowest was luck in those particular folds. This lesson separates choosing a setting from measuring performance. It describes grid search and random search with a stated budget, explains why the best score of a search is optimistic, and shows how nested cross-validation, or a clean test set used once, evaluates the search itself.

Key terms

Hyperparameter tuning

Definition A hyperparameter is a setting fixed before a training algorithm runs, such as a ridge penalty λ≥0\lambda \ge 0, the number of neighbors kk or the maximum depth of a tree, while parameters such as coefficients are learned by the fitting. Hyperparameter tuning chooses a setting from a candidate set Λ\Lambda by estimating the error of each candidate on rows that did not fit it, with a validation set or cross-validation inside the development data, and taking the best estimate under a stated rule for ties,

λ^=argmin⁡λ∈ΛErr⁡^(λ).\hat{\lambda} = \operatorname{argmin}_{\lambda \in \Lambda} \widehat{\operatorname{Err}}(\lambda).

The test set plays no part. Every learned preprocessing step is refitted inside each training split of the search, and once a setting is chosen, the procedure is refitted with it on all development data. Tuning is part of the training procedure, so an honest estimate of how the final model will perform has to evaluate the tuning as well, on rows the search never used.

In plain words Fitting answers which coefficients to use for given settings, and tuning answers which settings to use. Each candidate is judged on rows it did not learn from, and the test set is kept for the end.

Example Take ridge regression with one input, which minimizes

∑i(yi−b−wxi)2+λw2\sum_{i} (y_i - b - w x_i)^2 + \lambda w^2

with the intercept bb unpenalized. With Sxx=∑i(xi−xˉ)2S_{xx} = \sum_i (x_i - \bar{x})^2 and Sxy=∑i(xi−xˉ)(yi−yˉ)S_{xy} = \sum_i (x_i - \bar{x})(y_i - \bar{y}), and assuming Sxx+λ>0S_{xx} + \lambda > 0, the minimizer is

w^λ=SxySxx+λ,b^λ=yˉ−w^λxˉ.\begin{gathered} \hat{w}_\lambda = \frac{S_{xy}}{S_{xx} + \lambda}, \\[0.4em] \hat{b}_\lambda = \bar{y} - \hat{w}_\lambda \bar{x} . \end{gathered}

For the constructed training pairs (0,1)(0, 1) and (2,5)(2, 5), the means are xˉ=1\bar{x} = 1 and yˉ=3\bar{y} = 3, with Sxx=2S_{xx} = 2 and Sxy=4S_{xy} = 4, so w^λ=4/(2+λ)\hat{w}_\lambda = 4/(2 + \lambda). The candidate λ=0\lambda = 0 gives the line 1+2x1 + 2x and λ=10\lambda = 10 gives 8/3+x/38/3 + x/3. On the validation pair (1,3)(1, 3) both lines predict 33, because every ridge line here passes through (xˉ,yˉ)(\bar{x}, \bar{y}), so the squared errors tie at 00 and the stated rule picks the smaller penalty λ=0\lambda = 0. A validation pair (3,7)(3, 7) would separate them. The first line predicts 77 with error 00, and the second predicts 11/311/3 with squared error 100/9≈11.1100/9 \approx 11.1.

Definition Grid search fixes a finite list of candidate values for each hyperparameter and evaluates every combination, the Cartesian product of the lists. With lists of sizes c1,…,cqc_1, \dots, c_q the grid has C=c1c2⋯cqC = c_1 c_2 \cdots c_q candidates. Evaluating each with kk-fold cross-validation takes CkCk fits, and one more fit refits the chosen candidate on all development data. Every candidate is scored on the same folds, so the scores are comparable and the search is reproducible from the lists and the fold assignment. The grid covers only the listed values. If good settings lie outside the listed range, the search cannot find them, and each hyperparameter is tried at only as many distinct values as its own list holds, however many combinations the grid contains.

In plain words Write down the values to try for each setting and test every combination on the same folds. It is simple and transparent, but its cost multiplies with every setting added, and it never looks between or beyond the listed values.

Example Two penalties and three feature sets give 2⋅3=62 \cdot 3 = 6 candidates, and four folds per candidate make 6⋅4=246 \cdot 4 = 24 fits before the final refit. The worked example of this lesson uses the grid Λ={0,10}\Lambda = \{0, 10\}. Penalty lists usually spread their values over orders of magnitude, such as 0.01,0.1,1,10,1000.01, 0.1, 1, 10, 100, because in the formula above a penalty acts through its size relative to SxxS_{xx}, which grows with the spread of the input and the number of rows.

Definition Random search draws NN settings independently from a stated probability distribution over the hyperparameter space, with a recorded seed, and evaluates each setting like a grid candidate. Its result depends on the distribution, the ranges, NN and the seed, so all of them are reported. For a positive scale setting such as a penalty or a step size, a log-uniform distribution on an interval [a,b][a, b] with 0<a<b0 < a < b makes log⁡λ\log \lambda uniform on [log⁡a,log⁡b][\log a, \log b], so every factor of 1010 inside the range gets the same probability. A uniform distribution on the same interval with a≤b/10a \le b/10 puts the fraction 0.9b/(b−a)0.9b/(b - a) of its draws in the top factor of 1010, from b/10b/10 to bb, which is about 9090 percent when aa is tiny compared with bb. If a region of settings has probability qq under the sampling distribution, NN independent draws land in it at least once with probability 1−(1−q)N1 - (1 - q)^N. When only some hyperparameters matter, NN draws from a continuous distribution give NN distinct values of each one with probability 11, while a grid of NN candidates over several hyperparameters tries far fewer distinct values of each.

In plain words Instead of a fixed lattice, sample the settings at random from ranges you believe are sensible, and sample scale settings by their order of magnitude. Random search is no better than its ranges, and with a recorded seed it is as reproducible as a grid.

Example On the interval from 10−310^{-3} to 10310^{3}, a log-uniform draw falls at or below 11 with probability 1/21/2, since that part covers three of the six factors of 1010. A uniform draw on the same interval does so with probability (1−0.001)/(1000−0.001)≈0.001(1 - 0.001)/(1000 - 0.001) \approx 0.001. A region holding 55 percent of the sampling probability is hit at least once by 6060 independent draws with probability 1−0.9560≈0.9541 - 0.95^{60} \approx 0.954. With two hyperparameters, a 3×33 \times 3 grid tries 33 values of each, while 99 random draws try 99 values of each.

Search budget

Definition The search budget is the amount of searching a tuning procedure is allowed. It covers the number of candidates, the validation rows or folds per candidate, the resulting number of fits and the computing time, and the number of times results are inspected and the search is revised. Tuning is part of the procedure being evaluated, so the budget is reported together with the search space, the sampling distributions and seeds, the metric, the fold design, the tie rule and the final refit. A larger budget can find better settings, but it also gives chance more opportunities to make some candidate’s score look better than its true performance. Every revision of the search made after looking at evaluation results counts as searching, and the results that guided it become development data.

In plain words Say how hard you searched. A best score from two candidates and a best score from two thousand carry different amounts of luck, and a reader can judge a result only when the size and design of the search are on record.

Example The nested example below has 88 outer folds, 22 candidates and 77 inner fits per candidate, so the inner searches take 8⋅2⋅7=1128 \cdot 2 \cdot 7 = 112 fits and the outer refits add 88, for 120120 fits in the estimate. Producing the final model takes a further search on all 88 rows, 2⋅8=162 \cdot 8 = 16 fits, and 11 refit. In general, KK outer folds, CC candidates and kk inner folds cost K(Ck+1)K(Ck + 1) fits for the nested estimate.

Nested cross-validation

Definition Nested cross-validation estimates the performance of a whole tuning procedure. The development data are split into KK outer folds. For each outer fold jj, its outer training rows TjT_j are split again into inner folds, and the complete search, with its candidates, preprocessing, budget and tie rule, runs by cross-validation on TjT_j alone and selects λ^j\hat{\lambda}_j. The procedure is refitted with λ^j\hat{\lambda}_j on all of TjT_j, giving f^j\hat{f}_j, and scored on the held-out outer fold VjV_j,

λ^j=search⁡(Tj),sj=score⁡(Vj, f^j),Err⁡^nested=1K∑j=1Ksj,\begin{gathered} \hat{\lambda}_j = \operatorname{search}(T_j), \\[0.4em] s_j = \operatorname{score}\bigl(V_j,\ \hat{f}_j\bigr), \\[0.4em] \widehat{\operatorname{Err}}_{\text{nested}} = \frac{1}{K} \sum_{j=1}^{K} s_j , \end{gathered}

or the size-weighted mean when the folds differ in size. No row of VjV_j enters any inner fit, inner score, preprocessing step or selection for that outer fold. Different outer folds may select different settings, which is expected, because the object being evaluated is the search procedure and not one fixed setting. The estimate describes the search applied to training sets of about (K−1)/K(K - 1)/K of the development rows. The deployable model comes from running the same search on all development data, selecting one setting and refitting. Groups and time order have to be respected by the inner folds as well as the outer ones. Nesting is one way to keep selection apart from evaluation. A clean test set, used once after a single search on the development data, is another. Revising the search after looking at outer scores turns those scores into development feedback.

In plain words The inner loop chooses and the outer loop grades. Each outer fold plays the part of future data for a complete run of the search, so the outer score shows how well the habit of searching this way works, rather than how good the luckiest candidate looked.

Example The constructed data have inputs 0,1,…,70, 1, \dots, 7 and outcomes 1,3,4,7,9,10,13,151, 3, 4, 7, 9, 10, 13, 15. Both loops use leave-one-out folds, the candidates are the ridge penalties 00 and 1010, and ties go to the smaller penalty. Inside every outer training set the inner mean squared error is about 0.190.19 to 0.400.40 for λ=0\lambda = 0 and about 2.322.32 to 3.243.24 for λ=10\lambda = 10, so all eight searches select λ=0\lambda = 0. With the row at input 00 held out, the refit on the other seven rows is y^=4/7+(57/28)x\hat{y} = 4/7 + (57/28)x, which predicts 4/7≈0.5714/7 \approx 0.571 against the outcome 11, a squared error of 9/49≈0.1849/49 \approx 0.184. The eight outer predictions are about 0.5710.571, 2.6562.656, 4.9134.913, 6.7126.712, 8.7128.712, 10.91310.913, 12.65612.656 and 14.57114.571, and the nested mean squared error is about 0.3050.305. The search on all eight rows also selects λ=0\lambda = 0, and the final model is y^=0.75+2x\hat{y} = 0.75 + 2x. Because every search chose the same penalty, the nested estimate equals the best leave-one-out score on all eight rows. The two numbers separate when the winning setting depends on which rows the search sees.

Optimistic selection bias

Definition Optimistic selection bias is the tendency of the best of several noisy performance estimates to look better than the selected candidate actually performs, when the same estimates are used both to choose and to report. Suppose candidates 1,…,C1, \dots, C have true errors R1,…,RCR_1, \dots, R_C, and their estimates R^1,…,R^C\hat{R}_1, \dots, \hat{R}_C are unbiased, E[R^c]=RcE[\hat{R}_c] = R_c, as for errors measured on validation rows that were not used to fit any of the candidates. The reported minimum is at most each R^c\hat{R}_c, so with c^\hat{c} the selected candidate,

E[min⁡cR^c]≤min⁡cRc≤E[Rc^].\begin{aligned} E\Bigl[\min_{c} \hat{R}_c\Bigr] &\le \min_{c} R_c \\[0.4em] &\le E\bigl[R_{\hat{c}}\bigr]. \end{aligned}

The reported minimum therefore underestimates the selected candidate’s true error on average, and the gap tends to grow with the number of candidates that have similar true errors and noisy estimates. For accuracy, where larger is better, the same holds with maxima and the inequalities reversed. A clean test set used once on the selected procedure, or nested cross-validation, keeps the reported estimate apart from the selection. Test or outer scores consulted again and again to revise the search pick up the same bias.

In plain words If you pick the best of many noisy scores and report it, you report the luck along with the skill. The more candidates you try, the more luck the winner tends to carry, and only rows that played no part in the choice can measure the winner fairly.

Example Two procedures have the same true error 0.200.20, and each estimate is 0.180.18 or 0.220.22 with probability 1/21/2, independently. These numbers are constructed. The smaller estimate is 0.220.22 only when both are 0.220.22, so the reported best has expected value 0.18⋅3/4+0.22⋅1/4=0.190.18 \cdot 3/4 + 0.22 \cdot 1/4 = 0.19, while the chosen procedure’s true error is 0.200.20. With CC such procedures the expected best is 0.18+0.04⋅2−C0.18 + 0.04 \cdot 2^{-C}, which is 0.18250.1825 for C=4C = 4 and about 0.180040.18004 for C=10C = 10. Observing 0.180.18 for one procedure and 0.220.22 for the other does not show that the first is better.

Check yourself

  1. Ridge regression with an unpenalized intercept is tuned over λ∈{0,4}\lambda \in \{0, 4\} on the training pairs (1,2)(1, 2) and (3,8)(3, 8), with the validation pairs (2,6)(2, 6) and (4,10)(4, 10) and ties going to the smaller penalty. Find both fitted lines, their validation mean squared errors and the selected penalty. What does the validation pair at input 22 contribute?
Show the answer

The means are xˉ=2\bar{x} = 2 and yˉ=5\bar{y} = 5. The centered inputs are −1-1 and 11 and the centered outcomes −3-3 and 33, so Sxx=2S_{xx} = 2 and Sxy=3+3=6S_{xy} = 3 + 3 = 6.

With λ=0\lambda = 0 the slope is 6/2=36/2 = 3 and the intercept 5−3⋅2=−15 - 3 \cdot 2 = -1, so the line is −1+3x-1 + 3x. With λ=4\lambda = 4 the slope is 6/6=16/6 = 1 and the intercept 5−2=35 - 2 = 3, so the line is 3+x3 + x.

At input 22 both lines predict 55, a squared error of 11 each. At input 44 the first predicts 1111, a squared error of 11, and the second predicts 77, a squared error of 99. The validation mean squared errors are (1+1)/2=1(1 + 1)/2 = 1 and (1+9)/2=5(1 + 9)/2 = 5, so the search selects λ=0\lambda = 0.

The input 22 is the training mean of xx, where every ridge line passes through yˉ=5\bar{y} = 5, so that pair adds the same error to both candidates and cannot separate them. The choice rests on the single pair at input 44. The winner’s validation error 11 is the smaller of two estimates, so as a measure of the chosen line’s error on new cases it is optimistic, and two validation rows are very little evidence in any case.

  1. A report states that the best inner cross-validation accuracy of a search was 9191 percent and that the three outer folds gave 8282, 8585 and 8787 percent. Which number estimates the performance of the search procedure, and can the 9191 percent be reported as independent final performance? What changes if the outer folds held 200200, 100100 and 100100 cases?
Show the answer

The outer scores estimate the performance of the search procedure, because each comes from rows that took no part in the search that produced its model. Their equally weighted mean is

82+85+873=2543,\frac{82 + 85 + 87}{3} = \frac{254}{3} ,

about 84.6784.67 percent. The 9191 percent is the best of the inner comparisons. It chose the setting, so it is a selected development result carrying optimistic selection bias, and it cannot be reported as independent final performance.

With outer folds of 200200, 100100 and 100100 cases, the folds have 164164, 8585 and 8787 correct predictions, and the accuracy over all 400400 outer cases is

164+85+87400=336400,\frac{164 + 85 + 87}{400} = \frac{336}{400} ,

which is 0.840.84, or 8484 percent. It counts every case once, while the equal-weight mean of 84.6784.67 percent gives every fold the same weight. Either way, report the design, the fold sizes and the search budget with the number. Three dependent fold scores do not by themselves give a valid confidence interval.

  1. A data set has 600600 visits from 150150 patients, 44 visits each, and the model will be used for new patients. The search is a grid of 55 penalties and 44 feature sets with 55 inner folds, evaluated with 44 outer folds. How many fits does the nested estimate take, and how many more does the final model take if its search uses 55 folds on all the development data? How should the folds be formed, and what should the report record?
Show the answer

The grid has 5⋅4=205 \cdot 4 = 20 candidates. In each outer fold the inner search takes 20⋅5=10020 \cdot 5 = 100 fits and the refit adds 11, so the four outer folds take 4⋅101=4044 \cdot 101 = 404 fits. The final search on all development data takes another 100100 fits and 11 refit, so the whole plan costs 505505 fits.

Every fold at both levels has to keep whole patients together, since the model will meet new patients. The outer folds hold whole patients, about 3737 or 3838 each, and the inner folds are formed from the patients of each outer training set. Visits of one patient split between an inner training set and its inner validation fold would let the search favor settings that recognize familiar patients.

The report records the grid values, the metric, the fold assignments or the seeds that produced them, the tie rule, the budget of 505505 fits, and any change made to the search after outer results were seen. A random search with 2020 draws from stated distributions would cost the same number of fits and would need the same record.

How this lesson connects