Ensemble Learning Boosting Combining Weak Learners into Strong Predictors
# Ensemble Learning & Boosting: Combining Weak Learners into Strong Predictors
## Introduction & Motivation
A single predictive model, no matter how carefully tuned, carries an irreducible amount of error rooted in its particular inductive bias, its particular sensitivity to the noise and sampling idiosyncrasies of the training set it happened to see, and the specific approximation errors of whatever function class it belongs to. Ensemble learning starts from the observation that many such imperfect models, each wrong in somewhat different ways, can be combined into a single predictor that is systematically more accurate than any individual constituent, provided the individual models are reasonably competent and their errors are not perfectly correlated. This idea long predates deep learning and remains, to this day, one of the most reliable and widely deployed techniques in applied machine learning, particularly on tabular data, where gradient-boosted tree ensembles routinely outperform far more elaborate neural architectures.
Two broad families dominate practical ensemble learning, distinguished by how they generate diversity among their constituent models and how they combine them. Bagging (bootstrap aggregating) trains many instances of the same base learner independently and in parallel on different bootstrap resamples of the training data, then averages or votes across their predictions, primarily to reduce variance. Boosting instead trains a sequence of typically very simple base learners, each one deliberately focused on correcting the mistakes of the ensemble built so far, primarily to reduce bias while incidentally also controlling variance through the implicit regularization of its sequential, additive structure. A third family, stacking, trains a meta-learner to combine the predictions of several different, typically diverse, base learner types, exploiting complementary strengths across model families rather than diversity within a single family.
These three ideas, resampling for variance reduction, sequential error-correction for bias reduction, and learned meta-combination for exploiting model diversity, together explain why ensemble methods, and gradient-boosted trees in particular, remain a default first choice for structured, tabular prediction problems in industry, and why understanding precisely which failure mode (bias or variance) an ensemble technique addresses is essential to applying these methods effectively rather than treating them as an unconditionally beneficial black box.
## Core Concepts & Theory
Bagging exploits a simple statistical fact: averaging several unbiased but noisy estimators reduces variance without increasing bias, provided the estimators are not perfectly correlated. By training each base learner (commonly a deep, low-bias, high-variance decision tree) on an independent bootstrap resample of the training set, roughly sampling with replacement to produce a resample of the same size in which some training points are duplicated and others omitted, bagging deliberately introduces enough randomness across base learners that their individual errors partially decorrelate, so that averaging their predictions cancels out a substantial fraction of each learner's variance while leaving the shared, systematic bias of the base learner class largely intact. Random forests extend bagging with an additional source of decorrelation: at each split in each tree, only a random subset of features is considered as candidates, which further reduces the correlation between trees, particularly when a small number of features are individually very predictive and would otherwise dominate the top splits of nearly every bagged tree.
Boosting operates on an entirely different principle: rather than training independent models on resampled data and averaging them, boosting trains base learners sequentially, where each new learner is fit specifically to the residual errors, or a re-weighted version of the training data emphasizing previously mispredicted examples, left by the ensemble constructed so far. AdaBoost, the original and conceptually clearest boosting algorithm, maintains a distribution of per-example weights that is updated after each round to upweight examples the current ensemble gets wrong and downweight examples it gets right, so that each successive weak learner is trained to focus disproportionately on the hardest remaining examples; the final prediction is a weighted vote across all weak learners, with each learner's vote weight determined by its own weighted training accuracy. Gradient boosting generalizes this residual-correction idea to arbitrary differentiable loss functions by having each new weak learner fit the negative gradient of the loss with respect to the current ensemble's predictions, which, for squared-error loss, reduces to simply fitting the current residuals, and for other losses (log-loss for classification, quantile loss for quantile regression) generalizes naturally while preserving the same sequential, additive structure.
Stacking (stacked generalization) treats the outputs of several base learners, ideally chosen to be diverse in their inductive biases so that their errors are only weakly correlated, as input features to a second-stage meta-learner that learns how to optimally combine them, typically a simple model such as linear or logistic regression to avoid overfitting the (comparatively small) meta-training set. Because training the meta-learner directly on the base learners' predictions on their own training data would leak information and produce overly optimistic meta-training signal, stacking is normally implemented using out-of-fold predictions, generating each base learner's training-set predictions through k-fold cross-validation so the meta-learner only ever sees predictions the base learner produced on data it did not itself train on.
## Mathematical Formulation
For a bagging ensemble of $M$ base learners $f_1, \ldots, f_M$, each trained on an independent bootstrap resample $\mathcal{D}_m$ drawn with replacement from the training set $\mathcal{D}$, the ensemble prediction is the simple average (for regression) or majority vote (for classification),
$$ \hat{f}_{ ext{bag}}(x) = \frac{1}{M} \sum_{m=1}^{M} f_m(x) $$
Assuming each $f_m$ is an unbiased estimator of the true function with variance $\sigma^2$ and pairwise correlation $
ho$ between any two learners' errors, the variance of the averaged ensemble is
$$ ext{Var}\left[ \hat{f}_{ ext{bag}}(x) ight] = ho \sigma^2 + \frac{1 - ho}{M} \sigma^2 $$
which shows explicitly that variance reduction from averaging is bounded below by $
ho \sigma^2$ as $M o \infty$: bagging can only reduce variance to the extent that the base learners' errors are decorrelated, which is precisely the quantity that random forests' additional feature subsampling is designed to reduce further.
AdaBoost maintains example weights $w_i^{(t)}$ updated multiplicatively after each round $t$ based on whether weak learner $h_t$ correctly classifies example $i$,
$$ w_i^{(t+1)} = w_i^{(t)} \exp\left( -\alpha_t y_i h_t(x_i) ight), \qquad \alpha_t = \frac{1}{2} \ln\left( \frac{1 - \epsilon_t}{\epsilon_t} ight) $$
where $\epsilon_t$ is the weighted training error of $h_t$ under the current weight distribution and $\alpha_t$, the vote weight assigned to $h_t$ in the final ensemble, grows as $\epsilon_t$ shrinks below chance level $0.5$. The final AdaBoost prediction is $H(x) = ext{sign}\left( \sum_{t=1}^{T} \alpha_t h_t(x)
ight)$.
Gradient boosting builds an additive model $F_M(x) = \sum_{m=1}^{M} \eta \, h_m(x)$, where $\eta$ is a learning rate and each $h_m$ is fit to approximate the negative gradient of a differentiable loss $L$ with respect to the current ensemble's predictions,
$$ h_m \approx \arg\min_h \sum_{i=1}^{n} \left( -\left. \frac{\partial L(y_i, F(x_i))}{\partial F(x_i)} ight|_{F = F_{m-1}} - h(x_i) ight)^2 $$
For squared-error loss $L(y, F) = frac{1}{2}(y - F)^2$, the negative gradient is simply the residual $y_i - F_{m-1}(x_i)$, recovering the familiar description of gradient boosting as sequential residual fitting; for other losses the same framework applies with a different pseudo-residual target at each round.
## Advanced Theory & Extensions
The bias-variance decomposition of ensemble error, $ ext{Error} = ext{Bias}^2 + ext{Variance} + ext{Irreducible Noise}$, cleanly explains the complementary strengths of bagging and boosting: bagging is applied to low-bias, high-variance base learners (deep, largely unpruned trees) specifically to attack the variance term while leaving bias essentially unchanged, whereas boosting is applied to high-bias, low-variance base learners (shallow trees or stumps) specifically to attack the bias term by sequentially reducing residual error, with variance controlled indirectly through the learning rate, the number of boosting rounds, and per-tree regularization such as depth limits and leaf-count penalties.
Gradient boosting's connection to functional gradient descent, viewing the sequence of weak learners as approximate steepest-descent steps in the infinite-dimensional space of functions rather than in a fixed finite parameter space, is what allows the framework to generalize immediately to arbitrary differentiable losses (Huber loss for robust regression, log-loss for classification, ranking losses for learning-to-rank) simply by changing the pseudo-residual computed at each round, without altering the core sequential-fitting algorithm. Modern gradient boosting implementations such as XGBoost and LightGBM extend this basic framework with second-order (Newton) updates that use both the gradient and the Hessian of the loss to compute more accurate per-leaf optimal values and a more principled split-quality criterion, typically yielding faster convergence and better-regularized trees than first-order gradient boosting alone.
Margin-based generalization theory for AdaBoost, explaining boosting's empirically observed resistance to overfitting even after driving training error to zero, argues that continuing to boost past zero training error keeps increasing the margin (a measure of prediction confidence) by which training examples are correctly classified, and that a larger average margin correlates with better generalization even though it does not further reduce training error, a distinct account from the bias-variance framing that motivated boosting's original design and that helps explain why boosting frequently does not overfit as aggressively as pure model-complexity intuition might otherwise suggest.
## Computational Considerations
Bagging and random forests parallelize trivially across base learners, since each tree is trained completely independently on its own bootstrap sample, making them well suited to distributed or multi-core training with near-linear speedup in the number of available workers, and prediction similarly parallelizes across trees at inference time. Gradient boosting's sequential dependency, each new tree requires the current ensemble's predictions to compute its pseudo-residual targets, structurally prevents this same across-tree parallelism, so modern implementations instead parallelize within each individual tree's construction, particularly the search over candidate split points across features, and further accelerate this search using histogram-based binning of continuous features (grouping feature values into a fixed number of discrete bins before searching for the best split threshold) to avoid the cost of sorting or scanning every unique feature value at every split.
Memory and training-time scaling for tree-based ensembles is dominated by dataset size, feature count, and tree depth; random forests additionally require holding, or being able to regenerate, each tree's bootstrap sample and feature subset, while gradient boosting requires maintaining a running prediction vector across all training examples that is updated after every boosting round, adding a comparatively modest bookkeeping overhead relative to the tree-construction cost itself. Out-of-bag (OOB) evaluation, available specifically to bagging-family methods because each bootstrap resample by construction omits roughly a third of the training examples, gives a nearly free validation-style error estimate using only examples excluded from each individual tree's training resample, without requiring a separate held-out validation split.
## Practical Implementation Strategies
For bagging and random forests, the primary implementation choice is the depth or leaf-count of individual trees, which should generally be allowed to grow deep (low bias, high variance) since the ensemble averaging step is specifically responsible for controlling the resulting variance; artificially shallow trees in a bagging ensemble sacrifice the low-bias property that makes bagging effective in the first place. The number of trees in a random forest primarily trades off computational cost against a diminishing-returns reduction in variance, with performance typically plateauing well before the point of computational infeasibility, making it one of the least sensitive hyperparameters to tune carefully.
For gradient boosting, the learning rate and number of boosting rounds are the two most consequential and most tightly coupled hyperparameters: a smaller learning rate generally requires proportionally more rounds to reach comparable training loss but tends to generalize better by taking smaller, more conservative steps in function space, so practitioners typically fix a small learning rate (commonly in the range 0.01 to 0.1) and use early stopping on a held-out validation set to select the number of rounds automatically, rather than tuning both jointly by grid search. Individual tree depth in gradient boosting is typically kept shallow (commonly 3 to 8 levels), since, unlike bagging, boosting's bias reduction comes from the sequential accumulation of many weak learners rather than from any single tree being individually powerful, and deep individual trees in a boosted ensemble tend to overfit quickly.
Stacking's most important implementation detail is strict avoidance of information leakage between the base-learner training process and the meta-learner's training targets, which requires either out-of-fold predictions generated via k-fold cross-validation or a dedicated held-out split reserved exclusively for generating meta-training features, since training the meta-learner on base learners' in-sample predictions produces an overly optimistic and poorly generalizing meta-model that has effectively learned to trust each base learner's training-set memorization rather than its genuine held-out predictive skill.
## Benchmark Datasets & Evaluation
Tabular machine learning benchmarks, including UCI repository datasets, Kaggle competition datasets spanning domains from credit scoring to click-through-rate prediction, and more recent standardized suites such as the OpenML-CC18 benchmark collection, remain the primary evaluation ground for ensemble tree methods, and gradient-boosted tree implementations (XGBoost, LightGBM, CatBoost) have consistently ranked among the top-performing methods on such benchmarks across many independent comparative studies, frequently matching or exceeding deep learning approaches on datasets with moderate size and heterogeneous, non-image, non-sequential feature types. Evaluation typically reports standard task-appropriate metrics (accuracy, AUC-ROC, log-loss for classification; RMSE, MAE for regression) alongside training-time and inference-latency comparisons, since ensemble size directly trades off against both.
Learning curves plotting training and validation error as a function of the number of trees (for both bagging, where variance-driven improvement plateaus, and boosting, where bias-driven improvement can continue for far longer before validation error eventually turns upward due to overfitting) are a standard and informative diagnostic specific to ensemble methods, directly visualizing the distinct variance-reduction and bias-reduction dynamics that bagging and boosting exhibit as more base learners are added. Feature importance measures derived from tree ensembles, whether based on split-count frequency, average impurity reduction, or the more principled permutation-importance and SHAP-value approaches, are also widely reported alongside raw predictive accuracy, since interpretability of the fitted ensemble is frequently as practically important as its predictive performance in tabular application domains such as credit underwriting and healthcare risk scoring.
## Key Challenges & Limitations
Boosting's sequential dependency makes it inherently more sensitive to noisy or mislabeled training examples than bagging, since a mislabeled example that is repeatedly misclassified receives ever-increasing weight (in AdaBoost) or ever-increasing pseudo-residual magnitude (in gradient boosting) across rounds, potentially causing the ensemble to progressively overfit to what is, in fact, simply label noise rather than genuine signal; robust loss functions (such as Huber loss for regression) and example-weight capping are common mitigations but do not eliminate the underlying sensitivity. Bagging and random forests, by contrast, are comparatively robust to label noise and outliers, since any individual noisy example influences only the subset of bootstrap resamples that happen to include it, and its effect is substantially diluted by averaging across the full ensemble.
Both families of tree ensembles share tree-based methods' well-known weakness on extrapolation and on smoothly varying continuous relationships, since decision trees partition the feature space into axis-aligned regions with constant predictions, meaning ensemble predictions for inputs well outside the training distribution's range are structurally incapable of extrapolating a trend beyond what was observed, unlike smooth parametric models such as linear regression or neural networks with unbounded activation ranges. Random forests and gradient-boosted trees also both handle very high-cardinality categorical features and very high-dimensional sparse feature spaces (as commonly arise in text or one-hot-encoded categorical data) considerably less gracefully than either linear models with appropriate regularization or specialized embedding-based neural approaches, motivating hybrid pipelines that use learned embeddings or target encoding to preprocess such features before they reach a tree-based ensemble.
## Hyperparameter Tuning
Random forests are comparatively forgiving to tune, with the number of trees primarily a compute-versus-diminishing-returns tradeoff, the number of features considered at each split (commonly the square root of the total feature count for classification, or a third of the feature count for regression, as widely used defaults) controlling the degree of inter-tree decorrelation, and maximum tree depth or minimum leaf size providing a secondary lever against overfitting on especially small or noisy datasets, though random forests generally overfit far less severely than gradient boosting when trees are allowed to grow deep. Gradient boosting is considerably more tuning-sensitive: the learning rate, number of rounds (or equivalently, early-stopping patience), and per-tree depth interact strongly, and practitioners commonly use a coarse-to-fine search strategy, first fixing a small learning rate and using early stopping to find an appropriate round count, then tuning tree depth, minimum samples per leaf, and column/row subsampling fractions (analogous to bagging's resampling, applied within gradient boosting to further control variance) against a validation set.
Row and column subsampling within gradient boosting, training each individual tree on a random subset of training examples and features analogous to bagging's resampling strategy, is a widely used regularization technique that combines boosting's bias-reduction strength with some of bagging's variance-reduction benefit, and subsampling fractions in the range of 0.5 to 0.8 are common defaults that meaningfully reduce overfitting risk at modest additional computational cost from re-sampling at each round. Stacking's meta-learner should generally be kept simple and well-regularized (ridge or logistic regression with modest regularization strength) relative to the base learners it combines, since the meta-training set is typically far smaller in effective size than the original training set (limited by the number of cross-validation folds and the correlation this induces among out-of-fold predictions), making an overly flexible meta-learner prone to overfitting the base learners' idiosyncrasies rather than learning a genuinely useful combination rule.
## Real-World Applications & Case Studies
Gradient-boosted tree ensembles have become the dominant modeling approach across a broad swath of industry applications operating on structured, tabular data, including credit risk scoring and loan default prediction, fraud and anomaly detection in financial transactions, click-through-rate and conversion prediction in online advertising and recommendation, and demand forecasting in retail and logistics, with XGBoost and LightGBM in particular achieving widespread adoption following a string of winning solutions in Kaggle and other data science competitions across highly varied tabular problem domains. Random forests remain heavily used in domains valuing robustness and comparative ease of tuning over the absolute last percentage point of predictive accuracy, including bioinformatics applications such as gene expression classification and variant effect prediction, ecological species distribution modeling, and various government and public-sector statistical modeling applications where model stability across data revisions is valued alongside raw accuracy.
Stacking ensembles combining diverse model families, gradient-boosted trees, neural networks, linear models, and nearest-neighbor methods, have been a consistent feature of winning solutions in high-profile machine learning competitions such as the Netflix Prize, where the winning solution itself was ultimately a large stacked ensemble of over a hundred individually modest models, illustrating stacking's practical value in squeezing out the last increments of accuracy in settings where computational cost during training is not the binding constraint. AdaBoost's original formulation found early and lasting practical success in real-time face detection (the Viola-Jones detector), where a cascade of boosted, extremely simple weak learners (single-pixel-pair intensity comparisons) achieved both high accuracy and, critically, the low per-example inference cost necessary for real-time video processing on the hardware of its era.
## Integration with Other Methods
Ensemble methods and neural networks are increasingly combined rather than treated as competing paradigms, including using neural network-derived embeddings as engineered input features to a gradient-boosted tree model when the raw data is unstructured (such as image or text embeddings feeding into a tabular ensemble alongside genuinely tabular features), and, in the other direction, using tree ensembles to generate features or pseudo-labels for training or distilling neural models on data domains where neural training data is scarcer than tabular training data. Ensemble methods are themselves a natural target for further ensembling: bagging can be, and often is, applied on top of gradient-boosted models as an additional layer of variance reduction (training several independent gradient-boosting runs with different random seeds or data subsamples and averaging their predictions), combining boosting's bias reduction with bagging's variance reduction in a single pipeline.
Ensemble methods interact closely with model interpretability and explainability techniques, since SHAP (SHapley Additive exPlanations) values, one of the most widely used model-agnostic explanation frameworks, have particularly efficient exact computation algorithms specifically for tree ensembles, making gradient-boosted trees and random forests unusually well suited to rigorous, per-prediction feature attribution relative to many other high-performing model classes where exact Shapley value computation remains computationally prohibitive. Automated machine learning (AutoML) pipelines commonly treat the choice between random forest, gradient boosting, and stacked combinations thereof, along with their associated hyperparameters, as core search-space dimensions, reflecting how central ensemble methods remain to the practical toolkit that automated model-selection systems are built to search over.
## Future Research Directions
Extending gradient boosting's theoretical understanding beyond the functional-gradient-descent framing, particularly toward a more complete account of its implicit regularization properties and its relationship to both classical statistical boosting theory and modern deep learning generalization theory, remains an active area, especially as practitioners continue to observe boosted ensembles generalizing well even under configurations (very large numbers of rounds, very small learning rates) that naive model-complexity arguments would predict should overfit severely. Hybrid architectures that more tightly integrate differentiable, gradient-boosting-style sequential refinement with representation learning, rather than treating neural feature extraction and tree-based prediction as separate pipeline stages, are an active direction motivated by the persistent gap between tree ensembles' dominance on tabular data and neural networks' dominance on unstructured data, with the goal of narrowing or eliminating that gap for mixed or borderline data modalities.
Fairness-aware and robustness-aware variants of boosting, which explicitly account for boosting's known sensitivity to label noise and its potential to amplify pre-existing biases present in mislabeled or systematically skewed training examples through its residual-focusing mechanism, are an increasingly important direction as gradient-boosted models are deployed in higher-stakes decision domains such as lending and criminal justice risk assessment. Finally, developing ensemble methods and associated theory specifically tailored to the very large, high-cardinality categorical and mixed-type feature spaces increasingly common in modern industrial tabular datasets, an area where current tree-based methods still rely heavily on ad hoc encoding heuristics, remains an open and practically consequential research direction.
## Summary & Key Takeaways
Ensemble learning combines multiple imperfect predictive models into a single, typically more accurate predictor, with bagging (and its refinement, random forests) primarily reducing variance by averaging many independently trained, high-variance base learners over bootstrap resamples, and boosting (AdaBoost and gradient boosting) primarily reducing bias by sequentially training weak learners to correct the accumulated errors of the ensemble built so far, with gradient boosting generalizing this sequential residual-fitting idea to arbitrary differentiable loss functions through functional gradient descent. Stacking offers a complementary, orthogonal source of ensemble improvement by learning to combine diverse model families through a meta-learner trained on out-of-fold base-learner predictions, exploiting complementary inductive biases across model types rather than diversity within a single model family. Gradient-boosted tree implementations such as XGBoost, LightGBM, and CatBoost remain, to this day, among the most consistently strong performers on structured tabular prediction tasks across industry and competitive machine learning alike, and understanding whether a given ensemble technique is fundamentally attacking bias or variance, and tuning its hyperparameters (learning rate, tree depth, number of rounds, subsampling fractions) accordingly, remains essential to applying these methods effectively.
Keywords: ensemble learning, bagging, boosting, random forests, gradient boosting, AdaBoost, XGBoost, LightGBM, stacking, bias-variance tradeoff, weak learners, bootstrap aggregating, out-of-bag evaluation, functional gradient descent, stacked generalization
---
## Appendix: Practical Labs
### Lab 1: Bagging Reduces Prediction Variance Relative to a Single Tree-Like Learner
This lab trains many independent stump-based regressors on bootstrap resamples of noisy training data and verifies that averaging their predictions (bagging) substantially reduces prediction variance across repeated training runs, and improves test-set MSE, relative to a single stump trained without resampling.
import numpy as np
def test_bagging_reduces_variance_vs_single_tree():
rng = np.random.default_rng(0)
n_train, n_test, d = 200, 500, 5
def true_fn(X):
return np.sin(X[:, 0] * 2) + 0.5 * X[:, 1] - 0.3 * X[:, 2] ** 2
def make_dataset(n, noise=0.5):
X = rng.uniform(-2, 2, size=(n, d))
y = true_fn(X) + rng.normal(scale=noise, size=n)
return X, y
def fit_stump(X, y):
best = None
for feat in range(X.shape[1]):
thresholds = np.percentile(X[:, feat], np.arange(10, 100, 10))
for t in thresholds:
left = X[:, feat] <= t
if left.sum() < 2 or (~left).sum() < 2:
continue
left_val = y[left].mean()
right_val = y[~left].mean()
pred = np.where(left, left_val, right_val)
mse = np.mean((pred - y) ** 2)
if best is None or mse < best[0]:
best = (mse, feat, t, left_val, right_val)
return best[1:]
def predict_stump(stump, X):
feat, t, left_val, right_val = stump
return np.where(X[:, feat] <= t, left_val, right_val)
X_test, y_test = make_dataset(n_test, noise=0.0)
n_repeats = 30
single_preds = np.zeros((n_repeats, n_test))
bagged_preds = np.zeros((n_repeats, n_test))
n_bags = 25
for r in range(n_repeats):
X_train, y_train = make_dataset(n_train)
stump = fit_stump(X_train, y_train)
single_preds[r] = predict_stump(stump, X_test)
bag_preds = np.zeros((n_bags, n_test))
for b in range(n_bags):
idx = rng.integers(0, n_train, size=n_train)
Xb, yb = X_train[idx], y_train[idx]
stump_b = fit_stump(Xb, yb)
bag_preds[b] = predict_stump(stump_b, X_test)
bagged_preds[r] = bag_preds.mean(axis=0)
var_single = single_preds.var(axis=0).mean()
var_bagged = bagged_preds.var(axis=0).mean()
mse_single = np.mean((single_preds - y_test) ** 2)
mse_bagged = np.mean((bagged_preds - y_test) ** 2)
print(f"variance: single={var_single:.4f} bagged={var_bagged:.4f}")
print(f"mse: single={mse_single:.4f} bagged={mse_bagged:.4f}")
assert var_bagged < var_single * 0.6
assert mse_bagged < mse_single
print("Bagging variance reduction test passed.")
if __name__ == "__main__":
test_bagging_reduces_variance_vs_single_tree()### Lab 2: AdaBoost Combines Weak Stumps to Solve a Non-Linearly-Separable Problem
This lab implements AdaBoost from scratch over decision stumps on a circularly separable dataset that no single axis-aligned stump can classify well, and verifies that the weighted ensemble achieves substantially lower training error than the single best stump.
import numpy as np
def test_adaboost_reduces_training_error_below_best_single_stump():
rng = np.random.default_rng(3)
n, d = 300, 4
X = rng.uniform(-1.5, 1.5, size=(n, d))
radius = np.sqrt(X[:, 0] ** 2 + X[:, 1] ** 2)
y = np.where(radius < 1.0, 1, -1)
def fit_stump(X, y, weights):
best = None
for feat in range(X.shape[1]):
thresholds = np.percentile(X[:, feat], np.arange(5, 100, 5))
for t in thresholds:
for polarity in (1, -1):
pred = np.where(X[:, feat] <= t, polarity, -polarity)
err = np.sum(weights * (pred != y))
if best is None or err < best[0]:
best = (err, feat, t, polarity)
return best
def stump_predict(stump, X):
_, feat, t, polarity = stump
return np.where(X[:, feat] <= t, polarity, -polarity)
n_rounds = 60
weights = np.ones(n) / n
stumps, alphas = [], []
for rnd in range(n_rounds):
err, feat, t, polarity = fit_stump(X, y, weights)
err = min(max(err, 1e-6), 1 - 1e-6)
alpha = 0.5 * np.log((1 - err) / err)
stump = (err, feat, t, polarity)
pred = stump_predict(stump, X)
weights = weights * np.exp(-alpha * y * pred)
weights /= weights.sum()
stumps.append(stump)
alphas.append(alpha)
ensemble_score = np.zeros(n)
for stump, alpha in zip(stumps, alphas):
ensemble_score += alpha * stump_predict(stump, X)
ensemble_pred = np.sign(ensemble_score)
ensemble_err = np.mean(ensemble_pred != y)
best_single = fit_stump(X, y, np.ones(n) / n)
single_pred = stump_predict(best_single, X)
single_err = np.mean(single_pred != y)
print(f"single stump training error: {single_err:.4f}")
print(f"adaboost ensemble training error: {ensemble_err:.4f}")
assert ensemble_err < single_err * 0.5
assert ensemble_err < 0.15
print("AdaBoost error reduction test passed.")
if __name__ == "__main__":
test_adaboost_reduces_training_error_below_best_single_stump()### Lab 3: Gradient Boosting Sequentially Reduces Residual Error
This lab implements gradient boosting from scratch, fitting a sequence of stump regressors to the residuals left by the ensemble built so far, and verifies both that training MSE decreases substantially over rounds and that the final boosted ensemble outperforms a single stump fit directly to the target.
import numpy as np
def test_gradient_boosting_sequentially_reduces_residual_error():
rng = np.random.default_rng(4)
n, d = 200, 3
def true_fn(X):
return np.sin(X[:, 0] * 3) * 2 + X[:, 1] ** 2 - X[:, 2]
X = rng.uniform(-2, 2, size=(n, d))
y = true_fn(X) + rng.normal(scale=0.3, size=n)
def fit_stump_regressor(X, residual):
best = None
for feat in range(X.shape[1]):
thresholds = np.percentile(X[:, feat], np.arange(10, 100, 10))
for t in thresholds:
left = X[:, feat] <= t
if left.sum() < 2 or (~left).sum() < 2:
continue
left_val = residual[left].mean()
right_val = residual[~left].mean()
pred = np.where(left, left_val, right_val)
mse = np.mean((pred - residual) ** 2)
if best is None or mse < best[0]:
best = (mse, feat, t, left_val, right_val)
return best[1:]
def stump_predict(stump, X):
feat, t, left_val, right_val = stump
return np.where(X[:, feat] <= t, left_val, right_val)
learning_rate = 0.3
n_rounds = 50
pred = np.full(n, y.mean())
mse_history = []
for rnd in range(n_rounds):
residual = y - pred
stump = fit_stump_regressor(X, residual)
update = stump_predict(stump, X)
pred = pred + learning_rate * update
mse_history.append(np.mean((pred - y) ** 2))
single_stump = fit_stump_regressor(X, y - y.mean())
single_pred = y.mean() + stump_predict(single_stump, X)
single_mse = np.mean((single_pred - y) ** 2)
final_mse = mse_history[-1]
early_mse = mse_history[0]
print(f"single stump mse: {single_mse:.4f}")
print(f"gradient boosting mse after round 1: {early_mse:.4f}, after {n_rounds} rounds: {final_mse:.4f}")
assert final_mse < single_mse * 0.5
assert final_mse < early_mse
increases = sum(1 for i in range(1, len(mse_history)) if mse_history[i] > mse_history[i - 1] + 1e-9)
assert increases < n_rounds * 0.1
print("Gradient boosting sequential residual-fitting test passed.")
if __name__ == "__main__":
test_gradient_boosting_sequentially_reduces_residual_error()### Lab 4: Stacking a Meta-Learner Beats the Best Individual Base Learner
This lab trains three deliberately mismatched base learners (linear, quadratic-feature, and sinusoidal-feature regressions) on a target combining all three kinds of structure, combines their out-of-fold predictions with a stacked meta-learner, and verifies the stacked model beats every individual base learner on held-out test data.
import numpy as np
def test_stacking_meta_learner_beats_best_individual_base_learner():
rng = np.random.default_rng(5)
n_train, n_test, d = 300, 300, 4
def true_fn(X):
return 1.5 * X[:, 0] - 2.0 * X[:, 1] ** 2 + np.sin(X[:, 2] * 2)
X_train = rng.uniform(-2, 2, size=(n_train, d))
y_train = true_fn(X_train) + rng.normal(scale=0.4, size=n_train)
X_test = rng.uniform(-2, 2, size=(n_test, d))
y_test = true_fn(X_test) + rng.normal(scale=0.4, size=n_test)
def fit_linear(X, y):
Xb = np.column_stack([X, np.ones(len(X))])
coef, *_ = np.linalg.lstsq(Xb, y, rcond=None)
return coef
def predict_linear(coef, X):
Xb = np.column_stack([X, np.ones(len(X))])
return Xb @ coef
def fit_quad(X, y):
Xq = np.column_stack([X, X ** 2, np.ones(len(X))])
coef, *_ = np.linalg.lstsq(Xq, y, rcond=None)
return coef
def predict_quad(coef, X):
Xq = np.column_stack([X, X ** 2, np.ones(len(X))])
return Xq @ coef
def fit_sin(X, y):
Xs = np.column_stack([X, np.sin(X * 2), np.ones(len(X))])
coef, *_ = np.linalg.lstsq(Xs, y, rcond=None)
return coef
def predict_sin(coef, X):
Xs = np.column_stack([X, np.sin(X * 2), np.ones(len(X))])
return Xs @ coef
k = 5
fold_size = n_train // k
idx = rng.permutation(n_train)
oof_preds = np.zeros((n_train, 3))
for fold in range(k):
val_idx = idx[fold * fold_size:(fold + 1) * fold_size]
train_idx = np.setdiff1d(idx, val_idx)
Xtr, ytr = X_train[train_idx], y_train[train_idx]
Xval = X_train[val_idx]
oof_preds[val_idx, 0] = predict_linear(fit_linear(Xtr, ytr), Xval)
oof_preds[val_idx, 1] = predict_quad(fit_quad(Xtr, ytr), Xval)
oof_preds[val_idx, 2] = predict_sin(fit_sin(Xtr, ytr), Xval)
meta_coef, *_ = np.linalg.lstsq(
np.column_stack([oof_preds, np.ones(n_train)]), y_train, rcond=None
)
c_lin = fit_linear(X_train, y_train)
c_quad = fit_quad(X_train, y_train)
c_sin = fit_sin(X_train, y_train)
test_preds = np.column_stack([
predict_linear(c_lin, X_test),
predict_quad(c_quad, X_test),
predict_sin(c_sin, X_test),
])
stacked_pred = np.column_stack([test_preds, np.ones(n_test)]) @ meta_coef
mse_lin = np.mean((test_preds[:, 0] - y_test) ** 2)
mse_quad = np.mean((test_preds[:, 1] - y_test) ** 2)
mse_sin = np.mean((test_preds[:, 2] - y_test) ** 2)
mse_stacked = np.mean((stacked_pred - y_test) ** 2)
best_individual = min(mse_lin, mse_quad, mse_sin)
print(f"base learner test MSE: linear={mse_lin:.4f} quad={mse_quad:.4f} sin={mse_sin:.4f}")
print(f"stacked meta-learner test MSE: {mse_stacked:.4f} (best individual: {best_individual:.4f})")
assert mse_stacked < best_individual
print("Stacking meta-learner test passed.")
if __name__ == "__main__":
test_stacking_meta_learner_beats_best_individual_base_learner()