{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,5]],"date-time":"2026-06-05T04:36:13Z","timestamp":1780634173927,"version":"3.54.1"},"reference-count":48,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2022,8,18]],"date-time":"2022-08-18T00:00:00Z","timestamp":1660780800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,8,18]],"date-time":"2022-08-18T00:00:00Z","timestamp":1660780800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["ISS-1910317"],"award-info":[{"award-number":["ISS-1910317"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000185","name":"Defense Advanced Research Projects Agency","doi-asserted-by":"publisher","award":["N66001-17-2-4032"],"award-info":[{"award-number":["N66001-17-2-4032"]}],"id":[{"id":"10.13039\/100000185","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000006","name":"Office of Naval Research","doi-asserted-by":"publisher","award":["N00014-18-1-2561"],"award-info":[{"award-number":["N00014-18-1-2561"]}],"id":[{"id":"10.13039\/100000006","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100004332","name":"JPMorgan Chase and Company","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100004332","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J of Log Lang and Inf"],"published-print":{"date-parts":[[2023,3]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Recent work has shown that the input-output behavior of some common machine learning classifiers can be captured in symbolic form, allowing one to reason about the behavior of these classifiers using symbolic techniques. This includes explaining decisions, measuring robustness, and proving formal properties of machine learning classifiers by reasoning about the corresponding symbolic classifiers. In this work, we present a theory for unveiling the <jats:italic>reasons<\/jats:italic> behind the decisions made by Boolean classifiers and study some of its theoretical and practical implications. At the core of our theory is the notion of a <jats:italic>complete reason,<\/jats:italic> which can be viewed as a necessary and sufficient condition for why a decision was made. We show how the complete reason can be used for computing notions such as sufficient reasons (also known as PI-explanations and abductive explanations), how it can be used for determining decision and classifier bias and how it can be used for evaluating counterfactual statements such as \u201ca decision will stick even if ...because ... .\u201d We present a linear-time algorithm for computing the complete reasoning behind a decision, assuming the classifier is represented by a Boolean circuit of appropriate form. We then show how the computed complete reason can be used to answer many queries about a decision in linear or polynomial time. We finally conclude with a case study that illustrates the various notions and techniques we introduced.\n<\/jats:p>","DOI":"10.1007\/s10849-022-09377-8","type":"journal-article","created":{"date-parts":[[2022,8,18]],"date-time":"2022-08-18T08:02:54Z","timestamp":1660809774000},"page":"63-88","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":16,"title":["On the (Complete) Reasons Behind Decisions"],"prefix":"10.1007","volume":"32","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3976-6735","authenticated-orcid":false,"given":"Adnan","family":"Darwiche","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Auguste","family":"Hirth","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2022,8,18]]},"reference":[{"key":"9377_CR1","doi-asserted-by":"crossref","unstructured":"Audemard, G., Bellart, S., Bounia, L., Koriche, F., Lagniez, J. M., & Marquis, P. (2021) On the explanatory power of decision trees. CoRR arXiv:2108.05266","DOI":"10.1016\/j.datak.2022.102088"},{"key":"9377_CR2","doi-asserted-by":"crossref","unstructured":"Audemard, G., Bellart, S., Bounia, L., Koriche, F., Lagniez, J., & Marquis, P. (2021). On the computational intelligibility of Boolean classifiers. CoRR arXiv:abs\/2104.06172","DOI":"10.24963\/kr.2021\/8"},{"key":"9377_CR3","doi-asserted-by":"crossref","unstructured":"Audemard, G., Koriche, F., & Marquis, P. (2020). On tractable XAI queries based on compiled representations. In KR (pp. 838\u2013849).","DOI":"10.24963\/kr.2020\/86"},{"key":"9377_CR4","unstructured":"Barcel\u00f3, P., Monet, M., P\u00e9rez, J., & Subercaseaux, B. (2020). Model interpretability through the lens of computational complexity. In NeurIPS."},{"key":"9377_CR5","unstructured":"Beame, P., & Liew, V. (2015). New limits for knowledge compilation and applications to exact model counting. In UAI (pp. 131\u2013140). AUAI Press."},{"key":"9377_CR6","unstructured":"Beame, P., Li, J., Roy, S., & Suciu, D. (2013). Lower bounds for exact model counting and applications in probabilistic databases. In UAI. AUAI Press."},{"issue":"6","key":"9377_CR7","doi-asserted-by":"publisher","first-page":"1250","DOI":"10.1007\/s00224-018-9904-z","volume":"63","author":"B Bollig","year":"2019","unstructured":"Bollig, B., & Buttkus, M. (2019). On the relative succinctness of sentential decision diagrams. Theory of Computing Systems, 63(6), 1250\u20131277.","journal-title":"Theory of Computing Systems"},{"issue":"8","key":"9377_CR8","doi-asserted-by":"publisher","first-page":"677","DOI":"10.1109\/TC.1986.1676819","volume":"35","author":"RE Bryant","year":"1986","unstructured":"Bryant, R. E. (1986). Graph-based algorithms for Boolean function manipulation. IEEE Transactions on Computers, 35(8), 677\u2013691.","journal-title":"IEEE Transactions on Computers"},{"key":"9377_CR9","unstructured":"Chan, H., & Darwiche, A. (2003). Reasoning about Bayesian network classifiers. In UAI (pp. 107\u2013115). Morgan Kaufmann."},{"key":"9377_CR10","unstructured":"Choi, A., Shih, A., Goyanka, A., & Darwiche, A. (2020). On symbolically encoding the behavior of random forests. CoRR arXiv:abs\/2007.01493"},{"key":"9377_CR11","doi-asserted-by":"crossref","unstructured":"Coudert, O., & Madre, J. C. (1993). Fault tree analysis: $$10^{20}$$ prime implicants and beyond. In Proceedings of the annual reliability and maintainability symposium.","DOI":"10.1109\/RAMS.1993.296849"},{"key":"9377_CR12","unstructured":"Coudert, O., Madre, J. C., Fraisse, H., & Touati, H. (1993). Implicit prime cover computation: An overview. In Proceedings of the 4th SASIMI workshop."},{"key":"9377_CR13","doi-asserted-by":"crossref","unstructured":"Crama, Y., & Hammer, P. L. (2011). Boolean functions-theory, algorithms, and applications. In Encyclopedia of mathematics and its applications (vol. 142). Cambridge University Press.","DOI":"10.1017\/CBO9780511852008"},{"key":"9377_CR14","unstructured":"Darwiche, A. (2004). New advances in compiling CNF into decomposable negation normal form. In ECAI (pp. 328\u2013332). IOS Press."},{"key":"9377_CR15","unstructured":"Darwiche, A. (2011). SDD: A new canonical representation of propositional knowledge bases. In IJCAI (pp. 819\u2013826). IJCAI\/AAAI."},{"key":"9377_CR16","doi-asserted-by":"crossref","unstructured":"Darwiche, A. (2020). Three modern roles for logic in AI. In PODS (pp. 229\u2013243). ACM","DOI":"10.1145\/3375395.3389131"},{"key":"9377_CR17","unstructured":"Darwiche, A., & Hirth, A. (2020). On the reasons behind decisions. In ECAI, frontiers in artificial intelligence and applications (vol. 325, pp. 712\u2013720). IOS Press."},{"key":"9377_CR18","doi-asserted-by":"crossref","unstructured":"Darwiche, A., & Ji, C. (2022). On the computation of necessary and sufficient explanations. In AAAI. AAAI Press.","DOI":"10.1609\/aaai.v36i5.20498"},{"issue":"4","key":"9377_CR19","doi-asserted-by":"publisher","first-page":"608","DOI":"10.1145\/502090.502091","volume":"48","author":"A Darwiche","year":"2001","unstructured":"Darwiche, A. (2001). Decomposable negation normal form. Journal of the ACM, 48(4), 608\u2013647.","journal-title":"Journal of the ACM"},{"key":"9377_CR20","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1613\/jair.989","volume":"17","author":"A Darwiche","year":"2002","unstructured":"Darwiche, A., & Marquis, P. (2002). A knowledge compilation map. Journal of Artificial Intelligence Research, 17, 229\u2013264.","journal-title":"Journal of Artificial Intelligence Research"},{"key":"9377_CR21","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1613\/jair.1.12756","volume":"72","author":"A Darwiche","year":"2021","unstructured":"Darwiche, A., & Marquis, P. (2021). On literal quantification in Boolean logic and its applications to explainable AI. Journal of Artificial Intelligence Research, 72, 285\u2013328.","journal-title":"Journal of Artificial Intelligence Research"},{"issue":"2\u20133","key":"9377_CR22","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1016\/0004-3702(92)90027-U","volume":"56","author":"J de Kleer","year":"1992","unstructured":"de Kleer, J., Mackworth, A. K., & Reiter, R. (1992). Characterizing diagnoses and systems. Artificial Intelligence, 56(2\u20133), 197\u2013222.","journal-title":"Artificial Intelligence"},{"key":"9377_CR23","unstructured":"Huang, J., & Darwiche, A. (2005). DPLL with a trace: From SAT to knowledge compilation. In IJCAI (pp. 156\u2013162). Professional Book Center."},{"key":"9377_CR24","doi-asserted-by":"crossref","unstructured":"Huang, X., Izza, Y., Ignatiev, A., & Marques-Silva, J. (2021). On efficiently explaining graph-based classifiers. CoRR arXiv:abs\/2106.01350.","DOI":"10.24963\/kr.2021\/34"},{"key":"9377_CR25","unstructured":"Huang, X., Izza, Y., Ignatiev, A., Cooper, M.C., Asher, N., & Marques-Silva, J. (2021). Efficient explanations for knowledge compilation languages. CoRR arXiv:abs\/2107.01654."},{"key":"9377_CR26","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1613\/jair.2097","volume":"29","author":"J Huang","year":"2007","unstructured":"Huang, J., & Darwiche, A. (2007). The language of search. Journal of Artificial Intelligence Research, 29, 191\u2013219.","journal-title":"Journal of Artificial Intelligence Research"},{"key":"9377_CR27","doi-asserted-by":"crossref","unstructured":"Ignatiev, A., Narodytska, N., & Marques-Silva, J. (2019). Abduction-based explanations for machine learning models. In Proceedings of the thirty-three conference on artificial intelligence (AAAI) (pp. 1511\u20131519).","DOI":"10.1609\/aaai.v33i01.33011511"},{"key":"9377_CR28","unstructured":"Ignatiev, A., Narodytska, N., & Marques-Silva, J. (2019). On validating, repairing and refining heuristic ML explanations. CoRR arXiv:abs\/1907.02509."},{"key":"9377_CR29","doi-asserted-by":"crossref","unstructured":"Ignatiev, A., Narodytska, N., Asher, N., & Marques-Silva, J. (2020). From contrastive to abductive explanations and back again. In AI*IA, Lecture Notes in Computer Science, (vol. 12414, pp. 335\u2013355). Springer.","DOI":"10.1007\/978-3-030-77091-4_21"},{"key":"9377_CR30","unstructured":"Ignatiev, A., Narodytska, N., Marques-Silva, J. (2019). On relating explanations and adversarial examples. In Advances in neural information processing systems (vol. 32, pp. 15883\u201315893). Curran Associates, Inc. URL http:\/\/papers.nips.cc\/paper\/9717-on-relating-explanations-and-adversarial-examples.pdf."},{"key":"9377_CR31","unstructured":"Izza, Y., Ignatiev, A., & Marques-Silva, J. (2020). On explaining decision trees. CoRR arXiv:abs\/2010.11034."},{"key":"9377_CR32","first-page":"97","volume":"5","author":"G Katz","year":"2017","unstructured":"Katz, G., Barrett, C. W., Dill, D. L., Julian, K., & Kochenderfer, M. J. (2017). Reluplex: An efficient SMT solver for verifying deep neural networks. Computer Aided Verification CAV, 5, 97\u2013117.","journal-title":"Computer Aided Verification CAV"},{"key":"9377_CR33","doi-asserted-by":"crossref","unstructured":"Lagniez, J., & Marquis, P. (2017). An improved Decision-DNNF compiler. In IJCAI (pp. 667\u2013673). ijcai.org.","DOI":"10.24963\/ijcai.2017\/93"},{"key":"9377_CR34","unstructured":"Leofante, F., Narodytska, N., Pulina, L., & Tacchella, A. (2018). Automated verification of neural networks: Advances, challenges and perspectives. CoRR arXiv:abs\/1805.09938."},{"key":"9377_CR35","first-page":"216","volume-title":"KI 2019: advances in artificial intelligence","author":"F Lindner","year":"2019","unstructured":"Lindner, F., & M\u00f6llney, K. (2019). Extracting reasons for moral judgments under various ethical principles. In C. Benzm\u00fcller & H. Stuckenschmidt (Eds.), KI 2019: advances in artificial intelligence (pp. 216\u2013229). Cham: Springer International Publishing."},{"key":"9377_CR36","unstructured":"Marques-Silva, J., Gerspacher, T., Cooper, M. C., Ignatiev, A., & Narodytska, N. (2020). Explaining naive Bayes and other linear classifiers with polynomial time and delay. In NeurIPS."},{"issue":"6","key":"9377_CR37","doi-asserted-by":"publisher","first-page":"1417","DOI":"10.1002\/j.1538-7305.1956.tb03835.x","volume":"35","author":"EJ McCluskey","year":"1956","unstructured":"McCluskey, E. J. (1956). Minimization of Boolean functions. The Bell System Technical Journal, 35(6), 1417\u20131444. https:\/\/doi.org\/10.1002\/j.1538-7305.1956.tb03835.x.","journal-title":"The Bell System Technical Journal"},{"key":"9377_CR38","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.artint.2018.07.007","volume":"267","author":"T Miller","year":"2019","unstructured":"Miller, T. (2019). Explanation in artificial intelligence: Insights from the social sciences. Artificial Intelligence, 267, 1\u201338.","journal-title":"Artificial Intelligence"},{"issue":"6","key":"9377_CR39","first-page":"967","volume":"76","author":"S Minato","year":"1993","unstructured":"Minato, S. (1993). Fast generation of prime-irredundant covers from binary decision diagrams. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 76(6), 967\u2013973.","journal-title":"IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences"},{"key":"9377_CR40","doi-asserted-by":"crossref","unstructured":"Narodytska, N., Kasiviswanathan, S. P., Ryzhyk, L., Sagiv, M., & Walsh, T. (2018). Verifying properties of binarized deep neural networks. In Proceedings of the thirty-second AAAI conference on artificial intelligence (AAAI).","DOI":"10.1609\/aaai.v32i1.12206"},{"key":"9377_CR41","doi-asserted-by":"crossref","unstructured":"Oztok, U., & Darwiche, A. (2014). On compiling CNF into Decision-DNNF. In CP, Lecture Notes in Computer Science (vol. 8656, pp. 42\u201357). Springer.","DOI":"10.1007\/978-3-319-10428-7_7"},{"issue":"8","key":"9377_CR42","doi-asserted-by":"publisher","first-page":"521","DOI":"10.1080\/00029890.1952.11988183","volume":"59","author":"WV Quine","year":"1952","unstructured":"Quine, W. V. (1952). The problem of simplifying truth functions. The American Mathematical Monthly, 59(8), 521\u2013531.","journal-title":"The American Mathematical Monthly"},{"issue":"9","key":"9377_CR43","doi-asserted-by":"publisher","first-page":"755","DOI":"10.1080\/00029890.1959.11989404","volume":"66","author":"WV Quine","year":"1959","unstructured":"Quine, W. V. (1959). On cores and prime implicants of truth functions. The American Mathematical Monthly, 66(9), 755\u2013760.","journal-title":"The American Mathematical Monthly"},{"key":"9377_CR44","doi-asserted-by":"crossref","unstructured":"Ribeiro, M. T., Singh, S., & Guestrin, C. (2018). Anchors: High-precision model-agnostic explanations. In AAAI (pp. 1527\u20131535). AAAI Press.","DOI":"10.1609\/aaai.v32i1.11491"},{"key":"9377_CR45","doi-asserted-by":"crossref","unstructured":"Shi, W., Shih, A., Darwiche, A., & Choi, A. (2020). On tractable representations of binary neural networks. In KR (pp. 882\u2013892).","DOI":"10.24963\/kr.2020\/91"},{"key":"9377_CR46","doi-asserted-by":"crossref","unstructured":"Shih, A., Choi, A., & Darwiche, A. (2018). A symbolic approach to explaining Bayesian network classifiers. In IJCAI (pp. 5103\u20135111). ijcai.org.","DOI":"10.24963\/ijcai.2018\/708"},{"key":"9377_CR47","doi-asserted-by":"crossref","unstructured":"Shih, A., Choi, A., & Darwiche, A. (2019). Compiling Bayesian network classifiers into decision graphs. In AAAI (pp. 7966\u20137974). AAAI Press.","DOI":"10.1609\/aaai.v33i01.33017966"},{"key":"9377_CR48","doi-asserted-by":"crossref","unstructured":"Shih, A., Darwiche, A., & Choi, A. (2019). Verifying binarized neural networks by angluin-style learning. In SAT, Lecture Notes in Computer Science (vol. 11628, pp. 354\u2013370). Springer.","DOI":"10.1007\/978-3-030-24258-9_25"}],"container-title":["Journal of Logic, Language and Information"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10849-022-09377-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10849-022-09377-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10849-022-09377-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,17]],"date-time":"2023-02-17T12:09:51Z","timestamp":1676635791000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10849-022-09377-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,8,18]]},"references-count":48,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,3]]}},"alternative-id":["9377"],"URL":"https:\/\/doi.org\/10.1007\/s10849-022-09377-8","relation":{},"ISSN":["0925-8531","1572-9583"],"issn-type":[{"value":"0925-8531","type":"print"},{"value":"1572-9583","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,8,18]]},"assertion":[{"value":"1 July 2022","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 August 2022","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}