XGBoost › Example

Let's work through a concrete example to demonstrate how XGBoost builds trees and makes predictions. We'll use a simple regression problem with a small dataset to make the calculations manageable.

Consider a dataset with 6 samples for predicting house prices based on two features: square footage (sqft) and number of bedrooms (bedrooms):

We'll use mean squared error as our loss function: $l(y, \hat{y}) = \frac{1}{2}(y - \hat{y})^2$. The first and second derivatives are:

• $g_i = \frac{\partial l}{\partial \hat{y}} = -(y_i - \hat{y}_i)$
• $h_i = \frac{\partial^2 l}{\partial \hat{y}^2} = 1$

Step 1: Initialize with the mean We start by predicting the mean of all target values:

$$\hat{y}^{(0)} = \frac{200000 + 250000 + 150000 + 300000 + 220000 + 280000}{6} = 233,333$$

Step 2: Calculate gradients for the first tree For each sample, we calculate the gradient:

• Sample 1: $g_1 = -(200000 - 233333) = 33,333$, $h_1 = 1$
• Sample 2: $g_2 = -(250000 - 233333) = -16,667$, $h_2 = 1$
• Sample 3: $g_3 = -(150000 - 233333) = 83,333$, $h_3 = 1$
• Sample 4: $g_4 = -(300000 - 233333) = -66,667$, $h_4 = 1$
• Sample 5: $g_5 = -(220000 - 233333) = 13,333$, $h_5 = 1$
• Sample 6: $g_6 = -(280000 - 233333) = -46,667$, $h_6 = 1$

Step 3: Build the first tree Let's say we create a simple tree that splits on sqft < 1100:

• Left leaf (sqft < 1100): samples 1, 3, 5
• Right leaf (sqft ≥ 1100): samples 2, 4, 6

For the left leaf:

$$w_1 = -\frac{33333 + 83333 + 13333}{1 + 1 + 1 + \lambda} = -\frac{130000}{3 + \lambda}$$

For the right leaf:

$$w_2 = -\frac{-16667 - 66667 - 46667}{1 + 1 + 1 + \lambda} = -\frac{-130000}{3 + \lambda} = \frac{130000}{3 + \lambda}$$

Note: The negative sign in the right leaf calculation comes from the fact that we're taking the negative of a negative sum, which results in a positive value. This reflects that samples in the right leaf (larger houses) need positive corrections to their predictions.

If we set $\lambda = 1$ (L2 regularization):

• $w_1 = -\frac{130000}{4} = -32,500$
• $w_2 = \frac{130000}{4} = 32,500$

Step 4: Update predictions After the first tree:

• Sample 1: $\hat{y}^{(1)} = 233333 + (-32500) = 200,833$
• Sample 2: $\hat{y}^{(1)} = 233333 + 32500 = 265,833$
• Sample 3: $\hat{y}^{(1)} = 233333 + (-32500) = 200,833$
• Sample 4: $\hat{y}^{(1)} = 233333 + 32500 = 265,833$
• Sample 5: $\hat{y}^{(1)} = 233333 + (-32500) = 200,833$
• Sample 6: $\hat{y}^{(1)} = 233333 + 32500 = 265,833$

We can see that the first tree has started to correct the initial predictions, moving them closer to the actual values. The process continues iteratively, with each subsequent tree focusing on the remaining prediction errors.