30
$\begingroup$

Software implementations of random forest classifiers have a number of parameters to allow users to fine-tune the algorithm's behavior, including the number of trees in the forest. Is this a parameter that needs to be tuned, in the same way as $m$, the number of features to try at each split (what Leo Breiman calls mtry)?

$\endgroup$
34
+50
$\begingroup$

It's common to find code snippets that treat $T$ as a hyper-parameter, and attempt to optimize over it in the same way as any other hyper-parameter. This is just wasting computational power: when all other hyper-parameters are fixed, the model’s loss stochastically decreases as the number of trees increases.

Intuitive explanation

Each tree in a random forest is identically distributed. The trees are identically distributed because each tree is grown using a randomization strategy that is repeated for each tree: boostrap the training data, and then grow each tree by picking the best split for a feature from among the $m$ features selected for that node. The random forest procedure stands in contrast to boosting, the trees are grown on their own bootstrap subsample without regard to the other trees. (It is in this sense that the random forest algorithm is "embarrassingly parallel.")

In the binary case, each random forest tree votes 1 for the positive class or 0 for the negative class for each sample. The average of all of these votes is taken as the classification score of the entire forest. (In the general $k$-nary case, we simply have a categorical distribution instead, but all of these arguments still apply.)

The Weak Law of Large Numbers is applicable in these circumstances because

  1. the trees' decisions are identically-distributed r.v.s (in the sense that a random procedure determines whether the tree votes 1 or 0) and
  2. the variable of interest only takes values $\{0,1\}$ for each tree and therefore each experiment (tree decision) has finite variance (because all moments of countably finite r.v.s are finite).

Applying WLLN in this case implies that, for each sample, the ensemble will tend toward a particular mean prediction value for that sample as the number of trees tends towards infinity. Additionally, for a given set of samples, a statistic of interest among those samples (such as the expected log-loss) will converge to a mean value as well, as the number of trees tends toward infinity.

Elements of Statistical Learning

Hastie et al. address this question very briefly in ESL (page 596).

Another claim is that random forests “cannot overfit” the data. It is certainly true that increasing $\mathcal{B}$ [the number of trees in the ensemble] does not cause the random forest sequence to overfit... However, this limit can overfit the data; the average of fully grown trees can result in too rich a model, and incur unnecessary variance. Segal (2004) demonstrates small gains in performance by controlling the depths of the individual trees grown in random forests. Our experience is that using full-grown trees seldom costs much, and results in one less tuning parameter.

Stated another way, for a fixed hyperparameter configuration, increasing the number of trees cannot overfit the data; however, the other hyperparameters might be a source of overfit.

Mathematical explanation

This section summarizes Philipp Probst & Anne-Laure Boulesteix "To tune or not to tune the number of trees in random forest?". The key results are

  1. The expected error rate and area under the ROC curve can be a non-monotonous function of the number of trees.

    a. The expected error rate (equiv. $\text{error rate} = 1 - \text{accuracy}$) as a function of $T$ the number of trees is given by $$ E(e_i(T)) = P\left(\sum_{t=1}^T e_{it} > 0.5\cdot T\right) $$ where $e_{it}$ is a binomial r.v. with expectation $E(e_{it}) = \epsilon_i$, the decision of a particular tree indexed by $t$. This function is increasing in $T$ for $\epsilon_{i} > 0.5$ and decreasing in $T$ for $\epsilon_{i} < 0.5$. The authors observe

    We see that the convergence rate of the error rate curve is only dependent on the distribution of the $\epsilon_i$ of the observations. Hence, the convergence rate of the error rate curve is not directly dependent on the number of observations n or the number of features, but these characteristics could influence the empirical distribution of the $\epsilon_i$’s and hence possibly the convergence rate as outlined in Section 4.3.1

    b. The authors note that ROC AUC (aka $c$-statistic) can be manipulated to have monotonous or non-monotonous curves as a function of $T$ depending on how the samples' expected scores align to their true classes.

  2. Probability-based measures, such as cross entropy and Brier score, are are monotonic as a function of the number of trees.

    a. The Breier Score has expectation $$ E(b_i(T)) = E(e_{it})^2 + \frac{\text{Var}(e_{it})}{T} $$ which is clearly a monotonously decreasing function of $T$.

    b. The log-loss (aka cross entropy loss) has expectation which can be approximated by a Taylor expansion $$ E(l_i(T)) \approx -\log(1 - \epsilon_i + a) + \frac{\epsilon_i (1 - \epsilon_i) }{ 2 T (1 - \epsilon_i + a)^2} $$ which is likewise a decreasing function of $T$. (The constant $a$ is a small positive number that keeps the values inside the logarithm and denominator away from zero.)

  3. Experimental results considering 306 data sets support these findings.

