Ensemble Methods

Ensembles combine multiple weak learners into a strong one. This is the dominant approach in tabular ML competitions.

Table of contents

1. Why ensembles work (theory)
2. Bagging
3. Random forest
4. AdaBoost (derivation)
5. Gradient boosting machines (GBM)
6. XGBoost, LightGBM, CatBoost (modern GBDT)
7. Stacking and blending
8. Practical comparison and when to use what

1. Why ensembles work (theory)

1.1 Bias-variance view

Averaging reduces variance without increasing bias:

Let $\hat{f}_1, \ldots, \hat{f}_M$ be models trained on different samples, each with expected prediction $\bar{f}$ and variance $\sigma^2$. If the models are uncorrelated, the variance of their average:

Variance decreases by factor $M$. Bias stays the same ($\mathbb{E}[\bar{f}]$ = $\mathbb{E}[\hat{f}_m]$ for unbiased models).

In reality, models are correlated (same training distribution). If pairwise correlation is $\rho$:

Floor is $\rho\sigma^2$. To benefit from ensembling: maximize diversity (low $\rho$).

1.2 Wisdom of crowds

If each of $M$ classifiers is right with probability $p > 0.5$ and errors are independent, majority vote is right with probability:

2. Bagging (Bootstrap Aggregating)

2.1 Algorithm (Breiman, 1996)

1. For $m = 1, \ldots, M$:

a. Draw a bootstrap sample $\mathcal{D}_m$ of size $n$ by sampling with replacement from $\mathcal{D}$. b. Train a model $\hat{f}_m$ on $\mathcal{D}_m$.

1. Aggregate:

• Regression: $\hat{f}(\mathbf{x}) = \frac{1}{M}\sum_m \hat{f}_m(\mathbf{x})$.
• Classification: majority vote or average probabilities.

2.2 Out-of-bag (OOB) error

Each bootstrap sample includes ~63.2% of training points ($\lim_{n\to\infty}1-(1-1/n)^n = 1-e^{-1} \approx 0.632$). The remaining ~36.8% are out-of-bag (OOB).

Evaluate model $\hat{f}_m$ on its OOB samples → free estimate of generalization without a separate validation set.

2.3 Pasting

Bagging without replacement (draw subsamples of size < n). Less variance reduction but more diversity per model.

3. Random Forest

3.1 Additional randomization over Bagging

Random forests (Breiman, 2001) = bagging of decision trees + random feature subsets at each split:

• At each node, choose the best split among a random subset of $m$ features (not all $p$).
• Default: $m = \sqrt{p}$ for classification, $m = p/3$ for regression.

This reduces correlation among trees (key insight): trees trained on different features diverge more.

3.2 Why random features reduce correlation

Two trees grown on the same bootstrap without feature randomization will tend to split on the same strong features at the top → highly correlated → limited variance reduction.

With feature randomization: each tree sees different feature subsets → different splits → lower correlation → better ensemble.

3.3 Feature importance

Split-based importance (MDI — Mean Decrease in Impurity): sum of impurity reduction from splits on feature $j$ across all trees, weighted by sample count.

Permutation importance: permute values of feature $j$ in OOB samples; measure drop in accuracy. More reliable (MDI is biased toward high-cardinality features).

from sklearn.ensemble import RandomForestClassifier
from sklearn.inspection import permutation_importance

rf = RandomForestClassifier(n_estimators=200, max_features='sqrt', oob_score=True)
rf.fit(X_train, y_train)

print("OOB score:", rf.oob_score_)
print("MDI importances:", rf.feature_importances_)

perm = permutation_importance(rf, X_val, y_val, n_repeats=10)
print("Permutation importances:", perm.importances_mean)

3.4 Hyperparameters

4. AdaBoost (derivation)

4.1 Intuition

Boosting: train models sequentially, each one focusing on the mistakes of the previous.

AdaBoost (Freund & Schapire, 1997): maintain a weight distribution over samples; harder examples get higher weight.

