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

Home / AI Courses / Machine Learning / Random Forest

Random Forest — bagging

Random Forests — bagged ensemble of trees

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

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

Bagging — কেন variance কমায় (গাণিতিক explanation)
Random feature subset — bagging-এর অতিরিক্ত decorrelation
Random Forest pseudocode — তাত্ত্বিক ভিত্তি
NumPy থেকে scratch RF — bootstrap, feature sampling, voting
sklearn RandomForestClassifier — practical hyperparameter

১ · Single tree-এর সমস্যা

Decision tree interpretable, fast, কিন্তু — ছোট data perturbation-এ tree সম্পূর্ণ বদলায়। একে বলে high variance। দু'টি ভিন্ন training sets — দু'টি সম্পূর্ণ ভিন্ন tree। Test accuracy-ও ভিন্ন।

সমাধান কী? — অনেক tree বানাও, output average। যদি প্রতিটি tree-র error independent হয় — average এর variance dramatically কমবে। সংখ্যার law।

২ · Bagging — Bootstrap Aggregating

Breiman (১৯৯৬)-এর insight। BaggingBaggingBootstrap Aggregating — একই training set থেকে $B$টি bootstrap sample (with replacement), প্রতিটিতে আলাদা মডেল train, predictions average। Variance reduction-এর fundamental ensemble technique। পদ্ধতি:

Training set $D$ ($n$ samples) থেকে $B$টি bootstrap sample — প্রতিটি $n$ samples, with replacement।
প্রতিটি sample-এ একটি tree train।
Test-এ — সব trees-এর prediction average (regression) বা majority vote (classification)।

গাণিতিক ফল: $B$টি independent trees-এর mean prediction-এর variance:

$$\text{Var}(\bar{f}) = \frac{\sigma^2}{B}$$

কিন্তু trees শুধু একই data-র subset-এ train — তাই predictions correlated ($\rho$)। Real variance:

$$\text{Var}(\bar{f}) = \rho \sigma^2 + \frac{(1-\rho) \sigma^2}{B}$$

$B \to \infty$ — variance $\rho \sigma^2$-এ thামে। তাই $\rho$ কমানো দরকার।

৩ · Random Forest — feature randomness যোগ

Breiman (২০০১) — RF যোগ করে দু'টি জিনিস:

(১) Bootstrap sampling: bagging থেকে।
(২) Random feature subset: প্রতি split-এ — সব feature না দেখে, random একটি subset (size $m$) থেকে best বাছা।

এই feature randomness — trees-এর correlation $\rho$ আরো কমায়। প্রতিটি tree আলাদা features দিয়ে split করে — দেখতে আলাদা।

Default $m$

Classification: $m = \sqrt{d}$ — ১০০ features-এ ১০।
Regression: $m = d/3$ — ১০০ features-এ ৩৩।
Empirically Breiman optimal পেয়েছেন।

৪ · Random Forest — algorithm

$B$ গাছ — সাধারণত ১০০-৫০০।
প্রতি tree-এর জন্য:
1. $D$ থেকে $n$ samples bootstrap (with replacement)।
2. Tree grow — প্রতি split-এ:
  - $d$ features থেকে random $m$ বাছা।
  - সেই $m$-এ best split (Gini/entropy/MSE)।
3. Tree fully grow — pruning নেই।
Prediction:
- Classification — majority vote।
- Regression — mean prediction।

Pruning কেন নেই? — single tree overfit করুক, কিন্তু average smooth। Bagging-এর philosophy এটাই।

৫ · কেন কাজ করে — bias-variance lens

Bias: single tree আর forest প্রায় একই — bagging bias বদলায় না।
Variance: dramatically কমে — $B$ trees ও feature randomness মিলে।
Total error: variance-dominated regime-এ অনেক drop।
Trade-off: training time $\times B$, prediction time $\times B$ — but parallel।

"Wisdom of the crowd" — অনেক noisy estimator-এর majority প্রায়ই একটি smart estimator-এর চেয়ে ভাল। Condorcet's jury theorem-এর ML version।

Each tree — bootstrap sample-এ trained, প্রতি split-এ random feature subset। Final prediction — majority vote (classification) বা mean (regression)।

