Abstract
The successes of machine learning in recent years have triggered a fast growing range of applications. In important settings, including safety critical applications and when transparency of decisions is paramount, accurate predictions do not suffice; one expects the machine learning model to also explain the predictions made, in forms understandable by human decision makers. Recent work proposed explainable models based on decision sets which can be viewed as unordered sets of rules, respecting some sort of rule non-overlap constraint. This paper investigates existing solutions for computing decision sets and identifies a number of drawbacks, related with rule overlap and succinctness of explanations, the accuracy of achieved results, but also the efficiency of proposed approaches. To address these drawbacks, the paper develops novel SAT-based solutions for learning decision sets. Experimental results on computing decision sets for representative datasets demonstrate that SAT enables solutions that are not only the most efficient, but also offer stronger guarantees in terms of rule non-overlap.
This work was supported by FCT grants SAFETY (SFRH/BPD/120315/2016) and ABSOLV (028986/02/SAICT/2017), and LASIGE Research Unit, ref. UID/CEC/00408/2013.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
The generalization from \({\textsc {MinDS}}_{3}\) to \({\textsc {MinDS}}_{2}\) is straightforward, and omitted due to space constraints. Moreover, the model for \({\textsc {MinDS}}_{1}\) follows a similar approach.
- 2.
- 3.
A support threshold parameter \(\epsilon \) in the Apriori algorithm ensures that the candidate itemsets are present in at least \(\epsilon \) data points.
- 4.
- 5.
Some of the PMLB datasets are inconsistent, i.e. they have multiple occurrences of the same samples marked by different labels. Since the proposed models assume consistent data, the datasets were replaced by their largest consistent subsets. The number of samples shown above corresponds to the size of the resulting consistent datasets.
- 6.
These surprising results motivated in part our detailed analysis of overlap. It should be noted that the authors of IDS [21] have been informed of IDS’s poor performance and poor ability to avoid rule overlap, but have been unable to justify the results of IDS.
References
Agrawal, R., Srikant, R.: Fast algorithms for mining association rules in large databases. In: VLDB, pp. 487–499 (1994)
Angelino, E., Larus-Stone, N., Alabi, D., Seltzer, M., Rudin, C.: Learning certifiably optimal rule lists. In: KDD, pp. 35–44 (2017)
Bessiere, C., Hebrard, E., O’Sullivan, B.: Minimising decision tree size as combinatorial optimisation. In: CP, pp. 173–187 (2009)
Biere, A., Heule, M., van Maaren, H., Walsh, T. (eds.): Handbook of Satisfiability. IOS Press, Amsterdam (2009)
Cendrowska, J.: PRISM: an algorithm for inducing modular rules. Int. J. Man Mach. Stud. 27(4), 349–370 (1987)
Clark, P., Boswell, R.: Rule induction with CN2: some recent improvements. In: Kodratoff, Y. (ed.) EWSL 1991. LNCS, vol. 482, pp. 151–163. Springer, Heidelberg (1991). https://doi.org/10.1007/BFb0017011
Clark, P., Niblett, T.: The CN2 induction algorithm. Mach. Learn. 3, 261–283 (1989)
Cohen, W.W.: Fast effective rule induction. In: ICML, pp. 115–123 (1995)
DARPA: DARPA explainable Artificial Intelligence (XAI) program (2016). https://www.darpa.mil/program/explainable-artificial-intelligence
Eén, N., Sörensson, N.: An extensible SAT-solver. In: SAT, pp. 502–518 (2003)
EU Data Protection Regulation: Regulation (EU) 2016/679 of the European Parliament and of the Council (2016). http://eur-lex.europa.eu/legal-content/EN/TXT/PDF/?uri=CELEX:32016R0679&from=en
Feige, U., Mirrokni, V.S., Vondrák, J.: Maximizing non-monotone submodular functions. SIAM J. Comput. 40(4), 1133–1153 (2011)
Fürnkranz, J., Gamberger, D., Lavrac, N.: Foundations of Rule Learning. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-540-75197-7
Han, J., Kamber, M., Pei, J.: Data Mining: Concepts and Techniques, 3rd edn. Morgan Kaufmann, Burlington (2012)
Hauser, J.R., Toubia, O., Evgeniou, T., Befurt, R., Dzyabura, D.: Disjunctions of conjunctions, cognitive simplicity, and consideration sets. J. Mark. Res. 47(3), 485–496 (2010)
ICML, WHI Workshop: ICML Workshop on Human Interpretability in Machine Learning. https://sites.google.com/view/whi2017/home. Accessed Aug 2017
IJCAI, XAI Workshop: IJCAI Workshop on Explainable Artificial Intelligence (XAI). http://home.earthlink.net/~dwaha/research/meetings/ijcai17-xai/. Accessed Aug 2017
Jordan, M.I., Mitchell, T.M.: Machine learning: trends, perspectives, and prospects. Science 349(6245), 255–260 (2015)
Kamath, A.P., Karmarkar, N., Ramakrishnan, K.G., Resende, M.G.C.: A continuous approach to inductive inference. Math. Program. 57, 215–238 (1992)
Kearns, M.J., Li, M., Valiant, L.G.: Learning boolean formulas. J. ACM 41(6), 1298–1328 (1994)
Lakkaraju, H., Bach, S.H., Leskovec, J.: Interpretable decision sets: a joint framework for description and prediction. In: KDD, pp. 1675–1684 (2016)
LeCun, Y., Bengio, Y., Hinton, G.: Deep learning. Nature 521(7553), 436 (2015)
Marques-Silva, J., Argelich, J., Graça, A., Lynce, I.: Boolean lexicographic optimization: algorithms & applications. Ann. Math. Artif. Intell. 62(3–4), 317–343 (2011)
Marques-Silva, J., Heras, F., Janota, M., Previti, A., Belov, A.: On computing minimal correction subsets. In: IJCAI, pp. 615–622 (2013)
Mencía, C., Previti, A., Marques-Silva, J.: Literal-based MCS extraction. In: IJCAI, pp. 1973–1979 (2015)
Michalski, R.S.: On the quasi-minimal solution of the general covering problem. In: International Symposium on Information Processing, pp. 125–128 (1969)
Mitchell, T.M.: Machine Learning. McGraw-Hill, New York (1997)
Mnih, V., Kavukcuoglu, K., Silver, D., Rusu, A.A., Veness, J., Bellemare, M.G., Graves, A., Riedmiller, M., Fidjeland, A.K., Ostrovski, G., et al.: Human-level control through deep reinforcement learning. Nature 518(7540), 529 (2015)
Morgado, A., Ignatiev, A., Marques-Silva, J.: MSCG: robust core-guided MaxSAT solving. JSAT 9, 129–134 (2015)
NIPS, IML Symposium: NIPS Interpretable ML Symposium. http://interpretable.ml/. Accessed Dec 2017
Olson, R.S., La Cava, W., Orzechowski, P., Urbanowicz, R.J., Moore, J.H.: PMLB: a large benchmark suite for machine learning evaluation and comparison. BioData Min. 10(1), 36 (2017)
Pedregosa, F., et al.: Scikit-learn: machine learning in Python. J. Mach. Learn. Res. 12, 2825–2830 (2011)
Quinlan, J.R.: Generating production rules from decision trees. In: IJCAI, pp. 304–307 (1987)
Quinlan, J.R.: C4.5: Programs for Machine Learning. Morgan Kauffmann, Burlington (1993)
Rivest, R.L.: Learning decision lists. Mach. Learn. 2(3), 229–246 (1987)
Schaefer, M., Umans, C.: Completeness in the polynomial-time hierarchy: a compendium. SIGACT news 33(3), 32–49 (2002)
Triantaphyllou, E.: Inference of a minimum size boolean function from examples by using a new efficient branch-and-bound approach. J. Global Optim. 5(1), 69–94 (1994)
Triantaphyllou, E.: Data Mining and Knowledge Discovery via Logic-Based Methods: Theory, Algorithms, and Applications. Springer, Heidelberg (2010). https://doi.org/10.1007/978-1-4419-1630-3
Tseitin, G.S.: On the complexity of derivation in propositional calculus. In: Siekmann, J.H., Wrightson, G. (eds.) Automation of Reasoning. Symbolic Computation (Artificial Intelligence), pp. 466–483. Springer, Heidelberg (1983). https://doi.org/10.1007/978-3-642-81955-1_28
Umans, C., Villa, T., Sangiovanni-Vincentelli, A.L.: Complexity of two-level logic minimization. IEEE Trans. CAD Integr. Circuits Syst. 25(7), 1230–1246 (2006)
Wang, T., Rudin, C., Doshi-Velez, F., Liu, Y., Klampfl, E., MacNeille, P.: Or’s of And’s for interpretable classification, with application to context-aware recommender systems. CoRR, abs/1504.07614 (2015)
Wang, T., Rudin, C., Doshi-Velez, F., Liu, Y., Klampfl, E., MacNeille, P.: A Bayesian framework for learning rule sets for interpretable classification. J. Mach. Learn. Res. 18, 1–37 (2017)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2018 Springer International Publishing AG, part of Springer Nature
About this paper
Cite this paper
Ignatiev, A., Pereira, F., Narodytska, N., Marques-Silva, J. (2018). A SAT-Based Approach to Learn Explainable Decision Sets. In: Galmiche, D., Schulz, S., Sebastiani, R. (eds) Automated Reasoning. IJCAR 2018. Lecture Notes in Computer Science(), vol 10900. Springer, Cham. https://doi.org/10.1007/978-3-319-94205-6_41
Download citation
DOI: https://doi.org/10.1007/978-3-319-94205-6_41
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-94204-9
Online ISBN: 978-3-319-94205-6
eBook Packages: Computer ScienceComputer Science (R0)