Ensemble Learning ✦

ML / Placement Interview Notes — the "combine weak learners" chapter

Big idea: a single model has error = bias² + variance + noise. Ensembles combine multiple models so that their errors don't add up the same way — bagging kills variance, boosting kills bias. That one line answers 50% of ensemble interview questions.

1. Bagging (Bootstrap Aggregating)

Concept

Train many models in parallel, each on a different bootstrap sample (random sample with replacement, same size as original data).
Combine predictions by averaging (regression) or majority vote (classification).
Each tree sees ~63.2% unique rows (rest are duplicates) → each model is slightly different → low correlation between models.

Why variance drops (the math intuition): if you average N models each with variance σ² and pairwise correlation ρ, the variance of the average is:
Var = ρσ² + (1-ρ)σ²/N
As N→∞, the second term vanishes, but the ρσ² term stays. That's why bagging alone isn't enough — you also need to decorrelate the trees. That's exactly what Random Forest adds.

Random Forest = Bagging + Feature Randomness

Builds many decision trees on bootstrap samples AND at each split, only considers a random subset of features (typically √p for classification, p/3 for regression).
This extra randomness decorrelates the trees (reduces ρ above) — two trees are less likely to always split on the same dominant feature.
Result: variance reduces much more than plain bagging, bias stays roughly the same as a single deep tree (which is low-bias/high-variance to start with).

Feature Importance in RF (2 common methods)

Mean Decrease in Impurity (MDI): sum up the reduction in Gini/entropy each feature causes, averaged over all trees. Fast but biased toward high-cardinality / continuous features.
Permutation Importance: shuffle one feature's column in OOB data, measure how much accuracy drops. Slower but more reliable, not biased by cardinality.

"Why does RF reduce variance?" → Say: bootstrap sampling + random feature subsets at each split → decorrelates trees → averaging decorrelated high-variance, low-bias trees cancels out noise. Don't just say "because it averages many trees" — interviewers want the decorrelation part.

OOB (Out-of-Bag) error: since each tree only trains on ~63% of rows, the remaining ~37% ("out of bag") can be used as a free validation set per tree — no need for separate cross-validation. Great follow-up fact to mention.

2. Boosting

Concept — sequential error correction

Train weak model 1

→

Find its errors

→

Train model 2 focused on those errors

→

Repeat & combine (weighted sum)

Unlike bagging (parallel, independent), boosting is sequential — each new learner is trained to fix what previous learners got wrong. This directly attacks bias (underfitting), at some cost of variance/overfitting if you boost too long.

AdaBoost (Adaptive Boosting)

Start with equal weights on all training samples.
Train a weak learner (usually a decision stump — depth-1 tree).
Increase weights of misclassified points, decrease weights of correctly classified ones → next stump focuses more on the hard points.
Final prediction = weighted vote of all stumps, where each stump's vote weight (α) depends on its accuracy — better stumps get more say.

