Gradient boosting: the illustrated regression

Gradient boosting is a popular machine-learning technique used in both regression and classification problems. It works by iteratively adding weak learners, which are usually based on decision trees, to form a strong predictive model. In this topic, we will perform the calculations for gradient boosting in the regression setting.

The setup

In order to comprehend the gradient boosting stages, let's run gradient boosting on the following dataset:

A clarification on the loss function is required. The squared error loss ($L = (y^{(i)} - \hat{y})^2$) with a scaling factor of $1/2$ has an extremely convenient derivative, so it will be easy to demonstrate the steps of the algorithm:

$$\frac{\partial }{\partial h( x^{(i)})} \frac{1}{2}(y^{(i)} - h(\mathbf{x}^{(i)}))^2 = 2 \times \frac{1}{2} (y^{(i)} - h(\mathbf{x}^{(i)})) \times (0-1) \\= -(y^{(i)} -h(\mathbf{x}^{(i)} )) = h(\mathbf{x}^{(i)}) - y^{(i)} \\ \rightarrow r_i = -(h(\mathbf{x}^{(i)}) - y^{(i)}) = y^{(i)} - h(\mathbf{x}^{(i)})$$

For the reasons explained above, we set the loss to squared error loss with a scaling factor of $1/2$. For the sake of simplicity, only 2 iterations will be performed, so $T = 2$.

Initialize the model

To make a prediction based on all training examples at a given node in a decision tree, we can simply compute the average target value for all examples that reach that node, but for demonstration purposes, we will be more careful and stick to the formal algorithm.

$$h_0(\mathbf{x}) = \argmin_{\hat{y}} \sum \limits_{i=1}^n L(y^{(i)}, \hat{y}) = \argmin_{\hat{y}} \sum \limits_{i=1}^n \frac{1}{2} (y^{(i)} - \hat{y})^2$$

Now, we have to find the prediction, $\hat{y}$, that minimizes the sum:$$\sum \limits_{i=1}^n \frac{1}{2} (y^{(i)} - \hat{y})^2$$The derivative of the loss is equal to $y^{(i)} - \hat{y}$, so we set the sum to 0, expand, and solve for $\hat{y}$:

$$\sum \limits_{i=1}^5 \frac{\partial L}{\partial \hat{y}} =0 \rightarrow (0.5 - \hat{y}) + (0.5 - \hat{y})+ (5 - \hat{y})+ (2.2 - \hat{y}) + (2.8 - \hat{y}) =0 \\ \rightarrow 11 = 5 \hat{y} \rightarrow \hat{y} = 2.2$$

So, this particular loss function $h_0(\mathbf{x})$ is just the average of the target values:

$$h_0(\mathbf{x}) = \frac{1}{n} \sum\limits_{i=1}^n y^{(i)} = 2.2$$

Computing the gradients

Since we already know what the partial derivative looks like, the $r_1$ simplifies to

$$r_1 = y_1 - \hat{y_1}$$

In this case, the gradient vector looks like $$(0.5 - 2.2, 0.5-2.2, 5 -2.2,2.2-2.2, 2.8 - 2.2 ) = (-1.7, -1.7, 2.8, 0, 0.6)$$Next, we fit a decision tree on the obtained gradients:

If you are wondering how the decision boundaries were obtained (i.e., why was the HouseAge feature split on $<=43$), consider reading an article about How Decision Trees Split Nodes, from Loss Function Perspective. In this topic, we will get two identical trees on both iterations (meaning they share the decision boundaries and the samples that end up in the leaf are the same). In practice, since each consecutive tree is fitted on the negative gradients (which are re-computed and changed from iteration to iteration), different splitting boundaries might be selected to build the new tree.

Below, we go through the terminal node value calculation from the definition.

Let's say that the node $[\text{samples} = 1, \text{value} = 0.6]$ is the first leaf (denoted by $R_{j,t}$, where $j$ is the node index, and $t$ is the tree index in the procedure, so the first leaf will be $R_{1,1}$), and the node $[\text{samples} = 2, \text{value} = -1.7]$ is the second leaf (denoted by $R_{2, 1}$). Sample #5 ends up in the $R_{1,1}$, and samples #1 and #2 end up in $R_{2, 1}$.

Then, calculating the update: $$\hat{y}_{1, 1} = \argmin_{\hat{y}} \sum \limits_{x^{(i)} \in R_{i, j}} L(y^{(i)}, h_{t-1}(\mathbf{x}^{(i)}) + \hat{y}) = \argmin_{\hat{y}} \frac{1}{2} (y^{(5)} - (h_0(\mathbf{x}^{(5)}) + \hat{y} ))^2 \\ = \argmin_{\hat{y}} \frac{1}{2} (2.8 - (2.2 + \hat{y}))^2 = \argmin_{\hat{y}} \frac{1}{2} (0.6 - \hat{y})^2 \rightarrow [\text{minimizing}] \\ \frac{1}{2}(0.6 - \hat{y})^2 = 0 \rightarrow\hat{y} = 0.6$$

The calculation for the $R_{2, 1}$ will be similar, with the only difference being that we are minimizing the sum of the two losses:

$$\hat{y}_{2, 1} = \argmin_{\hat{y}} \big [ \frac{1}{2} (y^{(1)} - (h_0(\mathbf{x}^{(1)}) + \hat{y} ))^2 + \frac{1}{2} (y^{(2)} - (h_0(\mathbf{x}^{(2)}) + \hat{y} ))^2 \big]$$

Note: due to the choice of the loss function, the terminal regions, in this case, will be the average of the samples that ended up in that leaf, and, since we have two equal values in the $R_{2, 1}$, its predicted value is $\frac{-1.7 - 1.7}{2} = -1.7$, however, if the two (or any $n$) samples in the leaf had different values, with this loss function we would take their average. Calculation of the prediction with a different loss and $n$ samples would be akin to the $\hat{y}_{2, 1}$ equation with respect to the selected loss and $n$ terms in the sum.

Updating the predictions

We update the predictions, which yield:

$$h_1(\mathbf{x}) = h_0 (\mathbf{x}) + \alpha \sum\limits_{j=1}^4 \hat{y}_{j, 1}$$

Represented graphically, the prediction after the first round is:

Now, we can predict for a single sample. Let's consider the fifth sample (which ends up in the terminal node with the value 0.6), the prediction will be $h_1(x_5) = 2.2 + 0.1\cdot0.6 = 2.26$.

We can see that, compared to the initial prediction ($h_0(x)$), $\hat{y}_1$ moves closer to the true targets (MedHouseVal).

The second boosting round

Next, we can re-compute the gradients for the second round:

$$r_2 = (y^{(i)} - \hat{y}_1^{(i)}) = (0.5 - 2.03, 0.5-2.03, ..., 2.8 -2.26) \\= (-1.53, -1.53, 2.52, 0, 0.54)$$

Now, the updated prediction after the two rounds is:

$$h_2(\mathbf{x}) = h_0 (\mathbf{x}) + \alpha \sum\limits_{j=1}^4 \hat{y}_{j, 1} + \alpha \sum\limits_{j=1}^4 \hat{y}_{j, 2}$$

The updated set of predictions is:$$\hat{y}_2 = (2.03+0.1 \cdot (-1.53), ..., 2.26 + 0.1 * 0.54) = (1.877, 1.877, 2.732, 2.2, 2.314)$$Again, we see that the predictions iteratively move closer to the real targets:

Conclusion

As a result, you are now familiar with:

• The general workflow for gradient boosting in the regression setting;
• How to calculate the gradients and use them to update the predictions;
• How gradient boosting makes the predictions move closer to the target values over the consecutive boosting rounds.