Boosting
Bagging trains trees independently and averages them. Boosting trains trees sequentially, where each tree corrects the mistakes of the previous one. This reduces bias (underfitting), not just variance. Read it as an optimization procedure that happens to build a model: each round is a gradient step, but taken in function space rather than parameter space.
Real-world examples: Search ranking, click-through prediction, Kaggle competitions (XGBoost dominates tabular data).
The boosting idea
- Start with a simple model (e.g., a shallow tree)
- Find the examples it gets wrong
- Train a new model focusing on those mistakes
- Combine all models weighted by their accuracy
- Repeat until models are trained
where is the initial constant prediction (e.g. the mean of ), is the -th weak learner, and is the learning rate (shrinkage). This is the gradient-boosting form; AdaBoost (below) is the special case where each learner carries its own weight in place of a single shared .
Analogy
Imagine a student taking practice exams. After each exam, they focus on the questions they got wrong. Over time, they improve not by studying everything equally, but by targeting their weaknesses. Boosting does this with models.
AdaBoost (1995)
The original boosting algorithm:
- Initialize equal weights for all samples
- Train weak learner
- Compute weighted error:
- Compute model weight: — requires (better than random)
- Update sample weights:
- Normalize weights and repeat
Mispredicted samples get higher weights, so the next tree focuses on them.
Watch AdaBoost reweight the training set — misclassified points grow larger each round, forcing the next stump to focus on the hard examples:
AdaBoost: weight rebalancing across rounds
Each round focuses on the mistakes of previous rounds — misclassified points grow larger (higher weight). The stump's α controls how much it votes in the final ensemble.
The model weight is the exact minimizer of the exponential loss — differentiating and setting to zero yields . After the weight update, a key identity holds: the just-trained stump has exactly 0.5 weighted error on the new distribution, forcing the next stump to look elsewhere. For the full derivation, a step-by-step worked trace with weight normalization tables, and a from-scratch Python implementation:
from sklearn.ensemble import AdaBoostClassifier
from sklearn.tree import DecisionTreeClassifier
ada = AdaBoostClassifier(
estimator=DecisionTreeClassifier(max_depth=1), # "stump" — 1 split
n_estimators=200,
learning_rate=1.0,
random_state=42
)
ada.fit(X_train, y_train)
print(f"AdaBoost accuracy: {ada.score(X_test, y_test):.3f}")
Gradient Boosting
Generalizes boosting to any differentiable loss function. Each new tree fits the negative gradient (residuals) of the loss:
For MSE loss, this is simply the residual .
Worked trace: 3 rounds on a toy dataset
Five points : (1, 3), (2, 5), (3, 4), (4, 7), (5, 6). Initial prediction: .
Round 1: Residuals : [−2, 0, −1, 2, 1]. Fit a stump to these residuals. Best split: puts points 1 and 2 on the left (residuals , mean ); puts points 3–5 on the right (residuals , mean ). With :
Round 2: New residuals from : (1: 3−4.5=−1.5), (2: 5−4.5=0.5), (3: 4−5.33=−1.33), (4: 7−5.33=1.67), (5: 6−5.33=0.67). Fit another stump → the ensemble prediction moves closer to the targets.
After many rounds with a small learning rate, the ensemble converges to the underlying function.
from sklearn.ensemble import GradientBoostingClassifier
gbm = GradientBoostingClassifier(
n_estimators=200,
max_depth=4,
learning_rate=0.1,
subsample=0.8, # stochastic gradient boosting
min_samples_leaf=10,
random_state=42
)
gbm.fit(X_train, y_train)
print(f"GBM accuracy: {gbm.score(X_test, y_test):.3f}")
Learning rate vs n_estimators
These are inversely related. Lower learning rate → need more trees → better generalization. The sweet spot: - with 500-2000 trees. Always use early stopping to find the optimal number of trees.
From the idea to the engines
Modern gradient boosting lives in three libraries — XGBoost (regularized objective, sparse-aware, GPU), LightGBM (histogram splits, leaf-wise growth, native categoricals), and CatBoost. What separates them from the plain algorithm above (the regularized objective, shrinkage tuning, and subsampling) is the next lesson.
Boosting vs Bagging
| Property | Bagging | Boosting |
|---|---|---|
| Training | Parallel | Sequential |
| Bias reduction | No | Yes |
| Variance reduction | Yes | Some (via shrinkage + subsampling) |
| Overfitting risk | Low | High (if too many trees) |
| Speed | Fast (parallel) | Slow (sequential) |
| Sensitive to noise | No | Yes |
Boosting overfits easily
Boosting is more powerful than bagging but also more prone to overfitting, especially with noisy data. Always use:
- Low learning rate (0.01-0.1)
- Early stopping
- Subsample (0.8) for stochastic boosting
- Tree constraints (max_depth, min_samples_leaf)
When to use what
| Scenario | Best choice |
|---|---|
| Tabular data, default baseline | Random Forest |
| Tabular data, need best accuracy | XGBoost / LightGBM |
| Very noisy data | Random Forest (robust) |
| Need fast inference | Random Forest (parallel) |
| Kaggle competition | LightGBM or XGBoost |
| Text classification | Linear SVM or Naive Bayes |
Exercise
What is the key difference between boosting and bagging?
Need a hint?
Think about whether learners are trained independently or sequentially.
Exercise
In gradient boosting, what happens if you decrease the learning rate?
Need a hint?
Think about how many trees you'd need to compensate.
Exercise
Set the number of boosting rounds for gradient boosting on a medium-sized tabular classification task.
Need a hint?
More trees = lower training loss, but too many overfit. Use early stopping to find the sweet spot.
Common mistakes
- Too many trees without early stopping: Boosting will keep improving training accuracy long past the point of overfitting. Always use early stopping.
- High learning rate: is usually too aggressive. Use 0.01-0.1.
- Ignoring categorical features: XGBoost/LightGBM handle categoricals natively. Don't one-hot encode everything.
Key takeaways
- Boosting builds models sequentially, each fixing the last ensemble's mistakes — cutting bias.
- AdaBoost reweights errors; gradient boosting fits residual gradients.
- XGBoost/LightGBM are fast, regularized gradient boosting — top tabular performers.
- Lower
learning_rate+ more trees generalizes better; boosting can overfit if unregularized.
Related concepts
- Bagging & Random Forests: the parallel, variance-reducing ensemble
- Gradient Boosting in Practice: XGBoost: the regularized engine built on this recipe
- Decision Trees: the weak learner that gets boosted