Bagging & Random Forest

Bagging (Bootstrap Aggregating) is a parallel ensemble: for $k$ base learners, draw $n$ samples with replacement from the training set (bootstrap) and train each learner on its own bag; predict by voting (classification) or averaging (regression). Key probability: a given sample is never drawn in $n$ draws with probability $\left(1 - \frac{1}{n}\right)^n \to e^{-1} \approx 0.368$, so each bag contains only ~63.2% of the original samples on average and the remaining ~36.8% (≈ 1/3) are Out-of-Bag (OOB) samples unseen by that learner — evaluating on them gives the OOB error, an unbiased estimate without a separate validation set. Variance analysis: for base learners with variance $\sigma^2$ and pairwise correlation $\rho$, the averaged model has variance $\text{Var}\left(\bar{f}\right) = \rho \sigma^2 + \frac{1 - \rho}{k} \sigma^2$ — the first term survives as $k \to \infty$, so the real lever of bagging is reducing $\rho$, not just increasing $k$. Random Forest adds feature randomness: at each split, sample $m \approx \sqrt{d}$ features out of $d$ (regression: ~$d/3$) and pick the best split among them — the double randomness (samples + features) lowers $\rho$ substantially. From the bias-variance decomposition $\text{Err} = \text{bias}^2 + \text{variance} + \sigma_\epsilon^2$: averaging does not change bias, only variance, so bagging suits strong low-bias high-variance base learners (deep, unpruned trees).

why random forests beat single deep trees, what OOB error is, how $m$ is chosen, and why random forests parallelize — all are frequent interview topics; RF is also a strong baseline for tabular data, natively providing feature importance (mean split gain).

single deep trees have large variance and overfit — bootstrap resampling creates data perturbation so base learners differ (without replacement, the bags would be too similar, $\rho \to 1$, and averaging would barely reduce variance); in pure bagging strong features dominate every split so trees stay highly correlated, and feature-subset randomization (small $m$ → small $\rho$) drops variance from the $\sigma^2$ level to the $\rho \sigma^2$ level — the key reason RF beats plain bagging; OOB makes evaluation isomorphic to training at zero extra data cost, and every tree trains fully in parallel.

Bootstrap derivation: probability a sample is never drawn is $(1 - \frac{1}{n})^n \to e^{-1} \approx 0.368$; how is OOB error computed and why does it need no separate validation set?

Variance decomposition: $\text{Var}(\bar{f}) = \rho \sigma^2 + \frac{1-\rho}{k} \sigma^2$ — why does bagging reduce variance but not bias? Why is variance not zero as $k \to \infty$?

RF double randomness: bootstrap samples + random feature subsets ($m = \sqrt{d}$ classification / $d/3$ regression); why is feature randomness the key ingredient?

Why must bagging base learners be strong (deep, unpruned)? What happens if they are shallow?

OOB error vs K-Fold CV error: pros and cons; how does RF use OOB to compute feature importance?