Interpretable machine learning models, such as decision trees, are needed when decisions require trust. Optimal decision trees are shown to generalise better to new data than those constructed greedily, but due to the NP-hardness of the problem they are hard to apply to large datasets. Previous methods either do not take into account continuous features, are designed for a fixed maximum tree depth of two and three, or do not consider objectives other than classification.

We introduce CODTree, the first specialised branch-and-bound algorithm that finds optimal classification and regression trees with continuous features for an arbitrary maximum depth. Our algorithm is able to run different search strategies and includes a specialised solver for shallow trees. Our experiments show that global best-first search with a heuristic that prioritises smaller nodes with better lower bounds has the best time to optimality and anytime performance, and that the specialised solver for shallow trees provides a geometric mean speedup of 77.4x.

Compared to the state-of-the-art for classification, we have comparable runtime, but our search strategy has four orders of magnitude fewer operations for some datasets, although there are diminishing returns for greater depths. For regression, our algorithm is significantly faster than the state-of-the-art and, to the best of our knowledge, the first to find optimal regression trees at depth four. ... Read more

Interpretable models are essential in many machine learning applications, particularly in domains where transparency and trust are critical. Decision trees are a popular interpretable model, but their structure often leads to repeated identical subtrees and data fragmentation, which can result in large, overfit models with poor generalization. Decision diagrams could offer a more compact and less fragmented alternative by allowing sharing parts of the diagram, but constructing decision diagrams is computationally challenging and has seen limited practical adoption. This thesis introduces a novel local search-based algorithm for learning binary decision diagrams for classification. Our approach finds a middle ground between early greedy methods and exact optimization techniques, enabling scalable construction of compact and accurate diagrams. We define a local search approach with several move operators and explore multiple metaheuristics, identifying hill climbing with information gain-based initialization as the most effective strategy. We refer to this method as Decision Diagram Local Search (DDLS). We evaluate DDLS on 57 real-world datasets from the UCI repository and 480 synthetic datasets generated from known diagrams. Our method achieves competitive or superior accuracy compared to state-of-the-art decision tree and diagram methods on real-world datasets, while producing small models with lower fragmentation. Though challenges remain, especially on complex synthetic datasets, our results suggest that DDLS, and decision diagrams in general, hold significant untapped potential as interpretable classifiers. ... Read more

Interpretability distinguishes decision trees from most other machine learning models; what they still have in common is that they are vulnerable to adversarial examples. Various robust decision tree algorithms exist; however, they either do not provide optimal results or are not scalable with data that has continuous features. In this work, we demonstrate RobTree, a scalable optimal robust decision tree algorithm for continuous features. We propose new theorems that reduce the number of thresholds to be considered to half of what was previously considered and give way to pruning techniques. The results of this paper indicate that RobTree vastly outperforms the state-of-the-art in terms of runtime for trees of depth two up to two orders of magnitude.
... Read more

Finding the smallest decision tree that perfectly fits the training data is NP-complete; yet, such trees remain attractive due to their interpretability and minimal footprint. Existing solutions occupy two extremes: heuristics like CART instantly produce trees but remain far from optimal, whereas exact solvers like Witty give no intermediate output. We introduce AnyDTree, an anytime algorithm that continuously maintains a 100% accurate tree and monotonically shrinks its size. It employs an expand-and-backtrack search that ensures complete solutions at every step, combined with aggressive pruning and caching mechanisms to eliminate redundant exploration. On 70 binary-classification variants of 35 UCI datasets, AnyDTree incurs no statistically significant overhead in finding the optimal size compared with Witty (log-rank p>0.1). On the 46 datasets with known optima, it demonstrates significantly improved anytime behaviour - measured by the confined primal integral - with a median score of 0.00034, outperforming both Witty (0.00059) and CART (0.20) (p<0.001). These results position AnyDTree as a practical middle ground between heuristic and exact solutions. ... Read more

Algorithm Selection is a problem that involves finding a way to select the best algorithm out of a portfolio of candidate algorithms, depending on a set of instances for a problem. It has been shown that optimal decision trees that work on binary features are as accurate as state of the art models like random forest, while being more interpretable and smaller, motivating research into alternative, more scalable methods to generate such trees. In this paper we present an optimal decision tree algorithm that operates directly on continuous features and measure its suitability for the algorithm selection problem. We show that our algorithm performs over three orders of magnitude better than other algorithms that build similar decision trees, and that it achieves similar out of sample model selection quality as state of the art methods while being at least 2x faster than similar methods for binary features for higher binarization values. ... Read more

