1 Introduction↩︎

Policymakers and researchers often use recursive binary split rules to partition a population based on a binary outcome \(Y\in\{0,1\}\) and target subpopulations with a probability of \(Y = 1\) greater than 50% when implementing a policy. We call such policy targeting problems Latent Probability Classification (LPC). Practically, CART is often employed for LPC. For example, [1] uses CART to find subpopulations with a higher than 50% probability of being financially constrained and recommends targeting these households with a tax credit program. In Appendix 8.1, we cite 23 empirical cases of using CART for various LPC problems to demonstrate the broad applicability of the setup that this paper investigates. In these studies, researchers typically use CART to divide the samples into many nodes, estimate the probability of \(Y = 1\) for each node, and target those nodes with estimated probabilities higher than a threshold of 50%, denoted as \(c = 0.5\). This approach, though intuitive, is not optimal for LPC. Here, we provide a toy example in Figure 1 (a) to illustrate the limitation of using CART for an LPC problem.

A toy example: Suppose the latent probability of a binary event \(Y = 1\) is a sinusoidal function of an observable variable \(X\), \(\mathbb{P}(Y=1|X) = \frac{\sin (2 \pi X)+1}{3} \text{ where X \sim {\rm Unif}[0,1]}\). Figure 1 (a) shows the function, where the green segment represents the subpopulation that should be targeted, and the orange segments represent the subpopulation that should not be targeted. In this example, we impose that the policymaker can only split the population once based on the value of \(X\). CART splits at \(X = 0.5\), denoted as \(s^{CART}\) in Figure 1 (a). The left node has \(\mathbb{P}(Y=1 | X > 0.5) = \frac{2}{3}(0.5 + \frac{1}{\pi}) > 0.5\), whereas the right node has \(\mathbb{P}(Y=1| X \leq 0.5) = \frac{2}{3}(0.5 - \frac{1}{\pi}) \leq 0.5\). Consequently, we target the subpopulation by \(X \leq 0.5\), i.e., left node. To demonstrate why \(s^{CART}\) is suboptimal for the LPC problem, consider an alternative split at \(s^* = \frac{5}{12}\). The left node still has \(\mathbb{P}(Y=1|X \leq \frac{5}{12}) \approx 0.571 > 0.5\), right node has \(\mathbb{P}(Y=1|X >\frac{5}{12}) \approx 0.164 < 0.5\). Only the left node (\(X \leq \frac{5}{12}\)) is targeted.

All subgroups that are correctly targeted/not targeted by \(s^{CART}\) are also correctly targeted/not targeted by \(s^*\). Moreover, \(s^*\) excludes the group with \(\frac{5}{12} < X < 0.5\) whose \(\mathbb{P}(Y=1|X) < 0.5\) from being targeted whereas \(s^{CART}\) incorrectly targets this subgroup. We say that \(s^*\) strictly dominates \(s^{CART}\). Section 3 formally defines strict domination.

Proposed methods: This paper proposes methods that generate improved split rules. First, we replace the CART impurity function with a weighted sum of the distances between node means and the threshold \(c\). This method is called Maximizing Distance Final Split (MDFS). Assuming the existence of a unique intersection between \(\mathbb{P}(Y=1|X)\) and \(c\), MDFS identifies the unique best split (hence, strictly dominating CART). The second method, Penalized Final Split (PFS), is a generalization of MDFS. It relaxes the unique intersect assumption and still strictly dominates CART. The third method, weighted Empirical risk Final Split (wEFS), adapts the weighted loss function from the cost-sensitive binary classification literature to our setup.

Generalizing the threshold from \(c = 0.5\) to \(c \in (0,1)\): Though most of the LPC studies use 50% as the threshold (\(c=0.5\) corresponds to the classic 0-1 loss), there are more general choices. For example, [2] uses CART to determine which forest zone has a higher than \(c=61\%\) probability of forest fire to implement early warning systems. In some other cases, a policymaker may face budget constraints and hence, decides to adopt a threshold that is close to 1 [3]. In the rest of this paper, we use \(c \in (0,1)\) to denote the threshold. We assume that \(c\) is fixed before implementing our methods. In particular, policymakers can first tune \(c\) with CART and then implement our methods with the chosen \(c\). In this scenario, our methods still improve over CART because our theoretical results apply broadly to any fixed \(c \in (0,1)\).

Extending to Knowledge distillation: Knowledge distillation (KD) refers to a two-step learning algorithm. The first step trains a teacher model with a higher learning capacity, e.g., a neural network or a random forest, to learn \(\mathbb{P}(Y=1|X)\). The second step uses the learned \(\mathbb{P}(Y=1|X)\) as the response variable to train a simpler student model. The goal of the student model is to output a simple and interpretable representation of the teacher model’s knowledge. In our case, the student model is a CART. We refer the existing KD method with a CART student model as KD-CART. We apply the MDFS method to improve KD-CART and refer our proposed new method as KD-MDFS. This generalizes our contribution to a larger class of advanced tree-based methods.

Summary of contributions: Section 3 formulates the LPC problem from a wide range of empirical works and shows that split rule generated by CART/KD-CART is strictly dominated. Section 4 proposes MDFS, which point-identifies the unique best split rule assuming a unique intersection between \(\mathbb{P}(Y=1|X)\) and \(c\). In addition, we propose a consistent estimator for the MDFS split rule. Section 4.3 shows that MDFS generates policies that target more vulnerable subpopulations. To relax the unique intersection assumption, we further propose PFS and wEFS in Section 5. Lastly, in Section 6, we demonstrate that the proposed methods outperform their respective baselines and target more vulnerable subpopulations, using simulations with synthetic and real-world datasets.

2 Related literature↩︎

The novelty of our problem setup can be best established by comparing our work with various strands of existing frontier literature.

Nonparametric binary classification: Nonparametric binary classifiers are often not designed for transparent policymaking. [4]’s theorems apply to uninterpretable deep learning. [5] outputs stochastic decision rules, which raise fairness concerns. Our output policy is nonparametric, interpretable, and deterministic.

Policy targeting: Most of the existing policy targeting literature has been developed within the causal inference framework [6]–[8]. Such causal inference methods are incompatible with the LPC setup, where the treatment might not have been tested in real life. A more detailed comparison between LPC and policy learning literature is provided in Appendix 8.2.

