Chapter 6: Ensemble Methods

Bagging and boosting both combine many models but attack different errors. Bagging trains models independently on bootstrap samples and averages them; it reduces variance, so it suits deep, low-bias trees, and it parallelizes trivially. Boosting trains models in sequence, each one adjusted to the mistakes of the ensemble so far; it mainly reduces bias, so it suits shallow, high-bias learners such as stumps. Because each round depends on the previous one, boosting cannot parallelize across models, only within each model's training. Boosting is often more accurate when tuned, but more sensitive to noise and hyperparameters.

AdaBoost keeps a weight on every training sample, starting uniform at $1/n$. Each round it trains a weak learner on the weighted data, computes its weighted error $\epsilon_t$, the total weight of misclassified samples, and gives the learner a vote $\alpha_t$ that grows as $\epsilon_t$ falls. It then multiplies the weights of misclassified samples up and correct ones down, renormalizes them to sum to 1, and moves to the next round. After $T$ rounds, the prediction is the sign of the weighted vote. Each round therefore concentrates on the examples the current ensemble finds hardest. The algorithm is equivalent to greedily minimizing an exponential loss.

A weak learner is any model whose weighted error is reliably below one half on binary problems, better than a coin flip by some edge $\gamma$. Decision stumps, one-split trees, are the classic choice: fast, high bias, and different every round because the weights change. Boosting theory shows that if every round achieves edge $\gamma$, the training error of AdaBoost falls at least as fast as $e^{-2\gamma^2 T}$ after $T$ rounds, so weak learners can be combined into a strong one. A learner that is too strong, such as a deep tree, fits the weighted data perfectly and leaves boosting little to correct while overfitting.

Each weak learner's vote is $\alpha_t = \frac{1}{2}\ln\frac{1-\epsilon_t}{\epsilon_t}$, half the log-odds of being correct, where $\epsilon_t$ is its weighted error. A learner at 50 percent error gets $\alpha_t = 0$; as the error drops toward 0, $\alpha_t$ grows without bound; and a learner worse than chance gets a negative weight, which flips its predictions. This value is not arbitrary: it is the step size that minimizes the exponential loss for that round. The log makes votes grow quickly near zero error, so a nearly perfect learner can dominate the ensemble.

After learner $t$ votes, each sample's weight is multiplied by $e^{\alpha_t}$ if the learner got it wrong and by $e^{-\alpha_t}$ if right, then all weights are renormalized to sum to 1. The update is larger when $\alpha_t$ is large: mistakes by a confident learner matter more. After renormalization, the misclassified samples hold exactly half the total weight, so the current learner looks no better than chance on the new weights, forcing the next learner to find something different. A sample misclassified repeatedly grows exponentially, which is the root of AdaBoost's sensitivity to noise.

The final classifier is the sign of the weighted sum of votes, with each weak learner $h_t$ outputting $+1$ or $-1$ and voting with weight $\alpha_t$. The magnitude of the sum is a confidence score: a value near zero means the strong learners disagree. Dividing by the total of the $\alpha_t$ gives the margin, between -1 and +1. AdaBoost keeps increasing the margins of training points even after training error reaches zero, which helps explain why its test error often keeps falling. Calibrated probabilities need an extra step, such as a logistic transform of the score or Platt scaling.

AdaBoost minimizes an exponential loss, which grows exponentially with how badly a point is misclassified. A mislabeled example can never be fit correctly by honest learners, so its weight is multiplied up nearly every round, and soon a handful of noisy points dominate the training distribution. Later learners then contort themselves to fit them, and test accuracy falls. Mitigations: shrink each step with a learning rate below 1, cap the number of rounds with validation or early stopping, clean labels, or switch to gradient boosting with a robust loss such as the log loss or the Huber loss.

Start with a simple prediction, such as the mean target. Compute each training point's residual, what the current model still gets wrong, and fit a small regression tree to those residuals. Add the tree's output to the model, recompute residuals, and repeat. Each tree corrects part of the remaining error, and the final model is the sum of all trees. Because each tree only needs to capture some structure in the residuals, shallow trees of depth 3 to 8 suffice. Unlike bagging, the trees are not interchangeable: each depends on all the ones before it.

