# Regression Trees' greedy algorithm in Hastie et al. (2009)

I am reading The Elements of Statistical Learning (Hastie, Tibshirani and Friedman, 2009), more specifically the section on regression decision trees (p. 307 of the book). There is something I do not understand about their splitting algorithm. The authors are explaining the mechanism to derive the splitting variable and the split point; they write $-$ my emphasis:

"If we adopt as our criterion minimization of the sum of squares $\sum(y_i-f(x_i))^2$, it is easy to see that the best $\hat{c}_m$ is just the average $y_i$ in region $R_m$:

$$\hat{c}_m=\text{ave}(y_i|x_i \in R_m)$$

Now finding the best binary partition in terms of minimum sum of squares is generally computationally infeasible. Hence we proceed with a greedy algorithm. Starting with all of the data, consider a splitting variable $j$ and split point $s$ , and define the pair of half-planes

$$R_1(j,s)=\{X|X_j\leq s\} \quad \text{and} \quad R_2(j,s)=\{X|X_j > s\}$$

Then we seek the splitting variable $j$ and split point $s$ that solve

$$\min_{j,s} \left[\min_{c_1} \sum_{x_i \in R_1(j,s)}(y_i-c_1)^2 + \min_{c_2} \sum_{x_i \in R_2(j,s)}(y_i-c_2)^2 \right]$$

For any choice $j$ and $s$, the inner minimization is solved by

$$\hat{c}_1=\text{ave}(y_i|x_i \in R_1(j,s)) \quad \text{and} \quad \hat{c}_2=\text{ave}(y_i|x_i \in R_2(j,s))$$

For each splitting variable, the determination of the split point $s$ can be done very quickly and hence by scanning through all of the inputs, determination of the best pair $(j, s)$ is feasible."

I am struggling to understand how the greedy algorithm they describe is different from finding the best binary partition. Is it simply because we are limiting the set of admissible partitions to partitions of the form "variable $j$ is above/below $s$", hence if we were to consider all possible partitions we should also consider much more complex partitions?

• It's greedy in that it only considers the best split for the next level, rather than the best split for the final tree. If there could be a situation where a split decision is suboptimal for that level, but if used then further down the tree it allows for splits that end up being globally more optimal, this greedy algorithm can't find them. They are saying that it is infeasible to create every possible tree (i.e. a tree for each possible split and each possible ordering of those splits) and then check the performance of all those trees to find the globally optimal tree. – Dan Jan 2 '19 at 16:18
• @Dan I have a question: if each rectangle only contains one training data point, then will the total sum of square of errors become 0? And if there are $N$ data points in total, we can find this type of partition in $O(n)$. And here it only talks about training performance, not test performance yet. So I am confused about saying the global optimization problem is computationally infeasible to solve... – ftxx Feb 18 '19 at 2:54
• @ftxx it's not $O(n)$ because the splits aren't one record vs all. If they were then it will still be $O(n^2)$, but the splits need to consider every possible split of all the records left into two groups of any size. If you want the non greedy global optimum (yes on the training set only, or validation set of you're doing cross validation), then you have to consider the set of all possible splits at every split and that is computationally infeasible (almost certainly exponential). – Dan Feb 19 '19 at 17:33

The difference between the squared error minimization that is done for each split in a decision tree and that is done for a typical $L_2$ loss optimization has 1 subtle distinction:

The decision tree splitting problem must search across possible partitions of the data into 2 groups and then find the optimal means within each of the 2 groups of split data. For all continuous data you have $\mathcal{O}(n)$ possible binary partitions of the feature and the response vector.

• Can you be a little more specific? I don't fully understand your statement. – Daneel Olivaw Oct 31 '17 at 10:27
• Searching over all possible binary splits on a singlefeature has complexity $\mathcal{O}(2^n)$ which is a challenging problem. The key difference is the recursive nature of the splits. Once the first split has partitioned the data into subsets $D_1$ and $D_2$ respectively, the search proceeds on each of the new subsets of data similar to the first step. This process continues ad nauseam until a stopping rule is satisfied. Does that clarify? – Lucas Roberts Nov 1 '17 at 14:00
• So rereading your question it looks like there are 2 questions, one on the space of splits searched within a class of split rules. Second question is about searching across classes of split rules. The first question I try to answer in the comment above this one. The second question is pretty challenging. The more complex you allow your split rules the more complex the recursive search will be, e.g. linear combinations of 2 features as possible split rules will have complexity $\mathcal{O}(n^2)$ rather than $\mathcal{O}(n)$ of a single binary rule-general hyperplane splits more complex. – Lucas Roberts Nov 1 '17 at 14:05

This simple example might illustrate why the 'greedy algorithm' is quicker than 'finding the best partition', but also why it can be less good.

Imagine a binary outcome with two features that follows the following rule: the outcome is A if feature 1 is non-negative and feature 2 is negative or feature 1 is negative and feature 2 is non-negative. The outcome is B in every other case.

The optimal partition is very obvious: if ((f1 >= 0) & (f2 < 0)): the outcome is A ifelse (f1 < 0) & (f2 >= 0: the outcome is A. else the outcome is B.

However, to get this outcome it is necessary to evaluate two subsequent rules jointly (both regarding the f1 feature and the f2 feature). In other words, two rules would be evaluated simultaneously. This can get increasingly complex as the number of features increases (in this stylised example it would not be such a problem). Therefore, the greedy algorithm only looks at the single best decision rule of the form feature > a that can be made next.

Now if the algorithm can only choose f1 or f2 and a single split point a, which is the greedy algorithm, it very much depends on the latent structure of the data which one would be picked first (just think of some possible data structures which include the four possibilities [(f1 <0 , f2 < 0), (f1 < 0, f2 >= 0, (f1 >= 0, f2 < 0, (f1 >= 0, f2 >= 0]. It will definitely be fast, because it 'only' has to evaluate two variables spaces and all possibly binary partitions.

The best partition would require evaluating all possible partitions of the first choice variable, and all possible subsequenty partition of the next etc. As you can imagine, this is much more complex than the greedy approach.

This difference in complexity is what the authors refer to.