পাঠ ২৩ · ৪৫-এর মধ্যে · মডিউল ৩

Home / AI Courses / Machine Learning / Gradient Boosting

Gradient Boosting — additive মডেল

Gradient boosting — sequential weak learners

৮ মিনিট পড়া মাঝারি · Intermediate NumPy + sklearn

এই পাঠে যা শিখবেন

Sequential ensemble — bagging-এর সাথে fundamental পার্থক্য
Additive model formulation — stage-wise updating
"Functional gradient descent" — residual = negative gradient interpretation
Learning rate ও number of trees — main hyperparameter
NumPy থেকে scratch GBM regression — sklearn-এর সাথে compare

১ · Bagging vs Boosting — fundamental পার্থক্য

দিক	Bagging (RF)	Boosting (GBM)
Training	Parallel — independent	Sequential — dependent
Goal	Variance ↓	Bias ↓ (mostly)
Base learner	Deep, low-bias	Shallow, high-bias
Overfit	Resistant	Possible (tune dরকার)
Speed	Fast (parallel)	Slower (sequential)
Accuracy ceiling	Good	Often best (tabular)

২ · Additive model

Boosting-এর mathematical core — additive modelAdditive Model$F(x) = \sum_m h_m(x)$ — অনেক simple function-এর যোগ। Boosting এই form-এ stage-wise build। প্রতি stage-এ একটি $h_m$ যোগ — আগের $F$-এর residual fix করতে।:

$$F(x) = \sum_{m=0}^{M} \eta \cdot h_m(x)$$

$h_m$ — weak learner (সাধারণত depth ৩-৬-এর tree)।
$\eta$ — learning rate (০.০১-০.১ typical)।
$M$ — total iterations (১০০-২০০০)।

Iteratively build:

$$F_m(x) = F_{m-1}(x) + \eta \cdot h_m(x)$$

প্রতিটি $h_m$ চয়ন — যাতে loss সর্বনিম্ন হয়।

৩ · Residual = Negative Gradient

Squared error loss-এ:

$$L(y, F(x)) = \frac{1}{2}(y - F(x))^2$$

$F(x)$-এর সাপেক্ষে gradient:

$$\frac{\partial L}{\partial F(x)} = -(y - F(x))$$

অর্থাৎ residual $r = y - F(x)$ = negative gradient। তাই — residual fit করা মানে loss-এর gradient direction-এ এগোনো।

Functional Gradient Descent

Standard GD — parameter space-এ। GBM — function space-এ। Each $h_m$ — gradient direction step। $\eta$ — step size। Conceptually beautiful — Friedman-এর insight।

৪ · Algorithm — full picture

Initialize $F_0(x) = \arg\min_c \sum_i L(y_i, c)$ — squared loss-এ mean।
$m = 1, 2, \ldots, M$ পুনরাবৃত্তি:
1. প্রতি sample-এ pseudo-residual: $r_{i,m} = -\left[\frac{\partial L(y_i, F(x_i))}{\partial F(x_i)}\right]_{F=F_{m-1}}$।
2. একটি ছোট tree $h_m$ — $\{(x_i, r_{i,m})\}$-এ fit।
3. Optimal step size $\gamma_m$ (line search; trees-এ leaf-wise calc)।
4. Update: $F_m(x) = F_{m-1}(x) + \eta \cdot \gamma_m h_m(x)$।
Output $F_M(x)$।

Classification-এ: log-loss-এর gradient — pseudo-residual = $y_i - p_i$। শুধু loss function বদলায়; framework একই।

৫ · Learning rate — হঠাৎ কেন গুরুত্বপূর্ণ

Pure additive — $\eta = 1$, প্রতি step পুরো residual fix। কিন্তু বাস্তবে $\eta = 0.05-0.1$।

Shrinkage: প্রতি tree-এর contribution scale-down।
Regularization: overfitting prevent।
More trees needed: $\eta = 0.1$ → ১০× tree। Tradeoff।
Empirical sweet spot: $\eta = 0.05, M = 1000$ — typical Kaggle setup।

"Slow learning is good learning" — এই principle deep learning-এও similar (LR scheduling)। Boosting earliest example।

প্রতি iteration — pৃvious-এর residual fit। Training loss decay; validation loss U-shape — early stopping required।

৬ · NumPy দিয়ে — minimal regression GBM

Python · NumPy

import numpy as np
from sklearn.tree import DecisionTreeRegressor

