# Unbiased Isotonic Regression Tree for Discovering Hidden Heterogeneity in Monotonicity Constraints
## 3 The Proposed Approach
### Overall Framework and Optimization of UIRT  
This section outlines the overall framework of UIRT by combining the individual components described in the previous sections. The framework first defines the unified objective function of UIRT and explains the steps for deriving the final solution. Note that the objective function in UIRT does not admit a closed-form solution. Similarly to traditional regression trees, their non-linear and piecewise nature makes analytical derivation infeasible. Also, the addition of monotonicity constraints further increases the complexity of the problem. As a result, recursive and iterative methods are essential to systematically explore the solution space and find the optimal solution. The goal of UIRT is to partition the dataset \(\mathcal{D}=\{(x_{i},\ y_{i},\ z_{i})\}_{i=1}^{n}\) into disjoint regions \(R_{1},\ R_{2},\ \ldots,\ R_{m}\) such that the overall prediction error is minimized while ensuring monotonicity constraints. In doing so, UIRT can identify heterogeneous monotonic trends hidden in the dataset. The unified objective function is as follows:  
\[\min_{\{R_{k}\},\hat{\mathcal{G}}}\sum_{k=1}^{m}\sum_{(x_{i},\ y_{i})\in R_{k} }\bigl{(}\hat{\mathcal{G}}_{k}(x_{i})-y_{i}\bigr{)}^{2}, \tag{3}\]  
\[\text{subject to }\hat{\mathcal{G}}_{k}(x_{i})\leq\hat{\mathcal{G}}_{k}(x_{j}) \forall x_{i},\ x_{j}\in R_{k},\ x_{i}\lesssim x_{j}\]  
where \(R_{k}\) is a region resulting from the split and \(\hat{\mathcal{G}}_{k}(x_{i})\) represents the isotonic regression in region \(R_{k}\). Other components in the objective function (3) are already mentioned in the previous sections. This formulation enforces the fact that the function \(\hat{\mathcal{G}}_{k}\) in each region is monotonic with respect to the partial order \(x_{i}\lesssim x_{j}\). The solution to the objective function (3) is obtained through the following steps:  
* _(Step 1) Fitting isotonic regression:_ for the current node \(R_{k}\), isotonic regression fits a monotonic function \(\hat{\mathcal{G}}_{k}\) that minimizes the sum of squared errors. The local isotonic regression problem is expressed as follows: \[\min_{\hat{\mathcal{G}}_{k}}\sum_{(x_{i},\ y_{i})\in R_{k}}\bigl{(}\hat{ \mathcal{G}}_{k}(x_{i})-y_{i}\bigr{)}^{2},\] (4) subject to \(\hat{\mathcal{G}}_{k}(x_{i})\leq\hat{\mathcal{G}}_{k}(x_{j})\forall x_{i}, \ x_{j}\in R_{k},\ x_{i}\lesssim x_{j}\). As explained in Section 3.2, the solution to the objective function (4) is obtained using the pool adjacent violators algorithm (PAVA), which efficiently enforces monotonicity by adjusting predictions iteratively. * _(Step 2) Unbiased split variable selection:_ The most significant covariate \(Z^{*}\) is selected using a chi-square test on residuals from the isotonic regression. For each covariate \(Z_{s}\), the statistical dependency between residuals \(r_{i}=y_{i}-\hat{\mathcal{G}}_{k}(x_{i})\) and \(Z_{s}\) in region \(R_{k}\) was evaluated using a chi-square test statistic \(\chi^{2}(r_{i},\ Z_{s})\). For the chi-square test, the null hypothesis assumed no dependency between residuals and the covariate \(Z_{s}\). The optimal covariate \(Z^{*}\) was determined if it exhibited the strongest dependecy at a significance level, \(\alpha\), accounting for multiple testing. * _(Step 3) Optimal cutpoint identification:_ After selecting the best-split variable \(Z^{*}\), UIRT performed an exhaustive search to determine the optimal cutpoint \(c^{*}\) for splitting the observations in region \(R_{k}\). The optimal cutpoint \(c^{*}\) that minimized the sum of squared errors across the resulting regions is expressed as follows: \[c^{*}=\text{argmin}_{c}\left[\sum_{q}^{n_{q}}\bigl{(}y_{q}-\hat{\mathcal{G}}_{ L}(x_{q})\bigr{)}^{2}+\sum_{w}^{n_{w}}\bigl{(}y_{w}-\hat{\mathcal{G}}_{R}(x_{w}) \bigr{)}^{2}\right]\] where \(n_{q}\) and \(n_{w}\) are the number of samples, and \(\hat{\mathcal{G}}_{L}(x_{q})\) and \(\hat{\mathcal{G}}_{R}(x_{w})\) are the fitted isotonic regression at nodes \(R_{L}=\{\mathbf{Z}|Z^{*}\leq c\}\) and \(R_{R}=\{\mathbf{Z}|Z^{*}>c\}\), respectively.