Faith-Shap: The Faithful Shapley Interaction Index

Che-Ping TsaiChih-Kuan YehPradeep Ravikumar

article2023JMLR96 citations

Develops Faith-Shap, a uniquely determined feature interaction index that extends standard Shapley axioms to higher-order interactions by framing explanation as optimal polynomial approximation of the underlying game value function.

Listen

Modern machine learning increasingly relies on complex black-box models whose decisions require clear interpretation. While standard game-theoretic attribution techniques assign importance values to individual features, they fail to explain complex feature interactions, such as relationships between words in text or groups of pixels in images. Previous attempts to quantify these interactions either introduced unnatural mathematical restrictions or sacrificed critical properties like efficiency, where attributions must sum to the model's total predicted outcome.

The article develops a principled framework to quantify feature interactions up to an arbitrary order while preserving standard game-theoretic axioms. The authors frame interaction attribution as the most faithful polynomial approximation to a model's underlying set function, leading to a unique formulation named the Faithful Shapley Interaction index, or Faith-Shap.

The research evaluates this framework across theoretical game formulations and empirical benchmarks. The approach demonstrates mathematical uniqueness under core axiomatic properties and assesses computational performance on tabular marketing data and sentiment classification using deep language models. The estimation procedure formulates attributions as a regularized weighted least-squares regression rather than relying solely on combinatorial sampling.

The findings establish that Faith-Shap uniquely satisfies linearity, symmetry, dummy player, and efficiency constraints in the interaction setting. Across synthetic and practical datasets, the weighted least-squares estimation required significantly fewer model evaluations to reach target accuracy compared to existing interaction indices, often reducing sample needs by several fold. Furthermore, empirical tests on language data confirmed that Faith-Shap accurately disentangles complementary and non-complementary word interactions without distorting individual feature values.

These results provide a mathematically sound and computationally viable method for auditing high-stakes artificial intelligence systems where feature interactions drive critical decisions. Unlike earlier methods that distorted lower-order or higher-order contributions, Faith-Shap offers a balanced, faithful representation of complex model behavior.

Organizations deploying complex models in regulated or high-impact environments should adopt polynomial approximation frameworks like Faith-Shap when individual feature attributions provide insufficient explanations. Future work should expand formal theoretical guarantees for sample-based approximations and explore alternative cooperative game concepts for interaction settings.

Carnegie Mellon University Faithful Shapley Interaction Index Shapley interaction indices Shapley values

arXiv: 2203.00870 chepingt/Faith-Shap

Paper: A Unified Approach to Interpreting Model Predictions, Scott M. Lundberg et al. (2017). This foundational paper establishes the game-theoretic axiomatic framework for feature attribution and Kernel SHAP, which Faith-Shap directly generalizes to higher-order feature interactions.
Paper: From Local Explanations to Global Understanding with Explainable AI for Trees, Scott M. Lundberg et al. (2020). This work introduces early formulations of SHAP interaction values in tree models, providing the direct baseline and practical motivation for Faith-Shap's efficient interaction index.
Paper: Consistent Individualized Feature Attribution for Tree Ensembles, Scott M. Lundberg et al. (2018). This study analyzes mathematical consistency and local accuracy in tree-based game-theoretic attributions, foundational properties that Faith-Shap formalizes for arbitrary-order interactions.
Paper: “Why Should I Trust You?”: Explaining the Predictions of Any Classifier, Marco Tulio Ribeiro et al. (2016). This paper introduces local surrogate approximations via weighted least-squares regression, which forms the core estimation mechanism extended by Faith-Shap's polynomial formulation.
Paper: Axiomatic Attribution for Deep Networks, Mukund Sundararajan et al. (2017). This paper details the axiomatic approach to feature attribution, defining key invariance and completeness criteria that Faith-Shap preserves in the interaction setting.

Paper: Learning to Estimate Shapley Values with Vision Transformers, Ian Connick Covert et al. (2023). This paper applies scalable estimation techniques to compute game-theoretic Shapley values in modern Vision Transformers, building on efficient attribution paradigms like those in Faith-Shap.
Paper: Data Shapley in One Training Run, Jiachen T. Wang et al. (2025). This work extends cooperative game-theoretic attribution concepts beyond feature spaces into efficient data-valuation frameworks for large foundation models.
Paper: The Dead Salmons of AI Interpretability, Maxime Méloux et al. (2025). This text provides a critical theoretical critique of identifiability and statistical fragility across feature attribution and interpretability methods, offering an important perspective following Faith-Shap.

