【论文阅读：基于夏普利值的高效数据估值

基于Shapley值的高校数据价值评估

主要贡献

• 提出了一系列用于近似计算Shapley值的高效算法。
• 设计了一个算法，通过实现不同模型评估之间的适当信息共享来实现这一目标,该算法具有可证明的误差保证来近似N个数据点的SV，其模型评估数量为$O(\sqrt{N}log(N{)}^2)$
  • 这个算法依赖于学习算法的稳定性，对于复杂的ML模型，如深度神经网络，这很难证明。
• 此外，如果合理假设SV在“稀疏”的意义上仅有少数数据点具有显著值，那么我们可以进一步将模型训练数量减少到$O(loglog(N))$
  • 在第二个算法中，不得不做出的妥协是，所得到的SV估计不再具有关于近似误差的可证保证。
• 值得注意的是，这两个算法对计算SV的上下文是不可知的；因此，它们在数据估值之外的应用中也是有用的。

1.Introduction

处理数据估值问题的一种自然方法是采用博弈论的观点，其中将每个数据贡献者建模为合作博弈中的玩家，并通过效用函数来表征来自任何贡献者子集的数据的有用性。
Shapley值（SV）是合作博弈理论中的经典方法，用于分配所有玩家联盟生成的总收益，并已应用于各个领域的问题。
SV定义了一个独特的利润分配方案，满足一系列具有吸引力的现实世界解释的属性，如公平性、合理性和去中心化性。精确计算SV所需的效用函数评估次数随着参与者数量呈指数增长。

2. 相关工作

3.问题的表述

考虑一个包含来自N个用户的数据的数据集 D = { z i } i = 1 N D=\{z_i\}^N_{i=1} D={zi​}i=1N​
用$U(S)$表示效能（价值）函数，表示通过对 { Z i } i ∈ S \{Z_i\}_i\in S {Zi​}i​∈S的加法聚合计算出的总价值，其中 S ⊆ I = { 1 , . . . , N } S\subseteq I=\{1,...,N\} S⊆I={1,...,N}.
假设U(∅) = 0
我们的目标是分配$U_{tot}$分配给各个用户。
我们想要找到一个效能函数U，将$s(U,i)$分配给用户。

Shapley值（SV）是合作博弈论中的一个经典概念，用于将所有玩家联盟产生的总收益归因于各个玩家。给定效用函数U(·)，用户i的SV被定义为$z_i$对由其他用户组成的数据集 D = { z i } i ∈ I D = \{z_i\}_{i∈I} D={zi​}i∈I​的所有可能子集的平均边际贡献：
s i = ∑ S ⊆ I { i } 1 N ( N − 1 ∣ S ∣ ) [ U ( S ∪ { i } − U ( S ) ] ( 1 ) s_i=\sum_{S\subseteq I\{i \}} \frac{1}{N\bigl( \begin{smallmatrix} N-1\\ |S| \end{smallmatrix} \bigr)}[U(S\cup\{i\}-U(S)] \qquad(1) si​=S⊆I{i}∑​N(N−1∣S∣​)1​[U(S∪{i}−U(S)](1)

等价于：
s i = 1 N ! ∑ π ∈ Π ( D ) [ U ( P i π ∪ { i } ) − U ( P i π ) ] s_i = \frac{1}{N!} \sum_{\pi \in \Pi(D)} \left[ U(P^{\pi}_i \cup \{i\}) - U(P^{\pi}_i) \right] si​=N!1​∑π∈Π(D)​[U(Piπ​∪{i})−U(Piπ​)]

在这里，$\pi \in \Pi (D)$ 是用户的一个排列，$P_{{\pi }_i}$ 是排列 $\pi$ 中排在用户 $i$ 前面的用户集合。直观地说，想象一下所有用户的数据按随机顺序被收集，每个用户 $i$ 得到的是他的数据对已经收集到数据的用户带来的边际贡献。如果我们将这些贡献在所有可能的用户顺序上平均，就得到了 $s_i$。Shapley值的重要性在于它是唯一的价值分配方案，满足以下可取性质:
以下是用LaTeX表示的上述性质：

1. Group Rationality:
   $U(I)={\sum }_{i\in I}{s}_i$
2. Fairness(公平性):
   • (1) 对于相同贡献的两个用户，它们应具有相同的价值。
     若 U ( S ∪ { i } ) = U ( S ∪ { j } ) , ∀ S ⊆ I ∖ { i , j } , U(S \cup \{i\}) = U(S \cup \{j\}), \forall S \subseteq I \setminus \{i, j\}, U(S∪{i})=U(S∪{j}),∀S⊆I∖{i,j},则 $s_i=s_j$
   • (2) 对于对数据集的所有子集都没有边际贡献的用户，其价值为零。若 U ( S ∪ { i } ) = 0 U(S \cup \{i\}) = 0 U(S∪{i})=0, 对于所有 S ⊆ I ∖ { i } S \subseteq I \setminus \{i\} S⊆I∖{i}, 则$s_i=0$
3. Additivity(可加性)
   $s(U,i)+s(V,i)=s(U+V,i),\text{ 对于 }i\in I$

4. 高效的Shapley值估计

采用Shapley值的挑战在于其计算成本。使用公式（1）评估准确的Shapley值涉及计算每个用户对每个联盟的边际效用，其时间复杂度为O(2^N)。
在本文中将以$l_2$范数来衡量近似误差。$\hat{s}\in {\mathbb{R}}^N$ 是真实Shapley值 $s=[s_1,\dots ,s_N{]}^T\in {\mathbb{R}}^N$ 的$(ϵ,\delta )$-近似，即满足 $P[||{\hat{s}}_i-s_i|$