Random Forests & Bagging

Average many trees over bootstrap resamples to cut variance.

The idea

Bagging and random forests improve a decision tree by averaging many of them. A deep tree fits its training set closely but is unstable: change a few points and the splits change, and the predictions with them. Averaging is the remedy: if $B$ estimates each have variance $\sigma^{2}$ and are uncorrelated, their average has variance $\sigma^{2}/B$, so averaging shrinks the error instability causes while leaving the trees' small bias alone.

There is only one training set, so bagging manufactures the $B$ fits by bootstrap resampling.

Algorithm.

Algorithm: Bagging Input: a training set of n labelled points, a number of trees B Output: an ensemble prediction rule 1. b = 1 // index of the current tree 2. draw a bootstrap resample: n points, with replacement, from the n training points 3. fit a decision tree to the resample and store it 4. if b < B, set b = b + 1 and go to step 2 5. to predict at a new point: run it through all B stored trees, return the average prediction // classification: the label with the most votes

Each resample leaves some points out, and those out-of-bag points score the tree that never saw them, at no extra cost.

Resamples of one dataset overlap heavily, so the trees are correlated, and correlation limits what averaging can do. For $B$ trees of variance $\sigma^{2}$ with pairwise correlation $\rho$, the average has variance $\rho\,\sigma^{2} + \frac{1 - \rho}{B}\,\sigma^{2},$ where the second term vanishes as $B$ grows and the first does not. A random forest lowers that floor by changing how step 3 fits each tree: at each split the tree may choose only among a random subset of the features, so a few strong features cannot lead every tree, and $\rho$ falls.

Ways to work on it

Not sure where to start? Take the ten-question placement test.