Random Forest - Mathematics and Statistics

1 This is page 587 Printer: Opaque IntroductionBagging orbootstrap aggregation(section ) is a technique for reducingthe variance of an estimated prediction function. Bagging seems to workespecially well for high-variance, low-bias procedures, such as trees. Forregression, we simply fit the same regression tree many times to bootstrap-sampled versions of the training data, and average the result. For classifi-cation, acommitteeof trees each cast a vote for the predicted in Chapter 10 was initially proposed as a committee method aswell, although unlike bagging, the committee ofweak learnersevolves overtime, and the members cast a weighted vote.

2 Boosting appears to dominatebagging on most problems, and became the preferred forests(Breiman, 2001) is a substantial modification of baggingthat builds a large collection ofde-correlatedtrees, and then averages many problems the performance of Random forests is very similar toboosting, and they are simpler to train and tune. As a consequence, randomforests are popular, and are implemented in a variety of Definition of Random ForestsThe essential idea in bagging (Section ) is to average many noisy butapproximately unbiased models, and hence reduce the variance. Trees areideal candidates for bagging, since they can capture complex interaction58815.

3 Random ForestsAlgorithm Forest for Regression or Forb=1toB:(a) Draw a bootstrap sampleZ of sizeNfrom the training data.(b) Grow a Random - Forest treeTbto the bootstrapped data, by re-cursively repeating the following steps for each terminal node ofthe tree, until the minimum node sizenminis Selectmvariables at Random from Pick the best variable/split-point among Split the node into two daughter Output the ensemble of trees{Tb} make a prediction at a new pointx:Regression: fBrf(x)=1B Bb=1Tb(x).Classification:Let Cb(x) be the class prediction of thebth Random -foresttree. Then CBrf(x)=majority vote{ Cb(x)} in the data, and if grown sufficiently deep, have relatively lowbias.

4 Since trees are notoriously noisy, they benefit greatly from the averag-ing. Moreover, since each tree generated in bagging is identically distributed( ), the expectation of an average ofBsuch trees is the same as the ex-pectation of any one of them. This means the bias of bagged trees is thesame as that of the individual trees, and the only hope of improvement isthrough variance reduction. This is in contrast to boosting, where the treesare grown in an adaptive way to remove bias, and hence are not average Random variables, each with variance 2, has vari-ance1B 2. If the variables are simply (identically distributed, but notnecessarily independent) with positive pairwise correlation , the varianceof the average is (Exercise ) 2+1 B 2.

5 ( )AsBincreases, the second term disappears, but the first remains, andhence the size of the correlation of pairs of bagged trees limits the benefitsof averaging. The idea in Random forests (Algorithm ) is to improvethe variance reduction of bagging by reducing the correlation between thetrees, without increasing the variance too much. This is achieved in thetree-growing process through Random selection of the input , when growing a tree on a bootstrapped dataset:Before each split, selectm pof the input variables at randomas candidates for Definition of Random Forests 589 Typically values formare por even as low as trees{T(x; b)}B1are grown, the Random Forest (regression)predictor is fBrf(x)=1BB b=1T(x; b).

6 ( )As in Section (page 356), bcharacterizes thebth Random Forest tree interms of split variables, cutpoints at each node, and terminal-node , reducingmwill reduce the correlation between any pair of treesin the ensemble, and hence by ( ) reduce the variance of the DataNumber of TreesTest ErrorBaggingRandom ForestGradient Boosting (5 Node)FIGURE , Random Forest , and gradient boosting, applied to thespam data. For boosting,5-node trees were used, and the number of trees werechosen by10-fold cross-validation (2500trees). Each step in the figure corre-sponds to a change in a single misclassification (in a test set of1536).

7 Not all estimators can be improved by shaking up the data like seems that highly nonlinear estimators, such as trees, benefit the bootstrapped trees, is typically small ( or lower is typical; seeFigure ), while 2is not much larger than the variance for the originaltree. On the other hand, bagging does not changelinearestimates, suchas the sample mean (hence its variance either); the pairwise correlationbetween bootstrapped means is about 50% (Exercise ).59015. Random ForestsRandom forests are popular. Leo Breiman s1collaborator Adele Cutlermaintains a Random Forest website2where the software is freely available,with more than 3000 downloads reported by 2002.

8 There is arandomForestpackage in R, maintained by Andy Liaw, available from authors make grand claims about the success of Random forests: most accurate, most interpretable, and the like. In our experience ran-dom forests do remarkably well, with very little tuning required. A ran-dom Forest classifier achieves misclassification error on thespamtestdata, which compares well with all other methods, and is not significantlyworse than gradient boosting at Bagging achieves which issignificantly worse than either (using the McNemar test outlined in Ex-ercise ), so it appears on this example the additional 1RF 3 BaggingGBM 1 GBM SpheresTest Misclassification ErrorBayes ErrorFIGURE results of50simulations from the nested spheres model inIR10.

9 The Bayes decision boundary is the surface of a sphere (additive). RF-3 refers to a Random Forest withm=3, and GBM-6 a gradient boosted modelwith interaction order six; similarly for RF-1 and GBM-1. The training setswere of size2000, and the test sets10, shows the test-error progression on 2500 trees for the threemethods. In this case there is some evidence that gradient boosting hasstarted to overfit, although 10-fold cross-validation chose all 2500 , Leo Breiman died in July, adele/ Definition of Random Forests Housing DataNumber of TreesTest Average Absolute ErrorRF m=2RF m=6 GBM depth=4 GBM depth=6 FIGURE forests compared to gradient boosting on the Californiahousing data.

10 The curves represent mean absolute error on the test data as afunction of the number of trees in the models. Two Random forestsare shown, withm=2andm=6. The two gradient boosted models use a shrinkage parameter = ( ), and have interaction depths Random shows the results of a simulation3comparing Random foreststo gradient boosting on thenested spheresproblem [Equation ( ) inChapter 10]. Boosting easily outperforms Random forests here. Notice thatsmallermis better here, although part of the reason could be that the truedecision boundary is compares Random forests to boosting (with shrinkage) in aregression problem, using the California housing data (Section ).