Computing Optimal Decision Sets with SAT

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

29 citations recorded by the source corpus.

As machine learning is increasingly used to help make decisions, there is a demand for these decisions to be explainable. Arguably, the most explainable machine learning models use decision rules. This paper focuses on decision sets, a type of model with unordered rules, which explains each prediction with a single rule. In order to be easy for humans to understand, these rules must be concise. Earlier work on generating optimal decision sets first minimizes the number of rules, and then minimizes the number of literals, but the resulting rules can often be very large. Here we consider a better measure, namely the total size of the decision set in terms of literals. So we are not driven to a small set of rules which require a large number of literals. We provide the first approach to determine minimum-size decision sets that achieve minimum empirical risk and then investigate sparse alternatives where we trade accuracy for size. By finding optimal solutions we show we can build decision set classifiers that are almost as accurate as the best heuristic methods, but far more concise, and hence more explainable.

Subfields: Artificial Intelligence, 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 Artificial Intelligence

In Mathematical Optimization

In Algorithms & Complexity

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;…”
Mathematical optimization in classification and regression trees (2021, methodology): “The reader is referred to, e.g., Verhaeghe et al. (2019) for a constraint programming paradigm, an SAT one in Narodytska et al. (2018), Yu et al. (2020), and a dynamic programming one in Demirović et al. (2020).”
Optimal Decision Lists using SAT (2020, methodology): “The differences between the above model and the model of (Yu et al. 2020) is the addition of the n ij variables to track which items have been previously classiﬁed, and their use in constraint (8), as well as the rules to compute them given in constraints (5) and (6).”