Cover for Faith-Shap: The Faithful Shapley Interaction Index

Abstract

Shapley values, which were originally designed to assign attributions to individual players in coalition games, have become a commonly used approach in explainable machine learning to provide attributions to input features for black-box machine learning models. A key attraction of Shapley values is that they uniquely satisfy a very natural set of axiomatic properties. However, extending the Shapley value to assigning attributions to interactions rather than individual players, an interaction index, is non-trivial: as the natural set of axioms for the original Shapley values, extended to the context of interactions, no longer specify a unique interaction index. Many proposals thus introduce additional less “natural” axioms, while sacrificing the key axiom of efficiency, in order to obtain unique interaction indices. In this work, rather than introduce additional conflicting axioms, we adopt the viewpoint of Shapley values as coefficients of the most faithful linear approximation to the pseudo-Boolean coalition game value function. By extending linear to ℓ-order polynomial approximations, we can then define the general family of faithful interaction indices. We show that by additionally requiring the 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, which we denote Faith-Shap, as a natural generalization of the Shapley value to interactions. We then provide some illustrative contrasts of Faith-Shap with previously proposed interaction indices, and further investigate some of its interesting algebraic properties. We further show the computational efficiency of computing Faith-Shap, together with some additional qualitative insights, via some illustrative experiments.

Keywords

Faithful Shapley Interaction Index Shapley interaction indices Shapley values Shapley Taylor index interaction efficiency axiom higher-order interactions cardinal-probabilistic indices Banzhaf interaction feature attributions

1. Introduction
2. Preliminaries
2.1 Notations
2.2 Definitions
3. Background: Axioms for Interaction Indices
4. Faith-Interaction Indices
4.1 Axiomatic Characterization of Faith-Interaction Indices
5. Contrasting Faith-Interaction with other Interaction Indices
5.1 Examples
6. Computation of Faithful Shapley Interaction Index
7. Algebraic Properties of Faith-Interaction Indices
7.1 Cardinal Indices
7.2 Multilinear Formulation
7.2.1 Path Integrals
7.2.2 Taylor Expansion
7.2.3 Pseudo-Boolean Function Approximation
8. Experiments
8.1 Computational Efficiency
8.2 Explanations on a Language Dataset
9. Related work
10. Conclusion
Acknowledgments
References
Appendix A. Organization
Appendix B. Experimental Details and Supplementary Results of Computational Efficiency
Appendix C. Experimental details for Language Dataset
Appendix D. Additional Guidance on Theorem 16
Appendix E. Auxiliary Theoretical Results

Knowls

