Tree-Values: Selective Inference for Regression Trees

Abstract

We consider conducting inference on the output of the Classification and Regression Tree (CART) (Breiman et al., 1984) algorithm. A naive approach to inference that does not account for the fact that the tree was estimated from the data will not achieve standard guarantees, such as Type 1 error rate control and nominal coverage. Thus, we propose a selective inference framework for conducting inference on a fitted CART tree. In a nutshell, we condition on the fact that the tree was estimated from the data. We propose a test for the difference in the mean response between a pair of terminal nodes that controls the selective Type 1 error rate, and a confidence interval for the mean response within a single terminal node that attains the nominal selective coverage. Efficient algorithms for computing the necessary conditioning sets are provided. We apply these methods in simulation and to a dataset involving the association between portion control interventions and caloric intake.

Keywords: CART; Regression trees; hypothesis testing; post-selection inference; selective inference.

Figure 1:

The regression tree takes the form $\text{TREE}=\left\{{ℝ}^p,{\chi }_{1,s_1,1},{\chi }_{1,s_1,0},{\chi }_{1,s_1,1}\cap {\chi }_{2,s_2,1},{\chi }_{1,s_1,1}\cap {\chi }_{2,s_2,0}\right\}$. The regions $R_A={\chi }_{1,s_1,1}\cap {\chi }_{2,s_2,1}$ and $R_B={\chi }_{1,s_1,1}\cap {\chi }_{2,s_2,0}$ are siblings, and are children, and therefore descendants, of the region ${\chi }_{1,s_1,1}$. The ancestors of $R_A$ and $R_B$ are ${\mathbb{R}}^p$ and ${\chi }_{1,s_1,1}$. Furthermore, $R_A,R_B$, and ${\chi }_{1,s_1,0}$ are terminal regions.

Figure 2:

Data with $n=100$ and $p=2$. Regions resulting from CART $(\lambda =0)$ are delineated using solid lines. Here, $R_A={\chi }_{\mathrm{1,26,0}}\cap {\chi }_{\mathrm{2,72,1}}$ and $R_B={\chi }_{\mathrm{1,26,0}}\cap {\chi }_{\mathrm{2,72,0}}$. Top: Output of CART applied to $y^{\prime }\left(\varphi ,{\nu }_{sib}\right)$, where ${\nu }_{sib}$ in (6) encodes the contrast between $R_A$ and $R_B$, for various values of $\varphi$. The left-most panel displays $y=y^{\prime }\left({\nu }_{sib}^{\mathrm{T}}y,{\nu }_{sib}\right)$. By inspection, we see that $-14.9\in S_{sib}^0\left({\nu }_{sib}\right)$ and $5\in S_{sib}^0\left({\nu }_{sib}\right)$, but $0\notin S_{\mathit{\text{sib}}}^0\left({\nu }_{sib}\right)$ and $40\notin S_{\mathit{\text{sib}}}^0\left({\nu }_{\mathit{\text{sib}}}\right)$. In fact, $S_{\mathit{\text{sib}}}^0\left({\nu }_{sib}\right)=(-19.8,-1.8)\cup \left(\mathrm{0.9,34.9}\right)$. Bottom: Output of CART applied to $y^{\prime }\left(\varphi ,{\nu }_{reg}\right)$, where ${\nu }_{reg}$ in (14) encodes membership in $R_A$. The left-most panel displays $y=y^{\prime }\left({\nu }_{reg}^{\mathrm{T}}y,{\nu }_{reg}\right)$. Here, $S_{reg}^0\left({\nu }_{reg}\right)=(-\mathrm{\infty },3.1)\cup \left(\mathrm{5.8,8.8}\right)\cup (14.1,\mathrm{\infty })$.

Figure 3:

The true mean model in Section 5, for $a=0.5$ (left), $a=1$ (center), and $a=2$ (right). The difference in means between the sibling nodes at level two in the tree is $ab$, while the difference in means between the sibling nodes at level three is $b$.

Figure 4:

Quantile-quantile plots of the p-values for testing $H_0:{\nu }_{sib}^{\mathrm{T}}\mu =0$, as described in Section 5.3. A naive Z-test (green), sample splitting (blue), and selective $Z$-test (pink) were performed; see Section 5.2. The p-values are stratified by the level of the regions in the fitted tree.

Figure 5:

Proportion of true splits detected (solid lines) and rejected (dotted lines) for CART with selective $Z$-tests (pink), CTree (black), and CART with sample splitting (blue) across different settings of the data generating mechanism, stratified by level in tree. As CTree only makes a split if the p-value is less than 0.05, the proportion of detections equals the proportion of rejections.

Figure 6:

The median width of the selective $Z$-intervals for parameter ${\nu }_{reg}^{\mathrm{T}}\mu$ for regions at levels one (solid), two (dashed), and three (dotted) of the tree. Similar results hold for parameter ${\nu }_{sib}^{\mathrm{T}}\mu$. Panel (a) breaks results down by the parameters $a$ and $b$, whereas panel (b) aggregates results across values of parameters $a$ and $b$, and displays them as a function of the adjusted Rand Index between the true and estimated trees.

Figure 7:

QQ plots of the p-values from testing $H_0:{\nu }_{\mathit{\text{sib}}}^T\mu =0$ when $\mu =0_n$ using the selective $Z$-test with three different values plugged in to the truncated normal CDF for $\sigma$. The p-values are stratified by the level of the regions in the fitted tree.

Figure 8:

Proportion of true splits detected (solid lines) and rejected (dotted lines) for CART with the three versions of the selective $Z$-test. The results are stratified by level in tree.

Figure 9:

Left: A CART tree fit to the Box Lunch Study data. Each split has been labeled with a p-value (8), and each region has been labeled with a confidence interval (23). The shading of the nodes indicates the average response values (white indicates a very small value and dark blue a very large value). Top right: A CTree fit to the Box Lunch Study data. Bottom right: A scatterplot showing the relationship between the covariate hunger and the response.

Figure 10:

(a). An illustration of Case 1 (red), Case 2 (blue), and Case 3 (black) for a region $R\in {\mathrm{T}\mathrm{R}\mathrm{E}\mathrm{E}}^0\left\{y^{\prime }\left({\varphi }_1,\nu \right)\right\}$ in the base case of the proof of Lemma 27, where $ℛ\left(ℬ\right)=\left\{R^{\left(0\right)},\dots ,R^{\left(3\right)}\right\}$. (b.) The black regions show the possible cases for $R\in {\mathrm{T}\mathrm{R}\mathrm{E}\mathrm{E}}_{k-1}$ in the inductive step of the proof of Lemma 27.

Figure 11:

Simulation results comparing inference based on the full conditioning set to inference based on the identity permutation only (see Section 4.3). The left panel shows power curves. The center panel zooms in on one section of the left panel. The right panel shows median widths of confidence intervals.

Figure 12:

Quantile-quantile plots of the p-values for testing $H_0:{\nu }_{sib}^{\mathrm{T}}\mu =0$ under a global null. A naive Z-test (green), sample splitting (blue), and selective Z-test (pink) were performed; see Section 5.2.

Figure 13:

A CART tree fit to the Box Lunch Study data. Each split has been labeled with a p-value (8), and each region has been labeled with a confidence interval (23). Inference is carried out by plugging in ${\hat{\sigma }}_{\mathrm{c}\mathrm{o}\mathrm{n}\mathrm{s}\mathrm{ }}$, from Section 5.7, as an estimate of $\sigma$.