Searching for a Setting

Twelve people were measured, height in centimetres and weight in kilograms, from 150 centimetres and 50 kilograms up to 183 centimetres and 82 kilograms. To guess a new person’s weight from their height, the neighbour method finds the k people closest in height and averages their weights, and everything about that guess is fixed by the twelve people except k itself. Ask for one neighbour and the guess is one person’s weight; ask for nine and it is nearly the average of everyone.

A number like k is called a hyperparameter, and the word marks a difference in kind from the numbers a fit finds. The line page’s slope and intercept are chosen by the fit to make the misses small; k is chosen before the fit and changes what fitting means. The same is true of the ridge page’s penalty, the polynomial page’s degree, a tree’s depth and the number of rounds of boosting, and every one of them has to be set by the procedure on this page or by something like it.

We could try letting the fit choose k the way it chooses a slope, by asking which k makes the misses on the twelve people smallest. The grey line in the playground is that experiment, each k fitted on the nine searched people and scored on those same nine, and it reads exactly one at one neighbour and falls from there, 0.9758 at two, 0.9560 at three, 0.9258 at four and 0.8564 at five.

It reads one at k = 1 because every person’s nearest neighbour among the people the model remembers is that person, so the guess is their own weight and the miss is zero.

score on the fitted rows at k = 1  =  1 − 0 / TSS  =  1

So a fit allowed to set its own k would always answer one, and one neighbour is the setting that memorises. The training score cannot turn as k rises, for the same reason the held-out page gave about a polynomial’s degree, since a smaller k always has at least as much freedom to match the rows it was shown. A number that is guaranteed to prefer the most flexible setting cannot be the number that chooses between settings.

The ruler has to be data the fit did not see, which is the held-out page’s whole argument, and the version used here is its folded form. The searched people are dealt into folds, each k is fitted on all but one fold and scored on the fold it was denied, and the mean of those fold scores is what that k earns.

The indigo line in the playground is that number at each k, and it does turn, rising from 0.8944 at one neighbour to 0.9252 at two and then falling to 0.2448 at five.

score(k)  =  (1 / n_folds) Σ over folds f of R² of the k-neighbour fit
             fitted without fold f, scored on fold f

Read the two lines together. The grey line says memorising is best; the indigo line says two neighbours is best, because a guess averaged over two nearby people is steadier than one person’s weight and still local enough to follow the trend. Every score on this page from here on is a held-out one.

A search needs one model per setting, and the way it builds them matters more than it looks. The safe way is to build each candidate from scratch through the same constructor a person would use, handing it the searched value along with every other setting copied from the prototype, so that a value the model would refuse is refused here too, and a name the model does not have is refused before a single fold is fitted.

The dial’s name is checked against the model’s declared fields at the moment the range is written down, and the widget below lets you misspell it.

Misspell the dial as n_neighbors and the space is refused at once, with the two dials the model does have, metric and n_neighbours, named in the message. Try a zero and the model’s own constructor refuses the candidate, since a neighbour count has to be above zero. I made the other choice first, building candidates by copying the prototype and overwriting one field, and a copy accepts a field name it has never heard of without complaint and leaves the real field at its default, so a grid over the misspelling would have fitted the same model at every point, reported a perfectly flat curve, and picked the first value by tie-break.

Nothing about that output would look wrong.

One dial gives a list of candidates. Two dials give a grid, every value of the first paired with every value of the second, which is where the method gets its name. The lattice below searches two dials on the same nine people, the degree of a polynomial in height and the penalty of a ridge fit on the expanded columns, standardised in between, with the whole chain treated as one model so that a candidate is one degree and one penalty together.

Three degrees and four penalties make twelve candidates, each a cell, and the winner is degree 1 at a penalty of 0.1 with a score of 0.9883, which is what twelve people close to a line ought to prefer. The reason to try the combinations rather than each dial on its own is that the dials interact.

A penalty of 10 scores 0.5304 at degree 1 and 0.8468 at degree 3, since the degree-3 chain has more standardised columns to shrink and shrinking them costs less, so the best penalty depends on the degree it is paired with, and only a search that pairs them can find that out.

candidates  =  every (d, λ) with d in degrees and λ in penalties
count       =  |degrees| × |penalties|  =  3 × 4  =  12

The product that makes the grid thorough is also its bill. Twelve candidates on three folds is thirty-six fitted models, and the readout in the lattice counts them the same way, before any of them is run. Widen the ranges to four degrees and six penalties and the count is twenty-four candidates and seventy-two fits, with the winner unchanged at degree 1 and penalty 0.1, so the extra thirty-six fits bought the knowledge that a penalty of 100 scores −0.0792, which is worse than guessing the mean weight.

