# Unbiased Isotonic Regression Tree for Discovering Hidden Heterogeneity in Monotonicity Constraints
## 3 The Proposed Approach
### Unbiased Split Variable Selection  
Ideally, the best choice for the split variable \(Z_{s}\) would be the covariate among \(\mathbf{Z}=\{Z_{s},\,1\leq s\leq l\}\), which is most strongly associated with the residuals in regression. In a well-fitting case, residuals should be randomly distributed around zero, showing no dependency on any covariates. If residuals show dependency on the particular covariate, it implies that the model could be refined further, and the current node should be divided by the covariate. Motivated by this idea, the proposed unbiased split variable selection in the isotonic regression tree is conducted by the following steps: First, fit isotonic regression and calculate residuals at the current node \(R\). Second, calculate signed residuals and construct a contingency table for each covariate \(Z_{s}\). Third, from the contingency table, the following \(\chi^{2}\) test statistic is computed for each covariate \(Z_{s}\):  
\[\chi^{2}=\sum_{k}^{up}\frac{\left(O_{k}-E_{k}\right)^{2}}{E_{k}} \tag{1}\]  
where \(O_{k}\) denotes the observed counts, \(E_{k}\) denotes the expected counts for each cell, respectively, and \(u\) is the number of rows and \(p\) is the number of columns in the contigency table. Under the null hypothesis \(H_{0}\) (i.e., signed residuals are not associated with the set of covariates \(\mathbf{Z}\)), the test statistic in Equation (1) follows a chi-square distribution with degrees  
Figure 2: Partitioning at each node in the proposed unbiased isotonic regression tree. of freedom equal to \((u-1)(p-1)\). \(H_{0}\) is rejected if \(\chi^{2}>\chi^{2}_{\alpha}\) where \(\alpha\) is a pre-determined significance level corrected for multiple \(l\) testings. Finally, the \(p\)-values of all covariates are compared in the chi-square test. The covariate with the smallest \(p\)-value is selected as the optimal split variable \(Z^{*}\) as long as it is below an adjusted significance level \(\alpha\). Note that GUIDE does not account for multiple testing when conducting a chi-square test for split variable selection. As a result, this can inflate Type I error rates, leading to erroneous node splits within the tree. Some related issues in implementing the proposed algorithm are addressed as follows:
* _Fitting isotonic regression_: Suppose that n pairs of observations \((x_{1},y_{1},z_{1})\), \((x_{2},y_{2},z_{2}),\ldots\)\((x_{n},y_{n},z_{n})\) are available at the current node \(R\). Isotonic regression is used to fit a function \(\mathcal{G}:\{x_{1},x_{2},\ldots,x_{n}\}\rightarrow\mathbb{R}\) that is monotonic and aligns with the observed data [47] at node \(R\). The predictors \(x_{1},x_{2},\ldots,x_{n}\) are allowed to take value from any domain that allows a partial order, denoted by \(\lesssim\). In this context, a function \(\mathcal{G}\) is said to increase if \(x_{i}\lesssim x_{j}\) implies \(\mathcal{G}(x_{i})\lesssim\mathcal{G}(x_{j})\), and isotonic regression is used to optimize the following objective function: \[\min\sum_{i=1}^{n}\left(\mathcal{G}(x_{i})-y_{i}\right)^{2}\text{ subject to }\mathcal{G}(x_{i})\leq\mathcal{G}(x_{j})\text{ for all }(i,\ j)\in T,\] (2) where \(T=\big{\{}\big{(}x_{i},\ x_{j}\big{)}\bigm{|}x_{i}\lesssim x_{j},\ i,\ j=1,2, \ldots,\ n,\ i\
eq j\big{\}}\)[48]. As the constraint in the formulation (2) defines a convex region in \(\mathbb{R}\) (specifically, a convex cone), the formulated optimization problem is convex in nature. This property allows the optimization problem to be solved efficiently using the pool adjacent violators algorithm (PAVA) [49]. * _Construction of contigency table_: Basically, a chi-square test is conducted using a contingency table. In a contigency table, each row corresponds to the signs of residuals (i.e., positive vs. non-positive), and each column represents the number of categories for a certain split variable. For categorical split variables, constructing this contingency table is straightforward. In contrast, continuous split variables require defined categories to build the table.