class MiniGBM:
    def __init__(self, n_iter=100, eta=0.1, max_depth=3, seed=0):
        self.n_iter, self.eta, self.max_depth = n_iter, eta, max_depth
        self.seed = seed
        self.trees = []

    def fit(self, X, y):
        # F_0 — mean
        self.F0 = y.mean()
        F = np.full_like(y, self.F0, dtype=float)
        rng = np.random.RandomState(self.seed)
        for _ in range(self.n_iter):
            r = y - F                                # negative gradient (squared loss)
            t = DecisionTreeRegressor(max_depth=self.max_depth,
                                      random_state=rng.randint(1e6))
            t.fit(X, r)
            F = F + self.eta * t.predict(X)
            self.trees.append(t)
        return self

    def predict(self, X):
        F = np.full(X.shape[0], self.F0)
        for t in self.trees:
            F = F + self.eta * t.predict(X)
        return F

# Test on synthetic
np.random.seed(0)
X = np.random.rand(500, 1) * 10
y = np.sin(X[:, 0]) + 0.1 * np.random.randn(500)

gbm = MiniGBM(n_iter=200, eta=0.05).fit(X, y)
preds = gbm.predict(X)
print(f"Train MSE: {np.mean((preds - y)**2):.4f}")

Single tree — ১.০ MSE; GBM ২০০ iterations-এ ০.০২। Iterative residual learning-এর শক্তি।

৭ · sklearn — production GBM

Python · scikit-learn

from sklearn.ensemble import GradientBoostingClassifier
from sklearn.datasets import load_breast_cancer
from sklearn.model_selection import train_test_split

X, y = load_breast_cancer(return_X_y=True)
Xt, Xv, yt, yv = train_test_split(X, y, test_size=0.3, random_state=0)

gbm = GradientBoostingClassifier(
    n_estimators=300,
    learning_rate=0.05,
    max_depth=3,
    subsample=0.8,           # stochastic gradient boosting
    random_state=0
)
gbm.fit(Xt, yt)
print(f"Train acc: {gbm.score(Xt, yt):.4f}")
print(f"Val acc:   {gbm.score(Xv, yv):.4f}")

# Iteration-wise validation curve
import numpy as np
val_scores = [gbm.staged_predict(Xv)]  # generator → loop
errors = []
for i, p in enumerate(gbm.staged_predict(Xv)):
    errors.append(1 - (p == yv).mean())
print(f"Best iteration: {np.argmin(errors)}")

staged_predict — প্রতি iteration-এ prediction দেখায়। Validation error U-shape দেখলে — early stopping point খুঁজে পাবেন।

৮ · Hyperparameter — কী tune

n_estimators ও learning_rate: conjugate। কম $\eta$ → বেশি iterations। ${\eta} \cdot {M}$ — effective complexity।
max_depth (৩-৮): shallow trees, weak learners। Deep tree boost-এ overfit।
subsample (০.৫-১.০): Friedman's stochastic GB — প্রতি iteration random subset।
min_samples_leaf: noise-resistance।
Early stopping: validation loss U-shape — best iteration বাছুন।

৯ · GBM-এর সমস্যা ও modern সমাধান

Slow: sequential — parallel না। sklearn GBM ধীর। সমাধান: HistGradientBoostingClassifier, XGBoost, LightGBM।
Tuning sensitive: RF-এর তুলনায় বেশি hyperparameter, careful CV।
Overfit prone: early stopping critical।
Categorical handling weak: sklearn — one-hot needed। CatBoost native।

Modern era-এ "GBM" ≈ XGBoost/LightGBM। Vanilla sklearn-এর GBM educational; production-এ optimized libraries।

ভাবনার প্রশ্ন

প্রতিটি প্রশ্ন নিজে কিছুক্ষণ ভাবুন — তারপর "→ উত্তর" চাপুন।

প্র ০১ "Functional gradient descent" শুনতে exotic। GD parameter space-এ — boosting function space-এ — এই abstraction কেন এত powerful, এবং কীভাবে XGBoost এই idea-কে extend করেছে?

Friedman (২০০১)-এর "Greedy Function Approximation" — ML history-এর landmark paper। Boosting-কে gradient descent-এর lens-এ recast।

Standard parameter GD:

$\theta_{t+1} = \theta_t - \eta \nabla L(\theta_t)$।
Parameter space-এ step।
Linear/NN-এ.

