Learning Optimal Decision Trees with MaxSAT and its Integration in AdaBoost

By Hao Hu, Mohamed Siala, Emmanuel Hebrard, Marie-José Huguet. 2020

54 citations recorded by the source corpus.

Recently, several exact methods to compute decision trees have been introduced. On the one hand, these approaches can find optimal trees for various objective functions including total size, depth or accuracy on the training set and therefore. On the other hand, these methods are not yet widely used in practice and classic heuristics are often still the methods of choice. In this paper we show how the SAT model proposed by [Narodytska et.al 2018] can be lifted to a MaxSAT approach, making it much more practically relevant. In particular, it scales to much larger data sets; the objective function can easily be adapted to take into account combinations of size, depth and accuracy on the training set; and the fine-grained control of the objective function it offers makes it particularly well suited for boosting. Our experiments show promising results. In particular, we show that the prediction quality of our approach often exceeds state of the art heuristics. We also show that the MaxSAT formulation is well adapted for boosting using the well-known AdaBoost Algorithm.

Subfields: Artificial Intelligence, Information Systems, Optimization & Training, Algorithms & Complexity

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Information Systems

In Optimization & Training

In Algorithms & Complexity

Citations in the corpus

Interpretable Machine Learning: Fundamental Principles and 10 Grand Challenges (2021, background): “, 2020) and SAT solvers (Narodytska et al., 2018; Hu et al., 2020) (see also the review of Carrizosa et al.”
MurTree: Optimal Decision Trees via Dynamic Programming and Search (2020, background): “…conventional machine learning approaches, as the aim is to construct the smallest tree that perfectly describes the given dataset, i.e., leads to zero misclassiﬁcations on the training data, although they can be adapted to the accuracy criterion via maximum satisﬁability (MaxSAT) Hu et al. (2020).”
Recent advances in decision trees: an updated survey (2022, methodology): “…has been showcased for objectives like discrimination measures (Aghaei et al. 2019), imbalanced accuracy (Verwer and Zhang 2017; Lin et al. 2020; Günlük et al. 2021), and general combinations of accuracy and size (Bertsimas and Dunn 2017; Hu et al. 2020; Lin et al. 2020; Demirović et al. 2021).”
On Explaining Decision Trees (2020, background): “Motivated by this perception, there has been extensive work on learning DTs (and related logic ML models) with properties deemed important for interpretability, e.g. number of nodes, maximum/average depth, etc. [2,68,25,32,1,7,57,24,26,70,67,58,44,30,17,5,73,35,4,78,69,10,34,72,71,36,46,11,45] 2 .”