15
$\begingroup$

Suppose we have two regression trees (tree A and tree B) that map input $x \in \mathbb{R}^d$ to output $\hat{y} \in \mathbb{R}$. Let $\hat{y} = f_A(x)$ for tree A and $f_B(x)$ for tree B. Each tree uses binary splits, with hyperplanes as the separating functions.

Now, suppose we take a weighted sum of the tree outputs:

$$f_C(x) = w_A \ f_A(x) + w_B \ f_B(x)$$

Is the function $f_C$ equivalent to a single (deeper) regression tree? If the answer is "sometimes", then under what conditions?

Ideally, I'd like to allow oblique hyperplanes (i.e. splits performed on linear combinations of features). But, assuming single-feature splits could be ok if that's the only answer available.

Example

Here are two regression trees defined on a 2d input space:

enter image description here

The figure shows how each tree partitions input space, and the output for each region (coded in grayscale). Colored numbers indicate regions of input space: 3,4,5,6 correspond to leaf nodes. 1 is the union of 3 & 4, etc.

Now suppose we average the output of trees A and B:

enter image description here

The average output is plotted on the left, with the decision boundaries of trees A and B superimposed. In this case, it's possible to construct a single, deeper tree whose output is equivalent to the average (plotted on the right). Each node corresponds to a region of input space that can be constructed out of the regions defined by trees A and B (indicated by colored numbers on each node; multiple numbers indicate the intersection of two regions). Note that this tree is not unique--we could have started building from tree B instead of tree A.

This example shows that there exist cases where the answer is "yes". I'd like to know whether this is always true.

$\endgroup$
  • 2
    $\begingroup$ Hmm.. If that was the case why would we train a random forest? (Because clearly the linear combination of 500 trees can be re-expressed as 499 weighted pairwise sums of 500 trees) Nice question, +1. $\endgroup$ – usεr11852 Mar 23 '18 at 12:29
  • $\begingroup$ interesting question! I would assume the hypothesis space of decision trees and decision tree ensembles (boosting, linear combination of trees ) to be the same. Looking forward to an answer.. $\endgroup$ – Laksan Nathan Mar 23 '18 at 17:29
  • $\begingroup$ @usεr11852 Maybe because using a single very big tree instead of forest is so much slower? Just as in neural networks the one hidden layer networks can already approximate all of the continuous functions but adding layers makes the network faster. Not saying this is the case here but it might be. $\endgroup$ – Harto Saarinen Mar 24 '18 at 7:14
  • 1
    $\begingroup$ @HartoSaarinen: This is an interesting way of thinking about this but I suspect it does not hold easily. It is accepted that very deep trees might overfit and generalise poorly (their predictions are also quite unstable). In addition (regarding speed considerations) deeper trees require exponentially more splits and thus more training time. (A tree of depth 10 has at most 1023 splits but a tree of depth 20, 1048575 splits. Lots more work!) $\endgroup$ – usεr11852 Mar 24 '18 at 11:58
  • 1
    $\begingroup$ @usεr11852 I agree that it might be totally untrue and the answer might be something totally different. This is what makes the field so interesting at this moment, super many things to be discovered! $\endgroup$ – Harto Saarinen Mar 24 '18 at 13:12
6
$\begingroup$

Yes, the weighted sum of a regression trees is equivalent to a single (deeper) regression tree.

Universal function approximator

A regression tree is a universal function approximator (see e.g. cstheory). Most research on universal function approximations is done on artifical neural networks with one hidden layer (read this great blog). However, most machine learning algorithms are universal function approximations.

Being a universal function approximator means that any arbitrary function can be approximately represented. Thus, no matter how complex the function gets, a universal function approximation can represent it with any desired precision. In case of a regression tree you can imagine an infinitely deep one. This infinitely deep tree can assign any value to any point in space.

Since a weighted sum of a regression tree is another arbitrary function, there exists another regression tree that represents that function.

An algorithm to create such a tree

Knowing that such a tree exist is great. But we also want a recipe to create them. Such and algorithm would combine two given trees $T_1$ and $T_2$ and create a new one. A solution is copy-pasting $T_2$ at every leaf node of $T1$. The output value of the leaf nodes of the new tree is then the weighted sum of the leaf node of $T1$ (somewhere in the middle of the tree) and the leaf node of $T2$.

The example below shows two simple trees that are added with weight 0.5. Note that one node will never be reached, because there does not exist a number that is smaller than 3 and larger than 5. This indicates that these trees can be improved, but it does not make them invalid.

enter image description here

Why use more complex algorithms

An interesting additional question was raised by @usεr11852 in the comments: why would we use boosting algorithms (or in fact any complex machine learning algorithm) if every function can be modelled with a simple regression tree?

Regression trees can indeed represent any function but that is only one criteria for a machine learning algorithm. One important other property is how well they generalise. Deep regression trees are prone to overfitting, i.e. they do not generalise well. A random forest averages lots of deep trees to prevent this.

$\endgroup$

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.