# Unbiased Isotonic Regression Tree for Discovering Hidden Heterogeneity in Monotonicity Constraints
## 2 Literature Review
### Integrating Constraints in Decision Trees  
Various efforts have been made to integrate constraints into decision tree models, with the aim of constructing models that are fair, free from bias, interpretable, and dependable [29]. In general, these types of constraints in decision trees are classified into structure-level, attribute-level, and instance-level constraints. Structure-level constraints can generally be set by any user to control the complexity and readability of the decision tree. Attribute-level and instance-level constraints are often defined by domain experts or derived through a constraint-mining algorithm based on their specific knowledge requirements.  
Structure-level constraints focus on designing learning algorithms that yield trees with specific structural properties, thereby enhancing interpretability and controlling overfitting. For example, limiting the size of the tree--defined by the number of nodes--can improve overall readability [30]. Similarly, constraining the depth of the tree is crucial for comprehensibility and to reduce overfitting by limiting how deep decisions must be made. Such trees favor learning shallow trees [31; 32], which helps prevent model complexity and enhance interpretability as well. Finally, the number of leaf nodes provides a summary of decision rules and helps regulate tree growth, making predictions for particular classes easier to interpret [30]. These structural constraints, by directly influencing the tree's readability, are vital for creating models that can be easily understood by practitioners.  
Attribute-level constraints are frequently guided by expert knowledge or constraint-mining algorithms, which often address monotonicity, attribute costs, and hierarchy constraints. Monotonicity constraints ensure that specific features influence the outcome in a consistent direction, which enhances the interpretability and trustworthiness of decision trees in sensitive applications [33]. To incorporate monotonicity, studies have adjusted traditional algorithms either by adapting their heuristic functions [34; 35; 36; 37] or applying post-pruning techniques that enforce these constraints. More recently, the isotonic regression tree (IRT) was developed to deal with the bid landscape forecasting task [21]. IRT relies on isotonic regression at each node to capture monotonically increasing relationships between the bid price and auction win probability. In this sense, IRT could also handle shape-constraints in decision trees. Hierarchical and feature interaction constraints are also critical, especially in domains where domain knowledge is essential. In contrast, attribute cost constraints focus on reducing dependency on expensive features, which is particularly valuable in fields like healthcare [38; 39]. In addition to monotonicity, attribute costs, hierarchy constraints, privacy, and fairness constraints are also considered [40; 41; 42; 43; 44].  
Instance-level constraints integrate domain knowledge into the decision tree by imposing conditions on specific data points (e.g., certain instances may not be incorrectly classified). Although this approach provides a high degree of control, its use is relatively limited due to the requirement for external- and instance-specific information often provided by domain experts. These constraints include must-link and cannot-link rules, which structure data partitioning and sampling, and considerations for adversarial robustness [45]. Notably, instance-level constraints emphasize the need for decision trees to be resilient against adversarial noise, particularly in settings involving white-box and black-box attacks. This robustness is critical to preserving trustworthiness and reliability in real-world applications [46].