On the Tractability of SHAP Explanations

Štrumbelj and Kononenko (2014) show that Shapley values can be used to explain arbitrary machine learning models. Datta, Sen, and Zick (2016) use Shapley-value-based explanations as part of a broader framework for algorithmic transparency. Lundberg and Lee (2017) use Shapley values in a framework that unifies various explanation techniques, and they coined the term Shap explanation. They show that the Shap explanation is effective in explaining predictions in the medical domain; see Lundberg et al. (2020). More recently there has been a lot of work on the tradeoffs of variants of the original Shap explanations, e.g., Sundararajan and Najmi (2020), Kumar et al. (2020), Janzing, Minorics, and Bloebaum (2020), Merrick and Taly (2020), and Aas, Jullum, and Løland (2019).

Despite all of this interest, there is considerable confusion about the tractability of computing Shap explanations. The Shap explanations determine the influence of a given feature by systematically computing the expected value of the model given a subsets of the features. As a consequence, the complexity of computing Shap explanations depends on the predictive model as well as assumptions on the underlying data distribution. Lundberg et al. (2020) describe a polynomial-time algorithm for computing the Shap explanation over decision trees, but online discussions have pointed out that this algorithm is not correct as stated. We present a concrete example of this shortcoming in the supplementary material, in Appendix A. In contrast, for fully-factorized distributions, Bertossi et al. (2020) prove that there are models for which computing the Shap explanation is #P-hard. A contemporaneous paper by Arenas et al. (2020) shows that computing the Shap explanation for tractable logical circuits over uniform and fully factorized binary data distributions is tractable. In general, the complexity of the Shap explanation is open.

In this paper we consider the original formulation of the Shap explanation by Lundberg and Lee (2017) and analyze its computational complexity under the following data distributions and model classes:

1. 1.

   First, we consider fully-factorized distributions, which are the simplest possible data distribution. Fully-factorized distributions capture the assumption that the model’s features are independent, which is a commonly used assumption to simplify the computation of the Shap explanations, see for example Lundberg and Lee (2017).

   For fully-factorized distributions and any prediction model, we show that the complexity of computing the Shap explanation is the same as the complexity of computing the expected value of the model.

   It follows that there are classes of models for which the computation is tractable (e.g., linear regression, decision trees, tractable circuits) while for other models, including commonly used ones such as logistic regression and neural nets with sigmoid activation functions, it is #P-hard.

2. 2.

   Going beyond fully-factorized distributions, we show that computing Shap explanation becomes intractable already for the simplest probabilistic model that does not assume feature independence: naive Bayes. As a consequence, the complexity of computing Shap explanations on such data distributions is also intractable for many classes of models, including linear and logistic regression.

3. 3.

   Finally we consider the empirical distribution, and prove that computing Shap explanations is #P-hard for this class of distributions. This result implies that the algorithm by Lundberg et al. (2020) cannot be fixed to compute the exact Shap explanations over decision trees in polynomial time.

Suppose our data is described by $n$ indexed features $\mathbf{X}=\{X_{1},\ldots,X_{n}\}$. Each feature variable $X$ takes a value from a finite domain $\operatorname{dom}(X)$. A data instance $\mathbf{x}=(x_{1},\dots,x_{n})$ consists of values $x\in\operatorname{dom}(X)$ for every feature $X$. This instance space is denoted $\mathbf{x}\in\mathcal{X}=\operatorname{dom}(X_{1})\times\dots\times\operatorname{dom}(X_{n})$. We are also given a learned function $F:\mathcal{X}\to\mathbb{R}$ that computes a prediction $F(\mathbf{x})$ on each instance $\mathbf{x}$. Throughout this paper we assume that the prediction $F(\mathbf{x})$ can be computed in polynomial time in $n$.

For a particular instance of prediction $F(\mathbf{x})$, the goal of local explanations is to clarify why the function $F$ gave its prediction on instance $\mathbf{x}$, usually by attributing credit to the features. We will focus on local explanation that are inspired by game-theoretic Shapley values (Datta, Sen, and Zick 2016; Lundberg and Lee 2017). Specifically, we will work with the Shap explanations as defined by Lundberg and Lee (2017).

We start our study of the complexity of Shap by considering the simplest probability distribution: a fully-factorized distribution, where all features are independent.

