Marcelo Arenas

Pablo Barceló

Leopoldo Bertossi

Mikaël Monet

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

Scores 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 SHAPscore, 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).

Introduction

Explainable artificial intelligence has become an active area of research. Central to it is the observation that artificial intelligence (AI) and machine learning (ML) models cannot always be blindly applied without being able to interpret and explain their results. For example, when someone applies for a loan and sees their application rejected by an algorithmic decision-making system, the system should be able to provide an explanation for that decision. Explanations can be global -focusing on the general input/output relation of the model -, or local -focusing on how features affect the decision of the model for a specific input. Recent literature has strengthened the importance of the latter by showing their ability to provide explanations that are often overlooked by global explanations [START_REF] Molnar | Interpretable machine learning: A guide for making black box models explainable[END_REF].

One natural way of providing local explanations for classification models consists in assigning numerical scores to the feature values of an entity that has gone through the classification process. Intuitively, the higher the score of a feature value, the more relevant it should be considered. It is in this context that the SHAP-score has been introduced [START_REF] Lundberg | A unified approach to interpreting model predictions[END_REF][START_REF] Lundberg | From local explanations to global understanding with explainable AI for trees[END_REF]. This recent notion has rapidly gained attention and is becoming influential. There are two properties of the SHAP-score that support its rapid adoption. First, its definition is quite general and can be applied to any kind of classification model. Second, the definition of the SHAP-score is grounded on the well-known Shapley value [START_REF] Shapley | A value for n-person games[END_REF][START_REF] Roth | The Shapley value: essays in honor of Lloyd S. Shapley[END_REF]), that has already been used successfully in several domains of computer science; see, e.g., [START_REF] Hunter | On the measure of conflicts: Shapley inconsistency values[END_REF][START_REF] Livshits | The Shapley value of tuples in query answering[END_REF][START_REF] Michalak | Efficient computation of the Shapley value for game-theoretic network centrality[END_REF][START_REF] Cesari | An application of the Shapley value to the analysis of co-expression networks[END_REF]. Thus, SHAP-scores have a clear, intuitive, combinatorial meaning, and inherit all the desirable properties of the Shapley value.

For a given classifier M , entity e and feature x, the SHAP-score SHAP(M, e, x) intuitively represents the importance of the feature value e(x) to the classification result M (e). In its general formulation, SHAP(M, e, x) is a weighted average of differences of expected values of the outcomes (c.f. Section 2 for its formal definition). Unfortunately, computing quantities that are based on the notion of Shapley value is in general intractable. Indeed, in many scenarios the computation turns out to be #Phard [START_REF] Faigle | The Shapley value for cooperative games under precedence constraints[END_REF][START_REF] Deng | On the complexity of cooperative solution concepts[END_REF][START_REF] Livshits | The Shapley value of tuples in query answering[END_REF][START_REF] Bertossi | Causality-based explanation of classification outcomes[END_REF], which makes the notion difficult to use -if not impossible -for practical purposes [START_REF] Arora | Computational Complexity -A Modern Approach[END_REF]. Therefore, a natural question is: For what kinds of classification models the computation of the SHAP-score can be done efficiently? This is the subject of this paper.

In this work, we focus on classifiers working with binary feature values (i.e., propositional features that can take the values 0 or 1), and that return 1 (accept) or 0 (reject) for each entity. We will call these Boolean classifiers. The second assumption that we make is that the underlying probability distribution on the population of entities is what we call a product distribution, where each binary feature x has a probability p(x) of being equal to 1, independently of the other features. We note here that the restriction to binary inputs can be relevant in many practical scenarios where the features are of a propositional nature.

More specifically, we investigate Boolean classifiers defined as deterministic and decomposable Boolean circuits, a widely studied model in knowledge compilation [START_REF] Darwiche | On the tractable counting of theory models and its application to truth maintenance and belief revision[END_REF][START_REF] Darwiche | A Knowledge Compilation Map[END_REF]. Such circuits encompass a wide range of Boolean models and binary decision diagrams classes that are considered in knowledge compilation, and in AI more generally. For instance, they generalize binary decision trees, ordered binary decision diagrams (OBDDs), free binary decision diagrams (FB-DDs), and deterministic and decomposable negation normal norms (d-DNNFs) [START_REF] Darwiche | On the tractable counting of theory models and its application to truth maintenance and belief revision[END_REF][START_REF] Amarilli | Connecting knowledge compilation classes and width parameters[END_REF][START_REF] Darwiche | On the reasons behind decisions[END_REF]. These circuits are also known under the name of tractable Boolean circuits, that is used in recent literature [START_REF] Shih | Verifying binarized neural networks by Angluin-style learning[END_REF][START_REF] Shi | On tractable representations of binary neural networks[END_REF]Shih, Choi, and Darwiche 2018b,a;Shih et al. 2019;[START_REF] Peharz | Einsum networks: Fast and scalable learning of tractable probabilistic circuits[END_REF]). We provide an example of a deterministic and decomposable Boolean circuit next (and give the formal definition in Section 2).

Example 1.1. We want to classify papers submitted to a conference as rejected (Boolean value 0) or accepted (Boolean value 1). Papers are described by features fg, dtr, nf and na, which stand for "follows guidelines", "deep theoretical result", "new framework" and "nice applications", respectively. The Boolean classifier for the papers is given by the Boolean circuit in Figure 1. The input of this circuit are the features fg, dtr, nf and na, each of which can take value either 0 or 1, depending on whether the feature is present (1) or absent (0). The nodes with labels ¬, ∨ or ∧ are logic gates, and the associated Boolean value of each one of them depends on the logical connective represented by its label and the Boolean values of its inputs. The output value of the circuit is given by the top node in the figure .  The Boolean circuit in Figure 1 is said to be decomposable, because for each ∧-gate, the sets of features of its inputs are pairwise disjoint. For instance, in the case of the top node in Figure 1, the left-hand side input has {fg} as its set of features, while its right-hand side input has {dtr, nf, na} as its set of features, which are disjoint. Also, this circuit is said to be deterministic, which means that for every ∨-gate, two (or more) of its inputs cannot be given value 1 by the same Boolean assignment for the features. For instance, in the case of the only ∨-gate in Figure 1, if a Boolean assignment for the features gives value 1 to its left-hand side input, then feature dtr has to be given value 1 and, thus, such an assignment gives value 0 to the right-hand side input of the ∨gate. In the same way, it can be shown that if a Boolean assignment for the features gives value 1 to the right-hand side input of this ∨-gate, then it gives value 0 to its left-hand side input.

Readers who are not familiar with knowledge compilation can simply think about deterministic and decomposable circuits as a tool for establishing in a uniform manner the tractability of computing SHAP-scores on several Boolean classifier classes. Our main contributions are the following:

1. We provide a polynomial time algorithm that computes the SHAP-score for deterministic and decomposable Boolean circuits, in the special case of uniform prob- ability distributions (that is, when each p(x) is 1 2 ). In particular, this provides a precise proof of the claim made in [START_REF] Lundberg | From local explanations to global understanding with explainable AI for trees[END_REF]) that the SHAP-score for Boolean classifiers given as decision trees can be computed in polynomial time. Moreover, we also obtain as a corollary that the SHAP-score for Boolean classifiers given as OB-DDs, FBDDs and d-DNNFs can be computed in polynomial time.

2. We observe that computing the SHAP-score on Boolean circuits in a class is always polynomially as hard as the model counting problem for that class (under a mild condition). By using this observation, we obtain that each one of the determinism assumption and the decomposability assumption is necessary for tractability.

3. Last, we show that the results above (and most interestingly, the polynomial-time algorithm) can be extended to the SHAP-score defined on product distributions for the entity population.

Our contributions should be compared to the results obtained in the contemporaneous paper [START_REF] Van Den Broeck | On the Tractability of SHAP Explanations[END_REF]. There, the authors establish the following theorem: for every class C of classifiers and under product distributions, the problem of computing the SHAP-score for C is polynomial-time equivalent to the problem of computing the expected value for the models in C. Since computing expectations is in polynomial time for tractable Boolean circuits, this in particular implies that computing the SHAP-score is in polynomial time for the circuits that we consider; in other words, their results capture ours. However, there is a fundamental difference in the approach taken to show tractability: their reduction uses multiple oracle calls to the problem of computing expectations, whereas we provide a more direct algorithm to compute the SHAP-score on these circuits.

Our algorithm for computing the SHAP-score could be used in practical scenarios. Indeed, recently, some classes of classifiers have been compiled into tractable Boolean circuits. This is the case, for instance, of Bayesian Classifiers (Shih, Choi, and Darwiche 2018a), Binary Neural Networks [START_REF] Shi | On tractable representations of binary neural networks[END_REF], and Random Forests [START_REF] Choi | On Symbolically Encoding the Behavior of Random Forests[END_REF]. The idea is to start with a Boolean classifier M given in a formalism that is hard to interpret -for instance a Binary neural network -and to compute a tractable Boolean circuit M ′ that is equivalent to M (this computation can be expensive). One can then use M ′ and the nice properties of tractable Boolean circuits to interpret the decisions of the model. Hence, this makes it possible to apply the results in this paper on the SHAP-score to those classes of classifiers.

