PaperlayerView exact revision on arXiv

Source-linked AI summary

Impossibility Theorems for Feature Attribution

Blair Bilodeau, Natasha Jaques, Pang Wei Koh, Been Kim

arXiv:2212.11870v3cs.LGcs.AI

TL;DR

The paper asks whether feature attribution methods reliably reveal local counterfactual model behaviour for tasks such as recourse and spurious-feature identification. It formalizes these tasks as hypothesis tests and shows theoretically and empirically that complete and linear methods, including SHAP and IG, can be unreliable, while brute-force model queries can work for some defined tasks.

  • Problem

    Practitioners lack a principled basis for using feature attribution methods to infer local counterfactual model behaviour in tasks such as recourse and spurious-feature identification.

  • Method

    The paper formalizes counterfactual behaviour as hypothesis testing and analyzes complete and linear attribution methods theoretically and empirically across model classes and datasets.

  • Results

    Complete and linear methods can perform no better than random guessing for inferring model behaviour, with near-random ROC curves for SHAP and Integrated Gradients in almost all experiments.

  • Takeaways & Limitations

    End-tasks should be defined concretely, because repeated model evaluations can provide a reliable brute-force approach for some tasks despite being computationally expensive.

  • Takeaways & Limitations

    The brute-force hypothesis test is designed to always succeed for spurious-feature identification but may be inefficient for more structured models.

Abstract

from arXiv · show

Despite a sea of interpretability methods that can produce plausible explanations, the field has also empirically seen many failure cases of such methods. In light of these results, it remains unclear for practitioners how to use these methods and choose between them in a principled way. In this paper, we show that for moderately rich model classes (easily satisfied by neural networks), any feature attribution method that is complete and linear -- for example, Integrated Gradients and SHAP -- can provably fail to improve on random guessing for inferring model behaviour. Our results apply to common end-tasks such as characterizing local model behaviour, identifying spurious features, and algorithmic recourse. One takeaway from our work is the importance of concretely defining end-tasks: once such an end-task is defined, a simple and direct approach of repeated model evaluations can outperform many other complex feature attribution methods.

1 Introduction

The paper argues that complete and linear feature attribution methods can be unreliable for local counterfactual questions, despite being widely viewed as more reliable. It develops impossibility results and discusses repeated model queries as a direct alternative for defined end-tasks.

  • Motivation: Feature attribution methods are used to answer local counterfactual questions about model behaviour near a particular example.Applications include algorithmic recourse and spurious feature identification.
  • Main result: Complete and linear methods, including SHAP and Integrated Gradients, can be less reliable than simpler gradient-based methods for local counterfactual questions.The paper argues that users may do no better than random guessing for algorithmic recourse and spurious feature identification.
  • Main result: There are uncountably many model pairs sharing feature attributions while having arbitrarily different counterfactual behaviour.Conversely, distinct attribution values can correspond to model pairs with identical counterfactual behaviour.
  • Failure mechanism: Complete and linear methods can remain unreliable in infinitesimally small neighborhoods because they depend on model behaviour at a potentially distant baseline.This creates failure modes even when the target behaviour is highly local.
  • Practical direction: Repeated model queries provide a brute-force approach for inferring counterfactual behaviour when reliable attribution methods are unavailable.The paper gives an example for spurious feature identification and notes that the approach is computationally expensive.

2 Problem Framework

