Gradient Boosting

The page answers six questions in order. What does one round of boosting actually fit, and why is the miss on each reading the direction in which the error falls fastest? How do stumps, each nearly useless alone, assemble into the arc of the throw, and what happens to the misses as they do? What does the learning rate change, and is a small rate with more rounds really the better model once it is measured?

How deep should each member be? When do we stop adding rounds, and how would we know? And how does this differ from bagging, which also grows many trees, and from AdaBoost, which also grows them in sequence?

Everything starts from the laziest possible model. The fifteen readings of the full throw have a mean height of 12.76 metres, so the first prediction is 12.76 at every time, before any tree exists. That flat line misses the reading at the launch by 12.06 metres, since the ball was at 0.7, and misses the reading at two seconds by 8.24 in the other direction, since the ball was at 21.0. Squaring the fifteen misses and adding them up gives 654.36, which is what every later round is trying to bring down.

prediction₀(t) = mean of the heights
residualᵢ = hᵢ − prediction(tᵢ)

On the three readings the page works by hand, heights of 2, 6 and 10 at one, two and three seconds, the mean is 6 and the residuals are −4, 0 and 4, with squares adding to 32. The signs matter. A residual says how far off the prediction is and in which direction, and the direction is what the next round needs.

A stump is a tree one question deep. It asks whether the time is below some threshold and answers with one number on each side, the mean of whatever it was fitted to among the readings on that side. The first thing to notice about a boosting round is that the stump is never shown the heights. It is shown the residuals, and its whole job is to predict the current mistakes.

left:   6 + 0.5·(−4) = 4
right:  6 + 0.5·(2)  = 7
predictions   4, 7, 7
residuals     2−4, 6−7, 10−7   =   −2, −1, 3
squared total 4 + 1 + 9 = 14

On the full throw the first stump asks whether t is below 0.43, the midpoint between the second and third readings, and answers −9.81 on the left, the mean of the two launch residuals −12.06 and −7.56, and 1.51 on the right, the mean of the other thirteen. Adding three tenths of that takes the flat 12.76 to 9.82 for the two early readings and 13.21 for the rest, and the squared total falls from 654.36 to 541.09.

Fitting the residual looks like a rule of thumb, and the word gradient in the name is the claim that it is more than that. Take one reading, hold its true height y still, and ask how the squared error changes as the committee’s prediction p for that reading moves. The error is the squared miss with the conventional half in front.

E = ½·(y − p)²
dE/dp = −(y − p)

The slope of the error with respect to the prediction is minus the residual. Downhill is the direction that lowers the error, which is the opposite of the slope, so downhill is the residual’s own direction and its own size. A reading the committee under-predicts by 4 wants its prediction raised, and the residual says 4; a reading it over-predicts by 4 wants it lowered, and the residual says −4.

The calculus primer walked downhill on a curve by moving a setting a fraction of the slope in the downhill direction. Here the thing being moved is the prediction itself, one per reading, rather than a setting, and a step of size η reads as follows.

p  ←  p − η·dE/dp  =  p + η·(y − p)

That is exactly what a round does, with one substitution. The residual y − p is known for every training reading, and a stump fitted to those residuals is a rule that can say approximately what the residual is for any time, the readings it saw and the times between them alike. So the stump stands in for the gradient, η times its answer is the step, and the walk takes place in the space of possible prediction rules rather than in the space of a few coefficients.

On the three readings the step from 6 to 4 and 7 was this line applied by hand.

With the start, the residual and the step in hand, the method is four lines and a loop.

prediction₀ = mean of the heights
for each round r = 1 … R
    residualᵢ = hᵢ − prediction(tᵢ)          for every reading
    fit a small tree to the residuals
    prediction ← prediction + η · tree

Round one left predictions of 4, 7 and 7 and residuals of −2, −1 and 3. Round two fits a stump to those.

left:   4 − 0.75 = 3.25     and     7 − 0.75 = 6.25
right:  7 + 1.5  = 8.5
predictions   3.25, 6.25, 8.5
residuals     −1.25, −0.25, 1.5
squared total 3.875

The stepper runs the same three readings, and the lower picture shows the two-shelf stump each round fits to the bars it is handed.

…

