Feature Necessity & Relevancy in ML Classifier Explanations
Authors: 
Xuanxiang Huang, Martin C. Cooper, Antonio Morgado, 
Jordi Planes, Joao Marques-SilvaAuthors Info & Claims
Pages 167 - 186
Abstract
Given a machine learning (ML) model and a prediction, explanations can be defined as sets of features which are sufficient for the prediction. In some applications, and besides asking for an explanation, it is also critical to understand whether sensitive features can occur in some explanation, or whether a non-interesting feature must occur in all explanations. This paper starts by relating such queries respectively with the problems of relevancy and necessity in logic-based abduction. The paper then proves membership and hardness results for several families of ML classifiers. Afterwards the paper proposes concrete algorithms for two classes of classifiers. The experimental results confirm the scalability of the proposed algorithms.
References
[1]
Akers, S.B.: Binary decision diagrams. IEEE Transactions on computers27(06), 509–516 (1978)
[2]
Alcalá-Fdez, J., Fernández, A., Luengo, J., Derrac, J., García,S., Sánchez, L., Herrera, F.: Keel data-mining software tool: data setrepository, integration of algorithms and experimental analysis framework.Journal of Multiple-Valued Logic & Soft Computing 17 (2011), https://sci2s.ugr.es/keel/dataset.php?cod=21
[3]
Amgoud, L., Ben-Naim, J.: Axiomatic foundations of explainability. In: IJCAI.pp. 636–642 (2022)
[4]
Arenas, M., Baez, D., Barceló, P., Pérez, J., Subercaseaux, B.:Foundations of symbolic languages for model interpretability. In: NeurIPS(2021)
[5]
Arenas, M., Barceló, P., Romero, M., Subercaseaux, B.: On computingprobabilistic explanations for decision trees. CoRR abs/2207.12213(2022). 10.48550/arXiv.2207.12213, https://doi.org/10.48550/arXiv.2207.12213
[6]
Arora, S., Barak, B.: Computational Complexity - A Modern Approach. CambridgeUniversity Press (2009), http://www.cambridge.org/catalogue/catalogue.asp?isbn=9780521424264
[7]
Audemard, G., Bellart, S., Bounia, L., Koriche, F., Lagniez, J., Marquis, P.:On the computational intelligibility of boolean classifiers. In: KR. pp.74–86 (2021)
[8]
Audemard, G., Koriche, F., Marquis, P.: On tractable XAI queries based oncompiled representations. In: KR. pp. 838–849 (2020)
[9]
Bach, S., Binder, A., Montavon, G., Klauschen, F., Müller, K.R., Samek, W.:On pixel-wise explanations for non-linear classifier decisions by layer-wiserelevance propagation. PloS one 10(7), e0130140 (2015)
[10]
Barceló, P., Monet, M., Pérez, J., Subercaseaux, B.: Modelinterpretability through the lens of computational complexity. In: NeurIPS(2020)
[11]
Bekker, J., Davis, J., Choi, A., Darwiche, A., den Broeck, G.V.: Tractablelearning for complex probability queries. In: NeurIPS. pp. 2242–2250 (2015), https://github.com/ML-KULeuven/LearnSDD
[12]
Bengio, Y., LeCun, Y., Hinton, G.E.: Deep learning for AI. Commun. ACM64(7), 58–65 (2021), https://doi.org/10.1145/3448250
[13]
Biere, A., Heule, M., van Maaren, H., Walsh, T. (eds.): Handbook ofSatisfiability - Second Edition, Frontiers in Artificial Intelligence andApplications, vol. 336. IOS Press (2021), https://doi.org/10.3233/FAIA336
[14]
Blanc, G., Lange, J., Tan, L.: Provably efficient, succinct, and preciseexplanations. In: NeurIPS (2021)
[15]
Boumazouza, R., Alili, F.C., Mazure, B., Tabia, K.: ASTERYX: Amodel-Agnostic SaT-basEd appRoach for sYmbolic and score-basedeXplanations. In: CIKM. pp. 120–129 (2021)
[16]
Brayton, R.K., Hachtel, G.D., McMullen, C., Sangiovanni-Vincentelli, A.: Logicminimization algorithms for VLSI synthesis, vol. 2. Springer Science &Business Media (1984)
[17]
Breiman, L.: Random forests. Mach. Learn. 45(1), 5–32 (2001). 10.1023/A:1010933404324, https://doi.org/10.1023/A:1010933404324
[18]
Breiman, L., Friedman, J.H., Olshen, R.A., Stone, C.J.: Classification andRegression Trees. Wadsworth (1984)
[19]
Clark, P., Boswell, R.: Rule induction with cn2: Some recent improvements. In:European Working Session on Learning. pp. 151–163. Springer (1991)
[20]
Clarke, E.M., Grumberg, O., Jha, S., Lu, Y., Veith, H.: Counterexample-guidedabstraction refinement for symbolic model checking. J. ACM 50(5),752–794 (2003). 10.1145/876638.876643,https://doi.org/10.1145/876638.876643
[21]
Daniels, H., Velikova, M.: Monotone and partially monotone neural networks.IEEE Trans. Neural Networks 21(6), 906–917 (2010)
[22]
Darwiche, A.: SDD: A new canonical representation of propositional knowledge bases. In: IJCAI. pp. 819–826 (2011).
[23]
Darwiche, A., Marquis, P.: A knowledge compilation map. J. Artif. Intell. Res.17, 229–264 (2002). 10.1613/jair.989
[24]
Darwiche, A., Marquis, P.: On quantifying literals in boolean logic and itsapplications to explainable AI. J. Artif. Intell. Res. 72,285–328 (2021)
[25]
Eiter, T., Gottlob, G.: The complexity of logic-based abduction. J. ACM42(1), 3–42 (1995), https://doi.org/10.1145/200836.200838
[26]
Fard, M.M., Canini, K.R., Cotter, A., Pfeifer, J., Gupta, M.R.: Fast and flexible monotonic functions with ensembles of lattices. In: NeurIPS. pp. 2919–2927 (2016).
[27]
Ferreira, J., de Sousa Ribeiro, M., Gonçalves, R., Leite, J.: Looking inside the black-box: Logic-based explanations for neural networks. In: KR. p. 432–442 (2022).
[28]
Flach, P.A.: Machine Learning - The Art and Science of Algorithms that Make Sense of Data. CUP (2012).
[29]
Friedman, J.H.: Greedy function approximation: a gradient boosting machine. Annals of statistics pp. 1189–1232 (2001).
[30]
Friedrich, G., Gottlob, G., Nejdl, W.: Hypothesis classification, abductive diagnosis and therapy. In: ESE. pp. 69–78 (1990).
[31]
Gergov, J., Meinel, C.: Efficient boolean manipulation with OBDD’s can beextended to FBDD’s. IEEE Transactions on Computers 43(10),1197–1209 (1994). 10.1109/12.324545
[32]
Goodfellow, I.J., Bengio, Y., Courville, A.C.: Deep Learning. Adaptivecomputation and machine learning, MIT Press (2016),http://www.deeplearningbook.org/
[33]
Gorji, N., Rubin, S.: Sufficient reasons for classifier decisions in the presence of domain constraints. In: AAAI (February 2022).
[34]
Haaren, J.V., Davis, J.: Markov network structure learning: A randomized feature generation approach. In: AAAI (2012).
[35]
Huang, X., Izza, Y., Ignatiev, A., Cooper, M.C., Asher, N., Marques-Silva, J.: Tractable explanations for d-DNNF classifiers. In: AAAI. pp. 5719–5728 (2022).
[36]
Huang, X., Izza, Y., Ignatiev, A., Marques-Silva, J.: On efficiently explaining graph-based classifiers. In: KR. pp. 356–367 (2021).
[37]
Ignatiev, A., Izza, Y., Stuckey, P.J., Marques-Silva, J.: Using MaxSAT for efficient explanations of tree ensembles. In: AAAI. pp. 3776–3785 (2022).
[38]
Ignatiev, A., Marques-Silva, J.: SAT-based rigorous explanations for decision lists. In: SAT. pp. 251–269 (2021).
[39]
Ignatiev, A., Narodytska, N., Asher, N., Marques-Silva, J.: From contrastive to abductive explanations and back again. In: AIxIA. pp. 335–355 (2020).
[40]
Ignatiev, A., Narodytska, N., Marques-Silva, J.: Abduction-based explanations for machine learning models. In: AAAI. pp. 1511–1519 (2019).
[41]
Ignatiev, A., Pereira, F., Narodytska, N., Marques-Silva, J.: A SAT-based approach to learn explainable decision sets. In: IJCAR. pp. 627–645 (2018).
[42]
Izza, Y., Ignatiev, A., Marques-Silva, J.: On tackling explanation redundancyin decision trees. J. Artif. Intell. Res. 75, 261–321 (2022),https://doi.org/10.1613/jair.1.13575
[43]
Izza, Y., Marques-Silva, J.: On explaining random forests with SAT. In: IJCAI. pp. 2584–2591 (2021).
[44]
Kohavi, R.: Bottom-up induction of oblivious read-once decision graphs: strengths and limitations. In: AAAI. pp. 613–618 (1994).
[45]
Kohavi, R., et al.: Scaling up the accuracy of naive-bayes classifiers: A decision-tree hybrid. In: Kdd. vol. 96, pp. 202–207 (1996).
[46]
Larochelle, H., Murray, I.: The neural autoregressive distribution estimator. In: AISTATS. pp. 29–37 (2011).
[47]
LeCun, Y., Bengio, Y., Hinton, G.: Deep learning. nature 521(7553),436–444 (2015)
[48]
Liu, X., Han, X., Zhang, N., Liu, Q.: Certified monotonic neural networks. In: NeurIPS (2020).
[49]
Lowd, D., Davis, J.: Learning Markov network structure with decision trees. In: ICDM. pp. 334–343 (2010).
[50]
Lundberg, S.M., Lee, S.: A unified approach to interpreting model predictions. In: NeurIPS. pp. 4765–4774 (2017).
[51]
Malfa, E.L., Michelmore, R., Zbrzezny, A.M., Paoletti, N., Kwiatkowska, M.: On guaranteed optimal robust explanations for NLP models. In: IJCAI. pp. 2658–2665 (2021).
[52]
Marques-Silva, J., Gerspacher, T., Cooper, M.C., Ignatiev, A., Narodytska, N.: Explaining naive bayes and other linear classifiers with polynomial time and delay. In: NeurIPS (2020).
[53]
Marques-Silva, J., Gerspacher, T., Cooper, M.C., Ignatiev, A., Narodytska, N.: Explanations for monotonic classifiers. In: ICML. pp. 7469–7479 (2021).
[54]
Marques-Silva, J., Ignatiev, A.: Delivering trustworthy AI through formal XAI. In: AAAI. pp. 12342–12350 (2022).
[55]
Miller, T.: Explanation in artificial intelligence: Insights from the socialsciences. Artif. Intell. 267, 1–38 (2019)
[56]
Müller, B., Reinhardt, J., Strickland, M.T.: Neural networks: an introduction. Springer Science & Business Media (1995).
[57]
Olson, R.S., La Cava, W., Orzechowski, P., Urbanowicz, R.J., Moore, J.H.:PMLB: a large benchmark suite for machine learning evaluation andcomparison. BioData Mining 10(1), 36 (2017),https://epistasislab.github.io/pmlb/index.html
[58]
Ribeiro, M.T., Singh, S., Guestrin, C.: "Why should I trust you?": Explaining the predictions of any classifier. In: KDD. pp. 1135–1144 (2016).
[59]
Ribeiro, M.T., Singh, S., Guestrin, C.: Anchors: High-precision model-agnostic explanations. In: AAAI. pp. 1527–1535 (2018).
[60]
Rivest, R.L.: Learning decision lists. Mach. Learn. 2(3), 229–246(1987)
[61]
Selman, B., Levesque, H.J.: Abductive and default reasoning: A computational core. In: AAAI. pp. 343–348 (1990).
[62]
Shalev-Shwartz, S., Ben-David, S.: Understanding Machine Learning - From Theory to Algorithms. Cambridge University Press (2014).
[63]
Shih, A., Choi, A., Darwiche, A.: A symbolic approach to explaining bayesian network classifiers. In: IJCAI. pp. 5103–5111 (2018).
[64]
Sill, J.: Monotonic networks. In: NIPS. pp. 661–667 (1997).
[65]
Sivaraman, A., Farnadi, G., Millstein, T.D., den Broeck, G.V.: Counterexample-guided learning of monotonic neural networks. In: NeurIPS (2020).
[66]
Van den Broeck, G., Darwiche, A.: On the role of canonicity in knowledge compilation. In: AAAI. pp. 1641–1648 (2015).
[67]
Wäldchen, S., MacDonald, J., Hauch, S., Kutyniok, G.: The computationalcomplexity of understanding binary classifier decisions. J. Artif. Intell.Res. 70, 351–387 (2021),https://doi.org/10.1613/jair.1.12359
[68]
Wegener, I.: Branching Programs and Binary Decision Diagrams. SIAM (2000), https://ls2-www.cs.uni-dortmund.de/monographs/bdd/.
[69]
Wehenkel, A., Louppe, G.: Unconstrained monotonic neural networks. In: NeurIPS. pp. 1543–1553 (2019).
[70]
You, S., Ding, D., Canini, K.R., Pfeifer, J., Gupta, M.R.: Deep lattice networks and partial monotonic functions. In: NeurIPS. pp. 2981–2989 (2017), https://github.com/tensorflow/lattice.
Recommendations
Preferences and explanations
In abductive reasoning, preference criteria for selecting the best explanation are regarded as qualitative properties (like being simpler or more plausible) which are beyond the pure causal or deductive relationship between an explanandum and its ...
Towards Unifying Feature Attribution and Counterfactual Explanations: Different Means to the Same End
AIES '21: Proceedings of the 2021 AAAI/ACM Conference on AI, Ethics, and SocietyFeature attributions and counterfactual explanations are popular approaches to explain a ML model. The former assigns an importance score to each input feature, while the latter provides input examples with minimal changes to alter the model's ...
Complexity results for explanations in the structural-model approach
We analyze the computational complexity of Halpern and Pearl's (causal) explanations in the structural-model approach, which are based on their notions of weak and actual cause. In particular, we give a precise picture of the complexity of deciding ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Apr 2023
717 pages
ISBN:978-3-031-30822-2
DOI:10.1007/978-3-031-30823-9
- Editors:
- Sriram Sankaranarayanan,
- Natasha Sharygina
© The Author(s) 2023.
Open Access This chapter is licensed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license and indicate if changes were made.The images or other third party material in this chapter are included in the chapter's Creative Commons license, unless indicated otherwise in a credit line to the material. If material is not included in the chapter's Creative Commons license and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder.
Publisher
Springer-Verlag
Berlin, Heidelberg
Publication History
Published: 22 April 2023
Author Tags
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 13 Nov 2024
Other Metrics
Citations
View Options
View options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in