Data Shapley Value 笔记

本文为 Data Shapley: Equitable Valuation of Data for Machine Learning 的阅读笔记,涉及论文中的 Data Shapley Value 计算公式、两种实现算法、实验应用部分的梳理。
为理解 Data Shapley Value,本文首先讨论 Shapley Value的相关内容,利用一个具体实例计算 Shapley Value 并讨论其计算公式。而后,解释一脉相承的 Data Shapley Value 计算公式、两种实现算法的伪代码。
欢迎讨论!若有错误,敬请指正!


Shapley Value

Shapley value 的核心思想:在一个合作游戏中,每个玩家的价值可以通过其对所有可能的合作联盟(玩家子集)的贡献平均值来衡量。

Shapley value 的引例 – “哪位程序员的贡献最大”

某公司有三个程序猿,分别是屌丝 A,大佬 B,美女 C。如果大家不合作,A 每个季度可以完成 3 个项目,B 每个季度可以完成 10 个项目,C 每个季度只能完成 1 个项目。但是老板小王为了充分挖掘员工潜力,合理配置公司资源,让 A,B,C 尝试了各种合作模式。

王老板观察发现,屌丝都是潜力股,美女都是催化剂:屌丝 A 和大佬 B 合作每个季度可以完成 15 个项目,合作效果提升还行;屌丝 A 和美女 C 合作每个季度可以完成 50 个项目,合作效果爆炸;大佬 B 和美女 C 合作每个季度仅完成了 12 个项目,看来对大佬来说不影响拔刀的速度就不错了;ABC 一起合作每个季度可以完成 70 个项目。最终王老板拍板让 ABC 以后就一起工作,按照小组完成的项目数额外发放项目奖金。那么,如何根据员工的贡献值来确定哪位员工的奖金最多?

说 A 的同学:明显屌丝是潜力股,虽然单独工作表现一般,但是和美女一起合作,大大激发了工作热情,肯定是 A 贡献最多!说 B 的同学:应该是大佬贡献最大,因为单独来看,大佬本身能力是最强的!说 C 的同学:应该是美女贡献最大,虽然美女单独工作没什么效率,但显然对团队的影响无法替代!

为解决这一问题,我们采用 shapley 值尝试求解这一问题。设想我们以某种顺序将 ABC 放到合作队伍中(合作队伍一开始为空),那么合作的组合会有 3!=6 种,每种组合的概率均为 1/6,各种组合及各员工的贡献如下表所示:

集合序号加入顺序A加入的贡献B加入的贡献C加入的贡献概率
1A+B+C3-0=315-3=1270-15=551/6
2A+C+B3-0=370-50=2050-3=471/6
3B+A+C15-10=510-0=1070-15=551/6
4B+C+A70-12=5810-0=1012-10=21/6
5C+A+B50-1=4970-50=201-0=11/6
6C+B+A70-12=5812-1=111-0=11/6

在 A+B+C 的组合中,A 的贡献为 A 单独工作的效率 3;B 的贡献为 A+B 一起工作的效率与 A 单独工作效率的差值:15-3=12;C 的贡献为 A+B+C 一起工作的效率与 A+B 一起工作的效率的差值:70-15=55。

通过计算数学期望来计算各员工的贡献,得 A 的期望贡献:(3+3+5+58+49+58)/6=176/6;B 的期望贡献:(12+20+10+10+20+11)/6=83/6;C 的期望贡献: (55+47+55+2+1+1)/6=161/6。所有员工的期望贡献和为:(176+83+161)/6=70,刚好是 ABC 的整体合作效果,验证了我们计算的合理性。

对贡献值归一后可知,A 的贡献占比是 29.33%,B 的贡献占比是 13.83%,C 的贡献占比是 26.83%。所以,A 的贡献是最多的,C 也次之,B 最少。

Shapley value 概念

假设有 n n n 位合作人,记 D = 1 , 2 , . . . , n D={1,2, ... ,n} D=1,2,...,n S S S D D D 中不含第 i i i 位合作者的集合,即 S ⊆ D − { i } S \subseteq D-\{i\} SD{i} V ( S ) V(S) V(S) 表示集合 S S S 中的贡献值。

边际贡献

i i i 位合作人的贡献,一般采用集合 S S S 与第 i i i 位合作人合作后的贡献减去集合 S S S 的贡献来描述。即, V ( i ) = V ( S ∪ i ) − V ( S ) V(i)=V(S\cup{i})-V(S) V(i)=V(Si)V(S)

合作者加入团队的顺序/合作者在团队中的排序会影响边际贡献值,例如引例中,集合序号 3、4 中 A 的贡献值。

边际贡献对应的概率

