TLDR: RS-ORT is a new branch-and-bound algorithm for training optimal regression trees. It addresses limitations of existing methods by using a two-stage optimization that branches only on tree-structural variables, making it independent of dataset size. Key innovations include closed-form leaf predictions, empirical threshold discretization, and exact depth-1 subtree parsing. RS-ORT demonstrates superior accuracy, scalability, and interpretability on large datasets with continuous features, achieving provably optimal solutions where other methods fail or time out.
Researchers have introduced a new approach to building optimal regression trees, addressing long-standing challenges in handling continuous and large-scale datasets. The new method, called Reduced-Space Optimal Regression Trees (RS-ORT), offers a significant leap forward in machine learning, particularly for applications where both accuracy and clear interpretability of models are crucial, such as in medicine.
Optimal decision trees are highly valued for their ability to provide transparent predictions. However, existing methods, especially those based on mixed-integer programming (MIP), often struggle with regression tasks involving continuous data. These methods either require converting continuous features into binary ones, which can compromise the model’s overall best performance and lead to overly complex trees, or they become too computationally demanding for large datasets.
A Novel Two-Stage Optimization Approach
RS-ORT redefines the problem of training optimal regression trees as a two-stage optimization process. The first stage focuses exclusively on the structural elements of the tree – things like which features to split on, where to set the thresholds for those splits, and how samples are assigned to the final ‘leaf’ nodes. Crucially, this design ensures that the algorithm’s complexity and memory usage do not grow with the number of training samples, a major limitation of previous MIP formulations.
The second stage then handles the sample-specific responses, calculating the actual predictions for each data point. This separation of concerns allows RS-ORT to use a specialized branch-and-bound algorithm that branches only on these structural variables, guaranteeing that it will find the best possible tree structure.
Key Innovations for Enhanced Performance
To make this theoretical advantage practical, the researchers introduced several clever techniques:
-
Closed-Form Leaf Predictions: Once the tree structure is set, the optimal prediction value for each leaf node can be calculated directly using a simple formula (the average of the target values for samples in that leaf). This eliminates a whole set of continuous variables from the complex search process, significantly reducing the computational burden.
-
Discretization of Threshold Variables: Instead of searching for split thresholds across an infinite range of continuous values, RS-ORT intelligently limits the search to only the actual observed feature values in the training data. This doesn’t sacrifice optimality because any split between two consecutive observed values would yield the same data partition. This effectively converts an infinite search space into a finite, manageable one.
-
Exact Depth-1 Subtree Parsing: The algorithm can ‘fathom’ or resolve parts of the tree early. Specifically, for the lowest level of the tree, it can determine the optimal splits using a fast, greedy search method (similar to a simple CART model). This provides stronger lower bounds and prunes large sections of the search space, accelerating convergence.
These strategies, combined with the algorithm’s inherent ability for parallel execution, allow RS-ORT to tackle massive datasets with millions of rows, a feat previously intractable for exact methods.
Empirical Validation and Superior Results
The research team rigorously tested RS-ORT against state-of-the-art methods, including the MIQP formulation by Bertsimas & Dunn (2019), the Optimal Sparse Regression Tree (OSRT) algorithm by Zhang et al. (2023), and the widely used CART algorithm. The experiments, conducted on various regression benchmarks with both binary and continuous features, demonstrated RS-ORT’s superior performance.
Notably, on a dataset with 2 million continuous samples (the Household dataset), RS-ORT successfully found a provably globally optimal regression tree within four hours. This tree was often simpler and showed better generalization ability than competing models. In contrast, other exact methods either reported large optimality gaps (meaning they didn’t find the true optimum within the time limit) or encountered ‘out-of-memory’ errors, especially on large datasets with diverse continuous features.
Even when competitors like OSRT were given their preferred binarized inputs, RS-ORT, operating directly on continuous features, often achieved lower training and test errors, showcasing its robustness and effectiveness. For more details, you can read the full research paper here.
Also Read:
- OptiTree: Structuring Knowledge for Advanced Optimization with Language Models
- Variational Pólya Tree: Bridging Bayesian Nonparametrics with Deep Generative Models
Conclusion
RS-ORT represents a significant advancement in the field of optimal decision tree learning. By intelligently reducing the search space and incorporating efficient bounding techniques, it provides a scalable, accurate, and interpretable solution for regression tasks, particularly those involving large datasets with continuous features. This method offers guaranteed training performance, simpler tree structures, and better generalization, making it a powerful tool for high-stakes decision-making.