The paper frames local counterfactual reasoning as a hypothesis-testing problem over model behaviours near an example. It evaluates feature attribution methods by whether their outputs support reliable decisions across model classes, using specificity and sensitivity as worst-case criteria.

  • Counterfactual model behaviour: Counterfactual model behaviour describes a model’s outputs near an example when a feature varies within a specified neighborhood.The framework studies which of two candidate local behaviours is more likely.
  • End-tasks: Users may need to distinguish broad behaviour classes, such as increasing versus decreasing models, rather than identify one exact local function.The theoretical results apply to every candidate pair and therefore extend to more general behaviour classes.
  • End-tasks: The framework connects counterfactual model behaviour to algorithmic recourse and spurious feature identification.Recourse asks whether increasing or decreasing a feature is beneficial, while spurious-feature identification tests sensitivity to local perturbations.
  • Hypothesis testing: The paper formulates learning counterfactual behaviour as hypothesis testing between disjoint subsets of a model class.A feature-attribution hypothesis test must make its decision solely from the attribution output at an example.
  • Feature attribution methods: Feature attribution methods may take a model, a localized example, and a baseline distribution as inputs.The baseline incorporates model behaviour from other examples; Gradient is independent of the baseline, whereas IG depends on it.
  • Evaluation criteria: Specificity measures correct non-rejection under the null, while sensitivity measures correct rejection under the alternate hypothesis.The framework takes the infimum over models in each hypothesis class and seeks to maximize both quantities.
  • Evaluation criteria: The evaluation is deterministic because the model is already learned and there is no randomness over retraining data.This differs from standard testing over random data-generating processes while retaining a requirement to perform across all models of interest.
  • Assumptions: The framework does not assume that features are independent under the baseline distribution.This is an explicit scope condition in the paper’s notation and setup.

3 Impossibility Theorems

For mildly rich model classes, complete and linear feature attribution methods cannot generally support better-than-random inference of counterfactual model behaviour or related tasks without strong additional assumptions. The paper establishes this theoretically for SHAP and Integrated Gradients, applies it to recourse and spurious-feature identification, and contrasts them with cases where Gradient or repeated model queries are more reliable.

  • Main impossibility result: Mildly rich model classes make it impossible to conclude that complete and linear attribution methods outperform random guessing for counterfactual model behaviour.The result applies without strong additional assumptions on the learning algorithm or data distribution.
  • Method class: Completeness requires feature attributions to sum to the output difference from a baseline, while linearity constrains attributions for additive models; SHAP and Integrated Gradients satisfy both properties.
  • Scope: The assumptions are typically satisfied by neural-network settings, because ReLU networks can represent sufficiently many piecewise-linear extensions of local counterfactual behaviour.
  • Formal consequence: Theorem 3.3 shows that complete and linear methods cannot provide a sensitivity-specificity tradeoff better than random guessing, including for recourse and spurious-feature identification.The paper reports empirical evidence that this pattern also holds for real data and real models.
  • Scope and implications: The conclusions are not guaranteed to be more reliable than random guessing for high-stakes applications such as determining clinical-trial membership.The stated results focus on single-feature dependence, while extensions to feature groups and proofs are deferred to an appendix.
  • Comparison with Gradient: For sufficiently local perturbations, Gradient is always successful at one sensitivity task, whereas complete and linear methods may be unreliable and can be less reliable than Gradient.
  • End-tasks: The impossibility result applies to algorithmic recourse and spurious feature identification, including distinguishing whether increasing or decreasing a feature changes the model output.
  • Simple models: Even simple model classes can produce incorrect inferences with significant probability; in one case, attribution-based tests draw the wrong conclusion at least 1/4 of the time.

4 Experiments

Experiments evaluate attribution methods on tabular and image datasets using ROC curves for recourse and spurious-feature tasks. SHAP and IG are usually near random guessing, while simpler local methods sometimes perform better but remain unreliable.

  • Evaluation setup: Experiments compare attribution methods by constructing empirical ROC curves across datasets and end-tasks.The study retrains 10 neural networks per dataset, samples 20 test examples, and evaluates attribution-based hypothesis tests.
  • Results: SHAP and Integrated Gradients ROC curves are near random guessing for almost all experiments.This experimental pattern agrees with the paper’s theoretical results.
  • Results: IG performance depends on its baseline, but both tested baselines are often near the random-guessing line.The all-zero baseline is generally worse than the minimum-feature baseline, and the appropriate baseline cannot be known in advance without strong additional knowledge.
  • Results: Simpler local methods sometimes outperform SHAP and IG, although gradients, SmoothGrad, and LIME also frequently fail to improve on random guessing.The authors suggest their occasional advantage may reflect that recourse and spurious-feature identification are local end-tasks.
  • Results: End-tasks appear generally easier on tabular than image datasets: tabular ROC curves are often far from random guessing, whereas image curves are near the diagonal.The authors conjecture that simpler tabular models make gradients more indicative of counterfactual behaviour.

5 Towards Theoretical Guarantees for Perturbation-Based Methods

