3
$\begingroup$

I've been optimizing a random forest model built from the sklearn implementation. One of the parameters in this implementation of random forests allows you to set Bootstrap = True/False. While tuning the hyperparameters of my model to my dataset, both random search and genetic algorithms consistently find that setting bootstrap=False results in a better model (accuracy increases >1%). I am using 3-fold CV AND a separate test set at the end to confirm all of this. Tuned models consistently get me to ~98% accuracy. The dataset is a few thousands examples large and is split between two classes.

My question is this: is a random forest even still random if bootstrapping is turned off? I thought the whole premise of a random forest is that, unlike a single decision tree (which sees the entire dataset as it grows), RF randomly partitions the original dataset and divies the partitions up among several decision trees. If bootstrapping is turned off, doesn't that mean you just have n decision trees growing from the same original data corpus? Or is it the case that when bootstrapping is off, the dataset is uniformly split into n partitions and distributed to n trees in a way that isn't randomized?

In addition, it doesn't make sense that taking away the main premise of randomness from the algorithm would improve accuracy.


Note: Did a quick test with a random dataset, and setting bootstrap = False garnered better results once again.

from sklearn.ensemble import RandomForestClassifier as rfc
from sklearn.datasets import make_classification
from sklearn.model_selection import train_test_split

X, y = make_classification(n_samples=10000, n_features=4000, n_informative=3000, n_redundant=600, random_state=0, shuffle=True)
X_train, X_test, y_train, y_test = train_test_split(X, y)

clf_True = rfc(bootstrap=True, random_state=0)
clf_False = rfc(bootstrap=False, random_state=0)

clf_True.fit(X_train, y_train)
clf_False.fit(X_train, y_train)

scoreTrue = clf_True.score(X_test, y_test)
scoreFalse = clf_False.score(X_test, y_test)

>>>scoreTrue =  0.5232; scoreFalse = 0.5336

What is going on under the hood?

Edit: I made the number of features high in this example script above because in the data set I'm working with (large text corpus), I have hundreds of thousands of unique terms and only a few thousands training/testing instances. I believe bootstrapping omits ~1/3 of the dataset from the training phase. Could it be that disabling bootstrapping is giving me better results because my training phase is data-starved?

$\endgroup$
  • 4
    $\begingroup$ You're still considering only a random selection of features for each split. Thats the real randomness in random forest. $\endgroup$ – Matthew Drury Jul 3 '18 at 19:54
5
$\begingroup$

My question is this: is a random forest even still random if bootstrapping is turned off?

Yes, it's still random. Without bootstrapping, all of the data is used to fit the model, so there is not random variation between trees with respect to the selected examples at each stage. However, random forest has a second source of variation, which is the random subset of features to try at each split.

I thought the whole premise of a random forest is that, unlike a single decision tree (which sees the entire dataset as it grows), RF randomly partitions the original dataset and divies the partitions up among several decision trees.

This is incorrect. Random forest s the data for each tree, and then grows a decision tree that can only use a random subset of samples at each split. The documentation states "The sub-sample size is always the same as the original input sample size but the samples are drawn with replacement if bootstrap=True (default)," which implies that bootstrap=False draws a sample of size equal to the number of training examples without replacement, i.e. the same training set is always used.

Detailed explanations of the random forest procedure and its statistical properties can be found in Leo Breiman, "Random Forests," Machine Learning volume 45 issue 1 (2001) as well as the relevant chapter of Hastie et al., Elements of Statistical Learning.

We can also examine the source, which shows that the original data is not further altered when bootstrap=False

    if forest.bootstrap:
      ...irrelevant...
    elif class_weight == 'balanced_subsample':
      ...irrelevant...
    else:
      tree.fit(X, y, sample_weight=sample_weight, check_input=False)

If bootstrapping is turned off, doesn't that mean you just have n decision trees growing from the same original data corpus?

Yes, with the exception that only a random subsample of features can be chosen at each split.

Or is it the case that when bootstrapping is off, the dataset is uniformly split into n partitions and distributed to n trees in a way that isn't randomized?

No.


Remark - I haven't studied the details of sklearn.datasets.make_classification at all, but it seems that at least part of your result depends on how it generates its data, and how many features are relevant.

$\endgroup$
  • $\begingroup$ This is a great explanation! Does this mean if bootstrap=False and each split uses all the features (no random subsampling) then the forest is not random? $\endgroup$ – willk Mar 27 at 14:53
  • $\begingroup$ I think so. There could be some idiosyncratic behavior in the event that two splits are equally good, or similar corner cases. $\endgroup$ – Sycorax Mar 27 at 14:56
  • $\begingroup$ This seems like an interesting question to test. Should be pretty doable with Sklearn since you can even print out the individual trees to see if they are the same. $\endgroup$ – willk Mar 27 at 15:47
  • $\begingroup$ @willk I look forward to reading about your results. You could even ask & answer your own question on stats.SE. $\endgroup$ – Sycorax Mar 27 at 15:53
  • $\begingroup$ I asked the question here. Still working on visualizing the individual trees, but it appears setting bootstrap=False and using all the features does not produce identical random forests, at least in Scikit-Learn. Whether this is because of the particular implementation remains to be seen! $\endgroup$ – willk Mar 28 at 1:16

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.