Confidence interval for Regression Trees

Question

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.

Answer 1

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.

Answer 2

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.