Random Forests - 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. 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.

2 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. 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.

3 Then CBrf(x)=majority vote{ Cb(x)} in the data, and if grown sufficiently deep, have relatively lowbias. 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.( )AsBincreases, the second term disappears, but the first remains, andhence the size of the correlation of pairs of bagged trees limits the benefitsof averaging.

4 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).( )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.

5 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).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.

6 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. 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.

7 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. 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].

8 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 ).Two strong features that emerge are Random Forests stabilize at about 200 trees, while at 1000 trees boost-ing continues to improve. Boosting is slowed down by the shrinkage,as well as the fact that the trees are much smaller. Boosting outperforms Random Forests here. At 1000 terms, the weakerboosting model (GBM depth 4) has a smaller error than the stronger3 Details: The Random Forests were fit using the R packagerandomForest ,with 500 trees. The gradient boosting models were fit using R packagegbm ,withshrinkage parameter set to , and 2000 Random of TreesMisclassification ErrorOOB ErrorTest ErrorFIGURE computed on thespamtraining data, compared to thetest error computed on the test forest (RFm= 6); a Wilcoxon test on the mean differencesin absolute errors has a p-value of For largermthe randomforests performed no Details of Random ForestsWe have glossed over the distinction between Random Forests for classifica-tion versus regression.

9 When used for classification, a Random forest obtainsa class vote from each tree, and then classifies using majority vote (see Sec-tion on bagging for a similar discussion). When used for regression, thepredictions from each tree at a target pointxare simply averaged, as in( ). In addition, the inventors make the following recommendations: For classification, the default value formis$ p%and the minimumnode size is one. For regression, the default value formis$p/3%and the minimumnode size is practice the best values for these parameters will depend on the problem,and they should be treated as tuning parameters. In Figure them=6performs much better than the default value$8/3%= Out of Bag SamplesAn important feature of Random Forests is its use ofout-of-bag(oob)sam- Details of Random Forests 593 For each observationzi=(xi,yi),constructitsrandom forestpredictor by averagingonlythose trees corresponding to boot-strap samples in whichzidid estimate is almost identical to that obtained byN-fold cross-validation; see Exercise Hence unlike many other nonlinear estimators, Random Forests can be fit in one sequence, with cross-validation being per-formed along the way.

10 Once theooberror stabilizes, the training can shows theoobmisclassification error for thespamdata, com-pared to the test error. Although 2500 trees are averaged here, it appearsfrom the plot that about 200 would be Variable ImportanceVariable importance plots can be constructed for Random Forests in exactlythe same way as they were for gradient-boosted models (Section ).At each split in each tree, the improvement in the split-criterion is theimportance measure attributed to the splitting variable, and is accumulatedover all the trees in the forest separately for each variable. The left plotof Figure shows the variable importances computed in this way forthespamdata; compare with the corresponding Figure on page 354 forgradient boosting. Boosting ignores some variables completely, while therandom forest does not. The candidate split-variable selection increasesthe chance that any single variable gets included in a Random forest , whileno such selection occurs with Forests also use theoobsamples to construct a differentvariable-importancemeasure, apparently to measure the prediction strength of eachvariable.