There are both practical and computational reasons why it makes sense to assume a fully-factorized data distribution when computing Shap explanations. First, functions $F$ are often the product of a supervised learning algorithm that does not have access to a generative model of the data – it is purely discriminative. Hence, it is convenient to make the practical assumption that the data distribution is fully factorized, and therefore easy to estimate. Second, fully-factorized distributions are highly tractable; for example they make it easy to compute expectations of linear regression functions (Khosravi et al. 2019b) and other hard inference tasks (Vergari et al. 2020).

Lundberg and Lee (2017) indeed observe that computing the Shap-explanation on an arbitrary data distribution is challenging and consider using fully-factorized distributions (Sec. 4, Eq. 11). Other prior work on computing explanations also use fully-factorized distributions of features, e.g., Datta, Sen, and Zick (2016); Štrumbelj and Kononenko (2014). As we will show, the Shap explanation can be computed efficiently for several popular classifiers when the distribution is fully factorized. Yet, such simple data distributions are not a guarantee for tractability: computing Shap scores will be intractable for some other common classifiers.

Features in real-world data distributions are not independent. In order to capture more realistic assumptions about the data when computing Shap scores, one needs a more intricate probabilistic model. In this section we prove that the complexity of computing the Shap-explanation quickly becomes intractable, even over the simplest probabilistic models, namely naive Bayes models. To make computing the Shap-explanation as easy as possible, we will assume that the function $F$ simply outputs the value of one feature. We show that even in this case, even for function classes that are tractable under fully-factorized distributions, computing Shap explanations becomes computationally hard.

Let $\text{\tt NBN}_{n}$ denote the family of naive Bayes networks over $n+1$ variables $\mathbf{X}=\{X_{0},X_{1},\ldots,X_{n}\}$, with binary domains, where $X_{0}$ is a parent of all features:

As usual, the class $\text{\tt NBN}\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\bigcup_{n\geq 0}\text{\tt NBN}_{n}$. We write $X_{0}$ for the function $F$ that returns the value of feature $X_{0}$; that is, $F(\mathbf{x})=\mathbf{x}_{0}$. We prove the following.

The proof in Appendix D is by reduction from the number partitioning problem, similar to the proof of Corollary 6. We note that the subset sum problem was also used to prove related hardness results, e.g., for proving hardness of the Shapely value in network games (Elkind et al. 2008).

This result is in sharp contrast with the complexity of the Shap score over fully-factorized distributions in Section 3. There, the complexity was dictated by the choice of function class F. Here, the function is as simple as possible, yet computing Shap is hard. This ruins any hope of achieving tractability by restricting the function, and this motivates us to restrict the probability distribution in the next section. This result is also surprising because it is efficient to compute marginal probabilities (such as the expectation of $X_{0}$) and conditional probabilities in naive Bayes distributions.

Theorem 8 immediately extends to a large class of probability distributions and functions. We say that $F$ depends only on $X_{i}$ if there exist two constants $c_{0}\neq c_{1}$ such that $F(\mathbf{x})=c_{0}$ when $\mathbf{x}_{i}=0$ and $F(\mathbf{x})=c_{1}$ when $\mathbf{x}_{i}=1$. In other words, $F$ ignores all variables other than $X_{i}$, and does depend on $X_{i}$. We then have the following.

This corollary follows from two simple observations. First, each of the classes of probability distributions listed in the corollary can represent a naive Bayes network over binary variables $\mathbf{X}$. For example, a Markov network will consists of $n$ factors $f_{1}(X_{0},X_{1}),f_{2}(X_{0},X_{2}),\ldots,f_{n}(X_{0},X_{n})$; similar simple arguments prove that all the other classes can represent naive Bayes, including tractable probabilistic circuits such as sum-product networks (Vergari et al. 2020).

Second, for each function that depends only on $X_{0}$, there exist two distinct constants $c_{0}\neq c_{1}\in\mathbb{R}$ such that $F(\mathbf{x})=c_{0}$ when $\mathbf{x}_{0}=0$ and $F(\mathbf{x})=c_{1}$ when $\mathbf{x}_{0}=1$. For example, if we consider the class of logistic regression functions $F(\mathbf{x})=\sigma(\sum_{i}w_{i}\mathbf{x}_{i})$, then we choose the weights $w_{0}=1$, $w_{1}=\ldots=w_{n}=0$ and we obtain $F(\mathbf{x})=1/2$ when $\mathbf{x}_{0}=0$ and $F(\mathbf{x})=1/(1+e^{-1})$ when $\mathbf{x}_{0}=1$. Then, over the binary domain $\{0,1\}$ the function is equivalent to $F(\mathbf{x})=(c_{1}-c_{0})\mathbf{x}_{0}+c_{0}$, and, therefore, by the linearity of the Shap explanation (Equation 4) we have $\textsc{Shap}_{F}(X_{0})=(c_{1}-c_{0})\cdot\textsc{Shap}_{X_{0}}(X_{0})$ (because the Shap explanation of a constant function $c_{0}$ is 0) for which, by Theorem 8, the decision problem is NP-hard.