每个集合出现具有一定的概率,下面以 i = 1 i=1 i=1​ 为例,绘制权重分配树,分析每种集合出现的概率。当 i = 1 i=1 i=1 时, ∣ S ∣ |S| S 集合人数存在 n − 1 n-1 n1 种情况,每种情况出现的概率为 1 / n 1/n 1/n。其中,若 ∣ S ∣ = 1 |S|=1 S=1 时, ∣ S ∣ |S| S 集合又可以细分为 C n − 1 ∣ 1 ∣ {C_{n-1}^{|1|}} Cn1∣1∣ 种情况,分别是: 1 , 2 , 1 , 3 , . . . 1 , n {1,2}, {1,3}, ...{1,n} 1,2,1,3,...1,n,每种情况出现的概率为 1 C n − 1 ∣ S ∣ \frac{1}{C_{n-1}^{|S|}} Cn1S1。由归纳法知,当 i = 1 i=1 i=1 时,每种集合存在的概率可以用通式表示为: 1 n × 1 C n − 1 ∣ S ∣ \frac{1}{n} \times \frac{1}{C_{n-1}^{|S|}} n1×Cn1S1​,整理后为: 1 n × 1 C n − 1 ∣ S ∣ = 1 n × ( n − 1 − ∣ S ∣ ) ! ( ∣ S ∣ ) ! ( n − 1 ) ! = ( n − ∣ S ∣ − 1 ) ! ( ∣ S ∣ ) ! n ! \begin{aligned} \frac{1}{n} \times \frac{1}{C_{n-1}^{|S|}} & =\frac{1}{n} \times \frac{(n-1-|S|) !(|S|)!}{(n-1)!} =\frac{(n-|S|-1)!(|S|)!}{n!}\end{aligned} n1×Cn1S1=n1×(n1)!(n1S)!(S)!=n!(nS1)!(S)!​。

不难发现,概率值仅与 ∣ S ∣ |S| S 大小有关,与集合 S S S​ 中的排序无关。

关于概率值 ( n − ∣ S ∣ − 1 ) ! ( ∣ S ∣ ) ! n ! \frac{(n-|S|-1)!(|S|)!}{n!} n!(nS1)!(S)! 的理解: ( n − ∣ S ∣ − 1 ) ! (n-|S|-1)! (nS1)! 表示 i i i 后元素的排列组合数, ( ∣ S ∣ ) ! (|S|)! (S)! 表示 i i i 前元素的排列数, n ! n! n! 表示所有元素的排列数。模型解释–Shapley Values - 简书 (jianshu.com)

请添加图片描述

存在三种理解概率值的角度:构造联盟角度-总体平等性、联盟内外平等性角度-平均加权、联盟中参与人贡献平等性的角度-平等贡献性。见 Shapley_Value公式推导

公式理解

由以上分析,可表示出第 i i i 合作者的期望贡献 ϕ i \phi_i ϕi 为:
ϕ i = ∑ S ⊆ D − { i } ( n − ∣ S ∣ − 1 ) ! ( ∣ S ∣ ) ! n ! [ V ( S ∪ { i } ) − V ( S ) ] \phi_i=\sum_{S \subseteq D-\{i\}} \frac{(n-|S|-1) !(|S|)!}{n!}[V(S \cup\{i\})-V(S)] ϕi=SD{i}n!(nS1)!(S)![V(S{i})V(S)]
在引例中,计算 Shapley value 过程中详细列出所有情况,过于复杂。现可以直接以上述公式求得每个程序员的贡献度。

