Source-linked AI summary
L-Shapley and C-Shapley: Efficient Model Interpretation for Structured Data
Jianbo Chen, Le Song, Martin J. Wainwright, Michael I. Jordan
TL;DR
Shapley-based feature attribution provides instancewise explanations but is computationally difficult because exact scoring scales exponentially with the number of features. This paper develops graph-structured L-Shapley and C-Shapley algorithms with linear complexity, relates them to Shapley and Myerson values, and reports favorable comparisons on language and image data. The approach is scoped to graph-structured settings, with L-Shapley becoming practical for images when small patches rather than pixels are used as features.
Problem
Shapley-based feature-importance scoring requires exponentially many model evaluations, while sampling approximations can have high variance or require prohibitively many samples for large feature sets.
Method
The paper develops L-Shapley and C-Shapley, graph-structured instancewise feature-scoring methods for settings such as chains and grids, and relates them to Shapley and Myerson values.
Results
The proposed algorithms show superior performance to other instancewise feature-scoring methods on text and image classification.
Takeaways & Limitations
Graph structure provides a model-based framework for efficient instancewise feature-importance scoring on language and image data.
Takeaways & Limitations
For image data, L-Shapley becomes practical when small image patches rather than individual pixels are used as features.
Abstract
from arXiv · showhide
We study instancewise feature importance scoring as a method for model interpretation. Any such method yields, for each predicted instance, a vector of importance scores associated with the feature vector. Methods based on the Shapley score have been proposed as a fair way of computing feature attributions of this kind, but incur an exponential complexity in the number of features. This combinatorial explosion arises from the definition of the Shapley value and prevents these methods from being scalable to large data sets and complex models. We focus on settings in which the data have a graph structure, and the contribution of features to the target variable is well-approximated by a graph-structured factorization. In such settings, we develop two algorithms with linear complexity for instancewise feature importance scoring. We establish the relationship of our methods to the Shapley value and another closely related concept known as the Myerson value from cooperative game theory. We demonstrate on both language and image data that our algorithms compare favorably with other methods for model interpretation.
1 Introduction
The paper addresses black-box model interpretability by developing graph-structured, model-based feature-importance methods. L-Shapley and C-Shapley reduce the evaluation cost of Shapley-style scoring from exponential to linear in the number of features.
- Black-box models can achieve high prediction accuracy while sacrificing interpretability, which is crucial in medicine, financial markets, and criminal justice.
- Instancewise feature-importance scoring explains each prediction with a feature-associated vector whose relative importances may vary across instances.
- Shapley-based interpretation is conceptually appealing but generally requires an exponential number of model evaluations.
- The paper adopts a model-based paradigm in which explanations are computed or approximated under structural assumptions rather than without assumptions.
- For graph-structured data such as chains and grids, L-Shapley and C-Shapley exploit the underlying structure to reduce model evaluations to linear in the number of features.
- The paper relates its measures to constrained Shapley values and connects C-Shapley to the Myerson value for graph-restricted games.
2 Background and preliminaries
The paper defines feature-subset importance through a model’s conditional output distribution, then aggregates feature interactions with Shapley values. It also introduces estimation strategies and highlights the exponential cost of exact Shapley computation.
- Importance of a feature subset: The model predicts Y from feature vector x, and P_m(Y | x_S) denotes its conditional response distribution using only subset S.For S = ∅, the restricted distribution is defined as the marginal P_m(Y).
- Importance of a feature subset: The subset importance score v_x(S) has a coding interpretation as the negative expected number of bits needed to encode the model output from x_S.It is zero for deterministic predictions and larger when the output distribution is closer to uniform.
- Importance of a feature subset: Choosing a k-feature subset S*(x) that maximizes v_x(S) also maximizes mutual information I(X_S*(X), Y) among conditional size-k subset-selection rules.The passage states that the converse is also true.
- Importance of a feature subset: Class-specific importance replaces the conditional output distribution with a degenerate distribution and yields the expected log probability of the predicted class.This modification measures subset importance relative to the predicted class rather than the full conditional distribution.
- Estimating the conditional distribution: Conditional probabilities can be estimated using empirical averages or plug-in reference points; the paper uses plug-in estimates with padding indices for language and average pixel strength for images.The plug-in approach is described as more computationally efficient when suitable reference points exist.
- Shapley value: Feature interactions matter because a feature can be uninformative alone yet important in context, as illustrated by “not” in sentiment analysis.The marginal contribution compares subset importance with and without the feature.
- Computational challenge: Sampling-based Shapley approximations may have high variance and require prohibitively many samples when feature counts are large.The paper addresses this challenge with a model-based graph-structured approach and presents its methods as complementary to sampling and regression approximations.
3 Methods
L-Shapley and C-Shapley restrict Shapley-based feature attribution to graph neighborhoods, using local proximity and connectivity to reduce computation while approximating the original scores under assumptions.
- Graph-structured features: Graph structure links features as nodes, with line graphs modeling sequences and grid graphs modeling images.Graph distance is the shortest-path edge count; a k-neighborhood contains nodes within distance k.
- Graph-structured features: The proposed algorithms target settings where distant or disconnected features have weaker interactions.This graph-structured assumption motivates restricting the subsets used to compute feature importance.
- 3.1 Local Shapley: L-Shapley estimates a feature’s importance by perturbing only neighboring features within its graph neighborhood.Its coefficients match the Shapley coefficients restricted to N_k(i), and k is selected partly according to computational considerations.
- 3.2 Connected Shapley: C-Shapley further restricts evaluation to connected subsets of the neighborhood, excluding disconnected subsets included by L-Shapley.For text, this corresponds to evaluating n-grams near the word being explained.
- 3.2 Connected Shapley: C-Shapley’s coefficients arise from a Myerson-based graph coalitional game in which disconnected feature influences are additive.Under certain statistical assumptions, the error between C-Shapley and the original Shapley value can be controlled.
- 3.2 Connected Shapley: On a line graph, computing all C-Shapley scores requires O(k^2d) model evaluations.Each feature requires O(k^2) evaluations, yielding linear complexity in the number of features for fixed k.
4 Properties
L-Shapley and C-Shapley approximate Shapley values under graph-encoded probabilistic structure, while C-Shapley also coincides with the Myerson value under local additivity.
- Approximation of Shapley value: Under graph-encoded Markovian assumptions, both L-Shapley and C-Shapley are related to the original Shapley value.The paper studies these approximation relationships through probabilistic dependence conditions.
- Approximation of Shapley value: The expected error of the L-Shapley estimate relative to the true Shapley-based importance score is bounded by 4ε.
- Approximation of Shapley value: Under the stated conditional-independence assumptions, L-Shapley and C-Shapley equal the Shapley value almost surely.The L-Shapley and C-Shapley conditions are expressed using conditional independence from graph-separated features.
- Approximation of Shapley value: The expected error of the C-Shapley estimate relative to the true Shapley-based importance score is bounded by 6ε.
- Relation to Myerson value: For decomposable score functions, the Myerson value is the Shapley value associated with graph-connected components and satisfies decomposability, additivity, equal contributions, and monotonicity.Decomposability requires a subset score to equal the sum of scores over its connected components.
- Relation to Myerson value: With plug-in conditional-probability estimates and additive disconnected-feature influence, C-Shapley of order k = d is exactly the Myerson value over G.The equivalence follows by partitioning each subset into connected components and summing the corresponding coefficients.
- Approximation methods: Sampling-based Shapley approximations can be combined with local L-Shapley or C-Shapley computations to reduce evaluation complexity in large neighborhoods.The paper describes evaluating connected subsequences on chains and connected squares on grids, and using permutation or regression-based sampling.
5 Experiments
The experiments evaluate L-Shapley and C-Shapley against established interpretation methods on text and image classification. C-Shapley performs especially strongly on image data and on the LSTM text task, while L-Shapley leads on IMDB.
- Experimental setup: The study compares L-Shapley and C-Shapley with KernelSHAP, SampleShapley, LIME, and, for images, Saliency maps.Experiments cover three neural text models and MNIST and CIFAR10 image classifiers.
- Experimental setup: The evaluation measures how the predicted class’s average log-odds score decreases as increasingly important features are masked.The metric is computed on 1,000 test samples, with words replaced by zero padding in the text experiments.
- Text classification: On IMDB, L-Shapley performs best; on AG News, L-Shapley and C-Shapley both outperform the other algorithms.On Yahoo! Answers, C-Shapley outperforms the other methods by a large margin, followed by LIME.
- Computational budget: Under the image evaluation budget, L-Shapley is omitted because raw-pixel evaluation requires nearly 16,000 model evaluations.C-Shapley’s regression-based version evaluates image patches with n ≤4.
- Image classification: C-Shapley performs poorly supported by the provided image evidence?
- Image classification: C-Shapley consistently outperforms the other methods on MNIST and CIFAR10.The image comparison masks top-ranked pixels over increasing percentages of the image.
- Image classification: C-Shapley-selected pixels concentrate around and inside MNIST digits and identify class-distinguishing regions in CIFAR10 images.For CIFAR10, highlighted regions include the head and body parts distinguishing deers and horses, as well as the person riding the horse.
6 Discussion
The paper concludes that L-Shapley and C-Shapley use graphical representations for instancewise feature importance and outperform other methods in text and image classification.
- Discussion: L-Shapley and C-Shapley use a graphical representation of the data for instancewise feature importance scoring.
- Discussion: The proposed algorithms show superior performance to other instancewise feature-importance methods in text and image classification.
A Model structure
The appendix describes the neural architectures used in the text and image experiments, including CNNs, a bidirectional LSTM, and their training setups.
- Text models: The IMDB Word-CNN uses word embeddings, one convolutional layer, max pooling, a dense layer, ReLU, dropout, and RMSProp.It achieves 90.1% test accuracy.
- Text models: The AG News Char-CNN uses six convolutional layers, three max-pooling layers, two dense layers, and SGD with momentum.It reaches 90.09% test accuracy.
- Text models: The Yahoo! Answers model uses 300-dimensional word embeddings, a bidirectional LSTM with 256-dimensional units, dropout, and RMSProp.It reaches 70.84% test accuracy.
- Image models: The MNIST CNN has two 5 × 5 convolutional layers, max pooling, and a final dense linear layer.It achieves 99.7% test accuracy.
- Image models: The CIFAR10 CNN is modified from AlexNet and contains six convolutional layers, two dense layers, pooling, dropout, and Adam optimization.It achieves 96.1% test accuracy.
B Proof of Theorems
The appendix collects the proofs of Theorems 1 and 2.
- Proofs: The appendix contains proofs for Theorems 1 and 2.
B.1 Proof of Theorem 1
The proof of Theorem 1 combines a combinatorial equality with a two-case analysis of feature subsets. It bounds expected approximation error using conditional probability expressions and absolute mutual information, with zero error under additional conditional-independence assumptions.
- Combinatorial lemma: Lemma 1 supplies the combinatorial equality used to simplify the coefficients in the theorem’s error analysis.The proof states the identity for positive n and non-negative s,t with s ≥ t, then applies it with parameters determined by d, S, and U.
- Case analysis: The proof separates the analysis into S = N_k(i) and the general case S ⊂ N_k(i).The L-Shapley estimate for feature i is extended to arbitrary feature subsets S containing i for notational convenience.
- Case 1: For S = N_k(i), subsets A are partitioned by their intersection with S and by the size of their complement intersection.The decomposition A = U_S(A) ∪ V_S(A) organizes the Shapley-value sum before applying the combinatorial equality.
- Case 2: Under the stated conditional-independence assumptions, the bound holds with ε = 0, implying zero expected approximation error.The proof then treats the general case S ⊂ N_k(i) using the preceding arguments.
B.2 Proof of Theorem 2
The proof of Theorem 2 again uses a two-case partitioning argument, adapting it to connected subsequences in the graph structure. Expected error is bounded through combinatorial simplification and conditional mutual-information expressions under stated independence conditions.
- Case structure: The proof begins by dividing the analysis into two cases, paralleling the preceding proof.The cases distinguish the full neighborhood setting from the general setting S ⊂ N_k(i) ⊂ [d].
- Case 1: When S = N_k(i) = [d], each subset A is decomposed into a connected component containing i and a disconnected remainder.The connected component is denoted U_S(A), while V_S(A) is disconnected from it.
- Case 1: The collection C consists of subsets containing i that form connected subsequences, and Shapley subsets are partitioned according to this component.The proof further partitions sets with fixed U_S(A) by the size of V_S(A).
- Case 1: Applying Lemma 1 to the resulting partition yields an upper bound on expected error, after which the difference between m_x(A,i) and m_x(U,i) is analyzed.The stated substitution uses parameters n = d − |U| − 2, s = |U| + 1, and t = |U| − 1.
- Error bound: The error analysis rewrites the relevant difference with conditional probability ratios and bounds it using absolute mutual-information terms.The same structure is used after taking expectation over X and invoking the theorem’s result for the general case.