{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,24]],"date-time":"2025-08-24T01:49:26Z","timestamp":1756000166483,"version":"3.40.5"},"reference-count":59,"publisher":"Cambridge University Press (CUP)","issue":"3","license":[{"start":{"date-parts":[[2021,12,27]],"date-time":"2021-12-27T00:00:00Z","timestamp":1640563200000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["Theory and Practice of Logic Programming"],"published-print":{"date-parts":[[2023,5]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We propose answer-set programs that specify and compute counterfactual interventions on entities that are input on a classification model. In relation to the outcome of the model, the resulting counterfactual entities serve as a basis for the definition and computation of causality-based explanation scores for the feature values in the entity under classification, namely <jats:italic>responsibility scores<\/jats:italic>. The approach and the programs can be applied with black-box models, and also with models that can be specified as logic programs, such as rule-based classifiers. The main focus of this study is on the specification and computation of <jats:italic>best<\/jats:italic> counterfactual entities, that is, those that lead to maximum responsibility scores. From them one can read off the explanations as maximum responsibility feature values in the original entity. We also extend the programs to bring into the picture semantic or domain knowledge. We show how the approach could be extended by means of probabilistic methods, and how the underlying probability distributions could be modified through the use of constraints. Several examples of programs written in the syntax of the <jats:italic>DLV<\/jats:italic> ASP-solver, and run with it, are shown.<\/jats:p>","DOI":"10.1017\/s1471068421000582","type":"journal-article","created":{"date-parts":[[2021,12,27]],"date-time":"2021-12-27T07:07:31Z","timestamp":1640588851000},"page":"559-593","update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":9,"title":["Declarative Approaches to Counterfactual Explanations for Classification"],"prefix":"10.1017","volume":"23","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1144-3179","authenticated-orcid":false,"given":"LEOPOLDO","family":"BERTOSSI","sequence":"first","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2021,12,27]]},"reference":[{"key":"S1471068421000582_ref46","unstructured":"Molnar, C. 2020. Interpretable Machine Learning: A Guide for Making Black Box Models Explainable. https:\/\/christophm.github.io\/interpretable-ml-book"},{"key":"S1471068421000582_ref28","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511973000"},{"key":"S1471068421000582_ref35","doi-asserted-by":"crossref","unstructured":"Ignatiev, A. , Narodytska, N. and Marques-Silva, J. 2019. Abduction-based explanations for machine learning models. In Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence, AAAI 2019, AAAI Press, 1511\u20131519.","DOI":"10.1609\/aaai.v33i01.33011511"},{"key":"S1471068421000582_ref3","unstructured":"Arenas, M. , Pablo Barcel\u00f3, P. , Bertossi, L. and Monet, M. 2012. The tractability of shap-scores over deterministic and decomposable boolean circuits. In Proceedings of the Thirty-Fifth AAAI Conference on Artificial Intelligence, AAAI 2021. AAAI Press, 6670\u20136678."},{"key":"S1471068421000582_ref5","doi-asserted-by":"publisher","DOI":"10.1007\/BF01530761"},{"key":"S1471068421000582_ref47","doi-asserted-by":"crossref","unstructured":"Narodytska, N. , Shrotri, A. , Meel, K. , Ignatiev, A. and Marques-Silva, J. 2019. Assessing heuristic machine learning explanations with model counting. In Proceedings of the 22nd International Conference on Theory and Applications of Satisfiability Testing, SAT 2019, M. Janota and I. Lynce, LNCS, vol. 11628, Springer, 267\u2013278.","DOI":"10.1007\/978-3-030-24258-9_19"},{"key":"S1471068421000582_ref39","doi-asserted-by":"crossref","unstructured":"Law, M. , Russo, A. and Broda, K. 2019. Logic-based learning of answer set programs. In Reasoning Web. Explainable Artificial Intelligence - 15th International Summer School 2019, Tutorial Lectures, Kr\u00f6tzsch, M. and Stepanova, D. , Eds. LNCS, vol. 11810, Springer, 196\u2013231.","DOI":"10.1007\/978-3-030-31423-1_6"},{"key":"S1471068421000582_ref50","doi-asserted-by":"crossref","unstructured":"Russell, Ch . 2019. Efficient search for diverse coherent explanations. In Proceedings of the Conference on Fairness, Accountability, and Transparency, FAT * 2019, Boyd, D. and Morgenstern, J. H. , Eds. ACM, 20\u201328.","DOI":"10.1145\/3287560.3287569"},{"key":"S1471068421000582_ref17","doi-asserted-by":"crossref","unstructured":"Calimeri, F. , Cozza, S. , Ianni, G. and Leone, N. 2009. An ASP system with functions, lists, and sets. In Proceedings of the 10th International Conference on Logic Programming and Nonmonotonic Reasoning, LPNMR 2009, Erdem, E. , Lin, F. and Schaub, T. , Eds. LNCS, vol. 5753, Springer, 483\u2013489.","DOI":"10.1007\/978-3-642-04238-6_46"},{"key":"S1471068421000582_ref25","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(96)00179-X"},{"key":"S1471068421000582_ref30","doi-asserted-by":"crossref","unstructured":"Izza, Y. and Marques-Silva, J. 2021. On explaining random forests with SAT. In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI 2021, Z.-H. Zhou, Ed., 2584\u20132591.","DOI":"10.24963\/ijcai.2021\/356"},{"key":"S1471068421000582_ref37","unstructured":"Karimi, A-H. , Barthe, G. , Balle, B. and Valera, I. 2020a. Model-agnostic counterfactual explanations for consequential decisions. In Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics, AISTATS 2020, Chiappa, S. and Calandra, R. , Eds. PMLR, vol. 108, 895\u2013905."},{"key":"S1471068421000582_ref12","doi-asserted-by":"crossref","unstructured":"Bertossi, L. , Li, J. , Schleich, M. , Suciu, D. and Vagena, Z. 2020. Causality-based explanation of classification outcomes. In Proceedings of the Fourth Workshop on Data Management for End-To-End Machine Learning, In Conjunction with the 2020 ACM SIGMOD\/PODS Conference, DEEM@SIGMOD 2020, Sebastian Schelter, S. , Whang, S. and Stoyanovich, J. , Eds., 6:1\u20136:10.","DOI":"10.1145\/3399579.3399865"},{"key":"S1471068421000582_ref31","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139342124"},{"key":"S1471068421000582_ref51","doi-asserted-by":"crossref","unstructured":"Ribeiro, M. T. , Singh, S. and Guestrin, C. 2016. \u201cWhy should I trust you?\u201d: Explaining the predictions of any classifier. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2016, Krishnapuram, B. , Shah, M. , Smola, A. J. , Aggarwal, C.C. , Shen, D. and Rastogi, R. , Eds. ACM, 1135\u20131144.","DOI":"10.1145\/2939672.2939778"},{"key":"S1471068421000582_ref2","doi-asserted-by":"crossref","unstructured":"Alviano, M. , Amendola, G. , Dodaro, C. , Leone, N. , Maratea, M. and Ricca, F. 2019. Evaluation of disjunctive programs in WASP. In Proceedings of the 15th International Conference on Logic Programming and Nonmonotonic Reasoning, LPNMR 2019. Marcello Balduccini, M. , Lierler, Y. and Woltran, S. , Eds. LNCS, vol. 11481, Springer, 241\u2013255.","DOI":"10.1007\/978-3-030-20528-7_18"},{"key":"S1471068421000582_ref43","doi-asserted-by":"publisher","DOI":"10.25300\/MISQ\/2014\/38.1.04"},{"key":"S1471068421000582_ref4","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068408003645"},{"key":"S1471068421000582_ref33","doi-asserted-by":"publisher","DOI":"10.1023\/A:1018999404360"},{"key":"S1471068421000582_ref59","doi-asserted-by":"crossref","unstructured":"Wang, E. , Khosravi, P. and Van den Broeck, G. 2021. Probabilistic sufficient explanations. In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI 2021, Z.-H. Zhou, Ed., 3082\u20133088.","DOI":"10.24963\/ijcai.2021\/424"},{"key":"S1471068421000582_ref16","unstructured":"Brewka, G. , Delgrande, J. , Romero, J. and Schaub, T. 2015. asprin: Customizing answer set preferences without a headache. In Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, AAAI 2015, Blai Bonet, B. and Koenig, S. , Eds. AAAI Press, 1467\u20131474."},{"key":"S1471068421000582_ref52","unstructured":"Ribeiro, M. T. , Singh, S. and Guestrin, C. 2018. Anchors: high-precision model-agnostic explanations. In Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, AAAI 2018, McIlraith, S. A. and Weinberger, K. Q. , Eds. AAAI Press, 1527\u20131535."},{"key":"S1471068421000582_ref38","unstructured":"Karimi, A-H. , von Kgen, B. J. , Sch\u00f6lkopf, B. and Valera, I. 2020b. Algorithmic recourse under imperfect causal knowledge: a probabilistic approach. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, H. Larochelle, M. Ranzato, R. , Balcan, M.-F. and Lin, H.-T. , Eds."},{"key":"S1471068421000582_ref20","doi-asserted-by":"publisher","DOI":"10.1613\/jair.1391"},{"key":"S1471068421000582_ref11","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-020-01516-6"},{"key":"S1471068421000582_ref23","doi-asserted-by":"crossref","unstructured":"Datta, A. , Sen, S. and Zick, Y. 2016. Algorithmic transparency via quantitative input influence: theory and experiments with learning systems. In Proceedings of the IEEE Symposium on Security and Privacy, SP 2016. IEEE Computer Society, 598\u2013617.","DOI":"10.1109\/SP.2016.42"},{"key":"S1471068421000582_ref24","unstructured":"Darwiche, A. and Hirth, A. 2020. On the reasons behind decisions. In Proceedings of the 24th European Conference on Artificial Intelligence, ECAI 2020, De Giacomo, G. , Catal\u00e1, A. , Dilkina, B. , Milano, M. , Barro, S. , Bugarn, B. and Lang, J. , Eds. IOS Press, 712\u2013720."},{"key":"S1471068421000582_ref56","doi-asserted-by":"crossref","unstructured":"Ustun, B. , Spangher, A. and Liu, Y. 2019. Actionable recourse in linear classification. In Proceedings of the Conference on Fairness, Accountability, and Transparency, FAT * 2019, Boyd, D. and Morgenstern, J. H. , Eds. ACM, 10\u201319.","DOI":"10.1145\/3287560.3287566"},{"volume-title":"Machine Learning","year":"1997","author":"Mitchell","key":"S1471068421000582_ref45"},{"key":"S1471068421000582_ref19","doi-asserted-by":"publisher","DOI":"10.1016\/j.datak.2010.01.005"},{"key":"S1471068421000582_ref36","doi-asserted-by":"crossref","unstructured":"Ignatiev, A. 2020. Towards trustable explainable AI. In Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI 2020, C. Bessiere, Ed., 5154\u20135158.","DOI":"10.24963\/ijcai.2020\/726"},{"key":"S1471068421000582_ref13","doi-asserted-by":"publisher","DOI":"10.1145\/3386687"},{"key":"S1471068421000582_ref42","doi-asserted-by":"publisher","DOI":"10.1038\/s42256-019-0138-9"},{"key":"S1471068421000582_ref49","doi-asserted-by":"publisher","DOI":"10.1038\/s42256-019-0048-x"},{"key":"S1471068421000582_ref54","doi-asserted-by":"crossref","unstructured":"Shi, W. , Shih, A. , Darwiche, A. and Choi, A. 2020. On tractable representations of binary neural networks. In Proceedings of the 17th International Conference on Principles of Knowledge Representation and Reasoning, KR 2020, Calvanese, D. , Erdem, E. and Thielscher, M. , Eds., 882\u2013892.","DOI":"10.24963\/kr.2020\/91"},{"key":"S1471068421000582_ref26","first-page":"2","article-title":"The dlvhex system","volume":"32","author":"Eiter","year":"2019","journal-title":"K\u00fcnstliche Intelligenz"},{"volume-title":"Synthesis Lectures in Data Management","year":"2011","author":"Bertossi","key":"S1471068421000582_ref6"},{"key":"S1471068421000582_ref18","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068419000450"},{"key":"S1471068421000582_ref32","doi-asserted-by":"publisher","DOI":"10.1007\/BF03037169"},{"key":"S1471068421000582_ref7","doi-asserted-by":"crossref","unstructured":"Bertossi, L. 2019. Database repairs and consistent query answering: origins and further developments. Gems of PODS paper. In Proceedings of the 38th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2019, Suciu, D. , Skritek, S. and Koch, Ch , Eds. ACM, 48\u201358.","DOI":"10.1145\/3294052.3322190"},{"key":"S1471068421000582_ref48","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511803161"},{"key":"S1471068421000582_ref21","unstructured":"Choi, A. , Shih, A. , Goyanka, A. and Darwiche, A. 2020. On symbolically encoding the behavior of random forests. ArXiv 2007.01493, 2020."},{"key":"S1471068421000582_ref14","unstructured":"Bertossi, L. and Reyes, G. 2021. Answer-set programs for reasoning about counterfactual interventions and responsibility scores for classification. In Proceedings of the 1st International Joint Conference on Learning and Reasoning, IJCLR 2021. LNCS, to appear, Springer. Extended version posted as ArXiv 2107.10159."},{"key":"S1471068421000582_ref58","first-page":"841","article-title":"Counterfactual explanations without opening the black box: Automated decisions and the GDPR","volume":"31","author":"Wachter","year":"2017","journal-title":"Harvard Journal of Law and Technology"},{"key":"S1471068421000582_ref1","doi-asserted-by":"crossref","unstructured":"Alviano, M. , Calimeri, F. , Dodaro, C. , Fusc\u00e0, D. , Leone, L. , Perri, S. , Ricca, F. , Veltri, P. and Zangari, J. 2017. The ASP system dlv2. In Proceedings of the 14th International Conference on Logic Programming and Nonmonotonic Reasoning, LPNMR 2017, Balduccini, M. and Janhunen, T. , Eds. LNCS, vol. 10377, Springer, 215\u2013221.","DOI":"10.1007\/978-3-319-61660-5_19"},{"key":"S1471068421000582_ref57","unstructured":"Van den Broeck, G. , Lykov, A. , Schleich, M. and Suciu, D. 2021. On the tractability of SHAP explanations. In Proceedings of the Thirty-Fifth AAAI Conference on Artificial Intelligence, AAAI 2021. AAAI Press, 6505\u20136513."},{"key":"S1471068421000582_ref34","doi-asserted-by":"publisher","DOI":"10.1093\/bjps\/axi147"},{"key":"S1471068421000582_ref22","doi-asserted-by":"publisher","DOI":"10.1145\/502807.502810"},{"key":"S1471068421000582_ref40","unstructured":"Lee, J. and Yang, Z. 2017. LPMLN, weak constraints, and p-log. In Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence, AAAI 2017, Singh, S. P. and Markovitch, S. , Eds. AAAI Press, 1170\u20131177."},{"key":"S1471068421000582_ref53","doi-asserted-by":"crossref","unstructured":"Schleich, M. , Geng, Z. , Zhang, Y. and Suciu, D. 2021. GeCo: Quality counterfactual explanations in real time. Proceedings of the VLDB Endowment, 14, 9, 1681\u20131693.","DOI":"10.14778\/3461535.3461555"},{"key":"S1471068421000582_ref55","unstructured":"Shih, A. , Choi, A. and Darwiche, A. 2018. Formal verification of Bayesian network classifiers. In Proceedings of the International Conference on Probabilistic Graphical Models, PGM 2018, Studen\u00fd, M. , and Kratochvl, V. , Eds. PLMR, vol. 72, 157\u2013168."},{"key":"S1471068421000582_ref44","doi-asserted-by":"crossref","unstructured":"Meliou, A. , Gatterbauer, W. , Moore, K. F. and Suciu, D. 2010. The complexity of causality and responsibility for query answers and non-answers. Proceedings of the VLDB Endowment, 4, 1, 34\u201345.","DOI":"10.14778\/1880172.1880176"},{"key":"S1471068421000582_ref10","unstructured":"Bertossi, L. 2020. An ASP-based approach to counterfactual explanations for classification. In Proceedings \u201cRules and Reasoning\u201d - 4th International Joint Conference, RuleML+RR 2020, Guti\u00e9rrez-Basulto, V. , Kliegr, T. , Soylu, A. , Giese, M. and Roman, D. , Eds. LNCS vol. 12173, Springer, 70\u201381."},{"key":"S1471068421000582_ref8","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-016-9718-9"},{"key":"S1471068421000582_ref15","doi-asserted-by":"publisher","DOI":"10.1145\/2043174.2043195"},{"key":"S1471068421000582_ref29","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068411000329"},{"key":"S1471068421000582_ref41","doi-asserted-by":"publisher","DOI":"10.1145\/1149114.1149117"},{"key":"S1471068421000582_ref27","doi-asserted-by":"crossref","unstructured":"Eiter, T. , Kaminski, T. , Redl, C. , Sch\u00fcller, P. and Weinzierl, A. 2017. Answer set programming with external source access. In Reasoning Web. Semantic Interoperability on the Web - 13th International Summer School 2017, Tutorial Lectures, Ianni, G. , Lembo, D. , Bertossi, L. , Faber, W. , Glimm, B. , Gottlob, G. and Staab, S. , Eds. LNCS, vol. 10370, Springer, 204\u2013275.","DOI":"10.1007\/978-3-319-61033-7_7"},{"key":"S1471068421000582_ref9","doi-asserted-by":"publisher","DOI":"10.1016\/j.ijar.2017.07.010"}],"container-title":["Theory and Practice of Logic Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S1471068421000582","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,19]],"date-time":"2023-05-19T03:07:59Z","timestamp":1684465679000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S1471068421000582\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,12,27]]},"references-count":59,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2023,5]]}},"alternative-id":["S1471068421000582"],"URL":"https:\/\/doi.org\/10.1017\/s1471068421000582","relation":{},"ISSN":["1471-0684","1475-3081"],"issn-type":[{"type":"print","value":"1471-0684"},{"type":"electronic","value":"1475-3081"}],"subject":[],"published":{"date-parts":[[2021,12,27]]},"assertion":[{"value":"\u00a9 The Author(s), 2021. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}}]}}