Bagging

Bagging

1. Algorithm (Bootstrap Aggregating)

for m=1..M: sample n points with replacement → train tree f_{m} (deep, unpruned)
predict: average (regression) or vote (classification)

Each bootstrap misses ~37% points (out-of-bag) — free validation set.

2. Random Forest = Bagging + Feature Randomness

At each split, try only random subset ($m ≈ \sqrt{d}$) of features. Decorrelates trees → more variance reduction. Default: 200-500 deep trees.

3. Properties

• Reduces variance, keeps bias (deep trees = low bias).
• Handles mixed data, missing values, no scaling needed.
• OOB error ≈ CV — no separate validation needed.
• Feature importance from impurity drop / permutation.

4. Worked

Single tree: 78% ± 5%. 200-tree forest: 85% ± 1.5% — same bias, much lower spread.

5. Exam Points

• Bagging steps + OOB — 5-7 marks, very frequent.
• Random Forest extra randomness — 3-5 marks, frequent.
• Why deep trees + average — 3 marks, frequent.