以程序员 A 为例,计算其 Shapley value - ϕ A \phi_A ϕA
ϕ A = ∑ S ⊆ D − { i } ( n − ∣ S ∣ − 1 ) ! ( ∣ S ∣ ) ! n ! [ V ( S ∪ { i } ) − V ( S ) ] = ∑ S ⊆ { A , B , C } − { A } ( 3 − ∣ S ∣ − 1 ) ! ( ∣ S ∣ ) ! 3 ! [ V ( S ∪ { A } ) − V ( S ) ] = ( 3 − 0 − 1 ) ! ( 0 ) ! 3 ! [ V ( { A } ) − V ( ∅ ) ] + ( 3 − 1 − 1 ) ! ( 1 ) ! 3 ! [ V ( { B } ∪ { A } ) − V ( B ) ] + ( 3 − 1 − 1 ) ! ( 1 ) ! 3 ! [ V ( { C } ∪ { A } ) − V ( C ) ] + ( 3 − 2 − 1 ) ! ( 2 ) ! 3 ! [ V ( { B C } ∪ { A } ) − V ( B C ) ] = 2 ! 3 ! ∗ 3 + 1 3 ! ∗ [ 15 − 10 ] + 1 3 ! ∗ [ 50 − 1 ] + 2 ! 3 ! ∗ [ 70 − 12 ] = 1 + 5 6 + 49 6 + 58 3 = 176 6 \begin{align*} \phi_A &=\sum_{S \subseteq D-\{i\}} \frac{(n-|S|-1) !(|S|)!}{n!}[V(S \cup\{i\})-V(S)] \\ &=\sum_{S \subseteq\{A, B, C\}-\{A\}} \frac{(3-|S|-1) !(|S|) !}{3 !}[V(S \cup\{A\})-V(S)] \\ &=\frac{(3-0-1) !(0) !}{3 !}[V(\{A\})-V(\varnothing)]+\frac{(3-1-1) !(1) !}{3 !}[V(\{B\} \cup\{A\})-V(B)]+\frac{(3-1-1) !(1) !}{3 !}[V(\{C\} \cup\{A\})-V(C)]+\frac{(3-2-1) !(2) !}{3 !}[V(\{B C\} \cup\{A\})-V(B C)] \\ &=\frac{2 !}{3 !} * 3+\frac{1}{3 !} *[15-10]+\frac{1}{3 !} *[50-1]+\frac{2 !}{3 !} *[70-12]=1+\frac{5}{6}+\frac{49}{6}+\frac{58}{3}=\frac{176}{6} \end{align*} ϕA=SD{i}n!(nS1)!(S)![V(S{i})V(S)]=S{A,B,C}{A}3!(3S1)!(S)![V(S{A})V(S)]=3!(301)!(0)![V({A})V()]+3!(311)!(1)![V({B}{A})V(B)]+3!(311)!(1)![V({C}{A})V(C)]+3!(321)!(2)![V({BC}{A})V(BC)]=3!2!3+3!1[1510]+3!1[501]+3!2![7012]=1+65+649+358=6176

Shapley value 存在负值,表示负贡献。

Shapley value 的性质/公理

以下三条性质/公理,能将 ϕ i \phi_i ϕi 确定为比例常数。

对称性

每个参与人的贡献/获得的价值与它在集合 D = { 1 , 2 , … , n } D=\{1,2,…,n\} D={1,2,,n} 中的排列位置无关。数学描述: S ⊆ D − { i , j } , V ( S ∪ i ) = V ( S ∪ j ) , 则 ϕ i = ϕ j S \subseteq D-\{i,j\},V(S\cup i)=V(S\cup j),则 \phi_i=\phi_j SD{i,j},V(Si)=V(Sj),ϕi=ϕj

有效性
  1. 如果一个参与者在所有可能的联盟中都没有对结果的影响力,那么该参与者的 Shapley value 应为零。数学描述: S ⊆ D − { i } , V ( S ) = V ( S ∪ i ) , 则 ϕ i = 0 S \subseteq D-\{i\},V(S)=V(S \cup i),则 \phi_i=0 SD{i},V(S)=V(Si),ϕi=0
  2. 所有参与者的 Shapley value 之和等于合作博弈的总价值。数学描述: ∑ ϕ i = a \sum\phi_i=a ϕi=a a a a 为合作博弈的总价值。
可加性

n 个人同时进行两项互不影响的合作,则两项合作的分配也应互不影响,每人的分配额是两项合作单独进行时应分配数的和。数学描述:当 V = V 1 + V 2 V=V_1+V_2 V=V1+V2 时,有 ϕ = ϕ i + ϕ j \phi=\phi_i+\phi_j ϕ=ϕi+ϕj。一般来说,记 V k = − L k V_k=-L_k Vk=Lk L k L_k Lk 表示损失值,为正数,损失值越大, V k V_k Vk 越小。

Shapley value 的评价

Shapley 值方法很公平,在经济、金融、管理、政治中都有不少的推广应用。比如多方金融投资合作如何分配利润;不同人数的党派团体如何更科学地设置投票通过票数;安全管理团队中按照重要性对事故中的不同责任方进行责任判定等等。在机器学习中,也可以使用 Shapley 值方法对不同的特征进行重要性评价,进行特征的筛选工作,即使是深度神经网络这种黑盒模型也可以获悉不同特征对于整个算法的贡献分布。

