【论文阅读:Towards Efficient Data Valuation Based on the Shapley Value】

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

主要贡献

  • 提出了一系列用于近似计算Shapley值的高效算法。
  • 设计了一个算法,通过实现不同模型评估之间的适当信息共享来实现这一目标,该算法具有可证明的误差保证来近似N个数据点的SV,其模型评估数量为 O ( N l o g ( N ) 2 ) O(\sqrt Nlog(N)^2) O(N log(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}iS的加法聚合计算出的总价值,其中 S ⊆ I = { 1 , . . . , N } S\subseteq I=\{1,...,N\} SI={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}iI的所有可能子集的平均边际贡献:
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=SI{i}N(N1S)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表示的上述性质:

  1. Group Rationality:
    U ( I ) = ∑ i ∈ I s i U(I) = \sum_{i \in I} s_i U(I)=iIsi
  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}),SI{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\} SI{i}, 则 s i = 0 s_i = 0 si=0
  3. 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), 对于 iI

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]TRN ( ϵ , δ ) (\epsilon, \delta) (ϵ,δ)-近似,即满足 P [ ∣ ∣ s ^ i − s i ∣ ∣ p ≤ ϵ ] ≥ 1 − δ P[||\hat{s}_i - s_i||_p \leq \epsilon] \geq 1 - \delta P[∣∣s^isipϵ]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(biai)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,jI,两者之间的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|}} sisj=N11SI{i,j}(SN2)U(S{i})U(S{j})

引理2:假设 C i j C_{ij} Cij是一个对于 s i − s j s_i - s_j sisj ( ε / ( 2 N ) , δ / ( N ( N − 1 ) ) ) 分布的近似 (\varepsilon/(2\sqrt N),\delta/(N(N-1)))分布的近似 (ε/(2N ),δ/(N(N1)))分布的近似
∑ 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=1Ns^i=Utot(5)(s^is^j)Cij2N ε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^

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^

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Typora配置PicGo图床,将图片文件上传到gitee厂库,获取图片链接显示在md文件中

Typora配置PicGo图床,将图片文件上传到gitee厂库,获取图片链接显示在md文件中 创建Gitee创库和配置私人令牌 名字、路径、描述自己随便添,但是必须开源,链接才能可以访问: 进入偏好设置 > 图像 > 选择PicGo-Cor…

CAS 与 volatile

