Shortcut for computing RSS at different split point when building regression trees?

Question

I'm coding regression trees from scratch in R. For a given ordered predictor variable, $X$, obviously I have to compute the RSS at each unique ordered value of $X_i$. When moving over to the next possible split point, I am trying to avoid doing the entire RSS computation from scratch (i.e., scrolling through all the $y_i$'s to recompute the RSS) in order to improve computational efficiency. I've read that there are algebraic shortcuts for this, but have not been able to figure it out. Can someone provide insight as to how this would be done?

Answer 1

I think doing this directly from the RSS may be hard. One shortcut (that I think I've seen before) is to save two components of RSS:

$$ \begin{align*} RSS &= \sum (y_i - \bar{y})^2 = \sum (y_i^2 - 2\bar{y} y_i + \bar{y}^2 ) \\ &= \sum y_i^2 + \left(- \frac2n \left(\sum y_i\right)^2 + n \left(\frac1n \sum y_i\right)^2 \right) \\ &= \sum y_i^2 - \frac1n \left(\sum y_i\right)^2. \end{align*} $$

(You might recognize that trick from the common rewriting of variance.) So save the sum of squares together with the sum of values. When you move one point from the right side to the left, it's easy to update those two values (and $n$) for each branch, and from that to compute their RSS.