PaperlayerView exact revision on arXiv

Source-linked AI summary

The Shapley Taylor Interaction Index

Kedar Dhamdhere, Ashish Agarwal, Mukund Sundararajan

arXiv:1902.05622v2cs.GTecon.TH

TL;DR

Feature attribution traditionally assigns predictions to base features, but the paper addresses the need to explain joint feature influence. It proposes the Shapley-Taylor index, axiomatizes and analyzes it against a prior interaction index, and applies it across three models and tasks, identifying qualitative interactions.

  • Problem

    Existing attribution methods focus on base-feature importance, while the paper seeks explanations of feature influence in conjunction, including main effects and interactions.

  • Method

    The paper generalizes the Shapley value to interactions up to size k, using random feature orderings, Shapley-style axioms, efficiency, and an interaction distribution axiom.

  • Results

    The Shapley-Taylor index preserves efficiency, contrasts with Shapley interaction indices, and is applied to sentiment analysis, random forest regression, and question answering.

  • Takeaways & Limitations

    The method provides richer individual-input explanations by assigning importance to feature interactions and identifying qualitative interactions across three applications.

  • Takeaways & Limitations

    The axiomatization includes efficiency and an interaction distribution axiom, with the latter defined for interaction functions representing pure interactions.

Abstract

from arXiv · show

The attribution problem, that is the problem of attributing a model's prediction to its base features, is well-studied. We extend the notion of attribution to also apply to feature interactions. The Shapley value is a commonly used method to attribute a model's prediction to its base features. We propose a generalization of the Shapley value called Shapley-Taylor index that attributes the model's prediction to interactions of subsets of features up to some size k. The method is analogous to how the truncated Taylor Series decomposes the function value at a certain point using its derivatives at a different point. In fact, we show that the Shapley Taylor index is equal to the Taylor Series of the multilinear extension of the set-theoretic behavior of the model. We axiomatize this method using the standard Shapley axioms -- linearity, dummy, symmetry and efficiency -- and an additional axiom that we call the interaction distribution axiom. This new axiom explicitly characterizes how interactions are distributed for a class of functions that model pure interaction. We contrast the Shapley-Taylor index against the previously proposed Shapley Interaction index (cf. [9]) from the cooperative game theory literature. We also apply the Shapley Taylor index to three models and identify interesting qualitative insights.

1 Introduction

The paper extends feature attribution from individual features to interactions among subsets, seeking richer explanations for individual model inputs. It proposes and axiomatizes the Shapley-Taylor index, connects it to Taylor series, compares it with Shapley interaction indices, and applies it to three tasks.

  • Motivation: Feature attribution measures how base features contribute to a model prediction but does not reveal the network’s logic beyond individual feature importance.The paper motivates interaction analysis as a richer form of explanation for individual inputs.
  • Motivation: The paper seeks to identify whether sets of features influence predictions jointly rather than independently, including pairwise and higher-order interactions.The motivation highlights interactions in tasks such as sentiment analysis and models that create higher-order representations.
  • Contributions: The Shapley-Taylor index attributes a prediction to interactions among feature subsets up to a chosen size k.For k = 2, the target explanation contains main effects and pairwise interaction effects.
  • Contributions: The method is axiomatized using standard Shapley principles plus an interaction distribution axiom for functions representing pure interactions.The new axiom specifies how interactions are distributed for interaction functions.
  • Contributions: The paper replaces the Shapley interaction index’s recursive axiom with efficiency and reports that the earlier method can amplify interaction effects or produce seemingly incorrect signs.The comparison concerns whether attributions sum to the function score difference between the input and the empty set.
  • Contributions: The Shapley-Taylor index is equivalent to applying a Taylor series to the multilinear extension of the function, and the paper demonstrates applications in sentiment analysis, regression, and question answering.The applications study a convolutional neural network, a random forest, and QANet.

2 Shapley-Taylor indices

The Shapley-Taylor index generalizes the Shapley value by assigning attributions to feature interactions of sizes up to an explanation order k. It averages discrete interaction effects over uniformly random feature orderings and reduces to the Shapley value when k = 1.

  • 2.1 Shapley Value: The Shapley value assigns each feature its marginal contribution averaged over uniformly random orderings of the features.A feature receives the change in function value from adding it to the set of preceding features.
  • 2.2 Definition of Shapley-Taylor indices: The Shapley-Taylor index extends feature attribution by including interaction terms in addition to individual-feature attributions.It is computed as an expectation over uniformly random feature orderings.
  • 2.2 Definition of Shapley-Taylor indices: For k = 2, individual features use their marginal contributions, while each pair receives a discrete derivative evaluated at the features preceding both members in the ordering.The pairwise value is then averaged over uniformly random orderings.
  • 2.2 Definition of Shapley-Taylor indices: For interaction sets smaller than k, the fixed-ordering value is the discrete derivative at the empty set and therefore does not depend on the permutation.The predecessor set πS contains elements preceding every feature in S.
  • 2.2 Definition of Shapley-Taylor indices: When k = 1, the construction becomes precisely the Shapley value, so Shapley-Taylor indices generalize the standard feature-attribution method.The closed-form theorem provides another way to compute the indices, although direct computation over all subsets is exponential.
  • 2.2 Definition of Shapley-Taylor indices: The Shapley interaction index is a previously proposed alternative that the paper introduces for comparison.The paper contrasts its definition and properties with the Shapley-Taylor construction.

3 Axiomatization of the Shapley-Taylor Interaction Index

