Gradient Boosting from Scratch

Gradient boosting is one of the most powerful and widely-used techniques in machine learning, forming the backbone of champion models in data science competitions and industrial applications alike. While libraries like XGBoost, LightGBM, and CatBoost provide highly optimized implementations, truly understanding how the algorithm works from the ground up transforms you from a user into an architect. By building it step-by-step, you gain an intuitive grasp of its mechanics, empowering you to customize models and tune hyperparameters with precision, rather than relying on trial and error.

The Intuition Behind Boosting

At its core, gradient boosting is an ensemble learning technique that builds a strong predictive model by combining many weak, simple models—typically decision trees with limited depth. The fundamental idea is sequential correction. Imagine a student taking practice exams. After the first attempt, they review their incorrect answers (residuals). They then focus their next study session specifically on those missed concepts (fits a new model to the errors). With each round, their performance improves by systematically addressing weaknesses. Gradient boosting operates on this same principle: it starts with a naive guess, calculates the error of the current ensemble, and then adds a new model that specifically tries to correct that error.

This process is formalized as an additive model, where the final prediction is the sum of the predictions from all the sequential weak learners. Each new learner is a small step in the right direction, guided by the gradient of a loss function. This perspective is crucial because it frames the entire procedure as a form of functional gradient descent, where we are "descending" the error landscape of our model in the space of possible functions.

Step 1: Initialization with a Constant Model

Every journey needs a starting point. Gradient boosting begins by making an initial, very simple prediction for all samples. This is typically the value that minimizes the overall loss function for the target variable. For the common squared error loss $L(y,\hat{y})=(y-\hat{y}{)}^2$, the optimal constant prediction is the mean of the target values.

Mathematically, we initialize our model $F_0(x)$ as: $$F_0(x)=\arg \underset{\gamma }{\min }\sum _{i=1}^{n}L(y_i,\gamma )$$ For squared error, $\gamma$ is simply the mean: $\bar{y}$. So, $F_0(x)=\bar{y}$ for all inputs $x_i$. This constant model is our baseline. All subsequent steps will iteratively add adjustments to this starting point.

Step 2: Computing Pseudo-Residuals

Now, we enter the iterative loop that defines boosting. For each iteration $m=1$ to $M$ (where $M$ is the total number of trees we want to build), we calculate the so-called pseudo-residuals. These are not simple errors, but rather the negative gradient of the loss function with respect to the current model's predictions.

For observation $i$, the pseudo-residual $r_{im}$ is: $$r_{im}=-{\left[\frac{\partial L(y_i,F(x_i))}{\partial F(x_i)}\right]}_{F(x)=F_{m-1}(x)}$$

Let's make this concrete with squared error loss. The loss is $L(y,F)=\frac{1}{2}(y-F{)}^2$. The derivative with respect to $F$ is $-(y-F)$. The negative gradient is therefore $y-F$. Thus, for squared error, the pseudo-residual for an observation is simply its plain residual: the difference between the true value and the current predicted value.

These pseudo-residuals become the new target for our next weak learner. Instead of trying to predict the original $y$, we are now building a model to predict how far off our current ensemble is. This is the "gradient" in gradient boosting.

Step 3: Fitting a Weak Learner to the Residuals

With our new targets $r_{im}$ in hand, we fit a weak learner—almost always a regression tree—to this pseudo-residual data. We use the original features $x_i$ to predict the residuals $r_{im}$. The key here is that the tree is constrained to be weak; it is often limited to a small number of terminal leaves (e.g., between 4 and 8), a maximum depth of 3-6, or a minimum number of samples per leaf. This constraint is vital. We do not want a strong, deep tree that perfectly fits the residuals, as that would lead to overfitting and break the sequential, additive improvement process.

Think of this step as identifying patterns in our current mistakes. The tree partitions the feature space into $J$ regions (terminal leaves) $R_{jm}$, grouping together samples with similar residuals.

Step 4: Computing the Output Value for Each Leaf

After the tree is fitted, we cannot simply add its raw predictions. For each terminal leaf region $R_{jm}$ of the tree, we need to compute an optimal output value ${\gamma }_{jm}$. This value is the multiplier that, when added to the current model's prediction for samples in that leaf, results in the greatest reduction in overall loss.

For a given leaf region $R_{jm}$, we find ${\gamma }_{jm}$ by solving: $${\gamma }_{jm}=\arg \underset{\gamma }{\min }\sum _{x_i\in R_{jm}}L(y_i,F_{m-1}(x_i)+\gamma )$$

For squared error loss, this has a simple closed-form solution: it is the average of the pseudo-residuals that ended up in that leaf. For other loss functions (like absolute error or logistic loss), this step may require a line search or a Newton-Raphson step. This is where loss function customization becomes a powerful lever. By changing $L$, you change how residuals are calculated and how leaf values are optimized, allowing you to tailor the model for specific tasks like robust regression or classification.

Step 5: Updating the Model with the Learning Rate

Finally, we update our additive model. We take the current model $F_{m-1}(x)$ and add the new tree's contribution, scaled by a learning rate $\nu$ (also called the shrinkage parameter). $$F_m(x)=F_{m-1}(x)+\nu \cdot \sum _{j=1}^J{\gamma }_{jm}I(x\in R_{jm})$$

The learning rate, typically a small value like 0.01, 0.1, or 0.3, is a critical regularization hyperparameter. It controls how much each new tree contributes to the ensemble. A smaller learning rate makes each step more cautious, requiring more trees (boosting rounds) to achieve the same performance but often leads to a better generalization and a smoother optimization path. This additive update is the heart of the sequential building process.

Common Pitfalls

1. Using Deep Trees as Weak Learners: A common misconception is that stronger base learners yield a stronger ensemble. In gradient boosting, the opposite is true. Using deep, complex trees allows each one to fit the residuals too well, causing the algorithm to converge quickly and overfit. The power comes from many small, sequential corrections. Always restrict tree depth (max_depth=3-6 is a good start) and consider limiting the number of leaves.

2. Ignoring the Learning Rate and Number of Trees Trade-off: The learning rate $\nu$ and the number of boosting rounds $n\_estimators$ are deeply intertwined. A very small learning rate (e.g., 0.01) requires a very large number of trees to converge, increasing computational cost. A good practice is to set the learning rate low (for better generalization) and then use early stopping—halting training when validation performance stops improving—to determine the optimal number of trees automatically.

3. Misinterpreting Feature Importance: While gradient boosting provides robust feature importance measures (often based on how much a feature reduces loss across all trees), these can be misleading with correlated features. The importance may be spread arbitrarily among correlated predictors. Understanding that the model is additive helps you see that it's the combined sequential use of features that matters, not just the raw importance score of a single one.

Summary

• Gradient boosting builds a strong model sequentially by adding weak learners (shallow trees) that correct the errors of the current ensemble, formalized as an additive model.
• The algorithm is guided by the gradient of a loss function, where pseudo-residuals point in the direction of greatest error reduction for each observation.
• The learning rate is a crucial regularization tool that scales the contribution of each new tree, controlling the speed of learning and requiring a careful balance with the number of boosting rounds.
• Understanding the internal steps—from residual calculation to leaf value optimization—empowers you to customize loss functions for specific tasks and make informed hyperparameter tuning decisions, moving beyond black-box usage to principled model design.