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

Abstract

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.

References in corpus (1)

• Learning to Explain: An Information-Theoretic Perspective on Model Interpretation

Cited by in corpus (14)

• Understanding Global Feature Contributions With Additive Importance Measures
• On the Explainability of Natural Language Processing Deep Models
• Deep neural network or dermatologist?
• Neuron Shapley: Discovering the Responsible Neurons
• A Distributional Framework for Data Valuation
• Feature Removal Is a Unifying Principle for Model Explanation Methods
• Why model why? Assessing the strengths and limitations of LIME
• Who's responsible? Jointly quantifying the contribution of the learning algorithm and training data
• Improving KernelSHAP: Practical Shapley Value Estimation via Linear Regression
• Rethinking Cooperative Rationalization: Introspective Extraction and Complement Control
• Evaluating and Rewarding Teamwork Using Cooperative Game Abstractions
• Efficient Interpretation of Deep Learning Models Using Graph Structure and Cooperative Game Theory: Application to ASD Biomarker Discovery
• Logic Traps in Evaluating Attribution Scores
• Model-Agnostic Explanations using Minimal Forcing Subsets