3
1.2 Outline of Paper
Section 2 gives some theoretical background for random forests. Use of the
Strong Law of Large Numbers shows that they always converge so that
overfitting is not a problem. We give a simplified and extended version of
the Amit and Geman [1997] analysis to show that the accuracy of a random
forest depends on the strength of the individual tree classifiers and a measure
of the dependence between them (see Section 2 for definitions).
Section 3 introduces forests using the random selection of features at each
node to determine the split. An important question is how many features
to select at each node. For guidance, internal estimates of the generalization
error, classifier strength and dependence are computed. These are called out-
of-bag estimates and are reviewed in Section 4. Sections 5 and 6 give
empirical results for two different forms of random features. The first uses
random selection from the original inputs; the second uses random linear
combinations of inputs. The results compare favorably to Adaboost.
The results turn out to be insensitive to the number of features selected to
split each node. Usually, selecting one or two features gives near optimum
results. To explore this and relate it to strength and correlation, an empirical
study is carried out in Section 7.
Adaboost has no random elements and grows an ensemble of trees by
successive reweightings of the training set where the current weights depend
on the past history of the ensemble formation. But just as a deterministic
random number generator can give a good imitation of randomness, my
belief is that in its later stages Adaboost is emulating a random forest.
Evidence for this conjecture is given in Section 8.
Important recent problems, i.e.. medical diagnosis and document retrieval ,
often have the property that there are many input variables, often in the
hundreds or thousands, with each one containing only a small amount of
information. A single tree classifier will then have accuracy only slightly
better than a random choice of class. But combining trees grown using
random features can produce improved accuracy. In Section 9 we experiment
on a simulated data set with 1,000 input variables, 1,000 examples in the
training set and a 4,000 example test set. Accuracy comparable to the Bayes
rate is achieved.
In many applications, understanding of the mechanism of the random forest
"black box" is needed. Section 10 makes a start on this by computing internal
estimates of variable importance and binding these together by reuse runs.
Section 11 looks at random forests for regression. A bound for the mean
squared generalization error is derived that shows that the decrease in error
评论1