ML from Scratch · Lecture 2 of 5

Bagging vs Boosting, and XGBoost from the Objective Up

Two opposite ways to combine weak learners: average independent ones, or build them in sequence to fix each other's mistakes. Gradient boosting as gradient descent, and the second-order maths inside XGBoost.

Bias, variance and two strategies

Expected test error decomposes as $\text{bias}^2+\text{variance}+\text{noise}$.

• Bagging (Lecture 1) trains strong, low-bias models in parallel on bootstrap samples and averages them, which reduces variance.
• Boosting trains weak, high-bias models (shallow trees, even stumps) in sequence, each focused on what the ensemble so far gets wrong, which reduces bias.

AdaBoost: reweighting mistakes

Start with equal sample weights. At round $m$ fit a weak classifier $h_m$, compute its weighted error $\varepsilon_m$, give it a vote $\alpha_m=\tfrac12\ln\frac{1-\varepsilon_m}{\varepsilon_m}$, and multiply the weights of misclassified points by $e^{\alpha_m}$. The final model is $\operatorname{sign}\sum_m\alpha_mh_m(x)$. AdaBoost turns out to be stagewise minimisation of the exponential loss $e^{-yF(x)}$, a hint at the general view below.

Gradient boosting: descent in function space

We want $F$ minimising $\sum_i\ell(y_i,F(x_i))$. Treat the predictions $F(x_i)$ as parameters and take a gradient step:

We can't move each $F(x_i)$ freely (we need a function that generalises), so we fit a small tree $h_m$ to the pseudo-residuals $r_{im}$. For squared loss $\ell=\tfrac12(y-F)^2$, $r=y-F$: each tree literally fits what's left over.

With few rounds the fit is a crude staircase (high bias). As rounds increase it hugs the curve. With a large learning rate and many rounds, the test error eventually rises as the model starts fitting noise. The shrinkage η trades rounds for robustness: small η plus many trees usually generalises best.

XGBoost: a regularised, second-order version

XGBoost (Chen & Guestrin, 2016) writes the objective at round $t$ with an explicit penalty on tree complexity:

where $T$ is the number of leaves and $w_j$ the leaf values. Take a second-order Taylor expansion (the same trick as Lecture 4 of the Black–Scholes series) with $g_i=\partial_{\hat y}\ell$ and $h_i=\partial^2_{\hat y}\ell$:

Each leaf is an independent quadratic in $w_j$, minimised at

So a split of a leaf into $L$ and $R$ is worth

Split only if Gain > 0, so γ acts as a minimum gain and automatically prunes. λ shrinks leaf weights, which is ridge regularisation on the tree. Because only $g$ and $h$ are needed, any twice-differentiable loss works: squared error ($g=\hat y-y$, $h=1$), logistic ($g=p-y$, $h=p(1-p)$), Poisson, ranking losses and so on.

The engineering that made it win Kaggle

• Shrinkage η and row/column subsampling (borrowed from random forests).
• Histogram / approximate split finding: bucket features into quantiles so split search is fast.
• Sparsity-aware splits: each split learns a default direction for missing values.
• Cache-aware, parallel column blocks. LightGBM and CatBoost push the same ideas further (leaf-wise growth, ordered boosting for categoricals).

import xgboost as xgb
model = xgb.XGBRegressor(n_estimators=2000, learning_rate=0.03, max_depth=6,
                         subsample=0.8, colsample_bytree=0.8, reg_lambda=1.0, gamma=0.0,
                         early_stopping_rounds=100)
model.fit(X_tr, y_tr, eval_set=[(X_va, y_va)], verbose=200)