Paper structure. We give preliminaries in Section 2. In Section 3, we prove that the SHAP-score can be computed in polynomial time for deterministic and decomposable Boolean circuits for uniform probability distributions. In Section 4 we establish the limits of the tractable computation of the SHAP-score. Next we show in Section 5 that our results extend to the setting where we consider product distributions. We conclude and discuss future work in Section 6.

Preliminaries

Entities, distributions and classifiers

Let X be a finite set of features, also called variables. An entity over X is a function e : X → {0, 1}. We denote by ent(X) the set of all entities over X. On this set, we consider the uniform probability distribution, i.e., for an event E ⊆ ent(X), we have that P (E) := |E| 2 |X| . We will come back to this assumption in Section 5, where we will consider the more general product distributions (we start with the uniform distribution to ease the presentation).

A Boolean classifier M over X is a function M : ent(X) → {0, 1} that maps every entity over X to 0 or 1. We say that M accepts an entity e when M (e) = 1, and that it rejects it if M (e) = 0. Since we consider ent(X) to be a probability space, M can be regarded as a random variable.

The SHAP-score over Boolean classifiers

Let M : ent(X) → {0, 1} be a Boolean classifier over the set X of features. Given an entity e over X and a subset S ⊆ X of features, the set cw(e, S) := {e ′ ∈ ent(X) | e ′ (x) = e(x) for each x ∈ S} contains those entities that coincide with e over each feature in S. In other words, cw(e, S) is the set of entities that are consistent with e on S. Then, given an entity e ∈ ent(X) and S ⊆ X, we define the expected value of M over X \ S with respect to e as φ(M, e, S) := E M (e ′ ) | e ′ ∈ cw(e, S) .

Since we consider the uniform distribution over ent(X), we have that φ(M, e, S) = e ′ ∈cw(e,S)

1 2 |X\S| M (e ′ ).
Intuitively, φ(M, e, S) is the probability that M (e ′ ) = 1, conditioned on the inputs e ′ ∈ ent(X) to coincide with e over each feature in S. This function is then used in the general formula of the Shapley value [START_REF] Shapley | A value for n-person games[END_REF][START_REF] Roth | The Shapley value: essays in honor of Lloyd S. Shapley[END_REF]) to obtain the SHAP-score for feature values in e. Definition 2.1. Given a Boolean classifier M over a set of features X, an entity e over X, and a feature x ∈ X, the SHAP score of feature x on e with respect to M is defined as

SHAP(M, e, x) := S⊆X\{x} |S|! (|X| -|S| -1)! |X|! φ(M, e, S ∪ {x}) -φ(M, e, S) . (1)
Thus, SHAP(M, e, x) is a weighted average of the contribution of feature x on e to the classification result, i.e., of the differences between having it and not, under all possible permutations of the other feature values. Observe that, from this definition, a high positive value of SHAP(M, e, x) intuitively means that setting x to e(x) strongly leans the classifier towards acceptance, while a high negative value of SHAP(M, e, x) means that setting x to e(x) strongly leans the classifier towards rejection. Several restrictions of Boolean circuits with good computational properties have been studied. Let C be a Boolean circuit over a set of variables X and g a gate of C. The Boolean circuit C g over X is defined by considering the subgraph of C induced by the set of gates g ′ in C for which there exists a path from g ′ to g in C. Notice that g is the output gate of C g . The set var(g) is defined as the set of variables x ∈ X such that there exists a variable gate with label x in C g . Then, an ∨-gate g of C is said to be deterministic if for every pair g 1 , g 2 of distinct input gates of g, the Boolean circuits C g1 and C g2 are disjoint in the sense that there is no entity e that is accepted by both C g1 and C g2 (that is, there is no entity e ∈ ent(X) such that C g1 (e) = C g2 (e) = 1). The circuit C is called deterministic if every ∨-gate of C is deterministic. An ∧-gate g of C is said to be decomposable if for every pair g 1 , g 2 of distinct input gates of g, we have that var(g 1 ) ∩ var(g 2 ) = ∅. Then, C is called decomposable if every ∧-gate of C is decomposable.

Deterministic and decomposable Boolean circuits

A
Example 2.2. In Example 1.1, we explained at an intuitive level why the Boolean circuit in Figure 1 is deterministic and decomposable. By using the terminology defined in the previous paragraph, it can be formally checked that this Boolean circuit indeed satisfies these conditions.

As mentioned before, deterministic and decomposable Boolean circuits generalize many decision diagrams and Boolean circuits classes. We refer to [START_REF] Darwiche | On the tractable counting of theory models and its application to truth maintenance and belief revision[END_REF][START_REF] Amarilli | Connecting knowledge compilation classes and width parameters[END_REF] for detailed studies of knowledge compilation classes and of their precise relationships. For the reader's convenience, we explain in the supplementary material how FBDDs and binary decision trees can be encoded in linear time as deterministic and decomposable Boolean circuits.

Tractable Computation of the SHAP-Score

In this section, we prove our first tractability result, namely, that computing the SHAP-score for Boolean classifiers given as deterministic and decomposable Boolean circuits can be done in polynomial time, for uniform probability distributions. Formally: Theorem 3.1. The following problem can be solved in polynomial time. Given as input a deterministic and decomposable Boolean circuit C over a set of features X, an entity e : X → {0, 1}, and a feature x ∈ X, compute the value SHAP(C, e, x).

In particular, since binary decision trees, OBDDs, FBDDs and d-DNNFs are all restricted kinds of deterministic and decomposable circuits, we obtain as a consequence of Theorem 3.1 that this problem is also in polynomial time for these classes. For instance, for binary decision trees we obtain: Corollary 3.2. The following problem can be solved in polynomial time. Given as input a binary decision tree T over a set of features X, an entity e : X → {0, 1}, and a feature x ∈ X, compute the value SHAP(T, e, x).

The authors of [START_REF] Lundberg | From local explanations to global understanding with explainable AI for trees[END_REF] give a proof of this result, but, unfortunately, with few details to fully understand it. Moreover, it is important to notice that Theorem 3.1 is a nontrivial extension of the result for decision trees, as it is known that deterministic and decomposable circuits can be exponentially more succinct than binary decision trees (in fact, than FBDDs) at representing Boolean classifiers [START_REF] Darwiche | On the tractable counting of theory models and its application to truth maintenance and belief revision[END_REF][START_REF] Amarilli | Connecting knowledge compilation classes and width parameters[END_REF].

In order to prove Theorem 3.1, we need to introduce some notation. Let M be a Boolean classifier over a set of features X. We write SAT(M ) ⊆ ent(X) for the set of entities that are accepted by M , and #SAT(M ) for the cardinality of this set. Let e, e ′ ∈ ent(X) be a pair of entities over X. We define sim(e, e ′ ) := {x ∈ X | e(x) = e ′ (x)} to be the set of features on which e and e ′ coincide. Given a Boolean classifier M over X, an entity e ∈ ent(X) and a natural number k ≤ |X|, we define the set SAT(M, e, k) := SAT(M ) ∩ {e ′ ∈ ent(X) | |sim(e, e ′ )| = k}, in other words, the set of entities e ′ that are accepted by M and which coincide with e in exactly k features. Naturally, we write #SAT(M, e, k) for the size of SAT(M, e, k).

Example 3.3. Let M be the Boolean classifier represented by the circuit in Example 1.1. Then SAT(M ) is the set containing all papers that are accepted according to M , so that #SAT(M ) = 5. Now, consider the entity e such that e(fg) = 1, e(dtr) = 1, e(nf) = 0 and e(na) = 1. Then one can check that #SAT(M, e, 0) = 0, #SAT(M, e, 1) = 0, #SAT(M, e, 2) = 2, #SAT(M, e, 3) = 2 and #SAT(M, e, 4) = 1.

Our proof of Theorem 3.1 is technical and is divided into two modular parts. The first part, which is developed in Section 3.1, consists in showing that the problem of computing SHAP(•, •, •) can be reduced in polynomial time to that of computing #SAT(•, •, •). This part of the proof is a sequence of formula manipulations, and it only uses the fact that deterministic and decomposable circuits can be efficiently conditioned on a variable value (to be defined in Section 3.1). In the second part of the proof, which is developed in Section 3.2, we show that computing #SAT(•, •, •) can be done in polynomial time for deterministic and decomposable Boolean circuits. It is in this part that the properties of deterministic and decomposable circuits are really used.

Reducing

