Random Forests & Bagging

A single decision tree is a fast, honest learner with one fatal flaw: it is high variance. Grow it deep enough to separate the classes and it memorises the noise, so a tiny change in the training data reshuffles the whole boundary. In the last lesson we watched that instability show up as a jagged, overfit staircase.

This lesson is about the fix, and it is one of the most reliable ideas in all of machine learning: do not trust one model, average many. We will build up to the Random Forest in three moves. First, the reason averaging works at all (Condorcet's Jury Theorem and the variance of an average). Second, how to manufacture many different trees from one dataset (bagging and the bootstrap). Third, the one extra trick that turns good bagging into a great forest (random feature subsets, which decorrelate the trees).

1. The ensemble idea: wisdom of crowds

Condorcet's Jury Theorem

In 1785 the Marquis de Condorcet asked a question about voting that turns out to be exactly the question behind ensembles. (The name is Condorcet, not "Concord.") Suppose a jury of $N$ people each decides a yes/no question independently, and each juror is correct with probability $p$. The jury rules by majority vote. How often is the majority right?

The majority is correct whenever more than half the jurors are correct, so we sum the binomial probabilities from a strict majority up to all $N$:

The theorem states the striking consequence:

Read that carefully. Every juror can be barely better than a coin flip, say $p = 0.55$, and yet a large enough jury is right almost every single time. The individual is mediocre; the crowd is nearly infallible. That is the entire promise of an ensemble: replace each juror with a weak classifier, replace the majority vote with a vote across models, and mediocre learners combine into a strong one.

The two conditions are non-negotiable and worth stamping into memory:

• Better than chance ($p > 0.5$). If jurors are worse than a coin, the same math drives the majority toward being reliably wrong. A crowd amplifies whatever the members are on average.
• Independence. The clean climb toward certainty assumes the jurors err independently. If everyone makes the same mistakes, adding jurors adds nothing. Hold on to this word, because decorrelation is where Random Forests earn their name.

Slide $p$ and the jury size $N$ below. Watch the majority accuracy climb toward 1 the moment $p$ crosses one half, and collapse toward 0 when it does not.

From jurors to a variance calculation

Condorcet is the intuition. For a regression ensemble (averaging numbers rather than voting on labels) there is an even sharper statement, and it names the villain directly. Suppose we average $B$ trees, each an unbiased predictor with variance $\sigma^2$, and suppose every pair of trees has correlation $\rho$. The variance of their average is:

This one line is the whole theory of bagging. Look at what each term does as we add more trees:

• The second term, $\dfrac{1-\rho}{B}\,\sigma^2$, is divided by $B$. Averaging more trees drives it to zero. This is the free lunch: pile on trees and this part of the variance melts away.
• The first term, $\rho\,\sigma^2$, has no $B$ in it. No amount of averaging can push it below $\rho\sigma^2$. It is a floor, set entirely by how correlated the trees are.

So the equation splits our job in two. Averaging many trees kills the $\dfrac{1-\rho}{B}$ term for free. But to break through the floor we must shrink $\rho$ itself, and that is a modelling decision, not a matter of adding more trees. Bagging attacks the second term; the random-feature trick attacks the first. Keep this decomposition in view for the rest of the lesson.

2. Bagging: bootstrap aggregation

To average trees we need different trees, and to get different trees we need different training sets. But we only have one dataset. Bagging (short for bootstrap aggregating, coined by Leo Breiman in 1996) manufactures the variety with a resampling trick.

The recipe is disarmingly simple:

1. From the training set of $N$ points, draw a bootstrap sample: $N$ points sampled uniformly with replacement. Some points appear twice or more, others not at all.
2. Train one tree on that sample, grown deep with no pruning.
3. Repeat $B$ times to get $B$ trees, each shaped by a slightly different slice of the data.
4. To predict, average their outputs (regression) or take a majority vote (classification).

Each tree still overfits its own bootstrap sample, so each is individually high-variance. But because their errors point in different directions, the average is far steadier than any one of them. That is the $\dfrac{1-\rho}{B}$ term at work. Bagging lowers variance without raising bias, which is precisely the medicine a lone decision tree needs.

Bootstrap sampling and the out-of-bag set

The bootstrap hands us an unexpected gift. When you sample $N$ points with replacement, what fraction of the original points get left out entirely?

For a single draw, one specific point is not chosen with probability $1 - \tfrac{1}{N}$. The $N$ draws are independent, so the point is missed by all of them with probability:

That limit is one of the cleanest appearances of $e$ in all of statistics. It means that for a reasonably sized dataset, each bootstrap sample contains about 63.2% of the unique points, and leaves roughly 36.8% untouched. Those left-out points are called the tree's out-of-bag (OOB) set.

Here is why that matters: for any given data point, roughly a third of the trees never saw it during training. We can score each point using only the trees that did not train on it, then average those errors across all points. The result, the out-of-bag score, is an honest held-out estimate of generalisation performance, computed for free, with no separate validation split. Bagging comes with its own built-in cross-validation.

Draw bootstrap samples below. Watch duplicates swell and out-of-bag points fall out with dashed rings, watch the averaged (bagged) prediction settle onto the true signal as $B$ grows, and watch the OOB fraction hover near 37%.

3. Random Forests: bagging plus random features

Bagging alone leaves money on the table, and the variance equation told us exactly where. We are driving down the $\dfrac{1-\rho}{B}$ term by adding trees, but we are still stuck above the $\rho\,\sigma^2$ floor. So how correlated are bagged trees, really?

Very. If one feature is a strong predictor, then every tree, on every bootstrap sample, tends to pick that same feature for its first split. The trees end up looking alike near the top, their errors line up, and $\rho$ stays stubbornly high. Bagging changed the data each tree sees, but not the greedy way each tree chooses its splits.

Breiman's 2001 Random Forest adds one deliberately disruptive rule:

At each split, do not consider all features. Draw a fresh random subset of the features (a common default is $\sqrt{p}$ of the $p$ features for classification) and choose the best split only among those.

This looks almost sabotaging. We are hiding the best feature from most splits on purpose. But that is the point. By forcing different trees to split on different features, we stop them from all latching onto the same dominant predictor. Their structures diverge, their errors stop agreeing, and $\rho$ drops. Lowering $\rho$ lowers the $\rho\,\sigma^2$ floor, so the whole ensemble variance falls below what plain bagging could ever reach. This is decorrelation, and it is the single idea that separates a Random Forest from ordinary bagged trees.

The price is a small rise in each individual tree's bias (a tree denied its best feature is a bit weaker on its own). The trade is overwhelmingly worth it: a little more bias per tree in exchange for a much lower variance floor across the ensemble.

Put the two boundaries side by side below. On the left, one deep tree carves a jagged, noise-chasing staircase (high variance, 0% training error, brittle). On the right, grow the forest tree by tree and watch the averaged vote melt into a smooth, stable boundary that ignores the noise.

Notice what stayed the same and what changed. Every tree in that forest is still a greedy, overfitting decision tree. We did not make the base learner smarter. We made the base learners disagree in useful ways, then averaged the disagreement away.

4. Build it yourself

Time to make it real. The playground below builds a small tabular dataset with 3 genuinely informative features and 3 pure-noise features, then pits a single deep DecisionTreeClassifier against a RandomForestClassifier. It prints both test accuracies, prints the forest's oob_score_ (the free held-out estimate we derived above), and draws the forest's feature_importances_ as a bar chart.

Run it, then read the three signals it exposes: the forest beats the lone tree on test accuracy, the OOB score lands close to the true test accuracy without ever touching the test set, and the importance bars light up the 3 real features while the noise features sit near zero.

Now make it yours. Set n_estimators=1 and the forest collapses back toward a single noisy tree, its OOB estimate wobbling. Crank it to 300 and both the accuracy and the OOB score steady out (the $\dfrac{1-\rho}{B}$ term shrinking before your eyes). Push flip_y to 0.3 to flood the labels with noise and watch the single tree's test accuracy crater while the forest degrades gracefully. Break it, then fix it.

Interview readiness