I was intrigued by the reply from @JohnRos to the post Making a single decision tree from a random forest. They say "<...> a random forest prediction cannot be represented by a single tree. This is because they learn predictors in different hypothesis classes: a random forest learns predictors over the space of linear combinations of trees, which includes predictors that are not trees <...>". I cannot understand why a linear combination of trees includes predictors that are not trees. So my first question is, can somebody please clarify the statement above?
So let us say I grow a Random Forest. I obtain a function that maps an input vector to an outcome. Why cannot this function be replicated by a single tree? Let me attempt a rational argument. Random Forest will generate a piecewise-constant function, from a space $R^n$,where $n$ is the number of feature inputs, to $R$, a single output. The domain is partitioned in regions with orthogonal boundaries. Let me consider the case $n=2$, I fail to see why this could not be generalised. The domain will be partitioned by Random Forest into something as
where colors represents regions over which the output is constant. I take it that the pic represent domain whose sides are multiple of a fixed length, which will not be the case for RF, but that does not matter for the argument (simply extend each vertical/horizontal edge vertically/horizontally, will still end up in a grid). Given this partition, I do not see why it could not be represented by a single tree. Get the leftmost vertical split, and partition the top node: now the domain is split in two, leftmost column, all the other columns. Keep partitioning the leftmost column with horizontal splits. Now consider all the $n-1$ columns, and repeat. Split vertically the leftmost columns, and split this one with horizontal splits. And so on.
Now I have a tree that represents the RF function exactly.
The second question is then, where am I going wrong?
To clarify my question, would like to underline the image I posted represents the decision boundary for a single tree, see for example this page, or slide 15 of this document, also slide 10 for a 2D and 3D examples.
My question can be then rephrased as follows.
- Given a tree, a decision boundary is determined.
- Given a Random Forest, a decision boundary is also determined
- Given the decision boundary of a RF, I argue that there is a procedure to reconstruct one possible tree, compatible with said Decision Boundary.
- Hence, it is possible to represent an entire Random Forest with a single tree.
Where is the flaw in this line of reasoning?