基于Shapley值的高校数据价值评估
主要贡献
- 提出了一系列用于近似计算Shapley值的高效算法。
- 设计了一个算法,通过实现不同模型评估之间的适当信息共享来实现这一目标,该算法具有可证明的误差保证来近似N个数据点的SV,其模型评估数量为
O
(
N
l
o
g
(
N
)
2
)
O(\sqrt Nlog(N)^2)
O(Nlog(N)2)
- 这个算法依赖于学习算法的稳定性,对于复杂的ML模型,如深度神经网络,这很难证明。
- 此外,如果合理假设SV在“稀疏”的意义上仅有少数数据点具有显著值,那么我们可以进一步将模型训练数量减少到
O
(
l
o
g
l
o
g
(
N
)
)
O(loglog(N))
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
)
U(S)
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
t
o
t
U_{tot}
Utot分配给各个用户。
我们想要找到一个效能函数U,将
s
(
U
,
i
)
s(U,i)
s(U,i)分配给用户。
Shapley值(SV)是合作博弈论中的一个经典概念,用于将所有玩家联盟产生的总收益归因于各个玩家。给定效用函数U(·),用户i的SV被定义为
z
i
z_i
zi对由其他用户组成的数据集
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π)]
在这里,
π
∈
Π
(
D
)
π ∈ Π(D)
π∈Π(D) 是用户的一个排列,
P
π
i
P_{\pi_i}
Pπi 是排列
π
π
π 中排在用户
i
i
i 前面的用户集合。直观地说,想象一下所有用户的数据按随机顺序被收集,每个用户
i
i
i 得到的是他的数据对已经收集到数据的用户带来的边际贡献。如果我们将这些贡献在所有可能的用户顺序上平均,就得到了
s
i
s_i
si。Shapley值的重要性在于它是唯一的价值分配方案,满足以下可取性质:
以下是用LaTeX表示的上述性质:
- Group Rationality:
U ( I ) = ∑ i ∈ I s i U(I) = \sum_{i \in I} s_i U(I)=∑i∈Isi - 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 s_i = s_j si=sj - (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 s_i = 0 si=0
- (1) 对于相同贡献的两个用户,它们应具有相同的价值。
- Additivity(可加性)
s ( U , i ) + s ( V , i ) = s ( U + V , i ) , 对于 i ∈ I s(U, i) + s(V, i) = s(U + V, i), \text{ 对于 } i \in I s(U,i)+s(V,i)=s(U+V,i), 对于 i∈I
4. 高效的Shapley值估计
采用Shapley值的挑战在于其计算成本。使用公式(1)评估准确的Shapley值涉及计算每个用户对每个联盟的边际效用,其时间复杂度为O(2^N)。
在本文中将以
l
2
l_2
l2范数来衡量近似误差。
s
^
∈
R
N
\hat{s} \in \mathbb{R}^N
s^∈RN 是真实Shapley值
s
=
[
s
1
,
…
,
s
N
]
T
∈
R
N
s = [s_1, \ldots , s_N]^T \in \mathbb{R}^N
s=[s1,…,sN]T∈RN 的
(
ϵ
,
δ
)
(\epsilon, \delta)
(ϵ,δ)-近似,即满足
P
[
∣
∣
s
^
i
−
s
i
∣
∣
p
≤
ϵ
]
≥
1
−
δ
P[||\hat{s}_i - s_i||_p \leq \epsilon] \geq 1 - \delta
P[∣∣s^i−si∣∣p≤ϵ]≥1−δ。
4.1 基准方法:排列抽样
π
\pi
π一个关于
I
I
I的随机排列,每个排列出现的可能均为
1
/
N
!
1/N!
1/N!
ϕ
i
\phi_i
ϕi表示该排列下的边际贡献为
U
(
P
i
π
∪
{
i
}
)
−
U
(
P
i
π
)
U(P^{\pi}_i\cup\{i\})-U(P^{\pi}_i)
U(Piπ∪{i})−U(Piπ),根据公式2有
s
i
=
E
[
ϕ
i
]
s_i = \mathbb E[\phi_i]
si=E[ϕi]
根据Hoeffding’s Bound(霍夫丁界)不等式,该公式说明在大量独立观测的情况下,实际观测到的样本均值
S
n
S_n
Sn距离总体均值μ 的偏离(以ϵ 表示)超过一定阈值的概率有一个严格的上限。这个上限随着样本数量n 的增加而指数级下降,表明样本均值会以很高的概率集中在总体均值附近。
P
(
∣
S
n
−
μ
∣
≥
ϵ
)
≤
2
exp
(
−
2
n
ϵ
2
∑
i
=
1
n
(
b
i
−
a
i
)
2
)
P\left(\left|S_n - \mu\right| \geq \epsilon\right) \leq 2 \exp\left(-\frac{2n\epsilon^2}{\sum_{i=1}^{n}(b_i - a_i)^2}\right)
P(∣Sn−μ∣≥ϵ)≤2exp(−∑i=1n(bi−ai)22nϵ2)
Hoeffding不等式的一个应用指出,在达到一个(ε, δ)近似解时所需排列的数量
m
p
e
r
m
m_{perm}
mperm可以通过以下公式计算得出:
m
perm
=
(
2
r
2
N
ε
2
)
log
(
2
N
δ
)
m_{\text{perm}} = \left(\frac{2r^2N}{\varepsilon^2}\right) \log\left(\frac{2N}{\delta}\right)
mperm=(ε22r2N)log(δ2N)
- m p e r m m_{perm} mperm 表示所需的排列次数。
- ε 是设定的近似误差值。
- δ \delta δ 是允许的失败概率(置信水平)。
- N 是被排列的数据集或总体的大小。
- r 表示效用函数的取值范围,即效用函数在所有可能输入上最大值与最小值之差。
因为我们需要计算出N个用户的边际效应,所以我们可以将其表示为:
m
e
v
a
l
=
N
×
m
p
e
r
m
m_{eval}=N\times m_{perm}
meval=N×mperm
简化后用大O记法为:
m
e
v
a
l
=
O
(
N
2
l
o
g
N
)
m_{eval}=O(N^2logN)
meval=O(N2logN)
在机器学习任务中,我们可以将效用函数写作
U
(
S
)
=
U
m
(
A
(
S
)
)
U(S)=U_m(A(S))
U(S)=Um(A(S)),其中A(⋅) 是一个映射数据集
S 到模型的学习算法,而
U
m
(
⋅
)
U_m(⋅)
Um(⋅)是衡量模型性能的一些指标,比如测试准确率。通常情况下,与效用评估相关的大部分计算成本在于执行 A(⋅),即训练模型的过程。
在这种情况下,针对每一个排列,仅需对包含所有N 个用户的训练集进行一次完整的遍历(一次训练过程),就能通过增删单个用户的数据逐步得到每个用户i 对于最终模型性能的影响,即其边际贡献
ϕ
i
\phi_i
ϕi,也就是说一次训练可以得到N个用户的边际贡献。
所以在具备增量训练特性的模型训练算法下,要达到一个近似解所需要的模型训练次数实际上就等于
m
p
e
r
m
m_{perm}
mperm:
m
m
o
d
e
l
_
t
r
a
i
n
=
m
p
e
r
m
=
O
(
N
l
o
g
N
)
m_{model\_train}=m_{perm}=O(NlogN)
mmodel_train=mperm=O(NlogN)
这意味着即使在处理大规模数据集时,通过增量训练的方式,我们也能在一定程度上减少模型训练的迭代次数,从而优化算法的整体效率。
4.2 群组检测方法
这种群组检测(Group Testing)方法通常涉及将多个个体(例如用户或数据点)分组成群组,然后同时对整个群组进行效用评估,而不是单独评估每个个体。这样做的好处在于,通过合并处理信息,可以在某些条件下大幅降低评估次数。
目标是通过尽可能少的测试,来评估所有用户子集的效用。这可以有效地减少计算成本。
假设共有T次测试,在第t次测试时,从用户集合
I
I
I中随机抽取一组用户,并对所选用户集合的效能进行评估。对于用户i和用户j的测试中的表现用布尔随机变量
β
i
\beta_i
βi和
β
j
\beta_j
βj来表示,所以用户i和j的效能之差如下:
(
β
i
−
β
j
)
U
(
β
1
,
.
.
.
,
β
N
)
(\beta_i-\beta_j)U(\beta_1,...,\beta_N)
(βi−βj)U(β1,...,βN)
U
(
β
1
,
.
.
.
,
β
N
)
U(\beta_1,...,\beta_N)
U(β1,...,βN)是在那些布尔出现随机变量为1的用户上评估出的整体效用函数值。
引理1:对于任意
i
,
j
∈
I
i, j \in I
i,j∈I,两者之间的SV差异为(这是作者推导出来的):
s
i
−
s
j
=
1
N
−
1
∑
S
⊆
I
∖
{
i
,
j
}
U
(
S
∪
{
i
}
)
−
U
(
S
∪
{
j
}
)
(
N
−
2
∣
S
∣
)
s_i - s_j = \frac{1}{N-1} \sum_{S \subseteq I \setminus \{i,j\}} \frac {U(S \cup \{i\}) - U(S \cup \{j\})}{\dbinom{N-2}{|S|}}
si−sj=N−11S⊆I∖{i,j}∑(∣S∣N−2)U(S∪{i})−U(S∪{j})
引理2:假设
C
i
j
C_{ij}
Cij是一个对于
s
i
−
s
j
s_i - s_j
si−sj的
(
ε
/
(
2
N
)
,
δ
/
(
N
(
N
−
1
)
)
)
分布的近似
(\varepsilon/(2\sqrt N),\delta/(N(N-1)))分布的近似
(ε/(2N),δ/(N(N−1)))分布的近似
∑
i
=
1
N
s
^
i
=
U
tot
(
5
)
∣
(
s
^
i
−
s
^
j
)
−
C
i
j
∣
≤
ε
2
N
∀
i
,
j
∈
{
1
,
…
,
N
}
(
6
)
\sum_{i=1}^{N} \hat{s}_i = U_{\text{tot}} \quad (5) \newline \left| (\hat{s}_i - \hat{s}_j) - C_{ij} \right| \leq \frac{\varepsilon}{2\sqrt{N}} \quad \forall i, j \in \{1, \ldots, N\} \quad (6)
i=1∑Ns^i=Utot(5)∣(s^i−s^j)−Cij∣≤2Nε∀i,j∈{1,…,N}(6)
引理3:说明了在给定一定的测试数量的情况下,Algorithm 1可以提供对Shapley值(SV)的近似。这个近似是相对于l2-范数的,而且具有一定的误差限制(ε, δ)。换句话说,如果我们有足够数量的测试,并且满足了定理中的条件,那么我们可以使用Algorithm 1来近似计算SV,并且这个近似是有一定保证的。
4.3算法解读
4.3.1 Group Testing Based SV Estimation(GTB-Shapley)
- 输入
- N个参与方的数据集D
- 效用评估函数U(·)
- 测试的轮数T
- 输出
- 每个参与方的估计SV
- 初始化
- 首先计算Z和q(k),其中Z是一个常数,q(k)是一个与k有关的权重。
- 初始化 β t i \beta_{ti} βti为0
- 测试过程
- 循环迭代T次
- 首先,从权重q(k)中随机选择一个值k,表示这一轮测试中将从样本中选择k个点进行测试。
- 接着,对于每个选定的测试集,通过均匀抽样从{1, …, N}中选择k个点,将这些点作为测试集。
- 对于每个测试集,计算其效用 u t = U ( i : β t i = 1 ) u_t = U({i : β_{ti} = 1}) ut=U(i:βti=1),即测试集中被标记为1的点的效用之和。
- SV差异计算:通过测试集的效用,计算每对样本之间的SV差异 ∆ U i j ∆U_{ij} ∆Uij
- 解决可行性问题:通过解决一个可行性问题,找到一个解 s ^ \hat s s^,使得其满足约束条件,其中约束条件要求每对样本之间的SV差异与估计值的差异不超过一定阈值。
- 输出结果:输出估计的SV值 s ^ \hat s s^。
- 循环迭代T次
4.3.2 Compressive Permutation Sampling(压缩置换采样)
这个算法需要一定的前置知识,看不懂的朋友可以先了解一下Permutation Test
- 输入
- N个参与方的数据集D
- 效用评估函数U(·)
- 测量数量M
- 置换数量T
- 输出
- 每个参与方的估计SV
- 初始化
- :算法首先通过Bernoulli矩阵A进行随机抽样,其中 A m , i ∈ { − 1 / M , 1 / M } A_{m,i} ∈ \{-1/\sqrt M, 1/\sqrt M\} Am,i∈{−1/M,1/M},这个过程用于压缩数据,减少测量数量。
- 循环过程
- 对于N个参与方生成一个随机序列 π t \pi_t πt
- 置换过程:对于每个置换 π t π_t πt,算法计算每个样本点的置换效用差异 ϕ i t \phi^t_i ϕit。
- 测量过程:对于每个置换,算法根据压缩矩阵A对置换效用差异进行测量,得到 y ^ m , t \hat y_{m,t} y^m,t
- 收尾阶段
- 平均值计算:算法计算每个测量的平均值,得到 y ‾ m \overline y_m ym
- 约束问题求解:算法解决一个约束最小化问题,寻找一个Δs,使得在满足约束条件的情况下, A ( s ‾ + Δ s ) A(\overline s + Δs) A(s+Δs)与 y ‾ \overline y y的二范数误差最小化。
- 输出结果:输出估计的SV值 s ^ \hat s s^。