Gradient Boosting

Random Forest solved an important weakness of decision trees. A single tree was unstable, so Random Forest averaged many trees to make the final prediction more reliable.

But the trees in a Random Forest are trained independently. They receive different bootstrap samples, make their own predictions, and vote equally. They never talk to each other.

This raises a natural question. Instead of asking many independent trees for their opinions, what if every new tree focused specifically on the mistakes made by the previous trees?

Gradient Boosting turns an ensemble from a vote into a sequence of corrections.

Imagine predicting whether Jessie will order a burger. The first tree learns a simple rule:

Hungry?
  yes -> Burger
  no  -> No Burger

It gets some visits wrong. Maybe it predicts burger when Jessie is trying to diet. Gradient Boosting does not throw the tree away. It asks what the tree failed to explain.

Tree 1: learns the broad pattern
Tree 2: corrects dieting mistakes
Tree 3: corrects special restaurant cravings
Tree 4: corrects the remaining edge cases

Every new tree is a specialist. It does not learn the whole problem from scratch. It learns the remaining error of the current ensemble.

That is the key difference from Random Forest. Random Forest asks what everyone thinks. Gradient Boosting asks what mistake it should fix next.

Gradient Boosting also has two stories: the computations performed by the algorithm, and the optimization idea that explains the word gradient.

The Algorithm

Suppose the training set is $D=\{(x_1,y_1),\ldots,(x_n,y_n)\}$. The prediction after $m$ trees is $F_m(x)$. For regression, we usually start with the mean target value:

First compute the residual for every training example. The residual is what the current model still fails to explain.

A positive residual means the prediction was too small. A negative residual means the prediction was too large.

Next, train a shallow decision tree on the residuals, not on the original targets. If that tree is $h_1(x)$, it is learning a correction.

Then add the correction to the existing model:

The learning rate $\eta$ controls how much we trust each new tree. Smaller values make learning slower but often more stable.

The general update is:

After each update, compute new residuals, fit a new tree, and add another correction. The model is additive: every tree remains part of the final prediction.

Worked Example

Suppose the first tree predicts Jessie correctly on two visits but misses three. Instead of relearning everything, the second tree focuses on the missed visits. If only one hard case remains, the third tree spends most of its capacity explaining that remaining error.

Why It Works

Random Forest mainly reduces variance by averaging many independent trees. Gradient Boosting mainly reduces bias by building a sequence of increasingly accurate models.

Each individual tree can be weak. It may be shallow and unable to represent the full pattern alone. But the ensemble can represent a complicated function because every tree adds another correction.

The word gradient comes from optimization. Suppose we want to minimize a loss function $L(y,F(x))$. The negative gradient tells us the direction that most rapidly decreases the loss.

For squared error, the negative gradient is exactly the residual:

For other losses, such as logistic loss, the residual is replaced by the negative gradient of that loss. Each new tree approximates the direction that most reduces the current loss.

Random Forest Versus Gradient Boosting

Complexity

If we build $T$ trees, training costs approximately:

Unlike Random Forest, the trees cannot be trained independently because tree $m$ depends on the residuals left by the previous ensemble. Prediction also grows linearly with the number of trees because every tree contributes to the final prediction.

This basic version implements Gradient Boosting for regression. It starts with the mean target, repeatedly fits shallow trees to residuals, and adds each correction with a learning rate.

import numpy as np

class GradientBoostingRegressor:
    def __init__(self, n_estimators=100, learning_rate=0.1, max_depth=2):
        self.n_estimators = n_estimators
        self.learning_rate = learning_rate
        self.max_depth = max_depth
        self.initial_prediction = 0.0
        self.trees = []

    def fit(self, X, y):
        self.initial_prediction = np.mean(y)
        predictions = np.full(len(y), self.initial_prediction)
        self.trees = []

        for _ in range(self.n_estimators):
            residuals = y - predictions

            tree = DecisionTreeRegressor(max_depth=self.max_depth)
            tree.fit(X, residuals)
            correction = tree.predict(X)

            predictions += self.learning_rate * correction
            self.trees.append(tree)

        return self

    def predict(self, X):
        predictions = np.full(X.shape[0], self.initial_prediction)

        for tree in self.trees:
            predictions += self.learning_rate * tree.predict(X)

        return predictions

Libraries such as XGBoost, LightGBM, and CatBoost build on this core idea with stronger split finding, regularization, missing-value handling, categorical features, and systems-level optimizations.