Optimization in regression trees splitting

Question

The optimization problem that need to solve in the recursive binary splitting algorithm in regresion tree models to determine which variable expand, the one which will be have the minimum sum of the square residuals between the two regions, is formulated in the book "An introduction to Statistical Learning" (2015) as following:

"" For any j and s, we define the pair of half-planes:

$R_1(j,s) = \{X|X_j < s\}$ and $R_2(j,s) = \{X|X_, >= s\}$

and we seek the vaalue of j and s that minimize the equation

$\sum_{i:x_i\in R_1(j,s)}(y_i - \hat{y}_{R_1})^2 + \sum_{i:x_i\in R_2(j,s)}(y_i - \hat{y}_{R_2})$ "" (page 307)

How can I optimize the above formulation in order to program the algorithm?

I try with an exhaustive search of $s$ in the space defined by $[min(X_j), max(X_j)]$, so cut the plane into two halves, compute the metric, update $s$ in $\alpha$ and then repeat the process until reach the upper bound $max(X_j)$. The code in R looks like:

for (i in 1:length(var)) {
 var <- X[var[i]]
 min_val <- min(var)
 max_val <- max(var)
 s <- min_val
 alpha <- 0.02
 # create a vector to store the s - SRCT values
 output <- vector("double", (max_val - min_val) / alpha)
 j = 1
 while (s <= max_val) {
   half_plane <- var > s
   yhat1 <- mean(y[half_plane])
   yhat2 <- mean(y[!half_plane])
   e1 <- y[half_plane] - yhat1
   e2 <- y[!half_plane] - yhat2
   SRC1 <- sum(e1 ^ 2)
   SRC2 <- sum(e2 ^ 2)
   SRCT <- SRC1 + SRC2
   # store the results
   output[j] <- SRCT
   names(output)[j] <- s
   # update s and j
   s <- s + alpha
   j <- j + 1
  }
}

But the immediate problems of this approach are how to define the update parameter alpha ($\alpha$) and from those $s$ that produce the same results how could determine the best $s$.

Answer 1

Just to summarize what you've done: you've taken the range $[min(x), max(x)]$, and you have broken it into equal length pieces with stride $\alpha$:

$$min(x), \ min(x) + \alpha, \ min(x) + 2 \alpha, \ldots $$

Then you've used each $min(x) + k \alpha$ as a potential cut point, computed the loss using these cutpoints, and then found the cut-point that optimizes the loss.

This is a reasonable approach, but it does lead to two problems:

1) Sometimes two cut points lie between two consecutive datapoints

$$ x_i \leq min(x) + k \alpha < min(x) + (k+1) \alpha < x_{i+1} $$

which means that you will get the same value of the loss function for each of these cutpoints.

2) Sometimes there are two consecutive datapoints between which no cut-point lands:

$$ min(x) + k \alpha < x_i < x_{i+1} < min(x) + (k+1) \alpha $$

so in this case you have lost some granularity, and could possibly miss the minimal value of the loss function.

This suggests a simple solution, use the midpoints between data points as the cut-points:

$$ \frac{x_1 + x_0}{2}, \frac{x_2 + x_1}{2}, \ldots $$

This immediately resolves both issues, and is the strategy most implementations take.