fits  =  n_folds × Π over dials of |range|
      =  3 × (4 × 6)  =  72

There is a subtler cost than the count. In the four-by-six lattice the twenty-four candidates test only four distinct degrees, since every row repeats the same degree six times, and the winner’s neighbours along its own row differ from it by a few thousandths. When one dial matters and the other does not, which is common, a grid spends most of its budget re-measuring the same few values of the one that counts.

Sampling the two dials at random instead tests twenty-four distinct values of each, which is the argument behind random search, which is not built here yet, so this page can state the argument and not measure it.

Before any candidate is scored, a quarter of the people is put aside and not looked at again until the search is over. Under the page’s seed the three held back are persons 5, 9 and 12, at 162, 174 and 183 centimetres, and the other nine are dealt into three folds of three. Both deals are seeded shuffles, which is what lets the page name the people in each and quote the scores they produce.

Two things are settled by this one deal. Every candidate is fitted and judged on exactly these folds, and the three held-back people are the only rows on the page that no candidate ever sees, so they are the only rows that can judge the winner without having helped choose it. Part 6 is about the second of those.

The whole search is this arithmetic repeated, so let us do it once. Take the second fold at two neighbours. The fold judges persons 2, 6 and 8, at 153, 165 and 171 centimetres and 52, 63 and 71 kilograms, and the fit is allowed the other six searched people, at 150, 157, 159, 168, 177 and 180 centimetres.

predicted   52.5,  61.5,  71
missed by    0.5,   1.5,   0
squared     0.25 + 2.25 + 0  =  2.5

TSS  =  100 + 1 + 81  =  182

fold score  =  1 − 2.5 / 182  =  0.9863

With one neighbour on this fold, the predictions are 50, 66 and 66 kilograms. Their errors are 2, 3 and 5 kilograms. Square those errors and compare their total with the fold’s baseline variation.

squared error total = 2² + 3² + 5² = 38
R² = 1 − 38 / 182 ≈ 0.7912

That is the difference between using one neighbour’s weight and averaging the two nearest weights on this fold.

The other two folds give scores about 0.9402 and 0.8491. Average the three fold scores to obtain the candidate score plotted for two neighbours.

mean fold R² ≈ (0.9863 + 0.9402 + 0.8491) / 3 ≈ 0.9252

Repeat this procedure for each candidate. The faint dots show the individual fold scores, which can vary substantially even when their mean is summarized by one point.

A candidate’s score is a mean of three noisy numbers, and the noise is not small. On this deal the third fold reads 0.0029 at five neighbours where the second reads 0.4316, and the two settings that matter, one neighbour and two, are separated by 0.0308 in the mean while their folds are separated by up to 0.1951.

Here is a rule that is easy to state and was once broken here. Every candidate has to be scored on the same deal of the folds. If each candidate were scored on a fresh deal, the difference between two candidates would include the difference between two deals, and a search could prefer one setting for reasons that have nothing to do with the setting. The widget scores two neighbours on six fresh deals to show how much a deal alone can move the number.

A candidate can receive quite different validation scores under different folds. On the nine-person example, the same two-neighbor model produces the following scores across the six displayed seeds:

R² by split seed:
0.7909, 0.5832, 0.6013, 0.9252, −9.0911, 0.4413

The very negative result comes from a split that groups the shortest people in one fold and the tallest in another. The corresponding training folds then lack examples from the end of the range they must predict. The nearest-neighbor model repeats an available training average rather than extrapolating that trend.

This explains why candidates must use the same folds within a search. Otherwise, we could select a candidate because it received an easier split. The API fixes the split seed within each search, and the repeated-configuration comparison checks that identical candidates receive identical scores.

With every candidate scored the winner is the largest score, two neighbours at 0.9252 on the twelve people. The comparison is strict, so a candidate has to beat the incumbent to replace it and a tie goes to the earlier one, which sounds like a detail and is not. Two candidates that are genuinely equivalent come back differing in the last bits or not at all, and letting a tie swap the winner would make the answer depend on the order the grid was written in.

Ask the lattice in section 5 for the same degree twice and the two cells tie exactly, the spread reads zero, and the first of the two is named.

winner  =  the candidate with the largest score,
           the earlier of two equal scores

