Ensembles and Boosting

Every ensemble method attacks one term of Test error = Bias^2 + Variance + sigma^2: bagging and forests cut variance, boosting cuts bias, and sigma^2 (label noise) is the unreachable floor.

The decomposition

• Assumes squared-error loss, mean-zero additive noise, and i.i.d. rows; time-series and grouped data break it (variance estimates go optimistic).
• Bias^2 (f - Ef)^2: error left with infinite data, model class too rigid.
• Variance E[(Ef - f_hat)^2]: how much the fit moves when the training sample is redrawn.
• sigma^2: irreducible label noise; no model removes it.
• A single unpruned tree is low bias, high variance; a forest inherits the bias and loses the variance.

Bagging (variance fix)

• Bootstrap aggregating: draw B samples of size n with replacement, fit one model each, average.
• Variance of the average = rho·sigma_t^2 + (1-rho)/B · sigma_t^2. First term is a floor with no B in it; second vanishes as B grows.
• B is a convergence knob, not a tuning knob: set it high, then forget it.
• Base learner must be unstable (high variance) or there is nothing to average away. Never prune trees inside a bag (pruning trades away free variance for permanent bias).
• Out-of-bag: each row is missing from ~e^-1 = 36.8% of trees; score it with those for a free validation estimate.
• Average regression values or probabilities; vote for classes (cannot average categories).

Random forests (decorrelation)

• Only lever on bagging’s rho·sigma_t^2 floor is rho: at each split offer only m of p features, forcing trees down different paths.
• Best m is in the middle (U-shape): too low starves trees of the good feature and bias jumps. Defaults sqrt(p) (classification), p/3 (regression).
• max_features is the real knob; n_estimators is convergence-only.
• Assumes signal is spread across several features; fails when 2 of 200 carry it all (raise max_features).
• Extra Trees: also randomize split thresholds, no bootstrap; lower rho, higher per-tree bias.
• Feature importance: impurity/feature_importances_ is biased toward high-cardinality columns (a random ID looks important). Use permutation importance on held-out data.

Boosting (bias fix)

• Forward stagewise: F_m = F_{m-1} + eta·h_m, earlier stages frozen. Sequential, not parallelizable across m.
• Sum of weak learners is more expressive than one (sum of stumps = any additive function), which is what cuts bias.
• Overfits as M grows (chases noise once signal is gone), so early stopping is mandatory.
• Base learner must be weak but > chance (stump, depth ≤ 4); labels must be mostly correct; needs an honest (time/group-aware) validation split.

AdaBoost

• err_m = weighted error; vote alpha_m = 0.5·ln((1-err)/err); reweight w_i *= exp(-alpha_m·y_i·h_m(x_i)), labels in {-1,+1}.
• After each round the misclassified rows hold exactly half the weight, for any err (sqrt(err(1-err)) on each side). Next learner is forced to a coin flip on the new distribution.
• Exponential loss makes it brittle to label noise: one mislabeled row’s weight grows unbounded.

Gradient boosting

• Gradient descent in function space: fit each tree to -g (negative gradient) by least squares, then re-solve leaf values on the true loss.
• Swapping the loss changes only the gradient line:

• Gotcha: log-loss gradient uses {0,1} labels here (g = p - y), not AdaBoost’s {-1,+1}; mixing them makes every negative row’s gradient wrong by 1.0, silently.

GBDT libraries

• XGBoost: leaf w_j* = -G_j/(H_j+lambda) (Newton step), split Gain = 0.5·[G_L^2/(H_L+lambda) + G_R^2/(H_R+lambda) - (G_L+G_R)^2/(H_L+H_R+lambda)] - gamma. gamma = admission fee per split in loss units. min_child_weight floors H_j (curvature mass), not row count.
• LightGBM leaf-wise trap: num_leaves must sit well below 2^max_depth (e.g. 31 with depth 7), else it degenerates to the balanced, most-overfit tree.
• CatBoost leak: naive target encoding puts row i’s own label in its encoding; singleton categories get separated perfectly on train. Signature: train AUC pins to 1.0 by iteration ~10, valid at 0.5, one feature holds >0.8 importance. Fix with ordered/OOF target statistics.

Stacking

• Combines different model kinds via a meta learner fit on out-of-fold base predictions (n rows x M models).
• OOF is non-negotiable: in-sample meta features hand full weight to the most overfit base model. Blending uses one holdout instead of K folds (loses data).
• Keep the meta learner simple (ridge or non-negative LS): OOF columns correlate 0.90+, so plain OLS fits noise.

Tuning order

1. Fix eta at 0.05-0.1, take M from early stopping (eta·M roughly constant, so never grid-search n_estimators).
2. Tree capacity: max_depth/num_leaves, min_child_weight, min_data_in_leaf.
3. Sampling: subsample, colsample_bytree (free variance cut, same rho idea as forests).
4. Explicit reg: lambda, alpha, gamma (a big gain here means step 2 was wrong).
5. Lower eta and refit once, at the end.

• Early stopping: use three splits (train fits, valid stops, test reports). The stopped-on validation score is optimistically biased. Patience 50-100 rounds, scaled inversely with eta.

GBDT vs neural nets on tabular data

• Axis-aligned splits match threshold/bracket targets; MLPs are biased toward smooth functions.
• MLPs are rotation-invariant, but table columns mean something individually and aren’t interchangeable.
• No preprocessing surface: splits use only value order, so any monotone transform gives the same tree; missing values get a learned direction.
• Sample efficient at small n. NNs win with text/image/audio, very high-cardinality IDs (embeddings), tens of millions of rows, or multi-task/online learning.