Knowl 1 — Faithfulness as weighted polynomial approximation
model/method
Let $[d]=\{1,\ldots,d\}$ be the feature set, let $v:2^{[d]}\to\mathbb{R}$ be a coalition value function, and let $\ell\in[d]$ be the maximum interaction order. Faith-Interaction indices approximate every coalition value by the sum of the attributions of its subsets of order at most $\ell$ :
$E(v,\ell)=\underset{E\in\mathbb{R}^{\mathcal{S}_{\ell}}}{\arg\min}\;\sum_{S\subseteq[d]}\mu(S)\left(v(S)-\sum_{T\subseteq S,\,|T|\leq\ell}E_T(v,\ell)\right)^2,$
where $\mathcal{S}_{\ell}=\{T\subseteq[d]:|T|\leq\ell\}$ and $\mu:2^{[d]}\to\mathbb{R}_{+}\cup\{\infty\}$ weights coalitions. An infinite weight imposes the exact constraint $v(S)=\sum_{T\subseteq S,|T|\leq\ell}E_T(v,\ell)$ ; a weighting function is proper when it is finite and strictly positive for every nonempty, non-full coalition. Proper weighting makes the constrained least-squares problem have a unique minimizer. Thus, Faith-Interaction indices are precisely the interaction attributions obtained by fitting an order- $\ell$ pseudo-Boolean polynomial to the coalition value function while optionally enforcing exact values at selected coalitions.
Knowl 2 — Axiomatic structure of Faith-Interaction indices
theoretical result
Every Faith-Interaction index is linear in the coalition value function. It satisfies interaction symmetry whenever its coalition weights are permutation-invariant, meaning $\mu(S)$ depends only on $|S|$ ; under the finite-weight setting, permutation invariance is also necessary. It satisfies the interaction dummy property when the coalition weights factor as independent feature-presence probabilities,
$\mu(S)\propto\prod_{i\in S}p_i\prod_{j\notin S}(1-p_j),\qquad 0<p_i<1.$
For finite weights, the simultaneous requirements of linearity, symmetry, and dummy reduce the admissible weighting functions to a two-parameter family. For $a,b\in\mathbb{R}_{+}$ with $a>b$ and positive resulting weights,
$\mu(S)\propto\sum_{i=|S|}^{d}\binom{d-|S|}{i-|S|}(-1)^{i-|S|}g(a,b,i),$
where
$g(a,b,i)=\begin{cases} 1,&i=0,\\ \displaystyle\prod_{j=0}^{i-1}\frac{a(a-b)+j(b-a^2)}{a-b+j(b-a^2)},&1\leq i\leq d. \end{cases}$
A sufficient condition ensuring positivity for every coalition is $1\geq a>b\geq a^2>0$ . The parameters have the interpretation that $a$ is the total weight of coalitions containing a specified feature and $b$ is the total weight of coalitions containing a specified pair of features.
Knowl 3 — Unique Faith-Shap interaction index
theoretical result
The Faith-Shap index is the unique Faith-Interaction index satisfying the interaction extensions of linearity, symmetry, dummy, and efficiency. Here, linearity means linear dependence on $v$ ; symmetry means equally treated features receive equal interaction scores; dummy means an uninfluential feature has zero scores in every interaction containing it; and efficiency means $E_{\varnothing}(v,\ell)=v(\varnothing)$ and $\sum_{\varnothing\neq S\in\mathcal{S}_{\ell}}E_S(v,\ell)=v([d])-v(\varnothing)$ . Its weighting function is
$\mu(S)\propto\frac{d-1}{\binom{d}{|S|}|S|(d-|S|)},\qquad 1\leq |S|\leq d-1,$
with $\mu(\varnothing)=\mu([d])=\infty$ . If $a(v,S)$ denotes the Möbius coefficient
$a(v,S)=\sum_{R\subseteq S}(-1)^{|S|-|R|}v(R),$
then the resulting closed form is
$E^{\mathrm{F\text{-}Shap}}_S(v,\ell)=a(v,S)+(-1)^{\ell-|S|}\frac{|S|}{\ell+|S|}\binom{\ell}{|S|} \sum_{\substack{T\supset S\\|T|>\ell}} \frac{\binom{|T|-1}{\ell}}{\binom{|T|+\ell-1}{\ell+|S|}}a(v,T), \qquad S\in\mathcal{S}_{\ell}.$
When $\ell=1$ , Faith-Shap reduces exactly to the classical Shapley feature values. For $\ell>1$ , it remains order-aware, faithful to all coalition values through the weighted regression objective, and distributes $v([d])-v(\varnothing)$ across all interaction orders up to $\ell$ .
Knowl 4 — Faith-Banzhaf as the generalized-2-efficient alternative
theoretical result
Replacing interaction efficiency by generalized interaction 2-efficiency yields a second unique index within the Faith-Interaction class. Generalized 2-efficiency requires that when two features $i$ and $j$ are merged into one player, the attribution of a coalition containing the merged player equals the sum of the corresponding attributions for $i$ and $j$ in the original game. For $d\geq3$ , the unique index satisfying linearity, symmetry, dummy, and generalized 2-efficiency uses uniform coalition weights $\mu(S)\propto2^{-d}$ and is called Faith-Banzhaf:
$E^{\mathrm{F\text{-}Bzf}}_S(v,\ell)=a(v,S)+(-1)^{\ell-|S|} \sum_{\substack{T\supseteq S\\|T|>\ell}} \left(\frac12\right)^{|T|-|S|} \binom{|T|-|S|-1}{\ell-|S|}a(v,T), \qquad |S|\leq\ell.$
At the highest order, $|S|=\ell$ , Faith-Banzhaf equals the Banzhaf interaction value:
$E^{\mathrm{F\text{-}Bzf}}_S(v,\ell)= \sum_{T\subseteq[d]\setminus S}\frac{1}{2^{d-|S|}}\,\Delta_Sv(T),$
where the discrete derivative is $\Delta_Sv(T)=\sum_{L\subseteq S}(-1)^{|S|-|L|}v(T\cup L)$ for disjoint $S$ and $T$ . Unlike Faith-Shap, Faith-Banzhaf does not impose interaction efficiency.
Knowl 5 — Top-order Faith-Shap is a cardinal-probabilistic and beta-path index
theoretical result
For every maximum order $\ell$ and every coalition $S$ with $|S|=\ell$ , the top-order Faith-Shap attribution is a weighted average of the discrete derivative of $S$ over all disjoint contexts $T$ :
$E^{\mathrm{F\text{-}Shap}}_S(v,\ell)=\sum_{T\subseteq[d]\setminus S}p^{\ell}_{|T|}\,\Delta_Sv(T),$
with
$p^{\ell}_{t}=\frac{(2\ell-1)!(\ell+t-1)!(d-t-1)!}{((\ell-1)!)^2(d+\ell-1)!}, \qquad \sum_{t=0}^{d-\ell}\binom{d-\ell}{t}p^{\ell}_{t}=1.$
Thus, Faith-Shap averages interaction effects across every possible context rather than evaluating them only at the empty context. Equivalently, let $g:[0,1]^d\to\mathbb{R}$ be the multilinear extension of $v$ ,
$g(x)=\sum_{R\subseteq[d]}v(R)\prod_{i\in R}x_i\prod_{i\notin R}(1-x_i),$
and let $\Delta_Sg(x)$ denote its mixed partial derivative with respect to the coordinates in $S$ . The top-order Faith-Shap value is the diagonal path integral
$E^{\mathrm{F\text{-}Shap}}_S(v,\ell)=\int_0^1\Delta_Sg(x,\ldots,x)\,dI_x(\ell,\ell),$
where $I_x(\ell,\ell)$ is the cumulative distribution function of a $\mathrm{Beta}(\ell,\ell)$ random variable.
Knowl 6 — Sampling and computation of Faith-Shap
algorithm
Exact Faith-Shap computation generally requires evaluating the black-box value function on all $2^d$ coalitions. The paper proposes estimating it by weighted least squares. Given a value function $v$ , feature count $d$ , maximum order $\ell$ , and $n$ sampled coalitions, draw each coalition $S$ with probability proportional to
$\frac{d-1}{\binom{d}{|S|}|S|(d-|S|)}$
for $1\leq|S|\leq d-1$ , while enforcing the endpoint constraints $E_{\varnothing}=v(\varnothing)$ and $\sum_{|T|\leq\ell}E_T=v([d])$ . Solve the sampled regression, optionally with $\ell_1$ regularization:
Input: black-box value function $v$ , feature count $d$ , maximum order $\ell$ , sample count $n$
Output: estimated attributions $\widehat E_T$ for every $T$ with $|T|\leq\ell$
Set $E_{\varnothing}=v(\varnothing)$ and enforce $\sum_{|T|\leq\ell}E_T=v([d])$
For $r=1,\ldots,n$
    Sample a coalition $S_r$ with probability proportional to $\frac{d-1}{\binom{d}{|S_r|}|S_r|(d-|S_r|)}$
    Evaluate the black-box model to obtain $v(S_r)$
    Add the squared residual $\left(v(S_r)-\sum_{T\subseteq S_r,\,|T|\leq\ell}E_T\right)^2$ to the regression objective