Decision trees are accurate and interpretable models that can predict classes or values based on features of a data point, but they are vulnerable to small changes to the data that greatly affect the predictions. Previous work has resulted in methods that can find robust optimal classification trees or robust regression trees, but not robust optimal regression trees. Computing optimal decision trees is already NP-hard, and continuous prediction values make robust regression trees more complex than robust classification trees. We analyze in further detail why this is a difficult problem to solve. We introduce ForTree, a method that uses exhaustive search with pruning to find robust optimal regression trees out of a set of trees with limited prediction values. It evaluates all possible configurations of trees with this limitation and stores the tree with the highest adversarial accuracy. We also introduce the partial accuracy as a lower bound for pruning, which we use to speed up the runtime of ForTree. Our experiments show that ForTree achieves up to 1.23 times the adversarial accuracy of state-of-the-art robust regression tree methods, but that the runtime of ForTree is greatly sensitive to the amount of unique feature values in a dataset. We propose multiple approaches to find robust regression trees with higher adversarial accuracy or within less runtime in the future. ... Read more

Decision-Focused Learning (DFL) focuses on a setting where a system gets as input some features and needs to predict coefficients to a downstream optimization problem. Classically, one would apply a two-stage solution, which trains the predictor as a regression task and only uses the optimizer during evaluation. However, the two-stage solution fails to optimize the downstream optimization problem. As such, one might use DFL techniques to train the predictor. Nonetheless, these fail to take the entire solution space into account and only optimize toward the optimal true solution, and as such, they might fail to optimize the total downstream value. Furthermore, these techniques are computationally expensive.

We tackle these two problems using Decision Diagrams (DDs) for DFL. DDs for DFL have three main benefits. First, the DD can be cached between runs, speeding up the training loop. Second, we present four novel loss functions that use DDs to reason efficiently over entire solution spaces. Furthermore, we introduce a novel method to relax the DDs to reduce solve-time during training.

We experimentally show that the DDs speed up the training loop substantially. We further show that the DFL losses perform on par with other state-of-the-art DFL losses. Finally, we experimentally show when and which losses work with relaxed DDs.
... Read more

The Algorithm Selection Problem (ASP) presents a significant challenge in numerous industries, requiring optimal solutions for complex computational problems. Traditional approaches to solving ASP often rely on complex, black-box models like random forests, which are effective but lack transparency, and they often fail to balance performance with interpretability. This paper investigates the performance-interpretability trade-off for the ASP, specifically focused on Optimal Decision Trees (ODTs) as recent innovations have made the use of ODTs more viable. We compare ODTs against 4 other tree-based models, using 11 different datasets. We show there is no apparent tradeoff between performance and interpretability for ODTs which have been trained using an instance cost-sensitive approach, as they achieve comparable performance to a Random Forest Regressor while maintaining interpretability through multiple orders of magnitude fewer leaf nodes. ... Read more

Decision trees are valued for their ability to logically and transparently classify data. While heuristic methods to compute such trees are efficient, they often compromise on accuracy, prompting interest in Optimal Decision Trees (ODTs), which have the best misclassification score for a given tree size limit and training dataset. The dynamic programming (DP) approach for ODTs has shown improvements over alternatives such as mixed-integer or constraint programming. That being said, it requires further improvements to handle exponential runtime scaling with the depth of the tree and the number of features of the dataset. Leveraging modern hardware, such as multiple CPU cores, offers a promising solution to improve efficiency. This paper proposes a multithreading method for DP ODTs which we apply to STreeD specifically. We introduce a shared memory model and determine which components of the original program can be made local to the threads. We investigate whether it is more efficient to start multithreading at the root of the search tree than near its leaf nodes. We find the former to be superior, resulting in faster runtimes and less shared resource access. Empirical evaluations against the state of the art demonstrate better runtimes, particularly beneficial for large datasets. Finally, thread scaling analyses reveal substantial speed-ups, exceeding 2.5 times with four threads, highlighting our approach's effectiveness for computationally-intensive tasks. ... Read more

