3
$\begingroup$

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

domain partition.

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?

EDIT

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.

  1. Given a tree, a decision boundary is determined.
  2. Given a Random Forest, a decision boundary is also determined
  3. Given the decision boundary of a RF, I argue that there is a procedure to reconstruct one possible tree, compatible with said Decision Boundary.
  4. Hence, it is possible to represent an entire Random Forest with a single tree.

Where is the flaw in this line of reasoning?

$\endgroup$
8
  • $\begingroup$ RFs are ensembles of lots (many) individual mini-trees the results from which are aggregated to produce a set of summary performance metrics. That said, your graphic is a heat map. Where's the tree diagram? $\endgroup$
    – user78229
    Commented Jul 30, 2023 at 11:53
  • $\begingroup$ I know what RFs are. I also tried to explain what the heat map represents, that is, the partition of the domsin induced by the tree, and ultimately, by the Forest. The tree diagram is irrelevant for my question. I am asking, given a RF, why cannot a single tree being built, giving the same outcome. There is also another angke to the same question, at the beginning of the post. $\endgroup$
    – Smerdjakov
    Commented Jul 30, 2023 at 12:21
  • $\begingroup$ CART trees are a specific type of visual. Sorry, but your graphic doesn't express anything in tree form. Per your claim, add a tree diagram and I'll shut up. $\endgroup$
    – user78229
    Commented Jul 30, 2023 at 12:25
  • $\begingroup$ the heat map is a 2D decision boundary. $\endgroup$
    – Smerdjakov
    Commented Jul 30, 2023 at 12:25
  • $\begingroup$ Another heat map, scikit-learn.org/stable/modules/generated/… $\endgroup$
    – Smerdjakov
    Commented Jul 30, 2023 at 12:26

1 Answer 1

6
+50
$\begingroup$

I think you are right and @JohnRos is wrong. Here's the argument.

  1. A random forest (RF) can be represented by a single tree if and only if the decision boundaries of the RF (within which a constant value is predicted) can be written as finite unions of hyperrectangles parallel to the coordinate axes. (Note that this does not mean that such a tree can be obtained from one of the standard algorithms to generate trees from data! You can construct the tree from systematically partitioning the space in order to reproduce the decision rule of the RF.)

  2. But this is in fact the case. If the RF was computed from $k$ individual trees, every observation that falls into the same intersection of the $k$ tree's leaves will end up predicted by the same constant, and these intersections must themselves be hyperrectangles parallel to the coordinate axes as this is what the original trees deliver.

This doesn't imply that the resulting tree is useful or allows better interpretation, as it may be extremely big. It basically needs to emulate all involved random trees, so trying to interpret it may just be as difficult as looking at the whole random tree ensemble that led to the RF, and nothing is won. And, as said before, neither does it mean that one could have any tree-building algorithm that could generate it directly from the data other than of course "do the RF first and then construct the tree from it".

$\endgroup$
1
  • $\begingroup$ thank you, yes I see your points indeed. The resulting tree is not meant to be useful in general, I was just intrigued by sheer curiosity by its existence . And yes I see the tree would not be necessary the outcome of any tree algorithm, as you say, I am just looking for the possibility to reconstruct it a posteriori. $\endgroup$
    – Smerdjakov
    Commented Jul 30, 2023 at 13:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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