12 de abril de 2022 · 1 Min. de lectura

3 Overview of Talks 3.1 SHAP Explanations with Booleans Circuit Classifiers

RL2, Publisher: Dagstuhl Reports, Link >

AUTHORS

Leopoldo Bertossi

Abstract

The presentation turns around the subject of explainable AI. More specifically, we deal with attribution numerical scores that are assigned to features values of an entity under classification, to identify and rank their importance for the obtained classification label. We concentrate on the popular SHAP score [2] that can be applied with black-box and open models. We show that, in contrast to its general #P

AUTHORS

Leopoldo Bertossi

-hardness, it can be computed in polynomial time for classifiers that are based on decomposable and deterministic Boolean decision circuits. This class of classifiers includes decision trees and ordered binary decision diagrams. This result was established in [1]. The presentation illustrates how the proof heavily relies on the connection to SAT-related computational problems.



45 visualizaciones