# Unbiased Isotonic Regression Tree for Discovering Hidden Heterogeneity in Monotonicity Constraints
## 2 Literature Review  
### Overview of Decision Trees  
The principle behind the decision trees involves recursively segmenting the predictor space into subgroups until the optimal fit is achieved. The segmentation involves selecting the best-split variable and corresponding cutpoint to maximize the improvement. Decision trees are referred to as classification trees for categorical responses and regression trees for continuous responses. Since the response variable in this study is an inherently continuous one, this study focuses on regression trees. Regression trees are further categorized into  
Figure 1: An example of isotonic regression trees.  
piecewise-constant and piecewise-linear types. Piecewise-constant trees make constant predictions based on the mean response, and piecewise-linear trees employ linear regression within each subgroup.  
The Classification and Regression Tree (CART) [24] is the most popular decision tree model for constructing piecewise-constant trees. CART identifies optimal splits by calculating the impurity at each node and selecting the split variable and cutpoint simultaneously, which minimizes the impurity across the resulting subnodes. To regulate tree size, CART initially grows a large tree and then prunes it back to find a subtree that minimizes the cross-validation error, which is known as post-pruning. Similarly, the Automatic Interaction Detection (AID) algorithm seeks optimal splits in the same fashion but restricts tree growth through pre-pruning, applying criteria such as a fraction of initial impurity [26].  
The foundational model for piecewise-linear regression trees is Smoothed and Unsmoothed Piecewise Polynomial Regression Trees (SUPPORT) introduced by [PERSON] et al. (1994) [27]. To identify optimal subnodes, SUPPORT performs split variable selection followed by determining the best cutpoint for the chosen variable. These two separate steps are able to reduce selection bias in choosing the split, which cannot be achieved by CART's simultaneous approach [25]. For variable selection, SUPPORT calculates residuals from a linear regression at each node across all variables and then divides the observations by the residual sign. For each variable, a two-sample \(t\)-test and Levene's test are performed to assess differences in means and variances between groups. If the differences are statistically significant, the most influential variable is chosen for splitting, and the cutpoint is set to the average of the sample means. The Generalized, Unbiased Interaction Detection and Estimation (GUIDE) algorithm builds on the foundations of SUPPORT but extends functionality [28]. GUIDE can handle both regression and classification problems, accommodating categorical predictors and interactions that SUPPORT does not. Prior to the learning tree, GUIDE defines the role of each predictor as splitting-only, regression-only, or both. Linear regression is then performed at each node using predictors designated for regression alone and both splitting and regression. Residuals are calculated, and they are categorized by their signs (i.e., positive vs. negative). A chi-square test assesses the relationship between residual signs and split variables, identifying associations by testing if residual signs are independent of split variables. As the chi-square test requires categorical data, continuous variables are discretized. The variable with the smallest \(p\)-value is then selected as the split variable, and its cutpoint is chosen by minimizing squared residuals in the resulting subnodes.