PaperlayerView exact revision on arXiv

Source-linked AI summary

On the Tractability of SHAP Explanations

Guy Van den Broeck, Anton Lykov, Maximilian Schleich, Dan Suciu

arXiv:2009.08634v2cs.AIcs.CCcs.LG

TL;DR

The paper asks whether SHAP explanations for common machine-learning models can be computed efficiently. It analyzes fully-factorized, naive Bayes, and empirical distributions, showing equivalent expectation complexity in the first setting and intractability across the studied cases. These results establish computational boundaries for exact SHAP explanations.

  • Problem

    The computational tractability of SHAP explanations for common machine-learning models and data distributions is not known despite substantial interest.

  • Method

    The paper analyzes the complexity of computing original SHAP explanations under fully-factorized, naive Bayes, and empirical data distributions.

  • Results

    SHAP complexity equals expected-value complexity for fully-factorized distributions, while naive Bayes and empirical distributions yield intractable SHAP computation, including #P-hard cases.

  • Takeaways & Limitations

    Exact SHAP computation is tractable for some model classes but intractable for commonly used models and simple data distributions.

  • Takeaways & Limitations

    The empirical-distribution analysis assumes binary features and defines zero-probability conditional expectations as zero.

Abstract

from arXiv · show

SHAP explanations are a popular feature-attribution mechanism for explainable AI. They use game-theoretic notions to measure the influence of individual features on the prediction of a machine learning model. Despite a lot of recent interest from both academia and industry, it is not known whether SHAP explanations of common machine learning models can be computed efficiently. In this paper, we establish the complexity of computing the SHAP explanation in three important settings. First, we consider fully-factorized data distributions, and show that the complexity of computing the SHAP explanation is the same as the complexity of computing the expected value of the model. This fully-factorized setting is often used to simplify the SHAP computation, yet our results show that the computation can be intractable for commonly used models such as logistic regression. Going beyond fully-factorized distributions, we show that computing SHAP explanations is already intractable for a very simple setting: computing SHAP explanations of trivial classifiers over naive Bayes distributions. Finally, we show that even computing SHAP over the empirical distribution is #P-hard.

1 Introduction

The paper addresses uncertainty about the computational tractability of SHAP explanations by analyzing common models and data distributions. It shows that tractability depends on both the predictive model and the assumed data distribution.

  • SHAP explanations attribute influence to individual features using Shapley values from cooperative game theory.
  • Their computational complexity depends on both the predictive model and assumptions about the underlying data distribution.
  • The paper analyzes SHAP computation under fully-factorized distributions, naive Bayes distributions, and empirical distributions.
  • For fully-factorized distributions, SHAP computation has the same complexity as computing the model’s expected value.
  • Under fully-factorized distributions, SHAP computation is #P-hard for commonly used models including logistic regression and sigmoid neural networks.

2 Background and Problem Statement

The paper defines SHAP as a local, Shapley-value-inspired explanation that uses a data distribution to evaluate partial feature assignments. It formalizes functional and decision versions of the computational problem.

  • A local explanation attributes credit to features to clarify why a predictive function produced a particular instance’s prediction.
  • SHAP uses a probability distribution over features to compute conditional expectations for partial instances.
  • For a coalition of features, the SHAP value function evaluates its value for making the prediction under the data distribution.
  • The SHAP score averages each feature’s contribution over all possible contexts, measuring its influence on the prediction.
  • The functional SHAP problem computes all feature scores, whereas the decision SHAP problem tests whether one score exceeds a threshold.
  • The analysis uses polynomial-time reductions to compare the complexity of SHAP problems with other computational problems.

3 SHAP over Fully-Factorized Distributions

For fully-factorized data, SHAP complexity is equivalent to expectation complexity, yielding tractable classes and #P-hard classes. Logistic regression remains #P-hard even under a uniform distribution.

  • Fully-factorized distributions assume feature independence and are commonly used because they simplify SHAP computation and are easy to estimate.
  • 3.1 Equivalence to Computing Expectations: For every function class, computing SHAP under fully-factorized distributions is polynomial-time equivalent to computing the model’s expected value.
  • 3.3 Tractable Function Classes: Linear regression, trees, tree ensembles, factorization machines, regression circuits, d-DNNF functions, and bounded-treewidth CNFs have polynomial-time SHAP computation under fully-factorized distributions.
  • 3.4 Intractable Function Classes: Computing the expectation of logistic regression is #P-hard even under a uniform data distribution.
  • 3.4 Intractable Function Classes: #P-hardness applies to logistic regression, sigmoid neural networks, naive Bayes classifiers, logistic circuits, and Boolean functions in CNF or DNF.

4 Beyond Fully-Factorized Distributions

