Many machine learning problems require performing dataset valuation, i.e. to
quantify the incremental gain, to some relevant pre-defined utility, of
aggregating an individual dataset to others. As seminal examples, dataset
valuation has been leveraged in collaborative and federated learning to create
incentives for data sharing across several data owners. The Shapley value has
recently been proposed as a principled tool to achieve this goal due to formal
axiomatic justification. Since its computation often requires exponential time,
standard approximation strategies based on Monte Carlo integration have been
considered. 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 of the Shapley value, referred to as discrete
uniform Shapley (DU-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 show that DU-Shapley tends towards the Shapley value
when the number of data owners is large. The benefits of the proposed framework
are finally illustrated on several dataset valuation benchmarks. DU-Shapley
outperforms other Shapley value approximations, even when the number of data
owners is small.

本文提出了一种基于离散均匀分布的 Shapley 值近似估计方法，以更高效地进行数据集估价和数据共享，并通过多个数据集估价基准测试表明 DU-Shapley 的效果优于其他 Shapley 估算方法。