Gradient Boosting
Gradient Boosting is one of the most powerful ensemble learning algorithms used in Machine Learning. It is the foundation of popular algorithms such as XGBoost, LightGBM, and CatBoost.
Instead of building one large decision tree, Gradient Boosting builds many small decision trees one after another. Every new tree tries to correct the mistakes made by the previous trees.
In this article, we will understand the intuition behind Gradient Boosting and explain Step 1 of the algorithm in detail.
What is Gradient Boosting?
Suppose we want to predict
$$
Y=f(X)
$$
where
- $X$ = Input Features
- $Y$ = Target Variable
Our goal is to find the mathematical function
$$
f(x)
$$
that best maps the input to the output.
Instead of finding this function directly, Gradient Boosting constructs it piece by piece.
Every new model improves the prediction of the previous model.
Intuition
Imagine a student solving a mathematics problem.
First attempt:
❌ Wrong
Teacher points out the mistakes.
Second attempt:
Much better.
Teacher again points out the remaining mistakes.
Third attempt:
Almost correct.
Gradient Boosting works exactly like this.
Instead of building one perfect model, it continuously improves previous predictions.
Additive Modeling
Suppose the final prediction function is
$$
Y=f(x)
$$
Gradient Boosting assumes
$$
f(x)=f_0(x)+f_1(x)+f_2(x)+\cdots+f_M(x)
$$
where
- $f_0(x)$ = Initial prediction
- $f_1(x)$ = First decision tree
- $f_2(x)$ = Second decision tree
- ...
- $f_M(x)$ = Last decision tree
Each new model adds some correction.
Instead of replacing the previous model,
it adds to it.
This is why Gradient Boosting is called an Additive Model.
Example Dataset
Suppose our dataset is
| R&D | Operations | Marketing | Profit |
|---|---|---|---|
| 145 | 24 | 105 | 32 |
| 12 | 58 | 27 | 57 |
| 59 | 97 | 109 | 89 |
Here,
Input Features
X=(R&D ,Operations, Marketing)
Target
$$
Y=Profit
$$
Mathematically,
$$
D={(x_i,y_i)}_{i=1}^{N}
$$
where
- $x_i$ represents one row of input features.
- $y_i$ represents the actual output.
Loss Function
A machine learning model predicts
$$
\hat{Y}=f(x)
$$
The prediction may not be exactly equal to the actual value.
To measure the prediction error, we use a Loss Function.
Mathematically,
$$
L(Y,\hat{Y})
$$
or
$$
L(Y,f(x))
$$
where
- $Y$ = Actual value
- $\hat{Y}$ = Predicted value
Gradient Boosting requires the loss function to be differentiable because it computes gradients (derivatives) while training.
Squared Error Loss (decision)
For decision problems, the most common loss function is
$$
L(Y,\hat{Y})=
\frac12
\sum_{i=1}^{N}
(Y_i-\hat{Y}_i)^2
$$
Complete Gradient Boosting Algorithm
Input
Training Dataset
$$
{(x_i,y_i)}_{i=1}^{N}
$$
Differentiable Loss Function
$$
L(y,f(x))
$$
Number of Iterations
$$
M
$$
Step 1
Initialize
f_0(x)=\operatorname*{argmin}_{\gamma}\sum_{i=1}^{N}L(y_i,\gamma)
Step 2
For
$$
m=1,2,\ldots,M
$$
Step 2(a)
Compute pseudo residuals
$$
r_{im}=-
\left[
\frac{\partial
L(y_i,f(x_i))}
{\partial f(x_i)}
\right]_
{f=f_{m-1}}
$$
Step 2(b)
Train a decision Tree using
$$
r_{im}
$$
The tree creates terminal regions
$$
R_{jm},
\qquad
j=1,2,\ldots,J_m
$$
Step 2(c)
For every terminal region,
compute
\gamma_{jm}=
\operatorname*{argmin}_{\gamma}
\sum_{x_i\in R_{jm}}L
\left(
y_i,
f_{m-1}(x_i)+\gamma
\right)
Step 2(d)
Update the model
$$
f_m(x)=
f_{m-1}(x)
+
\sum_{j=1}^{J_m}
\gamma_{jm}
I(x\in R_{jm})
$$
where
$$
I(x\in R_{jm})=
\begin{cases}
1,&x\in R_{jm}\
0,&\text{otherwise}
\end{cases}
$$
Output
Final Prediction Function
$$
\hat f(x)=f_M(x)
$$
Step 1: Initialization
The first question is:
How do we start Gradient Boosting if we don't have any tree yet?
Initially,
there is no model.
Therefore,
the algorithm begins with only one constant value.
Mathematically,
f_0(x)=
\operatorname*{argmin}_{\gamma}
\sum_{i=1}^{N}
L(y_i,\gamma)
Here,
$\gamma$ is simply a constant prediction.
Our objective is to find the constant value that minimizes the total loss.
Why Does It Become the Mean?
Using squared error loss,
$$
L=
\sum_{i=1}^{N}
(y_i-\gamma)^2
$$
Differentiate with respect to
\gamma
$$
\frac{d}{d\gamma}
\sum_{i=1}^{N}
(y_i-\gamma)^2=
0
$$
Expanding,
$$
-2
\sum_{i=1}^{N}
(y_i-\gamma)=
0
$$
Removing the constant,
$$
\sum_{i=1}^{N}
(y_i-\gamma)=
0
$$
Rearranging,
$$
\sum_{i=1}^{N}
y_i=
N\gamma
$$
Finally,
$$
\boxed{
\gamma=
\frac1N
\sum_{i=1}^{N}
y_i
}
$$
Therefore,
the initial prediction is simply the mean of the target values.
Numerical Example
Our target values are
| Profit |
|---|
| 32 |
| 57 |
| 89 |
The mean is
$$
\frac{32+57+89}{3}=
59.33
$$
Therefore,
f_0(x)=59.33
Notice something interesting.
The first model is not a decision tree.
It is simply one constant value.
Every training sample initially receives the same prediction.
| Actual Profit | Initial Prediction |
|---|---|
| 32 | 59.33 |
| 57 | 59.33 |
| 89 | 59.33 |
$$
f_0(x) = \bar{Y} = 59.3
$$
Therefore, every training sample is initially predicted as 59.3.
| R&D | Operations | Marketing | Actual Profit ($Y$) | $f_0(x)$ |
|---|---|---|---|---|
| 145 | 24 | 105 | 32 | 59.3 |
| 12 | 58 | 27 | 57 | 59.3 |
| 59 | 97 | 109 | 89 | 59.3 |
Step 2(a)
For each boosting iteration,
$$
m = 1 \text{ to } M
$$
compute the pseudo residual for every training sample:
r_{im}=-
\left[
\frac{\partial L(Y_i,f(x_i))}
{\partial f(x_i)}
\right]_{f=f_{m-1}}
where
- $i$ = row (training sample)
- $m$ = boosting iteration
Since this is the first iteration, we substitute
$$
f=f_0
$$
Therefore,
$$
r_{i1}=-
\left[
\frac{\partial L(Y_i,f_0(x_i))}
{\partial f_0(x_i)}
\right]
$$
Loss Function
For decision, we use the Squared Error Loss:
$$
L(Y,\hat{Y})=
\frac12
\sum_{i=1}^{n}
(Y_i-\hat{Y}_i)^2
$$
Since
$$
\hat{Y}=f_0(x_i)
$$
the loss becomes
$$
L=
\frac12
\sum_{i=1}^{n}
(Y_i-f_0(x_i))^2
$$
Differentiate the Loss Function
Differentiate with respect to $f_0(x_i)$.
$$
r_{i1}=-
\frac12
\frac{\partial}
{\partial f_0(x_i)}
\sum_{i=1}^{n}
(Y_i-f_0(x_i))^2
$$
Taking the derivative,
$$
r_{i1}=
f_0(x_i)-Y_i
$$
Because the pseudo residual contains a negative sign,
$$
-\left(f_0(x_i)-Y_i\right)=
Y_i-f_0(x_i)
$$
Hence, the pseudo residual is simply
$$
r_{i1}=
Y_i-f_0(x_i)
$$
which is the actual value minus the current prediction.
Calculate the Residual for Every Row
Row 1
$$
r_{11}=
32-59.3=
-27.3
$$
Row 2
$$
r_{21}=
57-59.3=
-2.3
$$
Row 3
$$
r_{31}=
89-59.3=
29.7
$$
Residual Table
| R&D | Operations | Marketing | Profit | $f_0(x)$ | Residual ($r_1$) |
|---|---|---|---|---|---|
| 145 | 24 | 105 | 32 | 59.3 | -27.3 |
| 12 | 58 | 27 | 57 | 59.3 | -2.3 |
| 59 | 97 | 109 | 89 | 59.3 | 29.7 |
What is a Pseudo Residual?
The pseudo residual is the error made by the current model.
It tells us how much the prediction differs from the actual value.
For squared error loss,
$$
\text{Pseudo Residual}=
Y-\hat{Y}
$$
where
- $Y$ = actual value
- $\hat{Y}$ = prediction made by the current model
These residuals become the target values for the next decision tree.
Step 2(b): Train the Next decision Tree
Now we train a new decision tree using the residuals.
M0 ---------> M1
(Mean) (decision Tree)
Input Features
- R&D
- Operations
- Marketing
Target
Residuals
$$
r_1=
[-27.3,,-2.3,,29.7]
$$
Instead of predicting the original output (Profit), the second model learns to predict the errors made by the first model.
The first model predicts the average value.
The second model learns how to correct those prediction errors.
Terminal Regions
After training the decision tree, the data is divided into several terminal regions (leaf nodes).
A terminal region is simply the final leaf node of a decision tree.
Each terminal region stores one value that will later be added to the model prediction to reduce the residual error.
Example:
Root
/ \
○ ○
/ \
○ ○
Number of terminal regions = 3
These three leaf nodes correspond to
- Region 1
- Region 2
- Region 3
-------------------------------
Region 1 | Region 2 | Region 3
-------------------------------
x x | x x | x
x | x | x x
-------------------------------
Each training sample belongs to exactly one terminal region.
Step 2(c): Compute the Output Value of Each Terminal Region
After the decision tree is built, we compute the output value for every terminal region.
The equation is
\gamma_{jm}=
\operatorname*{argmin}_{\gamma}
\sum_{x_i\in R_{jm}}
L\left(
Y_i,
f_{m-1}(x_i)+\gamma
\right)
where
- $R_{jm}$ = terminal region
- $\gamma_{jm}$ = value stored in the leaf node
- $m$ = boosting iteration
- $j$ = terminal region number
- $L$ = Loss function
- $\gamma$ = Output value stored in the leaf node
For our example,
- $m=1$
- $j=1,2,3$
Example
Suppose one terminal region contains only
$$
Y_3
$$
Then,
$$
\gamma_{11}=
\operatorname*{argmin}_{\gamma}
L
\left(
Y_3,
f_0(x_3)+\gamma
\right)
$$
Since we are using Squared Error Loss,
$$
L=
(Y_3-f_0(x_3)-\gamma)^2
$$
Differentiate with respect to $\gamma$
$$
\frac{d}{d\gamma}
(Y_3-f_0(x_3)-\gamma)^2=0
$$
Applying the chain rule,
$$
-2
(Y_3-f_0(x_3)-\gamma)=
0
$$
Divide both sides by $-2$
$$
Y_3-f_0(x_3)-\gamma=
0
$$
Therefore,
$$
\boxed{
\gamma=
Y_3-f_0(x_3)
}
$$
Numerical Calculation
Previously,
$$
f_0(x)=59.3
$$
For Region 1,
$$
\gamma_{11}=
89-59.3=
29.7
$$
Similarly,
$$
\gamma_{21}=
57-59.3=
-2.3
$$
and
$$
\gamma_{31}=
32-59.3=
-27.3
$$
Therefore,
| Terminal Region | Output Value |
|---|---|
| Region 1 | 29.7 |
| Region 2 | -2.3 |
| Region 3 | -27.3 |
These values become the prediction values of the leaf nodes.
Step 2(d): Update the Model
After computing the output value of every terminal region, the model is updated.
The update equation is
$$
f_m(x)=
f_{m-1}(x)+
\sum_{j=1}^{J_m}
\gamma_{jm}
I(x\in R_{jm})
$$
where
- $J_m$ = Number of terminal regions
- $\gamma_{jm}$ = Output value of the $j^{th}$ region
- $I(x\in R_{jm})$ = Indicator function
The indicator function is defined as
$$
I(x\in R_{jm})=
\begin{cases}
1, & x\in R_{jm} \
0, & \text{otherwise}
\end{cases}
$$
This means that only the output value of the region containing the input sample is added to the prediction.
First Model Update
For the first boosting iteration,
$$
m=1
$$
Therefore,
$$
f_1(x)=
f_0(x)+
\text{decision Tree}_1
$$
where
- $f_0(x)$ = Initial prediction (mean)
- decision Tree$_1$ = First tree trained using pseudo residuals
Example
Suppose we continue training.
Second iteration
$$
f_2(x)=
f_1(x)+
\text{decision Tree}_2
$$
Third iteration
$$
f_3(x)=
f_2(x)+
\text{decision Tree}_3
$$
Fourth iteration
$$
f_4(x)=
f_3(x)+
\text{decision Tree}_4
$$
Fifth iteration
$$
f_5(x)=
f_4(x)+
\text{decision Tree}_5
$$
Substituting repeatedly,
$$
\boxed{
f_5(x)=
f_0(x)+
\text{decision Tree}_1
+
\text{decision Tree}_2
+
\text{decision Tree}_3
+
\text{decision Tree}_4
+
\text{decision Tree}_5
}
$$
This is called Additive Modeling because every new decision tree adds a correction to the previous model.
Complete Workflow
Training Data
│
▼
Initialize Model (Mean)
│
▼
Compute Pseudo Residuals
│
▼
Train decision Tree
│
▼
Create Terminal Regions
│
▼
Compute γ for Each Region
│
▼
Update the Model
│
▼
Repeat Until M Trees
│
▼
Final Prediction
Key Takeaways
- Gradient Boosting starts with the average target value.
- Pseudo residuals represent the errors of the current model.
- A decision tree is trained on these residuals.
- Each leaf node stores an output value $\gamma$.
- The model is updated by adding the prediction of the new tree.
- Every new tree corrects the mistakes made by the previous trees.
- The final prediction is the sum of all previous models.
Conclusion
Gradient Boosting builds an ensemble of decision trees sequentially.
Instead of fitting the original target values repeatedly, each new tree learns the remaining errors made by the previous model.
By continuously minimizing the loss function and updating the model step by step, Gradient Boosting produces highly accurate predictions and forms the foundation of advanced algorithms such as XGBoost, LightGBM, and CatBoost.
Extra
Gradient Boosting performs stage-wise optimization in function space. We start with an initial function, calculate the negative gradient of the loss, and use a weak learner such as a decision tree to approximate that gradient. We then add the learner to the existing function using a learning rate. Each subsequent tree focuses on the remaining error of the current ensemble. Hyperparameters such as tree depth, learning rate, and number of estimators control the complexity and generalization of the final model.
Hand written notes