The paper axiomatizes Shapley-Taylor indices using the standard Shapley axioms plus Interaction Distribution, proving that these axioms uniquely characterize the method and connecting it to Taylor expansions of multilinear extensions.

  • Interaction Distribution axiom: The Interaction Distribution axiom assigns zero to lower-order terms of pure interactions, while order-k terms accumulate higher-order contributions.Interaction functions are nonzero exactly when all features in T are present; |T| is their interaction order.
  • Uniqueness theorem: Theorem 2 states that Shapley-Taylor indices are the only interaction indices satisfying axioms 1–5.The proof first verifies the axioms for Shapley-Taylor indices, then derives the required values on unanimity functions for any method satisfying them.
  • Axiom satisfaction: Shapley-Taylor indices satisfy linearity, dummy, symmetry, Interaction Distribution, and efficiency axioms.The proofs use discrete-derivative properties, permutation expectations, dummy-feature behavior, and unanimity functions.
  • Uniqueness theorem: For unanimity functions, interaction values depend only on the unanimity set size and explanation order, and the values extend uniquely to all functions.Unanimity functions form a linear basis of G_N, so their axiomatically determined values uniquely determine the method.
  • Connection to Taylor series: For explanation order k, Shapley-Taylor indices of orders j<k can be obtained from the corresponding jth-order terms of the multilinear extension’s Taylor series.The multilinear extension has a probabilistic interpretation, and the result follows from the Taylor expansion of its diagonal restriction.

4 Comparison of Shapley Interaction Index and Shapley Taylor Index

The comparison examples show that Shapley-Taylor indices conserve interaction mass and provide stable pairwise explanations, whereas Shapley interaction indices can inflate or obscure interactions.

  • A Linear Model with Crosses: For a three-feature cross, Shapley-Taylor assigns c/3 to each pair, totaling c, while preserving main effects of 1 each.This matches the coefficient of the three-way cross and the expected main effects.
  • A Linear Model with Crosses: Shapley interaction indices assign c/2 to each pair, totaling 3c/2 and amplifying the interaction magnitude.The inflation factor depends on interaction size.
  • A Linear Model with Crosses: When c exceeds 3, subtracting inflated pairwise interactions from Shapley values produces negative main effects.The paper identifies this sign as inconsistent with the expected decomposition of the function.
  • The Majority Function: For majority functions, pairwise Shapley-Taylor singleton terms are zero and each pair receives 2/(n · (n −1)), indicating interaction-focused behavior.The pairwise values follow from symmetry and efficiency.
  • The Majority Function: Pairwise Shapley interaction indices are zero for every pair in majority functions, while larger-order values can be nonzero and non-intuitive.With three features, the all-feature interaction value is −2.
  • The Majority Function: Across majority functions, total Shapley interaction diverges and alternates sign despite the function value remaining constant at 1.The plotted totals are in log scale, and each fixed-size family of non-singleton interactions has the same sign.
  • Comparison: Pairwise Shapley-Taylor analysis uses O(n^2) quantities and can reveal behavior regardless of the size of interacting feature sets.The alternative requires comparing 2^n quantities and can produce unstable results.

5 Applications

The Shapley-Taylor indices reveal qualitative feature interactions across sentiment, house-price regression, and reading-comprehension models. The analyses identify linguistic effects, substitutive feature pairs, and question–context word matches.

  • 5 Applications: The study applies Shapley-Taylor indices to sentiment classification, house-price regression, and reading comprehension.The models are a convolutional neural network, random forest, and QANet, respectively.
  • 5.1 Insights: Sentiment interactions capture negation, intensification, complementarity, and suppression effects in review text.Examples include “inspiring” amplified by “both,” “crisp” intensified by sentence position, and third-person sentiment suppressed by interaction with “A.”
  • 5.1 Insights: Most influential house-price pair interactions are substitutes: negative main effects can accompany positive pairwise interaction values.The authors suggest correlated features may explain this pattern and plot pairwise main effects against interaction effects in Figure 1.
  • 5.1 Insights: Figure 3 identifies which paragraph words important question words match with, including percentage–percent and touchdown matches.This extends prior analyses that examined whether important question words were ignored without identifying their matching paragraph words.

6 Appendix

The appendix proves the Shapley-Taylor theorem by reducing the analysis to unanimity functions and extending the result by linearity. It connects Möbius coefficients, discrete derivatives, and the multilinear-extension Taylor expansion.

  • 6 Appendix: The proof decomposes any function into unanimity functions and uses linearity to extend the index from those basis functions to the general function.The theorem is first proved for unanimity functions, whose multilinear extensions are then analyzed.
  • 6 Appendix: Beta-function identities determine the coefficients appearing in the Shapley-Taylor expansion and remainder.The appendix uses 1/(k · B(w + 1, k)) and related Beta-function expressions.
  • 6 Appendix: Möbius coefficients are related to discrete derivatives, providing the algebraic bridge used in the decomposition.The appendix states and proves a lemma establishing this relation.
  • 6 Appendix: The proof derives the multivariate Taylor expression from the diagonal restriction g(t) = f(t, . . . , t).Because f is multilinear, only mixed partial terms remain, and the j! mixed partials are identical.
  • 6 Appendix: The Lagrange remainder is evaluated through mixed partial derivatives and integration, with an extra factor of k surviving after rearrangement.The appendix exchanges summation and integration while analyzing the remainder term.
  • 6 Appendix: At the origin, the discrete derivative satisfies Δ_S f_W(0) = 1 exactly when S = W and is otherwise zero.This identity supplies the basis-function evaluation used in the proof.
Loading 1902.05622v2…