Formula flavor (good to mention, don't need to derive): α_t = 0.5 · ln((1-err_t)/err_t) — lower error → higher α → more voting power.

Gradient Boosting — the general idea

Instead of reweighting samples, gradient boosting fits each new tree to the residual errors (technically, the negative gradient of the loss function w.r.t. predictions) of the current ensemble.
For squared error loss, negative gradient = simple residual (y - ŷ), so intuitively: "tree 2 predicts the mistakes of tree 1, tree 3 predicts the mistakes of (tree1+tree2), and so on."
Final prediction = ŷ = F₀ + η·tree₁ + η·tree₂ + ... where η (learning rate) shrinks each tree's contribution so no single tree overcorrects.
This generalizes AdaBoost to any differentiable loss function (log-loss, Huber, etc.) — that's literally why it's called "Gradient" Boosting: it's gradient descent, but in function space (each tree = one gradient step).

Bagging vs Boosting one-liner: Bagging = parallel, reduces variance, uses full-depth trees. Boosting = sequential, reduces bias, uses shallow/weak trees (stumps).

3. XGBoost vs LightGBM vs CatBoost

All three are gradient boosting implementations — the core idea (fit trees to gradients) is same. Interviewers want to know the engineering differences:

Aspect	XGBoost	LightGBM	CatBoost
Tree growth	Level-wise (splits all nodes at a depth before going deeper)	Leaf-wise (splits the leaf with max loss reduction) → deeper, more accurate trees, faster convergence, but can overfit on small data	Symmetric / oblivious trees (same split condition across a whole level) → faster inference, natural regularization
Split finding	Exact greedy + approximate histogram (in newer versions)	Histogram-based from the start — buckets continuous features into discrete bins, so it evaluates splits on ~256 bins instead of every unique value → much faster	Also histogram-based; adds ordered boosting to reduce target leakage/overfitting
Categorical features	Needs manual encoding (one-hot / label / target encoding)	Can take categorical columns directly (integer-encoded + special handling), still often benefits from encoding	Best-in-class native handling — uses ordered target statistics (a leak-safe form of target encoding) so you can feed raw categorical columns directly
Regularization	L1 (alpha) & L2 (lambda) on leaf weights + gamma (min loss reduction to split) — very tunable, "the regularized GBM"	Similar params (lambda_l1/l2) + leaf-wise growth needs `num_leaves`/`max_depth` capped to avoid overfitting	Ordered boosting itself acts as regularization against prediction shift/leakage
Speed on large data	Good, but slower than LightGBM on very large/high-dim data	Fastest — histogram binning + GOSS (Gradient-based One-Side Sampling: keeps high-gradient samples, samples low-gradient ones) + EFB (Exclusive Feature Bundling: merges sparse mutually-exclusive features)	Slower to train than LightGBM, but often needs less tuning and handles categoricals/small data well
Best for	General purpose, tabular Kaggle default, strong docs/support	Huge datasets, many features, speed-critical pipelines	Data with lots of categorical columns, want good defaults with less tuning

One-liner to say out loud: "XGBoost = regularized GBM done right, LightGBM = XGBoost optimized for speed via histogram+leaf-wise+GOSS/EFB, CatBoost = optimized for categorical features + prevents leakage via ordered boosting."

Code — quick fit (both look almost identical)

# XGBoost
import xgboost as xgb

model = xgb.XGBClassifier(
    n_estimators=300,     # number of boosting rounds (trees). Too high = overfit, use with early_stopping
    learning_rate=0.05,   # shrinkage 'eta' — how much each tree corrects; lower = needs more trees but generalizes better
    max_depth=4,          # depth per tree — controls model complexity (bias-variance knob)
    subsample=0.8,        # row sampling per tree — adds randomness, reduces overfitting
    colsample_bytree=0.8, # feature sampling per tree — like RF's random subspace trick
    reg_lambda=1.0,       # L2 regularization on leaf weights
    eval_metric="logloss"
)
model.fit(X_train, y_train, eval_set=[(X_val, y_val)], verbose=False)


# LightGBM
import lightgbm as lgb

model = lgb.LGBMClassifier(
    n_estimators=300,
    learning_rate=0.05,
    max_depth=-1,          # -1 = no limit; LightGBM controls complexity via num_leaves instead
    num_leaves=31,        # key LightGBM param (leaf-wise growth) — roughly 2^max_depth, tune together with max_depth
    subsample=0.8,
    colsample_bytree=0.8
)
model.fit(X_train, y_train, eval_set=[(X_val, y_val)])

4. Stacking

Train several different types of base models (e.g., logistic regression + RF + SVM) on the same data — called level-0 / base learners.
Take their (out-of-fold, to avoid leakage) predictions as new features, and train a meta-model (level-1, often simple like logistic regression) on top of these predictions.
The meta-model learns how much to trust each base model — e.g., "trust the RF more when feature X is high."
Key difference from bagging/boosting: base learners can be heterogeneous (different algorithms), and combination is learned, not just averaged or weighted by accuracy.
Must use out-of-fold predictions (like k-fold CV) to generate training data for the meta-model — otherwise it overfits (meta-model would just learn to trust whichever base model memorized the data best).

Quick contrast: Bagging → parallel, same algorithm, averaging. Boosting → sequential, same algorithm, weighted additive. Stacking → parallel, different algorithms, combination is learned by a meta-model.

Random Forest vs XGBoost — when to pick which

Criterion	Random Forest	XGBoost
Mechanism	Parallel bagging of deep trees	Sequential boosting of shallow trees
Handles	High variance / overfitting-prone base learners → averages it out	High bias base learners → sequentially corrects errors
Tuning effort	Low — fairly robust with default params (n_estimators, max_features)	High — many interacting hyperparams (lr, depth, subsample, regularization) need careful tuning/early stopping
Training speed	Fast, easily parallelizable (trees are independent)	Slower per tree (sequential dependency), though histogram tricks help
Overfitting risk	Lower, hard to overfit badly even with many trees	Higher if learning rate/depth/n_estimators not controlled
Accuracy ceiling (tabular data)	Good, often slightly below boosting on structured/tabular competitions	Usually higher, near state-of-the-art on tabular data when tuned well
Robustness to noisy data/outliers	More robust (averaging smooths noise)	More sensitive (sequential fitting can chase noisy residuals) — needs regularization
Interpretability	Simple feature importance, easy to explain to non-ML stakeholders	SHAP values commonly used, slightly more complex story
Pick it when...	Need a fast, low-maintenance, hard-to-mess-up baseline; limited time to tune; noisy/small data; parallel compute available	Need best possible accuracy, have time/compute to tune, data is clean-ish, tabular competition or production model where marginal gains matter

Classic follow-up: "Which would you use as a quick baseline vs a final production model?" → RF as baseline (fast, robust, minimal tuning) → XGBoost/LightGBM for the tuned final model once you have time to optimize hyperparameters.

— end of notes, good luck! ✦ —