A winner is always named, even when the candidates barely differ, so the number to read beside it is the best score less the worst. On the twelve people that spread is 0.6804, from 0.9252 at two neighbours down to 0.2448 at five, and a spread that size says the dial matters here and the search found a real preference.

On the lattice it is 0.4579 at three by four and 1.0675 at four by six, almost all of it between the light penalties and the heavy ones, since the three cells at penalty 0.1 are within 0.0016 of each other.

spread  =  max over candidates of score  −  min over candidates of score

A spread of a few thousandths would mean the opposite, that the search had nothing to choose between and the winner was a coin toss decided by which fold happened to hold whom. On the pure-noise target of Part 5 the spread reads 1.3448, which looks like a strong preference and is entirely the difference between one neighbour memorising noise and many neighbours averaging it away, with nothing in it about which setting predicts better.

Every candidate is scored and the winner is looked for only afterwards, rather than a best-so-far being tracked and the rest discarded, because the losing scores are what the spread is made of and what the ranking is made of. On the twelve people the ranking is two, one, three, four, five, and the runner-up at 0.8944 is close enough to the winner that a reader who wanted the simpler model could take one neighbour and lose 0.0308 of cross-validated score for it.

A search that had kept only the winner could not have offered that choice.

Every cross-validated score is an estimate with noise on it, and the winner was chosen because its estimate came out largest. Part of what made it largest is the setting, and part is that its folds happened to be kind to it, and the two cannot be told apart from the number itself. So the winner’s score is biased upward by the act of its having won, and the more candidates there were, the more chances the noise had to hand one of them a lucky draw.

measured   sᵢ  =  qᵢ + eᵢ        qᵢ the true quality, eᵢ noise averaging zero

E[ max over i of sᵢ ]  ≥  max over i of qᵢ

One gap on twelve people proves nothing, since it could be those three particular people. To measure the effect we need a case where the right answer is known in advance, and the cleanest such case is a target with nothing in it to learn. The chart searches twenty-five neighbour counts against eighty rows whose target is pure noise, unrelated to any of its four columns, so no setting can honestly beat a score of zero and the horizontal line marks that ceiling.

On draw 12 the winner is seventeen neighbours at 0.0146, above the ceiling, where the mean candidate reads −0.1738. The search has found a setting that appears to explain something in data that contains nothing. The dashed line is the same seventeen neighbours scored again with the folds dealt twelve fresh ways and averaged, and it reads −0.0915, so the setting is worth less than guessing the mean and the score it won with was 0.1061 too high.

That gap is one draw, and one draw can land on either side of zero; averaged over twelve consecutive draws the winner’s score is flattering by 0.0728.

The re-score uses the same ruler as the selection, folds over the same eighty rows, rather than a fresh holdout, and the reason is a measurement I made while building the chart. Five folds of sixteen rows read every setting a little low, and over twenty draws the winner read 0.05 above a fresh-fold re-score and 0.02 below a four-hundred-row holdout, so scoring against a holdout would have hidden the flattering inside the difference between two rulers.

The argument in section 15 says the bias should grow with the number of candidates, since more draws from the noise make a larger expected maximum, and the table checks that on the same draw of noise with the search cut short at two, five, ten and twenty-five neighbour counts.

…

Averaged over twelve draws the flattering is 0.0153 with two candidates, 0.0479 with five, 0.0500 with ten and 0.0728 with twenty-five, rising every time, though not by the same step, since the added candidates from ten to twenty-five are the large neighbour counts whose scores crowd together near the mean and add little to the maximum. And on draw 12 alone the two-candidate search comes out at −0.0878, its winner scoring below its own re-score, which is the single draw landing on the wrong side that the mean over draws is there to survive.

The textbook says the bias is a property of selection and should be present whenever a winner is chosen, and the worry is that a target with real signal in it, where the candidates genuinely differ, might hide it. The last row of the table and the second button on the chart search the same twenty-five counts against a target driven by two of the four columns with noise over the top.

There the winner is three neighbours at 0.7386 against a mean candidate of 0.5834, its re-score is 0.7050, and the flattering averaged over twelve draws is 0.0185, a quarter of the noise figure. It did not vanish and it did not reverse.

I had expected it might reverse, because an earlier measurement on the ridge penalty, ten candidates on a smooth curve, came out slightly negative, with the noise between fold deals swamping a small selection bias. On this target with twenty-five candidates it came out positive on every count tried, so the honest statement is the measured one. A real signal shrinks the flattering by giving the candidates genuine differences to be separated by, and it does not remove it.

