Optimal Decision Lists using SAT

By Jinqiang Yu, Alexey Ignatiev, Pierre Le Bodic, Peter James Stuckey. 2020

10 citations recorded by the source corpus.

Decision lists are one of the most easily explainable machine learning models. Given the renewed emphasis on explainable machine learning decisions, this machine learning model is increasingly attractive, combining small size and clear explainability. In this paper, we show for the first time how to construct optimal "perfect" decision lists which are perfectly accurate on the training data, and minimal in size, making use of modern SAT solving technology. We also give a new method for determining optimal sparse decision lists, which trade off size and accuracy. We contrast the size and test accuracy of optimal decisions lists versus optimal decision sets, as well as other state-of-the-art methods for determining optimal decision lists. We also examine the size of average explanations generated by decision sets and decision lists.

Subfields: Mathematical Optimization, 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 Mathematical Optimization

1. Chudi Zhong
2. Lesia Semenova
3. Zhi Chen
4. Haiyang Huang
5. Cynthia Rudin
6. Berk Ustun
7. Ş. Ertekin
8. Tong Wang

In Algorithms & Complexity

1. Chudi Zhong
2. Lesia Semenova
3. Zhi Chen
4. Haiyang Huang
5. Cynthia Rudin
6. Ş. Ertekin

Citations in the corpus

• Interpretable Machine Learning: Fundamental Principles and 10 Grand Challenges (2021, background): “Some recent works can jointly optimize performance metrics and sparsity for decision lists (Rudin and Ertekin, 2016; Yu et al., 2020a; Angelino et al., 2017, 2018; Aı̈vodji et al., 2019) and decision sets (Wang and Rudin, 2015b; Lakkaraju et al., 2016; Ignatiev et al., 2018; Dash et al., 2018b;…”