The paper studies repeated model evaluations as a direct alternative to attribution methods for solving counterfactual end-tasks. Sufficiently many queries can achieve arbitrarily high specificity and sensitivity, though the simple guarantee may be inefficient.

  • Brute-force guarantees: Repeatedly evaluating f at nearby points can directly infer counterfactual behaviour because that behaviour is determined by f(x′).The paper uses this brute-force strategy to establish guarantees for spurious-feature identification.
  • Brute-force guarantees: For every n, a hypothesis test using n evaluations exists for Lipschitz models in the spurious-feature identification setting.The theorem considers real-valued outputs, fixed δ and ε, and a selected feature.
  • Brute-force guarantees: Specificity and sensitivity can approach one as the number of model evaluations tends to infinity.The result also extends to multivariate settings, where the dependence on the number of features is exponential.
  • Concrete example: For 10 features, roughly 20,000 model evaluations yield perfect specificity and over 90% sensitivity for detecting sensitivity to a 5% feature change exceeding 1%.This example uses 1-Lipschitz models and concerns spurious-feature identification.
  • Limitations: The simple always-successful hypothesis test may be inefficient for more structured models, and the reliability of more efficient brute-force tests remains unclear across end-tasks.The authors identify this as an open direction for evaluating and designing task-specific methods.

6 Related Literature

Related work includes impossibility results for stability and local approximation, formalizations of feature attribution, and individual counterexamples. This paper distinguishes its broader guarantees across sufficiently rich model classes and counterfactual settings.

  • Impossibility results: Prior work proves that complete attribution methods cannot be weakly dependent on the input.The paper argues that its results further imply complete and linear methods cannot even be close to weakly dependent for relevant piecewise-linear models.
  • Impossibility results: Fokkema et al. show failures for continuous methods near decision boundaries, whereas this paper claims unreliability at any example for sufficiently rich model classes.The paper also extends the target beyond recourse-like behaviour to general counterfactual model behaviour.
  • Impossibility results: Han et al. identify neighbourhoods where perturbation-based attributions fail to match the model, while this paper places the failure in the neighbourhood around which attribution is centered.The contrast concerns where the mismatch is guaranteed, not merely whether a mismatch exists somewhere.
  • Formalizations: Other studies formalize attribution through necessity and sufficiency, decision theory, functional feature dependence, or loss minimization.These approaches provide lenses for studying feature attribution rather than the impossibility result developed here.
  • Counterexamples: The literature also contains individual counterexamples in which SHAP and IG disagree or SHAP attributions conflict with human intuition.These examples motivate broader theoretical analysis of reliability.

7 Conclusion

The paper concludes that common complete and linear attribution methods need not improve on random guessing for inferring model behaviour. It emphasizes precise end-task definitions and direct task-optimized methods, including computationally expensive brute-force evaluation.

  • Conclusion: Feature attribution methods used in high-stakes settings require rigorous understanding of when their performance is reliable.The conclusion frames this need in contexts such as medicine and law.
  • Conclusion: Complete and linear methods can be provably unreliable, while brute-force evaluation is guaranteed to work for some end-tasks despite being computationally expensive.The conclusion presents both the limitation of current guarantees and the contrasting brute-force approach.
  • Conclusion: Precisely defining the end-task is crucial because directly optimizing a method for that task can provide straightforward answers.The paper concludes that interpretability goals are not impossible, but require new methods and explicit assumptions about reliability.

A Proofs for Completeness and Linearity

This section formally defines SHAP and Integrated Gradients and establishes that both methods satisfy completeness and linearity. It also specifies the marginal SHAP convention and a baseline-distribution extension for Integrated Gradients.

  • SHAP: SHAP is defined using the marginal-expectation convention, which is the most common practical implementation.The original SHAP definition was conditional, but the paper focuses on the marginal version for tractability.
  • Integrated Gradients: Integrated Gradients is extended from a single baseline example to averaging over a baseline distribution.The point-mass case recovers the original definition.
  • Completeness: SHAP is complete.
  • Completeness: Under stated differentiability or Lipschitz conditions, Integrated Gradients is complete.The proposition gives two sufficient regularity conditions for completeness.
  • Linearity: Integrated Gradients and SHAP are linear.The appendix introduces precise definitions and proofs for this shared property.

B.2 Proof of Main Result

