Computer Engineering is coming soon

We're still writing and reviewing the notes for every subject, and we'll open it when every subject is ready. Meanwhile you can practise aptitude, ask Aria about any subject, or see the branches that are ready.

Boosting and stacking

Boosting builds a strong predictor by adding many weak learners in a stagewise way (AdaBoost, gradient boosting); stacking combines different trained models by learning a meta-learner on their predictions.

Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.

Why it matters

Boosting and stacking are two powerful ensemble techniques engineers use when a single model underfits or when combining models gives better accuracy. Boosting is used in production for high-accuracy tabular prediction (e.g., Gradient Boosting Machines, XGBoost) and stacking is used to combine heterogeneous models (trees, neural nets, linear models) in competitions and final-system ensembles.

Key ideas

Define terms before use:

  • Ensemble: a method that combines multiple models (called learners or base learners) to produce a single prediction. Each base learner by itself may be weak; the ensemble aims to be stronger.
  • Weak learner: a classifier or regressor whose accuracy is slightly better than random (for classification) or which has limited predictive power. In boosting theory, a weak learner is any learning algorithm that can achieve error < 1/2 on weighted training data for binary classification.
  • Strong learner: a learner with arbitrarily low error given enough training (the target of boosting).
  • Boosting: an additive, stagewise method that trains base learners sequentially so each new learner focuses on examples that previous learners predicted poorly.
  • Stacking (stacked generalisation): trains several base learners in parallel and then trains a meta-learner on the base learners' predictions (often using cross-validated predictions) to produce final predictions.

Exact statement (AdaBoost): Given training set {(x_i, y_i)} with y_i ∈ {+1, −1}, AdaBoost builds a strong classifier H(x) = sign(Σ_{t=1..T} α_t h_t(x)), where each h_t is a weak classifier trained on a reweighted dataset and α_t = (1/2) ln((1 − ε_t)/ε_t) with ε_t the weighted error of h_t. AdaBoost updates sample weights w_i by multiplying by exp(−α_t y_i h_t(x_i)), then renormalising.

Assumptions behind AdaBoost: the weak learner can accept example weights and produce hypotheses with weighted error ε_t < 1/2. The training labels are ±1. Edge cases: if ε_t = 0, stop early (perfect classifier) or cap α_t to a large finite value; if ε_t ≥ 1/2, discard or modify the weak learner (e.g., flip its predictions or adjust parameters) because α_t would be non-positive and hurt performance.

Derivation sketch (AdaBoost from exponential loss):

  1. Consider additive model F(x) = Σ_{t} α_t h_t(x) and exponential loss L = Σ_i exp(−y_i F(x_i)).
  2. Greedy stagewise minimisation chooses at round t the new α_t and h_t to reduce L: minimize Σ_i w_i exp(−y_i α h(x_i)), where w_i = exp(−y_i F_{t−1}(x_i)).
  3. For fixed h, the optimal α is 1/2 ln((1 − ε)/ε); optimizing over h yields the weak learner minimizing weighted error ε.
  4. The weight update w_i ← w_i exp(−α_t y_i h_t(x_i)) follows from definition of w_i for next round.

Gradient boosting (general losses):

  • Gradient boosting treats boosting as forward stagewise additive modelling for arbitrary differentiable loss L(y, F(x)). At step m we have F_{m−1}(x). We compute the pseudo-residuals r_{im} = −[∂L(y_i, F(x_i))/∂F(x_i)]{F=F{m−1}}. Then a base learner h_m(x) is fit to the pseudo-residuals. Finally set F_m(x) = F_{m−1}(x) + ν · γ_m · h_m(x) where γ_m is computed (often by line search per leaf for regression trees) and ν (0<ν≤1) is the learning rate.

Assumptions: loss L differentiable with respect to model prediction. Base learner can fit residual signal.

Stacking: exact procedure description used in practice:

  1. Split training set into K holdout folds.
  2. For each base learner b and for each fold k: train b on the other K−1 folds and predict on fold k. Collect these out-of-fold predictions to get a full-length vector of predictions for each base learner (no data leakage).
  3. Use these vectors (one per base learner) as features and original y as labels to train a meta-learner (level-1 model).
  4. For final deployment: train each base learner on the whole training set; to predict on new x, get base-learner predictions and pass them to the meta-learner.

