XGBoost fundamentals and tuning — AI-ML notes

WHY does XGBoost exist?

Compared to Random Forest (which averages independent trees built in parallel), boosting builds trees sequentially and dependently — each depends on what came before.

WHAT is the model? (Additive form)

We add trees greedily: at round $t$ the prediction is $\hat{y}_i^{(t)} = \hat{y}_i^{(t-1)} + f_t(x_i).$ We must choose $f_t$ (the new tree) to reduce the objective the most.

The Objective — WHY regularization is baked in

WHY: ordinary gradient boosting only minimizes loss; XGBoost adds $\Omega$ inside the optimization so trees are pruned and leaf weights shrunk automatically, not as an afterthought.

HOW: Deriving the leaf weights from first principles

Plug the additive step into the objective at round $t$ (dropping constants from earlier trees): $\mathcal{L}^{(t)} = \sum_{i=1}^{n} l\!\left(y_i,\; \hat{y}_i^{(t-1)} + f_t(x_i)\right) + \Omega(f_t).$

Step 1 — Taylor-expand the loss to 2nd order around $\hat{y}^{(t-1)}$ . Why this step? We can't optimize an arbitrary loss over tree structures directly, so we approximate it by a quadratic — which we can solve in closed form.

Define per-example gradient and Hessian: $g_i = \partial_{\hat y}\, l(y_i,\hat y)\Big|_{\hat y^{(t-1)}}, \qquad h_i = \partial^2_{\hat y}\, l(y_i,\hat y)\Big|_{\hat y^{(t-1)}}.$ Then $\mathcal{L}^{(t)} \approx \sum_i \Big[ g_i f_t(x_i) + \tfrac12 h_i f_t(x_i)^2 \Big] + \gamma T + \tfrac{\lambda}{2}\sum_j w_j^2 + \text{const}.$

Step 2 — Group examples by leaf. A tree sends each $x_i$ to exactly one leaf $j$ . Let $I_j = \{ i : x_i \text{ lands in leaf } j\}$ and let that leaf output the constant $w_j$ . Since $f_t(x_i)=w_{q(i)}$ : $\mathcal{L}^{(t)} = \sum_{j=1}^{T} \Big[ \big(\textstyle\sum_{i\in I_j} g_i\big) w_j + \tfrac12\big(\textstyle\sum_{i\in I_j} h_i + \lambda\big) w_j^2 \Big] + \gamma T.$ Let $G_j = \sum_{i\in I_j} g_i$ and $H_j = \sum_{i\in I_j} h_i$ .

Why this step? Now the objective is a sum of independent quadratics in each $w_j$ — trivial to minimize.

Step 3 — Minimize over $w_j$ . Set derivative to zero: $\frac{\partial}{\partial w_j}\big(G_j w_j + \tfrac12(H_j+\lambda)w_j^2\big) = G_j + (H_j+\lambda)w_j = 0.$

Step 4 — Substitute back to get the best achievable objective for a fixed tree structure:

HOW a split is chosen — the Gain formula

We can't try every tree. Instead we grow greedily: at a node, try splitting its data into Left ( $L$ ) and Right ( $R$ ). The improvement is (score before) $-$ (score after):

Why the $-\gamma$ ? Splitting adds one leaf, costing $\gamma$ . If Gain $\le 0$ , don't split — this is built-in pruning.

Figure — XGBoost fundamentals and tuning

Worked Example 1 — Leaf weight (regression, squared error)

For squared error $l = \tfrac12(y-\hat y)^2$ : $g_i = \hat y_i^{(t-1)} - y_i$ (the negative residual), $h_i = 1$ .

Suppose a leaf holds 3 examples with residuals $(y-\hat y) = +2, +3, +5$ , so $g_i = -2,-3,-5$ . Take $\lambda = 1$ .

$G = -10$ , $H = 3$ .
$w^* = -G/(H+\lambda) = -(-10)/(3+1) = 2.5$ .

Why this step? The leaf outputs $2.5$ — close to the mean residual $3.33$ but shrunk by $\lambda$ toward 0. Larger $\lambda$ ⇒ more shrinkage ⇒ less overfit.

Worked Example 2 — Should we split?

Node has $G=-10, H=3$ . Proposed split: Left $(G_L=-8,H_L=2)$ , Right $(G_R=-2,H_R=1)$ . $\lambda=1,\gamma=2$ . $\text{Gain}=\tfrac12\!\left[\frac{64}{3}+\frac{4}{2}-\frac{100}{4}\right]-2 = \tfrac12[21.33+2-25]-2 = \tfrac12(-1.67)-2 = -2.83.$ Gain $<0$ ⇒ reject the split. Why: the reduction in loss doesn't beat the $\gamma$ complexity cost.

Worked Example 3 — Log-loss gradients

Binary classification, $p=\sigma(\hat y)$ , loss $=-[y\ln p+(1-y)\ln(1-p)]$ . Then $g_i = p_i - y_i$ and $h_i = p_i(1-p_i)$ . If $y=1$ and current $p=0.2$ : $g=-0.8$ (big push up), $h=0.16$ . Why: confident-wrong points get large gradients ⇒ next tree focuses on them.

Key Hyperparameters (the 80/20 that matters)

