Gradient Boosting Machines

---

WHY does Gradient Boosting exist?

---

WHAT is being built (definitions)

---

HOW to derive it from scratch (Gradient descent in function space)

Goal. Minimise total loss $\mathcal{L}(F)=\sum_{i=1}^n L(y_i, F(x_i))$ over the function $F$.

Step 1 — Gradient descent, but on the function's outputs. Treat the vector of predictions $\big(F(x_1),\dots,F(x_n)\big)$ as the thing we optimise. Ordinary gradient descent says: move opposite the gradient.

= F_{m-1}(x_i) + \nu\, r_{im}$$ *Why?* Steepest descent = subtract the gradient. The negative gradient $r_{im}$ IS the direction we want each prediction to move. **Step 2 — But we need to predict on NEW $x$.** The gradient $r_{im}$ only exists at training points. So we **fit a tree** $h_m(x)$ to approximate the pseudo-residuals: $$h_m = \arg\min_{h}\sum_{i=1}^n \big(r_{im} - h(x_i)\big)^2$$ *Why least-squares?* We just need a function that generalises the "direction to move" to unseen $x$; regressing on residuals is the simplest way. **Step 3 — Choose the step size $\gamma_m$** by a 1-D line search: $$\gamma_m = \arg\min_{\gamma}\sum_{i=1}^n L\big(y_i,\; F_{m-1}(x_i) + \gamma\, h_m(x_i)\big)$$ *Why?* The tree gives a direction; $\gamma$ gives the best distance along it for the *actual* loss. **Step 4 — Update with shrinkage:** $$F_m(x) = F_{m-1}(x) + \nu\,\gamma_m h_m(x)$$ *Why $\nu$?* Small steps regularise: many tiny corrections generalise better than a few big ones. > [!formula] The full GBM algorithm > 1. Initialise $F_0(x)=\arg\min_c \sum_i L(y_i,c)$. > 2. For $m=1..M$: > a. Compute $r_{im} = -\partial L / \partial F$ at $F_{m-1}$. > b. Fit tree $h_m$ to $\{(x_i, r_{im})\}$. > c. Line-search $\gamma_m$ (per leaf, in practice). > d. $F_m = F_{m-1} + \nu\,\gamma_m h_m$. > 3. Output $F_M$. ![[2.3.12-Gradient-Boosting-Machines.png]] --- ## Why the loss choice recovers familiar things > [!intuition] Squared error → literally "residuals" > With $L=\tfrac12(y-F)^2$, the gradient is $\partial L/\partial F = -(y-F)$, so > $r_{im} = y_i - F_{m-1}(x_i)$ = the **ordinary residual**. GBM then just keeps fitting trees to > the leftover error. This is the "fit residuals" story you may have heard — it's a *special case*. > [!intuition] Log-loss → classification > For binary classification with $L=\log(1+e^{-y_iF})$ (with $y_i\in\{-1,1\}$), the pseudo-residual > is $r_{im}=\dfrac{y_i}{1+e^{\,y_iF_{m-1}}}$: a soft "how wrong and how confident" signal. Same > machine, different derivative. --- ## Worked Example 1 — Regression by hand (squared error) Data: $x=[1,2,3]$, $y=[2,5,9]$. Use $F_0=\bar y=\tfrac{2+5+9}{3}=5.33$, $\nu=1$, depth-1 trees. **Round 1.** - Residuals $r = y - F_0 = [-3.33,\, -0.33,\, 3.67]$. *Why?* SE gradient = residual. - A stump splits at $x\le2$ vs $x>2$: left mean $=\tfrac{-3.33-0.33}{2}=-1.83$, right $=3.67$. - $F_1(x) = 5.33 + h_1(x) = [3.5, 3.5, 9.0]$. *Why this step?* We add the stump's prediction to move each point toward $y$. **Round 2.** - New residuals $y-F_1 = [-1.5,\, 1.5,\, 0.0]$. *Why?* Recompute after the update. - Stump splits $x\le1$: left $=-1.5$, right $=\tfrac{1.5+0}{2}=0.75$. - $F_2 = [2.0, 4.25, 9.75]$. Error shrinks each round. *Why?* Each tree removes the remaining bias. ## Worked Example 2 — Why shrinkage helps Suppose $\gamma_m h_m$ would perfectly zero one training point. With $\nu=1$ we jump all the way and risk **overfitting that point**. With $\nu=0.1$ we only move 10% — after 30 trees we've corrected it smoothly, and the model that generalises best is chosen via validation (early stopping). *Why this step?* Small $\nu$ + many trees $\approx$ implicit L2 regularisation of the ensemble. ## Worked Example 3 — Classification pseudo-residual Two points, true $y=[+1,-1]$, current $F_1=[0.4,\,0.2]$. $$r_1=\frac{+1}{1+e^{0.4}}=0.40,\qquad r_2=\frac{-1}{1+e^{-0.2}}=-0.45$$ *Why?* Positive residual pushes the score up for the $+1$ point; negative pushes down for the $-1$ point — magnitude reflects how unconfident/wrong we are. The next tree fits these values. --- > [!mistake] Steel-manning the common errors > **1. "GBM just fits residuals, so it only works for regression."** > *Why it feels right:* squared-error GBM literally fits $y-F$. *Fix:* residual = negative gradient > is a **special case**. Swap the loss (log-loss, Huber, Poisson) and the same engine handles > classification/ranking/counts. > > **2. "More trees is always better."** > *Why it feels right:* training loss keeps dropping with $M$. *Fix:* boosting **can overfit**; > validation loss eventually rises. Use ==early stopping==. > > **3. "Use deep trees for accuracy."** > *Why it feels right:* deep trees fit training data well. *Fix:* GBM wants **weak** learners > (depth 1–6). Deep trees each overfit, and boosting can't correct that. > > **4. "Random Forest and GBM are the same ensemble."** > *Why it feels right:* both are tree ensembles. *Fix:* RF = **parallel**, reduces variance by > averaging; GBM = **sequential**, reduces bias by gradient steps. > > **5. "Learning rate doesn't matter if I have enough trees."** > *Why it feels right:* both control fit. *Fix:* $\nu$ and $M$ **trade off** — halve $\nu$, roughly > double $M$. Smaller $\nu$ generalises better but costs compute. --- > [!recall]- Feynman: explain to a 12-year-old > Imagine you're throwing darts and you miss the bullseye. You look at *how far and which way* you > missed, then throw a small correction dart in that direction. Then you look at the new leftover > miss and throw another small correction. Do this many times with tiny nudges — after 100 gentle > corrections you're basically on the bullseye. Each "correction dart" is a small tree, and the > "which way you missed" is the gradient. That's Gradient Boosting. > [!mnemonic] Remember the loop > **"G-R-A-D"**: **G**uess (init $F_0$) → **R**esiduals (negative gradient) → **A**dd a tree fit to > them → **D**ampen with learning rate. Repeat. --- ## Active Recall > [!recall] Quick self-test > 1. What quantity does each new tree in GBM fit? > 2. Why is GBM called "gradient descent in function space"? > 3. What does the learning rate $\nu$ trade off against? > 4. For squared-error loss, what does the pseudo-residual reduce to? #flashcards/ai-ml What does each boosting stage fit its tree to? ::: The pseudo-residuals = negative gradient of the loss w.r.t. current predictions. Why is GBM "gradient descent in function space"? ::: Predictions are treated as the variables; each tree approximates the negative-gradient step on the loss. For squared-error loss, what is the pseudo-residual? ::: The ordinary residual $y_i - F_{m-1}(x_i)$. Role of the learning rate $\nu$? ::: Shrinkage/regularisation; small steps generalise better but need more trees. How do $\nu$ and number of trees $M$ relate? ::: They trade off — smaller $\nu$ requires larger $M$ for the same fit. GBM vs Random Forest? ::: GBM = sequential, reduces bias; RF = parallel/averaging, reduces variance. Should GBM trees be deep or shallow, and why? ::: Shallow (weak learners); deep trees overfit and boosting can't correct them. How is $\gamma_m$ (step size) chosen? ::: By a line search minimising the true loss along the tree's direction (per-leaf in practice). How do you prevent GBM from overfitting? ::: Early stopping on validation loss, small $\nu$, shallow trees, subsampling. Classification pseudo-residual for log-loss with $y\in\{-1,1\}$? ::: $r = \dfrac{y}{1+e^{yF}}$. --- ## Connections - [[Decision Trees]] — the weak learner inside every boosting round - [[Random Forests]] — contrast: parallel bagging vs sequential boosting - [[Gradient Descent]] — GBM is this, but in function space - [[Loss Functions]] — swapping the loss changes what "residual" means - [[XGBoost and LightGBM]] — engineered GBMs with 2nd-order (Newton) steps + regularisation - [[Bias-Variance Tradeoff]] — boosting attacks bias, bagging attacks variance - [[Early Stopping and Regularization]] — controlling $M$ and $\nu$ ## 🖼️ Concept Map ```mermaid flowchart TD A[Single Tree Problem] -->|underfits or overfits| B[Need Controlled Error] B -->|reduce bias| C[Gradient Boosting] C -->|is| D[Gradient Descent in Function Space] C -->|builds| E[Additive Model FM] E -->|sum of| F[Weak Learners hm] F -->|shallow trees depth 1-6| F D -->|negative gradient of loss| G[Pseudo-Residual rim] G -->|fit tree via least-squares| F F -->|line search| H[Step Size gamma m] H -->|scaled by| I[Learning Rate nu] I -->|shrinkage regularises| E G -->|direction to move| H ``` ## 🔊 Hinglish (regional understanding) > [!intuition]- Hinglish mein samjho > Gradient Boosting ka core idea simple hai: ek hi bada model banane ke bajaye, hum bahut saare > chhote-chhote weak trees banate hain — ek ke baad ek. Har naya tree pichhle sab trees ki galti > (error) ko theek karta hai. Aur "galti" ko naapte kaise hain? Loss function ka **negative gradient** > nikaal ke. Isiliye bolte hain: GBM asal mein **gradient descent hai, par function space mein** — > matlab hum predictions ko hi optimize kar rahe hain, ek chhota step at a time. > > Squared-error loss ke case mein yeh negative gradient bilkul simple ban jaata hai — wo hota hai > seedha residual $y - F$. To har round mein hum leftover error par ek chhota tree fit karte hain aur > use current prediction mein add kar dete hain. Learning rate $\nu$ (shrinkage) har step ko chhota > rakhta hai — badi jump se overfit ho jaata hai, chhoti-chhoti nudges se model achha generalize karta > hai. Isiliye $\nu$ chhota rakho to trees zyada lagengi, dono ka trade-off hota hai. > > Yeh important kyun hai? Kyunki Kaggle aur real-world tabular data (banking, fraud, ranking) par GBM > family — XGBoost, LightGBM, CatBoost — aaj bhi top performers hain. Bas do galti mat karna: (1) bahut > deep trees mat lo, weak learners chahiye (depth 1–6); (2) infinite trees mat lagao, **early stopping** > karo warna overfit ho jaayega. Random Forest se yaad rakho — RF parallel averaging karke variance > kam karta hai, jabki GBM sequential correction karke bias kam karta hai. ![[audio/2.3.12-Gradient-Boosting-Machines.mp3]]