SAT-based Decision Tree Learning for Large Data Sets
By André Schidler, Stefan Szeider. 2021
72 citations recorded by the source corpus.
Decision trees of low depth are beneficial for understanding and interpreting the data they represent. Unfortunately, finding a decision tree of lowest depth that correctly represents given data is NP-hard. Hence known algorithms either (i) utilize heuristics that do not optimize the depth or (ii) are exact but scale only to small or medium-sized instances. We propose a new hybrid approach to decision tree learning, combining heuristic and exact methods in a novel way. More specifically, we employ SAT encodings repeatedly to local parts of a decision tree provided by a standard heuristic, leading to a global depth improvement. This allows us to scale the power of exact SAT-based methods to almost arbitrarily large data sets. We evaluate our new approach experimentally on a range of real-world instances that contain up to several thousand samples. In almost all cases, our method successfully decreases the depth of the initial decision tree; often, the decrease is significant.
Subfields: Artificial Intelligence
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
- Carlos Eduardo Pedreira
- Vinícius G. Costa
- Stefan Szeider
- Emmanuel Hebrard
- Sebastian Ordyniak
- Peter James Stuckey
- C. Leckie
- Emir Demirovi'c
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)).”
- Recent advances in decision trees: an updated survey (2022, methodology): “More recently, works have considered the SAT approach from other angles: Schidler and Szeider (2021) used SAT techniques to progressively prune a greedy-induced tree, while Hu et al. (2020) used the MaxSAT framework to maximize accuracy instead of capturing it perfectly, resulting in an algorithm…”
- Parameterized Complexity of Small Decision Tree Learning (2021, methodology): “In view of this complexity barrier, several constrained-based and SAT-based methods have been proposed for learning small decision trees (Bessiere, Hebrard, and O’Sullivan 2009; Narodytska et al. 2018; Avellaneda 2020; Schidler and Szeider 2021).”