缺点:对于 n 值很大的情况,计算很不友好。对于 n n n 个数据点,可能的排列数量 n ! n! n!。对于 n n n 个数据点,有 2 n 2^n 2n子集(包括空集和整个数据集)。因为每个数据点都有两种可能:要么在子集中,要么不在。对于 n n n 个数据点,第一个数据点可以选择在或不在一个子集,第二个数据点同样有这两种选择,以此类推,直到最后一个数据点。不包含 i i i 的子集有 2 n − 1 2^{n-1} 2n1 个(包括空集)。有几种补救办法,有的是将合伙人分成若干组,按照组为最小合作单位进行计算;有的则是只考虑 n−1 大小的组合上增加合伙人带来的边际贡献等。无论是何种方法,本质上都和本文核心内容类似。

  1. 满足公平数据估值的几个自然属性(natural properties)
  2. 在提供洞察哪些数据对给定的学习任务更有价值方面,它比流行的“留一分”或杠杆得分更强大
  3. 低 Shapley 值的数据有效捕获异常值和腐败
  4. 高 Shapley 值的数据能告知需要获取何种类型的新数据来改进预测器

以上四点,论文中的 Experiments & Applications有涉及。关于这部分的梳理可见:回答十问Q6 Data Shapley: Equitable Valuation of Data for Machine Learning (readpaper.com)

Data Shapley Value

Data Shapley Value 依赖于数据集、算法、性能度量指标。

训练数据 D = { x i , y i } 1 n D=\{x_i,y_i\}_1^n D={xiyi}1n 是一个固定大小的 n 个数据点的集合,无分布和独立性假设。其中, x i x_i xi 是特征, y i y_i yi 是标签。 S S S 为数据集 D D D 的子集。关于符号 S S S D D D,除了表示数据,也能表示数据对应的索引

A \mathcal{A} A 是用数据集生成预测器(predictor, f f f)的算法。

V V V 是性能度量指标,量化每个数据对预测器 f f f 的作用。 V ( S , A ) V(S,\mathcal{A}) V(S,A) V ( S ) V(S) V(S) 表示在数据集 S S S 上训练的预测器的性能。一般采用留一法(Leave-one-out, LOO),即比较在整个数据集上训练的预测器性能相较于减去一点数据后的数据集上训练的预测器性能的减少量。本文采用 Shapley 而不用留一法的原因:LOO 只考虑单个数据点的移除对模型性能的影响,不考虑各数据点间的关系;不满足公平性、对称性、可加性等性质;计算效率低下。

i i i 个数据点(i-th datum)的 data shapely value 记为: ϕ i ( D , A , V ) = ϕ i ( V ) = ϕ i ∈ R \phi_i(D,\mathcal{A},V)=\phi_i(V)=\phi_i \in R ϕi(D,A,V)=ϕi(V)=ϕiR

ϕ i = C ∑ S ⊆ D − { i } V ( S ∪ { i } ) − V ( S ) ( n − 1 ∣ S ∣ ) \phi_i=C \sum_{S \subseteq D-\{i\}} \frac{V(S \cup\{i\})-V(S)}{\left(\begin{array}{c}n-1 \\ |S|\end{array}\right)} ϕi=CSD{i}(n1S)V(S{i})V(S)

其中, S S S D D D 中随机一个不含有 i i i 的子集, ( n − 1 ∣ S ∣ ) \left(\begin{array}{c}n-1 \\ |S|\end{array}\right) (n1S) 是组合数的一种写法,也可写为 C n − 1 ∣ S ∣ C_{n-1}^{|S|} Cn1S。求和符号表示讨论 D D D 中所有不含数据点 i i i 的子集 S S S。上式和 Shapley 计算公式唯一区别在于:上式中设了任意常数 C C C,而 Shapley 公式中为确定的 1 / n 1/n 1/n

实现方法

截断蒙特卡洛 Shapley 算法(Truncated Monte Carlo Shapley, TMC-Shapley)

此算法是针对整个数据集进行分析的,不需要选取子集 S S S。每次迭代都会对整个数据集中的所有数据点进行一次重新排列,一般对于 n n n 个数据点,可能的排列数量是 n ! n! n!​​。算法会随机选择所有数据点排列情况中的一部分,计算各数据点的Shapley 值的近似结果。

需要注意的是,此算法的准确性和效率依赖于迭代次数和数据集的大小,因此在实际应用中需要根据具体情况调整参数。

求解步骤