Formally, the model after $m$ trees is $F_m(x) = F_{m-1}(x) + \eta \cdot h_m(x)$, where $F_{m-1}$ is the previous ensemble, $h_m$ is a tree fit to the residuals $y - F_{m-1}(x)$, and $\eta$ is the learning rate, typically between 0.01 and 0.3. For squared error, the residual is exactly the negative gradient of the loss with respect to the prediction, so fitting residuals is gradient descent. Scaling each tree by $\eta$ means the model never fully trusts any one tree, which reduces overfitting to the noise each tree picks up, at the cost of needing more trees.

For a general differentiable loss $L(y, F)$, gradient boosting fits each tree to the pseudo-residuals, the negative gradient $-\partial L / \partial F$ at each training point. They say how each prediction should move to reduce loss fastest. For squared error they equal ordinary residuals; for absolute error they are the signs of the residuals, which caps any outlier's influence; for log loss in binary classification, with $F$ the log-odds and $p$ the predicted probability, they are $y - p$. After fitting the tree's structure, each leaf's value is usually re-optimized for the actual loss, often with a Newton step.

The learning rate $\eta$ scales every tree's contribution. Friedman found empirically that small values, 0.1 or below, combined with more trees, generalize better than large steps: each tree corrects only part of the error, so the noise any single tree fits is diluted, and the ensemble's path through function space is smoother. The number of trees needed grows roughly in proportion to $1/\eta$, so halving the rate roughly doubles training time. The practical recipe is to fix a small rate such as 0.05 to 0.1, then let early stopping choose the number of trees.

XGBoost, by Chen and Guestrin, made gradient boosting fast and robust enough to dominate tabular competitions. It optimizes a regularized objective: the loss plus a penalty on the number of leaves and an L2 penalty on leaf values. It uses both first and second derivatives of the loss, giving Newton-style leaf values $-G/(H + \lambda)$, where $G$ and $H$ sum the gradients and Hessians in the leaf. It also offers sparsity-aware handling of missing values, a learned default direction at each split, column and row subsampling, parallel split search, and a fast histogram method. Trees grow level by level by default.

LightGBM, from Microsoft, targets speed on large data. It grows trees leaf-wise: instead of splitting every node at a given depth, it repeatedly splits the single leaf with the largest loss reduction, which lowers loss faster for the same number of leaves but can overfit small data unless num_leaves and min_data_in_leaf are limited. GOSS keeps all samples with large gradients and only a random fraction of small-gradient ones, reweighting them to stay unbiased. Exclusive Feature Bundling merges sparse features that are rarely nonzero together. Histogram splits complete the speedup. Its paper reports training up to 20 times faster than conventional gradient boosting.

CatBoost, from Yandex, focuses on categorical features and on a subtle bias. Naive target encoding replaces a category with its mean target, which leaks each row's own label into its feature. CatBoost computes ordered target statistics: under a random permutation, each row's encoding uses only rows before it, smoothed by a prior. Ordered boosting applies the same principle to the residuals. It also builds symmetric trees, where all nodes at a depth share one split, which are fast to evaluate and resist overfitting. Its defaults are strong, so it often performs well with little tuning, especially on many high-cardinality categorical features.

Gradient boosting can drive training loss toward zero, so regularization is essential. Tree size limits, max_depth of 3 to 8 or num_leaves in LightGBM, keep each tree weak. The learning rate and the number of trees control how far the model travels. Subsampling, subsample for rows and colsample_bytree for columns, trains each tree on a random fraction, adding randomness that reduces variance, an idea Friedman called stochastic gradient boosting. Leaf-value penalties, reg_lambda for L2 and reg_alpha for L1, shrink extreme leaf values. min_child_weight and gamma require a minimum gain or Hessian mass before splitting.

