Polynomial calculation of the Shapley value based on sampling

By Javier Castro, D. Gómez, J. Tejada. Computers & Operations Research, 2009

716 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Economics and Econometrics, Management Science and Operations Research

View Paper: https://www.semanticscholar.org/paper/7d22afdac45f7775cee78c89dd4f55f84843fd5a

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 Economics and Econometrics

In Management Science and Operations Research

Citations in the corpus

A Diagnostic Study of Explainability Techniques for Text Classification (2020, methodology): “Another popular perturbation-based technique is the Shapley Value Sampling (Castro et al., 2009).”
Explaining prediction models and individual predictions with feature contributions (2014, methodology): “(10) could be approximated using a simple sampling algorithm, where ( Prei (O)∪{i} − Prei (O) ) would be one sample (see, for example, [7]).”
Data Shapley: Equitable Valuation of Data for Machine Learning (2019, methodology): “…methods, network approximations, as well as analytically solving Shapley value in specialized settings (Fatima et al., 2008; Michalak et al., 2013; Castro et al., 2009a; Maleki et al., 2013; Hamers et al., 2016) In linear regression, Cook’s Distance measures the effect of deleting one point on…”
Game Theory in Wireless and Communication Networks (2008, methodology): “For computing the Shapley value in reasonable time, several analytical techniques have been proposed, such as multi-linear extensions [377] and sampling methods for simple games [92].”
A Marketplace for Data: An Algorithmic Solution (2018, methodology): “We note some similar sampling based methods, albeit for different applications (cf. Mann & Shapley (1952); Castro et al. (2009); Maleki et al. (2013)).”
Explaining Deep Neural Networks and Beyond: A Review of Methods and Applications (2021, methodology): “, the occlusion method [201] and Shapley value resampling [29].”
An Efficient Explanation of Individual Classifications using Game Theory (2010, background): “(7), was presented by Castro et al. (2008). However, in our case, the exponential time complexity is still hidden in our definition of ∆ (see Eq.”
Coalitional game theory for communication networks (2009, neutral): “For computing the Sha pley value in reasonable time, several analytical techniqu es have been proposed such as multi-linear extensions [3], and s mpling methods for simple games [22], among others.”
Toward Interpretable Machine Learning: Transparent Deep Neural Networks and Beyond (2020, methodology): “While the more recent iNNvestigate Toolbox implements a superset of the modiﬁed backpropagation methods available in Deep-Explain, the latter also offers functionalty for perturbation-based attribution methods, i.e. the Occlusion method [159] and Shapley Value Resampling [25].”
Explaining Deep Neural Networks with a Polynomial Time Algorithm for Shapley Values Approximation (2019, methodology): “Some previous works proposed sampling-based methods to approximate Shapley values (Castro et al., 2009; Strumbelj & Kononenko, 2010; Datta et al., 2016).”
Algorithms to estimate Shapley value feature attributions (2022, methodology): “…the original work, other methods have been developed to estimate Shapley value explanations more eﬃciently, using model-agnostic strategies (permutation [30], multilinear extension [31], FastSHAP [32]) and model-speciﬁc strategies (linear models [28], tree models [16], deep models [29, 33, 34]).”