End for
Minimize the sampled objective subject to the endpoint constraints
Return the fitted coefficients $\widehat E_T$
If the value function has Möbius order $\ell_v$ , meaning $a(v,R)=0$ for all $|R|>\ell_v$ , exact computation of an attribution of order $|S|$ requires only $O\!\left(d^{\ell_v-|S|}\right)$ relevant Möbius terms; in particular, it is polynomial in $d$ when $\ell_v=O(\ell)$ . The paper does not establish finite-sample approximation guarantees for the sampling estimator.
Knowl 7 — Faith-Shap captures both diminishing and increasing returns
data/table
Two symmetric 11-player games were used to test whether interaction scores reflect the sign and magnitude of marginal effects. In the diminishing-return game, $v(S)=0$ for $|S|\leq1$ and $v(S)=|S|-p\binom{|S|}{2}$ otherwise. In the increasing-return wind-turbine game, $v(S)=0$ for $|S|=0$ , $v(S)=3$ for $|S|=1$ , and $v(S)=3|S|-(|S|-2\log(|S|+1))$ for $2\leq|S|\leq11$ .

For the diminishing-return game, the reported values for a representative singleton and pair are:
Could not parse LaTeX table
For the increasing-return wind-turbine game with maximum order $\ell=2$ , the corresponding values are:
Could not parse LaTeX table
Faith-Shap assigns positive singleton effects near one and negative pair effects in the diminishing-return game, and positive pair effects in the increasing-return game. Its order-1 and order-2 scores can therefore be interpreted jointly as individual contributions plus contextual cooperation or competition; the comparison indices either lose this interpretation or concentrate too much mass at one interaction order.
Knowl 8 — Faith-Shap requires fewer model evaluations in estimation experiments
empirical result
The computational comparison used top-order interactions with $\ell=2$ , exhaustive coalition evaluation as ground truth, and averaged results over 50 inputs and 20 random seeds. The simplified IMDB experiment used 50 test examples with $d=15$ words and a BERT sentiment model; the Portuguese bank-marketing experiment used $d=17$ features and an XGBoost model. Faith-Shap was estimated by the sampled weighted regression with $\ell_1$ regularization, using $\alpha=10^{-3}$ for IMDB and $\alpha=10^{-6}$ for bank marketing. Shapley Taylor and Shapley Interaction used permutation-based sampling.