The bars below carry the same run onward. Round zero is the flat mean’s leftover of 32, one round cuts it to 14, two leave 3.875, and by the eighteenth round the leftover reads zero to six decimals, since three readings at three distinct times can be matched exactly by enough shelves.

Now the fifteen readings at a rate of 0.3. The upper picture is the committee’s answer after the current round, with the previous answer left faint behind it; the lower picture is what the next round is handed, every reading’s miss as a bar, with the stump the round fits to those misses drawn over them. Step forward and watch the bars shrink.

…

The first three stumps ask whether t is below 0.43, then below 3.57, then below 0.715, which is the launch, then the landing, then the launch again, because the two ends of the arc are where a flat line is most wrong and each correction leaves the other end as the largest remaining miss. The squared total goes 654.36, 541.09, 434.59, 359.77.

By ten rounds it is 111.58 and R² is 0.829; by twenty, 28.55 and 0.956; by thirty, 9.82 and 0.985; by sixty, 1.84 and 0.997. The largest single miss handed to round one was 12.06 metres and the largest handed to round sixty is 1.24.

A claim worth checking rather than trusting. At a rate of 0.3 the squared leftover on the fifteen readings fell at every one of the sixty rounds, and at a rate of 1.0 it fell at every one as well, from 654.36 to 432.27 after the first round and to 0.77 after sixty. I measured both sequences and neither ever went up.

The fitted curve is built entirely out of shelves, since every member is a tree and a tree’s answer is constant between its thresholds. A hundred stumps hold two hundred shelves between them and the arc in the playground is the staircase they add up to, close enough at that count to read as a curve and still a staircase.

A round fits a stump to the residuals and could add all of it. The learning rate says how much to add instead, and the effect on a single reading is easy to follow. If the stump answers the residual r exactly for that reading, adding η of it leaves a residual of (1 − η)·r for the next round.

residual after the round = r − η·r = (1 − η)·r

On the three readings the launch residual of −4 became −2 after round one at a rate of a half, which is this line with η at 0.5. On the full throw the first stump is the same stump whatever the rate, t below 0.43 with answers −9.81 and 1.51, and keeping all of it leaves a squared total of 432.27 where keeping three tenths left 541.09.

The larger rate takes more of the correction now, and the question the rest of this part asks is whether taking less now and more rounds later ends somewhere better.

To measure this we need readings the committee never saw, and here the fifteen-point throw is too small an instrument. The site’s seeded deal holds out four of its fifteen readings, at 0.0, 0.29, 2.86 and 3.43 seconds, and the first two lie before the first training reading at 0.57, where the previous section showed a tree answers with a flat shelf.

The held-out score there is mostly a verdict on extrapolation, and the best any rate reached on it was 0.204. So this part and the next two use the same throw measured sixty times, the button in the playground, which the same deal cuts into forty-two training readings and eighteen held out, and whose held-out times run from 0.11 to 3.92 seconds against training times from 0.25 to 3.88.

…

Read the table under the curves. At a rate of 1.0 the training score passes 0.95 at round 14, the held-out score is highest at round 77, where it reads 0.8985, and by round 300 it has come back down to 0.8857. At 0.3 the training score passes 0.95 at round 26, the held-out score peaks at round 217 at 0.8963 and is 0.8951 at 300.

At 0.1 the training score needs 86 rounds and the held-out score is still rising at round 300, where it reads 0.8914. At 0.05 it takes 176 rounds to train and the held-out score at 300 is 0.8794, still short of where the others got.

The usual claim is that a small rate with many rounds beats a large rate with few, and I measured it on this throw and found that it did not hold. The best held-out scores the four rates reached were 0.8794, 0.8914, 0.8963 and 0.8985, within 0.02 of one another and increasing with the rate, and the largest of them belongs to the rate of 1.0.

What the smaller rates changed was not the height of the peak; it was when the peak came and how gently the curve fell after it. At 1.0 the score had given back 0.013 by round 300, at 0.3 it had given back 0.001, and at 0.1 it had not turned at all.

Holding the product of rate and rounds fixed makes the trade visible. At a total step of 30 the rates of 0.1 and 0.3 come within 0.001 of each other on both scores, and 1.0 is 0.006 behind on the held-out one, so on this throw the rate and the round count trade almost one for one and the smaller rate is buying a wider, flatter plateau rather than a higher one.

