Ensemble Learning

Ensemble learning combines many base models into one predictor that is more accurate and robust than any single member. The core idea is that independent errors partly cancel when predictions are aggregated.

Why Ensembles Help

Decompose expected error into bias, variance, and irreducible noise (see Bias-Variance Tradeoff). Ensembles attack different terms depending on how they are built.

• Averaging $M$ models with identical bias leaves the bias unchanged but shrinks the variance. If the members were independent with variance ${\sigma }^2$, the average has variance ${\sigma }^2/M$.
• Real models are correlated, so the variance floor is set by that correlation:

$\text{Var}\left(\frac{1}{M}{\sum }_i{f}_i\right)=\rho {\sigma }^2+\frac{1-\rho }{M}{\sigma }^2$

where $\rho$ is the average pairwise correlation. Driving $\rho$ down (decorrelating members) is therefore as important as adding more members.

The recipe

A good ensemble needs base learners that are individually better than chance and make errors in different places. Diverse-but-decent beats a crowd of identical experts.

Bagging

Bagging (bootstrap aggregating) trains each member on a bootstrap sample (draw $n$ points with replacement) and averages their outputs (or takes a majority vote).

• Each bootstrap sample omits about $37\%$ of the data ($(1-1/n{)}^n\to 1/e$), giving out-of-bag points that serve as a free validation set.
• It reduces variance, so it pairs best with low-bias, high-variance learners like deep unpruned decision trees.

BAGGING(data, M):
  for m in 1..M:
    S_m = bootstrap_sample(data)        # n points, with replacement
    f_m = train_base_learner(S_m)
  return x -> aggregate({f_m(x)})       # average (regression) or vote (classification)

Boosting

Boosting builds members sequentially, each new one focusing on the mistakes of the current ensemble. It mainly reduces bias, turning weak learners into a strong one.

AdaBoost

Maintain a weight on each training example, up-weighting misclassified points each round, and combine weak learners with weights based on accuracy.

ADABOOST(data, M):
  w_i = 1/n for all i
  for m in 1..M:
    h_m = train weak learner weighted by w
    err = sum of w_i over misclassified i
    alpha_m = 0.5 * ln((1 - err) / err)
    w_i <- w_i * exp(-alpha_m * y_i * h_m(x_i)); renormalize
  return x -> sign( sum_m alpha_m * h_m(x) )

• ${\alpha }_m$ grows as error shrinks, so accurate learners get more say.
• AdaBoost is equivalent to stagewise minimization of an exponential loss.

Gradient Boosting

Generalize boosting to any differentiable loss. Each new learner is fit to the negative gradient (the “pseudo-residuals”) of the loss with respect to the current predictions:

$r_i^{(m)}=-{\left[\frac{\partial L(y_i,F(x_i))}{\partial F(x_i)}\right]}_{F=F_{m-1}},F_m=F_{m-1}+\nu h_m$

• With squared loss the pseudo-residuals are just ordinary residuals $y_i-F_{m-1}(x_i)$.
• The learning rate $\nu$ (shrinkage) trades rounds for generalization. Libraries like XGBoost and LightGBM add second-order info and regularization.

Boosting can overfit

Because boosting keeps reducing training error, too many rounds (or noisy labels it obsesses over) can overfit. Control with a small learning rate, shallow trees, subsampling, and early stopping on a validation set. Bagging, by contrast, rarely overfits as $M$ grows.

Stacking

Stacking trains a meta-model to combine the predictions of diverse base models, rather than using a fixed rule like averaging.

• Generate base predictions using out-of-fold (cross-validated) predictions to avoid leakage, then feed those as features to the meta-learner.
• The meta-learner (often a simple linear or logistic model) learns which base models to trust in which regimes.

Relation to Random Forests

Random forests are bagging plus an extra decorrelation trick: at each split only a random subset of features is considered.

• Restricting the features lowers the inter-tree correlation $\rho$, which (per the variance formula above) tightens the variance beyond plain bagging.
• Trees are grown deep and left unpruned so each is low bias and high variance, exactly the regime where averaging pays off. Gradient-boosted trees instead grow shallow trees sequentially to reduce bias.