৬ · NumPy দিয়ে — minimal Random Forest

Python · NumPy

import numpy as np
from sklearn.tree import DecisionTreeClassifier

class MiniRandomForest:
    def __init__(self, n_trees=50, max_features='sqrt', max_depth=None, seed=0):
        self.n_trees = n_trees
        self.max_features = max_features
        self.max_depth = max_depth
        self.rng = np.random.RandomState(seed)
        self.trees = []

    def fit(self, X, y):
        n, d = X.shape
        m = int(np.sqrt(d)) if self.max_features == 'sqrt' else d
        self.trees = []
        for _ in range(self.n_trees):
            # bootstrap sample
            idx = self.rng.choice(n, size=n, replace=True)
            # random feature subset for each tree (sklearn handles per-split internally)
            tree = DecisionTreeClassifier(max_features=m,
                                          max_depth=self.max_depth,
                                          random_state=self.rng.randint(1e6))
            tree.fit(X[idx], y[idx])
            self.trees.append(tree)
        return self

    def predict(self, X):
        votes = np.array([t.predict(X) for t in self.trees])
        # majority vote per column
        return np.array([np.bincount(votes[:, i]).argmax()
                         for i in range(X.shape[0])])

# Test
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)

rf = MiniRandomForest(n_trees=50).fit(Xt, yt)
single = DecisionTreeClassifier(random_state=0).fit(Xt, yt)
print(f"Single tree val acc:  {single.score(Xv, yv):.4f}")
print(f"Random Forest val acc: {(rf.predict(Xv) == yv).mean():.4f}")

Single tree typically ৯০-৯২%, RF ৯৫-৯৭% — শুধু bagging ও feature randomness যোগ করেই। কোনো tuning নেই।

৭ · sklearn — production Random Forest

Python · scikit-learn

from sklearn.ensemble import RandomForestClassifier
from sklearn.datasets import load_breast_cancer
from sklearn.model_selection import cross_val_score

X, y = load_breast_cancer(return_X_y=True)

rf = RandomForestClassifier(
    n_estimators=300,
    max_features='sqrt',
    max_depth=None,         # fully grown trees
    min_samples_leaf=1,
    n_jobs=-1,              # parallel
    random_state=0
)

scores = cross_val_score(rf, X, y, cv=5, n_jobs=-1)
print(f"CV accuracy: {scores.mean():.4f} ± {scores.std():.4f}")

# Top features
rf.fit(X, y)
feat_imp = sorted(zip(rf.feature_importances_, range(len(rf.feature_importances_))),
                  reverse=True)[:5]
print("Top 5 features (idx, importance):")
for imp, idx in feat_imp:
    print(f"  feature {idx}: {imp:.4f}")

n_jobs=-1 — সব CPU core ব্যবহার করে parallel। RF embarrassingly parallel — প্রতি tree independent। feature_importances_ built-in।

৮ · Hyperparameter — কী tune করবেন

n_estimators (১০০-১০০০): বেশি = better, plateau আসে। ৫০০ সাধারণ default।
max_features ('sqrt', 'log2', None): trees-এর correlation control। Default ভালো।
max_depth (None বা ১০-৩০): overfit prevent। Default None — fully grown।
min_samples_leaf (১-১০): leaf-এ minimum samples। Noise-এ leaf prevent।
min_samples_split (২-২০): split-এর minimum sample।
bootstrap (True/False): Default True — bagging-এর core।

৯ · কোথায় Random Forest fail

Sparse high-dim data: তথ্য কম — decision boundary noisy। NLP-এ NB/linear better।
Smooth functions: physics regression — kernel methods বা NN।
Time series — temporal: RF independence assume — sequential data ব্যবহারের জন্য careful feature engineering।
Categorical with high cardinality: tree splits problematic। Target encoding বা CatBoost।
Memory: ৫০০ deep trees — hundreds of MB। Edge deployment-এ challenging।

Random Forest "default-এ ভাল" — production-এ সবসময় baseline-এ run করুন। যদি RF accuracy > ৮৫% হয় — অন্য কিছুই ৯০% পেতে অনেক effort। Pareto principle।

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

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