Because boosting keeps reducing training loss, the number of trees is itself a regularization parameter. Early stopping sets a large maximum, monitors loss on a validation set after each round, and stops once it has not improved for a patience number of rounds, keeping the best iteration. This tunes the number of trees within a single run. In XGBoost, pass an eval_set and early_stopping_rounds; LightGBM and CatBoost offer equivalents, and scikit-learn's HistGradientBoosting uses early_stopping and n_iter_no_change. The validation set is used for selection, so report final performance on separate test data.

Voting is the simplest way to combine different models. Hard voting gives each model one vote for its predicted class and returns the majority. Soft voting averages predicted probabilities and picks the class with the highest average, so confident models count more than hesitant ones. Soft voting usually performs better, but only if the probabilities are reasonably calibrated; an overconfident model can dominate it. Weights can favor stronger models. Voting has no trainable combiner, so it cannot learn that one model is reliable only in some cases. scikit-learn provides VotingClassifier and VotingRegressor.

Stacking has two levels. At level 0, several base models are trained on the original features. At level 1, a meta-model is trained on a new dataset whose features are the base models' predictions for each training example, often probabilities, and whose target is the true label. The meta-model learns how much to trust each base model, and with a flexible meta-model, when to trust it. At prediction time, every base model predicts first and the meta-model combines them. A stack is rarely worse than its best member when built correctly, but the gain over that member is often small.

The meta-model must be trained on predictions like those it will see at test time, made by base models that never saw the example. If a base model is fit on all the training data and then predicts that same data, its predictions are overconfident, a deep forest is nearly perfect on its own training rows, and the meta-model learns to trust it blindly. The fix is out-of-fold prediction: split the data into $K$ folds, fit each base model on $K-1$ folds, and predict the held-out fold, so every training row gets an honest prediction. The base models are then refit on all the data for test time.

An ensemble improves on its members only where they disagree. For squared error, the ensemble's error equals the average member error minus the average disagreement of members from the ensemble, the ambiguity decomposition. Models that make the same mistakes add accuracy-weighted copies of the same errors. Diversity comes from different inductive biases: trees split on axis-aligned thresholds, linear models fit global trends, kernel methods measure similarity, and neural networks learn representations. Different feature sets or preprocessing add diversity too. A strong but redundant model adds less than a slightly weaker but different one.

The meta-model's inputs are few, one or a few columns per base model, highly correlated with each other, and already strong predictors of the target. A simple model fits this setting best: logistic regression for classification, ridge or non-negative least squares for regression. A linear meta-model's weights are also readable, showing how much each base model contributes. Flexible meta-models such as boosted trees can learn when each base model is reliable, but they overfit the out-of-fold predictions easily and need much more data. Start linear with regularization, and move to something flexible only if cross-validation shows a real gain.

Blending is a simpler variant of stacking that replaces cross-validation with a single holdout split. Base models are trained on one part of the training data, they predict a separate blend set, and the meta-model is trained on those holdout predictions. Each base model is trained once instead of $K$ times, and the procedure is easy to reason about and leak-free by construction. The costs are that base models see less training data and the meta-model learns from fewer rows, so its estimates are noisier. Blending suits large datasets and quick experiments; stacking with cross-validation suits smaller data.

Stacking helps most when several base models are individually strong, their errors are not highly correlated, and there is enough data to fit the meta-model reliably. It is a staple of competitions, where a fraction of a percent decides the ranking. In production its costs weigh more: every prediction runs every base model, so latency and serving cost multiply, and there are more models to monitor, retrain, and debug. The gain over the best single model is often small and sometimes negative. Weigh it against simpler options, such as tuning the best model or averaging two.

Scikit-learn's StackingClassifier and StackingRegressor implement stacking safely. You pass a list of named base estimators and a final_estimator. During fit, it generates out-of-fold predictions for each base model with internal cross-validation, controlled by cv, trains the final estimator on them, and refits every base model on the full training data for prediction. stack_method selects which output becomes a meta-feature, predict_proba by default when available. passthrough=True also feeds the original features to the final estimator. The whole stack behaves like one estimator, so it can sit inside pipelines and be scored with cross_val_score.