SHAP(•, •, •) to #SAT(•, •, •)
In this section, we show that for deterministic and decomposable Boolean circuits, the computation of the SHAPscore can be reduced in polynomial time to the computation of #SAT(•, •, •). To achieve this, we will need two more definitions. Let M be a Boolean classifier over a set of features X and x ∈ X, and let Boolean classifiers M +x : ent(X \ {x}) → {0, 1} and M -x : ent(X \ {x}) → {0, 1} be defined as follows. For e ∈ ent(X \ {x}), we write e +x and e -x the entities over X such that e +x (x) = 1, e -x (x) = 0 and e +x (y) = e -x (y) = e(y) for every y ∈ X \ {x}. Then define M +x (e) := M (e +x ) and M -x (e) := M (e -x ). In the literature, M +x (resp., M -x ) is called the conditioning by x (resp., by ¬x) of M . Conditioning can be done in linear time for a Boolean circuit C by replacing every gate with label x by a constant gate with label 1 (resp., 0). We write C +x (resp., C -x ) for the Boolean circuit obtained via this transformation. One can easily check that, if C is deterministic and decomposable, then C +x and C -x are deterministic and decomposable as well.

We now introduce the second definition needed for the proof. For a Boolean classifier M over a set of variables X, an entity e ∈ ent(X) and an integer k ≤ |X|, we define

H(M, e, k) := S⊆X |S|=k e ′ ∈cw(e,S)
M (e ′ ).

( Then by the definition of the SHAP-score in (1), we have:

SHAP(C, e, x) = n-1 k=0 k!(n -k -1)! n! Diff k (C, e, x).
Observe that all arithmetical terms (such as k! or n!) can be computed in polynomial time: this is simply because n is given in unary, as it is bounded by the size of the circuit. Therefore, it is enough to show how to compute in polynomial time the quantities Diff k (C, e, x) for each k ∈ {0, . . . , n -1}, as n = |X| is bounded by the size of the input (C, e, x). By definition of φ(•, •, •), we have that Diff k (C, e, x) = αβ, where:

α = S⊆X\{x} |S|=k 1 2 n-(k+1) e ′ ∈cw(e,S∪{x}) C(e ′ ) β = S⊆X\{x} |S|=k 1 2 n-k e ′ ∈cw(e,S)
C(e ′ ).

Next we show how the computation of α and β can be reduced in polynomial-time to the computation of H(•, •, •). For an entity e ∈ ent(X) and S ⊆ X, let e |S be the entity over S that is obtained by restricting e to the domain S (that is, formally e |S ∈ ent(S) and e |S (y) := e(y) for every y ∈ S). Then, starting with β, we have that:

β = S⊆X\{x} |S|=k 1 2 n-k e ′ ∈cw(e,S) C(e ′ ) = S⊆X\{x} |S|=k 1 2 n-k e ′ ∈cw(e,S) e ′ (x)=1 C(e ′ ) + S⊆X\{x} |S|=k 1 2 n-k e ′ ∈cw(e,S) e ′ (x)=0 C(e ′ ) = 1 2 n-k S⊆X\{x} |S|=k e ′′ ∈cw(e |X\{x} ,S) C +x (e ′′ ) + 1 2 n-k S⊆X\{x} |S|=k e ′′ ∈cw(e |X\{x} ,S) C -x (e ′′ ) = 1 2 n-k H(C +x , e |X\{x} , k) + H(C -x , e |X\{x} , k) .
The last equality is obtained by using the definition of H(•, •, •). A similar analysis allows us to conclude that:

α =      1 2 n-(k+1) H(C +x , e |X\{x} , k), if C(e) = 1 1 2 n-(k+1) H(C -x , e |X\{x} , k), if C(e) = 0
.

Hence, if we can compute in polynomial time H(•, •, •) for deterministic and decomposable Boolean circuits, then we can compute α and β in polynomial time (because C +x and C -x can be computed in linear time from C, and they are deterministic and decomposable as well). Thus, we can compute Diff k (C, e, x) in polynomial time for each k ∈ {0, . . . , n -1} and, hence, SHAP(C, e, x) as well. In conclusion, SHAP(C, e, x) can be computed in polynomial time if there is a polynomial-time algorithm to compute H(•, •, •) for deterministic and decomposable Boolean circuits.

Reducing from H(•, •, •) to #SAT(•, •, •). We now show that computing H(•, •, •) can be reduced in polynomial time to computing #SAT(•, •, •). Given as input a deterministic and decomposable circuit C over a set of variables X, an entity e ∈ ent(X), and an integer k ≤ |X|, recall the definition of H(C, e, x) in (2). Then consider an entity e ′′ ∈ ent(X) and reason about how many times e ′′ will occur as a summand in the expression (2). First of all, it is clear that if |sim(e, e ′′ )| < k, then e ′′ will not appear in the sum; this is because if e ′ ∈ cw(e, S) for some S ⊆ X such that |S| = k, then S ⊆ sim(e, e with the last equality being obtained by using the definition of #SAT(•, •, •). This concludes the reduction of this section and, hence, the first part of the proof.

Computing #SAT(•, •, •) in polynomial time

We now take care of the second part of the proof of Theorem 3.1, i.e., proving that computing #SAT(•, •, •) for deterministic and decomposable Boolean circuits can be done in polynomial time. To do this, given a deterministic and decomposable Boolean circuit C, we first perform two preprocessing steps on C, which will simplify the proof.

• Rewriting to fan-in at most 2. First, we modify the circuit C so that the fan-in of every ∨and ∧-gate is at most 2. This can simply be done in linear time by rewriting every ∧-gate (resp., and ∨-gate) of fan-in m > 2 with a chain of m -1 ∧-gates (resp., ∨-gates) of fan-in 2. It is clear that the resulting Boolean circuit is deterministic and decomposable. Hence, from now on we assume that the fan-in of every ∨and ∧-gate of C is at most 2. • Smoothing the circuit. A deterministic and decomposable circuit C is smooth [START_REF] Darwiche | On the tractable counting of theory models and its application to truth maintenance and belief revision[END_REF]Shih et al. 2019) if for every ∨-gate g and input gates g 1 , g 2 of g, we have that var(g 1 ) = var(g 2 ), and we call such an ∨gate smooth. A standard construction allows to transform in polynomial time a deterministic and decomposable Boolean circuit C into an equivalent smooth deterministic and decomposable Boolean circuit, and where each gate has fan-in at most 2. Thus, from now on we also assume that C is smooth. We illustrate how the construction works in Example 3.4 . Full details can be found in the supplementary material (namely, in Section E.2, paragraph Smoothing the circuit).

We have all the ingredients to prove that #SAT(•, •, •) can be computed in polynomial time. Let C be a deterministic and decomposable Boolean circuit over a set of variables X, e ∈ ent(X), ℓ a natural number such that ℓ ≤ |X| and n = |X|. For a gate g of C, let R g be the Boolean circuit over var(g) that is defined by considering the subgraph of C induced by the set of gates g ′ in C for which there exists a path from g ′ to g in C. Notice that R g is a deterministic and decomposable Boolean circuit with output gate g. Moreover, for a gate g and natural number k ≤ |var(g)|, define α k g := #SAT(R g , e |var(g) , k), which we recall is the number of entities e ′ ∈ ent(var(g)) such that e ′ satisfies R g and |sim(e |var(g) , e ′ )| = k. We will show how to compute all the values α k g for every gate g of C and k ∈ {0, . . . , |var(g)|} in polynomial time. This will conclude the proof since, for the output gate g out of C, we have that α ℓ gout = #SAT(C, e, ℓ). Next we explain how to compute these values in a bottom-up manner.

Variable gate. g is a variable gate with label y ∈ X, so that var(g) = {y}. Then α 0 g = 1e(y) and α 1 g = e(y). Constant gate. g is a constant gate with label a ∈ {0, 1}.

Then var(g) = ∅ and α 0 g = a.2 ¬-gate. g is a ¬-gate with input gate g ′ . Then var(g) = var(g ′ ), and the values α k g ′ for k ∈ {0, . . . , |var(g)|} have already been computed. Fix k ∈ {0, . . . , |var(g)|}.

Since |var(g)| k is equal to the number of entities e ′ ∈ ent(var(g)) such that |sim(e |var(g) , e ′ )| = k, we have that

