Dynamic Shapley Value Computation
Dynamic Shapley Value Computation
复制标题
DOI：
10.1109/icde55515.2023.00055
复制
发表时间：
2023-04
期刊：
影响因子：
--
通讯作者：
Jiayao Zhang;Haocheng Xia;Qiheng Sun;Jinfei Liu;Li Xiong;Jian Pei;Kui Ren
中科院分区：
文献类型：
--
作者：
Jiayao Zhang;Haocheng Xia;Qiheng Sun;Jinfei Liu;Li Xiong;Jian Pei;Kui Ren
随着数据驱动研究的盛行，数据评估引起了计算机科学领域的关注。如何评估单个数据成为一个紧迫的问题，特别是在机器学习的背景下。 Shapley 值被广泛用于公平地衡量机器学习中数据点的贡献，因为它是满足所有四个所需属性的独特定义：平衡、对称性、可加性和零元素。然而，众所周知，计算 Shapley 值是一个#P 难题。由于数据会发生变化，动态数据在现实场景中普遍存在。由于从头开始重新计算的成本极其昂贵，因此对此类动态数据进行定价更具挑战性。在本文中，我们研究动态Shapley值计算问题，该问题在动态添加/删除数据点时更新Shapley值。为了添加数据点，为了修剪重叠模型实用程序的不必要的计算，我们提出了基于枢轴的算法，该算法通常可以减少一半的计算时间。我们还提出了基于增量的算法来捕获 Shapley 值变化，这需要较小的样本量才能收敛。为了删除数据点，我们提出了 YN-NN 算法，该算法以有效的方式从预计算模型实用程序的数据结构中导出新的 Shapley 值。基于 Shapley 值的变化，我们给出了另一个版本的基于 Delta 的数据点删除算法。此外，我们提出启发式算法来利用实验观察来添加和删除数据点。大量的实验结果证明了我们提出的算法的效率和有效性。
With the prevalence of data-driven research, data valuation has attracted attention from the computer science field. How to appraise a single datum becomes an imperative problem, especially in the context of machine learning. Shapley value is widely used to fairly measure the contribution of data points in machine learning since it is the unique definition that satisfies all four desired properties: balance, symmetry, additivity, and zero element. However, computing Shapley value is known to be a #P-hard problem. As data is subject to changes, dynamic data exists pervasively in real-world scenarios. Pricing such dynamic data is more challenging due to the prohibitively expensive cost of recalculation from scratch. In this paper, we study the problem of Dynamic Shapley Value Computation, which updates Shapley value when dynamically adding/deleting data points. For adding data points, to prune unnecessary computation of overlapping model utilities, we propose the pivot-based algorithm that can reduce half computation time in general. We also propose the delta-based algorithm to capture Shapley value changes, which requires a smaller sample size to converge. For deleting data points, we present the YN-NN algorithm that derives the new Shapley value from the data structure of precomputed model utilities in an efficient way. Based on Shapley value changes, we give another version of the delta-based algorithm for deleting data points. Besides, we propose heuristic algorithms to draw on experimental observations for both adding and deleting data points. Extensive experimental results demonstrate the efficiency and effectiveness of our proposed algorithms.