Gradient Boosting Trees and XGBoost

Gradient boosting is the workhorse of tabular machine learning. From Kaggle competitions to production fraud detection, boosted trees consistently outperform neural networks on structured data. Here's how it works, from first principles to XGBoost.

Ensemble Methods: The Core Idea

The metaphor is teamwork. A single weak learner — a model barely better than random guessing — can't solve hard problems. But combine many weak learners, and you get a strong one.

Two fundamentally different approaches:

Method	Strategy	Parallelism	Weak Learners
Bagging (Bootstrap Aggregating)	Train each model independently on random data subsets, then average	Fully parallel	High-variance models (deep trees)
Boosting	Train models sequentially, each correcting the previous one's errors	Inherently sequential	Low-variance models (shallow trees)

Bagging reduces variance. Boosting reduces bias. Random Forest is the most famous bagging method. Gradient boosting — and XGBoost specifically — dominates among boosting methods.

Gradient Boosting: From First Principles

Step 1: Start with a Constant Prediction

The simplest possible model: predict the mean of the target variable for all observations.

For a regression problem predicting weight (kg) from features like height, gender, and favorite color:

Initial prediction: mean(weights) = 72.2 kg

Step 2: Compute Residuals

Residuals are the errors — what the model hasn't captured yet:

Height (m)	Gender	Favorite Color	Weight (kg)	Initial Pred.	Residual
1.6	Male	Blue	88	72.2	+15.8
1.7	Female	Green	76	72.2	+3.8
1.5	Female	Blue	56	72.2	−16.2
1.8	Male	Red	77	72.2	+4.8
1.6	Female	Green	64	72.2	−8.2

Step 3: Train a Weak Learner on the Residuals

Fit a shallow decision tree (typically depth 2–6) to predict the residuals, not the original target. The tree splits on the features that best separate positive and negative residuals:

Tree splits:
  1. Gender = Female?
     → Yes: Height < 1.7?  → Yes: predict −2.2
                            → No: predict +4.8
     → No: Favorite Color = Blue? → Yes: predict +15.8
                                   → No: predict −16.2

Step 4: Update Predictions

Add the tree's predictions, scaled by a learning rate η (typically 0.01–0.3), to the running prediction:

New prediction = Previous prediction + η × tree_prediction

A small learning rate means each tree contributes only a tiny correction — which seems inefficient, but is essential for generalization. More trees (hundreds or thousands) compensate for the small step size.

Step 5: Repeat

Steps 2–4 repeat: compute new residuals, fit another tree, update predictions. Each tree corrects a small portion of the remaining error.

Why "Gradient" Boosting?

The "gradient" in gradient boosting comes from optimization theory. The residual at each step is proportional to the negative gradient of the loss function with respect to the current prediction.

For mean squared error (MSE) loss:

Loss = Σ(y_true − y_pred)² / n
Gradient = −2 × (y_true − y_pred) / n  =  −2 × residual / n

By fitting trees to the negative gradient, gradient boosting performs gradient descent in function space — each tree is a step in the direction that most reduces the loss.

This generalizes beyond MSE: you can use any differentiable loss function (log loss for classification, Huber loss for robustness, quantile loss for prediction intervals). The tree just fits the gradient of whichever loss you choose.

XGBoost: Gradient Boosting at Scale

XGBoost (eXtreme Gradient Boosting) took the core ideas and made them production-ready. Key innovations:

Regularization

Standard gradient boosting can overfit. XGBoost adds L1 (Lasso) and L2 (Ridge) regularization terms to the objective function, penalizing both the number of leaves and leaf weights. This is a major reason XGBoost dominates in competitions where overfitting is the enemy.

Second-Order Approximation

XGBoost uses a second-order Taylor expansion of the loss function, incorporating both the gradient (first derivative) and Hessian (second derivative). This provides a more accurate approximation of how the loss changes with each split, leading to better split choices.

Weighted Quantile Sketch

For large datasets, finding optimal split points by scanning every value is expensive. XGBoost's weighted quantile sketch algorithm finds approximate split candidates in a single pass, weighted by the Hessian of each instance — faster and nearly as accurate as exact greedy search.

Sparsity Awareness

Real-world data has missing values. XGBoost learns the optimal default direction for missing values at each split. If a feature is missing, the instance goes left or right depending on which direction minimizes loss. No imputation needed.

System Optimizations

• Column block structure: data stored in compressed column (CSC) format for parallel split finding
• Cache-aware access: block structure enables prefetching and minimizes non-contiguous memory access
• Out-of-core computation: processes data that doesn't fit in memory by compressing blocks to disk

XGBoost vs. Alternatives

Feature	XGBoost	LightGBM	CatBoost	Random Forest
Tree growth	Level-wise	Leaf-wise	Symmetric	Independent
Categorical support	Manual encoding	Manual encoding	Native	Manual encoding
GPU training	Yes	Yes	Yes	Limited
Missing values	Learned	Handled	Handled	Imputation needed
Regularization	L1 + L2	L1 + L2	L2	None

When to use each:

• XGBoost: General purpose, strong defaults, excellent documentation
• LightGBM: Very large datasets (100M+ rows), faster training, leaf-wise can overfit on small data
• CatBoost: Heavy categorical features, minimal preprocessing needed
• Random Forest: Baseline model, interpretable, robust to hyperparameters

Practical Tips

1. Start with default hyperparameters — XGBoost's defaults are excellent. Tune only when necessary.
2. Use early_stopping_rounds — stop training when validation performance plateaus. Prevents overfitting without guessing tree count.
3. Scale features for linear models, not trees — tree-based models are invariant to monotonic feature scaling.
4. Watch the learning rate × n_estimators trade-off — lower learning rates need more trees. 0.1 with cross-validation to find optimal rounds is a good starting point.
5. Feature importance ≠ causality — XGBoost's built-in importance scores (gain, cover, weight) show which features the model uses, not causal relationships.
6. For imbalanced classification, use scale_pos_weight or a custom evaluation metric like AUC rather than accuracy.

Download the Full Presentation

For a step-by-step walkthrough with visual decision trees, residual plots, and ensemble method comparisons, download the lecture slides:

→ Download: Gradient Boosting Trees and XGBoost (PDF)