The bias came from measuring and selecting on the same numbers, so the repair is to score the winner on numbers that took no part in the selection. That is what the quarter from section 8 is for. The winner is refitted on all nine searched people, which is the usual move since the fits inside the search each saw only six, and scored once on the three held back. On the twelve people that reads 0.8720 where the winner’s own score was 0.9252.

honest score  =  R² of the winner, refitted on the searched rows,
                 on the rows held out before the search began

predicted   (57 + 63) / 2 = 60,   (71 + 76) / 2 = 73.5,   (78 + 76) / 2 = 77
missed by   1,   1.5,   5
squared     1 + 2.25 + 25  =  28.25

honest score  =  1 − 28.25 / 220.67  ≈  0.8720

The direction of that gap is what the argument predicts on average and not what every deal shows. Press the ideal-case button in the playground and the winner is one neighbour at 0.7635 while its held-out score is 0.9788, because the three people that deal held back happen to be easy ones with close neighbours on both sides. Three people are a small jury, as the held-out page measured, and a held-out score from three people says less about the winner than it says about which three they were.

There is a way to get this wrong that produces a number called honest and is the most flattering figure on the page, and it was live here for a day. Refit the winner on the held-out rows and score it on those same rows, and the result is a training score. The playground’s fourth readout is the winner fitted on the nine searched people and scored on those nine, 0.9758 at two neighbours, and the probe that separates the two procedures structurally is a search whose only candidate is one neighbour.

At one neighbour a same-rows score is exactly 1.0 on any data without duplicated heights, since every row’s nearest neighbour is itself, while the honest procedure reads 0.7825 on the three held-out people. At larger k the same-rows flattering shrinks to roughly one part in k and drowns in the noise of a small holdout, which is why the first test written for the bug was at the winner’s own k and could not tell the two apart, and why the sharp version is the one-neighbour probe.

One holdout is one deal, and section 19 showed a deal of three people saying whatever those three people say. The structural fix is to fold the holdout too. Deal the people into outer folds, run the whole search inside each outer training share with its own inner folds, refit that share’s winner and score it on the outer fold it never saw, and average those scores.

Every person then judges a winner exactly once, and no person judges a winner they helped choose. Nothing here wraps that up as one object yet, so the outer loop on this page is written by hand, one outer fold at a time over the same folds and the same search everything else on the page uses.

for each outer fold o
    search the candidates on the other outer folds, with inner folds
    refit the winner there, score it on fold o
nested score  =  mean over o

On the twelve people the four inner searches each choose one neighbour and their selection scores read 0.9170, 0.8768, 0.8443 and 0.8787, while the honest scores on the outer folds read −0.0274, 0.2718, 0.3105 and 0.9094, a mean of 0.3661 with a spread of 0.9368. A flat search over all twelve chooses two neighbours at 0.7932.

The nested figure is far below it and far more honest about how little twelve people can say, since an outer fold of three people has almost no spread of its own for a ratio to explain, and the fold judging persons 6, 8 and 9, whose weights are 63, 71 and 72, reads below zero for that reason.

On the noise draw of section 16 the same loop reads −0.1222 where the flat winner claimed 0.0146, which is the correction the procedure exists to make.

The practical rule follows from everything above. The winner’s own score is a selection score and is the right number for comparing candidates and the wrong number for saying how good the chosen model is. Write down the winner, the spread beside it so a reader can tell a real preference from a coin toss, and a score from rows that took no part in the choosing, whether that is the quarter held out before the search or the mean over a second layer of folds.

Section 16 measures that bias and the honest score sits beside it, and nothing about the procedure stops a reader from quoting the flattering number instead.

A search states its deal and its rules in full. Which model and which of its dials are varied, and that the names are checked against the model before anything is fitted; the values in each range and that the candidates are their Cartesian product; that each candidate is built through the model’s own constructor; the share held out before the search and the seed that cut it; the fold count, the seed that dealt the folds, and that one arrangement serves every candidate; the score read on a fold and how folds are combined, averaged for a regressor and pooled for a classifier; the comparison and the tie rule; that every candidate’s score is kept; and which of the winner, the spread, the honest score and the nested score it reports, with the winner’s own score labelled as a selection score.

A grid search is three things stacked, a deal of the folds, a fit on each fold, and a score, and each of the three needs something from the data before it means anything. When one of those needs goes unmet the search does not become approximate, it becomes undefined, and the honest thing is to say which of the three ran out. The table gathers the cases, with what the mathematics says in each.