Gradient Boosting Machines (GBM)

Five points, nowhere near a straight line. At 0 rounds the fit is just the flat average — bad everywhere. Each round after that fits a small step to whatever's still left over, and the curve bends closer to the data.

This is gradient boosting. Start from the simplest possible model — a constant — then repeatedly fit a new small model to whatever the current ensemble still gets wrong, and add it in:

• $F_0(x)$ — the starting prediction: just the training mean $\bar{y}$, before any model has run.
• $F_m(x)$ — the ensemble's prediction after $m$ rounds.
• $h_m(x)$ — round $m$'s new "weak learner", here a single-split regression stump.

$h_m$ is fit to each point's pseudo-residual — the negative gradient of the loss with respect to the current prediction. For squared-error loss $L = \frac{1}{2}(y - F)^2$, that gradient works out to something completely ordinary:

• $r_i^{(m)}$ — point $i$'s pseudo-residual going into round $m$.
• $y_i$ — point $i$'s true target value.

1. Squared-error loss makes it literal

   For squared-error loss, "fit the negative gradient" and "fit the ordinary leftover residual" are the exact same instruction — that's why the very first boosting example anyone sees is usually just "fit the residuals," with the gradient framing hidden underneath.

2. Any differentiable loss plugs into the same recipe

   Swap in a different differentiable loss (say, one built for classification) and the pseudo-residual formula changes, but the outer loop — fit a small model to the current gradient, add it in, repeat — doesn't.

3. Every round only ever sees what's still wrong

   Round $m$'s stump never sees $y$ directly — only $r^{(m)}$, the part of $y$ that $F_{m-1}$ hasn't explained yet. Whatever the ensemble already gets right stays untouched.

Watch the residual list shrink as rounds are added — this is the "pseudo-residual" input each new stump is actually trained on, made visible.

Five points: $(1,1), (2,2), (3,8), (4,9), (5,13)$.

1. F0 is just the mean

   $\bar{y} = (1+2+8+9+13)/5 = 6.6$. Each point's residual going into round 1 is $y_i-6.6$:

   • $x=1$: $1-6.6=-5.6$
   • $x=2$: $2-6.6=-4.6$
   • $x=3$: $8-6.6=1.4$
   • $x=4$: $9-6.6=2.4$
   • $x=5$: $13-6.6=6.4$

   Squaring and summing: $(-5.6)^2+(-4.6)^2+1.4^2+2.4^2+6.4^2 = 31.36+21.16+1.96+5.76+40.96 = 101.2$.

2. Round 1's stump finds the split at x = 2.5

   Splitting into $\{1,2\}$ and $\{3,4,5\}$:

   • Left group mean: $(-5.6-4.6)/2=-5.1$
   • Right group mean: $(1.4+2.4+6.4)/3=3.4$

   This beats every other candidate split by a wide margin. $F_1(x) = 6.6 - 5.1 = 1.5$ for $x < 2.5$, and $6.6 + 3.4 = 10$ for $x \geq 2.5$.

3. New residuals, and a new SSE

   $y-F_1$ at each point:

   • $x=1$: $1-1.5=-0.5$
   • $x=2$: $2-1.5=0.5$
   • $x=3$: $8-10=-2$
   • $x=4$: $9-10=-1$
   • $x=5$: $13-10=3$

   Squaring and summing: $(-0.5)^2+0.5^2+(-2)^2+(-1)^2+3^2 = 0.25+0.25+4+1+9=14.5$ — down from $101.2$. Real progress, but $x=3,4,5$ are still off by as much as 3.

4. Round 2 fits a fresh stump to those residuals

   Splitting at $x = 4.5$ (isolating the single worst point, $x=5$):

   • Left group mean ($x=1,2,3,4$): $(-0.5+0.5-2-1)/4=-0.75$
   • Right group mean ($x=5$): $3/1=3$

   $F_2(x) = F_1(x) - 0.75$ for $x < 4.5$, and $F_1(x) + 3 = 13$ for $x \geq 4.5$:

   • $x=1,2$: $1.5-0.75=0.75$
   • $x=3,4$: $10-0.75=9.25$
   • $x=5$: $10+3=13$

   New residuals $y-F_2$ are $0.25, 1.25, -1.25, -0.25, 0$, giving a final SSE of just $0.25^2+1.25^2+1.25^2+0.25^2+0^2=3.25$.