L-Shapley and C-Shapley: Efficient Model Interpretation for Structured Data

By Jianbo Chen, Le Song, Martin J. Wainwright, Michael I. Jordan. 2018

238 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computer Networks and Communications

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

Citations in the corpus

Explainable machine learning in deployment (2019, methodology): “perturbation-based techniques [8, 14, 22, 34, 50, 61] and gradientbased techniques [7, 41, 57, 59, 60, 62].”
Data Shapley: Equitable Valuation of Data for Machine Learning (2019, background): “Shapley value has been recently proposed as a feature importance score for the purpose of interpreting black-box predictive models (Kononenko et al., 2010; Datta et al., 2016; Lundberg & Lee, 2017; Cohen et al., 2007; Chen et al., 2018; Lundberg et al., 2018).”
On Completeness-aware Concept-Based Explanations in Deep Neural Networks (2019, methodology): “…methods fall under the categories: (a) feature-based explanation methods, that attribute the decision to important input features [1, 2, 13, 14], (b) sample-based explanation methods, that attribute the decision to previously observed samples [15, 16, 17, 18], and (c) counterfactual-based…”
Explainable artificial intelligence: a comprehensive review (2021, methodology): “Chen et al. (2018) suggested two extensions of the SHAPE framework, which include L-Shapley and the C-Shapley algorithm, to score instance-wise feature importance in order to perform the model interpretation. After that, the degree that the features affect the output is well-explained using a graph-”
Understanding Global Feature Contributions With Additive Importance Measures (2020, methodology): “Shapley values have been studied extensively in game theory [33] and have been applied to machine learning for both local [7, 9, 25, 37] and global interpretability.”
On Concept-Based Explanations in Deep Neural Networks (2019, background): “Most works fall under two categories: (i) feature-based explanation methods, that attribute the decision to important input features [23, 19, 26, 6], and (ii) sample-based explanation methods, that attribute the decision to previously observed samples [17, 30, 13, 2].”
Deep neural network or dermatologist? (2019, methodology): “Finally, there exists recent, alternative methods for implementing Shapley analysis that may well produce better results and permit the use of higher resolution images [5,1] .”
Rethinking Cooperative Rationalization: Introspective Extraction and Complement Control (2019, background): “Many previous works (Lei et al., 2016; Chen et al., 2018a) follows the above deﬁnition of rationales.”
Explaining by Removing: A Unified Framework for Model Explanation (2020, methodology): “However, recent work has also proposed the strategy of local feature selection (Chen et al., 2018a), and other papers have introduced methods to isolate sets of relevant features (Zhou et al., 2014; Fong and Vedaldi, 2017; Dabkowski and Gal, 2017).”
The Explanation Game: Explaining Machine Learning Models with Cooperative Game Theory (2019, methodology): “The details of these techniques are beyond the scope of this work, but we refer the reader to (Maleki et al. 2013; Chen et al. 2018; Aas, Jullum, and Løland 2019; Hunt et al. 2019; Ancona, Oztireli, and Gross 2019).”
Generic Attention-model Explainability for Interpreting Bi-Modal and Encoder-Decoder Transformers (2021, methodology): “There are multiple families of explainability methods, including saliency-based methods [8, 34, 23, 49, 45, 48], methods that consider activations [10] using the forward pass or the backprop [46], perturbation based methods [11, 12], and methods based on Shapley-values [22, 6].”
On Explainability of Graph Neural Networks via Subgraph Explorations (2021, methodology): “Hence, in this work, we propose to adopt the Shapley values (Kuhn & Tucker, 1953; Lundberg & Lee, 2017; Chen et al., 2018a) as the scoring function.”
A Game Theoretic Approach to Class-wise Selective Rationalization (2019, methodology): “Many of these methods utilize gradient information [6, 20, 25, 26, 27, 28], while techniques like local perturbations [11, 13, 16, 22] and Parzen window [7] have also been used to loose the requirement of differentiability.”
Explaining individual predictions when features are dependent: More accurate approximations to Shapley values (2019, unknown): “Very recently, there has been some attempts at using the underlying graph structure of the input data to reduce the computational complexity (Chen et al., 2018; Li et al., 2018).”