# Confidence interval for Regression Trees

Many people think the regression tree is only an algorithm and it doesn't make sense approach confidence interval to it so I'd like to know if there's anyone figured out how to do it.

A regression tree can be write as follows (Friedman (2000)):

$$f(x)=\sum_{j=1}^{K}b_j I(x \in R_j)$$

Where $$R_j$$ is subset of predictors train set belongs to node $$j$$ that is $$x \in R_j$$ if $$x$$ respect all rules that generated $$j$$-th node, $$b_j$$ is the mean of response to $$x \in R_j$$, $$I(x \in R_j)=1$$ if $$x \in R_j$$ and $$I(x \in R_j)=0$$ unlike.

A var of regression tree can be get as follows:

$$V(f(x))=\sum_{j=1}^{K}V(b_j)I(x \in R_j)$$ since $$y_i$$ is iid and $$I(x \in R_j)^2=I(x \in R_j)$$

$$V(f(x))=\sum_{j=1}^{K}V(\frac{\sum_{i=1}^{|R_j|}y_i}{|R_j|})I(x \in R_j)$$ where $$|R_j|$$ is $$R_j's$$ size.

$$V(f(x))=\sum_{j=1}^{K}\frac{\sum_{i=1}^{|R_j|}V(y_i)}{|R_j|^2}I(x \in R_j)$$

$$V(f(x))=\sum_{j=1}^{K} \frac{\sum_{i=1}^{|R_j|}\sigma^2}{|R_j|^2}I(x \in R_j)$$

$$V(f(x))=\sum_{j=1}^{K}\frac{\sigma^2}{|R_j|}I(x \in R_j)$$

If $$y_i\sim N(u_y,\sigma^2)$$ then $$f(x) \sim N(\sum_{j=1}^{K}u_yI(x \in R_j), \sum_{j=1}^{K}\frac{\sigma^2}{|R_j|}I(x \in R_j))$$ so we can get a confidence interval to $$f(x)$$ by using normal distribuition theory.

If the $$R_j$$'s are known a-priori and $$f(x)$$ is genuinely equal to $$\sum_j b_j I(x \in R_j)$$ then this approach will basically work, under minor conditions (e.g., the number of observations in each $$R_j$$ tends to $$\infty$$, the error variance is finite and constant, and so forth).

There are a couple of issues with this approach in practice:

• In practice, the $$R_j$$'s are learned from the data, and so even if the model is correctly specified you need to take into account the fact that the $$R_j$$'s are estimated. It's far from trivial how to combine estimation of the $$R_j$$'s with the uncertainty quantification for $$f(x)$$ (even estimating the $$R_j$$'s in the first place is not easy, with CART being a particular estimator that need not be consistent).

• One can lower their expectations a bit, and only require $$f(x) \approx \sum_j b_j I(x \in R_j)$$. Again, if the $$R_j$$'s are known, then the approach outlined is valid as a confidence interval for the modified parameter $$\widetilde f(x) = E\{f(X) \mid X \in R(x)\}$$ where $$R(x)$$ is the rectangle $$R_j$$ that $$x$$ belongs to. So you get a valid confidence interval for something, it's just that this something is not $$f(x)$$.

• Even if the $$R_j$$'s are estimated, it still makes sense to take about inference for $$\widetilde f(x)$$. That is, we can ask about intervals for $$\widetilde f(x)$$ for the particular $$R_j$$'s we've estimated. A simple (albeit inefficient) way to do something like this is to data-split, using a training set to estimate the tree and a validation set to compute the confidence interval. But, again, a big issue that that you don't get an interval for $$f(x)$$.

I don't have citations on hand unfortunately (sorry) but I think most of the situation I laid out above is well-known to academics who work with decision trees. The much harder problem of making confidence intervals for random forests has received substantial interest in recent years, however, see e.g., this work from Wager et al.. That might give some references to works that handle the much simplerproblem you are interested in.

To simplify, I believe you are just saying to take the data within a node and compute an ordinary confidence interval using that data. That might work asymptotically, under some fairly strong assumptions concerning the nature of the response function. In finite samples you will have the additional problem of selection bias.

• $|R_j|$ must be greater than 30 to asymptotically approach works Jun 16, 2021 at 20:54
• There is nothing special about the number 30. Especially given the selection bias problem, the sometimes given (and usually silly) recommendation of 30 is bound to be way too low. Again, simulation offers the best answer. Jun 17, 2021 at 0:40
• simulation by bootstrap you mean? if you do, bootstrap only works asymptotically due to its cumulative density converges to real cumulative density. Jun 17, 2021 at 1:16
• I mean simulate to see how far off your suggested method is. You can check (i) bias, and (ii) coverage rate of the confidence intervals using simulation. That will give you an idea of how well you method works. Jun 17, 2021 at 14:41
• Asymptotics don't help here as tree complexity grows too fast. One can use the bootstrap to build hundreds of trees and get predicted values for specific $X$ combinations then get confidence intervals. You'll be disappointed with the honest confidence interval widths. This is related to the existence of bagging, boosting, random forests, which exist because of poor performance of single trees. Of course the multiple tree methods are uninterpretable, which is why regression hasn't disappeared. Aug 3, 2022 at 11:31