Ensembles & Boosting

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

One tree, all the data
Vote of 25 trees
One tree of the crowd

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

Peek inside: look at 3 different trees of the crowd.
Teamwork: use 25 or more trees and have the vote beat the single tree by at least 2 points.
Free exam: with 30 or more trees, get the out-of-bag score within 4 points of the fresh-dots score.
Too simple: set the depth to 1 (one cut per tree) with 40+ trees. The vote cannot bend around the curves.

What just happened?

How it works

  1. Draw a bootstrap sample: pick as many dots as the data has, at random, with repeats.
  2. Grow a decision tree on that sample.
  3. Repeat for every tree.
  4. To classify a new dot, every tree votes and the majority wins.
  5. 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.