The number of model evaluations needed to achieve averaged squared distance below $10^{-3}$ was:
Could not parse LaTeX table
Across averaged squared distance, precision@10, and the synthetic sparse-function experiments, Faith-Shap was reported to reach more accurate estimates with fewer model evaluations than both permutation-based competitors.
Knowl 9 — Faith-Shap exposes meaningful language interactions
experimental setup
The language explanation experiment used the simplified IMDB sentiment task, where the value function is the BERT-predicted probability of positive sentiment after removing words absent from a coalition. The model achieved 0.82 test accuracy. For each text, the experiment sampled 4000 coalitions, used maximum interaction order $\ell=2$ , and fitted Faith-Shap with Lasso regularization $\alpha=10^{-3}$ .

The strongest reported interactions included:
Could not parse LaTeX table
The corresponding high-magnitude interactions were the phrases “Never, forgot,” “only, good,” “headache, instead,” “appalling, waste,” and “blown, away.” The results demonstrate non-complementarity as well as complementarity: individually negative words can form a strongly positive phrase, individually positive words can form a negative phrase, and a phrase can add meaning only when its words co-occur. In comparison, the paper reports that Shapley Taylor lower-order scores are tied to single-word-versus-baseline effects and that Shapley Interaction scores are not directly comparable across orders because they lack interaction efficiency.
Knowl 10 — Scope and unresolved computational limitation
limitation
For an unrestricted value function on $d$ features, exact Faith-Shap computation remains exponential because the definition aggregates information from all $2^d$ coalitions and the closed form can require exponentially many Möbius coefficients. The paper's polynomial-time observation applies only when the value function has low Möbius order. For general black-box models, the proposed weighted-regression sampler is empirical: the paper demonstrates improved evaluation efficiency but leaves formal sampling approximation bounds and alternative approximation schemes for future work.

Coverage note — Proof-only auxiliary propositions, the full Lagrangian matrix characterization, competing-index sampling pseudocode, and supplementary comparison tables were omitted because they support the main results without adding independent contributed conclusions.

References

