DU-Shapley: A Shapley Value Proxy for Efficient Dataset Valuation

We consider the dataset valuation problem, that is, the problem of quantifying the incremental gain, to some relevant pre-defined utility of a machine learning task, of aggregating an individual dataset to others. The Shapley value is a natural tool to perform dataset valuation due to its formal axi...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2024-11
Main Authors: Garrido-Lucero, Felipe, Heymann, Benjamin, Vono, Maxime, Loiseau, Patrick, Perchet, Vianney
Format: Article
Language:English
Subjects:
Approximation
Asymptotic properties
Datasets
Incentives
Machine learning
Mathematical analysis
Valuation
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We consider the dataset valuation problem, that is, the problem of quantifying the incremental gain, to some relevant pre-defined utility of a machine learning task, of aggregating an individual dataset to others. The Shapley value is a natural tool to perform dataset valuation due to its formal axiomatic justification, which can be combined with Monte Carlo integration to overcome the computational tractability challenges. Such generic approximation methods, however, remain expensive in some cases. In this paper, we exploit the knowledge about the structure of the dataset valuation problem to devise more efficient Shapley value estimators. We propose a novel approximation, referred to as discrete uniform Shapley, which is expressed as an expectation under a discrete uniform distribution with support of reasonable size. We justify the relevancy of the proposed framework via asymptotic and non-asymptotic theoretical guarantees and illustrate its benefits via an extensive set of numerical experiments.
ISSN:2331-8422