目录 CAS volatile 为什么无锁效率高 CAS 的特点 CAS AtomicInteger 内部并没有用锁来保护共享变量的线程安全。那么它是如何实现的呢? public void withdraw(Integer amount) {while(true) {// 需要不断尝试,直到成功为止while (true) {// 比如拿到…

基于Springboot+Vue的Java项目-入校申报审批系统开发实战(附演示视频+源码+LW)

大家好!我是程序员一帆,感谢您阅读本文,欢迎一键三连哦。 💞当前专栏:Java毕业设计 精彩专栏推荐👇🏻👇🏻👇🏻 🎀 Python毕业设计 &am…

算法入门<一>:C++各种排序算法详解及示例源码

1、排序算法 排序算法(sorting algorithm)用于对一组数据按照特定顺序进行排列。排序算法有着广泛的应用,因为有序数据通常能够被更高效地查找、分析和处理。 1.1 评价维度 运行效率:我们期望排序算法的时间复杂度尽量低&#xf…

sunshine+n2n+moonlight串流远程控制全教程

远程主机说明(两台电脑不在同一局域网下): 控制台电脑 被控制电脑 所有工具下载地址:https://www.lanzouw.com/b00eepod7e 密码:1234 一、首先NTN组网 使用NTN技术创建虚拟局域网,实现设备之间的P2P连接。 NTN组网…

SpringBoot中阿里OSS简单使用

官方文档:Java跨域设置实现跨域访问_对象存储(OSS)-阿里云帮助中心 1.pom中引入依赖 <dependency><groupId>com.aliyun.oss</groupId><artifactId>aliyun-sdk-oss</artifactId><version>3.15.1</version> </dependency> 如…

区块链 | IPFS:Merkle DAG

&#x1f98a;原文&#xff1a;IPFS: Merkle DAG 数据结构 - 知乎 &#x1f98a;写在前面&#xff1a;本文属于搬运博客&#xff0c;自己留存学习。 1 Merkle DAG 的简介 Merkle DAG 是 IPFS 系统的核心概念之一。虽然 Merkle DAG 并不是由 IPFS 团队发明的&#xff0c;它来自…

模块六:模拟——1419.数青蛙

文章目录 题目描述算法原理解法&#xff08;模拟 分情况讨论&#xff09; 代码实现 题目描述 题目链接&#xff1a;1419.数青蛙 算法原理 解法&#xff08;模拟 分情况讨论&#xff09; 模拟⻘蛙的叫声。 当遇到 ‘r’ ‘o’ ‘a’ ‘k’ 这四个字符的时候&#xff0c;我…

c++容器与算法概述

容器与算法 每个标准库容器都提供了begin() end() 函数&#xff0c;分别返回容器的头部位置和尾部位置。 I/O 流 对于自定义的类型&#xff1a; struct Entry {std::string name;int number;};如果需要使用标准输出需要重载<< 运算符&#xff0c;特别注意&#xff1a…

ICMP详解

3 ICMP ICMP&#xff08;Internet Control Message Protocol&#xff0c;因特网控制报文协议&#xff09;是一个差错报告机制&#xff0c;是TCP/IP协议簇中的一个重要子协议&#xff0c;通常被IP层或更高层协议&#xff08;TCP或UDP&#xff09;使用&#xff0c;属于网络层协议…

结构分析的有限元法及matlab实现(徐荣桥)|【PDF教材+配套案例Matlab源码】

专栏导读 作者简介&#xff1a;工学博士&#xff0c;高级工程师&#xff0c;专注于工业软件算法研究本文已收录于专栏&#xff1a;《有限元编程从入门到精通》本专栏旨在提供 1.以案例的形式讲解各类有限元问题的程序实现&#xff0c;并提供所有案例完整源码&#xff1b;2.单元…

用栈实现队列——leetcode刷题

题目要求我们只用栈的基本操作 push to top 入栈&#xff0c;peek from top 返回栈顶元素&#xff0c;pop from top 移除并返回栈顶元素&#xff0c;size 栈的大小&#xff0c;is_empty 判断栈是否为空&#xff0c;这几个函数来实现队列&#xff0c;也就是说&#xff0c;我们在…

Linux字符设备驱动-详解与实操:驱动架构、设备树、Pinctrl子系统和GPIO子系统、platform、设备树下的platform

如何编写一个驱动程序&#xff1a; &#xff08;1&#xff09;确定主设备号 &#xff08;2&#xff09;定义自己的file_operations结构体&#xff1a; 包含对应的open(drv_open)/read(drv_read)等设备操作函数&#xff0c;需要到内核中去注册 &#xff08;3&#xff09;实现…

OpenAI最大对手推出iOS版APP 以期与ChatGPT展开竞争 | 最新快讯

财联社 5 月 2 日讯&#xff08;编辑牛占林&#xff09;美东时间周三&#xff0c;人工智能(AI)初创公司 Anthropic 宣布推出一款免费的移动端应用程序(APP)&#xff0c;不过目前仅有 iOS 版本。 这款应用名为 Claude&#xff0c;与 Anthropic 的大模型系列名字相同。Anthropic …

基于Python的在线学习与推荐系统设计与实现(论文+源码)-kaic

题目&#xff1a;在线学习与推荐系统设计与实现 摘 要 现代经济快节奏发展以及不断完善升级的信息化技术&#xff0c;让传统数据信息的管理升级为软件存储&#xff0c;归纳&#xff0c;集中处理数据信息的管理方式。本在线学习与推荐系统就是在这样的大环境下诞生&#xff0…

macbook文件管理,这款神器不得不说 macbook文件管理技巧 macbookpro文件管理软件

使用MacBook办公就是看重高效的特点&#xff0c;但很多时候随着使用时间的增长&#xff0c;MacBook上的文件也会越来越多&#xff0c;如果没有很好的管理方式&#xff0c;只会给日常的使用造成诸多不便。如何更好的搞定macbook文件管理呢&#xff0c;且看下面几个方法&#xff…

新势力4月交付量比拼:理想超问界夺冠,小米首月交付超七千辆 | 最新快讯

理想汽车超越问界夺下 4 月新势力交付量冠军。 5 月 1 日&#xff0c;各大造车新势力纷纷亮出最新成绩。新入局者小米汽车也准时发布了交付数据&#xff0c;在交付首月&#xff0c;同时又是非完整交付月&#xff0c;小米就交出了超七千辆的好成绩&#xff0c;在造车新势力中尚属…

ngrinder项目-本地调试遇到的坑

前提-maven mirrors配置 <mirrors><!--阿里公有仓库--><mirror><id>nexus-aliyun</id><mirrorOf>central</mirrorOf><name>Nexus aliyun</name><url>http://maven.aliyun.com/nexus/content/groups/public</ur…

【计算机网络】网络层总结

目录 知识梗概 IP地址 子网划分 IP包头格式 路由 网络层协议 ARP病毒/ARP欺骗 知识梗概 IP地址 IP相关介绍&#xff1a;机器之间需要交流&#xff0c;必须要一个地址才能找到对应的主机&#xff0c;IP地址是主机的一种表示&#xff0c;保证主机之间的正常通信&#xff…

1083 是否存在相等的差

solution 输出的是重复的差值&#xff0c;而非全部差值 #include<iostream> #include<algorithm> using namespace std; const int maxn 1e4 10; int flag[maxn] {0}; int main(){int n, x;scanf("%d", &n);for(int i 1; i < n; i){scanf(&…
最新文章