Input: Train data D = { 1 , … , n } D=\{1, \ldots, n\} D={1,,n}, learning algorithm
A \mathcal{A} A, performance score V V V
Output: Shapley value of training points: ϕ 1 , … , ϕ n \phi_1, \ldots, \phi_n ϕ1,,ϕn
Initialize ϕ i = 0 \phi_i=0 ϕi=0 for i = 1 , … , n i=1, \ldots, n i=1,,n and t = 0 t=0 t=0
while Convergence criteria not met do
t ← t + 1 t \leftarrow t+1 tt+1
π t \pi^t πt : Random permutation of train data points
v 0 t ← V ( ∅ , A ) v_0^t \leftarrow V(\emptyset, \mathcal{A}) v0tV(,A)
for j ∈ { 1 , … , n } j \in\{1, \ldots, n\} j{1,,n} do
if ∣ V ( D ) − v j − 1 t ∣ < \left|V(D)-v_{j-1}^t\right|< V(D)vj1t < Performance Tolerance then
v j t = v j − 1 t v_j^t=v_{j-1}^t vjt=vj1t
else
v j t ← V ( { π t [ 1 ] , … , π t [ j ] } , A ) v_j^t \leftarrow V\left(\left\{\pi^t[1], \ldots, \pi^t[j]\right\}, \mathcal{A}\right) vjtV({πt[1],,πt[j]},A)
end if
ϕ π t [ j ] ← t − 1 t ϕ π t − 1 [ j ] + 1 t ( v j t − v j − 1 t ) \phi_{\pi^t[j]} \leftarrow \frac{t-1}{t} \phi_{\pi^{t-1}[j]}+\frac{1}{t}\left(v_j^t-v_{j-1}^t\right) ϕπt[j]tt1ϕπt1[j]+t1(vjtvj1t)
end for
end for

  1. 初始化
    • 每个数据点的初始 Shapley value 设为 0( ϕ i = 0 \phi_i=0 ϕi=0 for i = 1 , … , n i=1, \ldots, n i=1,,n ),并设迭代计数变量 t t t 从 0 开始(通常, 3 n 3n 3n 个蒙特卡罗样本是足够收敛的)。
  2. 随机排列
    • 每次迭代中,对整个数据集中的所有数据点进行随机排列, π t \pi^t πt 就是第 t t t 次迭代中产生的数据点的随机排列。这个排列是随机的,意味着每个数据点都有可能出现在新排列的任何位置,根据排列序列可以确定数据点的加入顺序。
  3. 计算边际贡献
    • 对每次排序中的每个数据点 i i i,计算它在排列 π t \pi^t πt 中的边际贡献。这通过比较包含数据点 i i i 之外的所有数据点 S π i S_π^i Sπi,和加上数据点 i i i 后的性能分数差异来实现,即边际贡献/第 i i i 个数据点的贡献值为: V ( S π i ∪ i ) − V ( S π i ) V(S_π^i \cup {i}) - V(S_π^i) V(Sπii)V(Sπi)
  4. 计算及更新 Shapley 值
    • 设定每次迭代的初始性能得分 v 0 t = V ( ∅ , A ) v_0^t=V(\empty,\mathcal{A}) v0t=V(,A),即第 t t t 次迭代中,不使用任何数据点时模型的性能得分。在第 t t t 次迭代中,数据点间的排序已经确定,接下来便是依次对 j = 1 , 2 , . . . n j=1,2,...n j=1,2,...n 通过 j − 1 j-1 j1 个数据点的 Shapley 和 v t j − v t j − 1 v_t^j-v_t^{j-1} vtjvtj1 加权计算第 j j j 个数据点的 Shapley 值。
    • 计算 j j j数据点的性能得分。 v t j − 1 v_t^{j-1} vtj1 表示在当前迭代 t t t 中,已经将随机排列 π t \pi_t πt 中的前 j − 1 j-1 j1 个数据点纳入模型后的性能得分。若 ∣ V ( D ) ∣ − v j − 1 t < P e r f o r m a n c e T o l e r a n c e |V(D)|-v_{j-1}^t<Performance Tolerance V(D)vj1t<PerformanceTolerance,表明第 j j j 个及以后的所有数据点的性能得分可以忽略不记,可以直接使用 v j − 1 t v_{j-1}^t vj1t 的估计 v t j v_t^{j} vtj(此处体现了截断 Truncation)。反之,则需输入数据点序列中前 j j j 个数据点到模型中,计算前 j j j 个数据点的性能得分 v t j v_t^{j} vtj​​。
    • 加权计算第 j j j 个数据点的 Shapley 值。 ϕ π t [ j ] \phi_{\pi^t[j]} ϕπt[j] : 这是在第 t t t 次迭代中,数据点 π t j \pi_t^j πtj (即当前排列中的 j j j数据点) 的Shapley值的估计。 ϕ π t − 1 [ j ] \phi_{\pi^{t-1}[j]} ϕπt1[j] : 这是在第 t − 1 t-1 t1 次迭代中,同一个数据点 π t j \pi_t^j πtj 的 Shapley 值的估计。 t − 1 t \frac{t-1}{t} tt1 1 t \frac{1}{t} t1 : 归一化因子,用于在新旧估计之间进行加权平均,随着 t 值增大, t − 1 t \frac{t-1}{t} tt1 会逐渐增大,也就是旧估计的权重逐渐增大,有助于减少随机波动对 shapley 值的影响,减少对单次迭代结果的以来,使估计结果更加稳定。
  5. 重复迭代
    • 多次生成随机排列,并计算每个数据点的边际贡献,直到达到预定的迭代次数 T 或 Shapley 值收敛。