Functional GD:

$F$ — function (not parameters)।
$F_{t+1} = F_t - \eta \cdot g_t$ — function space-এ step।
$g_t = \nabla L|_{F=F_t}$ — gradient at each $x_i$।
$g_t$ একটি function — point-wise gradients।

সমস্যা — $g_t$ training points-এ defined শুধু:

$g_t$-এর মান $\{(x_i, g_t(x_i))\}$-এ available।
Test point $x^*$-এ unknown।
Solution: একটি weak learner $h$ — $g_t$ approximate, generalize।

Boosting interpretation:

Step direction = negative gradient।
$h_m$ = generalizable approximation।
Step size $\eta$।
$F_{m+1} = F_m + \eta \cdot h_m$।

কেন powerful:

(১) Loss-agnostic framework:

Squared loss → regression।
Log loss → binary classification।
Multinomial → multi-class।
Pinball → quantile regression।
Custom loss possible।

(২) Modular design:

Loss + base learner + step size — কাস্টমাইজেবল।
Same code, different problems।

(৩) Theoretical analysis:

Convergence guarantees।
Statistical properties।
Universal approximation।

XGBoost extension — second-order:

GBM first-order (gradient only)।
XGBoost — Taylor expansion second-order: $$L(F_t + h) \approx L(F_t) + g \cdot h + \frac{1}{2} H \cdot h^2$$
$g$ — gradient, $H$ — hessian।
Newton's method analogue।

সুবিধা — second-order:

Step size automatic — no $\eta$ tuning crucial।
Adaptive — different curvatures।
Faster convergence।
Better numerical stability।

XGBoost objective:

$$\mathcal{O}_t = \sum_i \left[g_i \cdot h_t(x_i) + \frac{1}{2} H_i \cdot h_t(x_i)^2\right] + \Omega(h_t)$$

$\Omega$ — regularization (number of leaves + leaf weight L2)।
Closed-form leaf weight — derivable।
Beautiful math।

Modern extensions:

LightGBM: histogram-based — speed।
CatBoost: ordered boosting — leak-free categorical।
NGBoost: probabilistic distributions।
SnapBoost: heterogeneous base learners।

Connection to neural nets:

NN — parameter GD, deep architecture।
Boosting — function GD, ensemble।
Both — gradient descent variants।
Tabular: boosting wins; image/text: NN wins।

মূল উপলব্ধি: Functional GD — abstract, কিন্তু practical। Loss-agnostic, modular, theoretically grounded। XGBoost — second-order extension — modern dominance-এর source।

প্র ০২ Bagging variance কমায়, boosting bias কমায় — কিন্তু কেন এই asymmetry? Deep tree boost-এ ব্যবহার করলে কী হয়?

Bias-variance perspective — ensemble methods বুঝতে central। Asymmetry rooted in algorithm design।

Bagging — variance reduction:

Independent estimators — $\sigma^2/B$ averaging।
Bias unchanged।
"Many wrong answers, mostly cancel"।

Boosting — bias reduction:

Sequential — each fixes previous mistakes।
Variance not main concern।
"Build complex model from simple parts"।

Why asymmetry:

(১) Bagging-এ base learner হাই-variance ভালো:

Deep tree — high variance, low bias।
Bagging variance-এ harm।
Average → low bias, low variance।

(২) Boosting-এ base learner হাই-bias ভালো:

Stump (depth ১) — high bias, low variance।
Boosting bias incrementally fix।
Sequential addition — complexity ধীরে ধীরে বাড়ে।

Deep tree in boosting — disasters:

(১) Overfitting catastrophic:

Deep tree — already overfit।
Boosting overfit amplify।
Validation degrade rapidly।

(২) Variance accumulate:

Each tree noisy।
Sum-এ noise compound।
No averaging-out।

(৩) Computational waste:

Each iteration expensive।
Marginal benefit।

(৪) Theoretical:

Boosting convergence — weak learner assumption।
Strong learner — assumption violation।
Theoretical guarantee lost।

Empirical evidence:

$max\_depth = 1$ — stump, AdaBoost classical।
$max\_depth = 3-6$ — modern GBM sweet spot।
$max\_depth > 10$ — sharp degradation।

Hybrid — Random Forest of GBMs?

Theoretically possible।
Practically unstable।
Each GBM already optimized।
Bagging-of-bagging redundant।

Stochastic Gradient Boosting:

Friedman extension।
Each iteration — random subset (sub-sample)।
Bagging-like variance reduction added।
$subsample = 0.5-0.8$ — typical।

Why this works:

Bias reduction (boosting) + variance reduction (subsampling)।
Best of both worlds।
Modern XGBoost/LightGBM — default include।

Practical decision tree:

Depth ১: Pure boosting, classical AdaBoost।
Depth ৩-৬: Modern GBM sweet spot।
Depth ৬-১০: Borderline — careful tuning।
Depth > ১০: Avoid in boosting।

Random Forest counterpart:

Depth limit None: fully grown — bagging variance kill।
$max\_depth = 5$ in RF — under-fit risk।
Opposite philosophy।

মূল উপলব্ধি: Algorithm-base learner pairing critical। RF — strong base; GBM — weak base। Hybrid (subsampling) — best of both।

প্র ০৩ Learning rate কমালে accuracy বাড়ে কেন? Validation curve U-shape কোথা থেকে আসে — early stopping কীভাবে কাজ করে?

Learning rate ও early stopping — boosting-এর critical art। Theoretical ও practical দু'দিক।

Learning rate বুঝা:

$F_{m+1} = F_m + \eta \cdot h_m$।
$\eta = 1$ — pure additive, full step।
$\eta = 0.1$ — partial step, "gradient descent"।

কেন কম $\eta$ better:

(১) Smoother gradient descent:

Big step — overshoot risk।
Small step — careful approach।
Convergence smoother।

(২) Implicit regularization:

Each tree contribute less।
"Slow learning" — generalize better।
Like Dropout — small effect each।

(৩) More effective trees:

$\eta = 1, M = 10$ → ১০ trees full influence।
$\eta = 0.1, M = 100$ → ১০০ trees partial।
Diversity ও averaging benefit।

(৪) Early signal accuracy:

$\eta$ ছোট — early trees important pattern capture।
Later trees — refinements।
Hierarchical learning।

$\eta$ ও $M$ tradeoff:

$\eta \cdot M \approx$ constant — effective complexity।
$\eta = 0.01, M = 5000$ — slow but accurate।
$\eta = 0.5, M = 100$ — fast but less।
Computational ও time tradeoff।

Validation curve U-shape:

Iteration 0: high error — under-fit।
Early iterations: rapid improvement।
Mid iterations: minimum error।
Late iterations: degradation — overfit।

Why U-shape:

Early — signal learned।
Mid — signal saturated।
Late — noise memorized।
Bias decreases, variance increases।

Early stopping algorithm:

Hold-out validation set।
প্রতি iteration — validation error track।
Best validation error iteration save।
Patience parameter — improvement plateau-এর পরে stop।
Final model — best iteration।

Implementation:

gbm = GradientBoostingClassifier(
    n_estimators=1000,
    learning_rate=0.05,
    n_iter_no_change=20,    # patience
    validation_fraction=0.2,
    tol=1e-4
)

XGBoost early stopping:

import xgboost as xgb
model = xgb.XGBClassifier(
    n_estimators=2000,
    learning_rate=0.05,
    early_stopping_rounds=50
)
model.fit(Xt, yt, eval_set=[(Xv, yv)], verbose=False)
print(f"Best iteration: {model.best_iteration}")

Practical recipe:

(১) $\eta$ small (0.01-0.1)।
(২) $M$ large (1000-10000)।
(৩) Early stopping patience।
(৪) Validation set 20-30%।
(৫) Multiple runs different seeds — robust।

Risks:

Validation contamination: stop নিলে — same validation hyperparameter selection।
Solution: separate test set।
Stopping noise: multiple seed averaging।

Theoretical perspective:

Early stopping — implicit regularization।
Equivalent to L2 in linear cases।
Capacity control — prevent memorization।

মূল উপলব্ধি: Slow learning + early stopping — boosting-এর dual safety net। "Stop before you regret"।

প্র ০৪ Bangladesh-এর একটি bank credit scoring-এ GBM ব্যবহার করতে চাইছেন। RF-এর তুলনায় কেন বেছে নেবেন? Deployment risk কী?

Credit scoring — production ML-এর high-stakes application। GBM choice strategic।

GBM-এর সুবিধা:

(১) Higher accuracy:

Tabular data Kaggle benchmark — GBM dominant।
RF ৯৩%, GBM ৯৫% — small diff, big money।
Per percentage — millions BDT।