Diagram to draw for stacking (exam answer): draw two horizontal layers: top layer labelled "base learners" with boxes B1, B2, B3. Arrows from training data pointing to each Bi. Show out-of-fold predictions from each Bi forming a matrix (N × number_of_base_learners). Label that matrix "stacked features". Arrow to bottom box labelled "meta-learner" which outputs final prediction. Label the K-fold split and show holdout fold arrows.

Explain why stacking is safe: it avoids leakage by using out-of-fold predictions to train the meta-learner.

Compare behaviours:

  • Boosting is sequential and reduces bias by fitting residuals; tends to create highly accurate single-model ensembles (popular for tabular data).
  • Stacking is parallel and reduces generalisation error by combining diverse model types; needs careful cross-validation to avoid overfitting.

Formulas

H(x) = sign(Σ_{t=1..T} α_t h_t(x)) — H(x): final ensemble prediction (±1). Unitless. Applies to AdaBoost classification.

ε_t = Σ_{i: h_t(x_i) ≠ y_i} w_i — ε_t: weighted error of weak learner at round t. Unitless. Applies in AdaBoost.

α_t = 1/2 · ln((1 − ε_t)/ε_t) — α_t: weight of weak learner t. Unitless. Assumes 0 < ε_t < 1.

w_i ← w_i · exp(−α_t y_i h_t(x_i)) then renormalise so Σ_i w_i = 1 — weight update rule in AdaBoost. Unitless.

L = Σ_i exp(−y_i F(x_i)) — exponential loss used to derive AdaBoost. Unitless.

F_m(x) = F_{m−1}(x) + ν · γ_m · h_m(x) — general additive update in gradient boosting. ν (learning rate) unitless; γ_m determined by line search or closed form.

r_{im} = −[∂L(y_i, F(x_i))/∂F(x_i)]_{F=F_{m−1}} — pseudo-residuals used in gradient boosting. Unitless.

For squared error loss L = 1/2 Σ_i (y_i − F(x_i))^2: r_{im} = y_i − F_{m−1}(x_i) — residuals. Units of target y.

F_0(x) = argmin_γ Σ_i L(y_i, γ) — initial constant model (e.g., mean for squared loss, log-odds for logistic loss). Unit depends on y.

Worked examples

Example 1 — AdaBoost small numeric (binary labels ±1) Training set of 4 examples, initial weights w_i = 1/4 each. Labels y: [+1, +1, −1, −1]. Weak learner h1 predicts: [+1, −1, −1, −1]. Weighted error ε1 = weight of misclassified = w2 = 0.25. Compute α1 = 1/2 ln((1 − 0.25)/0.25) = 0.5 ln(3) = 0.549306. Update weights w_i' = w_i · exp(−α1 y_i h1(x_i)):

  • i1: exp(−0.549306·(+1·+1)) = exp(−0.549306) = 0.577350 -> w1' = 0.25·0.577350 = 0.1443375
  • i2: exp(−0.549306·(+1·−1)) = exp(0.549306) = 1.7320508 -> w2' = 0.25·1.7320508 = 0.4330127
  • i3: exp(−0.549306·(−1·−1)) = exp(−0.549306) = 0.577350 -> w3' = 0.1443375
  • i4: same as i3 -> w4' = 0.1443375 Normalize: sum = 0.8660252. Normalised weights: w1 = 0.1443375/0.8660252 = 1/6 ≈ 0.166667, w2 = 0.4330127/0.8660252 = 1/2 = 0.5, w3 = w4 = 1/6. Second weak learner h2 predicts: [−1, +1, −1, −1] (error ε2 = w1 = 1/6 ≈ 0.166667). α2 = 0.5 ln((1 − 1/6)/(1/6)) = 0.5 ln(5) = 0.804719. Final combined score S(x) = α1·h1(x) + α2·h2(x). Predictions H(x) = sign(S(x)). Compute S for each example:
  • i1: 0.549306·(+1) + 0.804719·(−1) = −0.255413 -> H = −1 (wrong; true +1)
  • i2: 0.549306·(−1) + 0.804719·(+1) = +0.255413 -> H = +1 (correct)
  • i3: 0.549306·(−1) + 0.804719·(−1) = −1.354025 -> H = −1 (correct)
  • i4: same as i3 -> correct Final ensemble misclassifies only example 1. Bold final answer: Final predictions: [−1, +1, −1, −1].