1.John F Banzhaf III. Weighted voting doesn’t work: A mathematical analysis. Rutgers L. Rev., 19:317, 1964.
2.A Charnes, B Golany, M Keane, and J Rousseau. Extremal principle solutions of games in characteristic function form: core, chebychev and shapley value generalizations. In Econometrics of planning and efficiency, pages 123–133. Springer, 1988.
3.Hugh Chen, Joseph D Janizek, Scott Lundberg, and Su-In Lee. True to the model or true to the data? arXiv preprint arXiv:2006.16234, 2020.
4.Tianqi Chen and Carlos Guestrin. Xgboost: A scalable tree boosting system. In Proceedings of the 22nd acm sigkdd international conference on knowledge discovery and data mining, pages 785–794, 2016.
5.Ian Covert and Su-In Lee. Improving kernelshap: Practical shapley value estimation via linear regression. arXiv preprint arXiv:2012.01536, 2020.
6.Tianyu Cui, Pekka Marttinen, and Samuel Kaski. Learning global pairwise interactions with bayesian neural networks. arXiv preprint arXiv:1901.08361, 2019.
7.Anupam Datta, Shayak Sen, and Yair Zick . Algorithmic transparency via quantitative input influence: Theory and experiments with learning systems. In Security and Privacy (SP), 2016 IEEE Symposium on, pages 598–617. IEEE, 2016.
8.Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint arXiv:1810.04805, 2018.
9.Guoli Ding, Robert F Lax, Jianhua Chen, and Peter P Chen. Formulas for approximating pseudo-boolean random variables. Discrete Applied Mathematics, 156(10):1581–1597, 2008.
10.Guoli Ding, Robert F Lax, Jianhua Chen, Peter P Chen, and Brian D Marx. Transforms of pseudo-boolean random variables. Discrete Applied Mathematics, 158(1):13–24, 2010.
11.Christopher Frye, Damien de Mijolla, Laurence Cowton, Megan Stanley, and Ilya Feige. Shapley-based explainability on the data manifold. arXiv preprint arXiv:2006.01272, 2020.
12.Katsushige Fujimoto, Ivan Kojadinovic, and Jean-Luc Marichal. Axiomatic characterizations of probabilistic and cardinal-probabilistic interaction indices. Games and Economic Behavior, 55(1):72–99, 2006.
13.Vikas K Garg, Y Narahari, and M Narasimha Murty. Novel biobjective clustering (bigc) based on cooperative game theory. IEEE Transactions on Knowledge and Data Engineering, 25(5):1070–1082, 2012.
14.Amirata Ghorbani and James Zou. Data shapley: Equitable valuation of data for machine learning. In International Conference on Machine Learning, pages 2242–2251. PMLR, 2019.
15.Donald B Gillies. Some theorems on n-person games. princeton university. Unpublished doctoral dissertation.)[aAMC], 1953.
16.Michel Grabisch and Marc Roubens. An axiomatic approach to the concept of interaction among players in cooperative games. International Journal of Game Theory, 28(4):547–565, 1999.
17.Michel Grabisch and Agnieszka Rusinowska. k-additive upper approximation of tu-games. Operations Research Letters, 48(4):487–492, 2020.
18.Michel Grabisch, Jean-Luc Marichal, and Marc Roubens. Equivalent representations of set functions. Mathematics of Operations Research, 25(2):157–178, 2000.
19.Michel Grabisch et al. Set functions, games and capacities in decision making, volume 46. Springer, 2016.
20.Ulrike Grömping. Estimators of relative importance in linear regression based on variance decomposition. The American Statistician, 61(2):139–147, 2007.
21.Peter L Hammer and Ron Holzman. Approximations of pseudo-boolean functions; applications to game theory. Zeitschrift für Operations Research, 36(1):3–21, 1992.
22.John C Harsanyi. A simplified bargaining model for the n-person cooperative game. International Economic Review, 4(2):194–220, 1963.
23.Joseph D Janizek, Pascal Sturmfels, and Su-In Lee. Explaining explanations: Axiomatic feature interactions for deep networks. Journal of Machine Learning Research, 22(104):1–54, 2021.
24.Ruoxi Jia, David Dao, Boxin Wang, Frances Ann Hubis, Nick Hynes, Nezihe Merve Gürel, Bo Li, Ce Zhang, Dawn Song, and Costas J Spanos. Towards efficient data valuation based on the shapley value. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 1167–1176. PMLR, 2019.
25.Himabindu Lakkaraju, Ece Kamar, Rich Caruana, and Jure Leskovec. Faithful and customizable explanations of black box models. In Proceedings of the 2019 AAAI/ACM Conference on AI, Ethics, and Society, pages 131–138, 2019.
26.Richard Harold Lindeman. Introduction to bivariate and multivariate analysis. Scott Foresman & Co, 1980.
27.Scott M Lundberg and Su-In Lee. A unified approach to interpreting model predictions. In Advances in Neural Information Processing Systems, pages 4765–4774, 2017.
28.Scott M Lundberg, Gabriel Erion, Hugh Chen, Alex DeGrave, Jordan M Prutkin, Bala Nair, Ronit Katz, Jonathan Himmelfarb, Nisha Bansal, and Su-In Lee. From local explanations to global understanding with explainable ai for trees. Nature machine intelligence, 2(1):56–67, 2020.
29.Andrew L Maas, Raymond E Daly, Peter T Pham, Dan Huang, Andrew Y Ng, and Christopher Potts. Learning word vectors for sentiment analysis. In Proceedings of the 49th annual meeting of the association for computational linguistics: Human language technologies-volume 1, pages 142–150. Association for Computational Linguistics, 2011.
30.Jean-Luc Marichal and Pierre Mathonet. Weighted banzhaf power and interaction indexes through weighted approximations of games. European journal of operational research, 211(2):352–358, 2011.
31.Jean-Luc Marichal and Marc Roubens. The chaining interaction index among players in cooperative games. In Advances in Decision Analysis, pages 69–85. Springer, 1999.
32.Tsang Michael, Cheng Dehua, Liu Hanpeng, Feng Xue, Zhou Eric, and Yan Liu. Extracting and leveraging feature interaction interpretations. In International Conference on Learning Representations, 2020.
33.Rory Mitchell, Joshua Cooper, Eibe Frank, and Geoffrey Holmes. Sampling permutations for shapley value estimation. Journal of Machine Learning Research, 23(43):1–46, 2022.
34.Sérgio Moro, Paulo Cortez, and Paulo Rita. A data-driven approach to predict the success of bank telemarketing. Decision Support Systems, 62:22–31, 2014.
35.John F Nash Jr. The bargaining problem. Econometrica: Journal of the econometric society, pages 155–162, 1950.
36.Art B Owen. Sobol’indices and shapley value. SIAM/ASA Journal on Uncertainty Quantification, 2(1):245–251, 2014.
37.Art B Owen and Clémentine Prieur. On shapley value for measuring importance of dependent inputs. SIAM/ASA Journal on Uncertainty Quantification, 5(1):986–1002, 2017.
38.Guillermo Owen. Multilinear extensions of games. Management Science, 18(5-part-2):64–79, 1972.
39.Gregory Plumb, Denali Molitor, and Ameet S Talwalkar. Model agnostic supervised local explanations. In Advances in Neural Information Processing Systems, pages 2515–2524, 2018.
40.Marco Tulio Ribeiro, Sameer Singh, and Carlos Guestrin. Why should i trust you?: Explaining the predictions of any classifier. In Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining, pages 1135–1144. ACM, 2016.
41.Marco Tulio Ribeiro, Sameer Singh, and Carlos Guestrin. Anchors: High-precision model-agnostic explanations. In Thirty-Second AAAI Conference on Artificial Intelligence, 2018.
42.Luis M Ruiz, Federico Valenciano, and Jose M Zarzuelo. The least square prenucleolus and the least square nucleolus. two values for tu games based on the excess vector. International Journal of Game Theory, 25(1):113–134, 1996.
43.Luis M Ruiz, Federico Valenciano, and Jose M Zarzuelo. The family of least square values for transferable utility games. Games and Economic Behavior, 24(1-2):109–130, 1998.
44.David Schmeidler. The nucleolus of a characteristic function game. SIAM Journal on applied mathematics, 17(6):1163–1170, 1969.
45.Lloyd S Shapley. A value for n-person games. Contributions to the Theory of Games, 2(28):307–317, 1953.
46.Chandan Singh, W James Murdoch, and Bin Yu. Hierarchical interpretations for neural network predictions. arXiv preprint arXiv:1806.05337, 2018.
47.Mukund Sundararajan and Amir Najmi. The many shapley values for model explanation. arXiv preprint arXiv:1908.08474, 2019.
48.Mukund Sundararajan, Kedar Dhamdhere, and Ashish Agarwal. The shapley taylor interaction index. In International Conference on Machine Learning, pages 9259–9268. PMLR, 2020.
49.Michael Tsang, Dehua Cheng, and Yan Liu. Detecting statistical interactions from neural network weights. arXiv preprint arXiv:1705.04977, 2017.
50.Michael Tsang, Hanpeng Liu, Sanjay Purushotham, Pavankumar Murali, and Yan Liu. Neural interaction transparency (nit): Disentangling learned interactions for improved interpretability. Advances in Neural Information Processing Systems, 31:5804–5813, 2018.
51.Michael Tsang, Sirisha Rambhatla, and Yan Liu. How does this interaction affect me? interpretable attribution for feature interactions. arXiv preprint arXiv:2006.10965, 2020.
52.Xi Ye, Rohan Nair, and Greg Durrett. Connecting attributions and qa model behavior on realistic counterfactuals. arXiv preprint arXiv:2104.04515, 2021.
53.Chih-Kuan Yeh, Been Kim, Sercan Arik, Chun-Liang Li, Tomas Pfister, and Pradeep Ravikumar. On completeness-aware concept-based explanations in deep neural networks. Advances in Neural Information Processing Systems, 33, 2020.