That is a real thing to buy, since it makes the stopping round of Part 5 far less delicate, and it is not the thing the textbook sentence promises. The claim is usually made about tables with many features, more noise and deeper members, where each round has more room to commit to something spurious, and none of those conditions holds for stumps on a single time column.

The line in section 10 says what happens if the rate is pushed past one, and it is worth reading before the playground refuses it. At a rate of 1.5 a residual r is left as −0.5·r, so every fitted miss changes sign and keeps half its size, and at 2.5 it is left as −1.5·r, larger than it started.

η = 1.5:   r − 1.5·r = −0.5·r
η = 2.5:   r − 2.5·r = −1.5·r

Between one and two each round overshoots the mistake it just fitted and the leftover still shrinks, though by reflection rather than approach; past two the leftover grows every round and the fit runs away, which is the calculus primer’s runaway in prediction space. No committee is built with a rate above one at all, so the playground slider hands you its refusal in words when you cross that mark rather than a diverging curve. The primer’s descent slider is where the runaway itself can be watched.

A stump adds two shelves a round. A member two questions deep can add four, and one of depth d up to 2 to the power d, so depth is how much correction a single round is allowed to express. On data with several features depth also decides whether a member can express an interaction, a rule that depends on two features at once, and a stump cannot.

The throw has one feature, time, so there is no interaction to express and depth here is purely a matter of how fast the arc is roughed out.

The same curves as before, with the rate held at 0.1 and the depth varied instead.

…

Deeper members reach the training threshold sooner, in 86, 26, 19 and 17 rounds, and their held-out score peaks sooner too, at rounds 299, 97, 58 and 36. The peaks themselves are 0.8914, 0.8911, 0.8928 and 0.8875, so the depth changed almost nothing about how good the committee could get on this throw. What it changed was what happens afterwards.

At depth one the held-out score has not turned by round 300; at depths two, three and four it has fallen to 0.8802, 0.8783 and 0.8780, giving back 0.011, 0.015 and 0.010 of what it had reached, while the training score keeps rising towards 0.9937.

Push depth to its limit and the reason for keeping the member weak is measured rather than argued. A member six questions deep, kept in full at a rate of 1.0, explains 0.9877 of the training spread in its first round and scores 0.8889 on the held-out readings, which is nearly the whole job done by one tree.

Its second round nudges the held-out score to 0.8893, and from the fifth round on the training score is 0.9937 and the held-out score is 0.8780, where both stay for the remaining 295 rounds because there is nothing left for a later round to fit except noise, and every later round fits it.

The ceiling of 0.9937 is not a failure. Three of the training times appear twice with different heights, at 0.77, 3.01 and 3.15 seconds, and no rule that reads only the time can tell the two readings of a pair apart, so their mean is the best any tree can do there and the leftover from those pairs is permanent.

Section 8 showed the training leftover can only fall, and the previous part showed the held-out score reaching a peak. Put both on one picture, for three configurations chosen because their turns are easy to see, and the training scores are the dashed lines.

…

Take the third configuration, depth three at the full rate. Its training score is 0.914 after one round, 0.9934 after ten, and reaches its ceiling of 0.9937 soon after, while its held-out score peaks at round 5 at 0.8963, is 0.8785 by round 10, and stays at 0.8780 from round 20 onward. The stumps at the full rate do the same thing more slowly, peaking at round 77 at 0.8985 and reading 0.8857 at round 300 while the training score rises from 0.9819 to 0.9914 over the same rounds.

The round to stop at is the one where the held-out score was highest, and for the three configurations above that is round 5, round 24 and round 77, with held-out scores of 0.8963, 0.8915 and 0.8985 there. The price of running to 300 instead was 0.018, 0.013 and 0.013 of R². Those are small numbers on eighteen held-out readings, and the held-out page measured how far one seeded deal’s verdict moves when the seed changes, so a difference of that size between two configurations is not a finding about the configurations.

What the curves do establish is the shape, a rise, a broad top and a slow fall, and that the fall begins hundreds of rounds before the training score stops improving.

Bagging got its honest score for free, because every member missed about a third of the readings and those readings could judge it. Boosting has no such readings. Every round is fitted on every row, so no member has a row it never saw, and the held-out readings have to be supplied from outside, by a deal as above or by the folds the held-out page builds.

