SAT-Based Encodings for Optimal Decision Trees with Explicit Paths

By Mikoláš Janota, António Morgado. 2020

36 citations recorded by the source corpus.

Decision trees play an important role both in Machine Learning and Knowledge Representation. They are attractive due to their immediate interpretability. In the spirit of Occam’s razor, and interpretability, it is desirable to calculate the smallest tree. This, however, has proven to be a challenging task and greedy approaches are typically used to learn trees in practice. Nevertheless, recent work showed that by the use of SAT solvers one may calculate the optimal size tree for real-world benchmarks. This paper proposes a novel SAT-based encoding that explicitly models paths in the tree, which enables us to control the tree’s depth as well as size. At the level of individual SAT calls, we investigate splitting the search space into tree topologies. Our tool outperforms the existing implementation. But also, the experimental results show that minimizing the depth first and then minimizing the number of nodes enables solving a larger set of instances.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Information Systems

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 Computational Theory and Mathematics

In Information Systems

Citations in the corpus

MurTree: Optimal Decision Trees via Dynamic Programming and Search (2020, methodology): “Recently, an improved SAT model has been proposed by Narodytska et al. (2018), after which several other SAT-related works have been published (Avellaneda (2020); Janota and Morgado (2020); Schidler and Szeider (2021)).”
SAT-based Decision Tree Learning for Large Data Sets (2021, methodology): “Therefore, several exact methods have been proposed that encode the problem into SAT or CSP and use SAT/CSP solvers to ﬁnd an optimal tree (Bessiere, Hebrard and O’Sullivan 2009; Narodytska et al. 2018; Avellaneda 2020; Janota and Morgado 2020).”
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 .”
Recent advances in decision trees: an updated survey (2022, background): “…technical considerations, other algorithms assume that all attributes are categorical (Günlük et al. 2021) or, more often, binary (Bessiere et al. 2009; Nijssen and Fromont 2010; Narodytska et al. 2018; Verwer and Zhang 2019; Aglin et al. 2020; Janota and Morgado 2020; Demirović et al. 2021).”