Survival analysis predicts survival functions that give the probability of survival until a given time. Many applications of survival analysis involve health care, which requires interpretability of the models used to predict the survival function. Provably optimal decision trees have shown to be an interpretable alternative to so-called black box models. However, these algorithms often choose estimators that are fast, yet not necessarily most accurate. Moreover, the objective functions of optimal decision tree algorithms tend to make (possibly incorrect) assumptions about the survival function. In this paper, we tackle both problems. We implement the iterative Breslow estimator in an already existing optimal survival tree algorithm in order to iteratively improve the Nelson-Aalen estimator. This approach has great potential, as we show by using it on artificial datasets, but we do not see an improvement in accuracy on real world data. To eliminate the assumptions made by the objective function, we implement the Integrated Brier Score objective, which causes a significant improvement on training accuracy. However, we see no improvement on out-of-sample accuracy ... Read more

In the pursuit of employing interpretable and performant Machine Learning models, Decision Trees has become a staple in many industries while being able to produce near-optimal results. With computational power becoming more accessible, there has been increasing progress in constructing Optimal Decision Trees. It guarantees optimal solutions with respect to different metrics within a given size limit on training data while requiring a smaller number of nodes and becoming more viable to compute on real-world data. However, non-linear metrics, which are very effective when evaluating trees on imbalanced datasets, still represent a challenge regarding runtime performance and scalability. Previous approaches generate the Pareto Front of the set of possible solutions, an expensive operation in computing the optimal tree. To address this gap, we introduce a novel merging algorithm of two Pareto Fronts using convex hulls, offering better pruning and leading to an increase in scalability. The experiments show a significant improvement in runtime of almost 10\% on bigger datasets and higher-depth trees using the F1-score metric, with the potential to be applied to other convex metrics. ... Read more

Survival analysis is a branch of statistics concerned with studying and estimating the expected time duration until some event, such as biological death, occurs. Survival distributions are fitted based on historical data, where some instances are censored, meaning that the actual time of the event is not known precisely. Survival trees extend on the classical statistical methods developed and can capture complex non-linear relations between the variables by recursively splitting the instances by generated rules and fitting a different survival distribution in each leaf. Moreover, decision trees are desirable models due to their interpretable nature. We extend existing optimal survival tree methods by considering Cox Proportional Hazard models in each leaf node, which allows us to find more complex yet interpretable relationships than existing methods. The experiments show that our model outperforms state-of-the-art methods for creating survival trees, SurTree, OST, and CTree, especially in determining the relative risks between out-of-sample observations while generating significantly smaller trees. ... Read more

Decision trees are integral to machine learning, with their robustness being a critical measure of effectiveness against adversarial data manipulations. Despite advancements in algorithms, current solutions are either optimal but lack scalability or scale well, but do not guarrantee optimality. This paper presents a novel adaptation of the Murtree algorithm to address these challenges in the pursuit of optimal robust decision trees. We introduce a new method for modeling an adversary as a network flow problem, and provide a dynamic programming approach to solve optimal robust decision trees beyond a depth of two. The performance of our proposed algorithm is compared with bruteforce solutions across varying decision tree depths, feature numbers, and data sizes. This research contributes a significant advancement towards obtaining efficient and effective solutions for optimal robust decision trees, potentially setting a new performance benchmark in this area.
... Read more

In this paper, we tackle the problem of creating decision trees that are both optimal and individually fair. While decision trees are popular due to their interpretability, achieving optimality can be difficult. Existing approaches either lack scalability or fail to consider individual fairness. To address this, we define individual fairness as a separable optimization task by analyzing the fairness gained and lost within a sub-tree. Using the Streed framework, we implement an algorithm that constructs optimal decision trees with the lowest misclassification score and individual fairness value above a certain threshold. Our algorithm has been tested on various datasets, demonstrating its effectiveness and scalability. This research is a significant step towards creating fair decision trees that are optimal, fair, and scalable. ... Read more

