The Tractability of SHAP-Score-Based Explanations over Deterministic and Decomposable Boolean Circuits

Simple item page
dc.contributor.authorArenas, Marcelo
dc.contributor.authorBarcelo, Pablo
dc.contributor.authorBertossi, Leopoldo
dc.contributor.authorMonet, Mikael
dc.date.accessioned2024-01-10T14:24:56Z
dc.date.available2024-01-10T14:24:56Z
dc.date.issued2021
dc.description.abstractScores based on Shapley values are widely used for providing explanations to classification results over machine learning models. A prime example of this is the influential SHAP - score, a version of the Shapley value that can help explain the result of a learned model on a specific entity by assigning a score to every feature. While in general computing Shapley values is a computationally intractable problem, it has recently been claimed that the SHAP-score can be computed in polynomial time over the class of decision trees. In this paper, we provide a proof of a stronger result over Boolean models: the SHAP -score can be computed in polynomial time over deterministic and decomposable Boolean circuits. Such circuits, also known as tractable Boolean circuits, generalize a wide range of Boolean circuits and binary decision diagrams classes, including binary decision trees, Ordered Binary Decision Diagrams (OBDDs) and Free Binary Decision Diagrams (FBDDs). We also establish the computational limits of the notion of SHAP-score by observing that, under a mild condition, computing it over a class of Boolean models is always polynomially as hard as the model counting problem for that class. This implies that both determinism and decomposability are essential properties for the circuits that we consider, as removing one or the other renders the problem of computing the SHAP-score intractable (namely, #P-hard).
dc.description.funderFondecyt
dc.format.extent9 páginas
dc.fuente.origenWOS
dc.identifier.eisbn978-1-57735-866-4
dc.identifier.eissn2374-3468
dc.identifier.issn2159-5399
dc.identifier.urihttps://repositorio.uc.cl/handle/11534/80286
dc.identifier.wosidWOS:000680423506089
dc.information.autorucFacultad de Ingeniería; Arenas Saavedra, Marcelo Alejandro; S/I; 81488
dc.language.isoen
dc.nota.accesoSin adjunto
dc.pagina.final6678
dc.pagina.inicio6670
dc.publisherASSOC ADVANCEMENT ARTIFICIAL INTELLIGENCE
dc.relation.ispartof35th AAAI Conference on Artificial Intelligence / 33rd Conference on Innovative Applications of Artificial Intelligence / 11th Symposium on Educational Advances in Artificial Intelligence, FEB 02-09, 2021, ELECTR NETWORK
dc.rightsregistro bibliográfico
dc.subjectCOMPLEXITY
dc.titleThe Tractability of SHAP-Score-Based Explanations over Deterministic and Decomposable Boolean Circuits
dc.typecomunicación de congreso
dc.volumen35
sipa.codpersvinculados81488
sipa.indexWOS
sipa.trazabilidadCarga SIPA;09-01-2024
Files
Collections
Artículos de conferencia