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

• From Abstract to Actionable: Pairwise Shapley Values for Explainable AI [0.8192907805418583]
  We propose Pairwise Shapley Values, a novel framework that grounds feature attributions in explicit, human-relatable comparisons. Our method introduces pairwise reference selection combined with single-value imputation to deliver intuitive, model-agnostic explanations. We demonstrate that Pairwise Shapley Values enhance interpretability across diverse regression and classification scenarios.
  arXiv  Detail & Related papers  (2025-02-18T04:20:18Z)
• Shapley Value Approximation Based on k-Additive Games [21.023521613326654]
  The Shapley value is the prevalent solution for fair division problems in which a payout is to be divided among multiple agents. Despite its popularity and axiomatic justification, the Shapley value suffers from a computational complexity that scales exponentially with the number of entities involved. We propose SVA$k_textADD$, a novel approximation method that fits a $k$-additive surrogate game.
  arXiv  Detail & Related papers  (2025-02-07T08:52:57Z)
• Statistical Inference for Temporal Difference Learning with Linear Function Approximation [62.69448336714418]
  We study the consistency properties of TD learning with Polyak-Ruppert averaging and linear function approximation. First, we derive a novel high-dimensional probability convergence guarantee that depends explicitly on the variance and holds under weak conditions. We further establish refined high-dimensional Berry-Esseen bounds over the class of convex sets that guarantee faster rates than those in the literature.
  arXiv  Detail & Related papers  (2024-10-21T15:34:44Z)
• 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)
• 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)

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.