Beyond fully-factorized data, SHAP computation is already hard for naive Bayes distributions, even when the prediction function is trivial. This hardness extends to broader distribution and model classes.

  • Naive Bayes distributions: The SHAP decision problem is NP-hard for the trivial classifier F(x) = x0 over naive Bayes networks.The proof reduces from number partitioning.
  • Implication: Unlike the fully-factorized setting, restricting the prediction function alone cannot restore tractability for naive Bayes distributions.Here the function is as simple as possible, yet SHAP computation is hard.
  • Extensions: For functions depending only on one feature, SHAP remains NP-hard over naive Bayes and several broader distribution classes.The listed classes include bounded-treewidth Bayesian networks, Bayesian networks, Markov networks, factor graphs, and decomposable probabilistic circuits.
  • Extensions: The hardness is not tied to returning the network root: it also applies when F returns a single leaf variable.For Bayesian networks with latent variables, the corresponding SHAP decision problem is NP-hard even when F returns one leaf variable.

5 SHAP on Empirical Distributions

SHAP computation over empirical distributions is #P-hard, despite their small support and the polynomial-time computability of ordinary model expectations over the dataset.

  • Empirical distributions: An empirical distribution uses a binary data matrix whose rows are equally weighted, with repeated rows receiving proportional probability.A row occurring k times has probability k/m.
  • Hardness characterization: F-SHAP(F, X) is polynomial-time equivalent to expectation over positive, partitioned 2CNF formulas under quasi-symmetric distributions.This equivalence holds when each feature has a function in F depending only on that feature.
  • Complexity result: #P-hardness follows for SHAP over empirical distributions for broad function classes, including the classes listed in earlier corollaries.The condition is that, for each feature Xi, the function class contains some function depending only on Xi.
  • Implication: Although empirical distributions have few positive-probability worlds, computing E[F] requires one dataset pass while computing SHAP remains #P-hard.This contrasts the tractability of ordinary expectation with the hardness of SHAP on the same empirical distribution.
  • Tree-based models: The empirical-distribution hardness also implies hardness for the tree-based conditional-expectation problem targeted by TreeSHAP.Every empirical distribution can be represented by a binary tree of polynomial size.

6 Perspectives and Conclusions

The paper addresses uncertainty about SHAP tractability by analyzing three data-distribution settings and showing hardness in several commonly used cases. It argues that computational complexity deserves more attention alongside approximation-based SHAP variants.

  • Conclusions: The paper analyzes SHAP complexity for fully-factorized, naive Bayes, and empirical data distributions.These are presented as three important settings for establishing the complexity of computing SHAP explanations.
  • Conclusions: For fully-factorized distributions, SHAP complexity matches expected-value complexity, yet logistic regression can make SHAP computation intractable.The conclusion also identifies naive Bayes and empirical distributions as settings where SHAP is intractable for simple functions or distributions.
  • Perspectives: Approximation algorithms for SHAP often rely on simplifying assumptions that can produce counter-intuitive explanations.The paper therefore calls for more focus on the computational complexity of SHAP explanations.

A Discussion on the TreeSHAP algorithm

The discussion challenges TreeSHAP’s claimed computation of exact SHAP expectations by showing that its conditional-expectation procedure omits normalization. A two-feature example gives the correct weighted conditional value.

  • Algorithm: TreeSHAP’s Algorithm 1 follows observed branches for selected features and averages both branches for unselected split features.At leaves, it returns the model’s prediction.
  • Shortcoming: The algorithm does not compute E[F | xS] accurately because it fails to normalize by the probability of the conditioning event.The paper introduces a simple example to demonstrate the discrepancy.
  • Example: The example’s dataset contains two occurrences of (0,0), so empirical frequencies determine the conditional expectation weights.The dataset has two binary variables and uses occurrence counts as instance weights.
  • Example: For the example conditioned on X2 = 0, the correct expectation weights F(0, 0) by 2/3 and F(1, 0) by 1/3.These weights reflect the occurrence counts of the two relevant binary instances.

B Proof of Proposition 3

The proof reduces SHAP computation under a constructed binary distribution to expected-value computation while preserving the relevant conditional expectations and SHAP values.

  • Preserving SHAP values: For every feature set S, the constructed projection preserves conditional expectations: E[F|eS] = Eπ[Fπ|eS].The proof partitions the domain into disjoint events T(x) and establishes matching probabilities under the two distributions.
  • Preserving SHAP values: Because all conditional expectations match, the resulting SHAP explanations satisfy SHAPF,Pr(Xj) = SHAPFπ,Prπ(Xj) for every feature j.This follows directly from the SHAP definition after the event-wise expectation equality is established.
  • Distribution construction: The construction defines a probability space Pr′ and expectation E′[F] used to compute the projected function’s expectation.The proof verifies that the constructed probabilities form a valid probability space before invoking the expectation oracle.
  • Oracle reduction: The expected value E′[F] is computed through an oracle for E[F], followed by multiplication by quantities Z and W computable in polynomial time.Thus, the reduction adds only polynomial-time postprocessing around the expectation oracle.