Survival analysis revolves around studying and predicting the time it takes for a particular event to occur. In clinical trials on terminal illnesses, this is usually the time from the diagnosis of a patient until their death. Estimating the odds of survival of a new patient can be done by analyzing survival data from past patients in similar conditions. To cluster similar patients based on a set of features, survival trees may be employed, which act as decision trees that assign a survival distribution to each cluster. Many algorithms exist for creating useful survival trees, but not for creating optimal survival trees. In this paper, research on finding optimal classification trees is applied to survival analysis, by adapting the MurTree algorithm to construct survival trees. We present SurTree, an algorithm that applies many of MurTree’s techniques to create globally optimal survival trees. Furthermore, we compare the output quality and runtime performance of SurTree to a state-of-the-art method for constructing survival trees, showing its optimality and its fast computation times on smaller datasets. ... Read more

The Algorithm Selection Problem is a relevant question in computer science that would enable us to predict which algorithm would perform better on a given instance of a problem.
Different solutions have been proposed, either using Mixed Integer Programming or machine learning models, but both suffer from either poor scalability, no guarantees of optimality, or not interpretable models that could be used to gain insights into the nature of the problem.
In this work we propose a dynamic programming method to build Optimal Decision Trees to solve the Algorithm Selection Problem, giving us an interpretable model that is globally optimal over the training dataset. We also show that this method is orders of magnitude faster in training trees that are identical to the current state-of-the-art and propose possible improvements for future work. ... Read more

Decision trees make decisions in a way interpretable to humans, this is important when machines are increasingly used to aid in making high-stakes and socially sensitive decisions. While heuristics have been used for a long time to find decision trees with reasonable accuracy, recent approaches find fully optimal trees. Due to the computational hardness of finding fully optimal decision trees, it is only practically possible to find shallow trees for a limited dataset size. However, continuous algorithmic improvements keep pushing the scale of feasible solutions. Dynamic Programming approaches promise to find scalable optimal decision trees but need to be adapted for different objectives, such as regression. We combine and adapt the algorithmic techniques of two Dynamic Programming methods, creating a new method that improves the scalability of optimal regression trees. This new method often achieves an order of magnitude speed improvement over a previous state-of-the-art method. ... Read more

Decision tree learning is widely done heuristically, but advances in the field of optimal decision trees have made them a more prominent subject of research. However, current methods for optimal decision trees tend to overlook the metric of robustness. Our research wants to find out whether the robustness of optimal decision trees can be improved by incorporating randomization. To achieve this, we added randomization to the existing MurTree algorithm, and performed experiments to compare the robustness. The results show that adding randomization improves the robustness of the decision tree but lowers the out of sample accuracy. ... Read more

Several algorithms can often be used to solve a complex problem, such as the SAT problem or the graph coloring problem. Those algorithms differ in terms of speed based on the size or other features of the problem. Some algorithms perform much faster on a small size while others perform noticeably better on a larger instance. The optimization problem in this case is to select the best-performing algorithm based on the problem features, resulting in a much faster overall runtime. This is defined as the algorithm selection problem. Many different approaches have been used to solve this problem, such as constructing optimal decision trees. However, there is little published data on using optimal decision trees for algorithm selection and one study reveals a problem in finding a feasible solution on a large number of problem instances. We provide new insights into solving algorithm selection using a dynamic programming approach. The motivation to use this novel approach is that recent studies suggest it has lower scalability issues compared to the traditional optimal decision tree algorithms, due to several efficient techniques such as caching and frequency counting method. The investigation has shown that compared to the integer programming method, the dynamic programming approach is significantly faster and is able to solve large problem instances. ... Read more

Machine learning can be used to classify patients in a hospital. Here, the classifier has to minimize the cost of misclassifying the patient and minimize the costs of the tests. Unfortunately, obtaining features may be costly, e.g., taking blood tests or doing an x-ray scan. Furthermore, it is possible that acquiring those test results may take a few days. To train such a classifier, several machine learning algorithms exist. Decision trees appear as favourites since, unlike other classifiers, decision trees do not need all feature values to classify an instance. Current approaches, however, only use heuristics to find a local optimum. Although heuristics are relatively fast, they are not optimal and therefore may not capture well the underlying characteristics of the given dataset. We propose an optimal approach to train cost-sensitive decision trees while also considering these delayed tests. Here we show, smaller trees with higher accuracy and a lower cost can be constructed, compared to a heuristic approach. We use dynamic programming to allow us to skip many calculations, which speeds up the programming time to seconds. ... Read more