Boosted Trees › Example

Let's work through a detailed step-by-step example of boosted trees using a simple regression dataset. Suppose we want to predict house prices based on house size and number of bedrooms.

Given Data:

We have a small dataset of houses, each described by its size (in square feet), number of bedrooms, and price (in thousands):

• House Size (sq ft): [1200, 1500, 1800, 2000, 2200, 2500, 2800, 3000]
• Bedrooms: [2, 3, 3, 4, 4, 4, 5, 5]
• House Price (thousands): [180, 220, 260, 300, 340, 380, 420, 460]

Step 1: Initialize the model

The first step in gradient boosting is to start with a simple model. For regression, this is typically just the mean of the target variable. This initial prediction is our baseline before any trees are added.

$$F_0(\mathbf{x}) = \frac{1}{8} \sum_{i=1}^{8} y_i = \frac{180 + 220 + 260 + 300 + 340 + 380 + 420 + 460}{8} = 320$$

So, at this point, our model predicts 320 for every house, regardless of its features.

Step 2: Calculate pseudo-residuals for the first tree

Next, we measure how well our initial model is doing by calculating the errors (residuals) for each data point. In gradient boosting, these are called "pseudo-residuals" and, for mean squared error (MSE) loss, they are simply the difference between the true value and the current prediction.

$$r_{i1} = y_i - F_0(\mathbf{x}_i) = y_i - 320$$

Calculating these for each house:

• House 1: 180 - 320 = -140
• House 2: 220 - 320 = -100
• House 3: 260 - 320 = -60
• House 4: 300 - 320 = -20
• House 5: 340 - 320 = 20
• House 6: 380 - 320 = 60
• House 7: 420 - 320 = 100
• House 8: 460 - 320 = 140

These residuals represent the errors our current model makes, and the next tree will try to predict these errors.

Step 3: Train the first tree on pseudo-residuals

We now fit a decision tree to these pseudo-residuals. The tree tries to find patterns in the features (house size and bedrooms) that explain the errors made by the initial model. For simplicity, suppose the tree splits the data as follows:

• If House Size ≤ 2000: predict -80
• If House Size > 2000: predict 80

This means the tree has learned that smaller houses tend to be under-predicted (so it adds a negative correction), and larger houses are over-predicted (so it adds a positive correction).

Step 4: Find optimal step size

For each leaf of the tree, we determine how much to move the prediction in the direction suggested by the tree. This is done by finding the step size (also called the "shrinkage" or "learning rate") that minimizes the loss for the data points in that leaf. For the left leaf (House Size ≤ 2000):

$$\gamma_{11} = \arg\min_{\gamma} \sum_{i: \text{size}_i \leq 2000} (y_i - (320 + \gamma \cdot (-80)))^2$$

This optimization finds the best value of $\gamma$ to reduce the error for the houses in this group. The same process is repeated for the right leaf.

Step 5: Update the model

We update our model by adding the predictions from the first tree, scaled by the optimal step size:

$$F_1(\mathbf{x}) = F_0(\mathbf{x}) + \gamma_1 h_1(\mathbf{x}) = 320 + \gamma_1 h_1(\mathbf{x})$$

Here, $h_1(\mathbf{x})$ is the prediction from the first tree for input $\mathbf{x}$, and $\gamma_1$ is the step size we just computed.

Step 6: Calculate new pseudo-residuals

With the updated model, we again compute the pseudo-residuals, which now reflect the errors remaining after the first tree's corrections:

$$r_{i2} = y_i - F_1(\mathbf{x}_i)$$

These new residuals are typically smaller in magnitude, as the model has improved.

Step 7: Repeat the process

We repeat steps 3-6 for each subsequent tree. Each new tree is trained to predict the current residuals (errors), and the model is updated accordingly. Over time, the ensemble of trees becomes better at capturing the patterns in the data, as each tree focuses on the mistakes of the previous ones.

Final Prediction:

After training $M$ trees, the final prediction for a new data point is the sum of the initial prediction and the contributions from all the trees:

$$\hat{y} = F_0(\mathbf{x}) + \sum_{m=1}^{M} \gamma_m h_m(\mathbf{x}) = 320 + \sum_{m=1}^{M} \gamma_m h_m(\mathbf{x})$$

In summary, this example illustrates how boosted trees work: starting from a simple model, they iteratively add trees that correct the errors of the current ensemble, gradually building a more accurate predictor by focusing on the hardest-to-predict cases at each step.