Test 5. Ensemble Learning

Bagging builds multiple models on different bootstrap samples of the training data and aggregates their predictions.

• Algorithm:
  1. For $b=1$ to $B$:
     • Draw a bootstrap sample from the training set (sample with replacement).
     • Train a base learner $h_b$ on this sample.
  2. Aggregate: for regression, average $\hat{y}=\frac{1}{B}\sum _b{h}_b(x)$; for classification, majority vote.
• Variance reduction: averaging uncorrelated (or weakly correlated) models lowers overall variance.
• Effective when: using high‑variance learners (e.g., deep trees); less benefit for stable learners.

Random forest is a bagging ensemble of decision trees with random feature selection at each split.

• Extension of bagging: in addition to bootstrap sampling, each split considers a random subset of features of size $m$ rather than all features.
• Feature randomness: decorrelates trees, further reducing variance.
• Key hyperparameters:
  • n_estimators (number of trees): more trees → lower variance, higher cost.
  • max_features (features per split): smaller → more decorrelation, higher bias.
  • max_depth/min_samples_leaf: control tree complexity and overfitting.
  • bootstrap: whether to use sampling with replacement.

Boosting trains learners sequentially, where each new learner focuses on the errors of the combined ensemble so far.

• Contrast to bagging: bagging trains in parallel on bootstrap samples; boosting trains sequentially on weighted data.
• AdaBoost:
  1. Initialize weights equally.
  2. For each learner $t$:
     • Train $h_t$ on weighted data.
     • Compute error ${\epsilon }_t$ and learner weight ${\alpha }_t=\frac{1}{2}\ln \frac{1-{\epsilon }_t}{{\epsilon }_t}$.
     • Update sample weights to emphasize misclassified points.
  3. Final prediction: sign$\sum _t{\alpha }_t{h}_t(x)$.
• Gradient boosting: fits each learner to the negative gradient of the loss w.r.t. current predictions.
• Bias reduction: by focusing on residuals, boosting corrects systematic errors of prior learners.

XGBoost adds system and algorithmic optimisations plus regularisation to gradient boosting:

• Innovations:
  • Second‑order Taylor approximation of loss for efficient split finding.
  • Weighted quantile sketch for approximate tree learning on weighted data.
  • Parallel tree construction and block‑structured data layout for speed.
  • Sparsity awareness to handle missing values automatically.
• Regularisation:
  • ${\ell }_1$ (alpha) and ${\ell }_2$ (lambda) penalties on leaf weights.
  • Tree complexity penalty (gamma) for minimum loss reduction to make a split.
• Key hyperparameters:
  • eta (learning rate)
  • max_depth
  • subsample, colsample_bytree (row/feature sampling)
  • alpha, lambda, gamma

Stacking and blending train a “meta‑learner” on predictions of base learners to improve performance.

• Stacking:
  1. Level‑0: train multiple base models on the full training set (or via k‑fold to get out‑of‑fold predictions).
  2. Meta‑data: collect base model predictions on validation folds as features.
  3. Level‑1: train a meta‑learner on this meta‑data.
  4. Prediction: base learners predict on new data; meta‑learner combines these.
• Blending: similar but uses a hold‑out validation set instead of full k‑fold; simpler but less data‑efficient.
• Pitfalls:
  • Overfitting meta‑learner if using same data for base and meta training.
  • Increased complexity and training time.
  • Need careful cross‑validation to generate unbiased meta‑features.