基于主从博弈的分层联邦学习激励机制研究_贾云健.pdf
《基于主从博弈的分层联邦学习激励机制研究_贾云健.pdf》由会员分享,可在线阅读,更多相关《基于主从博弈的分层联邦学习激励机制研究_贾云健.pdf(8页珍藏版)》请在咨信网上搜索。
1、基于主从博弈的分层联邦学习激励机制研究贾云健黄宇梁靓*万杨亮周继华(重庆大学微电子与通信工程学院重庆400044)(95696部队重庆400030)(重庆金美通信有限责任公司复杂环境通信重庆市重点实验室重庆400030)摘要:为了优化分层联邦学习(FL)全局模型的训练时延,针对实际场景中终端设备存在自私性的问题,该文提出一种基于博弈论的激励机制。在激励预算有限的条件下,得到了终端设备和边缘服务器之间的均衡解和最小的边缘模型训练时延。考虑终端设备数量不同,设计了基于主从博弈的可变激励训练加速算法,使得一次全局模型训练时延达到最小。仿真结果显示,所提出的算法能够有效降低终端设备自私性带来的影响,提
2、高分层联邦学习全局模型的训练速度。关键词:分层联邦学习;博弈论;激励机制中图分类号:TN92文献标识码:A文章编号:1009-5896(2023)04-1366-08DOI:10.11999/JEIT220175Research on Hierarchical Federated Learning IncentiveMechanism Based on Master-Slave GameJIAYunjianHUANGYuLIANGLiangWANYangliangZHOUJihua(School of Microelectronics and Communication Engineering
3、,Chongqing University,Chongqing 400044,China)(95696 Troops,Chongqing 400030,China)(Chongqing Key Laboratory of Complex Environment Communication,Chongqing Jinmei CommunicationCo.Ltd.Chongqing 400030,China)Abstract:InordertooptimizethetrainingdelayofthehierarchicalFederatedLearning(FL)globalmodel,foc
4、usingontheselfishnessoftheterminaldevicesintheactualscene,anincentivemechanismbasedongametheoryisproposed.Undertheconditionoflimitedincentivebudget,theequilibriumsolutionbetweenterminaldevicesandedgeserversandtheminimumedgemodeltrainingdelayareobtained.Consideringthedifferentnumberofterminaldevices,
5、avariableincentivetrainingaccelerationalgorithmbasedonStackelberggameisdesignedtominimizethetrainingdelayofaglobalmodel.Simulationresultsdemonstratethattheproposedalgorithmcaneffectivelyreducetheimpactofterminaldevicesselfishnessandimprovethetrainingspeedofhierarchicalfederatedlearningglobalmodel.Ke
6、y words:HierarchicalFederatedLearning(FL);Gametheory;Incentivemechanism1 引言随着各种智能设备的不断普及,依赖数据和计算能力的机器学习技术得到了迅速发展。为了解决机器学习模型训练面临的数据安全问题,2017年谷歌提出了一种新的分布式机器学习方法联邦学习(FederatedLearning,FL)1。在联邦学习的架构中,设备用户的原始数据不会上传至数据中心,而是留在设备本地进行模型训练,设备只上传训练出的模型参数2。联邦学习将机器学习与在中心服务器中获取、存储和训练数据分离开来,实现了用户数据隐私保护3。自从谷歌提出联邦学习
7、这个概念后,联邦学习就成为机器学习领域的一个研究热点。McMahan等人4提出了一个基于模型平均的联邦学习实用模型,并进行了广泛的实证评估,这篇文章提出的联收稿日期:2022-02-25;改回日期:2022-06-27;网络出版:2022-08-16*通信作者:梁靓基金项目:国家自然科学基金(62071075,61971077),重庆市自然科学基金(cstc2020jcyj-msxmX0704)FoundationItems:TheNationalNaturalScienceFoundationofChina(62071075,61971077),TheNaturalScienceFounda
8、tionofChongqing(cstc2020jcyj-msxmX0704)第45卷第4期电子与信息学报Vol.45No.42023年4月JournalofElectronics&InformationTechnologyApr.2023邦平均算法(FederatedAveragealgorithm,FedAvg)成为一个经典的联邦学习算法。在此基础上,研究者针对FedAvg算法优化,进行了一系列研究。Li等人5在FedAvg的基础上引入了一个修正项,提出了FedProx(FedAvgwiththeProximalterm)算法,它允许在设备之间局部地执行可变量的工作,并且依赖这个修正项来确
9、保方法的稳定性,解决了联邦学习固有的系统异质性和统计异质性问题。Mills等人6采用分布式Adam优化技术和模型压缩技术,提出了一种改进的FedAvg算法CE-FedAvg(Communication-EfficientFedAvg),该算法可以减少达到目标精度所需的通信轮次和每一轮需要加载的数据量,解决了联邦学习在物联网边缘计算的高效通信问题。Li等人7则从算法的公平性角度出发,提出了q-FairFL算法,它重新权衡了FedAvg算法中的目标函数,在损失函数中分配更高的权重给损失较高的设备,从而使训练精度分布更加均匀。为了进一步优化联邦学习的性能,有研究者对传统联邦学习框架进行了改进。Liu
10、等人8将基于边缘和基于云的联邦学习结合起来,提出了分层联邦学习架构,该分层联邦学习架构与基于云的联邦学习架构相比,模型训练时间和终端设备的能耗都得到了降低。Abad等人9通过分簇法研究了在蜂窝网中的分层联邦问题,优化了分层联邦学习的全局通信时延。然而不管是针对传统联邦学习框架还是分层联邦学习框架,目前已有的研究大多集中在优化联邦学习算法以提高模型训练性能上,用于激励终端设备参加模型训练的激励机制在很大程度上却被忽视了。大多数流行的分布式训练算法都是使用小批量随机梯度下降10,这在实际训练中,需要等待每一个同步批次中最慢的设备,导致随机优化的完全同步往往很慢,即受到“掉队效应”11的影响,这在异
11、构网络中更为明显。同时,目前的大多数研究都做出了一个乐观的假设,即所有的终端设备在受到邀请时,都将无条件地参与联邦学习。这在现实世界中是不实际的,因为在联邦模型训练过程中,终端设备在计算和通信方面承受着相当大的开销12,如果没有精心设计的激励机制,具有自私性的终端设备将不会拿出足够的资源甚至不愿意加入到联邦学习任务中来,这将导致十分严重的“掉队效应”,使得模型的训练时间大大增加,影响联邦学习的使用。针对上述问题,本文在分层联邦学习框架下,考虑实际场景中每个边缘服务器下连接的终端设备数量不同,首先对模型训练过程进行了建模分析,得出一次全局模型训练的时间消耗和资源消耗。然后在终端设备和边缘服务器之
12、间设计了两层主从博弈(即Stackelberg博弈13),通过调整分配给每个边缘服务器的激励预算值,提出了基于主从博弈的可变激励训练加速算法。该算法能够刺激终端设备更加积极地参与到联邦学习的任务中来,有效地减小“掉队效应”的影响,从而最小化全局模型训练时间。2 系统模型CN=i:i=1,2,.,NiMi=m:m=1,2,.,M如图1所示在分层FL架构中,假设有一个云服务器,边缘服务器集合为,边缘服务器 下连接的终端设备集合为,每个终端设备集合大小不相同。考虑完全同步的FL,完成一次全局训练过程如下:m (0,1)m终端设备端。终端设备基于本地的数据集来进行本地模型训练,假设所有的终端设备的本地
13、数据集大小相同,为了达到相同的本地模型精度,终端设备需要进行迭代的次数可以表示为14L()=log2(1)(1)fi:mimCmL()im其中,是一个取决于数据集大小和机器学习任务的参数。表示边缘服务器 下的终端设备进行本地计算时的CPU频率,表示完成1次本地迭代计算任务需要的总的CPU转圈数。那么完成次本地迭代,边缘服务器 下的终端设备所消耗的能量和时间可以分别表示为ecmpi:m=L()kCm(fi:m)2(2)tcmpi:m=L()Cmfi:m(3)kiqi:mimmqi:mfi:m其中,是一个取决于芯片结构的系数。为了使终端设备投入更多的计算资源以减小本地训练模型所花的时间,边缘服务器
14、端会引入激励机制,即边缘服务器 向其下面的终端设备提供奖励,表示边缘服务器 对其服务范围内的终端设备提供的CPU频率单价,那么终端设备迭代一次获得的收入为。本地模型精度达到 之后,终端设备图1系统模型图第4期贾云健等:基于主从博弈的分层联邦学习激励机制研究1367B向对应的边缘服务器上传训练得到的参数。假设每个边缘服务器能够分配给终端设备的信道总带宽均为,边缘服务器将其均分给下面的每一个终端设备,那么传输率可以表示为rmi=Bmlog2(1+hmumN0)(4)N0umhmmi其中,为噪声功率,为传输功率,为信道增益。终端设备完成一次参数传输至边缘服务器所需要的时间为tcommi=dmrmi(
15、5)dmm其中,表示终端设备传输的参数量,所需要的能量为ecommi=tcommium(6)i边缘服务器端。边缘服务器 在收到终端设备传来的参数后,会进行聚合然后再分发下去。以上的过程会迭代多次,直到所有的边缘服务器达到一个相同边缘服务器模型精度。为了达到所需精度,对于一个凸的机器学习任务,边缘服务器需要迭代的次数可以表示为14I(,)=(log2(1)1 (7)iI(,)其中,是取决于学习任务的参数。由于边缘服务器通常拥有强大的计算能力和稳定的能量供给,所以边缘服务器端的模型参数聚合和分发所产生的时间与能量消耗在本文中没有考虑。对于终端设备来说,接收分发下来的参数所消耗的时间和能量相比于它上
16、传参数要小得多,在这里本文也不予考虑。因此,边缘服务器 完成次迭代,所需要的时间为Ti=I(,)maxmMi(tcmpi:m)+tcommi(8)m终端设备消耗的总能量为Ei:m=I(,)(ecmpi:m+ecommi)(9)ridi边缘服务器会向云服务器上传满足精度要求的边缘服务器模型参数,假设边缘服务器的传输率都为,上传的参数量为,那么上传1次参数,边缘服务器的时间和能量消耗分别为tcomiC=diri(10)ecomiC=uitcomiC(11)ui其中,表示边缘服务器的传输功率。云服务器端:在接收到边缘服务器端传来的模型参数后,云服务器端进行参数聚合并更新模型,这样就完成了一次全局迭代
17、。相较于其他环节,这个聚合时间非常短,本文也不考虑。那么,一次全局迭代,所需要的总时间为T=maxiNTi+tcomiC(12)ViWii1TiiRciRc1Ti云服务器负责分配激励预算给每个边缘服务器,总预算为。边缘服务器 所分配到的激励预算为。定义边缘服务器 对于一次全局迭代的时间贡献度为,时间贡献度越大,表示边缘服务器 迭代到所要求的精度的时间越短。云服务器会基于每个边缘服务器的时间贡献度来给予边缘服务器奖励,云服务器端总的奖励为,边缘服务器 从云服务器端获得的奖励定义为。3 基于主从博弈的激励机制3.1 博弈问题定义imqi:m=qi:1,qi:2,.,qi:mfi:m=fi:1,fi
18、:2,.,fi:mqi:mim本文考虑信息对称场景,即每个终端设备会在训练开始前向其所连接的边缘服务器报告自己能够提供的最大算力、本地数据集大小等先验信息。在终端设备层和边缘服务器层之间引入主从博弈(即Stackelberg博弈)。将终端设备作为跟随者(follower),边缘服务器作为领导者(leader)。边缘服务器 决定给每个终端设备的CPU频率单价。根据报价,每个边缘服务器服务范围内的各个终端设备向其报告自己用于参与训练的CPU频率,然后边缘服务器再调整单价。边缘服务器 下的终端设备的效用函数可以表示为Ui:m=I(,)L()qi:mfi:m Ei:m(13)mi其中,第1项为终端设备
19、完成一次全局迭代获得的激励奖励,第2项为总的计算和传输能耗。系数用于匹配效用函数前后两项的数量级。边缘服务器 的效用函数可以表示为Ui=Rc1TimMiqi:mfi:m ecomiC(14)iii其中,第1项为边缘服务器 从云服务器获得的奖励,第2项为边缘服务器 向下面的终端设备支出的激励总和,第3项为边缘服务器 上传参数的传输能耗。Wi博弈框架如图2所示。首先明确引入激励机制的目的是减小完成一次全局迭代的时间。云服务器作为激励预算分配者(Allocator),负责为每个边缘服务器分配用于激励的预算,然后每个边缘服务器和其服务范围内的终端设备形成1个博弈簇,进行Stackelberg博弈。在1
20、个博弈簇内,每个终端1368电子与信息学报第45卷m Miimi设备根据边缘服务器 的激励报价,决定自己投入训练任务的CPU频率,从而最大化自己的效用函数。故会产生个下层子博弈问题。边缘服务器 根据其服务范围内的所有终端设备的CPU频率投入情况,再重新调整自己给出的激励报价,最大化自己的效用函数。故产生一个上层子博弈问题。一个博弈簇内上下两层子博弈反复进行,直到达到纳什均衡点。下层子博弈问题定义为maxfi:mUi:m=I(,)L()qi:mfi:m Ei:ms.t.fmini:m fi:m fmaxi:m(15)上层子博弈问题定义为maxqi:mUi=Rc1TimMiqi:mfi:m eco
21、miCs.t.mMiqi:mfi:m WiiNWi V|(16)3.2 博弈均衡解分析3.2.1 下层子博弈求解Ui:m为了找到下层子博弈的均衡解,首先对求1阶导数,可以得到Ui:mfi:m=I(,)L()qi:m 2I(,)L()kCmfi:m(17)因为2Ui:mf2i:m=2I(,)L()kCm 0(18)Ui:m所以是严格凹的,保证了纳什均衡解存在且唯一。可得均衡解为fi:m(qi:m)=maxqi:m2kCm,fmaxi:m(19)3.2.2 上层子博弈求解iRc1TimMiqi:mfi:mecomiCecomiC边缘服务器 的效用函数式(14)由3部分组成,(1),(2),(3)。
22、由前面系统模型的描述中可知,可视为一个常量,所以下面分析(1)和(2)的凹凸情况。h=Rc1Tifi:m分析(1),令并代入可得表达式h(qi:m)=Rc1I(,)maxmMi(2kC2mL()/qi:m)+tcommi(20)h(qi:m)的黑塞矩阵定义为A=|2hq2i:1.2hqi:1qi:m.2hqi:mqi:1.2hq2i:m|(21)由于2hq2i:m=4kRcL()I(,)2C2mtcommi(2kL()I(,)C2m+I(,)tcommiqi:m)3(22)2hqi:mqi:n=0(m=n)(23)h(qi:m)所以的黑塞矩阵可进一步表示为A=|4kRcL()I(,)2C2mt
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 基于 主从 博弈 分层 联邦 学习 激励机制 研究 贾云健
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。