评价
优点缺点
TMC-Shapley1. 截断策略:通过设置 Performance Tolerance 有效减少计算量
2. 不要求模型可微分
1. 需要大量蒙特卡洛样本
2. 需要大数据集,小数据集会受到随机抽样的影响
3. 计算量仍大

Gradient Shapley, G-Shapley

这种方法特别适用于那些可以通过梯度下降等方法进行训练的模型,如神经网络和支持向量机等。以下是实现基于梯度的方法来计算数据 Shapley 值的步骤:

Input: Parametrized and differentiable loss function L ( . ; θ ) \mathscr{L}(. ; \theta) L(.;θ), train data D = { 1 , … , n } D=\{1, \ldots, n\} D={1,,n}, performance score function V ( θ ) V(\theta) V(θ)
Output: Shapley value of training points: ϕ 1 , … , ϕ n \phi_1, \ldots, \phi_n ϕ1,,ϕn
Initialize ϕ i = 0 \phi_i=0 ϕi=0 for i = 1 , … , n i=1, \ldots, n i=1,,n and t = 0 t=0 t=0
while Convergence criteria not met do
t ← t + 1 t \leftarrow t+1 tt+1
π t \pi^t πt : Random permutation of train data points
θ 0 t ← \theta_0^t \leftarrow θ0t Random parameters
v 0 t ← V ( θ 0 t ) v_0^t \leftarrow V\left(\theta_0^t\right) v0tV(θ0t)
for j ∈ { 1 , … , n } j \in\{1, \ldots, n\} j{1,,n} do
θ j t ← θ j − 1 t − α ∇ θ L ( π t [ j ] ; θ j − 1 ) \theta_j^t \leftarrow \theta_{j-1}^t-\alpha \nabla_\theta \mathscr{L}\left(\pi^t[j] ; \theta_{j-1}\right) θjtθj1tαθL(πt[j];θj1)
v j t ← V ( θ j t ) v_j^t \leftarrow V\left(\theta_j^t\right) vjtV(θjt)
ϕ π t [ j ] ← t − 1 t ϕ π t − 1 [ j ] + 1 t ( v j t − v j − 1 t ) \phi_{\pi^t[j]} \leftarrow \frac{t-1}{t} \phi_{\pi^{t-1}[j]}+\frac{1}{t}\left(v_j^t-v_{j-1}^t\right) ϕπt[j]tt1ϕπt1[j]+t1(vjtvj1t)

​ end for
end for

求解步骤
  1. 初始化与随机排列

    • 每个数据点的初始 Shapley value 设为 0( ϕ i = 0 \phi_i=0 ϕi=0 for i = 1 , … , n i=1, \ldots, n i=1,,n),并设迭代计数变量 t t t 从 0 开始。
    • t t t 轮迭代,生成一个所有数据点随机排列序列 π t \pi^t πt
    • 初始化参数 θ 0 t \theta_0^t θ0t,得出模型的性能得分 V ( θ 0 t ) V(\theta_0^t) V(θ0t),并赋值给 v 0 t v_0^t v0t(表示在第 t t t 次迭代开始时,不使用任何数据点时模型的性能得分,以便计算第 j j j 个数据点的边际贡献)。
  2. 梯度下降

    • L ( π t [ j ] ; θ j − 1 ) \mathscr{L}\left(\pi^t[j]; \theta_{j-1}\right) L(πt[j];θj1) 表示在第 t t t 次迭代中,根据随机排列 π t \pi_t πt 中的前 j − 1 j−1 j1 个数据点生成的模型参数 θ j − 1 \theta_{j-1} θj1 下,第 j j j 个数据点的损失函数 L \mathscr{L} L 的值。通过预设的学习率 α \alpha α​,更新参数值。
    • 更新参数后,重新计算 j j j数据点的贡献值。
  3. 加权计算第 j 个数据点的 Shapley value

    • ϕ π t [ j ] \phi_{\pi^t[j]} ϕπt[j] : 这是在第 t t t 次迭代中,数据点 π t j \pi_t^j πtj (即当前排列中的 j j j数据点) 的Shapley值的估计。 ϕ π t − 1 [ j ] \phi_{\pi^{t-1}[j]} ϕπt1[j] : 这是在第 t − 1 t-1 t1 次迭代中,同一个数据点 π t j \pi_t^j πtj 的 Shapley 值的估计。 t − 1 t \frac{t-1}{t} tt1 1 t \frac{1}{t} t1 : 归一化因子,用于在新旧估计之间进行加权平均,随着 t 值增大, t − 1 t \frac{t-1}{t} tt1 会逐渐增大,也就是旧估计的权重逐渐增大,有助于减少随机波动对 shapley 值的影响,减少对单次迭代结果的以来,使估计结果更加稳定。
  4. 重复迭代

    • 重新迭代,每轮迭代生成一个随机序列 π t \pi^t πt 并初始化参数 v 0 t v_0^t v0t。计算每个数据点在本轮序列中的 Shapley value。直到达到预定的迭代次数 T 或 Shapley 值收敛。
