Gradient Boosting Systems

Boosting methods train predictors sequentially, with each model attempting to correct its predecessor’s errors.

AdaBoost (Adaptive Boosting)

AdaBoost focuses on misclassified instances by adjusting their weights:

1. Initialize all instance weights to $w^{(i)} = 1/m$.
2. Train a base predictor and calculate its weighted error rate $r_j$.
3. Compute the predictor weight $\alpha_j = \eta \log((1-r_j)/r_j)$, where $\eta$ is the learning rate.
4. Update instance weights: increase weights for misclassified instances and decrease them for correctly classified instances.
5. Normalize weights and repeat.

Gradient Boosting

Unlike AdaBoost, Gradient Boosting trains models on the residual errors of the previous predictor.

For regression with squared error loss, the target for predictor $h_t(x)$ is the residual:

$r_t^{(i)} = y^{(i)} - \sum_{k=1}^{t-1} \eta h_k(x^{(i)})$

The final prediction aggregates all estimators:

$\hat{y}^{(i)} = \sum_{t=1}^{T} \eta h_t(x^{(i)})$

In classification, Gradient Boosting fits new trees to minimize the pseudo-residuals of the loss function, which are the negative gradients of the loss.

Histogram-Based Gradient Boosting

Modern implementations (like XGBoost, LightGBM, and scikit-learn’s HistGradientBoostingRegressor) bin continuous features into integer bins (e.g., 256 bins). This reduces the computational complexity of finding splits from $O(300 \times n \log n)$ to $O(300 \times n \text{ bins})$, speeding up training on large datasets.

Example: Residual Learning

The following example demonstrates fitting successive decision trees to residual errors:

import numpy as np
from sklearn.tree import DecisionTreeRegressor

# Target function: quadratic with noise
X = np.random.rand(50, 1) - 0.5
y = 3*X[:, 0]**2 + 0.05 * np.random.randn(50)

# Model 1
tree_reg1 = DecisionTreeRegressor(max_depth=2)
tree_reg1.fit(X, y)

# Train on residuals
y2 = y - tree_reg1.predict(X)
tree_reg2 = DecisionTreeRegressor(max_depth=2)
tree_reg2.fit(X, y2)

# Combined prediction
sample = [[0.2]]
pred = tree_reg1.predict(sample) + tree_reg2.predict(sample)
print(f"Gradient Boosted prediction: {pred[0]:.4f}")

Gradient Boosted prediction: ...

Exercise

Test your understanding of the boosting process:

Shrinkage and Estimator Limits

In gradient boosting, learning rate $\eta$ is also known as shrinkage. A low learning rate (e.g., $\eta = 0.01$) paired with more trees allows the model to converge smoothly, increasing generalization performance on tabular data.

References & Further Reading

• Géron, A. (2022). Hands-On Machine Learning (3rd ed.). O’Reilly Media.