Approximating the Shapley Value without Marginal Contributions
- URL: http://arxiv.org/abs/2302.00736v5
- Date: Tue, 30 Jan 2024 10:34:35 GMT
- Title: Approximating the Shapley Value without Marginal Contributions
- Authors: Patrick Kolpaczki, Viktor Bengs, Maximilian Muschalik, Eyke
H\"ullermeier
- Abstract summary: The Shapley value, which is arguably the most popular approach for assigning a meaningful contribution value to players in a cooperative game, has recently been used intensively in explainable artificial intelligence.
We propose two parameter-free and domain-independent approximation algorithms based on a representation of the Shapley value detached from the notion of marginal contribution.
- Score: 11.539320505465149
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The Shapley value, which is arguably the most popular approach for assigning
a meaningful contribution value to players in a cooperative game, has recently
been used intensively in explainable artificial intelligence. Its
meaningfulness is due to axiomatic properties that only the Shapley value
satisfies, which, however, comes at the expense of an exact computation growing
exponentially with the number of agents. Accordingly, a number of works are
devoted to the efficient approximation of the Shapley value, most of them
revolve around the notion of an agent's marginal contribution. In this paper,
we propose with SVARM and Stratified SVARM two parameter-free and
domain-independent approximation algorithms based on a representation of the
Shapley value detached from the notion of marginal contribution. We prove
unmatched theoretical guarantees regarding their approximation quality and
provide empirical results including synthetic games as well as common
explainability use cases comparing ourselves with state-of-the-art methods.
Related papers
- Fast Shapley Value Estimation: A Unified Approach [71.92014859992263]
We propose a straightforward and efficient Shapley estimator, SimSHAP, by eliminating redundant techniques.
In our analysis of existing approaches, we observe that estimators can be unified as a linear transformation of randomly summed values from feature subsets.
Our experiments validate the effectiveness of our SimSHAP, which significantly accelerates the computation of accurate Shapley values.
arXiv Detail & Related papers (2023-11-02T06:09:24Z) - DU-Shapley: A Shapley Value Proxy for Efficient Dataset Valuation [23.646508094051768]
We consider the dataset valuation problem, that is, the problem of quantifying the incremental gain.
The Shapley value is a natural tool to perform dataset valuation due to its formal axiomatic justification.
We propose a novel approximation, referred to as discrete uniform Shapley, which is expressed as an expectation under a discrete uniform distribution.
arXiv Detail & Related papers (2023-06-03T10:22:50Z) - Efficient Shapley Values Estimation by Amortization for Text
Classification [66.7725354593271]
We develop an amortized model that directly predicts each input feature's Shapley Value without additional model evaluations.
Experimental results on two text classification datasets demonstrate that our amortized model estimates Shapley Values accurately with up to 60 times speedup.
arXiv Detail & Related papers (2023-05-31T16:19:13Z) - A $k$-additive Choquet integral-based approach to approximate the SHAP
values for local interpretability in machine learning [8.637110868126546]
This paper aims at providing some interpretability for machine learning models based on Shapley values.
A SHAP-based method called Kernel SHAP adopts an efficient strategy that approximates such values with less computational effort.
The obtained results attest that our proposal needs less computations on coalitions of attributes to approximate the SHAP values.
arXiv Detail & Related papers (2022-11-03T22:34:50Z) - SHAP-XRT: The Shapley Value Meets Conditional Independence Testing [21.794110108580746]
We show that Shapley-based explanation methods and conditional independence testing are closely related.
We introduce the SHAPley EXplanation Randomization Test (SHAP-XRT), a testing procedure inspired by the Conditional Randomization Test (CRT) for a specific notion of local (i.e., on a sample) conditional independence.
We show that the Shapley value itself provides an upper bound to the expected $p$-value of a global (i.e., overall) null hypothesis.
arXiv Detail & Related papers (2022-07-14T16:28:54Z) - Accelerating Shapley Explanation via Contributive Cooperator Selection [42.11059072201565]
We propose a novel method SHEAR to significantly accelerate the Shapley explanation for DNN models.
The selection of the feature coalitions follows our proposed Shapley chain rule to minimize the absolute error from the ground-truth Shapley values.
SHEAR consistently outperforms state-of-the-art baseline methods across different evaluation metrics.
arXiv Detail & Related papers (2022-06-17T03:24:45Z) - A Unified Framework for Multi-distribution Density Ratio Estimation [101.67420298343512]
Binary density ratio estimation (DRE) provides the foundation for many state-of-the-art machine learning algorithms.
We develop a general framework from the perspective of Bregman minimization divergence.
We show that our framework leads to methods that strictly generalize their counterparts in binary DRE.
arXiv Detail & Related papers (2021-12-07T01:23:20Z) - Collective eXplainable AI: Explaining Cooperative Strategies and Agent
Contribution in Multiagent Reinforcement Learning with Shapley Values [68.8204255655161]
This study proposes a novel approach to explain cooperative strategies in multiagent RL using Shapley values.
Results could have implications for non-discriminatory decision making, ethical and responsible AI-derived decisions or policy making under fairness constraints.
arXiv Detail & Related papers (2021-10-04T10:28:57Z) - $\gamma$-ABC: Outlier-Robust Approximate Bayesian Computation Based on a
Robust Divergence Estimator [95.71091446753414]
We propose to use a nearest-neighbor-based $gamma$-divergence estimator as a data discrepancy measure.
Our method achieves significantly higher robustness than existing discrepancy measures.
arXiv Detail & Related papers (2020-06-13T06:09:27Z) - Projection Robust Wasserstein Distance and Riemannian Optimization [107.93250306339694]
We show that projection robustly solidstein (PRW) is a robust variant of Wasserstein projection (WPP)
This paper provides a first step into the computation of the PRW distance and provides the links between their theory and experiments on and real data.
arXiv Detail & Related papers (2020-06-12T20:40:22Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.