Tree-based methods’ consistency: The tree-based method literature has a vested interest in consistency. [9], [10] show that different tree-based methods are consistent for estimating \(\mathbb{P}(Y=1 | X)\). This work is interested in a different type of consistency. We show that our estimator consistently estimates the MDFS split rule.

Knowledge distillation with CART as student: [11], [12] use CART as the student model in knowledge distillation, termed as KD-CART in our paper. We show that the theoretical results we develop for MDFS apply to KD-CART.

3 Preliminaries: (OSF)LPC↩︎

We first restrict the theoretical discussion to the following one-split, one-feature (OSF) LPC problem characterized as follows. Let \(\mathcal{X} = [0,1]\) and \(\mathcal{Y} = \{0,1\}\) be the univariate feature space and label space, respectively. Let \(f: \mathcal{X}\xrightarrow[]{}\mathbb{R}^{+}\) be a probability density function that is continuous on \(\mathcal{X}\), \(F\) be its corresponding cumulative distribution function, and \(\eta(x) := \mathbb{P}(Y=1|X=x)\) be continuous. Consider a dataset comprising \(n\) i.i.d. samples, \((X_i, Y_i),\,i=1,\dots,n\), where \(X_i\sim f\) and \(Y_i|X_i\sim \text{Bernoulli}(\eta(X_i))\). A policymaker is allowed to split the feature space one time (i.e. one-split) using the univariate feature \(X\) (i.e. one-feature). After the split, policymakers target those node(s) whose node mean is greater than \(c\).

3.1 CART is strictly dominated↩︎

The most common criterion function optimized by CART to determine the split \(s^{CART}\) is the weighted sum of variances of the two child nodes, i.e., \(s^{CART} = \mathop{\mathrm{arg\,min}}_{s \in (0,1)} \mathcal{G}^{CART}(s)\) where \(\mathcal{G}^{CART}(s) = F(s)(\mu_L(s) - \mu^2_L(s)) + (1-F(s))(\mu_R(s) - \mu^2_R(s))\), \(\mu_L(s) =~ \int_0^s \eta(x) dF(x) / F(s)\) and \(\mu_R(s) =~ \int_s^1 \eta(x) dF(x) / (1 - F(s))\) are the left and right node mean, respectively.

