\Omega \subset \mathbb{R}^d$ a vector of features and $Y_i \in \{0,\ldots,J-1\}$ a class label. The goal is to estimate a classifier $f: \Omega \to \{0,\ldots,J-1\}$, which outputs a class label given an input feature vector. This involves partitioning the feature space $\Omega$ into subsets having different class labels, as illustrated in Figure 1. Classification trees are particularly popular to their combined flexibility and interpretability. Competitors like deep neural networks (DNN; @schmidhuber2015deep) often have higher accuracy in prediction, but are essentially uninterpretable black boxes.

Our focus is on the case in which $n_j = \sum_{k=1}^n \bm{1}_{\{Y_i = j\}}$ is small, for one or more $j \in \{0,\ldots,J-1\}$. For simplicity in exposition, we assume $J=2$, so that there are only two classes. Without loss of generality, suppose that $j=0$ is the majority class, $j=1$ is the minority class, and call set $\{x\in\Omega: f(x)=1\}$ the decision set (of the minority class). Hence, $n_1$ is relatively small compared to $n_0$ by this convention.

To illustrate the problems that can arise from this imbalance, we consider a toy example. Let the sample space of $X$ be $\Omega = [0,1]\times[0,1]\subset \mathbb{R}^2$. Let the conditional distribution of $X$ given $Y$ be $X|Y=1 \sim U([0,0.75]\times[0.25,0.75])$, $X|Y=0 \sim U(\Omega)$. 