Param	Controls	Direction
`eta` / learning_rate	shrinks each tree's contribution: $\hat y^{(t)}=\hat y^{(t-1)}+\eta f_t$	↓ = more robust, need more trees
`n_estimators`	number of trees $K$	pair with `eta`; use early stopping
`max_depth`	tree complexity	↓ to fight overfit
`min_child_weight`	min $\sum h_i$ in a leaf	↑ to fight overfit
`gamma`	min gain to split ( $\gamma$ )	↑ = more pruning
`lambda`, `alpha`	L2 / L1 on leaf weights	↑ = more regularization
`subsample`	row sampling per tree	<1 adds randomness
`colsample_bytree`	feature sampling	<1 decorrelates trees

Recall Feynman: explain to a 12-year-old

Imagine drawing a picture and a friend points out your mistakes. You fix them a little. Then another friend points out what's still wrong, and you fix that a little. Each friend only makes a small correction (that's the learning rate), and you don't listen to a friend if their "fix" is too tiny to matter (that's gamma pruning). After many friends, your picture is great — but if you keep calling friends forever, they start "fixing" things that were already fine and ruin it. So you stop at the right time (early stopping). XGBoost is a team of these polite friends who each nudge the answer closer using both which way to fix (gradient) and how carefully to fix (Hessian).

Recall — test yourself

Flashcards

What is the additive model form of XGBoost?

\hat y_i=\sum_{k=1}^K f_k(x_i)

, a sum of regression trees added sequentially, each fitting residual errors.

Why does XGBoost use a 2nd-order Taylor expansion of the loss?

To turn an arbitrary differentiable loss into a quadratic in the tree output, which can be minimized in closed form per leaf (Newton-style), using gradient

g_i

and Hessian

h_i

Formula for the optimal leaf weight?

w_j^*=-G_j/(H_j+\lambda)

where

G_j=\sum_{i\in I_j}g_i

H_j=\sum_{i\in I_j}h_i

Formula for split Gain?

\tfrac12[G_L^2/(H_L+\lambda)+G_R^2/(H_R+\lambda)-(G_L+G_R)^2/(H_L+H_R+\lambda)]-\gamma

What does

\gamma

do?

Minimum loss reduction required to make a split; acts as complexity penalty per leaf, enabling automatic pruning (reject split if Gain ≤ 0).

What does

\lambda

do?

L2 regularization on leaf weights; shrinks

w_j^*

toward 0, reducing overfit.

For squared error, what are

g_i

and

h_i

g_i=\hat y_i^{(t-1)}-y_i

(negative residual),

h_i=1

For log-loss, what are

g_i

and

h_i

g_i=p_i-y_i

h_i=p_i(1-p_i)

, with

p_i=\sigma(\hat y_i)

Why can't you just add unlimited trees in XGBoost like in Random Forest?

Trees are dependent and fit residuals, so extra trees overfit noise; use early stopping instead of averaging.

What is the role of learning rate (eta)?

Scales each tree's contribution:

\hat y^{(t)}=\hat y^{(t-1)}+\eta f_t

; smaller eta = slower, more robust learning needing more trees.

Which two hyperparameters are the highest-leverage tuning pair?

Low learning_rate + n_estimators controlled by early stopping on a validation set.

How is XGBoost different from Random Forest structurally?

RF averages independent parallel trees (variance reduction); XGBoost sums dependent sequential trees fitting residuals (bias reduction via boosting).

Connections

Gradient Boosting — XGBoost is a regularized, 2nd-order implementation.
Decision Trees — the base learner ( $f_k$ ).
Random Forests — contrast: bagging/parallel vs boosting/sequential.
Regularization (L1 L2) — $\lambda,\alpha$ act on leaf weights.
Bias-Variance Tradeoff — boosting reduces bias; regularization controls variance.
Taylor Series — basis of the gradient+Hessian approximation.
Newton's Method — $w^*=-G/(H+\lambda)$ is a damped Newton step.

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Dekho, XGBoost ka core idea simple hai: ek hi bada tree banane ki jagah, hum bahut saare chote trees ek-ek karke banate hain. Pehla tree kuch predict karta hai, usme jo galtiyan (residuals) reh jaati hain, doosra tree unko theek karta hai, phir teesra baaki galtiyan theek karta hai — aise chain chalti rehti hai. Isko boosting bolte hain. Random Forest se difference yeh hai ki wahan saare trees independent hote hain aur average lete hain, yahan har tree pichhle ke mistakes pe depend karta hai.

Ab maths ki jaan: har round pe hum loss ko 2nd-order Taylor expansion se approximate karte hain, yaani gradient $g_i$ (kis direction fix karna hai) aur Hessian $h_i$ (kitna carefully fix karna hai) dono use karte hain. Isse ek leaf ka best value nikalta hai: $w^* = -G/(H+\lambda)$ . Yeh $\lambda$ leaf value ko chhota (shrink) karta hai taaki overfit na ho. Aur split karna hai ya nahi, yeh Gain formula batata hai — agar Gain $\gamma$ se kam hai to split reject, matlab automatic pruning ho jaata hai.

Tuning ka 80/20: sabse important hai learning_rate (eta) chhota rakho aur early stopping use karo validation set pe, taaki trees ki sahi number khud choose ho jaaye. Ek badi galti students karte hain — "zyada trees matlab zyada accuracy" — yeh Random Forest me sahi hai, par XGBoost me zyada trees noise ko fit karke overfit kar dete hain. Isi tarah max_depth bahut zyada mat rakho (usually 3 se 8), warna har deep tree ke saath overfit compound hota jaata hai. Regularization ke liye gamma, min_child_weight, lambda ka combination use karo. Bas yaad rakho: dheere seekho, samay pe ruk jaao.

Test yourself — Tree-Based & Instance Methods

Connections