α k g = |var(g)| k -α k g ′ .
Therefore, given that |var(g)| k can be computed in polynomial time since k ≤ |var(g)| ≤ n = |X|, we have an efficient way to compute α k g . ∨-gate. g is an ∨-gate. By assumption, g is deterministic, smooth and has fan-in at most 2. If g has only one input g ′ , then clearly var(g) = var(g ′ ) and α k g = α k g ′ for every k ∈ {0, . . . , |var(g)|}. Thus, assume that g has exactly two input gates g 1 and g 2 , and recall that var(g 1 ) = var(g 2 ) = var(g), because g is smooth. Also, recall that α k g1 and α k g2 , for each k ∈ {0, . . . , |var(g)|}, have already been computed. Fix k ∈ {0, . . . , |var(g)|}. Given that g is deterministic and smooth, we have that SAT(R g ) = SAT(R g1 ) ∪ SAT(R g2 ), where SAT(R g1 ) ∩ SAT(R g2 ) = ∅. By intersecting these three sets with the set {e ′ ∈ var(g) | |sim(e |var(g) , e ′ )| = k}, we obtain that SAT(R g , e |var(g) , k) = SAT(R g1 , e |var(g) , k) ∪ SAT(R g2 , e |var(g) , k), where SAT(R g1 , e |var(g) , k) ∩ SAT(R g2 , e |var(g) , k) = ∅. Hence:

#SAT(R g , e |var(g) , k) = #SAT(R g1 , e |var(g) , k) + #SAT(R g2 , e |var(g) , k),
or, in other words, we have that α k g = α k g1 + α k g2 . Hence, we have an efficient way to compute α k g . ∧-gate. g is an ∧-gate. By assumption, recall that g is decomposable and has fan-in at most 2. If g has only one input g ′ , then clearly var(g) = var(g ′ ) and

α k g = α k g ′
for every k ∈ {0, . . . , |var(g)|}. Thus, assume that g has exactly two input gates g 1 and g 2 . Recall then that the values α i g1 and α j g2 , for each i ∈ {0, . . . , |var(g 1 )|} and j ∈ {0, . . . , |var(g 2 )|}, have already been computed. Fix k ∈ {0, . . . , |var(g)|}. Given that g is a decomposable ∧-gate, in this case it is possible to prove that:

α k g = i∈{0,...,
α i g1 • α j g2 . (3)
The complete proof of this property can be found in Appendix B. Therefore, as in the previous cases, we conclude that there is an efficient way to compute α k g . This concludes the proof that #SAT(•, •, •) can be computed in polynomial time for deterministic and decomposable Boolean circuits and, hence, the proof of Theorem 3.1.

Example 3.4. We illustrate how the algorithm for computing the SHAP-score operates on the Boolean circuit C given in Example 1.1. Recall that C is defined over X = {fg, dtr, nf, na}, and assume we want to compute SHAP(C, e, nf) for the entity e with e(x) = 1 for each x ∈ X. By the polynomial time reductions shown in Section 3.1, to compute SHAP(C, e, nf) it suffices to compute H(C -nf , e |X\{nf} , ℓ) and H(C +nf , e |X\{nf} , ℓ) for each ℓ ∈ {0, . . . , 3}, which in turn reduces to the computation of #SAT(C -nf , e |X\{nf} , ℓ) and #SAT(C +nf , e |X\{nf} , ℓ) for each ℓ ∈ {0, . . . , 3}. In what follows, we show how to compute the values #SAT(C +nf , e |X\{nf} , ℓ).

For the sake of presentation, let D := C +nf and e ⋆ = e |X\{nf} , so that we need to compute #SAT(D, e ⋆ , ℓ) for each ℓ ∈ {0, . . . , 3}. Notice that the values to be computed are #SAT(D, e ⋆ , 0) = 0, #SAT(D, e ⋆ , 1) = 0, #SAT(D, e ⋆ , 2) = 2 and #SAT(D, e ⋆ , 3) = 1. To compute #SAT(D, e ⋆ , ℓ), we first need to replace feature nf by constant 1 in C to generate D = C +nf , and then we need to transform D into a Boolean circuit that is smooth and where each gate has fan-in at most 2. The result of this process is shown in Figure 2, where the green node is added when replacing feature nf by constant 1, the gray node is added to satisfy the restriction that each gate has fan-in at most 2, and the blue nodes are added to have a smooth Boolean circuit.

dtr α 0 = 0 α 1 = 1 ∧ α 0 = 0 α 1 = 1 α 2 = 1 ∨ α 0 = 1 α 1 = 1 na α 0 = 0 α 1 = 1 ¬ α 0 = 1 α 1 = 0 na α 0 = 0 α 1 = 1 fg α 0 = 0 α 1 = 1 ∧ α 0 = 0 α 1 = 1 na α 0 = 0 α 1 = 1 1 α 0 = 1 ∧ ¬ α 0 = 1 α 1 = 0 α 0 = 0 α 1 = 1 α 2 = 0 ∨ α 0 = 0 α 1 = 2 α 2 = 1 ∧ α 0 = 0 α 1 = 0 α 2 = 2 α 3 = 1
The algorithm to compute #SAT(D, e ⋆ , ℓ) runs in a bottom-up fashion on the Boolean circuit, computing for each gate g the values α k g for k ∈ {0, . . . , |var(g)|}. We show these values next to each node in Figure 2, but omitting gate subscripts. For instance, for a variable gate g with label na, we have that var(g) = {na}, α 0 g = 0 and α 1 g = 1, given that e ⋆ |var(g) (na) = e ⋆ (na) = 1. Notice that for the output gate g out of the Boolean circuit, which is its top gate, we have that #SAT(D, e ⋆ , ℓ) = α ℓ gout for each ℓ ∈ {0, . . . , 3}, which were the values to be computed.

Limits on the Tractable Computation of the SHAP-Score

We have shown that the SHAP-score can be computed in polynomial time for deterministic and decomposable circuits. A natural question, then, is whether both determinism and decomposability are necessary for this positive result to hold. In this section we show this to be case, at least under standard complexity assumptions. Recall that #P consists of the class of functions that can be defined by counting the number of accepting paths of a non-deterministic Turing machine that works in polynomial time. The notion of hardness for the class #P is defined in terms of polynomial time Turing reductions. Under widely-held complexity assumptions, #P-hard problems cannot be solved in polynomial time [START_REF] Arora | Computational Complexity -A Modern Approach[END_REF]. We can then prove the following: Theorem 4.1. The following problems are #P-hard. 1. Given as input a decomposable Boolean circuit C over a set of features X, an entity e : X → {0, 1}, and a feature x ∈ X, compute the value SHAP(C, e, x). 2. Given as input a deterministic Boolean circuit C over a set of features X, an entity e : X → {0, 1}, and a feature x ∈ X, compute the value SHAP(C, e, x).

To prove Theorem 4.1, we start by showing that there is a polynomial-time reduction from the problem of computing the number of entities that satisfy M , for M an arbitrary Boolean classifier, to the problem of computing the SHAP-score over M . This holds under the mild condition that M (e) can be computed in polynomial time for an input entity e, which is satisfied for all the Boolean circuits and binary decision diagrams classes considered in this paper. The proof of this result follows from well-known properties of Shapley values. (A closely related result can be found as Theorem 5.1 in [START_REF] Bertossi | Causality-based explanation of classification outcomes[END_REF]). Lemma 4.2. Let M be a Boolean classifier over a set of features X. Then for every e ∈ ent(X) we have:

#SAT(M ) = 2 |X| M (e) - x∈X SHAP(M, e, x) .
We prove Lemma 4.2 in the supplementary material. Item (1) in Theorem 4.1 follows then by the following two facts: (a) Counting the number of entities that satisfy a DNF formula is a #P-hard problem [START_REF] Provan | The complexity of counting cuts and of computing the probability that a graph is connected[END_REF], and (b) DNF formulae are particular kinds of decomposable Boolean circuits. Analogously, item (2) in Theorem 4.1 can be obtained from the following two facts: (a) Counting the number of entities that satisfy a 3-CNF formula is a #P-hard problem, and (b) from every 3-CNF formula ψ, we can build in polynomial time an equivalent deterministic Boolean circuit C ψ . Details can be found in the supplementary material.

Tractability for the Product Distribution

In Section 2, we introduce the uniform distribution, and used it so far as a basis for the SHAP-score. Another probability space that is often considered on ent(X) is the product distribution, defined as follows. Let p : X → [0, 1] be a function that associates to every feature x ∈ X a value p(x) ∈ [0, 1]; intuitively, the probability that x takes value 1. Then, the product distribution generated by p is the probability distribution Π p over ent(X) such that, for every e ∈ ent(X),

Π p (e) := x∈X e(x)=1 p(x) • x∈X e(x)=0 (1 -p(x)) .
That is, the product distribution that is determined by prespecified marginal distributions, and that makes the features take values independently from each other. Observe the effect of the probability distribution on the SHAPscore: intuitively, the higher the probability of an entity, the more impact this entity will have on the computation. This can be used, for instance, to avoid bias in the explanations [START_REF] Lundberg | A unified approach to interpreting model predictions[END_REF][START_REF] Bertossi | Causality-based explanation of classification outcomes[END_REF].

Notice that the uniform space is a special case of product space, with Π p invoking p(x) := 1 /2 for every x ∈ X. Thus, our hardness results from Theorem 4.1 also hold in the case where the probabilities p(x) are given as input. What is more interesting is the fact that our tractability result from Theorem 3.1 extends to product distributions. Formally: Theorem 5.1. The following problem can be solved in polynomial time. Given as input a deterministic and decomposable circuit C over a set of features X, rational probability values p(x) for every feature x ∈ X, an entity e : X → {0, 1}, and a feature x ∈ X, compute the value SHAP(C, e, x) under the probability distribution Π p .

The proof of Theorem 5.1 is more involved than that of Theorem 3.1, and is provided in the supplementary material. In particular, the main difficulty is that φ(M, e, S) is no longer equal to e ′ ∈cw(e,S) 1 2 |X\S| M (e ′ ) (as it was the case for the uniform space), because the entities do not all have the same probability. This prevents us from being able to reduce to the computation of #SAT(•, •, •). Instead, we use a different definition of H(•, •, •), and prove that it can directly be computed in a bottom-up fashion on the circuits. We show in Algorithm 1 our algorithm to compute the SHAP score for deterministic and decomposable Boolean circuits under product distributions, which can be extracted from the proof in the supplementary material. Notice by using the techniques presented in Section 3, the first step of the algorithm transforms the input circuit C into an equivalent smooth circuit D where each ∨-gate and ∧-gate has fan-in 2.

Extensions and Future Work

We leave open many interesting directions for future work. For instance, we intend to extend our algorithm for efficiently computing the SHAP-score to work with non-Boolean classifiers, and to consider more general probability distributions that could better capture possible correlations and dependencies between features. We also aim to provide an experimental comparison of our algorithm, but specialized for decision trees, with the one provided in (Lundberg et al. 2020, Alg. 2). Last, we intend to test our algorithm on real-world scenarios.

Algorithm 1: SHAP-scores for deterministic and decomposable Boolean circuits Input : Deterministic and decomposable Boolean circuit C over features X with ouput gate g out , rational probability values p(x) for all x ∈ X, entity e ∈ ent(X), and feature x ∈ X. Output: The value SHAP(C, e, x) under the probability distribution Π p .

1 Transform C into an equivalent smooth circuit D where each ∨-gate and ∧-gate has fan-in 2;

2 Compute the set var(g) for every gate g in D;

3 Compute values γ ℓ g and δ ℓ g for every gate g in D and ℓ ∈ {0, . .

k! (|X| -k -1)! |X|! • (e(x) -p(x))(γ k gout -δ k gout ) ;
Given that g is a decomposable ∧-gate, we have that:

SAT(R g ) = SAT(R g1 ) ⊗ SAT(R g2 ).
Moreover, we have that SAT(R g , e |var(g) , k) = SAT(R g ) ∩ {e ′ ∈ var(g) | |sim(e |var(g) , e ′ )| = k} and Combining the previous results, we obtain that

SAT(R g1 ) ⊗ SAT(R g2 ) ∩ {e ′ ∈ var(g) | |sim(e |var(g) , e ′ )| = k} = {e 1 ∪ e 2 | e 1 ∈ SAT(R g1 ) and e 2 ∈ SAT(R g2 )} ∩ {e ′ ∈ var(g) | |sim(e |var(g) , e ′ )| = k} = {e 1 ∪ e 2 | e 1 ∈ SAT(R g1 ), e 2 ∈ SAT(R g2 ),
SAT(R g , e |var(g) , k) = i∈{0,...,|var(g1)|} j∈{0,...,|var(g2)|} i+j=k SAT(R g1 , e |var(g1) , i) ⊗ SAT(R g2 , e |var(g2) , j).
Thus, given that for every pair i 1 , i 2 ∈ {0, . . . , |var(g 1 )|} such that i 1 = i 2 , it holds that

SAT(R g1 , e |var(g1) , i 1 ) ∩ SAT(R g1 , e |var(g1) , i 2 ) = ∅
(and similarly for R g2 ), we conclude by the definitions of α k g , α i g1 , α j g2 that α k g = i∈{0,...,|var(g1)|} j∈{0,...,|var(g2)|} i+j=k

α i g1 • α j g2 ,
which was to be shown.

C Proof of Lemma 4.2

The validity of the equation from Lemma 4.2 will be consequence of the following property of the SHAP-score: for every Boolean classifier M over X, entity e ∈ ent(X) and feature x ∈ X, it holds that x∈X SHAP(M, e, x) = φ(M, e, X)φ(M, e, ∅).

This property is often called the efficiency property of the Shapley value. Although this is folklore, we prove Equation (4) here for the reader's convenience. For a permutation π : X → {1, . . . , n} and x ∈ X, let S x π denote the set of features that appear before x in π. Formally, S x π := {y ∈ X | π(y) < π(x)}. Then, letting Π(X) be the set of all permutations π : X → {1, . . . , n}, observe that the definition of SHAP-score from Definition 2.1 can be rewritten as

SHAP(M, e, x) = 1 n! π∈Π(X) φ(M, e, S x π ∪ {x}) -φ(M, e, S x π ) .
Hence, we have that

x∈X SHAP(M, e, x) = 1 n! x∈X π∈Π(X) φ(M, e, S x π ∪ {x}) -φ(M, e, S x π ) = 1 n! π∈Π(X) x∈X φ(M, e, S x π ∪ {x}) -φ(M, e, S x π ) = 1 n! π∈Π(X) φ(M, e, X) -φ(M, e, ∅) ,
where the last equality is obtained by noticing that the inner sum is a telescoping sum. This establishes Equation ( 4). Now, we simply use the definition of φ(•, •, •) in this equation to obtain

x∈X SHAP(M, e, x) = M (e) - 1 2 n e ′ ∈ent(X) M (e ′ ) = M (e) - #SAT(M ) 2 n ,
thus proving Lemma 4.2.

D Proof of Theorem 4.1

We have already explained in the body of this article why Item (1) of Theorem 4.1 holds. We now justify that (2) holds, by proving that from every 3-CNF formula ψ, we can build in polynomial time an equivalent deterministic Boolean circuit C ψ . Given a clause γ = (ℓ 1 ∨ ℓ 2 ∨ ℓ 3 ) consisting of three literals, define d(γ) as the propositional formula

(ℓ 1 ∧ ℓ 2 ∧ ℓ 3 ) ∨ (ℓ 1 ∧ ℓ 2 ∧ ℓ 3 ) ∨ (ℓ 1 ∧ ℓ 2 ∧ ℓ 3 ) ∨ (ℓ 1 ∧ ℓ 2 ∧ ℓ 3 ) ∨ (ℓ 1 ∧ ℓ 2 ∧ ℓ 3 ) ∨ (ℓ 1 ∧ ℓ 2 ∧ ℓ 3 ) ∨ (ℓ 1 ∧ ℓ 2 ∧ ℓ 3 ),
where x = ¬x and ¬x = x, for each propositional variable x. Clearly, γ and d(γ) are equivalent formulae. Moreover, given a propositional formula

ψ = γ 1 ∧ • • • ∧ γ k in 3-CNF,
where each γ i is a clause with three literals, define d(ψ) as the propositional formula

d(γ 1 ) ∧ • • • ∧ d(γ k ).
Clearly, ψ and d(ψ) are equivalent formulae, from which we have that #SAT(ψ) = #SAT(d(ψ)). Moreover, d(ψ) can be directly transformed into a deterministic Boolean Circuit C d(ψ) . Hence, from the fact that C d(ψ) can be constructed in polynomial time from an input propositional formula ψ in 3-CNF, and the fact that #SAT(•) is #P-hard for 3-CNFs, we have that Theorem 4.1 (2) holds from Lemma 4.2.

E Proof of Theorem 5.1

In this section, we prove that computing the SHAP-score for Boolean classifiers given as deterministic and decomposable Boolean circuits can be done in polynomial time for product distributions; see Theorem 5.1 for the formal statement. As mentioned in Section 5, the proof will be slightly more involved than that of Theorem 3.1; this is because not all entities have the same probability, and this prevents us from reducing to #SAT(•, •, •). Instead, we will use a different definition of H(•, •, •) and show that it can directly be computed bottom-up on the circuits. But before that, we introduce new notation that will be more convenient for this proof. For a Boolean classifier M over features X, probability distribution3 D : ent(X) → [0, 1], entity e ∈ ent(X) and set S ⊆ X, we define φ D (M, e, S) := E e ′ ∼D M (e ′ ) | e ′ ∈ cw(e, S) .

Notice that we now use the notation E e ′ ∼D [f (e ′ )] for expected value of a random variable f , instead of the simpler E[f (e ′ )] that we used in the body of the paper. This is because we will sometimes need to make explicit what is the probability distribution to consider. Then given a Boolean classifier M over a set of features X, a probability distribution D over ent(X), an entity e over X, and a feature x ∈ X, the Shapley value of feature x in e with respect to M under D is defined as

SHAP D (M, e, x) := S⊆X\{x} |S|! (|X| -|S| -1)! |X|! φ D (M, e, S ∪ {x}) -φ D (M, e, S) . (5)
Note that by taking D to be the uniform probability distribution on ent(X), we obtain the definition that we considered in Section 2. In this section we will consider the product distributions Π p as defined in Section 5. With these notation in place, we can now start the proof.

For a Boolean classifier M over a set of variables X, a probability distribution D over ent(X), an entity e ∈ ent(X) and a natural number k ≤ |X|, define

H D (M, e, k) := S⊆X |S|=k E e ′ ∼D [M (e ′ ) | e ′ ∈ cw(e, S)].
Our proof of Theorem 5.1 is divided into two modular parts. The first part, which is developed in Section E.1, consists in showing that the problem of computing SHAP Π• (•, •, •) can be reduced in polynomial time to that of computing H Π• (•, •, •). This part of the proof is again a sequence of formula manipulations, and it only uses the fact that deterministic and decomposable circuits can be efficiently conditioned on a variable value. In the second part of the proof, which is developed in Section E.2, we show that computing H Π• (•, •, •) can be done in polynomial time for deterministic and decomposable Boolean circuits. It is in this part that the magic of deterministic and decomposable circuits really operates.

E.1 Reducing in polynomial

-time from SHAP Π• (•, •, •) to H Π• (•, •, •)
In this section, we show that for deterministic and decomposable Boolean circuits and under product distributions, the computation of the SHAP-score can be reduced in polynomial time to the computation of H Π• (•, •, •). We wish to compute SHAP Πp (C, e, x), for a given deterministic and decomposable circuit C over a set of variables X, probability mapping p : X → [0, 1], entity e ∈ ent(X) and feature x ∈ X. Define

+ (1 -p(x)) • S⊆X\{x} |S|=k E e ′′ ∼Πp |X\{x} [C -x (e ′′ ) | e ′′ ∈ cw(e |X\{x} , S)] = p(x) • H Πp |X\{x} (C +x , e |X\{x} , k) + (1 -p(x)) • H Πp |X\{x} (C -x , e |X\{x} , k),
where the last equality is obtained simply by using the definition of We first perform two preprocessing steps on C, which will simplify the proof. These are the same preprocessing steps that we did in Section 3, but we added more details for the reader's convenience.

Rewriting to fan-in at most 2. First, we modify the circuit C so that the fan-in of every ∨and ∧-gate is at most 2. This can simply be done in linear time by rewriting every ∧-gate (resp., and ∨-gate) of fan-in m > 2 with a chain of m -1 ∧-gates (resp., ∨-gates) of fan-in 2. It is clear that the resulting Boolean circuit is deterministic and decomposable. Hence, from now on we assume that the fan-in of every ∨and ∧-gate of C is at most 2.

Smoothing the circuit. Recall that a deterministic and decomposable circuit C is smooth if for every ∨-gate g and input gates g 1 , g 2 of g, we have that var(g 1 ) = var(g 2 ), and we call such an ∨-gate smooth. We modify as follows the circuit C so that it becomes smooth. Recall that by the previous paragraph, we assume that the fan-in of every ∨-gate is at most 2. For an ∨-gate g of C having two input gates g 1 , g 2 violating the smoothness condition, define S 1 := var(g 1 ) \ var(g 2 ) and S 2 := var(g 2 ) \ var(g 1 ), and let d S1 , d S2 be Boolean circuits defined as follows. We will show how to compute all the values α l g for every gate g of C and l ∈ {0, . . . , |var(g)|} in polynomial time. This will conclude the proof since, for the output gate g out of C, we have that α k gout = H Πp (C, e, k). Next we explain how to compute these values by bottom-up induction on C.

Variable gate. g is a variable gate with label y ∈ X, so that var(g) = {y}. Then for e ′ ∈ ent({y}) we have R g (e ′ ) = e ′ (y), therefore ¬-gate. g is a ¬-gate with input gate g ′ . Notice that var(g) = var(g ′ ). Then, since for e ′ ∈ ent(var(g)) we have that R g (e ′ ) = 1 -R g ′ (e ′ ), we have for every l ∈ {0, . . . , |var(g)|}. By induction, the values α l g ′ for l ∈ {0, . . . , |var(g)|} have already been computed. Thus, we can compute all the values α l g for l ∈ {0, . . . , |var(g)|} in polynomial time. ∨-gate. g is an ∨-gate. By assumption, recall that g is deterministic, smooth and has fan-in at most 2. If g has only one input g ′ , then clearly var(g) = var(g ′ ) and α l g = α l g ′ for every l ∈ {0, . . . , |var(g)|}. Thus, assume that g has exactly two input gates g 1 and g 2 , and recall that var(g 1 ) = var(g 2 ) = var(g), because g is smooth. Given that g is deterministic, observe that for every e ′ ∈ ent(var(g)) we have R g (e ′ ) = R g1 (e ′ ) + R g1 (e ′ ). But then for l ∈ {0, . . . , |var(g)|} we have = α l g1 + α l g2 , where the second equality is by linearity of the expectation, and the last equality is valid because g is smooth. By induction, the values α l g1 and α l g2 , for each l ∈ {0, . . . , |var(g)|}, have already been computed. Therefore, we can compute all the values α l g for l ∈ {0, . . . , |var(g)|} in polynomial time. ∧-gate. g is an ∧-gate. By assumption, recall that g is decomposable and has fan-in at most 2. If g has only one input g ′ , then clearly var(g) = var(g ′ ) and α l g = α l g ′ for every l ∈ {0, . . . , |var(g)|}. Thus, assume that g has exactly two input gates g 1 and g 2 . For e ′ ∈ ent(var(g)) we have that R g (e ′ ) = R g1 (e ′ |var(g1) )•R g2 (e ′ |var(g2) ). Moreover, since var(g) = var(g 1 )∪var(g 2 ) and var(g 1 ) ∩ var(g 2 ) = ∅ (because g is decomposable), observe that every S ⊆ var(g) can be uniquely decomposed into S 1 ⊆ var(g 1 ), S 2 ⊆ var(g 2 ) such that S = S 1 ∪ S 2 . Henceforth, for l ∈ {0, . . . , |var(g)|} we have By induction, the values α l1 g1 and α l2 g2 , for each l 1 ∈ {0, . . . , |var(g 1 )|} and l 2 ∈ {0, . . . , |var(g 2 )|}, have already been computed. Therefore, we can compute all the values α l g for l ∈ {0, . . . , |var(g)|} in polynomial time. This concludes the proof of Lemma E.1 and, hence, the proof of Theorem 5.1.

α 0 g = S⊆{y} |S|=0 E e ′ ∼Πp |{y} [e ′ (

  Figure 1: A deterministic and decomposable Boolean Circuit as a classifier.

)

  We first explain how computing SHAP(•, •, •) can be reduced in polynomial time to the problem of computing H(•, •, •), and then how computing H(•, •, •) can be reduced in polynomial time to computing #SAT(•, •, •).Reducing from SHAP(•, •, •) to H(•, •, •). We need to compute SHAP(C, e, x), for a given deterministic and decomposable circuit C over a set of variables X, entity e ∈ ent(X), and feature x ∈ X. Let n = |X|, and define Diff k (C, e, x) := S⊆X\{x} |S|=k (φ(C, e, S ∪{x})φ(C, e, S)).

  ′ ) and, thus, k ≤ |sim(e, e ′ )|. Now, how many times does an entity e ′′ ∈ ent(X) such that |sim(e, e ′′ )| ≥ k occur as a summand in the expression? The answer is simple: once per S ⊆ sim(e, e ′′ ) of size k. Since there are |sim(e,e ′′ )| k such sets S, we obtain that H(C, e, k) is equal to e ′′ ∈ent(X) |sim(e,e ′′ )|≥k |sim(e, e ′′ )| k • C(e ′′ ) = e ′′ ∈SAT(C) |sim(e,e ′′ )|≥k |sim(e, e ′′ )| k = n ℓ=k e ′′ ∈SAT(C) |sim(e,e ′′ )|=ℓ |sim(e, e ′′ )| k (C, e, ℓ),

Figure 2 :

 2 Figure 2: Execution of our algorithm to compute #SAT(•, •, •) over the Boolean circuit C +nf from Example 3.4.

  and |sim(e |var(g) , e 1 ∪ e 2 )| = k} = {e 1 ∪ e 2 | e 1 ∈ SAT(R g1 ), e 2 ∈ SAT(R g2 ), and there exist i ∈ {0, . . . , |var(g 1 )|}, j ∈ {0, . . . , |var(g 2 )|} such that |sim(e |var(g1) , e 1 )| = i, |sim(e |var(g2) , e 2 )| = j, and i + j = k} = i∈{0,...,|var(g1)|} j∈{0,...,|var(g2)|} i+j=k {e 1 | e 1 ∈ SAT(R g1 ) and |sim(e |var(g1) , e 1 )| = i} ⊗ {e 2 | e 2 ∈ SAT(R g2 ) and |sim(e |var(g2) , e 2 )| = j} = i∈{0,...,|var(g1)|} j∈{0,...,|var(g2)|} i+j=k SAT(R g1 , e |var(g1) , i) ⊗ SAT(R g2 , e |var(g2) , j).

  Diff k (C, e, x) := S⊆X\{x} |S|=k (φ Πp (C, e, S ∪ {x})φ Πp (C, e, S)),and let n = |X|. We then haveSHAP Πp (C, e, x) = S⊆X\{x} |S|!(n -|S| -1)! n! (φ Πp (C, e, S ∪ {x})φ Πp (C, e, S)) nk -1)! n! Diff k (C, e, x).Therefore, it is enough to show how to compute in polynomial time the quantitiesDiff k (C, e, x) for each k ∈ {0, . . . , n -1}. By definition of φ Π• (•, •, •) we have that Diff k (C, e, x) = S⊆X\{x} |S|=k E e ′ ∼Πp [C(e ′ ) | e ′ ∈ cw(e, S ∪ {x})] ( †) -S⊆X\{x} |S|=k E e ′ ∼Πp [C(e ′ ) | e ′ ∈ cw(e, S)] .In this expression, let α and β be the left-and right-hand side terms in the subtraction. For a set of features X, mapping p : X → [0, 1] and S ⊆ X, we write p |S : S → [0, 1] for the mapping that is the restriction of p to S, and Π p |S : ent(S) → [0, 1] for the corresponding product distribution on ent(S). Looking closer at β, we have that β = S⊆X\{x} |S|=k E e ′ ∼Πp [C(e ′ ) | e ′ ∈ cw(e, S)] = p(x) • S⊆X\{x} |S|=k E e ′ ∼Πp [C(e ′ ) | e ′ ∈ cw(e, S) and e ′ (x) = 1] + (1p(x)) • S⊆X\{x} |S|=k E e ′ ∼Πp [C(e ′ ) | e ′ ∈ cw(e, S) and e ′ (x) = 0] = p(x) • S⊆X\{x} |S|=k E e ′′ ∼Πp |X\{x} [C +x (e ′′ ) | e ′′ ∈ cw(e |X\{x} , S)]

E

  y) | e ′ ∈ cw(e |{y} , S)]= E e ′ ∼Πp |{y} [e ′ (y) | e ′ ∈ cw(e |{y} , ∅)] = E e ′ ∼Πp |{y} [e ′ (y)] = 1 • p(y) + 0 • (1p(y)) = p(y) e ′ ∼Πp |{y} [e ′ (y) | e ′ ∈ cw(e |{y} , S)] = E e ′ ∼Πp |{y} [e ′ (y) | e ′ ∈ cw(e |{y} , {y})] = e(y).Constant gate. g is a constant gate with label a ∈ {0, 1}, and var(g) = ∅. We recall the mathematical convention that there is a unique function with the empty domain and, hence, a unique entity over ∅. But thenα 0 g = S⊆∅ |S|=0 E e ′ ∼Πp|∅ [a | e ′ ∈ cw(e |∅ , S)] = E e ′ ∼Πp |∅ [a | e ′ ∈ cw(e |∅ , ∅)] = a.

  |S|=lE e ′ ∼Πp |var(g) [1 -R g ′ (e ′ ) | e ′ ∈ cw(e |var(g) , S)].By linearity of expectations we deduce thatα l g = S⊆var(g) |S|=l E e ′ ∼Πp |var(g) [1 | e ′ ∈ cw(e |var(g) , S)] -S⊆var(g) |S|=l E e ′ ∼Πp |var(g) [R g ′ (e ′) | e ′ ∈ cw(e |var(g)

  |S|=lE e ′ ∼Πp |var(g) [R g1 (e ′ ) + R g2 (e ′ ) | e ′ ∈ cw(e |var(g) , S)] = S⊆var(g) |S|=l E e ′ ∼Πp |var(g) [R g1 (e ′ ) | e ′ ∈cw(e |var(g) , S)] + S⊆var(g) |S|=l E e ′ ∼Πp |var(g) [R g2 (e ′ ) | e ′ ∈ cw(e |var(g) , S)]

EE

  E e ′ ∼Πp |var(g) [R g1 (e ′ |var(g1) ) • R g2 (e ′ |var(g2) ) | e ′ ∈ cw(e |var(g) , S 1 ∪ S 2 )].But, by definition of the product distribution Π p |var(g) , we have that R g1 (e ′ |var(g1) ) and R g2 (e ′ |var(g2) ) are independent random variables, hence we deduceE e ′ ∼Πp |var(g) [R g1 (e ′ |var(g1) ) | e ′ ∈ cw(e |var(g) , S 1 ∪ S 2 )] × E e ′ ∼Πp |var(g) [R g2 (e ′ |var(g2) ) | e ′ ∈ cw(e |var(g) , S 1 ∪ S 2 )] . e ′′ ∼Πp |var(g 1 ) [R g1 (e ′′ ) | e ′′ ∈cw(e |var(g1) , S 1 )] × E e ′′ ∼Πp |var(g 2 ) [R g2 (e ′′ ) | e ′′ ∈ cw(e |var(g2) , S 2 )] , where the last equality is simply by definition of the product distributions, and because R g1 (e ′ |var(g1) ) is independent of the value e ′ |var(g2) , and similarly for R g2 (e ′ |var(g2) ). But then α l g = S1⊆var(g1) |S1|≤l E e ′′ ∼Πp |var(g 1 ) [R g1 (e ′′ ) | e ′′ ∈ cw(e |var(g1) , S 1 )] × S2⊆var(g2) |S2|=|var(g)|-|S1| 16 E e ′′ ∼Πp |var(g 2 ) [R g2 (e ′′ ) | e ′′ ∈ cw(e |var(g2) , S 2 )] = S1⊆var(g1) |S1|≤l E e ′′ ∼Πp |var(g 1 ) [R g1 (e ′′ ) | e ′′ ∈ cw(e |var(g1) , S 1 )] × α |var(g)|-|var(e ′′ ∼Πp |var(g 1 ) [R g1 (e ′′ ) | e ′′ ∈ cw(e |var(g1) , S 1 )]

  . , |var(g) \ {x}|} by bottom-up induction on D as follows:

	4	if g is a constant gate with label a ∈ {0, 1} then
	5	γ 0 g , δ 0 g ← a;
	6	else if g is a variable gate with var(g) = {x}
		then
	7	γ 0 g ← 1;
	8	δ 0 g ← 0;
	10	γ 0 g , δ 0 g ← p(y);
	11	γ 1 g , δ 1 g ← e(y);
	14	γ ℓ g ← |var(g)\{x}| ℓ	-γ ℓ g ′ ;
	15	δ ℓ g ← |var(g)\{x}| ℓ	-δ ℓ g ′ ;
	19	γ ℓ g ← γ ℓ g1 + γ ℓ g2 ;
	20	δ ℓ g ← δ ℓ g1 + δ ℓ g2 ;
	21	end
	22	else if g is an ∧-gate with input gates g 1 , g 2 then
	23	for ℓ ∈ {0, . . . , |var(g) \ {x}|} do
	24	γ ℓ g ← ℓ1∈{0,...,|var(g1)\{x}|}	γ ℓ1 g1 • γ ℓ2 g2 ;
		ℓ2∈{0,...,|var(g2)\{x}|}
		ℓ1+ℓ2=ℓ
	25	δ ℓ g ← ℓ1∈{0,...,|var(g1)\{x}|}	δ ℓ1 g1 • δ ℓ2 g2 ;
		ℓ2∈{0,...,|var(g2)\{x}|}
		ℓ1+ℓ2=ℓ
	26	end
	27 end
	28 return
		|X|-1
		k=0

9 else if g is a variable gate with var(g) = {y} and y = x then 12 else if g is a ¬-gate with input gate g ′ then 13 for ℓ ∈ {0, . . . , |var(g) \ {x}|} do 16 end 17 else if g is an ∨-gate with input gates g 1 , g 2 then 18 for ℓ ∈ {0, . . . , |var(g) \ {x}|} do

  H • (•, •, •). Hence, if we could compute in polynomial time H Π• (•, •, •) for deterministic and decomposable Boolean circuits, then we could compute β in polynomial time as C +x and C -x can be computed in linear time from C, and they are deterministic and decomposable Boolean circuits as well. We now inspect the term α, which we recall is α = S⊆X\{x} |S|=k E e ′ ∼Πp [C(e ′ ) | e ′ ∈ cw(e, S ∪ {x})]. ′′ ∼Πp |X\{x} [C +x (e ′′ ) | e ′′ ∈ cw(e |X\{x} , S)]

	But then observe that, for S ⊆ X \ {x} and e ′ ∈ cw(e, S ∪ {x}), it holds that
	C(e ′ ) =	C +x (e ′ |X\{x} ) if e(x) = 1 C -x (e ′ |X\{x} ) if e(x) = 0	.
	Therefore, if e(x) = 1, we have that
	α =	E e
	S⊆X\{x}
	|S|=k

= H Πp |X\{x} (C +x , e |X\{x} , k)

whereas if e(x) = 0, we have that

α = H Πp |X\{x} (C -x , e |X\{x} , k).

Hence, again, if we were able to compute in polynomial time H Π• (•, •, •) for deterministic and decomposable Boolean circuits, then we could compute α in polynomial time (as deterministic and decomposable Boolean circuits C +x and C -x can be computed in linear time from C). But then we deduce from ( †) that Diff k (C, e, x) could be computed in polynomial time for each k ∈ {0, . . . , n -1}, from which we have that SHAP Πp (C, e, x) could be computed in polynomial time, therefore concluding the existence of the reduction claimed in this section.

E.2 Computing H Π• (•, •, •) in polynomial time

We now take care of the second part of the proof of Theorem 5.1, i.e., proving that computing H Π• (•, •, •) for deterministic and decomposable Boolean circuits can be done in polynomial time. Formally:

Lemma E.1. The following problem can be solved in polynomial time. Given as input a deterministic and decomposable Boolean circuit C over a set of variables X, rational probability values p(x) for each x ∈ X, an entity e ∈ ent(X) and a natural number k ≤ |X|, compute the quantity H Πp (C, e, k).

  If S 1 = ∅, then d S1 consist of the single constant gate 1. Otherwise, d S1 encodes the propositional formula ∧ x∈S1 (x∨¬x), but it is constructed in such a way that every ∧and ∨-gate has fan-in at most 2. Boolean circuit d S2 is constructed exactly as d S1 but considering the set of variables S 2 instead of S 1 . Observe that var(d S1 ) = S 1 , var(d S2 ) = S 2 and d S1 , d S2 always evaluate to 1. Then, we transform g into a smooth ∨-gate by replacing gate g 1 by a decomposable ∧-gate (g 1 ∧ d S2 ), and gate g 2 by a decomposable ∧-gate (g 2 ∧ d S1 ). This does not change the Boolean classifier computed. Moreover, since var(g1 ∧ d S2 ) = var(g 2 ∧ d S1 ) = var(g 1 ) ∪ var(gProof of Lemma E.1. Let C be a deterministic and decomposable Boolean circuit C over a set of variables X, p : X → [0, 1] be a rational probability mapping, e ∈ ent(X) and k a natural number such that k ≤ |X|, and let n = |X|. For a gate g of C, let R g be the Boolean circuit over var(g) that is defined by considering the subgraph of C induced by the set of gates g ′ in C for which there exists a path from g ′ to g in C.4 Notice that R g is a deterministic and decomposable Boolean circuit with output gate g. Moreover, for a gate g and natural number l ≤ |var(g)|, define α l g := H Πp |var(g) (R g , e |var(g) , l), which we recall is equal, by definition, to H Πp |var(g) (R g , e |var(g) , l) = e ′ ∼Πp |var(g) [R g (e ′ ) | e ′ ∈ cw(e |var(g) , S)].

	S⊆var(g)
	|S|=l

2 ), we have that g is now smooth. Finally, the resulting Boolean circuit is deterministic and decomposable. Hence, by repeating the previous procedure for each non-smooth ∨-gate, we conclude that C can be transformed into an equivalent smooth Boolean circuit in polynomial time, which is deterministic and decomposable, and where each gate has fan-in at most 2. Thus, from now on we also assume that C is smooth.

E

Recall that the fan-in of a gate is the number of its input gates. In our definition of Boolean circuits, we allow unbounded fan-in ∧and ∨-gates.

We recall the mathematical convention that there is a unique function with the empty domain and, hence, a unique entity over ∅.

Note that D : ent(X) → [0, 1] is actually a probability mass function, but we will abuse notation to simplify the presentation.

The only difference between Rg and Cg (defined in Section 2) is that we formally regard Rg as a Boolean classifier over var(g), while we formally regarded Cg as a Boolean classifier over X.

Acknowledgments

Pablo Barceló was funded by Fondecyt grant 1200967.

Supplementary Material: Technical Appendix A Encoding Binary Decision Trees and FBDDs into Deterministic and Decomposable Boolean Circuits

In this appendix, we explain why binary decision trees and free binary decision diagrams (FBDDs) are special kinds of deterministic and decomposable Boolean circuits. First we need to define these formalisms.

Binary Decision Diagrams. A binary decision diagram (BDD) over a set of variables X is a rooted directed acyclic graph D such that: (i) each internal node is labeled with a variable from X, and has exactly two outgoing edges: one labeled 0, the other one labeled 1; and (ii) each leaf is labeled either 0 or 1. Such a BDD represents a Boolean classifier in the following way. Let e be an entity over X, and let π e = u 1 , . . . , u m be the unique path in D satisfying the following conditions: (a) u 1 is the root of D; (b) u m is a leaf of D; and (c) for every i ∈ {1, . . . , m -1}, if the label of u i is x ∈ X, then the label of the edge (u i , u i+1 ) is equal to e(x). Then the value of e in D, denoted by D(e), is defined as the label of the leaf u m . Moreover, a binary decision diagram D is free (FBDD) if for every path from the root to a leaf, no two nodes on that path have the same label, and a binary decision tree is an FBDD whose underlying graph is a tree.

As we show next, FBDDs can be encoded in linear time as deterministic and decomposable Boolean circuits.

Encoding FBDDs into deterministic and decomposable Boolean circuits (Folklore). Given an FBDD D over a set of variables X, we explain how D can be encoded as a deterministic and decomposable Boolean circuit C over X. Notice that the technique used in this example also apply to binary decision trees, as they are a particular case of FBDDs. The construction of C is done by traversing the structure of D in a bottom-up manner. In particular, for every node u of D, we construct a deterministic and decomposable circuit α(u) that is equivalent to the FBDD represented by the subgraph of D rooted at u. More precisely, for a leaf u of D that is labeled with ℓ ∈ {0, 1}, we define α(u) to be the Boolean circuit consisting of only one constant gate with label ℓ. For an internal node u of D labeled with variable x ∈ X, let u 0 and u 1 be the nodes that we reach from u by following the 0and 1-labeled edge, respectively. Then α(u) is the Boolean circuit depicted in the following figure:

x It is clear that the circuit that we obtain is equivalent to the input FBDD. We now argue that this circuit is deterministic and decomposable. For the ∨-gate shown in the figure, if an entity e is accepted by the Boolean circuit in its left-hand size, then e(x) = 0, while if an entity e is accepted by the Boolean circuit in its right-hand size, then e(x) = 1. Hence, we have that this ∨-gate is deterministic, from which we conclude that α(u) is deterministic, as α(u 0 ) and α(u 1 ) are also deterministic by construction. Moreover, the ∧-gates shown in the figure are decomposable as variable x is mentioned neither in α(u 0 ) nor in α(u 1 ): this is because D is a free BDD. Thus, we conclude that α(u) is decomposable, as α(u 0 ) and α(u 1 ) are decomposable by construction. Finally, if u root is the root of D, then by construction we have that α(u root ) is a deterministic and decomposable Boolean circuit equivalent to D. Note that this encoding can trivially be done in linear time. Thus, we often say, by abuse of terminology, that "FBDDs (or binary decision trees) are restricted kinds of deterministic and decomposable circuits".

B Proof of Theorem 3.1

To complete the proof of Theorem 3.1, we need to prove equation (3). Recall that in this case, we have that g is an ∧-gate, which is decomposable and has fan-in at most 2. Moreover, we assume that g has exactly two input gates g 1 and g 2 , and we fix k ∈ {0, . . . , |var(g)|}.

To prove equation (3), we need the following notation. For two disjoint sets of variables X 1 , X 2 and entities e 1 ∈ ent(X 1 ), e 2 ∈ ent(X 2 ), we denote by e 1 ∪ e 2 the entity over X 1 ∪ X 2 that coincides with e 1 over X 1 and with e 2 over X 2 (that is, e 1 ∪ e 2 ∈ ent(X 1 ∪ X 2 ), (e 1 ∪ e 2 )(x 1 ) = e 1 (x 1 ) for every x 1 ∈ X 1 , and (e 1 ∪ e 2 )(x 2 ) = e 2 (x 2 ) for every x 2 ∈ X 2 ). Moreover, for two sets S 1 ⊆ ent(X 1 ), S 2 ⊆ ent(X 2 ), we denote by S 1 ⊗ S 2 the set of entities over X 1 ∪ X 2 defined as S 1 ⊗ S 2 := {e 1 ∪ e 2 | e 1 ∈ S 1 and e 2 ∈ S 2 }.