评价
优点缺点
G-Shapley1. 适用于大型数据集和复杂模型,因为它避免了重复训练的需要,从而显著提高了计算效率。1. 因为要求骗到,所以要求模型可微分
2.依赖于梯度估计的准确性


参考:Data Shapley: Equitable Valuation of Data for Machine Learning(翻译)

Data Shapley : 机器学习数据的公平估值 ICML2019

代码实现 amiratag/DataShapley: Data Shapley: Equitable Valuation of Data for Machine Learning (github.com)

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/303618.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

深入了解与全面解析华为认证(HCIA/HCIP/HCIE)

一、网络行业技术认证 网络行业对于技术评定一般分为两种&#xff0c;一种是企业认证&#xff0c;一种是国家认证 企业认证属于技术认证&#xff0c;在国内的互联网企业都会承认&#xff0c;用于评定一个人的技术等级或者企业招投标的资质。 网络行业认证最好的有三种&#…

SpringBoot内容协商快速入门Demo

1.什么内容协商 简单说就是服务提供方根据客户端所支持的格式来返回对应的报文&#xff0c;在 Spring 中&#xff0c;REST API 基本上都是以 json 格式进行返回&#xff0c;而如果需要一个接口即支持 json&#xff0c;又支持其他格式&#xff0c;开发和维护多套代码显然是不合理…

Python 全栈体系【四阶】(二十五)

第五章 深度学习 三、计算机视觉基本理论 11. 图像梯度处理 11.1 什么是图像梯度 图像梯度计算的是图像变化的速度。对于图像的边缘部分&#xff0c;其灰度值变化较大&#xff0c;梯度值也较大&#xff1b;相反&#xff0c;对于图像中比较平滑的部分&#xff0c;其灰度值变化…

elementui 实现一个固定位置的Pagination(分页)组件

系列文章目录 一、elementui 导航菜单栏和Breadcrumb 面包屑关联 二、elementui 左侧导航菜单栏与main区域联动 三、elementui 中设置图片的高度并支持PC和手机自适应 四、 elementui 实现一个固定位置的Pagination&#xff08;分页&#xff09;组件 文章目录 系列文章目录…

基于“PLUS模型+”生态系统服务多情景模拟预测

工业革命以来&#xff0c;社会生产力迅速提高&#xff0c;人类活动频繁&#xff0c;此外人口与日俱增对土地的需求与改造更加强烈&#xff0c;人-地关系日益紧张。此外&#xff0c;土地资源的不合理开发利用更是造成了水土流失、植被退化、水资源短缺、区域气候变化、生物多样性…

HTTP 摘要认证

文章目录 一、什么是摘要认证二、工作流程三、实例演示 一、什么是摘要认证 摘要认证&#xff0c;即 Digest Access Authentication&#xff0c;是一种HTTP身份验证机制&#xff0c;用于验证用户的身份。相较于基本认证&#xff08;Basic Authentication&#xff09;使用用户名…

【随笔】Git 高级篇 -- 相对引用2 HEAD~n(十三)

&#x1f48c; 所属专栏&#xff1a;【Git】 &#x1f600; 作  者&#xff1a;我是夜阑的狗&#x1f436; &#x1f680; 个人简介&#xff1a;一个正在努力学技术的CV工程师&#xff0c;专注基础和实战分享 &#xff0c;欢迎咨询&#xff01; &#x1f496; 欢迎大…

Mongodb入门--头歌实验MongoDB 数据库基本操作

一、数据库创建 任务描述 本关任务&#xff1a;创建数据库。 相关知识 本关评测是在 Linux 环境下进行的&#xff0c;MongoDB 的安装与配置测评系统均已默认完成。 为了完成本关任务&#xff0c;你需要掌握&#xff1a; 1.如何连接数据库&#xff1b; 2.如何创建数据库。 连接数…

sqlmap(四)案例

一、注入DB2 http://124.70.71.251:49431/new_list.php?id1 这是墨者学院里的靶机&#xff0c;地址&#xff1a;https://www.mozhe.cn/ 1.1 测试数据库类型 python sqlmap.py -u "http://124.70.71.251:49431/new_list.php?id1" 1.2 测试用户权限类型 查询选…

