本文由“大数据治理的理论与技术”专题特约编辑杜小勇教授、杨晓春教授和童咏昕教授推荐.
数据不动的联邦学习框架是多个数据持有方合作训练机器学习模型的新范式. 多个数据持有方参与联邦学习时的贡献评估是联邦学习的核心问题之一. 参与方贡献评估需要兼顾有效性、公平性和合理性等要素, 在理论方法与实际应用中均面临多项挑战. 贡献评估首先需要明确如何度量数据价值, 然而数据估值存在主观性与依赖于实际任务场景的特点, 如何设计有效、可靠并对恶意数据鲁棒的数据估值指标是第一大挑战. 其次, 联邦学习合作中的参与方贡献评估是经典的合作博弈问题, 如何制定公平合理的参与方贡献评估方案, 实现参与方一致认可的博弈平衡是第二大挑战. 最后, 参与方贡献评估往往计算复杂度高, 同时, 联邦学习中围绕模型的数据估值时间开销大, 因此, 在实践中如何设计高效且准确的近似算法是第三大挑战. 近年来, 为了有效地解决上述挑战, 学术界对联邦学习中的贡献评估问题展开了广泛的研究. 首先, 简要介绍联邦学习与参与方贡献评估的背景知识; 然后, 综述数据估值指标、参与方贡献评估方案和相关优化技术; 最后, 讨论了联邦学习贡献评估仍面临的挑战并展望未来研究的发展方向.
Federated learning is a collaborative machine learning framework with multiple participants whose training datasets are kept locally. How to evaluate the corresponding data contribution of each participant is one of the critical problems of federated learning. However, contribution evaluation in federated learning faces multiple challenges. First, to evaluate participant contribution, data value needs to be quantified, however, data valuation is challenging because it is subjective, task context-dependent, and vulnerable to malicious data. Second, participant contribution evaluation is a classic cooperative game problem, and a fair yet rational cooperative contribution evaluation scheme is needed to achieve an optimal equilibrium among all participants. Third, contribution evaluation schemes often involve exponential computational complexity, where data valuation by training models in federated learning is also quite time consuming. In recent years, researchers have conducted extensive studies on participant contribution evaluation in federated learning to tackle the above challenges. This study first introduces the background knowledge of federated learning and contribution evaluation. Then, data valuation metrics, contribution evaluation schemes, and corresponding optimization technologies are surveyed successively. Finally, the remaining challenges of contribution evaluation and potential future work are discussed.
随着人工智能相关技术的广泛应用, 驱动人工智能模型的大数据已成为信息时代的“石油”[
为了吸引潜在优质数据持有方参与联邦学习, 需要根据各参与方数据在联邦合作中的预计贡献大小给予激励. 为此, 如何有效地评估参与方(数据)在联邦合作中的贡献, 是联邦学习实际应用与长远发展的关键问题. 贡献评估首先需要考虑如何度量数据价值高低的问题, 即数据估值子问题. 最直观的数据估值指标是测试准确率: 基于数据训练联邦模型, 在联邦测试集上评测模型, 测试准确率越高, 则认为训练数据的价值越高. 确定数据估值指标后, 容易将参与方自身的数据价值直接等同于参与方对联邦合作的贡献, 比如, 用参与方独自训练模型的联邦测试准确率来评价其在后续联邦合作中的贡献. 然而, 联邦合作下全体参与方的数据价值一般不等于各参与方数据价值之和, 即参与方个体数据价值并不能代表其在联邦合作中的贡献. 从博弈论角度来看, 评估个体在联邦合作中的贡献是合作博弈问题[
● 数据估值的有效性和可靠性. 如何度量数据价值是贡献评估的首要问题, 然而数据估值存在主观性, 且严重依赖于任务上下文, 比如对异常监测任务高价值的数据, 可能对于回归或分类任务价值不高. 同时, 在实践中可能存在策略性参与方的情况, 这些参与方希望通过低质量或者恶意数据从联邦中获利, 比如通过复制数据期望提高获利. 因此, 数据估值指标需要对这些低价值或者恶意数据具备鲁棒性, 识别并降低其对估值带来的影响. 当任务场景明确且任务测试集完备时, 可通过联邦模型在测试集上的效果来度量数据价值. 然而, 实践中很难收集到完备的测试数据, 且任务测试效果受到任务难度、模型有效性等因素的影响[
● 贡献评估的公平性和合理性. 从联邦集体来看, 参与方个体的数据价值不能代表其在联邦合作中的贡献, 贡献评估需要从参与方组合的数据价值出发, 评估引入某个参与方为联邦带来的边际价值增益. 从参与方个体来看, 在参与方联邦合作中, 贡献评估需要考虑公平性的问题, 比如, 持有类似数据的参与方应有类似的贡献评估结果, 在任何其他参与方组合下引入某参与方均不能给联邦合作带来边际价值增益, 则该参与方对联邦无贡献. 同时, 从联邦合作组合合理性角度来看, 全体参与方合作中, 数据的组合价值应等同于所有参与方的贡献之和. 此外, 贡献评估需要考虑新增数据价值度量指标、参与方组合的贡献评估结果相对于其数据价值是否足够合理等问题.
● 贡献评估计算的高效性. 有效的贡献评估方案往往需要枚举不同参与方组合来度量价值, 以计算引入某个参与方对联邦模型性能的边际提升效果. 然而, 潜在参与方组合数随参与方数量指数性增长. 同时, 联邦学习中不同参与方组合的数据估值往往需要重复训练并评测联邦模型, 这也额外地增加了计算代价. 因此, 如何围绕联邦学习特性设计高效的贡献评估优化算法, 是方案实际落地的关键问题. 此外, 低价值或者恶意参与方会对联邦带来负面的影响, 使得联邦合作训练的模型可用性降低.
自联邦学习被提出并广泛研究以来, 学术界已经开始研究参与方贡献评估的相关技术来攻克上述挑战.
● 首先, 解决贡献评估问题需要设计有效且可靠的数据估值指标, 以准确地度量数据对联邦学习任务的价值. 本文按是否依赖于联邦测试集综述两类数据估值指标. 对于联邦持有任务完备测试集的情况, 数据估值指标可以是数据训练联邦模型的测试准确率; 从信息论角度, 数据为测试集所带来的信息增益, 等等. 在联邦不具备测试集时, 数据估值指标可以是任务相关的数据统计指标、数据训练任务模型的相似度和模型不确定性等.
● 其次, 贡献评估的核心问题是探索公平合理的贡献评估方案, 以客观评价参与方在联邦合作中的贡献. 本文首先综述简单直观的个体法和留一法方案, 并分析这两种方案在评估参与方联邦合作贡献的不足之处. 本文接下来综述在合作博弈理论上更加公平合理的夏普利值和最小核方案, 对比其相对于个体法和留一法的优势, 并总结贡献评估方案相关的重要性质.
● 最后, 围绕一些贡献评估方案固有的高计算复杂度问题, 本文综述贡献评估计算的近似优化技术. 本文首先综述统计采样优化方法, 对比不同采样方法的理论计算复杂度, 并调研实际应用中加速采样计算收敛的优化策略. 随后, 本文综述面向联邦学习的估值计算优化方法, 调研如何复用模型梯度避免重复训练模型, 并从随机采样、模型训练和相关数据这3个层面总结模型训练的剪枝策略. 此外, 本文综述如何基于贡献评估结果来优化联邦学习流程, 分析如何降低低价值或恶意参与方对联邦带来的影响, 保障联邦模型的高可用性.
联邦学习贡献评估技术
本文主要综述针对联邦学习参与方的贡献评估技术, 相关综述工作涵盖联邦学习参与方激励、数据定价、质量评估、隐私安全以及贡献评估方法性能实证等[
本文第1节介绍联邦学习与贡献评估的背景知识. 第2节介绍如何度量数据价值, 并总结对比各类数据估值指标适应的场景. 第3节介绍参与方贡献评估的方案, 并总结分析各种博弈方案所满足的重要性质, 对比不同方案优劣和适用场景. 第4节调研面向联邦学习的贡献评估优化技术, 从统计采样优化、模型复用剪枝和降低恶意参与方对模型性能影响等方面详细梳理总结了相关技术. 第5节总结现有方法的不足之处, 展望未来数据估值指标设计的参考准则、贡献评估方案需考虑的要素以及面向联邦学习的评估优化研究方向.
在综述调研联邦学习参与方贡献评估相关技术之前, 本节先介绍联邦学习以及贡献评估的背景知识.
联邦学习(federated learning, FL)是数据不动的分布式机器学习框架, 机器学习模型由多个参与方合作经过多轮次训练完成[
联邦学习框架
每轮次训练分为两个阶段.
(1) 本地更新: 各参与方基于各自的本地数据更新本地模型, 并将参数梯度更新发送给联邦服务器.
(2) 联邦聚合: 联邦服务器聚合所有参与方的更新. 比如, 联邦平均(FedAvg)简单基于各参与方数据量加权聚合各参与方上传的梯度值, 并基于聚合梯度更新全局模型.
最后, 联邦服务器将更新完成的全局模型参数发送给各参与方, 各参与方更新本地模型, 以准备下一轮次训练. 联邦学习也有去中心化的端到端架构, 由于本文调研的相关几乎全部基于中心服务器架构的设定[
● 多方参与: 有2到多个参与方合作训练联邦模型, 每个参与方及联邦平台根据利益需要作出合理的决策.
● 数据不动: 联邦参与方注重自身数据隐私与安全, 在合作训练联邦模型过程中, 任何参与方的原始数据不会以任何形式部分或全部地离开参与方本地.
● 可信传输: 联邦学习过程中, 梯度与参数等信息基于安全方式传递, 其中, 联邦中心服务器是诚实可信的(honest), 会按联邦学习要求完成训练并不会窃取参与方的隐私数据; 参与方是半诚实的(semihonest, honest-but-curious), 会基于本地数据上传每轮次的真实梯度更新, 但对于获取其他参与方的隐私信息存在好奇[
按照参与方持有的数据维度不同, 联邦学习分为横向联邦学习(horizontal federated learning, HFL)和纵向联邦学习(vertical federated learning, VFL)[
● 横向联邦学习. 在横向联邦学习中, 各参与方拥有相同数据特征列下的不同数据行, 比如按照相同或者类似数据模型设计数据库的多个银行, 它们拥有相同的数据特征, 但是它们服务的客户不尽相同, 拥有不同的数据样本.
● 纵向联邦学习. 在纵向联邦学习中, 各参与方拥有相同数据行的不同数据列, 即持有不同数据特征, 比如为社会提供不同服务的银行与通信运营商, 它们拥有用户在银行信用与通信服务上的不同数据特征, 数据行可以通过用户身份信息对齐.
横向与纵向联邦学习对比
按照参与方对象的不同, 联邦学习被分为跨设备联邦学习(cross-device FL)和跨机构联邦学习(cross-silo FL)两类场景[
● 跨设备联邦学习. 个人终端或者物联网设备作为参与方的联邦学习称为跨设备联邦学习, 也称为企业对消费者联邦学习(business-to-consumer, B2C FL). 跨设备联邦学习场景呈现参与方数量多、算力有限、单个参与方数据量少、传输开销大等特点. 典型案例是谷歌和苹果等公司面向用户的智能手机应用训练联邦模型, 用户通过参与横向联邦学习来获得更智能的体验[
● 跨机构联邦学习. 企业或结构作为参与方的联邦学习称为跨机构联邦学习, 也称为企业对企业联邦学习(business-to-business, B2B FL). 跨机构联邦学习呈现参与方数量少、算力充足、单个参与方数据量大、存在商业风险顾虑等特点. 典型案例是FATE联邦学习平台, 为金融等行业提供数据隐私保护的联邦学习方案[
为了激励参与方加入联邦学习中来, 需要公平合理地评价参与方数据在联邦合作中的贡献, 并根据贡献给予各参与方相应的回报. 给定联邦学习参与方
评估参与方贡献需要解决如下3个子问题.
● 数据价值度量: 设计数据估值指标
● 参与方贡献评估: 基于数据估值指标
● 贡献评估优化: 基于联邦学, 优化参与方贡献评估计算. 与经典的合作博弈问题不同[
不同参与方组合数据训练联邦模型的测试准确率
Ø | {1} | {2} | {3} | {1, 2} | {1, 3} | {2, 3} | {1, 2, 3} | |
模型准确率(%) | 50 | 80 | 80 | 65 | 80 | 90 | 90 | 90 |
联邦学习参与方贡献评估需要解决的首要问题是如何度量数据价值, 本节综述数据估值相关指标, 为第3节介绍贡献评估技术奠定基础. 给定参与方组合
数据估值指标分类
在理想的情况下, 联邦拥有机器学习任务的完备测试数据集, 可以基于训练数据在测试场景中的表现来度量数据价值.
最直接的方式是基于数据训练模型, 通过联邦模型测试准确率来度量数据价值. 给定参与方组合
其中,
在实际应用中, 公式(1)根据测试效果判定的标准变化而变化. 对于回归任务, 公式中的均方误差可按照具体任务对单条数据样本的敏感程度修改为其他误差度量标准, 比如均方根误差或者绝对误差. 对于分类任务, 由于示性函数的输出只能为0或者1, 粗粒度地对于分类错误的测试样本同等看待, 不能区分在单条测试数据上预测结果好坏的程度, 因此不利于量化分类任务的具体误差. 为细粒度对正确分类置信度更低的数据设置更大的估值权重, 可以基于交叉熵(cross entropy)来度量分类任务中的数据价值[
对于纵向联邦, 根据不同参与方之间拥有相同数据行的特性, 可以无须训练并在测试集上评测模型来度量数据价值. 最典型的是直接基于参与方的特征为测试数据标签减少的不确定性来度量数据价值, 测试标签减少的不确定性越大, 数据特征价值越高. 可以基于信息论的条件互信息指标来度量测试结果的不确定性[
其中,
在通常的实际情况中, 联邦对任务应用场景了解有限, 很难获取到(完备的)测试集, 此时需要设计不依赖于测试集的数据估值指标.
数据统计指标是一类直观且易于实现的方法, 它通过数据的某些统计指标特性来度量数据的价值, 本文展开介绍自助度量与数据多样性度量指标.
● 自助度量
理想情况下, 若所有数据独立同分布, 在不具备其他知识的情况下, 认为数据价值与数据量正相关, 数据量越大, 数据价值越高[
● 数据多样性度量
在不存在恶意参与方提供虚假数据时, 数据分布的多样性一定程度上可以反映数据的价值, 即数据分布多样性越高, 数据价值越大. 在联邦中, 对齐数据共有
其中,
● 多指标复合
当联邦对于模型的应用背景足够了解, 对于所需的数据统计特征建模也足够完善时, 可以依据具体应用需求, 基于多种数据统计指标设计复合价值度量指标. 例如, 若某一特征列的取值与数据价值有直接关联, 可以直接通过计算
以上基于数据统计指标的价值度量指标适用于横向联邦下的数据价值度量, 它不依赖于任务、模型和测试集, 在一定程度上可以反映参与方组合的数据价值.
在假定联邦参与方的数据均对任务有利、不存在低贡献或者恶意参与方的情况下, 可以认为全体参与方参与下, 联邦合作训练的全局模型最优. 此时, 采用模型相似度指标衡量数据训练的模型与全局模型相似度, 可实现比数据统计指标面向任务更加具体准确的价值度量. 模型相似度最直接的比较方式是对比参与方组合数据训练联邦模型与联邦全局模型的参数相似度来衡量数据价值, 比如
● 梯度相似度
梯度相似度通过参与方组合
其中,
● 参数不确定性
基于参与方数据对联邦任务有利的假定下, 价值最高的参与方数据组合可以最大限度地优化联邦任务的目标函数, 降低模型参数的不确定性, 因此可以基于模型参数信息增益来度量数据价值, 以避免梯度相似度指标的不稳定性, 提高价值度量可靠性[
其中,
以上模型相似度相关指标在不依赖于联邦测试集的前提下, 尽可能任务相关地实现了数据价值的度量. 当全部参与方数据均对联邦任务有利, 或者不存在很多策略性的恶意参与方时, 模型相似度能够较为准确、有效地反映数据对联邦任务的价值. 但是, 当存在大量策略性的恶意参与方时, 比如持有一致分布的恶意数据能够使得任务目标函数优化下模型参数不确定性最小化, 仍需联邦提供测试数据来提升价值度量的有效、可靠性.
合成价值指标是一种简化的参与方组合价值度量指标. 它通过设定某种博弈规则来给不同参与方组合赋予不同的价值. 由于合成价值指标计算简单, 避免了基于真实任务和数据度量价值的高昂计算代价, 它可以用于与实际任务及数据价值无关的参与方贡献评估方案或者相关优化技术性能评估. 例如, 定义一个多参与方一致性表决博弈问题[
本节综述的数据估值指标主要围绕分类回归任务和横向或纵向联邦展开, 对于其他类型任务和横纵混合联邦相关的估值场景有待更深入的研究. 上述数据估值指标选择与联邦参与对象分类正交, 即同时适用于跨设备和跨机构联邦. 此外, 目前测试集无关的数据估值指标仍存在主观性过强, 而有效性和可靠性不够等问题, 对于不依赖于测试集或者结合不完善测试集的数据估值指标有待进一步的研究.
数据估值指标对比
任务依赖 | 模型依赖 | 测试集依赖 | 联邦类型 | 优点 | 缺点 | |
测试准确率[ |
√ | × | √ | HFL |
反映测试场景需要; |
依赖完备测试集 |
测试不确定性[ |
√ | × | √ | VFL | 无须训练评测模型; |
依赖安全计算技术 |
数据统计指标[ |
× | × | × | HFL | 简单直观, 不依赖于 |
不能完全反映任务 |
梯度相似度[ |
√ | × | × | HFL | 反映数据一致性 | 易受恶意参与方影响 |
参数不确定性[ |
√ | √ | × | HFL | 反映任务效果一致性 | 依赖于贝叶斯等离散模型 |
● 当联邦能够获得有效测试数据集时, 直接通过测试准确率可以反映数据对任务测试场景最准确的价值高低.
● 当联邦无法获得(完备的)测试数据集时, 需通过数据统计指标或者训练模型相似度对数据进行侧面的价值度量. 但是当联邦中存在过多低价值或者恶意参与方时, 这些指标可能存在无法准确而有效地反映数据价值的情况.
● 纵向联邦目前只能通过测试准确率和测试不确定性来度量数据价值, 其他面向纵向联邦的不依赖于测试集的价值度量指标仍有待进一步研究.
● 当联邦希望价值度量结果具有跨模型鲁棒性时, 可以采用模型无关的价值度量指标, 基于多种任务模型来度量数据价值.
在明确如何度量参与方组合数据价值的基础上, 本节介绍如何进一步度量参与方在联邦合作中的贡献, 具体介绍如下4种参与方贡献评估方案.
● 个体法[
● 留一法[
● 夏普利值[
● 最小核[
顾名思义, 个体法(individual)直接基于参与方自身的数据价值度量或者相关变体来评估参与方在联邦中的贡献:
其中,
● 个体信誉法
在假定有参与方数据价值评分的信誉系统中, 个体信誉法通过参与方历史参与联邦学习的信誉来评估参与方对联邦合作的贡献[
● 个体交叉验证法
对于需要估计参与方数据标签质量以及与联邦测试集一致性的场景中, 通过参与方本地模型和本地测试集与联邦全局模型和联邦测试集进行交叉测实验证来评估参与方对联邦合作的贡献[
● 个体互信息法
针对希望识别低价值或者恶意参与方的场景[
● 个体采样实验法
基于联邦学习全体参与方共同训练全局模型的设定, 可以设法直接在训练全局模型的同时, 完成各参与方的贡献评估, 以减少每个参与方额外训练模型的代价. 联邦学习训练过程中, 每轮次各参与方的数据会全部参与训练计算梯度, 如果随机改变各参与方数据的参与比例, 则相应的训练后联邦模型测试准确率会发生变化. 基于这样的观察, 可以调节不同的参与方数据参与比例, 重复训练多个联邦模型, 从而获得多个对应的测试准确率结果, 并基于深度学习技术来拟合各参与方采样率与联邦测试准确率的关系[
基于上述拟合随机采样比例与参与方贡献之间关系的启发, 可进一步引入强化学习算法, 通过交互式的反馈, 动态地调节参与方采样比例, 使得联邦模型测试准确率快速地收敛到最高, 并将最优情况下的参与方数据被采样比例作为该参与方对联邦合作的贡献[
● 个体影响函数法
上述参与方采样比例评估法在评估参与方个体在联邦学习中的贡献时, 仍需要重复多次训练联邦模型, 以验证何种参与比例下联邦模型最优. 如果只希望训练单个联邦模型, 不再额外训练局部模型, 则可以采用影响函数技术进行参与方贡献评估[
个体法中, 参与方对联邦合作的贡献评估直接基于参与方自身数据价值、参与方之间对比或者参与方在联邦合作中的影响大小来评估参与方的贡献. 基于个体法简单、高效易理解地评估参与方贡献的特性, 在联邦学习参与方贡献评估相关问题中被广泛采用. 但是, 个体法未考虑到参与方组合在联邦合作中参与方对联邦带来的边际贡献情况, 因此个体法在很多情况下无法公平、有效地评估参与方对联邦的实际贡献程度. 比如, 某个参与方持有少量与其他参与方互补的数据, 能够对未被其他参与方覆盖到的关键测试场景准确率有提升, 但因为不包含基础测试场景常规数据, 导致该参与方数据单独训练局部模型的测试准确率不高, 被误判为低贡献.
留一法(leave one out)在机器学习任务中被广泛应用于交叉验证[
与个体法不同, 留一法完全遵循参与方组合数据价值度量范式, 即贡献评估与数据价值度量问题正交, 可以适用于第2节中所有的价值度量指标. 但是, 留一法只考虑了其他参与方全部保留下某个参与方为联邦所带来的边际收益, 这种指定参与方最后加入联邦来评估贡献的方式同样存在公平性问题. 比如, 当存在多个参与方持有相同但对联邦高价值的数据时, 移除掉持有该数据的参与方中任何一个均不会对联邦测试准确率带来显著影响, 这些参与方会被评估为低价值, 但同时, 移除这些参与方将大大降低联邦的性能.
1953年, 夏普利值(shapley value)被提出来以解决合作博弈问题[
其中,
其中,
● 合理性(group rationality): 联邦所有参与方均参与下的数据总价值应完全分配给所有参与方, 即:
● 对称性(symmetry): 两个在任何组合下边际增益均相等的参与方拥有相同的联邦贡献, 比如持有相同数据, 即
● 零贡献(zero element): 若某个参与方在任何组合下边际贡献均为0, 不能提升提升联邦的性能, 则该参与方的数据贡献为0, 即
● 可加性(additivity): 参与方的价值函数为多个指标的线性和时, 参与方的价值是这多个指标评估结果的线性和, 即
其中, 联邦合理性使得参与方贡献评估直接有效反映参与方在联邦价值指标上的贡献量, 比如对联邦合作测试准确率贡献的比例. 对称性和零贡献性质常被组合使用, 保证贡献评估结果客观基于价值度量指标, 而不区分不同参与方[
上述夏普利值是合作博弈理论中众多评估方案中的一种[
其中,
参与方贡献评估方案对比
合理性 | 对称性 | 零贡献 | 可加性 | 公平性 | 复杂度 | 优点 | 缺点 | |
个体法[ |
× | × | × | √ | × | O( |
简单、高效, 适用于 |
个体价值评估近似, |
留一法[ |
× | √ | √ | √ | × | O( |
适用于评估数据的 |
对数据相似的同质 |
夏普利值[ |
√ | √ | √ | √ | 个体 |
O(2 |
适用于跨机构联邦; |
复杂度高, 不适合 |
最小核[ |
√ | √ | √ | × | 组合 |
O(2 |
适用于跨机构联邦; |
复杂度高, 不适合 |
对比夏普利值和核最小核方法来看, 主要区别是夏普利值满足可加性而不满足稳定性, 最小核不满足可加性但满足稳定性. 可加性使得夏普利值在评估后线性地新增价值度量指标时, 不再需要额外对已完成评估的价值度量指标进行重复评估, 可以大大减少重复评估代价. 当评估任务能够一次性了解全部价值度量指标时, 可以将多个价值度量指标复合成单个价值函数, 这时, 对评估方案的可加性要求是不必要的. 另一方面, 夏普利值考虑了所有加入联邦次序下参与方的边际价值增益, 满足了个体层面的公平性; 最小核保证任何参与方子组合获得相对于组合数据价值应得的贡献评估并给予相应回报激励, 满足了任意参与方组合下的公平性, 即联邦稳定性. 如果从经济角度联邦(或者数据集市)的长远发展出发, 最小核方法的稳定性特性有助于联邦的长期稳定发展需要, 避免了某些参与方子组合为追求更大收益结对离开联邦的问题.
在实际应用中, 个体法虽然不够公平合理, 但由于其直观简洁特性等原因, 仍被部分工作采纳; 而留一法主要被当作测评基准方法; 同时满足公平合理性需求的夏普利值合作博弈方案比最小核方案应用更加广泛, 是目前联邦贡献评估主要被采取的方案; 而最小核方案仍在应用的初步测评阶段.
从理论角度来看, 结合数据价值度量指标(第2节)与参与方贡献评估方案(第3节)已经可以完成联邦贡献评估. 然而在实际应用中, 公平合理的贡献评估方案往往需要穷尽枚举所有可能的参与方组合并度量不同组合的数据价值, 比如针对不同组合数据训练并评测联邦模型, 这导致评估计算产生高昂的运算代价. 此外, 联邦贡献评估还需考虑如何抵御潜在恶意参与方的影响, 避免恶意参与方影响联邦模型性能.
贡献评估优化技术分类
● 统计采样优化: 夏普利值和最小核评估方案需要枚举指数级的参与方组合来评估参与方贡献, 可以通过统计采样, 随机采样少量参与方组合来近似计算贡献, 降低贡献评估计算复杂度[
● 联邦特性优化: 联邦学习贡献评估往往需要训练并评测模型, 这导致了高昂的数据价值度量代价, 通过复用模型训练梯度, 大大减少重复训练成本[
夏普利值和最小核评估方案在计算中需枚举2
上述贡献评估的近似计算方法保证了理论上所需的排列样本数量复杂度上限, 但实践中仍存在着采样方法收敛慢的问题, 尤其是在参与方数量众多的情况下. 实践中, 可以通过约束参与方排列采样结果的统计特性来进一步加速贡献近似计算的收敛速度.
● 结构化采样. 一种有效的随机采样优化策略是结构化采样. 其思想是调整随机采样样本, 使得被评估的参与方出现在排列中每个位置的样本数量相等[
● 引导排列采样. 结构化采样进一步演化出了引导排列采样, 相比之下, 引导排列采样不直接调整排列采样结果中参与方出现在各个位置的占比, 而是直接约束随机采样时各参与方出现在靠前位置的频次, 保证每个参与方在小样本采样中仍出现在排列靠前位置的频次相等, 借此实现了贡献评估近似计算的快速收敛[
上述两种约束排列采样的方法均可以优化小样本下的采样结果, 保证不同参与方出现在排列中前后不同位置的分布更加均匀, 使其更快地收敛于参与方的贡献真值, 有效地降低近似计算所需的排列样本数量.
在参与方数量庞大的场景下, 比如每条任务数据视为一个参与方或者每个终端设备的数据作为一个参与方时, 上述多项式复杂度的优化与加速排列采样收敛的方法仍需采样大量排列样本来实现较为准确的贡献评估. 为了进一步优化计算效率, 仅采样少量参与方进行联邦参与方贡献评估来优化评估效率, 并通过回归拟合的方式评估未被采样的参与方的贡献[
其中,
贡献评估往往需要计算不同参与方组合的数据价值, 然而模型相关的价值度量指标, 比如测试准确率, 需要基于数据重新训练并评测模型, 这导致了高昂的数据价值度量代价. 为了避免重复训练联邦模型的代价, 考虑复用全体参与方组合下训练联邦模型时各参与方的梯度更新, 避免在其他参与方子组合下训练模型时各参与方重复的梯度计算, 大大减少模型训练相关的代价[
为了提升每轮次仅采样部分参与方进行贡献评估的公平性, 观察到多轮次不同参与方组合价值构成的矩阵具有低秩特性, 可以将价值度量转换为采样下的低秩矩阵补全问题[
在联邦参与方贡献评估过程中, 从采样排列中参与方的边际价值增益、模型多轮次训练的性能提升和数据样本这3个层面, 均可以进行剪枝优化.
● 排列剪枝. 在贡献评估的随机采样优化中, 对于每个排列, 需要从前往后计算每个参与方加入前缀参与方组合带来的边际贡献. 在假定所有参与方的边际贡献非负的情况下, 排列从前往后引入新参与方的过程中, 前缀参与方组合的数据价值逐渐趋近于全体参与方组合的价值. 因此, 可以设置边际增益阈值, 当排列中参与方前缀组合的价值与全体参与方组合的价值差小于阈值时, 往后的参与方不会带来显著边际增益, 因此可以剪枝停止计算引入剩余参与方的组合数据价值, 有效地提升参与方数量庞大情况下的计算效率[
● 训练剪枝. 机器学习模型往往需要多轮次训练才能收敛, 为了降低数据估值任务中模型的训练代价, 不必像模型应用性能测评中一样, 尽可能地让模型收敛, 在模型性能提升波动小于一定程度时进行剪枝, 提早结束模型训练. 甚至为进一步提升联邦数据评估效率, 可以根据任务复杂度适当提升模型学习率, 仅进行单轮次模型训练[
● 数据剪枝. 基于局部相关特性, 联邦采用
在联邦学习实践中, 无法保证所有参与方均提供高价值无恶意的数据. 为了保证联邦学习效果, 抵御恶意参与方攻击是联邦学习的一个重要研究议题[
● 按贡献调整联邦参与程度. 根据参与方的贡献大小, 调整参与方在联邦训练中的参与程度. 在经典联邦学习中, 所有参与方在联邦合作中参与程度仅与数据量挂钩, 即基于FedAvg, 按照各参与方数据量加权聚合各参与方的梯度更新. 然而这种情况下, 低价值或者恶意参与方持有大量数据时会影响联邦模型训练效果. 因此, 可以计算每轮次中参与方的贡献大小, 基于贡献加权下一轮联邦训练各参与方的参与程度. 具体而言, 参与程度可以量化为参与更新联邦模型的参数比例[
● 设阈值移除低贡献参与方. 当不存在完备联邦测试集时, 可以根据参与方之间交叉验证来鉴定并移除低贡献参与方. 参与方交叉验证指的是每个参与方基于本地数据训练局部模型, 验证每个参与方模型在其他参与方数据上的测试准确率, 最终聚合参与方模型在其他参与方数据上验证的效果来评估该参与方的数据价值. 基于多数票决的设定, 如果某个参与方的局部模型在超过一定数量其他参与方的数据上验证效果小于某个阈值, 则认定该参与方为低价值或者恶意参与方, 将其移出联邦合作任务[
● 按贡献奖励不同任务模型. 在很多联邦学习设定中, 参与方参与联邦学习的目的是获取性能更高的任务模型, 因此, 可以通过贡献大小来奖励相应性能的任务模型来避免低价值或者恶意参与方. 实现参与方按贡献获得不同任务模型, 需要改变经典联邦学习中每轮次训练后联邦同步最新全局模型给每个参与方的设定. 实现方法是: 联邦根据不同参与方每轮次的贡献大小, 仅反馈给该参与方相应比例数量的参与方梯度更新[
参与方贡献评估工作对比(按年份先后排序)
年份 | 联邦 | 价值度量 | 贡献评估 | 时间复杂度 | 技术方法 | 工作特点 | |
Ref.[ |
2017 | HFL | 测试准确率 | 个体法 | O( |
影响函数 | 无须重复训练 |
SMC-Shapley[ |
2018 | HFL | 合成价值 | 夏普利值 | O( |
结构化 |
降低运算成本; |
LOO, Shapley[ |
2019 | HFL |
测试准确率 | 留一法 |
O( |
排列采样 | 同时考虑横纵联邦 |
GTB-Shapley[ |
2019 | HFL | 测试准确率 | 夏普利值 | 分组检验 | 理论复杂度更低, |
|
TMC-Shapley[ |
2019 | HFL | 测试准确率 | 夏普利值 | O( |
排列采样、 |
降低运算成本 |
OR, MR[ |
2019 | HFL | 测试准确率 | 夏普利值 | O( |
梯度复用、 |
降低运算成本; |
Influence[ |
2019 | HFL | 测试准确率 | 个体法 | O( |
影响函数、 |
降低计算成本; |
KNN-Shapley[ |
2019 | HFL | 测试准确率 | 夏普利值 | O( |
降低运算成本 | |
Ref.[ |
2019 | HFL | 参与方信誉 | 个体法 | O( |
主观逻辑 |
无需测试集 |
CFFL[ |
2020 | HFL | 测试准确率 | 个体法 | O( |
按贡献 |
降低低贡献 |
FOC[ |
2020 | HFL | 交叉熵损失 | 个体法 | O( |
评估数据 |
评估数据标签 |
FedSV[ |
2020 | HFL | 测试准确率 | 夏普利值 | O( |
参与方采样、 |
降低计算成本; |
DVRL[ |
2020 | HFL | 训练损失 | 个体法 | O( |
强化学习 | 无需测试集 |
D-Shapley[ |
2020 | HFL | 测试准确率 | 夏普利值 | O( |
参与方 |
不受参与方 |
Ref.[ |
2020 | HFL | 信息增益 | 夏普利值 | O( |
贝叶斯 |
无需测试集 |
Least Core[ |
2021 | HFL |
测试准确率 | 最小核 | O( |
组合采样 | 保证组合公平, |
RV[ |
2021 | HFL | 数据多样性 | 夏普利值 | O( |
格拉姆 |
无需测试集 |
CGSV[ |
2021 | HFL | 梯度相似度 | 个体法 | O( |
模型梯度 |
无需测试集 |
FedCCEA[ |
2021 | HFL | 测试准确率 | 个体法 | O( |
深度学习 | 拟合参与方 |
F-RCCE[ |
2021 | HFL | 测试准确率 | 个体法 | O( |
强化学习 | 拟合参与方 |
GTG-Shapley[ |
2021 | HFL | 测试准确率 | 夏普利值 | O( |
引导排列采样 | 加速收敛, |
FedValue[ |
2021 | VFL | 条件互信息 | 夏普利值 | O( |
信息论、安全计算 | 保障数据安全; |
Fed-PCA[ |
2021 | HFL | 参数相似度 | 个体法 | O( |
模型参数互信息 | 无需测试集 |
Ref.[ |
2021 | HFL | 测试准确率 | 夏普利值 | O( |
简单模型的解析解 | 降低计算成本 |
Ref.[ |
2021 | HFL | 测试准确率 | 夏普利值 | 联邦去中心化 | 移除联邦服务器 |
|
ComFedSV[ |
2021 | HFL | 测试准确率 | 夏普利值 | O( |
参与方采样、 |
降低计算成本 |
VerFedSV[ |
2022 | VFL | 测试准确率 | 夏普利值 | O( |
数据采样、 |
降低计算成本 |
如
贡献评估技术发展历程
参与方贡献评估作为激励参与方加入联邦的关键问题, 目前已有一些探索性研究工作, 但是现有工作在价值度量有效性和可靠性、贡献评估方案公平合理性、评估算法在联邦学习应用上的性能和安全性等问题上仍存在不足之处, 有待未来研究攻克这些挑战.
目前, 相关研究已经尝试了基于测试集的测试准确率、基于信息论的信息增益、模型相似度和数据统计特征等指标度量数据价值, 这些指标在所适应的联邦场景和价值度量的假设约束上各有优劣与不同, 未来数据估值指标设计与选择, 需从联邦场景设定和对数据与参与方的相关假设来综合考虑.
数据估值指标设计需明确其所适合的联邦场景, 明确价值度量在联邦场景中的泛化性和针对特定场景的性能提升之间的平衡取舍.
● 联邦类型: 明确价值度量在横向联邦、纵向联邦和横纵联邦这3种联邦类型的适应性. 目前, 仅有依赖测试集的测试准确率指标同时适合于横向与纵向联邦; 此外, 条件互信息指标适合于纵向联邦, 其他指标均只适用于横向联邦, 因此, 未来需要研究更多适用于纵向联邦或者适用于横纵联邦的通用指标.
● 任务相关性: 明确价值度量是否任务相关. 在明确联邦具体的分类或回归任务时, 可以针对相关任务特性的优化目标函数设计更加合理的估值指标. 而对于任务目标函数尚未完全明确或者对联邦聚合查询分析需求的任务来说, 可以考虑从数据统计指标、分布特性和时效性等角度切入, 量化联邦主观需求来设计复合指标的数据估值是未来可供探索的方向.
● 模型依赖: 明确价值度量是否依赖于具体联邦任务模型. 设计模型无关的数据估值指标可以有更大的应用场景与泛化性, 而设计任务模型依赖的指标, 比如
● 测试集依赖: 明确价值度量是否依赖并且多大程度上依赖于联邦测试集. 目前, 价值度量完全划分为测试集依赖与测试集无关的指标, 尚未有结合不完善联邦测试集的半监督价值度量指标. 此外, 测试集无关指标仍存在价值度量不合理的问题. 未来方法需要考虑实际中如何结合联邦的不完善测试集和参与方训练集来度量价值的问题. 另外, 设计测试集无关的指标时, 需考虑价值度量与任务性能的相关合理性与潜在假设.
设计数据估值指标需明确其对于参与方数据所服从分布的假设, 需要能够有效显著区分高低价值的数据, 在度量指标设计上需要严谨、可靠, 能够有效地抵御低价值或者恶意参与方的攻击.
● 数据分布假设: 明确数据估值指标是否依赖于参与方数据分布假设. 对联邦参与方数据分布的信息有充分了解, 能够简化数据价值度量, 比如, 假设所有参与方数据独立并来自统一分布时, 任务数据量达到能够完全反映数据统计分布规律前, 数据价值与数据量呈正相关; 达到足够完全反映数据统计分布规律后, 数据整体的价值不再随数据量升高.
● 价值度量标准: 明确数据估值指标, 能够有效地量化联邦对数据的诉求. 在联邦提供测试集场景时, 测试集的准确率即代表联邦对所需数据的诉求. 在未提供测试集或者测试集不完善的情况下, 价值度量应当反映联邦任务对数据统计指标和分布特性的需求, 不能简单凭借数据体量、分布多样性或者参与方之间的一致性来量化数据价值.
● 恶意参与方: 明确数据估值指标, 能够防御的攻击类型[
目前, 在联邦学习参与方贡献评估中, 夏普利值是被普遍采用的方案; 与夏普利值具备类似应用潜力的最小核法最近才被调研, 目前尚未得到充分关注与性能验证; 留一法通常被当作基准方法; 而个体法因为简单直观仍被广泛采用. 但是, 由于个体法评价基于参与方自身价值, 未从考虑参与方对联邦合作集体带来的边际贡献出发评估贡献, 因此一定程度上缺乏公平合理性. 此外, 夏普利值与最小核以外未被关注的其他合作博弈理论可能存在合适的贡献评估应用场景, 仍值得去探索. 未来贡献评估方案选择可考虑如下要点.
● 公平性: 评估方案对参与方贡献评估需要具备对称性、零贡献特性, 面向不同参与方个体或者组合的公平性, 需要充分考虑联邦场景下参与方为联邦合作带来的边际贡献, 即参与方的组合价值增益.
● 合理性: 参与方贡献评估结果中, 各参与方贡献评估之和为全体参与方联邦合作的组合数据价值, 其中可能存在某些参与方的贡献为负的情况.
● 其他性质: 评估方案具备其他有利于联邦贡献评估方案的性质, 比如价值度量指标的可加性、评估结果的稳定性等.
● 联邦场景: 明确贡献评估方案所适应的联邦场景设定. 经典的联邦学习场景是对多个地位对等的参与方的数据贡献进行评估, 然而实际中更常见的情况是参与方的出现有先后次序和不同地位权重的情况. 未来需要考虑这些新设定下的贡献评估方案探索, 比如联邦已有部分固定的参与方, 如何对新来的参与方进行公平合理的贡献评估.
联邦学习贡献评估问题是合作博弈理论在联邦学习主题上的延伸, 除保留了通用合作博弈问题的共性以外, 在联邦学习这个数据不动的分布式框架中有着很多问题的新特性, 比如在联邦学习场景中, 参与方组合数据价值度量代价更大, 存在数据隐私安全问题, 存在分布式环境中的同步、异步通信传输问题以及横纵联邦框架差异和后续的联邦激励等问题. 因此, 未来联邦学习贡献评估可考虑如下要点.
● 计算优化: 结合联邦学习的特性, 优化参与方贡献评估计算. 由于贡献评估往往需要验证不同参与方组合的价值, 而联邦学习多数价值度量指标需要重复训练和评测联邦模型, 因此, 如何在不损失评估准确性的前提下, 结合模型更新梯度、多轮次训练和联邦学习分布式等特性来优化贡献评估计算值得关注.
● 联邦激励: 结合其他激励要素, 综合优化联邦激励机制问题. 在完成参与方数据贡献评估后, 联邦基于参与方数据贡献、算力和参与时长等其他可量化因素, 对联邦参与方提供相应参与激励. 因此, 结合联邦参与方激励的其他因素来综合多目标优化参与方激励机制, 也是值得深入研究的方向.
● 横纵联邦: 针对横向联邦、纵向联邦与横纵混合联邦场景实现并优化贡献评估. 目前, 贡献评估研究大多分别考虑横向联邦和纵向联邦场景, 而现实中, 横纵混合联邦的情况更符合实际情况. 因此, 未来需要研究面向横纵混合联邦更通用的方案[
● 数据隐私安全: 联邦贡献评估需要谨慎、充分考虑方案中的潜在的数据隐私安全隐患. 目前, 大部分方案都假设数据安全问题可以依托相关技术解决, 但存在一些方法, 在设计角度对数据隐私安全缺乏考虑, 甚至需要移动参与方数据[
联邦学习框架联合不同数据持有方, 打破数据孤岛, 在保障数据安全的前提下, 赋能人工智能应用. 但是, 如何吸引高价值数据持有方加入联邦合作中来, 避免低价值、无价值和恶意参与方窃取联邦合作成果, 是联邦学习首先要解决的问题. 为此, 需要制定健全的联邦学习参与方贡献评估方案, 保证参与方在联邦参与中的数据贡献得到公平合理的评估, 使参与方根据其在联邦合作中的贡献获得应得的回报, 以推动联邦学习方案落地与长效发展.
本文综述了联邦学习的参与方贡献评估技术. 本文针对参与方贡献评估面临的数据价值度量有效性和可靠性、评估方案公平合理性和如何贡献评估计算优化等问题与挑战展开了综述. 本文分别调研了数据估值指标、参与方贡献评估方案和估计计算优化这3个方面的技术. 本文首先综述了如何设计有效而可靠的价值度量指标, 调研了在有无联邦测试集等多种联邦场景设定下的数据价值度量指标, 其中包括测试准确率、测试不确定性和数据统计指标等. 本文接下来综述了如何设计公平合理的贡献评估方案, 介绍并分析了夏普利值和最小核方案相对于个体法和留一法的优势, 并总结了评估方案所需的重要性质和适用场景. 此外, 本文综述了针对贡献评估固有的高计算复杂度等问题, 调研了如何进一步基于统计方法优化贡献评估计算问题、如何结合联邦学习特性来优化计算以及如何降低恶意参与方对联邦影响的问题. 最后, 本文讨论了联邦学习贡献评估目前仍面临的挑战, 并展望了未来研究工作的前进方向.
Economist T. The World's Most Valuable Resource is No Longer Oil, But Data. New York: The Economist, 2017.
Liu Y, Fan T, Chen T, Xu Q, Yang Q. Fate: An industrial grade platform for collaborative learning with data protection. Journal of Machine Learning Research, 2021, 22(226): 1-6.
Yang Q, Liu Y, Chen T, Tong Y. Federated machine learning: Concept and applications. ACM Trans. on Intelligent Systems and Technology (TIST), 2019, 10(2): 1-19.
Ritzberger K,
Jain A, Patel H, Nagalapatti L, Gupta N, Mehta S, Guttula S, Mujumdar S, Afzal S, Sharma Mittal R, Munigala V. Overview and importance of data quality for machine learning tasks. In: Proc. of the 26th ACM SIGKDD Int'l Conf. on Knowledge Discovery & Data Mining. 2020. 3561-3562.
Wahab OA, Mourad A, Otrok H, Taleb T. Federated machine learning: Survey, multi-level classification, desirable criteria and future directions in communication and networking systems. IEEE Communications Surveys & Tutorials, 2021, 23(2): 1342-1397.
Zhan Y, Zhang J, Hong Z,
Zeng R, Zeng C, Wang X, Li B, Chu X. A comprehensive survey of incentive mechanism for federated learning. arXiv: 2106.15406, 2021.
Pei J. A survey on data pricing: From economics to data science. IEEE Trans. on Knowledge and Data Engineering, 2020, 34(10): 4586-4608.
Cong Z, Luo X, Jian P, Zhu F, Zhang Y. Data pricing in machine learning pipelines. arXiv: 2108.07915, 2021.
Batini C, Cappiello C, Francalanci C, Maurino A. Methodologies for data quality assessment and improvement. ACM Computing Surveys (CSUR), 2009, 41(3): 1-52.
Gupta N, Mujumdar S, Patel H, Masuda S, Panwar N, Bandyopadhyay S, Mehta S, Guttula S, Afzal S, Sharma Mittal R,
Mothukuri V, Parizi RM, Pouriyeh S, Huang Y, Dehghantanha A, Srivastava G. A survey on security and privacy of federated learning. Future Generation Computer Systems, 2021, 115: 619-640.
Jia R, Wu F, Sun X, Xu J, Dao D, Kailkhura B, Zhang C, Li B, Song D. Scalability vs. utility: Do we have to sacrifice one for the other in data importance quantification? In: Proc. of the IEEE/CVF Conf. on Computer Vision and Pattern Recognition. 2021. 8239-8247.
Huang J, Talbi R,
McMahan B, Moore E, Ramage D, Hampson S, Arcas BA. Communication-efficient learning of deep networks from decentralized data. In: Proc. of the Artificial Intelligence and Statistics. 2017. 1273-1282.
Kairouz P, McMahan HB, Avent B, Bellet A, Bennis M, Bhagoji AN, Bonawitz K, Charles Z, Cormode G, Cummings R,
Ma S, Cao Y, Xiong L. Transparent contribution evaluation for secure federated learning on blockchain. In: Proc. of the IEEE 37th Int'l Conf. on Data Engineering Workshops (ICDEW). 2021. 88-91.
Cai H, Rueckert D, Passerat-Palmbach J. 2CP: Decentralized protocols to transparently evaluate contributivity in blockchain federated learning environments. arXiv: 2011.07516, 2020.
Shi Y, Yu H, Leung C. A survey of fairness-aware federated learning. arXiv: 2111.01872, 2021.
Asad M, Moustafa A,
Liu Y, Kang Y, Xing C,
Yang T, Andrew G, Eichner H, Sun H, Li W, Kong N, Ramage D, Beaufays F. Applied federated learning: Improving google keyboard query suggestions. arXiv: 1812.02903, 2018.
Zhang T, Gao L, He C, Zhang M, Krishnamachari B, Avestimehr S. Federated learning for internet of things: Applications, challenges, and opportunities. arXiv: 2111.07494, 2021.
Branzei R, Dimitrov D, Tijs S. Models in Cooperative Game Theory. Springer, 2008.
Chen Y, Yang X, Qin X,
Liu YX, Chen H, Liu YH, Li CP. Privacy-preserving techniques in federated learning. Ruan Jian Xue Bao/Journal of Software, 2022, 33(3): 1057-1092 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/6446.htm [doi: 10.13328/j.cnki.jos. 006446]
刘艺璇, 陈红, 刘宇涵, 李翠平. 联邦学习中的隐私保护技术. 软件学报, 2022, 33(3): 1057-1092. http://www.jos.org.cn/1000-9825/6446.htm [doi: 10.13328/j.cnki.jos.006446].
Feng S, Niyato D, Wang P, Kim DI, Liang YC. Joint service pricing and cooperative relay communication for federated learning. In: Proc. of the Int'l Conf. on Internet of Things (iThings) and IEEE Green Computing and Communications (GreenCom) and IEEE Cyber, Physical and Social Computing (CPSCom) and IEEE Smart Data (SmartData). 2019. 815-820.
Kang J, Xiong Z, Niyato D, Xie S, Zhang J. Incentive mechanism for reliable federated learning: A joint optimization approach to combining reputation and contract theory. IEEE Internet of Things Journal, 2019, 6(6): 10700-10714.
Pandey SR, Tran NH, Bennis M, Tun YK, Manzoor A, Hong CS. A crowdsourcing framework for on-device federated learning. IEEE Trans. on Wireless Communications, 2020, 19(5): 3241-3256.
Banica T, Curran S. Decomposition results for Gram matrix determinants. Journal of Mathematical Physics, 2010, 51(11): Article No. 113503.
Xu X, Wu Z, Foo CS,
Zhao B, Liu X, Chen W. When crowdsensing meets federated learning: Privacy-preserving mobile crowdsensing system. arXiv: 2102.10109, 2021.
Xu X, Lyu L, Ma X,
Lv H, Zheng Z, Luo T, Wu F, Tang S, Hua L, Jia R, Lv C. Data-free evaluation of user contributions in federated learning. In: Proc. of the 19th Int'l Symp. on Modeling and Optimization in Mobile, Ad hoc, and Wireless Networks (WiOpt). 2021. 1-8.
Sim RHL, Zhang Y, Chan MC, Low BKH. Collaborative machine learning with incentive-aware model rewards. In: Proc. of the Int'l Conf. on Machine Learning. 2020. 8927-8936.
Agarwal N, Suresh AT, Yu FXX, Kumar S, McMahan B. CPSGD: Communication-efficient and differentially-private distributed SGD. Advances in Neural Information Processing Systems 31. 2018.
Campen T, Hamers H, Husslage B, Lindelauf R. A new approximation method for the shapley value applied to the WTC 9/11 terrorist attack. Social Network Analysis and Mining, 2018, 8(1): 1-12.
Wang G, Dang CX, Zhou Z. Measure contribution of participants in federated learning. In: Proc. of the IEEE Int'l Conf. on Big Data (Big Data). 2019. 2597-2604.
Shyn SK, Kim D, Kim K. FedCCEA: A practical approach of client contribution evaluation for federated learning. arXiv: 2106. 02310, 2021.
Koh PW, Liang P. Understanding black-box predictions via influence functions. In: Proc. of the Int'l Conf. on Machine Learning. PMLR, 2017. 1885-1894.
Yan T, Procaccia AD. If you like shapley then you'll love the core. In: Proc. of the AAAI Conf. on Artificial Intelligence, Vol. 35. 2021. 5751-5759.
Jøsang A. Subjective Logic. Cham: Springer, 2016.
Lin J, Du M, Liu J. Free-riders in federated learning: Attacks and defenses. arXiv: 1911.12560, 2019.
Miller N, Resnick P,
Dasgupta A, Ghosh A. Crowdsourced judgement elicitation with endogenous proficiency. In: Proc. of the 22nd Int'l Conf. on World Wide Web. 2013. 319-330.
Zhao J, Zhu X, Wang J, Xiao J. Efficient client contribution evaluation for horizontal federated learning. In: Proc. of the IEEE Int'l Conf. on Acoustics, Speech and Signal Processing (ICASSP 2021). IEEE, 2021. 3060-3064.
Yoon J, Arik S, Pfister T. Data valuation using reinforcement learning. In: Proc. of the Int'l Conf. on Machine Learning. PMLR, 2020. 10842-10851.
Cook RD, Weisberg S. Characterizations of an empirical influence function for detecting influential cases in regression. Technometrics, 1980, 22(4): 495-508.
Richardson A, Filos-Ratsikas A,
Kearns M, Ron D. Algorithmic stability and sanity-check bounds for leave-one-out cross-validation. Neural computation, 1999, 11(6): 1427-1453.
Shapley LS. A value for
Dubey P. On the uniqueness of the shapley value. Int'l Journal of Game Theory, 1975, 4(3): 131-139.
Jia R, Dao D, Wang B, Hubis FA, Hynes N, Gürel NM, Li B, Zhang C, Song D, Spanos CJ. Towards efficient data valuation based on the shapley value. In: Proc. of the 22nd Int'l Conf. on Artificial Intelligence and Statistics. PMLR, 2019. 1167-1176.
Peleg B, Sudhölter P. Introduction to the Theory of Cooperative Games. Springer, 2007.
Schmeidler D. The nucleolus of a characteristic function game. SIAM Journal on Applied Mathematics, 1969, 17(6): 1163-1170.
Telser LG. The usefulness of core theory in economics. Journal of Economic Perspectives, 1994, 8(2): 151-164.
Deng X, Papadimitriou CH. On the complexity of cooperative solution concepts. Mathematics of Operations Research, 1994, 19(2): 257-266.
Castro J, Gómez D, Tejada J. Polynomial calculation of the shapley value based on sampling. Computers & Operations Research, 2009, 36(5): 1726-1730.
Balkanski E, Syed U, Vassilvitskii S. Statistical cost sharing. In: Advances in Neural Information Processing Systems 30. 2017.
Maleki S, Tran-Thanh L, Hines G, Rahwan T, Rogers A. Bounding the estimation error of sampling-based shapley value approximation. arXiv: 1306.4265, 2013.
Ghorbani A, Kim M, Zou J. A distributional framework for data valuation. In: Proc. of the Int'l Conf. on Machine Learning. PMLR, 2020. 3535-3544.
Du D, Hwang FK, Hwang F. Combinatorial Group Testing and Its Applications. World Scientific, 2000.
Liu Z, Chen Y, Yu H, Liu Y, Cui L. GTG-shapley: Efficient and accurate participant contribution evaluation in federated learning. arXiv: 2109.02053, 2021.
Rauhut H. Compressive sensing and structured random matrices. In: Fornasier M, ed. Theoretical Foundations and Numerical Methods for Sparse Recovery, Vol. 9. Berlin: De Gruyter, 2010.
Mitchell R, Cooper J, Frank E,
Maleki S. Addressing the computational issues of the Shapley value with applications in the smart grid [Ph. D. Thesis]. University of Southampton, 2015.
Kwon Y, Rivas MA, Zou J. Efficient computation and analysis of distributional shapley values. In: Proc. of the Int'l Conf. on Artificial Intelligence and Statistics. PMLR, 2021. 793-801.
Song T, Tong Y, Wei S. Profit allocation for federated learning. In: Proc. of the IEEE Int'l Conf. on Big Data (Big Data). IEEE, 2019. 2577-2586.
Wang T, Rausch J, Zhang C, Jia R, Song D. A principled approach to data valuation for federated learning. In: Proc. of the Federated Learning. Springer, 2020. 153-167.
Fan Z, Fang H, Zhou Z, Pei J, Friedlander MP, Liu C, Zhang Y. Improving fairness for data valuation in federated learning. arXiv: 2109.09046, 2021.
Fan Z, Fang H, Zhou Z, Pei J, Friedlander MP, Zhang Y. Fair and efficient contribution valuation for vertical federated learning. arXiv: 2201.02658, 2022.
Ghorbani A, Zou J. Data shapley: Equitable valuation of data for machine learning. In: Proc. of the Int'l Conf. on Machine Learning. PMLR, 2019. 2242-2251.
Jia R, Dao D, Wang B, Hubis FA, Gurel NM, Li B, Zhang C, Spanos CJ, Song D. Efficient task-specific data valuation for nearest neighbor algorithms. arXiv: 1908.08619, 2019.
Lyu L, Yu J, Nandakumar K, Li Y, Ma X, Jin J, Yu H, Ng KS. Towards fair and privacy-preserving federated deep models. IEEE Trans. on Parallel and Distributed Systems, 2020, 31(11): 2524-2541.
Lyu L, Xu X, Wang Q, Yu H. Collaborative fairness in federated learning. In: Proc. of the Federated Learning. Springer, 2020. 189-204.
Fraboni Y, Vidal R, Lorenzi M. Free-rider attacks on model aggregation in federated learning. In: Proc. of the Int'l Conf. on Artificial Intelligence and Statistics. PMLR, 2021. 1846-1854.
Han X, Wang L, Wu J. Data valuation for vertical federated learning: An information-theoretic approach. arXiv: 2112.08364, 2021.
Li Q, Wen Z, Wu Z,