Ensemble Models Part 2: Gradient Boosting & XGBoost

Welcome to Part 2 of our Ensemble Models series!

In Part 1: Decision Trees & Random Forest, we studied the parallel approach of building independent, deep trees to reduce variance (overfitting).

In this post, we shift focus to the sequential family: Boosting. Instead of averaging independent models, boosting builds models one after another, where each new model is trained to correct the errors made by its predecessors.

---

⚡ 1. The Sequential Approach: Boosting

Boosting combines multiple weak learners (typically shallow decision trees, e.g., max_depth=3) to create a strong learner.

The Golf Analogy

Think of Boosting like taking shots in golf:

• Shot 1 (Tree 1): You swing. The ball lands 20 yards to the right of the hole. (Your error or “residual” is +20).
• Shot 2 (Tree 2): Instead of starting from scratch, you adjust your stance to correct for that 20-yard error. You swing again, overshoot, and land 2 yards to the left (New residual = -2).
• Shot 3 (Tree 3): You make a micro-adjustment to correct for the 2-yard error.

In boosting, each tree is trained to predict the residuals (errors) of the collective ensemble up to that point.

---

📉 2. Gradient Boosting

Gradient Boosting generalizes boosting by framing the learning process as a gradient descent optimization in the functional space.

Instead of adjusting sample weights, it trains a new tree to predict the negative gradient of the loss function (which, in the case of Mean Squared Error, is exactly equal to the residuals).

The Role of the Learning Rate (Shrinkage)

If we add the new tree’s predictions directly, the model will adapt too quickly and overfit. To prevent this, we multiply each tree’s prediction by a Learning Rate (\(\eta\)), typically between 0.01 and 0.1:

\[ \text{New Prediction} = \text{Old Prediction} + (\text{Learning Rate} \times \text{New Tree Prediction}) \]

Using a low learning rate means we take small, controlled steps towards the target, preventing us from overshooting. However, a lower learning rate requires you to train more trees (n_estimators).

---

🚀 3. XGBoost (Extreme Gradient Boosting)

XGBoost is a highly regularized, hardware-optimized implementation of Gradient Boosting that has dominated machine learning competitions and industrial projects since its release in 2014.

Here are the key mathematical and algorithmic optimizations that make XGBoost “Extreme”:

A. The Regularized Objective Function

Standard Gradient Boosting will keep adding splits until it perfectly fits every training point. XGBoost prevents this by adding regularization terms directly to its objective function:

\[ \mathcal{L}^{(t)} = \sum_{i=1}^n l\left(y_i, \hat{y}_i^{(t-1)} + f_t(x_i)\right) + \Omega(f_t) \]

Where the regularization term \(\Omega(f_t)\) is defined as:

\[ \Omega(f_t) = \gamma T + \frac{1}{2} \lambda \sum_{j=1}^T w_j^2 \]

• \(T\) is the number of leaves in the tree.
• \(w_j\) is the weight of leaf \(j\).
• \(\gamma\) (minimum loss reduction required to split) and \(\lambda\) (L2 regularization on weights) act as mathematical brakes to restrict model complexity.

B. Second-Order Taylor Approximation

To find the best splits quickly, XGBoost uses a second-order Taylor expansion of the loss function:

\[ \mathcal{L}^{(t)} \approx \sum_{i=1}^n \left[ l(y_i, \hat{y}^{(t-1)}) + g_i f_t(x_i) + \frac{1}{2} h_i f_t^2(x_i) \right] + \Omega(f_t) \]

Where:

• \(g_i = \frac{\partial l(y_i, \hat{y}^{(t-1)})}{\partial \hat{y}^{(t-1)}}\) is the gradient (first derivative).
• \(h_i = \frac{\partial^2 l(y_i, \hat{y}^{(t-1)})}{\partial (\hat{y}^{(t-1)})^2}\) is the Hessian (second derivative).

This allows the algorithm to optimize any loss function that is twice-differentiable (e.g., custom loss functions for asymmetric costs) and speeds up calculation times.

C. Sparsity-Aware Split Finding (Missing Values)

Real-world datasets often have missing values (NaN). XGBoost handles them natively:

• During training, at each split node, XGBoost routes missing values to the left child and measures loss reduction, then routes them to the right child.
• It automatically learns the best path for missing data and stores it as the “default direction” for production inference.

D. Weighted Quantile Sketch

To split continuous features, traditional models must sort all values, which is extremely slow for massive datasets. XGBoost uses a Weighted Quantile Sketch to construct candidate split points based on the feature distribution, allowing it to evaluate splits in parallel.

---

Hyperparameter Tuning Blueprint: XGBoost

• learning_rate (or eta): Step size shrinkage to prevent overfitting.
  • Tuning Tip: E.g., 0.05. Lower values are more robust but require more trees.
• n_estimators & Early Stopping:
  • Tuning Tip: Set n_estimators high (e.g., 1000) and use early stopping (e.g., stop if validation performance does not improve for 20 rounds).
• max_depth: The maximum depth of each tree.
  • Effect: Kept shallow (typically 3 to 8) since boosting models are ensembles of weak learners. Deep trees in boosting lead to rapid overfitting.
• subsample & colsample_bytree:
  • Effect: Fraction of rows and columns to sample for each tree. E.g., 0.8 adds row/feature randomization, which combats overfitting.
• gamma (min_split_loss): The minimum loss reduction required to make a split.
  • Effect: Acts as a regularization threshold.
• reg_alpha (L1) & reg_lambda (L2):
  • Effect: L1 and L2 regularization terms on leaf weights. Increasing these forces the weights to be smaller, smoothing out predictions.

---

📊 4. Bagging vs. Boosting Comparison

Dimension	Random Forest (Bagging)	XGBoost (Boosting)
How they are built	In Parallel: Trees are grown independently.	Sequentially: Trees are grown one after the other.
Base Model Type	Deep Trees: High-variance, low-bias (fully grown).	Shallow Trees: High-bias, low-variance (weak learners).
Primary Goal	Reduce Variance (combats overfitting).	Reduce Bias (combats underfitting).
Overfitting Risk	Low: Adding more trees never causes overfitting.	High: Adding too many trees will cause overfitting.
Tuning Difficulty	Easy: Works very well with default settings.	Harder: Requires careful tuning of learning rate and tree depth.
Feature Scaling	Not Required	Not Required

---

🎯 What’s Next?

In Part 3: Practical Pipeline & Hyperparameter Tuning, we will step away from the slide deck and look at concrete Python code, building a pipeline to train, tune, and evaluate these models.