Example 2 — Gradient boosting for simple regression (squared error) Data: x = [1,2,3,4], y = [3,7,5,11] (units: target units). N = 4. Initial model F0(x) = mean(y) = (3 + 7 + 5 + 11)/4 = 6.5. Residuals r_i = y_i − F0: [−3.5, 0.5, −1.5, 4.5]. Fit a regression stump (tree with two leaves) splitting x ≤ 2 and x > 2. Leaf predictions are average residuals in each region:

  • Region1 (x=1,2): mean residual = (−3.5 + 0.5)/2 = −1.5.
  • Region2 (x=3,4): mean residual = (−1.5 + 4.5)/2 = 1.5. Let h1(x) be these residual predictions. Choose learning rate ν = 0.5. Update F1(x) = F0(x) + ν · h1(x):
  • x=1: 6.5 + 0.5·(−1.5) = 6.5 − 0.75 = 5.75
  • x=2: 6.5 + 0.5·(−1.5) = 5.75
  • x=3: 6.5 + 0.5·1.5 = 7.25
  • x=4: 7.25 Compute squared errors after one step: (3 − 5.75)^2 = 7.5625, (7 − 5.75)^2 = 1.5625, (5 − 7.25)^2 = 5.0625, (11 − 7.25)^2 = 14.0625. Sum = 28.25. Using the earlier definition L = 1/2 Σ_i (y_i − F(x_i))^2, the loss after one step is L1 = 0.528.25 = 14.125, compared to the initial loss L0 = 0.535 = 17.5; hence the loss decreased. This shows how one boosting step moves predictions toward true y.

Example 3 — Short stacking model-answer (theory question) Question: Explain how to build a stacking ensemble using three base learners and give steps to avoid data leakage. Model answer: (provide the 4-step procedure listed earlier, emphasise use of K-fold out-of-fold predictions to train the meta-learner, train base learners on full training set before final predictions, and avoid using predictions on training data produced by models trained on the same data to prevent leakage).

Common mistakes

  • Interpreting α_t as probability rather than a weight in the final linear combination.
  • Using too-large learning rate ν in gradient boosting — causes overfitting and unstable training.
  • Not pruning or limiting tree depth in gradient boosting — trees that are too deep can overfit each stage.
  • Treating stacking as just averaging: meta-learner must be trained on out-of-fold predictions, simple averaging is voting, not stacking.

For your exam

Typical question types: definitions (define weak learner, ensemble, stacking), derivations (derive AdaBoost α_t and weight update from exponential loss), algorithmic steps (write AdaBoost or gradient boosting pseudo-code), numerical problems (run first two rounds of AdaBoost on small dataset), and diagram questions (draw stacking architecture). Full-marks answers include:

  • Clear definitions with notation (±1 labels for AdaBoost),
  • Step-by-step derivations (show loss, differentiate or show minimisation),
  • Algorithm steps numbered with stopping conditions, learning rate and regularisation notes,
  • For numericals, show initial weights, compute ε, α, weight updates and final predictions with used constants shown.

Quick check

  1. In AdaBoost for binary classification what does α_t represent and how is it computed?
  2. In gradient boosting what is the pseudo-residual r_{im} for squared error loss?
  3. Why must stacking use out-of-fold predictions to train the meta-learner? Answers: 1) α_t is the weight of weak learner t: α_t = 1/2 ln((1 − ε_t)/ε_t). 2) r_{im} = y_i − F_{m−1}(x_i). 3) To avoid data leakage — training meta-learner on predictions made on data that trained base models leads to overoptimistic estimates and overfitting.

Finished this topic? Mark it so your progress, study plan and readiness keep up.

Stuck on something here?