Efficient Computation of Shap Explanation Scores for Neural Network
  Classifiers via Knowledge Compilation
The use of Shap scores has become widespread in Explainable AI. However,
their computation is in general intractable, in particular when done with a
black-box classifier, such as neural network. Recent research has unveiled
classes of open-box Boolean Circuit classifiers for which Shap can be computed
efficiently. We show how to transform binary neural networks into those
circuits for efficient Shap computation.We use logic-based knowledge
compilation techniques. The performance gain is huge, as we show in the light
of our experiments.
Leopoldo Bertossi, Jorge E. Leon
# Opening Up the Neural Network Classifier for Shap Score Computation

###### Abstract

We address the problem of efficiently computing Shap explanation scores for classifications with machine learning models. With this goal, we show the transformation of binary neural networks (BNNs) for classification into deterministic and decomposable Boolean circuits, for which knowledge compilation techniques are used. The resulting circuit is treated as an open-box model, to compute Shap scores by means of a recent efficient algorithm for this class of circuits. Detailed experiments show a considerable gain in performance in comparison with computing Shap directly on the BNN treated as a black-box model.

## 1 Introduction

In recent years, in which more sophisticated machine learning (ML) models have emerged, and their uses have become widespread, there has been a growing demand for methods to explain and interpret the results they produce. For example, explanations for why a loan application is rejected, or why a medication is recommended, or why a candidate is selected for a job, etc. In this work, we concentrate on explanations for binary classification models that assign one of two labels to the inputs, say say \(0\) or \(1\).

Explanations come in different forms, and can be obtained through different approaches. A common one assigns _attribution scores_ to the features values associated to an input that goes through an ML-based model, to _quantify_ their relevance for the obtained outcome. We concentrate on _local_ scores, i.e. associated to a particular input, as opposed to a global score that indicated the overall relevance of a feature.

A popular local score is Shap [1], which is based on the Shapley value that has introduced and used in coalition game theory and practice for a long time [14, 15]. Another attribution score that has been recently investigated in [1, 16] is Resp, the responsibility score [1] associated to _actual causality_[17]. In this work we concentrate on the Shap score, but the issues investigated here would be also interesting for other scores.

Shap scores can be computed with a black-box or an open-box model [1]. With the former, we do not know or use its internal components, but only its input/output relation. This is the most common approach. In the latter case, we can have access to its internal structure and components, and we can use them for score computation. It is common to consider neural-network-based models as black-box models, because their internal gates and structure may be difficult to understand or process when it comes to explaining classification outputs. However, a decision-tree model, due to its much simpler structure and use, is considered to be open-box for the same purpose.