4.2 Algorithm (binary, $y_i \in \{-1,+1\}$)

Initialize: $w_i^{(1)} = 1/n$ for all $i$.

For $m = 1, \ldots, M$:

1. Train weak learner $h_m$ on weighted distribution $\{w_i^{(m)}\}$.
2. Compute weighted error:

1. Compute model weight (log odds of being correct):

Note: $\alpha_m > 0$ iff $\varepsilon_m < 0.5$ (better than random). Larger $\alpha$ for more accurate learners.

1. Update sample weights (increase weight of misclassified):

If correctly classified: $y_i h_m(\mathbf{x}_i) = +1$ → weight multiplied by $e^{-\alpha_m} < 1$. If misclassified: $y_i h_m(\mathbf{x}_i) = -1$ → weight multiplied by $e^{+\alpha_m} > 1$.

1. Normalize: $w_i^{(m+1)} \leftarrow w_i^{(m+1)} / \sum_j w_j^{(m+1)}$.

Final prediction:

4.3 AdaBoost minimizes exponential loss

It can be shown that AdaBoost is forward stagewise additive modeling with the exponential loss $\ell(y, f) = e^{-yf}$:

Minimizing this greedily → exactly the AdaBoost update. The exponential loss is sensitive to outliers (upweights them exponentially) — this is a weakness.

4.4 Training error bound

where $\gamma_m = 0.5 - \varepsilon_m$ is the "edge" (how much better than random). If each weak learner is slightly better than random ($\gamma_m \geq \gamma > 0$), error decays exponentially to zero.

5. Gradient Boosting Machines (GBM)

5.1 Key insight (Friedman, 2001)

Generalize boosting to arbitrary differentiable loss functions by framing it as gradient descent in function space.

Setup: train an ensemble additively:

where $h_m$ are weak learners (shallow trees) and $\nu_m$ are step sizes (learning rate).

5.2 Gradient in function space

At step $m$, we want to minimize $\sum_i L(y_i, F_{m-1}(\mathbf{x}_i) + h_m(\mathbf{x}_i))$.

Functional gradient descent: the direction that decreases loss fastest is the negative functional gradient:

These are called pseudo-residuals. Fit the next tree $h_m$ to predict these pseudo-residuals (regression tree, even for classification).

5.3 GBM algorithm

Initialize: $F_0(\mathbf{x}) = \arg\min_c \sum_i L(y_i, c)$.

For $m = 1, \ldots, M$:

1. Compute pseudo-residuals: $r_i^{(m)} = -[\partial L(y_i, F)/\partial F]_{F=F_{m-1}(\mathbf{x}_i)}$.
2. Fit regression tree $h_m$ to $\{(\mathbf{x}_i, r_i^{(m)})\}$.
3. Find optimal leaf output values (line search or closed form per leaf).
4. Update: $F_m(\mathbf{x}) = F_{m-1}(\mathbf{x}) + \nu \cdot h_m(\mathbf{x})$, with shrinkage $\nu \in (0,1]$.

5.4 Loss functions and their pseudo-residuals

5.5 Regularization in GBM

• Shrinkage (learning rate $\nu$): smaller → more trees needed but better generalization. Typical: 0.01–0.1.
• Subsampling (stochastic GBM): build each tree on a random subsample of data (e.g., 50%–80%). Reduces correlation between trees, speeds up training.
• Tree constraints: max_depth (3–8 typical), min_samples_leaf.
• L1/L2 regularization on leaf weights (XGBoost feature).

6. XGBoost, LightGBM, CatBoost (modern GBDT)

6.1 XGBoost (Chen & Guestrin, 2016)

Second-order approximation of the loss: use both gradient $g_i$ (first order) and Hessian $h_i$ (second order) for more accurate leaf updates.

For tree structure $q$ with leaf outputs $\mathbf{w}$, the regularized objective at step $m$:

where $g_i = \partial L/\partial \hat y_i$, $h_i = \partial^2 L/\partial \hat y_i^2$, $T$ = number of leaves, $\gamma$ = leaf count penalty, $\lambda$ = L2 on leaf weights.

