Learning Optimal Decision Trees with SAT

Learning Optimal Decision Trees with SAT

Nina Narodytska, Alexey Ignatiev, Filipe Pereira, Joao Marques-Silva

Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence
Main track. Pages 1362-1368. https://doi.org/10.24963/ijcai.2018/189

Explanations of machine learning (ML) predictions are of fundamental importance in different settings. Moreover, explanations should be succinct, to enable easy understanding by humans.  Decision trees represent an often used approach for developing explainable ML models, motivated by the natural mapping between decision tree paths and rules. Clearly, smaller trees correlate well with smaller rules, and so one  challenge is to devise solutions for computing smallest size decision trees given training data. Although simple to formulate, the computation of smallest size decision trees turns out to be an extremely challenging computational problem, for which no practical solutions are known. This paper develops a SAT-based model for computing smallest-size decision trees given training data. In sharp contrast with past work, the proposed SAT model is shown to scale for publicly available datasets of practical interest.
Keywords:
Constraints and SAT: Constraints and SAT
Constraints and SAT: SAT
Constraints and SAT: SAT: Applications
Constraints and SAT: Constraints and Data Mining ; Machine Learning