Faith-Shap: The Faithful Shapley Interaction Index
Che-Ping Tsai, Chih-Kuan Yeh, Pradeep Ravikumar; 24(94):1−42, 2023.
Abstract
Shapley values, originally designed to assign attributions to individual players in coalition games, are now commonly used in explainable machine learning to provide attributions to input features for black-box machine learning models. Shapley values have the advantage of satisfying a natural set of axiomatic properties. However, extending Shapley values to assign attributions to interactions rather than individual players, known as interaction indices, is not straightforward. The natural set of axioms for Shapley values, when applied to interactions, does not result in a unique interaction index. Many proposals introduce additional, possibly stringent axioms, sacrificing the key axiom of efficiency, to obtain unique interaction indices. In this work, we take a different approach by viewing Shapley values as coefficients of the most faithful linear approximation to the pseudo-Boolean coalition game value function. By extending linear to higher order polynomial approximations, we define a general family of faithful interaction indices. We show that by requiring these faithful interaction indices to satisfy interaction-extensions of the standard individual Shapley axioms (dummy, symmetry, linearity, and efficiency), we obtain a unique Faithful Shapley Interaction index, denoted as Faith-Shap, which serves as a natural generalization of the Shapley value to interactions. We also provide some illustrative comparisons between Faith-Shap and previously proposed interaction indices, and explore some of its interesting algebraic properties. Additionally, we demonstrate the computational efficiency of computing Faith-Shap and provide qualitative insights through illustrative experiments.
[abs]