Vue3 ts环境下的PropType

简介 在Typscript中&#xff0c;我们可以使用PropType进行类型的推断与验证。在日常的开发中我们常常会遇到下面这样的场景&#xff1a; 我们通过request请求从服务端获取了一条数据&#xff0c;数据是个Array的格式&#xff0c;Array中的每个元素又是一个对象&#xff0c;像下…

Web前端—属性描述符

属性描述符 假设有一个对象obj var obj {a:1 }观察这个对象&#xff0c;我们如何来描述属性a&#xff1a; 值为1可以重写可以遍历 我们可以通过Object.getOwnPropertyDescriptor得到它的属性描述符 var desc Object.getOwnPropertyDescriptor(obj, a); console.log(desc);我…

Python-VBA函数之旅-bytearray函数

目录 1、bytearray函数&#xff1a; 1-1、Python&#xff1a; 1-2、VBA&#xff1a; 2、相关文章&#xff1a; 个人主页&#xff1a;非风V非雨-CSDN博客 bytearray函数在Python中提供了一种可变字节序列的表示方式&#xff0c;这在实际编程中有多种应用场景。常见的应用场…

RabbitMQ3.13.x之九_Docker中安装RabbitMQ

RabbitMQ3.13.x之_Docker中安装RabbitMQ 文章目录 RabbitMQ3.13.x之_Docker中安装RabbitMQ1. 官网2. 安装1 .拉取镜像2. 运行容器 3. 访问 1. 官网 rabbitmq - Official Image | Docker Hub 2. 安装 1 .拉取镜像 docker pull rabbitmq:3.13.0-management2. 运行容器 # lates…

蓝桥杯-数组分割

问题描述 小蓝有一个长度为 N 的数组 A 「Ao,A1,…,A~-1]。现在小蓝想要从 A 对应的数组下标所构成的集合I 0,1,2,… N-1 中找出一个子集 民1&#xff0c;那么 民」在I中的补集为Rz。记S∑reR 4&#xff0c;S2∑rERA,&#xff0c;我们要求S、和 S,均为偶数&#xff0c;请问在这…

Spring6-单元测试:JUnit

1. 概念 在进行单元测试时&#xff0c;特别是针对使用了Spring框架的应用程序&#xff0c;我们通常需要与Spring容器交互以获取被测试对象及其依赖。传统做法是在每个测试方法中手动创建Spring容器并从中获取所需的Bean。以下面的两行常见代码为例&#xff1a; ApplicationCo…

【教程】混淆Dart 代码

什么是代码混淆&#xff1f; 代码混淆是一种将应用程序二进制文件转换为功能上等价&#xff0c;但人类难于阅读和理解的行为。在编译 Dart 代码时&#xff0c;混淆会隐藏函数和类的名称&#xff0c;并用其他符号替代每个符号&#xff0c;从而使攻击者难以进行逆向工程。 Flut…

基于SpringBoot的“垃圾分类网站”的设计与实现(源码+数据库+文档+PPT)

基于SpringBoot的“垃圾分类网站”的设计与实现&#xff08;源码数据库文档PPT) 开发语言&#xff1a;Java 数据库&#xff1a;MySQL 技术&#xff1a;SpringBoot 工具&#xff1a;IDEA/Ecilpse、Navicat、Maven 系统展示 系统功能结构图 系统功能界面图 用户登录、用户注…

SpirngBoot开发常用知识

springboot开发常用知识 命令行打包SpringBoot打包插件window端口命令临时属性设置热部署启动热部署热部署范围 常用计量单位数据校验加载测试的专用属性Web环境模拟测试如何发送虚拟请求业务层测试回滚随机产生测试用例内置数据源 命令行打包 对SpringBoot项目进行打包命令行…

适用于 Windows 10 的 10 大免费数据恢复软件

数据丢失可能是一场噩梦&#xff0c;尤其是在涉及重要文件和文档时。无论是由于意外删除、系统崩溃还是病毒攻击&#xff0c;找到适合 Windows 10 的文件夹恢复软件都可以在恢复丢失的数据方面发挥重要作用。在本指南中&#xff0c;我们将探索适用于 Windows 10 用户的 10 大免…

[STL-list]介绍、与vector的对比、模拟实现的迭代器问题

一、list使用介绍 list的底层是带头双向链表结构&#xff0c;双向链表中每个元素存储在互不相关的独立节点中&#xff0c;在节点中通过指针指向其前一个元素和后一个元素。与其他的序列式容器相比(array&#xff0c;vector&#xff0c;deque)&#xff0c;list通常在任意位置进行…