To illustrate that \(s^{CART}\) is strictly dominated, we first introduce the following definition of strict dominance for comparing two splitting rules \(s\) and \(s'\). The definition is adapted from dominating decision rule in classic decision theory. To guide our readers through the dense notation in Definition 1, we provide an intuitive explanation after introducing the definition.

Despite its dense notation, Definition 1 has a straightforward interpretation: split rule \(s'\) strictly dominates \(s\) if it performs no worse than \(s\) for all \(x \in [0,1]\) and strictly better than \(s\) for all \(x \in {\cal A} \subseteq [0,1]\), where \(\cal A\) has nonzero measure.¹

We show that under very general conditions, there exist some rules that strictly dominate CART’s split rule in Theorem 1. Proofs of all lemmas and theorems are collected in Appendix 9.

The key challenge in understanding Theorem 1 is the interpretation of \(s^*\). Figure 1 (a) provides a graphical illustration for interpreting \(s^*\). Given that \(\eta(s^{CART}) < c = 0.5\) and \(\mu_L(s^{CART}) > \mu_R(s^{CART})\), Figure 1 (a) corresponds to the first minimization problem in the definition of \(s^*\). The minimization problem searches for \(s^*\) over the intersection of \(s \in (0,s^{CART})\) and \(s \in \{s: \eta(s) = c\}\), where \(s^{CART} = 0.5\). In Figure 1 (a), there are two candidate values, \(s = \frac{1}{12}\) and \(s = \frac{5}{12}\), between which \(s=\frac{5}{12}\) is closer to \(s^{CART}\), and hence \(s^* = \frac{5}{12}\). The graphical illustration is generalizable: \(s^{CART}\) determines which of the two minimization problems is used to determine \(s^*\), then \(\eta(s) = c\) pins down a set of candidate values of \(s^*\), and lastly, \(s^*\) is set to be the one that is closest to \(s^{CART}\) among all candidate values.

3.2 KD-CART is strictly dominated↩︎

In the LPC setup, a teacher model learns \(\eta(x), x\in[0,1]\). Prediction based on the teacher model is denoted as \(\hat{\eta}(x)\). In the LPC setup, the student model is a CART that takes in \(\hat{\eta}(x)\) as the response and learns to partition the population based on \(\hat{\eta}(x)\). One can show that Theorem 1 also applies to KD-CART, meaning there exist split rules that strictly dominates the split rule generated by KD-CART. Details are provided in Lemma 4 in Appendix 9.

4 MDFS↩︎

The suboptimality of CART for solving OSF LPC problem motivates our proposed method MDFS, which point-identifies \(s^*\). Since our theoretical results apply to OSF LPC, we advocate using our methods at the final splits with features identified by CART.² Restricting modifications to the last splits may appear trivial at first, however, note that as the tree grows deeper, the number of final splits increases exponentially, leading to non-trivial modifications to the policy designs. We substantiate this claim with empirical applications in Section 6.2.

4.1 Identification and estimation of MDFS↩︎

We argue for the plausibility of Assumption 1 in Section 4.2.

The proof of Theorem 2 can be largely decomposed into two steps: first, we show that there exists an interval containing \(s^*\) in which first-order condition guarantees that \(s^*\) is the local minimum; second, we show that for all \(s\) outside of the interval, \(\mathcal{G}^*(s,c) < \mathcal{G}^*(s^*,c)\).

Theorem 2 states that \(s^*\) maximizes the population objective function \({\cal G}^*(s,c)\). In the finite sample regime (denote sample size as \(n\)), we can estimate the sample version of \(s^*\) using \(\{(X_i,Y_i)\}_{i=1}^{n}\) by maximizing the sample analogue of \({\cal G}^*(s,c)\). Following from Assumption 1, we have \(s^{*} \in (\epsilon,1-\epsilon)\). Define the MDFS final split estimator \(\hat{s}\) as \[\begin{align} \hat{s} = \mathop{\mathrm{arg\,max}}_{s\in(\epsilon,1-\epsilon)} \widehat{{\cal G}}^*(s,c), \notag \end{align}\] where \(\widehat{{\cal G}}^*(s,c) = s ~ \Bigg| \frac{\sum_{i=1}^{n} Y_i\mathbb{1}\{X_i \leq s\}}{\sum_{i=1}^{n}\mathbb{1}\{X_i \leq s\}} -c \Bigg|+ (1-s) \Bigg| \frac{\sum_{i=1}^{n} Y_i \mathbb{1}\{X_i > s\}}{\sum_{i=1}^{n}\mathbb{1}\{X_i > s\}} -c \Bigg|\) is the estimator of \({\cal G}^*(s,c)\). The following theorem states that \(\hat{s}\) is a consistent nonparametric estimator for \(s^*\).

4.2 Plausibility of Assumption 1↩︎

Uniform \(X\). The set of quantile statistics for any continuous feature follows a uniform distribution, so we can convert a continuous variable to its quantile statistics. For a discrete \(X\), the LPC problem is simpler. We defer the explanation to Appendix 9.

The unique intersection condition is weaker than monotonicity, which is assumed by some theoretical works on CART [13]. Moreover, in many real-life applications, the monotonicity of \(\eta(X)\) is a reasonable assumption. For example, in our real-world dataset application in Section 6.2, a final node is split based on blood glucose level, and the binary outcome \(Y\) is diabetic status. It is reasonable to assume that the probability of diabetes increases with blood glucose level. Nevertheless, monotonicity is not necessary, see Figure 1 (b) as a non-monotonic example that satisfies Assumption 1.

Further, when we apply MDFS to the final nodes, the splitting feature is determined by CART. CART selects the splitting feature that gives the greatest reduction in variances (i.e., the greatest increase in purity in binary classification). Hence, when many features are available, CART is likely to pick some features that exhibit a salient trend (e.g., monotonicity), ruling out features that are more likely to violate the unique intersect assumption. Also, as we go down the tree, the domain of all nodes becomes smaller and smaller, making Assumption 1 easier to satisfy. For example, take Figure 1 (a) as an example. It violates the unique intersect assumption. However, if we split the population at \(X = 0.3\), then both child nodes will satisfy the unique intersection assumption.

4.3 Policy significance of MDFS↩︎

This section relaxes the OSF LPC setup and consider the policy relevance of MDFS under many-node many-feature setup. We demonstrate two advantages of MDFS policies: (i) targeting more vulnerable subpopulations than CART by using the same amount of resources and (ii) uncovering subgroups with a higher-than-threshold probability of event \(Y=1\) that CART ignores.

Suppose there are two nodes \(\{t_1,t_2\}\) with the same amount of population and corresponding features \(X_1,X_2 \sim \rm{Unif}(0,1)\). We depict \(\eta_1(X_1)\) for node \(t_1\) in Figure 1 (b) and \(\eta_2(X_2)\) for node \(t_2\) in Figure 1 (c). The analytical forms of \(\eta_1(X_1)\) and \(\eta_2(X_2)\) are provided in Appendix 9. Here we compare the targeted population using MDFS policy versus CART policy. Splitting nodes \(t_1\) and \(t_2\) individually at \(s^{CART}\) versus \(s^*\) results in different target subpopulations: \(s^{CART}\): Target \(\{X_1<\frac{1}{2}\}\) in \(t_1\). \(s^*\): Target \(\{X_1<\frac{5}{12}\}\) in \(t_1\) and \(\{\frac{11}{12}<X_2<1\}\) in \(t_2\). The two sets of policies target the same proportion of the population, but \(\eta_1(x_1) < 0.75\) for \(x_1 \in \{\frac{5}{12}<X_1<\frac{1}{2}\}\), which is targeted by \(s^{CART}\), whereas \(\eta_2(x_2) > 0.75\) for \(x_2 \in \{\frac{11}{12}<X_2<1\}\), which is targeted by \(s^*\). Therefore, policies based on LPC target a more vulnerable subpopulation than CART/KD-CART policy. Admittedly, the fact that LPC and CART policies target the same proportion of the population in the previous example is by construction. It is also possible that the proportion of the population targeted by the MDFS policy is bigger than that by CART or KD-CART. In this scenario, comparing the effectiveness of the two sets of policies is not straightforward. Nonetheless, LPC still has policy significance. It discovers new latent groups with a higher-than-\(c\) probability of an adversarial event happening to them (i.e., vulnerable subpopulations), e.g., \(\eta_2(x_2) > 0.75\) for \(\frac{11}{12} < x_2 < 1\).

We make two remarks to formalize the two advantages that the MDFS policy offers. Assuming a homogeneous targeting cost per unit of population, the targeting cost of a policy is the percentage of the subpopulation targeted. Denote all \(M\) final splitting nodes as \(\{t_1,t_2,\dots,t_M\}\) and \(\mathcal{M} = \{1,2,\dots,M\}\). For node \(m\), we denote the feature selected by CART as \(X_{(m)}\) and the CDF of \(X_{(m)}\) as \(F_m\) and let \(\eta_m(x) = \mathbb{P}(Y=1|X_{(m)} = x)\). The cost of CART and MDFS policies are \[\begin{align} C^{CART}=& \sum_{m \in \mathcal{M}} \int_{0}^{1} \mathbb{1}\{\mu_{t(x)}(s^{CART}_m) > c\} dF_m(x) \\ C^{*}=& \sum_{m \in \mathcal{M}} \int_{0}^{1} \mathbb{1}\{\mu_{t(x)}(s^{*}_m) > c\} dF_m(x) \end{align}\] Assume that for some \(~ m \in \mathcal{M}, ~s^{CART}_m \neq s^{*}_m\).

5 sec:PFS32and32wEFS↩︎

To relax Assumption 1, we propose two additional methods: PFS and wEFS.

5.1 PFS↩︎

Intuitively, if \(\mu_L\) is close to \(c\) and it is slightly higher than \(c\), by the continuity assumption on \(\eta(x)\), it’s likely that there is a considerable amount of subpopulation from the left node with \(\eta(x) < c\), see \(0<x<\frac{1}{12}\) and \(\frac{5}{12}<x<\frac{1}{2}\) in Figure 1 (a) as examples. This can substantially increase misclassification cases because \(\mu_L\) and \(\eta(x)\) are on different sides of \(c\) for all these \(x\) values. Following this intuition, we consider adding a penalty to \(\mathcal{G}^{CART}\) that pushes \(\mu_L\) and \(\mu_R\) away from \(c\). Let \[\begin{align} &\mathcal{G}^{PFS}(s,c) = \mathcal{G}^{CART} + \lambda J \label{G95pfs} \end{align}\tag{1}\] where \(J = F(s) W(|\mu_L - c|) + (1-F(s)) W(|\mu_R - c|)\) and \(W: \mathbb{R}^{+} \cup 0 \to \mathbb{R}^{+}\cup 0\) is a decreasing function that penalizes small distances between the node means (i.e., \(\mu_L\) and \(\mu_R\)) and \(c\), and \(\lambda\ge0\) controls the weight of the penalty term, which we denoted as \(J\). The following theorem states that under some regularity conditions of the function \(W\) and weight \(\lambda\), the split rule that minimizes \({\cal G}^{PFS}\), denoted as \(s^{PFS}\), strictly dominates \(s^{CART}\).

We provide an intuitive explanation for Theorem 6 in Appendix 9. Note that MDFS is a special case of PFS whose \(\lambda = \infty\) and \(W\) is the identity function.

5.2 wEFS↩︎

We adapt cost-sensitive classifier from [14] to our setup and name it weighted Empirical Final Split (wEFS). Due to the lack of theoretical backing, we do not elaborate on wEFS. We defer the explanation for the lack of the theoretical results to Section 7. Details about wEFS can be found in Algorithm 5 in Appendix 10.2.

6 Experiments↩︎

In this section, we conduct comprehensive numerical experiments to compare the performance of our proposed methods and the classic CART under both regular and KD frameworks. Under regular framework, we compare the classic CART with MDFS, PFS, and wEFS. Under KD framework, we compare RF-CART with RF-MDFS. We replace KD with RF because the teacher model is a Random Forest.

6.1 Synthetic data↩︎

Settings: We simulate synthetic datasets using 8 different data generation processes (DGP), e.g., the Friedman synthetic datasets [15], [16]. These setups are designed to capture various aspects of real-world data complexities and challenges commonly encountered when using tree-based methods, such as nonlinear relationships, feature interactions, collinearity, and noises (subtitles in Figure 2). Detailed descriptions of the DGP are provided in Appendix 10.1. For each DGP, we consider a threshold of interest \(c\in\{0.5, 0.6, 0.7, 0.8\}\), resulting in 32 unique tasks.

We set two stopping rules for growing the tree: (i) a max depth of \(m\in\{4, 5, 6, 7\}\), (ii) a minimal leaf node size of \(\rho n\), where \(\rho \in \{1\%, 2\%, 3\%\}\) and \(n\) is the sample size. We set \(n = 5000\). The fitting procedures stop once either of the rules is met. These give us 12 configurations for each tasks. For each of the \(32\times 12 = 384\) settings, we do 50 replicates of experiments.

Evaluation metrics: We define false positives (FP) and false negatives (FN) before defining the two performance metrics that we use in the synthetic data simulations. \[\begin{align} FP =& \sum_{i=1}^n\mathbb{1}\{\hat{T}(\mathbf{X}_i) \leq c\}\mathbb{1}\{\eta(\mathbf{X}_i) > c\} \\ FN =& \sum_{i=1}^n\mathbb{1}\{\hat{T}(\mathbf{X}_i) > c\}\mathbb{1}\{\eta(\mathbf{X}_i) \leq c\} \end{align}\] where \(\mathbf{X}_i\) is the multivariate feature vector which includes all features in the simulation and \(\widehat{T}(\mathbf{X}_i)\) is the tree-estimate of \(\eta(\mathbf{X}_i)\).

We use two metrics to evaluate the performance and robustness of all methods: misclassification rate (MR) and F1 score (F1). MR and F1 are defined as \[\begin{align} \text{MR} =& \frac{1}{n} (FP + FN) \\ \text{F1} =& \frac{1}{n} \frac{2(n-FP)}{2(n-FP)+FP+FN} \end{align}\] Given that our theorems state that split rules generated by (RF-)MDFS and PFS strictly dominate (RF-)CART, we expect that our proposed methods outperform their counterpart in both metrics.

Model fitting procedures: As we mentioned in Section 4, our methods and their counterparts only differ in the splits at the final level (final splits). We first implement CART until the final split is reached based on the stopping rules. Once the final split is identified, we select the splitting feature using CART, then implement MDFS, PFS and wEFS with the selected splitting feature. MDFS and PFS decide the split by optimizing \(\mathcal{G}^*\) and \(\mathcal{G}^{PFS}\), respectively, while wEFS selects the split by identifying \(s\) such that the minimum weighted empirical risk is obtained.

For \(W\) in \(\mathcal{G}^{PFS}\) from 1 , we choose \(W(d) = 1 - d\). This choice of \(W\) satisfies conditions specified in Theorem 6. We also experiment with alternative choices, such as \(W(d)=(1-d)^2\) and \(W(d)=\exp(-d)\), but observed similar performance across these choices. Based on Theorem 6, we set \(\lambda=0.1\), a sufficiently small value that presumably satisfies the conditions of the theorem while maintaining practical effectiveness. We also propose a standard \(\lambda\) selection procedure inspired by cross-validation and the honest approach [17] (see details in Appendix 10.3).

Comparison against respective baselines: Figure 2 provides a pairwise evaluation of MR differences between CART and its three refinements—MDFS, PFS and wEFS, and between RF-CART and RF-MDFS. Each boxplot depicts the distribution of the MR difference for a single DGP across 50 replicates, with \(m=7, \rho = 2\%, c=0.5\). Tables beneath the boxplots report one-sided p-values from paired t-tests (mean \(<\) 0) and Wilcoxon signed-rank tests (median \(<\) 0). Except for a few cases in Ball, Friedman #1, and Ring, MDFS and RF-MDFS reduce both the mean and the median MR relative to their counterparts, CART and RF-CART, at the 5\(\%\) significance level. PFS and wEFS outperform CART in most cases, but have less stability than MDFS, as evidenced by their large p-values in a few cases.

The comparison in terms of F1 is similar. All proposed methods largely outperform their counterparts at the 5\(\%\) significance level. We defer this result to Appendix 10.4.

RF-MDFS has the strongest performance among six methods: Our methods have a clear advantage over their respective baselines, as shown by Figure 2. In addition, we compare all six methods together, instead of pair-wise comparison. RF-MDFS performs the best out of all six methods on 26 out of the 32 tasks in terms of MR, 27 out of 32 tasks in terms of F1, as shown by Table 1 and Table 2 in Appendix 10.4. These results highlight the strength of combining MDFS with KD-CART, a frontier tree-based algorithm.

6.2 Real-world datasets↩︎

We implement CART, MDFS, RF-CART and RF-MDFS with the Pima Indians Diabetes dataset [18] to demonstrate the policy significance of our proposed methods.³ The Pima Indians Diabetes dataset measures health factors among Pima Indian women with the response variable being a binary indicator of diabetes status: 34.9% of the sample is diabetic. It contains 768 observations and 8 features: number of pregnancies, glucose level, blood pressure, skin thickness, insulin level, BMI, family diabetes history index, and age. We use these eight features to search for subpopulations whose probability of having diabetes is above 60% with depth of trees fixed at \(m=3\). We pick these hyperparameter values so that one set of the empirical results match Remark 4. We also experimented with other hyperparameter values. The results from these additional experiments align with Remark 5.

CART vs MDFS: As shown in Figure 3, CART and MDFS commonly target those with \({\rm Glucose} > 129.5\) and \({\rm BMI} > 29.95\), which consists of 188 observations. The two methods’ targeting policies differ in two ways: CART additionally targets \(127.5 < {\rm Glucose} \leq 129.5\) and \({\rm BMI} > 29.95\). This subgroup consists of 19 observations. MDFS additionally targets \({\rm Glucose} > 166.5\) and \({\rm BMI} \leq 29.95\). This subgroup consists of 12 observations. The difference between the sizes of these two subgroups is 7, which is small relative to 188, i.e., the size of the subgroup commonly targeted by both policies. Assuming that the sample is representative of the population of all Pima Indian women, then the two sets of policies will incur a similar amount of targeting resources. The additional group targeted by CART has a 57.9% probability of having diabetes, whereas the additional group targeted by MDFS has a 66.7% probability of having diabetes. MDFS targets a subpopulation that is more prone to diabetes. This corresponds to Remark 4.

RF-CART vs RF-MDFS: As shown in Figure 3, both RF-CART and RF-MDFS commonly target \({\rm Glucose} > 157.5\) and \({\rm BMI} > 29.95\), a subgroup consisting of 92 observations. RF-MDFS additionally targets two subgroups: \({\rm Glucose} > 166.5\) and \({\rm BMI} \leq 29.95\) consisted of 12 observations and \(129.5 < {\rm Glucose} \leq 157.5\) and \({\rm BMI} > 29.95\), which consisted of 96 observations. RF-MDFS targets a much greater number of observations than RF-CART. If the sample is representative of the population, then RF-MDFS would use much more targeting resources than RF-CART. Nevertheless, RF-MDFS is useful in uncovering groups with higher than 60% probability of having diabetes that RF-CART is unable to find. For example, the first group that RF-MDFS additionally targets has a 63.6% probability of having diabetes. This aligns with Remark 5.

7 Further literature and conclusion↩︎

Cost-sensitive binary classification: LPC can be related to the cost-sensitive binary classification problem, further highlighting the policy significance of the LPC problem. [14], [19], [20] show that the optimal classifier of a cost-sensitive binary classification problem is determined by whether the latent probability is above some performance-metric-dependent threshold. Whether the theoretical results in the cost-sensitive classification literature carry over to our setup is unclear. For example, [19] shows risk consistency with uniform convergence of the empirical risk. In our setup, \(\{\mu_L(s),\mu_R(s)\}\) appear inside the indicator functions, and uniform convergence of empirical risk is not guaranteed even with a large sample. In another related work, [14] proves risk-consistency of weighted ERM assuming that the policymakers search through all real-valued functions. By definition, LPC searches binary-split-type policies only. The performance of wEFS is strong in our simulations, so it would be interesting to look into the theoretical property of wEFS in future research.

Subgroup discovery: [21]–[24] discuss a widely-used quality measure, called Weighted Relative Accuracy (WRAcc), in the subgroup discovery literature. Under the assumption that \(X \sim {\rm Unif}[0,1]\), \[\begin{align} \text{WRAcc}_L = F(s) \left( \frac{\int_{0}^{s}\eta(x) dx}{s} - \int_{0}^{1}\eta(x) dx \right) \end{align}\] where the subscript \(L\) indicates it is the WRAcc measure associated with the left node. \(\mathcal{G}^*\) is a generalization of \(\text{WRAcc}_L + \text{WRAcc}_R\). Hence, Theorem 2 applies to a combination of CART and WRAcc.

Conclusion: Our paper points out that classic CART/KD-CART is suboptimal for LPC in each split. Based on different assumptions, we propose three alternative methods: MDFS, PFS and wEFS. MDFS and PFS generate policy rules that strictly dominate CART. Our proposed methods predominantly outperform their counterparts in our simulation and provide more policy insights in real-world applications.

8 Additional literature reivew↩︎

8.1 Extensive use of CART for LPC setups↩︎

Traffic safety: [25] identifies potential sites of serious accidents in Brazil using different decision tree algorithms. Policymakers may choose to take more safety precautions at dangerous traffic spots whose probability of having a fatal accident is above a threshold. Other research that uses decision trees to identify dangerous traffic situations includes [26]–[28].

Fraud detection: [29]–[31] find conditions under which credit card fraudulent usage is likely to happen. Credit card companies can inform card owners when the probability of fraudulent usage is above a pre-specified threshold.

Mortgage lending: [32]–[34] predict different subpopulations’ mortgage (and other types of loan) default rates using a decision tree. Mortgage loan lenders can use the result to determine whether to deny a loan request. Another stream of literature on mortgage lending using decision trees focuses on racial discrimination [35]–[37]. Policymakers may want to intervene in situations where with high enough probability race seems to play a role in determining whether mortgage lending is denied and the probability of denial is high.

Health intervention: [38]–[43] classify diabetes (or other diseases) using relevant risk factors. Such classification result leads to different health interventions. Doctors may recommend various treatments based on whether the subpopulation a patient belongs to is more likely to be classified as type I or type II diabetes.

Water management: One of the objectives of [44] is to manage flood control and output a threshold-based water resources management policy. The authors output a set of conditions that define the subpopulation whose probability of flooding is high enough to justify policy intervention. Many other studies also use decision trees to classify whether the water quality is satisfactory, resulting in important implications to water management policies [45]–[47].

8.2 Comparing LPC and policy learning/causal subgroup/individualized treatment rules↩︎

Policy targeting can be largely divided into two cases: policy targeting with treatment testing and policy targeting without treatment testing. The former is a burgeoning literature termed policy learning/causal subgroup/individualized treatment rules. The LPC framework falls under the latter, imposing no requirement on treatment testing. Here we provide two common scenarios where LPC is useful but policy learning is not possible.

What if the treatment cannot be/has not yet been tested in real life?

Our methods do not need a randomized control trial/quasi-experiment/instrumental variable for unconfoundedness, which is a key assumption for the policy learning literature. Experimental data (or observational data that satisfies unconfoundedness) is not always available.

For instance, in the case of tax credit programs (the example in our introduction), it is nearly impossible to experiment since the tax credit program is a one-time, urgent assistance package for households during financial crisis. Policymakers are unlikely to test out the assistance package with a random set of households and then evaluate how to allocate these assistance packages at the population level. There are two reasons. One, such an experiment is ethically questionable; two, by the time such an experiment is completed, the financial crisis might have already been over.

In such cases, classic policy learning is impractical. LPC can help refine policy design by identifying and targeting the subgroups that are more likely to be financially constrained. It is much faster for the policymakers (in this case, the Italian central bank) to collect data on households’ financial information (e.g., whether the household is financially constrained) than to experiment.

What if the policymakers do not have a specific treatment in mind?

Another scenario that happens often is that the policymakers may decide the treatment after finding the vulnerable subgroups. In this case, testing the treatment is not possible, since there is no treatment to begin with.

Example 1: traffic safety

[25] uses CART to find out that for the northern part of BR-116 (a highway in Sao Paulo, Brazil), the severe traffic rate (FSI in the paper) is higher than 50% (severe means involving human injury/death, the rate is the number of severe events divided by the total number of accidents). In contrast, the southern part of BR-116 has a higher than 50% FSI during the peak hours (12 pm to 6 pm) when there is drizzle. Policymakers can analyze these two geographic regions separately and use different interventions for the northern and southern parts of BR-116.

For the northern part, there might be some geographic features (maybe curvy turns) that make the road dangerous at all times, then installing traffic mirrors/stop signs/traffic lights at curvy turns would be good solutions. For the southern part, since it is during specific times, then sending out more traffic police during those hours to check on the speed limit would work better with minimal disruption to ongoing traffic.

Example 2: welfare take-up

Another example is [48], in their paper, they find subgroups among eligible households for WIC (a welfare program) who have a low probability of choosing to participate in WIC (they use random forest instead of CART). They then analyze which subgroup is less likely to participate for what reason: unawareness, limited usefulness, hassle or stigma. For different reasons, different interventions are suggested. For example, an information campaign is suggested for higher-educated subgroups, and choice-inducing strategies are suggested for those who are already in the programs.

In both examples, the treatment is decided after the subgroups are found. This is inherently contradictory to the premise of policy learning that treatment has to be tested before finding the targeting subgroups.

9 Mathematical appendix↩︎

We state a property of the CART splitting rule in Lemma 1. This is useful for establishing the rest of the theoretical results.

Proof of Lemma 1 needs the following lemma, which is proved after the proof of Lemma 1.

Proof for Lemma 1.

Proof for Lemma 2.

Proof for Lemma 3

Proof for Theorem 1

Theoretical property of KD-CART

To explore the theoretical property of KD-CART, we treat it as a CART that takes true \(\eta(x)\) as input and splits the population based on \(\eta(x)\). KD-CART uses criterion function \(\mathcal{G}^{KD} := F_X(s) {\rm Var}(\eta(X)|X\leq s) + (1-F_X(s)) {\rm Var}(\eta(X)|X> s)\).

The proof of Lemma 4 is almost identical to Lemma 1 and is omitted here. The key take away is Theorem 1 also applies to \(s^{KD}\), as proof of Theorem 1 only requires that \(\eta(s^{CART})\) is strictly between \(\mu_L\) and \(\mu_R\), Lemma 4 shows that \(\eta(s^{KD})\) satisfies this condition. As a result, KD-CART does not minimize the misclassification risk.

Explanation for discrete \(X\)

Say \(X \in \{a_1, a_2, \dots, a_K\}\) where \(a_1, a_2, \dots, a_K\) are ordered and \(a_1 < a_2 < \dots < a_K\). Assumption 1 (a discrete \(X\) version) would guarantee that for one unique split rule, for all possible values of \(X\) in the left node, \(\eta(X) > c\) and for all possible values of \(X\) in the right node, \(\eta(X) < c\), or vice versa. We can identify this unique rule by simply comparing \(\eta(a_k)\) and \(c\) for \(k = 1, 2, \dots, K\). Estimation boils down to estimating \(\eta(X)\) for finitely many \(X\), which is trivial.

We find it clearer to prove Corollary 2 and then plug in some of the steps in the proof for Corollary 2 into proof for Theorem 2. Hence, we first present the proof for Corollary 2.

Proof for Corollary 2

Proof for Theorem 2

Proof for Theorem 3

Intuition for Theorem 6

We use Figure 4 to illustrate the intuition behind Theorem 6 based on the same setting as that in Figure 1 (a). From top to bottom, Figure 4 depicts \(\mathcal{G}^{CART}\), penalty term \(J\), \(\mathcal{G}^{PFS}\) and LPC misclassification risk \(R\) as functions of feature \(X\). The green curve shows that \(\mathcal{G}^{CART}\) is minimized at \(s^{CART}\). The green curve is also very flat around \(s^{CART}\). In contrast, the blue curve shows that penalty \(J\) increases sharply at \(X=s^{CART}\). Minimizing \(J\) would shift the split rule from \(s^{CART}\) to the left, as indicated by the arrow. Since \(\mathcal{G}^{PFS} = \mathcal{G}^{CART} + \lambda J\), the gradient of \(\mathcal{G}^{PFS}\) at \(s^{CART}\) is largely determined by the gradient of \(J\), given how flat \(\mathcal{G}^{CART}\) is at \(s^{CART}\) (See the black curve). Hence, minimizing \(\mathcal{G}^{PFS}\) also shifts the split rule from \(s^{CART}\) to the left (i.e., towards \(s^*\), the minimizer of the LPC misclassification risk as shown by the red curve). Our formal proof in Appendix 9 shows that the flatness of \(\mathcal{G}^{PFS}\) and sharp change in \(J\) at \(X=s^{CART}\) and shifting \(s^{CART}\) towards \(s^*\) are not coincidences; they are generally true under the assumptions in Theorem 6.

Proof for Theorem 6

Mathematical details for Figure 1 (b) and 1 (c)

Imagine there are two final splitting nodes \(\{t_1,t_2\}\) with the same mass of population. CART selects features \(\{X_1, X_2\}\) for nodes \(\{t_1,t_2\}\), respectively. The pdf of \(X_1\) and \(X_2\) in the \(\{t_1,t_2\}\) are both uniform, respectively: \(f_1(x) = 1\) and \(f_2(x) = 1\) \(\forall~x \in [0,1]\).

In node \(t_1\), \[P(Y=1|X_1) = : \eta_1(X_1) = \begin{cases} 1, \text{ when X_1 \in [0,\frac{1}{4}]} \\ \frac{{\rm sin}(2 \pi X_1) + 1}{2} , \text{ when X_1 \in (\frac{1}{4},\frac{3}{4})} \\ 0, \text{ when X_1 \in [\frac{3}{4},1]} \end{cases}\]

We depict \(\eta_1(X_1)\) in Figure 1 (b). Since \(\eta_1(X_1)\) is reflectional symmetric around \(\eta_1(0.5)\), \(s^{cart} = 0.5\). Splitting \(s^{cart}\), policymakers target the left node \(X_1 \leq 0.5\) only, the calculation is similar to Figure 1 (a) in the introduction.

The unique optimal LPC solution is \(s^* = \frac{5}{12}\). By shifting from \(s^{CART}\) to \(s^*\), the policymaker excludes subpopulation \(\{\frac{5}{12}<X_1<\frac{1}{2}|t_1\}\) from the targeted group. Again, the mathematics is similar to Figure 1 (a) in the introduction.

In node \(t_2\), \[P(Y=1|X_2) =: \eta_2(X_2) = \frac{9}{11}X_2\]

The other node \(t_2\) is depicted by Figure 1 (c). CART will split \(t_2\) at \(s^{CART} = 0.5\) because \(\eta_2(X_2)\) is reflectional symmetric around \(\eta_2(0.5)\). This would not target any subpopulations from \(t_2\), as both the left node mean and right node mean are smaller than 0.75. \[\begin{align} &P(Y = 1| X_2 < 0.5) = \frac{\int_{0}^{0.5} \frac{9}{11} x dx}{0.5} = \frac{9}{44} < 0.75 \\ &P(Y = 1| X_2 > 0.5) = \frac{\int_{0.5}^{1} \frac{9}{11} x dx}{0.5} = \frac{27}{44} < 0.75 \end{align}\] On the other hand, the best split for LPC is \(s^* = \frac{11}{12}\). This splits \(t_2\) into two groups, the left node is entirely below the threshold whereas the right node is entirely above, as illustrated by the orange and green segment in Figure 1 (c), respectively. As a result, splitting at \(s^*\) targets subpopulation \(\{\frac{11}{12}<X_2<1|t_2\}\).

To summarize, splitting nodes \(t_1\) and \(t_2\) individually at \(s^{CART}\) versus \(s^*\) results in different target subpopulations: (i) \(s^{CART}\): Target \(\{X_1<\frac{1}{2}|t_1\}\); (ii) \(s^*\): Target \(\{X_1<\frac{5}{12}|t_1\}\) and \(\{\frac{11}{12}<X_2<1|t_2\}\). Assuming that both \(t_1\) and \(t_2\) contain the same amount of population, the two sets of policies target the same proportion of the population, but \(\eta(x,t_1) < 0.75\) for \(x \in \{\frac{5}{12}<X_1<\frac{1}{2}\}\), which is targeted by \(s^{CART}\), whereas \(\eta(x,t_2) > 0.75\) for \(x \in \{\frac{11}{12}<X_2<1\}\), which is targeted by \(s^*\). Therefore, policies based on LPC, i.e., \(s^*\) policy, target a more vulnerable subpopulation than policies based on observed \(Y\) classification, i.e., \(s^{CART}\) policy or CART/KD-CART policy. This idea appears in our diabetes empirical study, which we detail in Section 6.2.

Proof of Remark 7 \[\begin{align} \mathcal{G}^{\text{WRacc}} =& \text{WRacc of left node} + \text{WRacc of right node} \\ =& F(s) \left| \frac{\int_0^s \eta(x) dF(x)}{F(s)} - \int_0^1 \eta(x) dF(x) \right| + (1 - F(s)) \left| \frac{\int_s^1 \eta(x) dF(x)}{1 - F(s)} - \int_0^1 \eta(x) dF(x) \right| \\ =& F(s) \left| \mu_L - \int_0^1 \eta(x) dF(x) \right| + (1 - F(s)) \left| \mu_R - \int_0^1 \eta(x) dF(x) \right| \\ =& s \left| \mu_L - \int_0^1 \eta(x) dx \right| + (1 - s) \left| \mu_R - \int_0^1 \eta(x) dx \right| \quad \text{Under Assumption \ref{assumption32unique32intersection32between32eta32and32c}} \end{align}\]

10 Synthetic data simulation studies↩︎

10.1 Data generation processes↩︎

1. Generate features: \(X_i \sim U(0, 1), i\in \{1,2,3,4,5\}\).

2. • Ball: \(f(X) = \sum_{i=1}^3 X_i^2\).

   • Friedman #1: \(f(X) = 10 \sin(\pi X_1 X_2) + 20(X_3 - 0.5)^2 + 10 X_4 + 5 X_5\)

   • Friedman #2:

     • Make transformations: \(Z_1 = 100 X_1, Z_2 = 40\pi + 520\pi X_2, Z_4 = 10X_4 + 1\)

     • Generate responses: \(f(X) = \sqrt{Z_1^2 + (Z_2 X_3 - \frac{1}{Z_2 Z_4}) ^2 }.\)

   • Friedman #3:

     • Make transformations: \(Z_1 = 100 X_1, Z_2 = 40\pi + 520\pi X_2, Z_4 = 10X_4 + 1\)

     • Generate responses: \(f(X) = \arctan\left((Z_2X_3 - \frac{1}{Z_2 Z_4})/Z_1\right).\)

   • Poly #1: \(f(X) = 4X_1 + 3X_2^2 + 2X_3^3 + X_4^4\)

   • Poly #2: \(f(X) = X_1^4 + 2X_2^3 + 3X_3^2 + 4X_1\).

   • Ring: \(f(X) = |\sum_{i=1}^3 X_i^2 - 1|\).

   • Collinear:

     • Create correlated features: \(X_{i+3} = X_i + 0.1 \cdot \mathcal{N}(0, 1)\), where \(i\in\{1,2,3\}\).

     • Generate responses: \(f(X) = \sum_{i=1}^6 X_i\).

3. Map it to probabilities: \(\eta = \text{Sigmoid}\left(f(X)-E(f(X))\right)\).

4. Generate labels: \(y \sim \text{Bernoulli}(\eta)\).

10.2 Full algorithms↩︎

We provide pseudo codes for CART, PFS, MDFS, wEFS, RF-CART, and RF-MDFS. In Algorithm [grow95tree], setting ‘method’ to CART, PFS, MDFS, or wEFS invokes the corresponding procedure. Likewise, in Algorithm [grow95tree95wp], choosing method = CART or MDFS produces RF-CART and RF-MDFS, respectively. The rest of the algorithms are all helper functions used in Algorithms [grow95tree] and [grow95tree95wp].

How to implement KD-CART/KD-MDFS: We first use RandomForestClassifier from sklearn [50] to train a random forest with the entire sample. All user-defined parameters of the random forest follow the default settings. Then, we grow an RF-CART and an RF-MDFS tree with the predicted probability output by the random forest as the response variable.

10.3 Choice of hyperparameter \(\lambda\)↩︎

Our simulations regarding PFS choose a small \(\lambda\) value of 0.1, and overall, this choice leads to lower misclassification error than CART. To identify an appropriate \(\lambda\) in practice, we had a standard procedure: we select the \(\lambda\) value using an approach that combines the idea of cross-validation and the honest approach [17]:

1. Divide the data into \(K = 5\) folds. For a fixed candidate \(\lambda\) value, by leaving out fold \(k \in \{1, 2, 3, 4, 5\}\), we can construct 5 trees, \(T^{-k}\). Denote \(T^{-k}\)’s estimate for \(X\) as \(T^{-k}(X)\).

2. Obtain an unbiased estimate of \(\eta\) for each node by feeding the left-out fold to \(T^{-k}\). Denote this estimate for \(X\) as \(\hat{\eta}^k(X)\).

3. Calculate misclassification score (MS) (i.e., honest approach), \[\text{MS} = \sum_{k=1}^{5} \sum_{i \in \text{fold }k} \mathbf{1}\left\{(T^{-k}(X_i) - c)(\hat{\eta}^k(X_i) - c) < 0\right\}.\]

4. Choose \(\lambda\) value that minimizes MS.

We implemented this approach in simulation for PFS, the results are comparable to setting \(\lambda = 0.1\).

10.4 Additional simulation results↩︎

Refer to Figure 9 and Table 1.

10.5 Computational complexity analysis↩︎

Since our proposed algorithm only operates at the last split, the tree-building processes are identical in upper levels among 4 strategies. Next, we evaluate the computational complexity of the final split, i.e., split at the final level.

Suppose the sample size in a node at the second to last level is \(n\) and the number of features is \(p\). In CART, the dominant step is to sort the samples based on each feature. With \(p\) features to consider, the computational complexity is \(O(pNlogN)\). PFS, MDFS, and wEFS all determine the feature to split on using CART. The split point decision requires another \(O(N)\) of time which is still dominated by the sorting process.

11 Additional empirical study details↩︎

We use publicly available data from our empirical studies. The Pima Indian Diabetes dataset can be downloaded at https://www.kaggle.com/datasets/uciml/pima-indians-diabetes-database. The Montesinho Park forest fire dataset can be downloaded at https://archive.ics.uci.edu/dataset/162/forest+fires. In this section, we use forest fire dataset to illustrate an application of our methods MDFS and RF-MDFS, and compare them to CART and RF-CART respectively.

The UCI Forest Fire dataset measures the characteristics of different forest fires in Montesinho Park with the response variable being the area burnt by a forest fire. We binarize the response by labeling those observations with a burnt area larger than 5 as 1, and 0 otherwise. 1 indicates a “big” forest fire. We search for conditions under which the probability of having a big forest fire is above 1/3. We use the following features in the dataset for this task: X and Y-axis spatial coordinates, month, FFMC, DMC, DC, ISI, temperature, RH (relative humidity), wind, and rain. All the acronyms except for RH are measures that positively correlate with the probability of a big forest fire. With a moderate sample size of 517, we set \(m=3\).

11.1 CART vs MDFS↩︎

As shown by Figure 3, the two sets of policies target many common groups except for the subgroup consisting of 43 observations defined by \(FFMC > 85.85\), \(temp \leq 26.0\), \(DC > 766.2\). This group that MDFS additionally targets has a 37.2% probability of catching a big forest fire, higher than the threshold. This finding aligns with Remark 5.

11.2 RF-CART vs RF-MDFS↩︎

As shown by Figure 3, RF-MDFS also additionally targets the subgroup consisting of 43 observations defined by \(FFMC > 85.85\), \(temp \leq 26.0\), \(DC > 766.2\). Hence, the comparison between RF-CART and RF-MDFS here also aligns with Remark 5.

Interestingly, both RF-CART and RF-MDFS (compared to CART and MDFS respectively) additionally target the subgroup \(FFMC > 85.85\), \(temp > 26.0\), \(RH \leq 24.5\).

11.3 Full CART/MDFS/RF-CART/MDFS for the diabetes example↩︎

References↩︎