প্র ০১ "Wisdom of the crowd" — অনেক weak learners-এর average একটি smart learner-এর চেয়ে ভাল কেন? গাণিতিকভাবে দেখান।

Bagging-এর foundation — Condorcet's jury theorem ও variance reduction। Ensemble learning-এর ভিত্তি।

Variance reduction (regression):

$B$ independent estimators, each variance $\sigma^2$।
Average estimator-এর variance: $\sigma^2 / B$।
$B = 100$ → ১০০ গুণ variance কম।
Bias unchanged।

Reality — correlated estimators:

Trees same data-র subset-এ trained → correlated।
Correlation $\rho$।
Average variance: $\rho \sigma^2 + (1-\rho) \sigma^2 / B$।
Limit ($B \to \infty$): $\rho \sigma^2$।
$\rho = 0.5, \sigma^2 = 1$ → ০.৫ variance — half।

RF-এর genius — $\rho$ কমানো:

Bagging — sample diversity।
Feature randomness — additional decorrelation।
$\rho$ ০.৩-এ নামতে পারে — variance ৩৫% কম।

Classification — Condorcet (১৭৮৫):

$n$ jurors, প্রতিজন accuracy $p > 0.5$।
Majority vote accuracy $\to 1$ as $n \to \infty$।
"Independent better-than-random voters" — collective infallible।

Mathematical example:

Each tree accuracy 0.6 (only 0.1 above random)।
Independent — ১০০ trees ensemble: $$P(\text{majority correct}) = \sum_{k=51}^{100} \binom{100}{k} (0.6)^k (0.4)^{100-k} \approx 0.97$$
From 60% to 97% — power of ensemble।

Independence importance:

Perfect correlation — ensemble = single model।
Independent — magnification।
Real — partially correlated, partially independent।

Why "weak" learners:

Strong learners — already $p \to 1$।
Diversity-এর scope কম।
Weak learners — cumulative gain বেশি।

Real-world analogues:

Stock market — wisdom of crowds (Galton ১৯০৬, ox weight estimation)।
Wikipedia — many editors converge accurate।
Kaggle — winning solutions ensemble of many models।

Failure modes:

Bias correlated — ensemble inherits bias।
Garbage-in models — averaging amplifies noise।
Adversarial — coordinated attack defeat ensemble।

Modern extension — Boosting:

Sequential — each model fix previous-এর mistake।
Bias reduction — additional power।
RF parallel; Boosting sequential — different tradeoffs।

মূল উপলব্ধি: Ensemble — ML-র "free lunch"-এর কাছাকাছি। Diversity engineered — accuracy free গামে। Single model perfectly tuned-এর চেয়ে — many models simply averaged better।

প্র ০২ RF কেন overfit prone নয়, যদিও individual trees fully grown? "More trees can't hurt" — সত্য না হাফ-সত্য?

RF-এর intriguing property। Common misconception আছে — "more trees overfit করে"। Reality nuanced।

Why fully-grown trees কাজ করে:

Single deep tree — high variance, low bias।
Bagging — variance kill।
Net result: low bias + low variance।
Pruning prematurely bias বাড়াত — tradeoff opposite direction।

"More trees can't hurt" — সত্য:

Test error monotonically nonincreasing as $B \to \infty$ (theoretical)।
$B$ বাড়ালে — variance শুধু কমে।
Bias unchanged।
Asymptotic error $\rho \sigma^2$ — plateau।

"More trees can't hurt" — হাফ-সত্য:

(১) Computation cost:

Time linearly grow।
Memory linearly grow।
৫০০ trees vs ৫০০০ trees — tiny accuracy gain, ১০× cost।

(২) Diminishing returns:

$B = 100$ → ৯৫% accuracy।
$B = 1000$ → ৯৫.২% accuracy।
$B = 10000$ → ৯৫.২৫%।
Plateau early।

(৩) Practical considerations:

Training data limited — same bootstrap repeat।
Trees redundant।
৫০০ trees usually optimal।

RF কখন overfit করে:

Noisy labels: trees noise-এ memorize।
Tiny dataset: bootstrap diverse না।
Highly correlated features: feature randomness ineffective।
Imbalanced classes: majority class dominate।

OOB error — built-in validation:

প্রতি tree — ৩৭% samples bootstrap-এ নেই।
সেগুলো প্রায় free validation।
OOB error — true test error-এর কাছাকাছি।
আলাদা CV অনেক সময় অপ্রয়োজন।

Bias source unchanged:

RF bias = single tree bias।
Tree-এর axis-aligned limitation persistent।
Diagonal boundary — many splits লাগে।
Solution: smarter base learner (oblique tree, GBT)।

Tuning advice:

$B$ — set high (৫০০), don't fuss।
$m$ (max_features) — sqrt usually best।
$min\_samples\_leaf$ — noise এ ১-৫।
$max\_depth$ — None typical।

Comparison with neural nets:

NN: epochs-এ overfit risk।
RF: trees-এ no overfit (theoretical)।
RF practical robustness — production preference।

মূল উপলব্ধি: RF "set and forget" mostly। Diminishing returns সত্য, কিন্তু harm নয়। Default hyperparameter-এ baseline — Bangladesh fintech, e-commerce, healthcare-এ standard।

প্র ০৩ RF-এর feature_importances_ — interpretable শোনায়, কিন্তু trap আছে। কী এই trap এবং reliable alternative কী?

Feature importance — production ML communication-এ critical। কিন্তু RF-এর built-in importance — subtle pitfalls।

RF built-in importance — কীভাবে calculate:

প্রতি split-এ Gini reduction।
সব trees-এ aggregate।
Normalize — sum to 1।
"Mean Decrease in Impurity" (MDI)।

Trap-1: High cardinality bias:

Continuous / many-category features অনেক split offer।
Random সম্ভাবনায় কিছু useful split পায়।
Importance inflated।
Example: customer_id (unique) — top important দেখায়, কিন্তু useless।

Trap-2: Correlated features:

Two correlated features — importance শেয়ার।
Each shows half importance।
Truth: একজন highly important।
Misleading attribution।

Trap-3: Training-only metric:

Importance training data-এ calculate।
Overfit features-ও high importance।
Generalization-এ irrelevant।

Trap-4: Direction lost:

"Income important" — কিন্তু high না low?
Importance scalar — direction nonexistent।
Linear coefficient সরাসরি direction দেখায়।

Reliable alternatives:

(১) Permutation Importance:

একটি feature-এর values randomly shuffle।
Performance drop measure।
Validation set-এ — generalization-aware।
Cardinality-bias-free।
sklearn: permutation_importance।

(২) SHAP values:

Shapley game theory — fair attribution।
Per-prediction explanation।
Direction included।
Computational expensive।
shap library — TreeExplainer fast tree-এর জন্য।

(৩) Drop-column importance:

একটি feature বাদ দিয়ে retrain।
Performance drop measure।
Most accurate, slowest।

(৪) Partial Dependence Plot (PDP):

Feature value vary করে — prediction average দেখা।
Direction ও nonlinearity visualize।
Marginal effect।

(৫) Linear baseline coefficient:

Logistic regression train।
Coefficient → direction + magnitude।
Cross-check tool।

Best practice:

Multiple methods compare।
Domain knowledge — sanity check।
Permutation + SHAP — gold standard।
Built-in MDI — quick screening only।

Real-world example — credit scoring:

MDI: customer_id top — clearly bug।
Permutation: income, history top — sensible।
SHAP: per-customer — "income above 50K → +20% approval"।
Multiple lens, fuller picture।

Bangladesh fintech context:

NID, mobile number — high cardinality, MDI inflate।
Permutation reveal — actually no signal।
Important features — income, history, location।
Regulator-এ explanation — SHAP per-decision।

Production workflow:

(১) MDI — quick top-20।
(২) Permutation — validate top-10।
(৩) SHAP — final 5-7 narrative-এ include।
(৪) Domain expert review।

মূল উপলব্ধি: "Built-in" tools convenient, কিন্তু validate দরকার। Feature importance — multi-method analysis। Single number-এ trust করা — dangerous।

প্র ০৪ আপনি bKash-এর ২০ মিলিয়ন user-এ fraud detection model বানাচ্ছেন। Random Forest কেন প্রথম পছন্দ — এবং কখন insufficient?

