Random forest: advantages/disadvantages of selecting randomly subset features for every tree vs for every node?

Question

There are two methods to select subset of features during a tree construction in random forest:

According to Breiman, Leo in "Random Forests":

“… random forest with random features is formed by selecting at random, at each node, a small group of input variables to split on.”

Tin Kam Ho used the “random subspace method” where each tree got a random subset of features.

I can imagine that by selecting a subset of features at each node is more superior as the correlated variables can still be involved in the whole tree construction. Whereas if we select a subset of features for each tree, one of the correlated variables will lose its importance.

Are there any other reasons why one method can perform better than the other one?

Answer 1

The general idea is that both Bagging and Random Forests are methods for variance reduction. This means that they work well with estimators that have LOW BIAS and HIGH VARIANCE (estimators that overfit, to put it simply). Moreover, the averaging of the estimator works best if these are UNCORRELATED from each other.

Decision trees are perfect for this job because, in particolar when fully grown, they can learn very complex interactions (therefore having low bias), but are very sensitive to the input data (high variance).

Both sampling strategies have the goal of reducing the correlation between the trees, which reduces the variance of the averaged ensemble (I suggest Elements of Statistical Learning, Chap. 15 for clarifications).
However, while sampling features at every node still allows the trees to see most variables (in different orders) and learn complex interactions, using a subsample for every tree greatly limits the amount of information that a single tree can learn. This means that trees grown in this fashion are going to be less deep, and with much higher bias, in particular for complex datasets. On the other hand, it is true that trees built this way will tend to be less correlated to each other, as they are often built on completely different subsets of features, but in most scenarios this will not overweight the increase in bias, therefore giving a worse performance on most use cases.

Answer 2

In context of tidy data, one bootstraps on samples(rows) and one bootstraps on both samples(rows) and variables(columns). They, as far as I know, always bootstrap in rows.

Here are the rules for "tidy" originally put forth by Hadley Wickham [1,2]:

1. Each variable forms a column.
2. Each observation forms a row.
3. Each type of observational units forms a table.

So the question becomes "what is the advantage of bootstrapping on columns".

It gives you what bootstrapping always gives, but applied to the column space:

• robust characterization. when a column is important, and excluded, error is much larger and vis versa. This can add emphasis on giving higher weight to higher importance variables, and given that tree-weights are inverse to error, this can reduce the impact of less important variables.
• Accelerated compute: when you operate on less data, ceteris paribus, your algo runs faster. If you make each tree with 75% of the columns, then they construct faster.

Update:

A classic CART-model looks at the along edges of the hyper-rectangle to find the location where a binary split of the domain best improves the measure of goodness. This is the stump. It then repeats the process for every sub-parcel of the domain until stopping criteria is met. A CART-model is a weak learner.

In a random forest, the parallel ensemble of CART-models, one is trying to aggregate weak learners to overcome their bias. Because there is more than one element required for an "ensemble" the ensemble can depart from classic CART and do things like bootstrap in row and column spaces. By column-wise bootstrapping, we are only looking at a subset of the axes for splitting. By row-wise bootstrapping, we are looking at a subset of points when evaluating the split metric.

The value of the approach is data-dependent. Mileage varies, as always.

There are, I have heard, some substantial compute-speedups to be found, but they only work if the whole column is treated as a single entity. I'm thinking about Gini importance or variance based trees. You can compute the score for the whole, and a subset, and then in O(1) get the score for the other subset. This doesn't work if you are bootstrapping on the rows(samples) but only on the columns(variables).

So the trade-off made is that the rows are resampled once per tree and the columns are resampled at each split. This allows faster compute per tree, faster per split, and allows bootstrapping on both.