Even for binary classification models, the complexity of Shap computation is provably hard, actually \(\#P\)-hard for several kinds of binary classification models, independently from whether the internal components of the model are used when computing Shap[1, 16, 17]. However, there are classes of classifiers for which, using the model components and structure, the complexity of Shap computation can be brought down to polynomial time [1, 16, 17].

A polynomial time algorithm for Shap computation with _deterministic and decomposable Boolean circuits_ (dDBCs) was presented in [1]. From this result, the tractability of Shap computation can be obtained for a variety of Boolean circuit-based classifiers and classifiers than can be represented as (or compiled into) them. In particular, this holds for _Ordered Binary Decision Diagrams_ (OBBDs) [15], decision trees, binary neural networks (BNNs), and other established classification models that can be compiled into OBDDs [14, 13]. Similar results can be obtained for _Sentential Decision Diagrams_ (SDDs) [16], which can be seen as dDBCs, and form a convenient _knowledge compilation_ target language [13, 12]. In [12], through a different approach, tractability of Shap computation was obtained for a collection of classifiers that intersect with that in [1].

In this work, we concentrate on explicitly developing this approach to the efficient computation of Shap for _binary neural networks_ (BNNs). For this, and inspired by [14], a BNN is transformed into a dDBC using techniques from _knowledge compilation_[13], an area that investigates the transformation of (usually) propositional theories into an equivalent one with a
canonical syntactic form that has some good computational properties, e.g. tractable model counting. The compilation may incur in a relatively high computational cost [15, 16], but it may still be worth the effort when a particular property will be checked often, as is the case of explanations for the same BNN.

More specifically, we describe in detail how a BNN is first compiled into a propositional formula in Conjunctive Normal Form (CNF), which, in its turn, is compiled into an SDD, which is finally compiled into a dDBC. We show how \(\mathsf{Shap}\) is computed on the resulting circuit via the efficient algorithm in [1]. This compilation is performed once, and is independent from any input to the classifier. The final circuit can be used to compute \(\mathsf{Shap}\) scores for different input entities.

We also make experimental comparisons between this open-box and circuit-based \(\mathsf{Shap}\) computation and that based directly on the BNN treated as a black-box, i.e. using only its input/output relation. We perform comparisons in terms of computation time and alignment of \(\mathsf{Shap}\) scores.

For our experiments, we consider real state as an application domain, where house prices depend on certain features, which we appropriately binarize.1 The problem consists in classifying property blocks, represented as entity records of thirteen feature values, as _high-value_ or _low-value_. This is a binary classification problem for which a BNN is first learnt, and then used.

Footnote 1: We use the California Housing Prices dataset available at [https://www.kaggle.com/datasets/camnugent/california-housing-prices](https://www.kaggle.com/datasets/camnugent/california-housing-prices).

To the best of our knowledge, our work is the first at using knowledge compilation techniques for efficiently computing \(\mathsf{Shap}\) scores, and the first at reporting experiments with the polynomial time algorithms for \(\mathsf{Shap}\) computation on binary circuits. We confirm that \(\mathsf{Shap}\) computation via the dDBC vastly outperforms the direct \(\mathsf{Shap}\) computation on the BNN. It is also the case that the scores obtained are fully aligned, as expected since the dDBC represents the BNN.

Compilation of binary classifiers, in particular BNNs, into obedds was used in [15] to provide different kinds of explanations for outcomes, but not for \(\mathsf{Shap}\) computation or any other kind of attribution score. In this work we concentrate only on explanations based on \(\mathsf{Shap}\) scores. There are several other explanations mechanisms for ML-based classification and decision systems in general, and also specific for neural networks. C.f. [17] and [14] for surveys.

This paper is structured as follows. Section 2 contains background on \(\mathsf{Shap}\) and Boolean circuits. Section 3 show in detail, by means of a running example, the kind of compilation of BNNs into dDBCs we use for the experiments. Section 4 presents the experimental setup, and the results of our experiments with \(\mathsf{Shap}\) computation. In Section 5 we draw some conclusions. Appendices A and B provide additional technical details for Section 3.

## 2 Preliminaries

In coalition game theory and its applications, the Shapley value is a established measure of the contribution by players to a shared wealth that is modelled as a game function. Given a set of players \(S\), and a game function \(G:\mathcal{P}(S)\rightarrow\mathbb{R}\), i.e. mapping subsets of players to real numbers, the general form of the Shapley value for a player \(p\in S\) is:

\[\mathit{Shapley}(S,G,p):= \tag{1}\] \[\sum_{s\subseteq S\setminus\{p\}}\frac{|s|!(|S|-|s|-1)!}{|S|!}(G( s\cup\{p\})-G(s)).\]

It quantifies the contribution of \(p\) to \(G\). It emerges as the only measure that enjoys certain desired properties [12]. Here all possible permutations of subsets of \(S\), and of their complements, are considered. So, this value is the average of differences between having \(p\) or not in a subteam. To apply the Shapley value, one defines a game function \(G\).

Now, consider a fixed entity \(\mathbf{e}=\langle F_{1}(\mathbf{e}),\dots,F_{N}(\mathbf{e})\rangle\) subject to classification. It has values \(F_{i}(\mathbf{e})\) for features \(\mathcal{F}=\{F_{1},\dots,F_{N}\}\). These values are \(0\) or \(1\) for binary features, which is our case. In [15, 16], the Shapley value in (1) is applied with \(\{F_{1}(\mathbf{e}),\dots,F_{N}(\mathbf{e})\}\) as the set of players, and the game function \(\mathcal{G}_{\mathbf{e}}(s):=\mathbb{E}(L(\mathbf{e}^{\prime})\mid\mathbf{e} ^{\prime}_{s}=\mathbf{e}_{s})\), giving rise to the \(\mathsf{Shap}\) score. Here, \(\mathbf{e}_{s}\) is the projection (or restriction) of \(\mathbf{e}\) on (to) the subset \(s\) of features, \(L\) is the label function associated to the classifier; \(0\) or \(1\) in our case. The \(\mathbf{e}^{\prime}\) inside the expected value is an entity whose values coincides with those of \(\mathbf{e}\) for the features in \(s\). Accordingly, for feature \(F\in\mathcal{F}\), and entity \(\mathbf{e}\), \(\mathsf{Shap}\) becomes:

\[\mathsf{Shap}(\mathcal{F},\mathcal{G}_{\mathbf{e}},F)=\sum_{s \subseteq\mathcal{F}\setminus\{F\}}\frac{|s|!(|\mathcal{F}|-|s|-1)!}{|\mathcal{F }|!}\left[\right. \tag{2}\] \[\left.\mathbb{E}(L(\mathbf{e}^{\prime})\mid\mathbf{e}^{\prime}_{S \cup\{F\}}=\mathbf{e}_{s\cup\{F\}})-\mathbb{E}(L(\mathbf{e}^{\prime})\mid \mathbf{e}^{\prime}_{s}=\mathbf{e}_{s})\left.\right].\]

The expected value is defined on the basis of an underlying probability distribution on the entity population. \(\mathsf{Shap}\) quantifies the contribution of feature value \(F(\mathbf{e})\) to the outcome label.

In order to compute \(\mathsf{Shap}\), we only need function \(L\), and none of the internal components of the classifier. Given that all possible subsets of features appear in its definition, \(\mathsf{Shap}\) is bound to be hard to compute. Actually, for some classifiers, its computation may become \(\#P\)-hard (c.f. [14] for some cases). However, in [14], it is shown that \(\mathsf{Shap}\) can be computed in polynomial time for every _deterministic and decomposable Boolean circuit_ (dDBC) used as a classifier. The circuit's internal structure is used in the computation (c.f. Section 4).

Figure 1 shows a Boolean circuit that can be used as a binary classifier, with input features \(x_{1},x_{2},x_{3}\). Their binary values are input at the bottom nodes, and then propagated upwards through the Boolean gates. The binary label is read off from the top node. This circuit is _deterministic_ in that, for every \(\vee\)-gate, at most one of its inputs is \(1\) when the output is \(1\). It is _decomposable_ in that, for every \(\wedge\)-gate, the inputs do not share features. The dDBC in the Figure is also _smooth_,
in that sub-circuits that feed a same \(\vee\)-gate share the same features. It has a _fan-in_ at most two, in that every \(\wedge\)-gate and \(\vee\)-gate have at most two inputs. We denote this subclass of dDBSCs with dDBCSFi(2).

In [1] it is established that Shap can be computed in polynomial time for dDBCSFi(2)-classifiers, assuming that the underlying probability distribution is the uniform, \(P^{u}\), or the product distribution, \(P^{\times}\). They are as follows for binary features: \(P^{u}(\mathbf{e}):=\frac{1}{2^{N}}\) and \(P^{\times}(\mathbf{e}):=\Pi_{i=1}^{N}p_{i}(F_{i}(\mathbf{e}))\), where \(p_{i}(v)\) is the probability of value \(v\in\{0,1\}\) for feature \(F_{i}\).

## 3 Compiling BNNs into dDBCs

In order to compute Shap with a BNN, we convert the latter into a dDBC. Shap scores will be computed in the end with the resulting circuit and the polynomial time algorithm in [1]. The transformation follows the following path, which we briefly describe next:

\[\begin{array}{ccccc}\text{BNN}&\underset{\text{(a)}}{\longrightarrow}& \text{CNF}&\underset{\text{(b)}}{\longrightarrow}&\text{SDD}&\underset{ \text{(c)}}{\longrightarrow}&\text{dDBC}\\ \end{array} \tag{3}\]

A BNN can be converted into a CNF formula [1, 2], which, in its turn, can be converted into an SDD [2, 3]. It is also known that SDDs can be compiled into a formula in d-DNNF [deterministic and decomposable negated normal form] [2], which forms a subclass of dDBCs. Actually, the resulting dDBC in (3) is eventually converted in polynomial time into a dDBCSFi(2).

Some of the steps in (3) may not be polynomial-time transformations, which we will discuss in more technical terms later in this section. However, we can claim at this stage that: (a) Any exponential cost of a transformation is kept under control by a usually small parameter. (b) The resulting dDBCSFi(2) is meant to be used multiple times, to explain different and multiple outcomes; and then, it may be worth taking a one-time, relatively high transformation cost. A good reason for our transformation path is the availability of implementations we can take advantage of.2

Footnote 2: The path in (3) is not the only way to obtain a dDBC. For example, [1] describe a conversion of BNNs into OBDDs, which can also be used to obtain dDBCs. However, the asymptotic time complexity is basically the same.

We will describe, explain and illustrate the conversion path (3) by means of a running example with a simple BNN, which is not the BNN used for our experiments. For them, we used a BNN with one hidden layer with 13 gates.

**Example 1**.: The BNN in Figure 2 has hidden neuron gates \(h_{1},h_{2},h_{3}\), an output gate \(o\), and three input gates, \(x_{1},x_{2},x_{3}\), that receive binary values. The latter represent, together, an input entity \(\bar{x}=\langle x_{1},x_{2},x_{3}\rangle\) that is being classified by means of a label returned by \(o\). Each gate \(g\) is activated by means of a _step function_ of the form:

\[\phi_{g}(\bar{i})=\text{\emph{sp}}(\bar{w}_{g}\bullet\bar{i}+b_{g})\ :=\left\{\begin{array}{ll}1&\text{if}\ \bar{w}_{g}\bullet\bar{i}+b_{g}\geq 0,\\ -1&\text{otherwise},\end{array}\right. \tag{4}\]

which is parameterized by a vector of binary weights \(\bar{w}_{g}\) and a real-valued constant bias \(b_{g}\).3 The \(\bullet\) is the inner vector product. For technical, non-essential reasons, for the gates, we use \(1\) and \(-1\) instead of \(0\) and \(1\). However, we assume we have a single output gate, for which the activation function returns instead \(1\) or \(0\), for _true_ or _false_, respectively.

Footnote 3: It is also possible to use more complex activation functions, such as sigmoid and softmax functions, as long as the output is binarized.

For example, \(h_{1}\) is _true_, i.e. outputs \(1\), for an input \(\bar{x}=(x_{1},x_{2},x_{3})\) iff \(\bar{w}_{h_{1}}\bullet\bar{x}+b_{h_{1}}=(-1)\times x_{1}+(-1)\times x_{2}+1 \times x_{3}+0.16\geq 0\). Otherwise, \(h_{1}\) is _false_, i.e. it returns \(-1\). Similarly, output gate \(o\) is _true_, i.e. returns label \(1\) for a binary input \(\bar{h}=(h_{1},h_{3},h_{3})\) iff \(\bar{w}_{o}\bullet\bar{h}=1\times h_{1}+1\times h_{2}+(-1)\times h_{3}-0.01\geq 0\), and \(0\) otherwise. \(\Box\)

The first step, (a) in (3), consists in representing the BNN as a CNF formula, i.e. as a conjunction of disjunctions of _literals_, i.e. atomic formulas or their negations. For this, we adapt the approach in [2], in their case, to verify properties of BNNs. Contrary to them, we avoid the use of auxiliary variables since their posterior elimination conflicts with our need for determinism.

Each gate of the BNN is represented by a propositional formula, initially not necessarily in CNF, which, in its turn,

Figure 1: A dDBC.

Figure 2: A BNN.
is used as one of the inputs to gates next to the right. In this way, we eventually obtain a defining formula for the output gate. The formula is converted into CNF. The participating propositional variables are logically treated as _true_ or _false_, even if they take numerical values \(1\) or \(-1\), resp.

**Example 2**.: (example 1 cont.) Consider gate \(h_{1}\), with parameters \(\bar{w}=\langle-1,-1,1\rangle\) and \(b=0.16\), and input \(\bar{i}=\langle x_{1},x_{2},x_{3}\rangle\). An input \(x_{j}\) is said to be _conveniently instantiated_ if it has the same sign as \(w_{j}\), and then, contributing to having a larger number on the LHS of the comparison in (4). E.g., this is the case of \(x_{1}=-1\). In order to represent as a propositional formula its output variable, also denoted with \(h_{1}\), we first compute the number, \(d\), of conveniently instantiated inputs that are necessary and sufficient to make the LHS of the comparison in (4) greater than or equal to \(0\). This is the (only) case when \(h_{1}\) becomes _true_; otherwise, it is _false_. This number can be computed in general by: [1]

\[d=\left[(-b+\sum_{j=1}^{\left|\bar{i}\right|}w_{j})/2\right]+\mbox{\# of negative weights in }\bar{w}. \tag{5}\]

In the case of \(h_{1}\), with 2 negative weights: \(d=\lceil(-0.16+(-1-1+1))/2\rceil+2=2\). With this, we can impose conditions on two input variables with the right sign at a time, considering all possible convenient pairs. For \(h_{1}\) we obtain its condition to be true:

\[h_{1}\;\longleftrightarrow\;(-x_{1}\wedge-x_{2})\vee(-x_{1}\wedge x_{3}) \vee(-x_{2}\wedge x_{3}). \tag{6}\]

This is DNF formula, directly obtained from considering all possible convenient pairs (which is already better that trying all cases of three variables at a time). However, there is a more expedite, iterative method that still uses the number of convenient inputs. In order to convey the bigger picture, we postpone the detailed description of this method (that is also used in our experiments) until Appendix A. Using this algorithm, we obtain an equivalent formula defining \(h_{1}\):

\[h_{1}\;\longleftrightarrow\;(x_{3}\wedge(-x_{2}\vee-x_{1}))\vee(-x_{2} \wedge-x_{1}). \tag{7}\]

Similarly, we obtain defining formulas for gates \(h_{2}\) and \(h_{3}\), and \(o\): (for all of them, \(d=2\))

\[h_{2} \longleftrightarrow(-x_{3}\wedge(-x_{2}\vee-x_{1}))\vee(-x_{2} \wedge-x_{1}),\] \[h_{3} \longleftrightarrow(x_{3}\wedge(x_{2}\lor x_{1}))\vee(x_{2} \wedge x_{1}),\] \[o \longleftrightarrow(-h_{3}\wedge(h_{2}\lor h_{1}))\vee(h_{2} \wedge h_{1}). \tag{8}\]

Replacing the definitions of \(h_{1},h_{2},h_{3}\) into (8), we finally obtain:

\[o\longleftrightarrow(-[(x_{3}\wedge(x_{2}\lor x_{1}))\vee(x_{2 }\wedge x_{1})]\wedge\] \[\qquad([(-x_{3}\wedge(-x_{2}\vee-x_{1}))\vee(-x_{2}\wedge-x_{1})]\lor\] \[\qquad[(x_{3}\wedge(-x_{2}\vee-x_{1}))\vee(-x_{2}\wedge-x_{1})])\lor\] \[\qquad([(-x_{3}\wedge(-x_{2}\vee-x_{1}))\vee(-x_{2}\wedge-x_{1})]\wedge\] \[\qquad[(x_{3}\wedge(-x_{2}\vee-x_{1}))\vee(-x_{2}\wedge-x_{1})]). \tag{9}\]

The final part of step (a) in path (3), requires transforming this formula into CNF. In this example, it can be taken straightforwardly into CNF.4 The resulting CNF formula is, in its turn, simplified into a shorter and simpler new CNF formula by means of the _Confer_ SAT solver [1]. For this example, the simplified CNF formula is as follows:

Footnote 4: For our experiments, we programmed a simple algorithm that does this job, while making sure the generated CNF does not grow too much (c.f. Appendix A).

\[o\;\longleftrightarrow\;(-x_{1}\vee-x_{2})\wedge(-x_{1}\vee-x_{3})\wedge(- x_{2}\vee-x_{3}). \tag{10}\]

Having a CNF formula will be convenient for the next conversion steps along path (3). \(\Box\)

Following with step (b) along path (3), the resulting CNF formula is transformed into a _Sentential Decision Diagram_ (SDD) [1, 2], which, as a particular kind of _decision diagram_[1], is a directed acyclic graph. So as the popular OBDDs [1], that SDDs generalize, they can be used to represent general Boolean formulas, in particular, propositional formulas (but without necessarily being _per se_ propositional formulas).

**Example 3**.: (example 2 cont.) Figure 3(a) shows an SDD, \(\mathcal{S}\), to be used for illustration. [1, 1] for precise definitions.) An SDD has different kinds of nodes. Those represented with encircled numbers are _decision nodes_[2], e.g. 1 and 3, that consider alternatives for the inputs (in essence, disjunctions). There are also nodes called _elements_. They are labeled with constructs of the form \([\ell_{1}|\ell_{2}]\), where \(\ell_{1},\ell_{2}\), called the _prime_ and the _sub_, resp., are Boolean literals, e.g. \(x_{1}\) and \(\neg x_{2}\), including \(\top\) and \(\bot\), for \(1\) or \(0\), resp. E.g. \([\neg x_{2}|\top]\) is one of them. The _sub_ can also be a pointer, \(\bullet\), with an edge to a decision node. \([\ell_{1}|\ell_{2}]\) represents two conditions that have to be satisfied simultaneously (in essence, a conjunction). An element without \(\bullet\) is a _terminal_.

An SDD represents (or defines) a total Boolean function \(F_{\mathcal{S}}:\;\langle x_{1},x_{2},x_{3}\rangle\in\{0,1\}^{3}\mapsto\{0,1\}\). For example, \(F_{\mathcal{S}}(0,1,1)\) is evaluated by following the graph downwards. Since \(x_{1}=0\), we descent to the right; next via node 3 underneath, with \(x_{2}=1\), we reach the instantiated leaf node labeled with \([1|0]\), a "conjunction", with the second

Figure 3: An SDD (a) and a vtree (b).
component due to \(x_{3}=1\). We obtain \(F_{\mathcal{S}}(0,1,1)=0\). \(\Box\)

In SDDs, the orders of occurrence of variables in the diagram must be compliant with a so-called _vtree_ (for "variable tree").5 The connection between a vtree and an SDD refers to the compatibility between the partitions \([\mathit{prime}|sub]\) and the tree structure (c.f. Example 4 below). Depending on the chosen vtree, substructures of an SDD can be better reused when representing a Boolean function, e.g. a propositional formula, which becomes important to obtain a compact representation. An important feature of SDDs is that they can easily be combined via propositional operations, resulting in a new SDD [12].

Footnote 5: Extending OBDDs, which have special kinds of vtrees that capture the condition that variables in a path must always appear in the same order. This generalization makes SDDs much more succinct than OBDDs [13, 14].

A vtree for a set of variables \(\mathcal{V}\) is binary tree that is full, i.e. every node has \(0\) or \(2\) children, and ordered, i.e. the children of a node are totally ordered, and there is a bijection between the set of leaves and \(\mathcal{V}\)[1].

**Example 4**.: (example 3 cont.) Figure 3(b) shows a vtree, \(\mathcal{T}\), for \(\mathcal{V}=\{x_{1},x_{2},x_{3}\}\). Its leaves, \(0,2,4\), show their associated variables in \(\mathcal{V}\). The SDD \(\mathcal{S}\) in Figure 3(a) is compatible with \(\mathcal{T}\). Intuitively, the variables at \(\mathcal{S}\)'s terminals, when they go upwards through decision nodes (\(\nexists\)), also go upwards through the corresponding nodes \(n\) in \(\mathcal{T}\). [16, 17] for a precise, recursive definition.)

The SDD \(S\) can be straightforwardly represented as a propositional formula by interpreting decision points as disjunctions, and elements as conjunctions, obtaining \([x_{1}\wedge((-x_{2}\wedge-x_{3})\vee(x_{2}\wedge\bot))]\vee[-x_{1}\wedge((x_ {2}\wedge-x_{3})\vee(-x_{2}\wedge\top))]\), which is logically equivalent to the formula on the RHS of (10) that represents the BNN. Accordingly, the BNN is represented by the SDD in Figure 3(a). \(\Box\)

In our experiments and in the running example, we used the _PySDD_ system [15], which, given a CNF formula \(\psi\), produces a vtree and a compliant SDD, both optimized in size, that represents the \(\psi\)[1, 12].

This compilation takes space and time that are exponential only in the _tree-width_, \(\mathit{TW}(\psi)\), of \(\psi\), which is the tree-width of the graph \(\mathcal{G}\) associated to \(\psi\)[1, 12]. \(\mathcal{G}\) contains the variables as nodes, and undirected edges between any of them when they appear in a same clause. The tree-width measures how close the graph is to being a tree. The exponential upper-bound on the tree-width is a positive _fixed-parameter tractability_ result [13] in that \(\mathit{TW}(\psi)\) is in general much smaller \(|\psi|\).

For example, the graph \(\mathcal{G}\) for the formula \(\psi\) on the RHS of (10) has \(x_{1},x_{2},x_{3}\) as nodes, and edges between any pair of variables, which makes \(\mathcal{G}\) a complete graph. Since every complete graph has a tree-width equal to the number of nodes minus one, we have \(\mathit{TW}(\psi)=2\).

Our final transformation step consists in obtaining a dDBC from the resulting SDD, as follows: An SDD turns out to correspond to a d-DNNF Boolean circuit, for which decomposability and determinism hold, and has only variables as inputs to negation gates [12]. The class d-DNNF is contained in dDBC.

The algorithm in [16] for Shap computing requires the dDBC a dDBCSFi(2). Every dDBC can be transformed in linear time into a dDBCSFi(2) [1]. More details can be found in Appendix B.

**Example 5**.: (example 3 cont.) By interpreting decision points and elements as disjunctions and conjunctions, resp., the SDD in Figure 3(a) can be easily converted into d-DNNF circuit. Notice that only variables are affected by negations. However, due to the children of node 3, that do not have the same variables, the directly resulting dBBC is not smooth (it has fan-in \(2\) though). It can be transformed into the dDBCSFi(2) in Figure 1. \(\Box\)

## 4 Shap Computation: Experiments

The dataset "California Housing Prices" dataset was used for our experiments, in particular, to train a BNN and compute Shap scores. It can be downloaded from Kaggle [12] (it has been used before, e.g. in [13]). It consists of 20,640 observations for 10 features with information on the block groups of houses in California, from the 1990 Census. Table 1 lists and describes the features, and the way in which they are binarized. The categorical feature #1 is one-hot encoded, giving rise to 5 binary features: #1\({}_{a}\),..., #1\({}_{e}\). Accordingly, we end up with 13 binary input features, plus the binary output feature, #10. Accordingly, thirteen binary predictor features are used to predict a binary output, representing whether the median price at each block is high or low (i.e. above or below the average of the original #10).

We used the "Tensorflow" and "Larq" Python libraries to train a BNN with one hidden layer, with as many neurons as predictors, and one neuron for the output. For the hidden neurons, the activation functions are step function, as in (4), with outputs \(1\) or \(-1\), whereas the step function for the output returns \(1\) or \(0\). All weights were rounded to binary values (1 or \(-1\)) and the biases were kept as real numbers. The loss function employed was the _binary cross-entropy_, defined by \(\mathit{BCE}(\bar{y},\hat{y})=-\frac{1}{|\hat{y}|}\sum_{i=1}^{|\hat{y}|}\left[y_{ i}\text{log}(\hat{y}_{i})+(1-y_{i})\text{log}(1-\hat{y}_{i})\right]\), where \(\hat{\hat{y}}\) represents the labels predicted by the model and \(\bar{y}\) are the true labels. The BNN ended up having a binary cross-entropy of 0.9041, and an accuracy of 0.6580, based on the test dataset.

According to the transformation path (3), the constructed BNN was first represented as a CNF formula with 2,391 clauses. It has a tree-width of 12, which makes sense having a middle layer of 13 gates, each with all features as inputs. The CNF was transformed, via the SDD conversion, into a dDBCSFi(2), \(\mathcal{C}\), which ended up having 18,671 nodes (without counting the negations affecting only input gates). Both transformations were programmed in Python. For the intermediate simplification of the CNF we used the SAT solver _Riss_. The initial transformation into CNF took 1.3 hrs. The conversion of the simplified CNF into the dDBCSFi(2) took 0.8276 secs.
After the transformation, we had the possibility to compute Shap for a given input entity in three different ways:

1. Directly on the BNN as a black-box model, i.e. using only its input/output relation for multiple calls, i.e. directly using formula (2);
2. Similarly, using the circuit \(\mathcal{C}\) as a black-box model; and
3. Using the efficient algorithm in [1], treating circuit \(\mathcal{C}\) as an open-box model. For completeness, it is reproduced here as Algorithm 1.

We performed these three computations for sets of 20, 40, 60, 80, and 100 input entities, to compare average times with increasing numbers of entities. In all cases, Shap was computed on the uniform probability distribution over the joint feature domain of size \(2^{13}\) (using Algorithm 1 with the product distribution with \(\frac{1}{2}\) for value \(1\)). Everything was programmed in Python.

The experimental results we report below are the average Shap score for each feature over 100 entities; and the average time taken to compute them for 20, 40, 60, 80, 100 entities. For the cases (a) and (b) above, i.e. computations with black-box models, the classification labels were first computed for all entities in the population \(\mathcal{E}\). After that, for each individual, fixed input entity \(\mathbf{e}\), when computing its Shap scores, all the other precomputed "counterfactual" versions in \(\mathcal{E}\) were used in formula (2).6 The specialized algorithm for (c), the open-box case, does not require the precomputation of all entity labels. All experiments were run on _Google Colab_ (with an NVIDIA Tesla T4 enabled).7

Footnote 6: The Shap scores reported in [1] were also computed in this way, but considering only the entity sample instead of the whole entity population.

Footnote 7: The complete code for _Google Colab_ can be found at: [https://github.com/Jorvan758/dDBCSFi2](https://github.com/Jorvan758/dDBCSFi2).

To report on Shap score computation, we used two different averages: over the original Shap scores, and over their absolute values. C.f. Figure 4. In this way, we can see the usual label each feature is associated with, and also its average relevance in absolute terms.

As expected, since the dDBC faithfully represent the BNN, we obtained exactly the same Shap scores under the three modes of computation, i.e. (a)-(c) above. Our results tell us that the three most relevant features for the classification label are #\(1_{b}\), #\(1_{e}\) and #6.

The times taken to compute Shap in the three cases, (a)-(c), are shown in Figure 5, in logarithmic scale. For example, the time with the BNN for 100 entities was 7.7 hrs, whereas for the open-box dDBC it was 4.2 min. We observe a huge gain in performance with the use of the efficient al

\begin{table}
\begin{tabular}{|p{56.9pt}|p{56.9pt}|p{56.9pt}|p{56.9pt}|p{56.9pt}|} \hline
**Id \#** & **Feature Name** & **Description** & **Original Values** & **Binarization** \\ \hline \#1 & _ocean\_proximity_ & A label of the location of the house w.r.t seq/ocean & Labels _lh\_ocean\_ island_, _near\_bay_ and _near\_ocean_ & Five features (one representing each label), for which 1 means a match with the value of _ocean\_proximity_, and \(-1\) otherwise \\ \hline \#2 & _households_ & The total number of households (a group of people residing within a home unit) for a block & Integer numbers from \(1\) to 6,082 & 1 (above average of the feature) or \(-1\) (below average) \\ \hline \#3 & _housing\_median\_age_ & The median age of a house within a block (lower numbers means newer buildings) & Integer numbers from \(1\) to \(52\) & 1 (above average of the feature) or \(-1\) (below average) \\ \hline \#4 & _latitude_ & The angular measure of how far north a block is the (the higher value, the farther north) & Real numbers from \(32.54\) to \(41.95\) & 1 (above average of the feature) or \(-1\) (below average) \\ \hline \#5 & _longitude_ & The angular measure of how far west a block is the (higher value, the farther west) & Real numbers from \(1-124.35\) to \(-114.31\) & 1 (above average of the feature) or \(-1\) (below average) \\ \hline \#6 & _median\_income_ & The median income for households within a block (measured in tens of thousands of US dollars) & Real numbers from \(0.50\) to \(15.00\) & 1 (above average of the feature) or \(-1\) (below average) \\ \hline \#7 & _population_ & The total number of people residing within a block & Integer numbers from \(3\) to 35,682 & 1 (above average of the feature) or \(-1\) (below average) \\ \hline \#8 & _total\_brooms_ & The total number of bedrooms within a block & Integer numbers from \(1\) to 6,445 & 1 (above average of the feature) or \(-1\) (below average) \\ \hline \#9 & _total\_rooms_ & The total number of rooms within a block & Integer numbers from \(2\) to \(39\),320 & 1 (above average of the feature) or \(-1\) (below average) \\ \hline \hline
**Id \#** & **Output** & **Description** & **Original Values** & **Labels** \\ \hline \#10 & _median\_house\_value_ & The median house value for households within a block (measured in US dollars) & Integer numbers from 14,999 to 500,001 & 1 (above average of the feature) or 0 (below average) \\ \hline \end{tabular}
\end{table}
Table 1: Features of the “California Housing Prices” dataset.
gorithm on the open-box dDBC. Those times do not show the one-time computation for the transformation of the BNN into the dDBC.

The difference in time between the BNN and the black-box dDBC, i.e. cases (a) and (b), resides in the fact that the BNN allows some batch processing for the initial label predictions, which translates into just 6 matrix operations (2 weight multiplications, 2 bias additions, and 2 activations), whereas with the dDBC the classifications are made one at a time.

## 5 Conclusions

The main objective of the research we reported about has been twofold. On one side, we have showed the convenience of applying knowledge compilation techniques to obtain explanations for ML-based models. On the other side, we have also established the huge difference in performance when computing explanation scores for a classifier when treating it as a black-box vs. treating it as an open-box.

In relation to the knowledge compilation phase, we emphasize once more, that the effort invested in transforming the BNN into a dDBC is something we incur once, being the compilation of the BNN into a CNF the most expensive step. In comparison, the subsequent transformations into SDD, and the required dDBC take a very small time.

Despite the intrinsic complexity involved, there is much room for improving the algorithmic and implementation aspects of the BNN compilation. The same applies to the implementation of the efficient Shap computation algorithm.

The resulting circuit can be used to obtain Shap scores multiple times, and for multiple inputs. We have showed that the performance gain in Shap computation with the circuit exceeds by far both the compilation time and the Shap computation time for the BNN used a black-box classifier. Furthermore, the resulting circuit can be used for other purposes, such as _verification_ of general properties of the classifier [10, 11].

When we can easily obtain explanation scores, such as Shap, we have an additional tool to analyze the goodness of our classifier. Obtaining unexpected or surprising explanations may invite us to reconsider the whole machine learning process, starting from the original dataset on, all the way to the deployment of the classifier.

We computed Shap scores using the uniform distribution on the entity population. There are a few issues to discuss in this regard. First, it is computationally costly to use it with a large number of features. One could use instead the _empirical distribution_ associated to the dataset, as in [1] for black-box Shap computation. This would require appropriately modifying the applied algorithm, which is left for future work. Secondly, and more generally, the uniform distribution does not capture possible dependencies among features. The algorithm is still efficient with the _product distribution_, which also suffers from imposing feature independence (c.f. [1] for a discussion of its empirical version and related issues). It would be interesting to explore to what extent other distributions could be used in

Figure 4: Average Shap score for each feature with 100 entities (a) (where red means an average closer to \(-1\) and blue closer 1), and for their absolute values (b).
combination with our efficient algorithm.

Independently from the algorithmic and implementation aspects of Shap computation, an important research problem has to do with bringing _domain knowledge_ or _domain semantics_ into the definitions and computations of attribution scores, to obtain more meaningful and interpretable results. This additional knowledge could come, for example, in declarative terms, expressed as _logical constraints_. They could be used to appropriately modify the algorithm or the underlying distribution (Bertossi, 2021). It is likely that domain knowledge can be more easily be brought into a score computation when it is done on a logic-based classifier, such as a dDBC.

In this work we have considered only binary NNs. It would be interesting to investigate to what extent our methods can be applied to non-binary NNs. There is work on binarized NNs (Qin et al., 2020; Yuan and Agaian, 2021; Simons and Lee, 2019), but it is not clear whether that would be a feasible way to go.

## Acknowledgments

Our special thanks go to: (a) Arthur Choi, for the use of the PySDD repository, and his kind and permanent advice on how to use it. And also answering more fundamental questions; (b) Andy Shih, for sharing some preliminary code for the conversion of BNNs into CNF, and explaining many issues; (c) Norbert Manthey, for his Riss tool collection repository, answering questions about its use and the simplification of CNF formulas; (d) Maximilian Schleich, for sharing some preliminary code for the black-box computation of Shap; and (e) Adnan Darwiche, for sharing useful insights.

Part of this work was funded by ANID - Millennium Science Initiative Program - Code ICN17002; and "Centro Nacional de Inteligencia Artificial" CENIA, FB210017 (Finamciamento Basal para Centros Cientificos y Tecnologicos de Excelencia de ANID), Chile. Both CENIA and SKEMA Canada funded Jorge Leon's visit to Montreal. L. Bertossi is a Professor Emeritus at Carleton University, Ottawa, Canada; and a Senior Fellow of the Universidad Adolfo Ibanez (UAI), Chile.

## Appendix A BNN to CNF Formula

Our conversion of the BNN into a CNF formula is inspired by a technique introduced in (Narodytska et al., 2018). However, it cannot be applied straightforwardly since it introduces auxiliary variables, whose final elimination becomes a challenge for our purposes. The application of a _variable forgetting_ technique (Oztok and Darwiche, 2017) turns out to damage the required determinism of the dDBC. Accordingly, it is necessary to adapt the conversion technique, avoiding the use of the auxiliary variables. We sketch the approach in the following. C.f. Example 2 for intuitions and motivation.

Consider a BNN receiving \(\ell_{0}\) input features, say \(\bar{x}=\langle x_{1},\dots,x_{\ell_{0}}\rangle\). The BNN has \(m\) hidden layers, each layer \(z\) (from \(1\) to \(m\)) with \(\ell_{z}\) neurons. A neuron in layer \(z\) receives the input vector \(\vec{i}=\langle i_{1},\dots,i_{\ell_{z-1}}\rangle\). The output layer has a single neuron. As in Section 3, all weights and features are \(-1\) or \(1\), with the activation functions returning \(-1\) or \(1\), except for the output layer that returns \(0\) or \(1\).

To convert the BNN into a CNF formula, we do it layer-wise from input to output. All the neurons in a layer can be converted in parallel. For every neuron gate \(g\), we encode the case when it returns \(1\), representing its activation function \(\mathit{sp}(\bar{w}_{g}\bullet\vec{i}+b_{g})\) as a CNF formula. For this, we compute, as in (5), the number \(d_{g}\) of inputs to be instantiated for the output to be \(1\).

For each neuron \(g\) on the first layer, and to conveniently manage the whole process, we construct a matrix-like structure \(\mathit{M}_{g}\) of dimension \(|\vec{i}|\times d_{g}\), whose components \(c_{k,t}\) are propositional formulas.

\[\mathit{M}_{g}=\begin{bmatrix}w_{1}\cdot i_{1}&\mathit{false}&\mathit{false}& \dots&\mathit{false}\\ w_{2}\cdot i_{2}&w_{2}\cdot i_{2}&\land_{2}&\land_{2}\\ \lor c_{1,1}&\land_{c1,1}&&\\ \par w_{3}\cdot i_{3}&(w_{3}\cdot i_{3}&\land_{3}&\land_{2}&\land_{2}\\ \lor c_{2,1}&\lor_{c2,2}&\land c_{2,2}&&\\ \dots&\dots&\dots&\dots&\dots\\ \par w_{|\vec{i}|\cdot i_{|\vec{i}|}}\vee(\vec{w}_{|\vec{i}|\cdot i_{|\vec{ i}|}}&(w_{|\vec{i}|\cdot i_{|\vec{i}|}}&(w_{|\vec{i}|\cdot i_{|\vec{i}|}} \land_{|\vec{i}|-1,1})&\land_{c1|\mid-1,2})&\dots&\ell_{|\vec{i}|-1,d_{g}-1} \\ c_{|\vec{i}|-1,1}&\lor_{c|\vec{i}|-1,2}&\lor_{c|\vec{i}|-1,3}&&\lor_{c|\vec{i}| -1,d_{g}}\end{bmatrix}\]

Figure 5: Seconds taken to compute Shap on 20, 40, 60, 80 and 100 entities; using the BNN as a black-box (blue bar), the dDBC as a black-box (red bar), and the dDBC as an open-box (orange bar). Note that the vertical axis employs a logarithmic scale.
In this array, a term of the form \(w_{k}\cdot i_{k}\)_does not represent a number_, but a propositional formula, namely \(i_{k}\) if \(w_{k}=1\), and \(\neg i_{k}\) if \(w_{k}=-1\). Every \(M_{\!g}\) is filled in a row-wise manner starting from the top, and then column-wise from left to right. The formula that will be passed over to the next layer to the right is the last entry, \(c_{\bar{|i|}\times d_{g}}\) (highlighted).

Only in the arrays for the first layer we find new propositional variables, for the inputs. For the next layers, the whole output formulas from the previous layer are passed over as inputs, and they become the \(i_{k}\)'s just mentioned. In this way, no auxiliary variables other that those for the initial inputs are created. Each row represents the number of the first \(k\in\{1,\ldots,\bar{|i|}\}\) inputs considered for the encoding, and each column, the threshold \(t\in\{1,\ldots,d_{g}\}\) to surpass (meaning that at least \(t\) inputs should be instantiated conveniently). For every component where \(k<t\), the threshold cannot be reached, which makes every component in the upper, right triangle to be _false_.

For explanation, the first row of \(M_{\!g}\) has the first entry \(w_{1}\cdot i_{1}\), and _false_ for the rest. Each entry \(c_{k,1}\) of the first column becomes \(w_{k}\cdot i_{k}\lor c_{k-1,1}\). For any other component \(c_{k,t}\), \(t>1\), we use \((w_{k}\cdot i_{k}\wedge c_{k-1,t-1})\lor c_{k-1,t}\). So, the lower right component \(c_{\bar{|i|},d_{g}}\) of \(M_{\!g}\) ends up being the encoding of neuron \(g\), and it is the only formula that will be used in the encondings for the next layer. All the \(M_{\!g}\)'s for a layer can be generated in parallel, as their encodings do not influence each other.

For the second layer, we take as inputs the encodings \(c_{\ell_{0},d_{g}}\) from the previous one, and we keep repeating this conversion. In other words, we compute \(d_{g}\) and \(M_{\!g}\) for every neuron \(g\) in the new layer, taking the previous encodings as inputs. The resulting \(c_{\ell_{1},d_{g}}\)s are given as inputs for the next layer, and we iterate all the way until the last layer. For illustration, c.f. Figure 6.

From the array \(M_{\!g}\) for the single output neuron, \(o\), at the last layer, we extract the component \(c_{\ell_{m},d_{a}}\), which becomes the propositional encoding of the whole BNN. This is a propositional formula that is next converted into a CNF formula, which in its turn is further simplified (c.f. Section 3).8

Footnote 8: Actually, every entry in an array \(M_{\!g}\) is immediately transformed into CNF and simplified, avoiding the iterative creation of extremely long, complex and non-CNF formulas.

```
Input : Original \(dDBC\) (starting from root node). Output : A \(dDBCSFi(\ref{eq:dDBC})\) equivalent to the given \(dDBC\).
1functionFIX_NODE(\(dDBC\_node\)) if\(dDBC\_node\) is a disjunction then
2\(c_{new}\) = false
3for each subcircuit \(sc\) in \(dDBC\_node\)
4\(sc_{\bar{|i|}}\) = FIX_NODE(\(sc\)) if\(sc_{\bar{|i|}}\) is a \(true\) value or is equal to \(\neg c_{new}\)then
5return\(true\)
6elseif\(sc_{\bar{|i|}}\) is not a false valuethen
7for each variable \(v\) in \(c_{new}\) and not in \(sc_{\bar{|i|}}\)
8\(sc_{\bar{|i|}}\) = \(sc_{\bar{|i|}}\wedge(v\lor\neg v)\)
9for each variable \(v\) in \(sc_{\bar{|i|}}\) and not in \(c_{new}\)
10\(c_{new}\) = \(c_{new}\wedge(v\lor\neg v)\)
11\(c_{new}\) = \(c_{new}\lor\mathit{s}\)\(\mathit{s}\)\(\mathit{s}\)\(\mathit{s}\)return\(c_{new}\)
12
13elseif\(dDBC\_node\) is a conjunctionthen
14\(c_{new}\) = \(true\)
15for each subcircuit \(sc\) in \(dDBC\_node\)
16\(sc_{\bar{|i|}}\) = FIX_NODE(\(sc\)) if\(sc_{\bar{|i|}}\) is a false value or is equal to \(\neg c_{new}\)then
17returnfalse
18elseif\(sc_{\bar{|i|}}\) is not a \(true\) valuethen
19\(c_{new}\) = \(c_{new}\wedge\mathit{s}\)\(\mathit{s}\)\(\mathit{s}\)\(\mathit{s}\)\(\mathit{s}\)return\(c_{new}\)
20elseif\(dDBC\_node\) is a negationthen
21return\(\neg\)FIX_NODE(\(\neg dDBC\_node\))
22
23else
24return\(dDBC\_node\)
25\(dDBCSFi(\ref{eq:dDBC})\) = FIX_NODE(\(root\_node\))
```

**Algorithm 2** From dDBC to dDBCSFi(2)