Experimental Demonstration

This is a practical demonstration using the diamonds data that ships with ggplot2. I turned it into a classification task by binarizing the price into "high" and "low" categories, with the dividing line determined by the median price.

From the perspective of cross-entropy, model improvements are very smooth. (However, the plot is not monotonic -- the divergence from the theoretical results presented above is because the theoretical results pertain to the expectation, rather than to the particular realizations of any one experiment.)

enter image description here

On the other hand, error rate is deceptive in the sense that it can swing up or down, and sometimes stay there for a number of additional trees, before reverting. This is because it does not measure the degree of incorrectness of the classification decision. This can cause the error rate to have "blips" of improved performance w.r.t. the number of trees, by which I mean that some sample which is on the decision boundary will bounce back and forth between predicted classes. A very large number of trees can be required for this behavior to be more-or-less suppressed.

Also, look at the behavior of error rate for a very small number of trees -- the results are wildly divergent! This implies that a method premised on choosing the number of trees this way is subject to a large amount of randomness. Moreover, repeating the same experiment with a different random seed could lead one to select a different number of trees purely on the basis of this randomness. In this sense, the behavior of the error rate for a small number of trees is entirely an artifact, both because we know that the LLN means that as the number of trees increases, this will tend towards its expectation, and because of the theoretical results in section 2. (Cross-validated hosts a number of questions comparing the merits of error rate/accuracy to other statistics.)

enter image description here

By contrast, the cross-entropy measurement is essentially stable after 200 trees, and virtually flat after 500.

Finally, I repeated the exact same experiment for error rate with a different random seed. The results are strikingly different for small $T$.

Code for this demonstration is available in this gist.

"So how should I choose $T$ if I'm not tuning it?"

Tuning the number of trees is unnecessary; instead, simply set the number of trees to a large, computationally feasible number, and let the asymptotic behavior of LLN do the rest.

In the case that you have some kind of constraint (a cap on the total number of terminal nodes, a cap on the model estimation time, a limit to the size of the model on disk), this amounts to choosing the largest $T$ that satisfies your constraint.

"Why do people tune over $T$ if it's wrong to do so?"

This is purely speculation, but I think that the belief that tuning the number of trees in a random forest persists is related to two facts:

  1. Boosting algorithms like AdaBoost and XGBoost do require users to tune the number of trees in the ensemble and some software users are not sophisticated enough to distinguish between boosting and bagging. (For a discussion of the distinction between boosting and bagging, see Is random forest a boosting algorithm?)

  2. Standard random forest implementations, like R's randomForest (which is, basically, the R interface to Breiman's FORTRAN code), only report error rate (or, equivalently, accuracy) as a function of trees. This is deceptive, because the accuracy is not a monotonic function of the number of trees, whereas continuous proper scoring rules such as Brier score and logloss are monotonic functions.

Citation

$\endgroup$
  • 1
    $\begingroup$ It seems like in any realistic scenario, the threshold should be tuned to get the best generalization error. We spend a lot of time around here telling people NOT to set their thresholds to 0.5! $\endgroup$ – Matthew Drury May 25 '18 at 20:43
  • $\begingroup$ It's true that we do spend time belaboring the 'thresholding' argument, but in this case, the arguments are true regardless of the choice of threshold. In the equation for expected error rate, pick any $ \theta \in (0,1) \cap \mathbb{R}$ and the argument still holds. $\endgroup$ – Reinstate Monica May 25 '18 at 20:45
  • $\begingroup$ I will read the paper this weekend (nice find), but is it still true if the threshold is tuned dynamically as a function of the number of trees? $\endgroup$ – Matthew Drury May 25 '18 at 20:46
  • 1
    $\begingroup$ @MatthewDrury The paper doesn't examine this question, but I don't think it matters how the the threshold is chosen (i.e. if we use 0.5 or optimize wrt some other function) in the sense that the behavior can still be non-monotonic depending on how the $\epsilon_i$ are distributed. $\endgroup$ – Reinstate Monica May 25 '18 at 20:53
  • $\begingroup$ Nice Q&A, +1. My immediate worry is that you write: "when all other parameters are fixed" Given one can readily optimise for the number of features used (~mtry) and the number of minimum observation per leaf (~minObs), we can have a dramatic changes in performance. Yes, I appreciate that probably 1000 trees will get things done 99.9% of the time but does this mean that different models hit their diminishing returns threshold sooner than others? (In which case optimising for ntrees is relevant if you want a smaller model for example) $\endgroup$ – usεr11852 says Reinstate Monic May 25 '18 at 22:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.