Gradient Boosting

Forward stagewise additive trees fit to the loss gradient.

The idea

Gradient boosting builds a predictor as a running sum of weak learners. Begin with a crude $F_0$, and at each round add one term: $F_m(x) = F_{m-1}(x) + \nu\, h_m(x).$ A round never revisits earlier terms; it only chooses the next $h_m$, and it chooses it to correct what the sum so far still gets wrong. The individual $h_m$ are weak — shallow trees, typically — and none is expected to fit the data on its own.

The loss decides which errors count. Suppose we minimize $L(y, F)$, and treat the current predictions $F(x_{i})$ as free variables. The direction that decreases $L$ fastest is the negative gradient $-\partial L/\partial F$ at those predictions, so we fit the new $h_m$ to those values, one target per training point. For squared error $L = \tfrac{1}{2}(y - F)^{2}$ the negative gradient is $y - F_{m-1}(x)$, the residual, so each tree fits the errors the sum has left over. A different loss puts a different target there.

Algorithm.

Algorithm: Gradient Boosting Input: training set, differentiable loss L(y, F), rounds M, learning rate ν Output: predictor F, a sum of M weak learners 1. F = initial constant fit 2. compute each point's target: the negative gradient -∂L/∂F at F(x) // for squared error, the residual y - F(x) 3. fit a weak learner h to those targets 4. F = F + ν h // a shrunk step; earlier terms are never revisited 5. if M rounds have run, return F 6. go to step 2

The factor $\nu \in (0, 1]$, the learning rate, takes only part of the step the new learner proposes. Small $\nu$ keeps any single term from moving the prediction far, so more rounds are needed and no one tree dominates the result.

Ways to work on it

• Walkthrough. Residuals as the negative gradient, the stagewise update, and shrinkage.
• Practice. Apply one shrunk stagewise update.
• Hardest. Run two rounds and find the next negative-gradient target.

Not sure where to start? Take the ten-question placement test.