1
$\begingroup$

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$.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Good synthesis and answer to improve the search of $s$. So if I understand well, the most common implementation use search with midpoints between data points as the cut-points to solve the minimization problem? Another method instead of search that perhaps are more efficiently? $\endgroup$ – Cristóbal Alcázar Aug 28 '17 at 3:22
  • $\begingroup$ There's not really a way to make it more efficient if you require the correct answer every time: the optimal split could occur between any pair of data points, so you have to try them all. On the other hand, some algorithms don't require the totally correct answer each time (boosting for example), and there it's common to only search through some of the midpoints, and just take the best one found. $\endgroup$ – Matthew Drury Aug 28 '17 at 3:25
  • $\begingroup$ @Matthew Drury I made the changes in the code but I still have the problem of different cut points were given the same result. Here is the computation, the result is 4 and in the book example the optimal cutpoint is 4.5. In my implementation 4 and 4.5 give the same value, but how can I break the tie? $\endgroup$ – Cristóbal Alcázar Aug 28 '17 at 18:42
  • $\begingroup$ Now works!, instead of $\frac{x_1 - x_0}{2}, ...$ is $\frac{x_1 + x_0}{2}$ $\endgroup$ – Cristóbal Alcázar Aug 29 '17 at 3:46
  • $\begingroup$ Ah, yes. I'm sorry my typo caused you so much trouble! $\endgroup$ – Matthew Drury Aug 29 '17 at 4:03

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.