Data valuation has found various applications in machine learning, such as data filtering, efficient learning and incentives for data sharing. The most popular current approach to data valuation is the Shapley value. While popular for its various applications, Shapley value is computationally expensive even to approximate, as it requires repeated iterations of training models on different subsets of data. In this paper we show that the Shapley value of data points can be approximated more efficiently by leveraging the structural properties of machine learning problems. We derive convergence guarantees on the accuracy of the approximate Shapley value for different learning settings including Stochastic Gradient Descent with convex and non-convex loss functions. Our analysis suggests that in fact models trained on small subsets are more important in the context of data valuation. Based on this idea, we describe $\delta$-Shapley -- a strategy of only using small subsets for the approximation. Experiments show that this approach preserves approximate value and rank of data, while achieving speedup of up to 9.9x. In pre-trained networks the approach is found to bring more efficiency in terms of accurate evaluation using small subsets.

通过利用机器学习问题的结构性质，我们提出了一种更高效的近似数据Shapley值的方法，此方法在不同学习设置中包括随机梯度下降和凸、非凸损失函数中证明了其近似Shapley值的准确性收敛性。实验证明，这种方法在保持数据的近似价值和排名的同时，提高了近似速度最高可达9.9倍，并且在使用小的子集进行精确评估时，对预训练网络的效率更高。

数据评估的加速Shapley值近似算法