The proof constructs models that share any prescribed complete-and-linear attribution while exhibiting contrasting local behavior. This makes attribution-based hypothesis tests unable to distinguish the relevant model classes reliably.

  • Main theorem: Any complete-and-linear attribution method and feature-attribution hypothesis test are covered by the main theorem.
  • Construction: The construction uses piecewise-linear models on local interval products and selects coefficients to match prescribed attribution values.The coefficients are chosen separately for relevant feature and output indices.
  • Hypothesis test: The proof defines a test that separates the contrasting model classes through local output changes near the example.For one class the test becomes one, while for the other it becomes zero under the constructed conditions.

C.2 Proof of Proposition 3.6

This proof reduces the proposition to an earlier theorem by embedding the one-feature construction into the broader model class. The remaining coordinates are fixed as constant functions.

  • Reduction: The proof defines G(0) and G(1) as subclasses of the proposition’s contrasting model sets.
  • Reduction: The earlier theorem then applies because the model class satisfies the required assumption.

C.3 Proof of Proposition 3.10

This proof compares the sign of complete-and-linear attribution with the sign of the model derivative for a polynomial family. The resulting thresholds differ, yielding a Gaussian-probability bound.

  • Threshold comparison: Complete-and-linear attribution is positive exactly when a > 1/(1−EµX^n), whereas the derivative is positive exactly when a > 1/n.
  • Probability bound: The differing thresholds imply a probability expression that is approximated using the Gaussian cumulative distribution function.
  • Probability bound: The upper bound follows because the Gaussian probability of a > 1/n is at most 0.5.

C.4 Proofs for Recourse and Spurious Features

The corollaries extend the impossibility result to algorithmic recourse and spurious-feature identification under specified model and distributional assumptions. They also formalize query-based testing as a separate procedure for deciding model behavior from repeated evaluations.

  • Recourse: The recourse corollary generalizes Theorem 3.3 to complete and linear feature attribution methods and feature-attribution hypothesis tests.The result is stated for functions satisfying the listed assumptions and for recourse-defined model classes.
  • Proof strategy: The proofs construct corresponding function classes by selecting component functions g(0) and g(1) whose behavior matches the recourse or spurious-feature definitions.The proof then applies the preceding theorem after verifying the required inclusions and assumptions.
  • Spurious Features: The spurious-feature corollary gives the analogous generalization for complete and linear feature attribution methods and feature-attribution hypothesis tests.Its setting uses model classes constructed from the spurious-feature definition and functions satisfying the stated assumptions.
  • Query-based testing: A query algorithm sequentially chooses examples to query, while a query hypothesis test uses the observed queries to determine the probability of rejecting the null hypothesis.The combined procedure is evaluated through a random variable representing its specificity and sensitivity.
  • Query-based testing: The formal query-testing framework treats the user’s objective as maximizing specificity and sensitivity simultaneously.The framework therefore evaluates both query selection and the subsequent hypothesis test.

D.2 Sample Complexity Theorems

This section formalizes local smoothness through Lipschitz constants and analyzes how many model queries are needed to solve a task that feature-attribution tests cannot solve. The resulting rate is shown to be nearly tight under the stated model assumptions.

  • Definitions: The local Lipschitz constant measures the largest output change per unit input distance on a set B for output coordinate k.It is defined as the supremum of |f(x)k − f(x′)k| divided by ||x − x′||∞ over x,x′ in B.
  • Upper bound: Sufficiently many queries can solve the task that Corollary C.4 shows to be impossible for feature-attribution hypothesis tests.The section introduces qδ to formalize the required query procedure.
  • Upper bound: Theorem D.1 studies this query procedure for models whose local Lipschitz constants are bounded by L.Its setting fixes arbitrary δ, ε > 0 and L > 0 and imposes the bound on the relevant local domain.
  • Tightness: The constructive query rate is nearly tight, as indicated by a first-order Taylor expansion of (1 − x)^n.Theorem D.2 gives the corresponding result for any model-agnostic query algorithm, hypothesis test, and sample size n under the stated assumptions.
  • Lower-bound construction: The lower-bound construction places a Lipschitz bump of maximal value ε inside one of a collection of small cubes.The construction compares a zero function with a function that differs only inside the selected cube.
Loading 2212.11870v3…