The interest in algorithms for learning optimal decision trees (ODTs) has increased significantly in recent years. These algorithms use combinatorial search to find a predictive machine learning model in the form of a tree. It was shown that ODTs can obtain better predictive performance than trees found using traditional, heuristic algorithms. In many applications where accuracy is important, however, in practice machine learning developers use forests of decision trees instead of single trees. The most popular approaches for learning forests, such as Adaboost, are heuristic in nature, and it is not clear where their good performance comes from. In an attempt to study this, a number of earlier papers developed approaches that rely on the definition of a global optimization criterion for learning forests; however, unfortunately, these papers did not present algorithms for optimizing these criteria exactly, hence leaving the value of the optimization criteria unclear. In this work, we show that by using recent techniques for learning exact ODTs, we can now also optimize forests exactly. We show the optimization gap with existing approaches and evaluate the performance of optimal decision forests using different optimization criteria compared to Adaboost. This reveals that optimal decision forests can be a good approach depending on the optimization criterion and in some cases can outperform Adaboost.

Several recent publications have studied the use of Mixed Integer Programming (MIP) for finding an optimal decision tree, that is, the best decision tree under formal requirements on accuracy, fairness or interpretability of the predictive model. These publications used MIP to deal with the hard computational challenge of finding such trees. In this paper, we introduce a new efficient algorithm, DL8.5, for finding optimal decision trees, based on the use of itemset mining techniques. We show that this new approach outperforms earlier approaches with several orders of magnitude, for both numerical and discrete data, and is generic as well. The key idea underlying this new approach is the use of a cache of itemsets in combination with branch-and-bound search; this new type of cache also stores results for parts of the search space that have been traversed partially.

Decision Trees (DTs) are widely used Machine Learning (ML) models with a broad range of applications. The interest in these models has increased even further in the context of Explainable AI (XAI), as decision trees of limited depth are very interpretable models. However, traditional algorithms for learning DTs are heuristic in nature; they may produce trees that are of suboptimal quality under depth constraints. We introduce PyDL8.5, a Python library to infer depth-constrained Optimal Decision Trees (ODTs). PyDL8.5 provides an interface for DL8.5, an efficient algorithm for inferring depth-constrained ODTs. The library provides an easy-to-use scikit-learn compatible interface. It cannot only be used for classification tasks, but also for regression, clustering, and other tasks. We introduce an interface that allows users to easily implement these other learning tasks. We provide a number of examples of how to use this library.