Vote of Many Trees
One tree memorises every wrong label. Many trees, each shown a shuffled copy of the data, vote and cancel out each other’s quirks.
Orange and purple dots, but some labels are wrong on purpose. The left map is one tree. The middle map is a crowd of trees voting. Slide number of trees up!
Decision maps
Colours are what the model would say for a dot placed there (orange or purple, paler when the vote is close). Right map: big dots were picked more than once, hollow dots were left out of that tree's shuffled copy.
Challenges
What just happened?
- Each tree got its own shuffled copy of the data (bootstrap: draw dots at random with repeats), so each tree saw a slightly different puzzle.
- Every tree memorised its own copy, noise and all, but they memorised different mistakes.
- When the trees vote, the odd mistakes get outvoted and the smooth pattern stays.
- Each tree never saw about a third of the dots. Testing the tree on those left-out dots gives a free honest score, called out-of-bag.
How it works
- Draw a bootstrap sample: pick as many dots as the data has, at random, with repeats.
- Grow a decision tree on that sample.
- Repeat for every tree.
- To classify a new dot, every tree votes and the majority wins.
- To score the training data honestly, each dot is judged only by the trees that never saw it.
For grown-ups: what's really going on
This is bagging (bootstrap aggregating, Breiman 1996). Each tree is a CART tree grown with weighted Gini impurity 1 − Σ pk² on a bootstrap sample; a sample of size n leaves out each row with probability (1 − 1/n)n ≈ 36.8%.
- Deep trees have low bias but high variance: they chase label noise. Averaging B roughly independent trees divides the variance part by about B, so the vote is smoother and generalises better.
- The trees are not fully independent, since they share the same data, so gains flatten after a few dozen trees.
- Out-of-bag (OOB) error is a nearly free estimate of test error: each row is scored by only the trees whose bootstrap sample missed it. Here it is measured against the noisy labels, just like the fresh dots.
- Shallow stumps have high bias. Voting many does not fix that, because averaging cuts variance, not bias. Random forests add a random choice of features at each split to decorrelate the trees further; with only two features here, this is plain bagging.
Data: two interleaved half-moons in the unit square with Gaussian jitter; a chosen fraction of labels is flipped. 120 training dots, 400 fresh dots, seeded.