Optimal leaf output for leaf $j$: $w_j^\star = -\frac{G_j}{H_j+\lambda}$, where $G_j = \sum_{i\in\text{leaf }j}g_i$, $H_j = \sum_{i\in\text{leaf }j}h_i$.

Split gain:

Key features:

• Weighted quantile sketch for approximate split finding (scalable).
• Column block data structure (efficient access).
• Missing value handling: learn default direction for missing values.
• Regularization: alpha (L1), lambda (L2), gamma (min gain).

6.2 LightGBM

Innovations for speed on large datasets:

• Gradient-based One-Side Sampling (GOSS): keep instances with large gradients (they contribute more), randomly sample instances with small gradients (with upweighting).
• Exclusive Feature Bundling (EFB): bundle mutually exclusive sparse features (e.g., OHE columns) into one dense feature.
• Leaf-wise growth: grow the leaf that reduces loss the most (vs. level-wise in XGBoost). Faster convergence but can overfit — limit via min_child_samples, num_leaves.
• Result: 10–20× faster than XGBoost on large datasets.

6.3 CatBoost

Innovations for categorical features:

• Target statistics for categoricals with an ordered (time-based) scheme to prevent leakage within the training set.
• Oblivious trees: all nodes at the same depth use the same split. Faster prediction, regularization effect.
• Symmetric quantile binning.

6.4 Hyperparameter guide

import xgboost as xgb
model = xgb.XGBClassifier(
    n_estimators=500, learning_rate=0.05, max_depth=6,
    subsample=0.8, colsample_bytree=0.8, gamma=0,
    reg_alpha=0.1, reg_lambda=1.0,
    eval_metric='logloss', early_stopping_rounds=20,
    random_state=42
)
model.fit(X_train, y_train, eval_set=[(X_val, y_val)], verbose=100)

import lightgbm as lgb
model = lgb.LGBMClassifier(
    n_estimators=1000, learning_rate=0.02, num_leaves=63,
    feature_fraction=0.8, bagging_fraction=0.8, bagging_freq=5,
    reg_alpha=0.1, reg_lambda=0.1,
    min_child_samples=20, random_state=42
)
model.fit(X_train, y_train,
          eval_set=[(X_val, y_val)],
          callbacks=[lgb.early_stopping(50, verbose=False)])

7. Stacking and blending

7.1 Stacking (stacked generalization)

Train a meta-learner on the predictions of base models:

1. Split training data into $k$ folds.
2. For each fold, train all base models on other folds, predict on this fold.
3. Collect out-of-fold predictions as meta-features.
4. Train a meta-learner (often logistic regression or LightGBM) on these meta-features.
5. At test time: predict with all base models, feed to meta-learner.

Prevents leakage: base model's predictions on training data are always made on data it hasn't seen.

from sklearn.ensemble import StackingClassifier
from sklearn.linear_model import LogisticRegression
from sklearn.ensemble import RandomForestClassifier, GradientBoostingClassifier

estimators = [
    ('rf', RandomForestClassifier(n_estimators=100, random_state=0)),
    ('gbm', GradientBoostingClassifier(n_estimators=100, random_state=0)),
]
meta_model = LogisticRegression()
stacker = StackingClassifier(estimators=estimators, final_estimator=meta_model, cv=5)

7.2 Blending

Simpler variant: use a holdout (not CV) to generate meta-features. Less data-efficient but faster.

7.3 Why stacking works

Different model classes have different biases. A meta-learner can learn which base model is better in which region of feature space, combining their strengths.

8. Practical comparison and when to use what

Rule of thumb for tabular data:

1. Start with LightGBM or XGBoost.
2. Tune hyperparameters (especially learning_rate, num_leaves/max_depth, subsampling).
3. Use early stopping with validation set.
4. Add stacking as final step if marginal gains matter.

*File: notes/08_ensemble_methods.md — next: notes/09_unsupervised_learning.md*