Variance reduced Shapley value estimation for trustworthy data valuation

DOI10.1016/J.COR.2023.106305MaRDI QIDQ6047839zbMATH OpenFDO

Authors

Publication date 13 September 2023

Published in Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2210.16835

zbMATH Keywords

data Shapleydata valuationmachine learningstratified samplingvariance reduction

Mathematics Subject Classification ID

Statistics (62-XX) Game theory, economics, finance, and other social and behavioral sciences (91-XX)

Abstract: Data valuation, especially quantifying data value in algorithmic prediction and decision-making, is a fundamental problem in data trading scenarios. The most widely used method is to define the data Shapley and approximate it by means of the permutation sampling algorithm. To make up for the large estimation variance of the permutation sampling that hinders the development of the data marketplace, we propose a more robust data valuation method using stratified sampling, named variance reduced data Shapley (VRDS for short). We theoretically show how to stratify, how many samples are taken at each stratum, and the sample complexity analysis of VRDS. Finally, the effectiveness of VRDS is illustrated in different types of datasets and data removal applications.

Recommendations

• Establishing the price of privacy in federated data trading
• A comparative study of methods for estimating model-agnostic Shapley value explanations
• A theory of dichotomous valuation with applications to variable selection
• Explaining individual predictions when features are dependent: more accurate approximations to Shapley values
• On Shapley Value for Measuring Importance of Dependent Inputs

Cites work

• 10.1162/153244302760200704
• A theory of pricing private data
• An efficient explanation of individual classifications using game theory
• Basics and Trends in Sensitivity Analysis
• Breast Cancer Diagnosis and Prognosis Via Linear Programming
• Feature Selection via Coalitional Game Theory
• scientific article; zbMATH DE number 3549966 (Why is no real title available?)
• scientific article; zbMATH DE number 3078997 (Why is no real title available?)
• Improving polynomial estimation of the Shapley value by stratified random sampling with optimum allocation
• On Shapley Value for Measuring Importance of Dependent Inputs
• On the Complexity of Cooperative Solution Concepts
• Polynomial calculation of the Shapley value based on sampling
• Shapley Effects for Global Sensitivity Analysis: Theory and Computation
• SHAPLEY EFFECTS FOR SENSITIVITY ANALYSIS WITH CORRELATED INPUTS: COMPARISONS WITH SOBOL' INDICES, NUMERICAL ESTIMATION AND APPLICATIONS
• Sobol' indices and Shapley value
• Variance reduction for estimation of Shapley effects and adaptation to unknown input distribution

Cited in

(1)

• Robust data sampling in machine learning: a game-theoretic framework for training and validation data selection

This page was built for publication: Variance reduced Shapley value estimation for trustworthy data valuation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6047839)