Gradient Boosting Machines — Hinglish notes

2.3.12 · AI-ML › Tree-Based & Instance Methods

GBM exist KYU karta hai?

KYA build ho raha hai (definitions)

Scratch se HOW derive karein (Function space mein Gradient descent)

Goal. Total loss $L (F) = \sum_{i = 1}^{n} L (y_{i}, F (x_{i}))$ ko function $F$ ke upar minimise karo.

Step 1 — Gradient descent, lekin function ke outputs par. Predictions ka vector $(F (x_{1}), \dots, F (x_{n}))$ ko woh cheez maano jo hum optimise kar rahe hain. Ordinary gradient descent kehta hai: gradient ke opposite move karo.

= F_{m-1}(x_i) + \nu\, r_{im}$$ *Kyun?* Steepest descent = gradient subtract karo. Negative gradient $r_{im}$ wahi direction HAI jis direction mein hum har prediction ko move karna chahte hain. **Step 2 — Lekin hume NAYE $x$ par predict karna hai.** Gradient $r_{im}$ sirf training points par exist karta hai. Toh hum pseudo-residuals ko approximate karne ke liye ek **tree** $h_m(x)$ fit karte hain: $$h_m = \arg\min_{h}\sum_{i=1}^n \big(r_{im} - h(x_i)\big)^2$$ *Least-squares kyun?* Hume sirf ek aisi function chahiye jo unseen $x$ ke liye "move karne ki direction" generalise kare; residuals par regress karna sabse simple tarika hai. **Step 3 — Step size $\gamma_m$ choose karo** ek 1-D line search se: $$\gamma_m = \arg\min_{\gamma}\sum_{i=1}^n L\big(y_i,\; F_{m-1}(x_i) + \gamma\, h_m(x_i)\big)$$ *Kyun?* Tree ek direction deta hai; $\gamma$ us direction mein *actual* loss ke liye best distance deta hai. **Step 4 — Shrinkage ke saath update karo:** $$F_m(x) = F_{m-1}(x) + \nu\,\gamma_m h_m(x)$$ *$\nu$ kyun?* Chote steps regularise karte hain: bohot saare tiny corrections, thodi badi ones se zyada generalise karte hain. > [!formula] Poora GBM algorithm > 1. Initialise karo $F_0(x)=\arg\min_c \sum_i L(y_i,c)$. > 2. $m=1..M$ ke liye: > a. $r_{im} = -\partial L / \partial F$ compute karo $F_{m-1}$ par. > b. Tree $h_m$ ko $\{(x_i, r_{im})\}$ par fit karo. > c. $\gamma_m$ line-search karo (practice mein per leaf). > d. $F_m = F_{m-1} + \nu\,\gamma_m h_m$. > 3. $F_M$ output karo. ![[2.3.12-Gradient-Boosting-Machines.png]] --- ## Loss choice familiar cheezein kyun recover karta hai > [!intuition] Squared error → literally "residuals" > $L=\tfrac12(y-F)^2$ ke saath, gradient hai $\partial L/\partial F = -(y-F)$, toh > $r_{im} = y_i - F_{m-1}(x_i)$ = **ordinary residual**. GBM phir bacha hua error ke liye trees fit karta rehta hai. Yeh "fit residuals" wali story jo aapne shayad suni hai — yeh ek *special case* hai. > [!intuition] Log-loss → classification > Binary classification ke liye $L=\log(1+e^{-y_iF})$ (jahan $y_i\in\{-1,1\}$) ke saath, pseudo-residual > hai $r_{im}=\dfrac{y_i}{1+e^{\,y_iF_{m-1}}}$: ek soft "kitna galat aur kitna confident" signal. Same machine, alag derivative. --- ## Worked Example 1 — Haath se Regression (squared error) Data: $x=[1,2,3]$, $y=[2,5,9]$. $F_0=\bar y=\tfrac{2+5+9}{3}=5.33$ use karo, $\nu=1$, depth-1 trees. **Round 1.** - Residuals $r = y - F_0 = [-3.33,\, -0.33,\, 3.67]$. *Kyun?* SE gradient = residual. - Ek stump $x\le2$ vs $x>2$ par split karta hai: 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]$. *Yeh step kyun?* Hum stump ki prediction add karte hain taaki har point $y$ ki taraf move kare. **Round 2.** - Naye residuals $y-F_1 = [-1.5,\, 1.5,\, 0.0]$. *Kyun?* Update ke baad recompute karo. - Stump $x\le1$ split karta hai: left $=-1.5$, right $=\tfrac{1.5+0}{2}=0.75$. - $F_2 = [2.0, 4.25, 9.75]$. Error har round mein shrink hoti hai. *Kyun?* Har tree remaining bias ko remove karta hai. ## Worked Example 2 — Shrinkage kyun help karta hai Maano $\gamma_m h_m$ ek training point ko perfectly zero kar deta. $\nu=1$ ke saath hum poora jump karte hain aur us **point ko overfit karne** ka risk hai. $\nu=0.1$ ke saath hum sirf 10% move karte hain — 30 trees ke baad humne use smoothly correct kar liya hai, aur jo model best generalise karta hai woh validation se choose hota hai (early stopping). *Yeh step kyun?* Chota $\nu$ + zyada trees $\approx$ ensemble ka implicit L2 regularisation. ## Worked Example 3 — Classification pseudo-residual Do 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$$ *Kyun?* Positive residual $+1$ point ke liye score upar push karta hai; negative $-1$ point ke liye neeche push karta hai — magnitude dikhata hai hum kitne unconfident/galat hain. Agla tree in values ko fit karta hai. --- > [!mistake] Common errors ko steel-man karna > **1. "GBM sirf residuals fit karta hai, isliye yeh sirf regression ke liye kaam karta hai."** > *Kyun sahi lagta hai:* squared-error GBM literally $y-F$ fit karta hai. *Fix:* residual = negative gradient ek **special case** hai. Loss swap karo (log-loss, Huber, Poisson) aur wahi engine classification/ranking/counts handle karta hai. > > **2. "Zyada trees hamesha better hote hain."** > *Kyun sahi lagta hai:* $M$ ke saath training loss girta rehta hai. *Fix:* boosting **overfit kar sakta hai**; validation loss eventually badhti hai. ==Early stopping== use karo. > > **3. "Accuracy ke liye deep trees use karo."** > *Kyun sahi lagta hai:* deep trees training data well fit karte hain. *Fix:* GBM **weak** learners chahta hai (depth 1–6). Deep trees har ek overfit karte hain, aur boosting usse correct nahi kar sakta. > > **4. "Random Forest aur GBM same ensemble hain."** > *Kyun sahi lagta hai:* dono tree ensembles hain. *Fix:* RF = **parallel**, averaging se variance reduce karta hai; GBM = **sequential**, gradient steps se bias reduce karta hai. > > **5. "Learning rate matter nahi karta agar mere paas enough trees hain."** > *Kyun sahi lagta hai:* dono fit control karte hain. *Fix:* $\nu$ aur $M$ **trade off** karte hain — $\nu$ aadha karo, roughly $M$ double karo. Chota $\nu$ better generalise karta hai lekin compute cost karta hai. --- > [!recall]- Feynman: ek 12-saal-ke ko explain karo > Socho tum darts phenk rahe ho aur bullseye miss ho gayi. Tum dekhte ho *kitna aur kis direction mein* miss hua, phir us direction mein ek chota correction dart phenko. Phir naya bacha hua miss dekho aur ek aur chota correction phenko. Yeh bohot baar tiny nudges ke saath karo — 100 gentle corrections ke baad tum basically bullseye par ho. Har "correction dart" ek chota tree hai, aur "kis direction mein miss hua" woh gradient hai. Yahi Gradient Boosting hai. > [!mnemonic] Loop yaad karo > **"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. GBM mein har naya tree kaunsi quantity fit karta hai? > 2. GBM ko "gradient descent in function space" kyun kehte hain? > 3. Learning rate $\nu$ kisse trade off karta hai? > 4. Squared-error loss ke liye, pseudo-residual kya ban jaata hai? #flashcards/ai-ml What does each boosting stage fit its tree to? ::: Pseudo-residuals = negative gradient of the loss w.r.t. current predictions. Why is GBM "gradient descent in function space"? ::: Predictions ko variables ki tarah treat kiya jaata hai; har tree loss par negative-gradient step approximate karta hai. For squared-error loss, what is the pseudo-residual? ::: Ordinary residual $y_i - F_{m-1}(x_i)$. Role of the learning rate $\nu$? ::: Shrinkage/regularisation; chote steps better generalise karte hain lekin zyada trees chahiye. How do $\nu$ and number of trees $M$ relate? ::: Yeh trade off karte hain — chota $\nu$ bada $M$ maangta hai same fit ke liye. GBM vs Random Forest? ::: GBM = sequential, bias reduce karta hai; RF = parallel/averaging, variance reduce karta hai. Should GBM trees be deep or shallow, and why? ::: Shallow (weak learners); deep trees overfit karte hain aur boosting unhe correct nahi kar sakta. How is $\gamma_m$ (step size) chosen? ::: Line search se jo true loss ko tree ki direction mein minimise kare (practice mein per-leaf). How do you prevent GBM from overfitting? ::: Early stopping on validation loss, chota $\nu$, shallow trees, subsampling. Classification pseudo-residual for log-loss with $y\in\{-1,1\}$? ::: $r = \dfrac{y}{1+e^{yF}}$. --- ## Connections - [[Decision Trees]] — har boosting round ke andar weak learner - [[Random Forests]] — contrast: parallel bagging vs sequential boosting - [[Gradient Descent]] — GBM yahi hai, lekin function space mein - [[Loss Functions]] — loss swap karne se "residual" ka matlab badal jaata hai - [[XGBoost and LightGBM]] — engineered GBMs with 2nd-order (Newton) steps + regularisation - [[Bias-Variance Tradeoff]] — boosting bias attack karta hai, bagging variance attack karta hai - [[Early Stopping and Regularization]] — $M$ aur $\nu$ ko control karna ## 🖼️ 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 ```