(২) Probability calibration:

RF probability "majority vote" → coarse।
GBM continuous output → smoother।
Risk score better।
Threshold tuning effective।

(৩) Custom loss:

Asymmetric cost — false approval costlier than false rejection।
GBM custom loss possible।
Business KPI direct optimize।

(৪) Feature importance fine-grained:

SHAP values — better calibration।
Per-decision explanation।
Regulator audit-friendly।

(৫) Memory efficient:

Shallow trees, fewer leaves।
Production-এ smaller।
Edge deployment feasible।

(৬) Fast inference:

৩০০ shallow trees — sub-millisecond।
Real-time scoring।

Deployment risks:

(১) Overfitting hidden:

Training accuracy high — false confidence।
Validation U-shape miss করলে — overfit।
Production drift — accuracy collapse।
Mitigation: rigorous early stopping, holdout test।

(২) Hyperparameter sensitivity:

RF default robust।
GBM tune-dependent।
Wrong hyperparameter — major degradation।
Mitigation: Bayesian optimization, repeated CV।

(৩) Concept drift:

Economic condition change — old patterns invalidate।
COVID era — mass default pattern shift।
GBM rigid — RF more robust to drift।
Mitigation: regular retraining, online learning, drift detection।

(৪) Adversarial:

Loan applicant gaming features।
Boundary samples manipulated।
GBM sharp boundary - fragile।
Mitigation: robust features, anomaly detection layer।

(৫) Class imbalance:

Default ৫% — minority।
GBM accuracy maximize → majority predict।
Recall low।
Mitigation: custom loss, sample weights, threshold tuning।

(৬) Interpretability concerns:

৫০০ trees — direct interpretability hard।
SHAP — slow per prediction।
Customer dispute — explanation needed।
Mitigation: SHAP cache, rule extraction।

(৭) Regulatory:

Bangladesh Bank — explainable AI guideline।
"Right to explanation" — emerging।
Black-box reject possible।
Mitigation: documentation, SHAP report per loan।

(৮) Bias amplification:

Historical bias — district, gender।
GBM amplify subtle bias।
Fair lending violation risk।
Mitigation: bias audit, fairness constraints।

(৯) Cold start:

New customer — sparse features।
GBM uncertain — high variance।
Mitigation: rule-based first 6 months, then GBM।

(১০) Explainability gap:

SHAP local — global narrative not direct।
Feature importance — global but ambiguous।
Mitigation: linear surrogate model alongside, hybrid।

Production architecture:

Layer 1 — rule: hard rejects (KYC fail)।
Layer 2 — GBM: primary score।
Layer 3 — linear: sanity check।
Layer 4 — human: high-value, edge cases।

Monitoring:

Daily — score distribution shift।
Weekly — calibration check।
Monthly — fairness audit।
Quarterly — full retraining।

Bangladesh-specific:

Mobile money data — new feature source।
Limited credit bureau।
Informal economy — alternative scoring।
Regulatory evolving — flexible architecture।

মূল উপলব্ধি: GBM accuracy advantage real, কিন্তু operational risks। RF + GBM hybrid — risk-balanced। Deployment process — algorithm choice 30%, system 70%।

অনুশীলন

হিসাব করুন: Squared loss-এ — $y = 5, F_0 = 3$। Pseudo-residual কত? $\eta = 0.1$, tree predicted $h_1 = 2$। $F_1$ কত?
- $r = y - F_0 = 5 - 3 = 2$।
- $F_1 = F_0 + \eta \cdot h_1 = 3 + 0.1 \cdot 2 = 3.2$।
- আরও কাছে — পরের iteration $r = 5 - 3.2 = 1.8$।

sklearn: $\eta = [0.01, 0.05, 0.1, 0.5]$ — accuracy plot। কোন optimum?

for lr in [0.01, 0.05, 0.1, 0.5]:
    gbm = GradientBoostingClassifier(n_estimators=300, learning_rate=lr,
                                     random_state=0).fit(Xt, yt)
    print(lr, gbm.score(Xv, yv))
# 0.01-0.05 typical sweet spot।

চিন্তা: Boosting parallel কেন না? Possible solutions বলুন।

প্রতি iteration previous-এর residual লাগে — sequential। Workarounds: (১) intra-tree parallelism (XGBoost split finding), (২) histogram-based parallel feature processing (LightGBM), (৩) approximate parallel boosting (research)।