On the same forty-two training readings the deep bagged trees of Part 6 report an out-of-bag score of 0.9029 beside a held-out score of 0.8761, and the boosted stumps can report only the second.

Every committee on this page is the plain form of the method and not the stochastic one, where each round is fitted on a random fraction of the rows and the rest can judge it, so there is no out-of-bag estimate to show here, and the page says so rather than inventing one.

The three settings are one decision about how much correction the committee is allowed to accumulate and how finely it is dispensed. Section 12 held the product of rate and rounds fixed and found the two smaller rates coming within 0.001 of each other; section 15 held the rate fixed and found depth moving the peak from round 299 to round 36 without raising it. So a sensible search fixes the depth low, chooses a rate small enough that the plateau is wide, and lets a held-out curve choose the round count, which is the procedure the search page lays out with the round count read off the curve rather than gridded.

Bagging and boosting both grow many trees on the same readings, and what each tree is shown is the whole difference. A bagged member is fitted to the heights, on a resample that drew some readings twice and missed others. A boosted member is fitted to every reading, on a target column that is not the heights at all.

…

The first three bagged members drew 27, 27 and 28 distinct readings of the 42, and every target they were shown is a height between 4.5 and 21.7 metres, the arc itself with some readings doubled and some absent. The first three boosted rounds were shown all 42 readings each time, and their targets are residuals, the largest 10.13, 10.60 and 8.67 metres, with squared totals of 1142.7, 952.9 and 784.6 falling round by round as the committee explains more of the arc.

Read across the bagged row and the pictures are the same shape with different readings; read across the boosted row and the readings are the same and the shape is changing.

Hand the two frames the same stump and the difference in what they make of it is the clearest measurement on the page.

…

Fifty bagged stumps score 0.4758 on the training readings and 0.2727 held out, because the average of fifty two-shelf rules is a smoothed two-shelf rule, and no amount of averaging supplies a shape none of the members has. Fifty boosted stumps at a rate of 0.3 score 0.9767 and 0.8832, because each stump was fitted to what the others left and the sum of fifty different two-shelf rules is a hundred-shelf staircase.

Fifty deep bagged trees score 0.9849 and 0.8761, which is the frame that averages handed the member built for averaging, and it reaches the boosted stumps’ held-out score within 0.007 by the opposite route.

AdaBoost is the other sequential committee, and from a distance it looks the same, one weak member after another, each aimed at what the last got wrong. The mechanism is different in every line. Every round is fitted to the same labels, on the same rows, and what changes between rounds is how much each row counts.

A row the last member got wrong has its weight raised, a row it got right has its weight lowered, and the next member is fitted on the reweighted rows, so it is pulled towards the hard cases without ever seeing a residual. The members are then combined by a weighted vote in which a member that did well on its weighted rows gets a louder voice, where a boosted regression gives every round the same rate.

The two are cousins rather than strangers. Friedman, Hastie and Tibshirani showed that AdaBoost is the same stagewise additive fitting under the exponential loss, and seen from the gradient view the reweighting is what that loss’s negative gradient looks like when the members are classifiers. AdaBoost here is a classifier and the throw is a regression, so there is no side-by-side fit to show on this page, and the contrast is stated rather than measured.

A complete implementation states the loss, since the residual is only the negative gradient of squared error and another loss changes both the start and what each round fits; the starting constant; the member and every setting it carries, its maximum depth and the fewest rows a split and a leaf may hold; the number of rounds; the learning rate and the range it is allowed; whether a per-leaf step length is searched after the tree is fitted or the leaf mean is taken as it is; whether any row subsampling happens per round, which is what would give an out-of-bag estimate; how a committee of fewer rounds relates to a longer one; and how a query at a time outside the readings is answered. Each of those is a place two implementations can quietly disagree while both report a fit.

Every row below was tried on the model itself and, where this page’s door lets it through, through the page as well. Some are refused, some are accepted with an answer worth knowing, and some are accepted and documented rather than defended.

Two of those deserve the extra sentence. The leaf-minimum row is the case where a model fits, predicts and scores without ever having learned anything, and nothing anywhere says so, since a flat mean is a legal answer; that one is on the reader to notice. And the learning rate’s bound is enforced by the constructor rather than by a data check, which is the right place for a setting whose failure does not depend on the data, and it means the refusal is not one this page can translate, only anticipate.