TY - JOUR
T1 - Learning optimal decision sets and lists with SAT
AU - Yu, Jinqiang
AU - Ignatiev, Alexey
AU - Stuckey, Peter J.
AU - Le Bodic, Pierre
N1 - Publisher Copyright:
© 2021 AI Access Foundation.
PY - 2021/12/10
Y1 - 2021/12/10
N2 - Decision sets and decision lists are two of the most easily explainable machine learning models. Given the renewed emphasis on explainable machine learning decisions, both of these machine learning models are becoming increasingly attractive, as they combine small size and clear explainability. In this paper, we define size as the total number of literals in the SAT encoding of these rule-based models as opposed to earlier work that concentrates on the number of rules. In this paper, we develop approaches to computing minimum-size \perfect"decision sets and decision lists, which are perfectly accurate on the training data, and minimal in size, making use of modern SAT solving technology. We also provide a new method for determining optimal sparse alternatives, which trade off size and accuracy. The experiments in this paper demonstrate that the optimal decision sets computed by the SAT-based approach are comparable with the best heuristic methods, but much more succinct, and thus, more explainable. 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. Finally, we examine the size of average explanations generated by decision sets and decision lists.
AB - Decision sets and decision lists are two of the most easily explainable machine learning models. Given the renewed emphasis on explainable machine learning decisions, both of these machine learning models are becoming increasingly attractive, as they combine small size and clear explainability. In this paper, we define size as the total number of literals in the SAT encoding of these rule-based models as opposed to earlier work that concentrates on the number of rules. In this paper, we develop approaches to computing minimum-size \perfect"decision sets and decision lists, which are perfectly accurate on the training data, and minimal in size, making use of modern SAT solving technology. We also provide a new method for determining optimal sparse alternatives, which trade off size and accuracy. The experiments in this paper demonstrate that the optimal decision sets computed by the SAT-based approach are comparable with the best heuristic methods, but much more succinct, and thus, more explainable. 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. Finally, we examine the size of average explanations generated by decision sets and decision lists.
UR - http://www.scopus.com/inward/record.url?scp=85122359686&partnerID=8YFLogxK
U2 - 10.1613/JAIR.1.12719
DO - 10.1613/JAIR.1.12719
M3 - Article
AN - SCOPUS:85122359686
SN - 1076-9757
VL - 72
SP - 1251
EP - 1279
JO - Journal of Artificial Intelligence Research
JF - Journal of Artificial Intelligence Research
ER -