# 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 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 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 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.
• 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