Feature transformations with ensembles of trees

Question

I'm using these ensemble algorithms for learning, and they are performing quite well. Now, I need to explain them to my peers and myself. Copied from the page, it says Transform your features into a higher dimensional, sparse space. Then train a linear model on these features.

How are these models transforming the features into higher dimensional, sparse space?

In the paragraph below, I get the fit an ensemble of trees on the training set. The next sentence about how each leaf of each tree is assigned a fixed arbitrary feature index in a new feature space is absolutely not clear; where and how did the new feature space come about?

Furthermore, why are the leaf indices one-hot encoded?

First fit an ensemble of trees (totally random trees, a random forest, or gradient boosted trees) on the training set. Then each leaf of each tree in the ensemble is assigned a fixed arbitrary feature index in a new feature space. These leaf indices are then encoded in a one-hot fashion.

In the last paragraph, it just seems as if the original features are turned off and on.

Each sample goes through the decisions of each tree of the ensemble and ends up in one leaf per tree. The sample is encoded by setting feature values for these leaves to 1 and the other feature values to 0.

From what I can understand, it just seems that there are a bunch of trees where each leaf node turns off/on features from the original space; this understanding seems to me to be reducing the feature space not projecting it to higher dimensions.

In the example with gradient boosted tree with logistic regression, it seems the algorithm is learning trees to turn on/off features (feature selection), then applying logistic regression to classify on a subset of the features. Of course, this understanding is completely against what's being stated.

Are there any more in-depth documentations on these techniques/algorithms?

Answer 1

I am not completely sure, but here is my understanding.
First of all, to your first question "How are these models transforming the features into higher dimensional, sparse space?". In the random forest model, suppose there are $n$ decision trees and for each tree $T_i$, there are $M_i$ leaves(not labels). When an instance goes through the random forest model, it ends up being 1 leaf in each tree and the final result is the majority vote of the leaves' value. Now, we come up a boolean variable $l_{i_m}$ to denote if the instance ends up in tree $T_i$ and leaf $m$. In this way, we will have $\sum_{i = 1}^{n} M_i$, binary variables, which is usually greater than the number of original predictors, after the random forest transformation. Since an instance can be only one leaf in a tree, most of the binary variables will be 0, which explains "sparse". Next step, we fit a logistic regression(linear model) using only with binary variables as inputs.