Shapley-Taylor Index

The Shapley-Taylor index distributes credit among all subsets of features of size k rather than just individual features. For a given order k, it computes the fair allocation of the model's output to each k-way interaction by applying the Shapley value formula to the lattice of feature subsets. This generalizes the standard SHAP value, which is the order-1 Shapley-Taylor index, to capture pairwise synergies (k=2), three-way interactions (k=3), and beyond.

A fundamental property of the Shapley-Taylor index is that the sum of all interaction effects across all orders exactly equals the model's prediction minus the baseline. Formally, summing the attributions for all subsets of size 1 through d (where d is the total number of features) reconstructs the full model output. This guarantees a complete and lossless decomposition of the prediction into main effects and interaction effects of increasing complexity.

The Shapley-Taylor index satisfies an interaction faithfulness axiom: if a model's output can be perfectly represented as a sum of functions depending on at most k features, then all interaction indices for orders greater than k are exactly zero. This property ensures the index does not hallucinate spurious high-order interactions when the model's decision function is inherently simpler, providing a truthful representation of the model's interaction structure.

The Shapley-Taylor index can be computed recursively from lower-order indices. The order-k interaction effect for a feature set S is derived by taking the discrete derivative of the model's prediction with respect to S and subtracting all lower-order effects that are subsumed within S. This recursive structure mirrors the Möbius inversion on the Boolean lattice and ensures that each interaction index captures only the pure k-way synergy not explained by any subset of the interacting features.

The Shapley-Taylor index is closely related to the functional ANOVA decomposition of a model. While ANOVA decomposes a function into orthogonal components of increasing interaction order under a uniform input distribution, the Shapley-Taylor index weights these components by Shapley-style coalitional coefficients. This weighting ensures the decomposition satisfies the efficiency and symmetry axioms of cooperative game theory, making it more robust for feature attribution than standard ANOVA.

Computing the exact Shapley-Taylor index for all interactions of order k requires evaluating the model on O(d^k) subsets in the worst case, where d is the number of features. For pairwise interactions (k=2), this scales quadratically with the number of features. Practical implementations use sampling approximations and leverage the recursive structure to reduce the number of model evaluations, trading exactness for tractability in high-dimensional settings.

A direct extension of SHAP that captures pairwise feature interaction effects by distributing credit among all pairs of features. Unlike the Shapley-Taylor index, which handles interactions of any order, standard SHAP interaction values decompose a prediction into a matrix of main effects and second-order interactions. The sum of all main effects and interactions equals the difference between the prediction and the baseline.

• Computed by applying the Shapley value to pairs of features
• Requires O(2^M) model evaluations for M features
• Visualized using dependence plots with interaction coloring

The mathematical operator at the core of the Shapley-Taylor interaction index. For a set of features A, the discrete derivative Δ_A f(S) measures the change in the model's output when all features in A are added to coalition S simultaneously. The Shapley-Taylor index of order k is a weighted average of these discrete derivatives over all coalitions.

• Generalizes the marginal contribution concept
• For k=1, reduces to the standard Shapley value
• For k=2, captures pairwise synergies beyond additive effects
• Higher-order derivatives reveal complex feature interdependencies

A fundamental Shapley axiom ensuring that the sum of all attributions exactly equals the difference between the model's prediction and the baseline value. For the Shapley-Taylor index, the efficiency property generalizes: the sum of all interaction indices across all subsets of features up to order k, weighted appropriately, reconstructs the total model output.

• Guarantees complete decomposition of the prediction
• Prevents unexplained residual variance
• Essential for audit and compliance scenarios
• Mathematically: Σ_{A⊆N, |A|≤k} I_A = f(x) - E[f(X)]

A measure of overall feature impact derived by aggregating absolute SHAP values across all instances. For interaction analysis, global importance can be extended to rank feature tuples by their average Shapley-Taylor interaction index magnitude. This reveals which feature combinations consistently drive model behavior across the dataset.

• Computed as mean(|SHAP value|) per feature
• Interaction importance: mean(|I_A|) for feature set A
• Identifies systematic synergies vs. instance-specific interactions
• Used to prune irrelevant feature combinations in high-dimensional data