C Proof of Theorem 5

The proof establishes #P-hardness of computing the expectation of logistic regression under the uniform distribution by reducing #NUMPAR to that expectation.

  • Reduction source: #NUMPAR counts subsets that partition the input numbers into two equal-sum sets and is #P-hard.The reduction starts from number partitioning, whose decision version is NP-complete.
  • Logistic-regression construction: The reduction constructs a logistic regression function F and uses an oracle for E_U[F] under the uniform distribution U over {0,1}^n.The weights are chosen from the number-partitioning instance and include a sufficiently large parameter m.
  • Recovering the count: The expectation determines |P| because the lower and upper bounds differ by less than one, allowing the exact integer count to be recovered.The count equals the ceiling of the lower bound and the floor of the upper bound.
  • Gap construction: For partition solutions, the paired sigmoid terms are near zero, whereas nonsolutions contribute values near one within ε.The bounds follow from choosing ε = 1/2^(n+3) and m so that the sigmoid tails are sufficiently small.

D Proof of Theorem 8

The proof reduces NUMPAR to SHAP computation for a trivial classifier over a naive Bayes network, creating a threshold gap that distinguishes partitionable instances.

  • Naive Bayes construction: The reduction builds a naive Bayes network with binary variables X0,...,Xn whose probabilities encode the NUMPAR instance.The construction assumes an even total input sum and introduces a large parameter m.
  • SHAP reduction: The classifier is arranged so that the SHAP value of X0 captures the distinction between number-partitioning solutions and nonsolutions.The proof expresses SHAP using the coalition events XS and groups subsets with their complements.
  • Threshold gap: Therefore, NUMPAR has a solution if and only if SHAPF(X0) ≥ 1/2(1 + ε).This threshold condition is the central claim establishing the reduction.
  • Threshold gap: If NUMPAR has no solution, SHAPF(X0) ≤ 1/2(1 + ε), while any solution yields SHAPF(X0) > 1/2(1 + ε).The separation follows from sigmoid bounds for partitioning and nonpartitioning subsets.

E Proof of Corollary 10

The corollary extends the hardness construction to a Bayesian network with latent variables while preserving the relevant SHAP computation.

  • Network extension: The construction adds two variables and edges X0 → Xn+1 → Xn+2, making X0, Xn+1 latent and setting X0 = Xn+1 = Xn+2.The prediction function is F = Xn+2, so the added variables reproduce the original network behavior.

F Proof of Lemma 13 (1)

This section reduces computing SHAP over an empirical distribution to computing expectations of PP2CNF formulas over quasi-symmetric distributions, establishing polynomial-time equivalence.

  • Computing SHAP-explanations over empirical distributions is polynomial-time equivalent to computing PP2CNF expectations over quasi-symmetric distributions.
  • The empirical distribution is represented by a 0/1 matrix x, with a PP2CNF formula Φx associated to the matrix.The prediction function is reduced, by SHAP linearity, to a function that is one on the first row and zero elsewhere.
  • For the restricted SHAP terms, rows or clauses are removed by fixing selected variables, allowing expectations of restricted formulas to be obtained through the expectation oracle.
  • A matrix is called good when its first row dominates every other row; deleting columns where that row is zero produces a good matrix.
  • For a good matrix, the proof defines quantities v_k and polynomials P and Q whose coefficients encode the values needed for SHAP computation.Although the polynomial definitions involve exponentially many subsets, P and Q have only (m + 1)(n + 1) terms by degree.
  • The coefficients of Q are recovered using oracle evaluations at distinct positive values, yielding a nonsingular system based on a Kronecker product of Vandermonde matrices.

G Proof of Lemma 13 (2)

This section proves the converse reduction: expectations of PP2CNF formulas over quasi-symmetric distributions can be computed using an oracle for SHAP on empirical distributions.

  • An oracle for SHAP on empirical distributions suffices to compute PP2CNF expectations over quasi-symmetric distributions in polynomial time.
  • The reduction first handles symmetric distributions, since variables assigned probability 1 can be fixed directly in the formula.
  • The resulting linear systems are nonsingular: one relies on Vandermonde structure, while another follows from a Cauchy double-alternant determinant.
  • SHAP values for the augmented feature recover the quantities V associated with the constructed matrices, which are then used to solve for the values v_k.
  • The algorithm constructs matrices by adding all-one rows and columns with prescribed zero-one patterns, then augments each with a feature that is one only in the first row.
  • Combining these steps yields the coefficients of the relevant polynomials and completes the proof of Lemma 13.
Loading 2009.08634v2…