Citation

MLA

Tsai, C.-P., et al. “Faith-Shap: The Faithful Shapley Interaction Index”. Journal of Machine Learning Research, vol. 24, no. 94, 2023, pp. 1–2, https://www.jmlr.org/papers/v24/22-0202.html.

APA

Tsai, C.-P., Yeh, C.-K., & Ravikumar, P. (2023). Faith-Shap: The Faithful Shapley Interaction Index. Journal of Machine Learning Research, 24(94), 1–42. https://www.jmlr.org/papers/v24/22-0202.html

Chicago

Tsai, C.-P., C.-K. Yeh, and P. Ravikumar. 2023. “Faith-Shap: The Faithful Shapley Interaction Index”. Journal of Machine Learning Research 24 (94): 1–42. https://www.jmlr.org/papers/v24/22-0202.html.

Harvard

Tsai, C.-P., Yeh, C.-K. and Ravikumar, P. (2023) “Faith-Shap: The Faithful Shapley Interaction Index”, Journal of Machine Learning Research, 24(94), pp. 1–42. Available at: https://www.jmlr.org/papers/v24/22-0202.html.

Vancouver

1. Tsai C-P, Yeh C-K, Ravikumar P (2023) Faith-Shap: The Faithful Shapley Interaction Index. Journal of Machine Learning Research 24:1–42