We end this section by proving that Theorem 8 continues to hold even if the prediction function $F$ is the value of some leaf node of a (bounded treewidth) Bayesian Network. In other words, the hardness of the Shap explanation is not tied to the function returning the root of the network, and applies to more general functions.

In supervised learning one does not require a generative model of the data, instead, the model is trained on some concrete data set: the training data. When some probabilistic model is needed, then the training data itself is conveniently used as a probability model, called the empirical distribution. This distribution captures dependencies between features, while its set of possible worlds is limited to those in the data set. For example, the intent of the KernelSHAP algorithm by Lundberg and Lee (2017) is to compute the Shap explanation on the empirical distribution. In another example, Aas, Jullum, and Løland (2019) extend KernelSHAP to work with dependent features, by estimating the conditional probabilities from the empirical distribution.

Compared to the data distributions considered in the previous sections, the empirical distribution has one key advantage: it has many fewer possible worlds with positive probability – this suggests increased tractability. Unfortunately, in this section, we prove that computing the Shap explanation over the empirical distribution is #P-hard in general.

To simplify the presentation, this section assumes that all features are binary: $\operatorname{dom}(X_{j})=\{0,1\}$. The probability distribution is given by a 0/1-matrix $\bm{d}=(x_{ij})_{i\in[m],j\in[n]}$, where each row $(x_{i1},\ldots,x_{in})$ is an outcome with probability $1/m$. One can think of $\bm{d}$ as a dataset with $n$ features and $m$ data instances, where each row $(x_{i1},\ldots,x_{in})$ is one data instance. Repeated rows are possible: if a row occurs $k$ times, then its probability is $k/m$. We denote by X the class of empirical distributions. The predictive function can be any function $F:\{0,1\}^{n}\rightarrow\mathbb{R}$. As our data distribution is no longer strictly positive, we adopt the standard convention that $\mathbf{E}[F|\mathbf{X}_{S}=1]=0$ when ${\textnormal{Pr}}(\mathbf{X}_{S}=1)=0$.

Recall from Section 2.2 that, by convention, we compute the Shap-explanation w.r.t. instance $\mathbf{e}=(1,1,\ldots,1)$, which is without loss of generality. Somewhat surprisingly, the complexity of computing the Shap-explanation of a function $F$ over the empirical distribution given by a matrix $\bm{d}$ is related to the problem of computing the expectation of a certain CNF formula associated to $\bm{d}$.

Thus, a PP2CNF formula is over $m+n$ variables $U_{1},\ldots,U_{m},V_{1},\ldots,V_{n}$, and has only positive clauses. The matrix $\bm{d}$ dictates which clauses are present. A quasy-symmetric probability distribution is a fully factorized distribution over the $m+n$ variables for which there exists two numbers $p,q\in[0,1]$ such that for every $i=1,m$, ${\textnormal{Pr}}(U_{i}=1)=p$ or ${\textnormal{Pr}}(U_{i}=1)=1$, and for every $j=1,n$, ${\textnormal{Pr}}(V_{j}=1)=q$ or ${\textnormal{Pr}}(V_{j}=1)$. In other words, all variables $U_{1},\ldots,U_{m}$ have the same probability $p$, or have probability $1$, and similarly for the variables $V_{1},\ldots,V_{n}$. We denote by $\text{\tt EQS}(\text{\tt PP2CNF})$ the expectation computation problem for PP2CNF over quasi-symmetric probability distributions. $\text{\tt EQS}(\text{\tt PP2CNF})$ is #P-hard, because computing $\mathbf{E}[\Phi_{\bm{d}}]$ under the uniform distribution (i.e. ${\textnormal{Pr}}(U_{1}=1)=\cdots={\textnormal{Pr}}(V_{n}=1)=1/2$) is #P-hard (Provan and Ball 1983). We prove:

The theorem is surprising, because the set of possible outcomes of an empirical distribution is small. This is unlike all the distributions discussed earlier, for example those mentioned in Corollary 9, which have $2^{n}$ possible outcomes, where $n$ is the number of features. In particular, given an empirical distribution $\bm{d}$, one can compute the expectation $\mathbf{E}[F]$ in polynomial time for any function $F$, by doing just one iteration over the data. Yet, computing the Shap explanation of $F$ is #P-hard.

Theorem 11 implies hardness of Shap explanations on the empirical distribution for a large class of functions.

For instance, any class of Boolean function that contains the $n$ single-variable functions $F\stackrel{{\scriptstyle\mathrm{def}}}{{=}}X_{i}$, for $i=1,n$, fall under this corollary. Section 4 showed an example of how the class of logistic regression functions fall under this corollary as well.

The proof of Theorem 11 follows from the following technical lemma, which is of independent interest:

The proof of the Lemma is given in Appendix F and G. The first item says that we can compute the Shap-explanation in polynomial time using an oracle for computing $\mathbf{E}[\Phi_{\bm{d}}]$ over quasi-symmetric distributions. The oracle is called only on the PP2CNF $\Phi_{\bm{d}}$ associated to the data $\bm{d}$, but may perform repeated calls, with different probabilities of the Boolean variables. This is somewhat surprising because the Shap explanation is over an empirical distribution, while $\mathbf{E}[\Phi_{\bm{d}}]$ is taken over a fully-factorized distribution; there is no connection between these two distributions. This item immediately implies $\text{\tt F-SHAP}(\text{\tt F},\text{\tt X})\leq^{P}\text{\tt EQS}(\text{\tt PP2CNF})$, where X is the class of empirical distributions $\bm{d}$, since the formula $\Phi_{\bm{d}}$ is in the class PP2CNF.

The second item says that a weak form of converse also holds. It states that we can compute in polynomial time the expectation $\mathbf{E}[\Phi]$ over a quasi-symmetric probability distributions by using an oracle for computing Shap explanations, over several matrices $\bm{d}$, but not necessarily restricted to the matrix associated to $\Phi$. Together, the two items of the lemma prove Theorem 11.

We end this section with a comment on the TreeSHAP algorithm in Lundberg et al. (2020), which is computed over a distribution defined by a tree-based model. Our result implies that the problem that TreeSHAP tries to solve is #P-hard. This follows immediately by observing that every empirical distribution $\bm{d}$ can be represented by a binary tree of size polynomial in the size of $\bm{d}$. The tree examines the attributes in the order $X_{1},X_{2},\ldots,X_{n}$, and each decision node for $X_{i}$ has two branches: $X_{i}=0$ and $X_{i}=1$. A branch that does not exists in the matrix $\bm{d}$ will end in a leaf with label $0$. A complete branch that corresponds to a row $x_{i1},x_{i2},\ldots,x_{in}$ in $\bm{d}$ ends in a leaf with label $1/m$ (or $k/m$ if that row occurs $k$ times in $\bm{d}$). The size of this tree is no larger than twice the size of the matrix (because of the extra dead end branches). This concludes our study of Shap explanations on the empirical distribution.

We establish the complexity of computing the Shap explanation in three important settings. First, we consider fully-factorized data distributions and show that for any prediction model, the complexity of computing the Shap explanation is the same as the complexity of computing the expected value of the model. It follows that there are commonly used models, such as logistic regression, for which computing Shap explanations is intractable. Going beyond fully-factorized distributions, we show that computing Shap explanations is also intractable for simple functions and simple distributions – naive Bayes and empirical distributions.

The recent literature on Shap explanations predominantly studies tradeoffs of variants of the original Shap formulation, and relies on approximation algorithms to compute the explanations. These approximation algorithms, however, tend to make simplifying assumptions which can lead to counter-intuitive explanations, see e.g., Slack et al. (2020). We believe that more focus should be given to the computational complexity of Shap explanations. In particular, which classes of machine learning models can be explained efficiently using the Shap scores? Our results show that, under the assumption of fully-factorized data distributions, there are classes of models for which the Shap explanations can be computed in polynomial time. In future work, we plan to explore if there are classes of models for which the complexity of the Shap explanations is tractable under more complex data distributions, such as the ones defined by tractable probabilistic circuits (Vergari et al. 2020) or tractable symmetric probability spaces (Van den Broeck, Meert, and Darwiche 2014; Beame et al. 2015).