Ensembles I: Bagging & Random Forests

Every tree here is grown to the same reckless max depth as Chapter 8's worst offender — each one individually overfits. But each is trained on a different random resample of the data, so each one overfits differently. Add more of them and watch the jagged, noise-chasing regions smooth out into the one boundary they all actually agree on.

This is bagging — bootstrap aggregating. Train $N$ trees, each on a random sample drawn with replacement from the training set (a "bootstrap sample"), then combine their predictions by majority vote:

• $\hat{y}(x)$ — the ensemble's final prediction for input $x$.
• $T_i(x)$ — the prediction of the $i$-th tree in the forest.
• $N$ — the number of trees in the ensemble.
• majority — the vote rule: whichever label the most trees predicted wins.

1. Each tree still overfits, but differently

   Each $T_i$ still overfits its own bootstrap sample. But the noise it overfits to is specific to which points that resample happened to include — different resamples chase different noise, so it rarely lines up.

2. Random forests also subsample features

   A random forest adds one more trick on top: at every split, each tree only gets to consider a random subset of the available features.

3. Not in play with a single feature

   With just one feature here, that trick has nothing to act on — bagging alone is already the whole story.

Watch training accuracy stay roughly flat while validation accuracy climbs as trees are added. No single tree in the forest got any less overfit — the ensemble generalizes better anyway, purely because their individual mistakes don't overlap.

At $x = 14.25$ (true label B):

1. Vote with the first three trees

   B, A, A — majority vote says A, wrong.

2. Add two more trees

   Predicting B and B, the vote among all five becomes B, A, A, B, B — majority B, correct.

3. Notice what actually changed

   No tree changed its mind; two more independent (wrong-in-different-ways) opinions were enough to outvote the two that agreed on the mistake.