How a forest votes
Breiman defined a random forest as a collection of tree classifiers, each grown from an independently sampled random vector drawn with the same distribution for every tree in the forest, with each tree casting one vote for the most popular class at a given input. [2]
The version he tested combines two sources of randomness. Each tree trains on a bootstrap resample of the training set, drawn with replacement, the same procedure Breiman had earlier called bagging. Within that, at every node, the tree considers only a small randomly chosen group of input variables when picking the split, rather than searching all of them. Trees are grown to full size with no pruning. He called this simplest version Forest-RI, and tried group sizes as small as a single random variable per node. [2]
Atlas interpretation: The paper's own accuracy bound (Theorem 2.3) is stated in terms of two competing quantities: how strong the individual trees are and how correlated they are with each other. Restricting each split to a random handful of variables is a way to buy down that correlation deliberately, at some cost to any single tree's strength, on the bet that the forest as a whole comes out ahead. [2]
The forest grades itself while it grows
Because each tree is trained on a bootstrap sample, roughly a third of the training instances are left out of any given tree. Breiman used those left-out cases as a built-in test set: for each training instance, only the trees that never saw it vote, and the error rate of that vote is the out-of-bag estimate. He reported that this estimate is as accurate as using a held-out test set of the same size, which removes the need to set data aside for validation at all. [2]
Theorem 1.2 shows, by the strong law of large numbers, that as the number of trees grows, the forest's generalization error converges almost surely to a fixed limit rather than continuing to drift. Breiman states this directly as the reason random forests do not overfit as more trees are added. [2]
Atlas interpretation: Put together, those two results are what let the method get away with almost no tuning. There is no separate validation split to manage and no point at which adding trees can make the forest worse, only a point past which more trees stop helping. The only real decision left is how many variables to consider at each split, and the paper found the results insensitive to that choice. [2]
How it stacked up against Adaboost
Breiman ran Forest-RI against Adaboost on thirteen data sets from the UCI repository, holding out ten percent of each smaller set for testing over one hundred repeated splits. On the results table, random forest error was sometimes lower and sometimes higher than Adaboost's: 20.6 versus 22.0 percent on glass, 3.4 versus 4.1 percent on vowel, 7.1 versus 6.4 percent on ionosphere, 24.4 versus 23.5 percent on German credit. Averaged across the data sets he tested, the gap between the two methods was small, and he described random forest accuracy as comparing favorably with Adaboost. [2]
The paper also measured training speed on the zip-code digit data set: growing a Forest-RI with a single random variable per split took about 4 minutes on a 250MHz Macintosh, against nearly three hours for Adaboost on the same machine, a roughly 40-fold difference Breiman attributed to each tree only ever searching one variable instead of all of them. [2]
Atlas interpretation: Adaboost builds its ensemble one tree at a time, each one reweighted based on where the previous trees erred, which is a sequential dependency that random forests do not have. Every tree in a forest can be grown independently of every other, on its own bootstrap sample and its own random split choices, which is what made the method both fast on 2001 hardware and simple to parallelize. Comparable accuracy without that sequential bottleneck is a large part of why it became the thing to try first rather than a curiosity to try after boosting. [2]
Where deep learning did not follow
Breiman motivated the random-features approach with problems like medical diagnosis and document retrieval, where there are hundreds or thousands of input variables and any single one carries only a small amount of information, so that a lone tree classifies barely better than chance while combining many trees grown on random subsets of those variables recovers useful accuracy. [2]
AlexNet won the 2012 ImageNet competition with error rates the authors called considerably better than the previous state of the art, which had relied on hand-engineered image features paired with a conventional classifier. A deep convolutional network learned its own features directly from raw pixels instead. [3]
Atlas interpretation: That win reordered image and speech recognition around learned representations within a decade of Breiman's paper, but it did not touch the kind of problem the random forest paper was built for: a table of columns that are numeric, categorical, sparse, and unrelated to each other by any shared geometry. A convolutional network gets its advantage from structure a grid of pixels has and a spreadsheet does not, which is a narrow claim about where each method's assumptions hold rather than a verdict that one method is generally stronger than the other. [2][3]
Sources
- Random Forests
Machine Learning · Oct 2001
- Random Forests
UC Berkeley Department of Statistics · Oct 2001
- ImageNet Classification with Deep Convolutional Neural Networks
Advances in Neural Information Processing Systems 25 (NeurIPS 2012) · Dec 3, 2012