Random Forest
Introduction
A Random Forest is an ensemble of decision trees. A single decision tree is easy to understand but notoriously high-variance: grow it deep enough and it will memorize the training set, carving out jagged regions around individual noisy points. A Random Forest fixes this by training many trees on slightly different versions of the data and letting them vote. The trees individually overfit, but because their errors are largely uncorrelated, averaging cancels out the noise and leaves a smooth, robust decision boundary.
Two sources of randomness make the trees disagree in useful ways: each tree sees a bootstrap sample of the rows, and at every split it may only choose from a random subset of the features. That second ingredient is what separates a Random Forest from plain “bagged trees.”
One-line intuition: averaging many decorrelated, over-fit trees keeps the (low) bias of a deep tree while slashing its (high) variance.
Ingredient 1 — Bagging (bootstrap aggregating)
Bagging = bootstrap aggregating. From a training set of n rows we draw a bootstrap sample: n rows sampled with replacement. Some rows appear several times, others not at all. We build one tree per bootstrap sample, then aggregate their predictions — majority vote for classification, average for regression.
Why does this help? If we average B independent predictors each with variance σ², the variance of the mean is σ²/B. Trees are not perfectly independent, so the real reduction is smaller, but the direction is the same: averaging reduces variance. Crucially it barely touches bias — the average of many low-bias trees is still low-bias.
With n large, the probability a given row is left out of a size-n bootstrap sample is (1 − 1/n)ⁿ → 1/e ≈ 0.368. So each tree naturally ignores about 37% of the data — those rows are “out-of-bag” for that tree (more on this below).
Ingredient 2 — Random feature subsets at each split
Here is the twist that makes a forest random. With plain bagging, every tree still uses a greedy split search over all features. If one feature is very strong, almost every tree splits on it first, so the trees end up highly correlated — and correlated predictors do not average away well.
Random Forest fixes this by, at every split, restricting the candidate features to a fresh random subset of size m (often m = √p for classification or m = p/3 for regression, where p is the total number of features). The tree must sometimes split on a weaker feature, forcing different trees down different structures. This decorrelates the trees so the averaging actually pays off.
If the variance of one tree is σ² and the pairwise correlation between trees is ρ, the variance of the average of B trees is ρσ² + (1 − ρ)σ²/B. Adding trees drives the second term to zero, but the floor ρσ² remains — so lowering ρ (decorrelating trees) is exactly the job of feature subsampling.
Interactive demo — one tree vs a forest
The points below form an XOR-style pattern (red and blue swap across the diagonals), plus a little label noise. The left plot shows a single tree trained on one bootstrap sample. The right plot shows the averaged vote of the whole forest. Drag the sliders and watch the boundary change. Set trees = 1 and the two plots match; raise it and the right side smooths out. Toggle the feature-subset checkbox off to see a forest degrade toward plain (more correlated) bagging.
Set to 1 and the right plot equals the left. Increase it and the boundary settles down.
Deeper trees overfit more individually — but averaging tames them.
Fraction of rows drawn (with replacement) for each tree.
Everything here is computed in your browser: real Gini-impurity greedy trees, real bootstrap samples, real per-split feature subsetting, and a genuine out-of-bag accuracy estimate.
Out-of-bag (OOB) error
Because each tree leaves out ~37% of the rows, the forest gets a free validation set. To compute the OOB prediction for a row, we let only the trees that did not train on that row vote on it. Comparing those predictions to the true labels gives the OOB error — an honest, nearly unbiased estimate of generalization performance, with no separate hold-out split or k-fold cross-validation needed.
OOB error tracks test error closely and is essentially free to compute. It is a standard way to tune a Random Forest (e.g. choosing m or the number of trees) without spending data on a validation set. In the demo above, the “OOB accuracy” number is computed exactly this way.
Feature importance
A forest can also tell you which features matter. Two common measures:
- Mean decrease in impurity (Gini importance): add up the impurity reduction every time a feature is used to split, averaged over all trees. Fast, but biased toward high-cardinality / continuous features.
- Permutation importance: randomly shuffle one feature's values and measure how much OOB accuracy drops. More reliable, but slower to compute and can be misled by correlated features.
Illustrative Gini-importance scores (summing to ~1) for a forest on the classic Iris dataset: the two petal features dominate.
Why a forest beats a single deep tree
| Property | Single deep tree | Random Forest |
|---|---|---|
| Bias | Low | Low (similar to a single tree) |
| Variance | High (overfits) | Much lower (averaging cancels noise) |
| Decision boundary | Jagged, follows noise | Smooth, robust |
| Validation | Needs a hold-out / CV | Free OOB estimate |
| Interpretability | Fully readable rules | Less so, but gives feature importances |
Random Forest vs plain bagged trees
Plain bagged trees
- • Each tree on a bootstrap sample of rows
- • Every split searches over ALL features
- • Strong features dominate → trees correlated
- • Variance reduction is limited by that correlation
Random Forest
- • Each tree on a bootstrap sample of rows
- • Every split searches over a random subset of m features
- • Trees forced to differ → decorrelated
- • Larger, more reliable variance reduction
Common misconception: “Random Forest is just bagging applied to trees.” Not quite — the defining extra is the random feature subset chosen afresh at every split. Set m = p (all features) and a Random Forest collapses back into ordinary bagged trees.
Practical notes & pitfalls
- More trees never hurt accuracy — they just cost compute and eventually plateau. There is no overfitting from adding trees (unlike boosting). Pick enough that OOB error stabilizes.
- Let individual trees grow deep. The ensemble controls variance, so under-pruned, low-bias trees are usually fine and even preferred.
- Tune m (features per split) — it is the main knob trading off tree strength against correlation.
- Forests do not extrapolate. Predictions are piecewise constant, so they cannot predict trends beyond the range of the training data (a limitation shared with single trees).
- Gini importance can mislead with correlated or high-cardinality features; prefer permutation importance when it matters.
Key Takeaways
- A Random Forest averages many decision trees to turn one high-variance model into a low-variance ensemble without raising bias.
- Bagging trains each tree on a bootstrap sample (rows drawn with replacement); aggregating their votes reduces variance.
- The defining extra over plain bagging is choosing a random subset of features at each split, which decorrelates the trees so averaging helps more.
- Variance of the ensemble is ρσ² + (1 − ρ)σ²/B; adding trees kills the second term, while feature subsampling lowers ρ.
- Out-of-bag rows (~37% per tree) give a free, nearly unbiased generalization estimate — no separate validation set needed.
- Forests report feature importance (Gini or permutation) but are less directly interpretable than a single tree.