Fraud detection — production ML-এর classic application। RF-এর strengths/weaknesses-এর textbook example।

RF-এর সুবিধা — fraud-এর জন্য:

(১) Feature heterogeneity handle:

Transaction amount (numerical), merchant category (categorical), time (cyclical), location (geographic)।
RF — সবই natural।
Pre-processing minimal।

(২) Non-linear pattern:

Fraud signature — interaction-heavy।
"Late night + new merchant + large amount" — interaction।
Tree natural fit।

(৩) Imbalanced data:

Fraud rare — ০.১%।
RF class_weight — accommodate।
Threshold tune — recall-precision tradeoff।

(৪) Missing data robustness:

Some users — incomplete profile।
RF — surrogate-like resilience।
Production-এ critical।

(৫) Speed:

২০ মিলিয়ন user — millions transactions/day।
RF prediction — milliseconds।
Real-time scoring।

(৬) Interpretability:

Bangladesh Bank — explanation চাইবে।
Customer dispute — reason show।
SHAP per-decision।

(৭) Concept drift adaptation:

Fraud pattern evolve।
Retrain quickly — RF training fast (parallel)।
Daily/weekly retrain feasible।

RF insufficient হয় যখন:

(১) Sequential pattern:

"Last ৫টি transaction-এ pattern" — RF memoryless।
Solution: feature engineering (rolling stats), LSTM।

(২) Network effects:

Fraud rings — connected accounts।
RF flat features দেখে।
Solution: Graph Neural Networks।

(৩) Adversarial evolution:

Fraudsters RF rules learn।
Game model।
Solution: anomaly detection + RF ensemble।

(৪) Cold start:

New user — no history।
RF features-এ default।
Solution: rule-based first ৩০ days, then ML।

(৫) Latency-critical:

৫০০ trees — ১-৫ms inference।
Sub-millisecond — XGBoost বা smaller RF।
Pruned ensemble।

(৬) High-dimensional textual:

Transaction description — text।
RF বদলে BERT + RF hybrid।

(৭) State-of-the-art fraud:

Adversarial deep learning attacks।
RF baseline, NN added।
Stacked ensemble।

Production architecture (recommended):

Layer 1 — rules: known patterns block।
Layer 2 — RF: primary classifier।
Layer 3 — XGBoost: close calls escalate।
Layer 4 — graph + NN: complex investigations।
Layer 5 — analyst: high-value disputed।

Deployment considerations:

Training pipeline: daily retraining।
Feature store: 200+ features online।
A/B test: shadow mode first।
Monitoring: drift, FPR, FNR dashboard।
Audit: monthly bias review।

Bangladesh-specific:

Mobile money — different pattern from card।
OTP fraud — phishing-driven।
Agent network fraud — geographic clustering।
Festival surge — model robust।
Regulatory: BB transaction monitoring guideline।

মূল উপলব্ধি: RF — fraud detection-এ excellent first model। Layered architecture — RF + specialized models — production-grade। Algorithm 30%, system 70% — successful deployment।

অনুশীলন

হিসাব করুন: $n = 1000$ samples-এ bootstrap। একটি sample bootstrap-এ থাকার probability কত? approximately not থাকার probability?
- একটি specific sample একবার selected হওয়ার probability $1/n = 0.001$।
- $n$ draws — না selected: $(1 - 1/n)^n \approx 1/e \approx 0.368$।
- তাই ~৬৩% bootstrap-এ থাকে, ~৩৭% থাকে না (OOB)।

sklearn: n_estimators [10, 50, 100, 500] — accuracy plot করুন।

for n in [10, 50, 100, 500]:
    rf = RandomForestClassifier(n_estimators=n, random_state=0, n_jobs=-1)
    print(n, cross_val_score(rf, X, y, cv=5).mean())
# 100-এর পর diminishing returns দেখা যাবে।

চিন্তা: দু'টি correlated features — কীভাবে RF importance শেয়ার করে? এই issue resolve করতে কী করবেন?

Two correlated features — importance প্রায় ৫০-৫০ split। Solutions: (১) feature selection আগে; (২) PCA-এ decorrelate; (৩) permutation importance — এক feature shuffle, drop measure; (৪) SHAP — context-aware।