BibTeX

@article{JMLR:v24:22-0202,
  author  = {Che-Ping Tsai and Chih-Kuan Yeh and Pradeep Ravikumar},
  title   = {Faith-Shap: The Faithful Shapley Interaction Index},
  journal = {Journal of Machine Learning Research},
  year    = {2023},
  volume  = {24},
  number  = {94},
  pages   = {1--42},
  url     = {http://jmlr.org/papers/v24/22-0202.html}
}

Metadata:DOI registry

Source Code

This paper has an official code repository available. Click below to access the source code.

View Repository

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

License: https://creativecommons.org/licenses/by/4.0/

Faith-Shap: The Faithful Shapley Interaction Index

Abstract

Keywords

Table of Contents

Knowls

Knowl 1 — Faithfulness as weighted polynomial approximation

Knowl 2 — Axiomatic structure of Faith-Interaction indices

Knowl 3 — Unique Faith-Shap interaction index

Knowl 4 — Faith-Banzhaf as the generalized-2-efficient alternative

Knowl 5 — Top-order Faith-Shap is a cardinal-probabilistic and beta-path index

Knowl 6 — Sampling and computation of Faith-Shap

Knowl 7 — Faith-Shap captures both diminishing and increasing returns

Knowl 8 — Faith-Shap requires fewer model evaluations in estimation experiments

Knowl 9 — Faith-Shap exposes meaningful language interactions

Knowl 10 — Scope and unresolved computational limitation

References

Citation

BibTeX

Source Code

Access the Paper