法律状态公告日
法律状态信息
法律状态
2022-07-05
授权
发明专利权授予
技术领域
本发明涉及联邦学习技术领域，具体涉及一种基于面向联邦学习参与用户拍卖激励机制的任务部署方法。
背景技术
联邦学习需要选取一定数量移动设备(用户)作为计算节点来参与联邦学习任务训练。当下，联邦学习选取移动设备(用户)的方式一般为随机选取，完全是处于一种理想状态下进行对移动设备(用户)的选取。但是这种选择方式不适合于真正的联邦学习用户，原因如下：首先，不同移动设备(用户)参与联邦学习任务训练并非出于自愿。移动设备(用户)参与联邦学习训练需要消耗移动设备电量和占用移动设备一部分的时间。因此，移动设备(用户)会索要一定数量的金钱。其次，移动设备(用户)有自身的时间安排，即不一定能全程参与到联邦学习任务训练当中。这会影响联邦学习任务的训练。
从一个联邦学习平台运营商的角度出发，假设他有一个联邦学习任务需要训练。联邦学习平台运营商首先向所有的平台用户发布任务的信息。用户接收到任务信息并向联邦学习平台运营商提供竞价信息，以及指定的局部联邦学习任务训练精度、可参与的总训练次数和可参与执行任务的时间范围。即使是不考虑用户联邦学习训练精度的前提下，对用户进行选择和部署已经是一个NP-hard问题。如果考虑一个更实际的情况，每个用户指定了联邦学习任务训练精度(现实中这些信息与移动设备相关，一般需要指定)，要求联邦学习平台运营商考虑联邦学习任务的通信成本和计算成本的平衡问题，问题将会变得更加复杂。
由此可知，现有技术中联邦学习任务部署的实现较为复杂。
发明内容
有鉴于此，本发明提供了一种基于面向联邦学习参与用户拍卖激励机制的任务部署方法，用以解决或者至少部分解决现有技术中的联邦学习任务部署的实现较为复杂的技术问题。
本发明提供了一种基于面向联邦学习参与用户拍卖激励机制的任务部署方法，包括：
步骤S1：联邦学习平台运营商向所有的平台用户发布任务信息；
步骤S2：接收用户基于任务信息后提交的用户信息，用户信息包括竞价信息、指定的局部联邦学习任务训练精度、可参与的总训练次数以及可参与执行任务的时间范围；
步骤S3：联邦学习平台运营商采用整数规划对联邦学习任务部署进行建模，以最小化竞价价格为目标，并构建约束条件；
步骤S4：根据训练精度和通信次数的关系计算通信次数的范围，根据不同的通信次数，挑选出能满足联邦学习训练条件的竞价信息并将步骤S3中的整数规划问题分解成一系列的决定胜者问题，再依次计算不同固定的通信次数下的决定胜者问题的总社会成本，其中，总社会成本为所有已选择用户竞价的竞价价格的总和，决定胜者问题中满足该问题的约束条件的集合为竞价候选集合；
步骤S5：将上述固定通信次数下的决定胜者问题重新构造，得到对应的松弛整数约束下的对偶问题，对偶问题包括决策变量；
步骤S6：计算每个用户竞价添加之后的有效增加的参与完成训练次数，基于有效增加的参与完成训练次数计算每个用户竞价的有效平均成本，基于经典的贪心算法框架从竞价候选集合选择当前最低有效平均成本的用户竞价，同时更新决策变量，更新已选胜者集合和剩余可选竞价集合，其中，已选胜者集合为记录有当前已选择的用户的竞价集合，剩余可选竞价集合为去除已选择的和不满足条件的用户竞价之后的剩余可以选择的用户竞价集合；
步骤S7：根据有效平均成本计算被选中的用户竞价的报酬；
步骤S8：判断目前已选的用户竞价是否满足联邦学习任务每个阶段的参与用户需求，如果没有满足，则返回步骤S6继续进行用户竞价的选择，如果已经满足，则执行步骤S9；
步骤S9：记录每个已选择的用户竞价的报酬和部署安排，并计算对应的决定胜者问题的总社会成本。
在一种实施方式中，在步骤S9之后，所述方法还包括：
判断通信次数的范围内所有通信次数的总社会成本是否都已获得；
如果不是都已获得，则返回步骤S5，否则对比所有已计算的通信次数下决定胜者问题的总社会成本，选择对应最小总社会成本的通信次数作为最终值，同时告知用户任务部署安排和报酬。
在一种实施方式中，步骤S3具体包括：
采用整数规划对联邦学习任务部署问题进行建模，其中目标函数为：
约束条件包括(1a)～(1h)：
T
其中，约束(1a)用以保证所有需训练的通信阶段的参与训练用户个数不小于K，其中未知变量y
在一种实施方式中，步骤S4具体包括：
S4.1：根据公式(2)计算出通信次数的具体范围，
其中，
S4.2：利用(2)关系公式，通过计算所有用户的提交竞价的最小局部精度θ
其中
S4.3：基于挑选出的合格的竞价候选集合
subject to:
在一种实施方式中，步骤S5具体包括：
S5.1：将公式(4)中的两个决策变量x
subject to:
其中，变量ρ
S5.2：对上述的决定胜者问题(5)进行对偶化，松弛整数约束下的对偶问题描述为：
subject to：
其中g(t)，λ
在一种实施方式中，步骤S6包括：
S6.1：利用公式(7)计算每个用户竞价添加之后的有效增加的参与完成训练次数：
其中，
S6.2：根据上述计算的每个用户竞价添加之后的有效增加的参与完成训练次数，计算出每个用户竞价的有效平均成本，其中，有效平均成为：ρ
其中
S6.3：基于经典的贪心算法框架从竞价候选集合选择当前最低有效平均成本的用户竞价，得到部署方案(i
在一种实施方式中，步骤S7包括：
S7.1：找出次最低有效平均成本的用户竞价(i′，l′)，计算公式描述为：
S7.2：计算用户i
其中
本申请实施例中的上述一个或多个技术方案，至少具有如下一种或多种技术效果：
本发明公开的基于面向联邦学习参与用户拍卖激励机制的任务部署方法，能够在联邦学习任务通信次数未知的情况下，对预参与联邦学习任务训练的用户进行选择和部署，以达到总社会成本最小化目的同时尽可能减小联邦学习任务的通信次数。联邦学习平台运营商根据本发明可以进行挑选出合适的用户并进行部署，以谋得最小化成本。
进一步地，本发明结合了线性规划建模。经典的拍卖理论(Auction)和贪心算法等，从理论上证明了其有效性和合理性。本发明能够在不需要知道单个联邦学习任务的完成通信次数情况下，趋向最优地对用户进行选择和部署，达到让满足联邦学习任务训练地同时最小化总成本。
附图说明
为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对实施例或现有技术描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他的附图。
图1是本发明实施例的概念流程图。
图2a和图2b是本发明实施例实验结果图。
图3a～3e是本发明实施例和其他现有算法结果的实验结果对比图。
具体实施方式
本发明的目的在于提供一种基于面向联邦学习参与用户拍卖激励机制的任务部署方法，用以改善现有技术中的联邦学习任务部署的实现较为复杂的技术问题。
为了解决上述技术问题，本发明的主要构思如下：
提供一种高效面向联邦学习参与用户的拍卖激励机制。用户接收到联邦学习平台发布的任务信息后，并联邦学习平台运营商提供竞价信息，以及指定的局部联邦学习任务训练精度、可参与的总训练次数和可参与执行任务的时间范围。联邦学习平台运营商通过算法来合理地选择参与用户，并将具体报酬和部署安排告知给用户。首先对问题进行建模(用线性规划来描述该问题)，然后基于经典的贪心算法框架来选择和部署移动设备(用户)。
为使本发明实施例的目的、技术方案和优点更加清楚，下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有作出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。
本实施例提供了基于面向联邦学习参与用户拍卖激励机制的任务部署方法，包括：
步骤S1：联邦学习平台运营商向所有的平台用户发布任务信息；
步骤S2：接收用户基于任务信息后提交的用户信息，用户信息包括竞价信息、指定的局部联邦学习任务训练精度、可参与的总训练次数以及可参与执行任务的时间范围；
步骤S3：联邦学习平台运营商采用整数规划对联邦学习任务部署进行建模，以最小化竞价价格为目标，并构建约束条件；
步骤S4：根据训练精度和通信次数的关系计算通信次数的范围，根据不同的通信次数，挑选出能满足联邦学习训练条件的竞价信息并将步骤S3中的整数规划问题分解成一系列的决定胜者问题，再依次计算不同固定的通信次数下的决定胜者问题的总社会成本，其中，总社会成本为所有已选择用户竞价的竞价价格的总和，决定胜者问题中满足该问题的约束条件的集合为竞价候选集合；
步骤S5：将上述固定通信次数下的决定胜者问题重新构造，得到对应的松弛整数约束下的对偶问题，对偶问题包括决策变量；
步骤S6：计算每个用户竞价添加之后的有效增加的参与完成训练次数，基于有效增加的参与完成训练次数计算每个用户竞价的有效平均成本，基于经典的贪心算法框架从竞价候选集合选择当前最低有效平均成本的用户竞价，同时更新决策变量，更新已选胜者集合和剩余可选竞价集合，其中，已选胜者集合为记录有当前已选择的用户的竞价集合，剩余可选竞价集合为去除已选择的和不满足条件的用户竞价之后的剩余可以选择的用户竞价集合；
步骤S7：根据有效平均成本计算被选中的用户竞价的报酬；
步骤S8：判断目前已选的用户竞价是否满足联邦学习任务每个阶段的参与用户需求，如果没有满足，则返回步骤S6继续进行用户竞价的选择，如果已经满足，则执行步骤S9；
步骤S9：记录每个已选择的用户竞价的报酬和部署安排，并计算对应的决定胜者问题的总社会成本。
具体来说，本发明采用的拍卖激励机制以及涉及的信息包括：一个联邦学习平台运营商需要训练一个联邦学习任务，其中任务的训练精度需要达到ε值且训练的通信次数不超过T。同时，每个通信阶段至少需要K个用户参与训练。有I个用户提交了其竞价信息给联邦学习平台运营商，其中每个用户提交了J种竞价方式：竞价价格b
联邦学习平台运营商在得到全部用户的竞价信息之后，开始为联邦学习任务选择和部署移动设备(用户)，并将最终的拍卖结果、部署安排和报酬告知给用户。移动设备(用户)则依据联邦学习平台的个人部署方案来参与联邦学习任务训练。联邦学习平台运营商通过对用户的激励、选择和部署来平衡计算成本和通信成本，来使得总社会成本最小化。
请参见图1，本发明实施例提供的概念流程图，其中的相关参数包括步骤S6中的决策变量以及已选胜者集合和剩余可选竞价集合。
在一种实施方式中，步骤S3具体包括：
采用整数规划对联邦学习任务部署问题进行建模，其中目标函数为：
约束条件包括(1a)～(1h)：
T
其中，约束(1a)用以保证所有需训练的通信阶段的参与训练用户个数不小于K，其中未知变量y
具体来说，本发明采用的拍卖激励机制的目的是，在满足真实性竞价和条件约束的情况下，对用户提交的竞价进行选择和部署)，以最小化总社会成本。
在一种实施方式中，步骤S4具体包括：
S4.1：根据公式(2)计算出通信次数的具体范围，
其中，
S4.2：利用(2)关系公式，通过计算所有用户的提交竞价的最小局部精度θ
其中
S4.3：基于挑选出的合格的竞价候选集合
subject to:
具体实施过程中，为了减小计算复杂度，本发明反向利用(2)关系公式，通过计算所有用户的提交竞价的最小局部精度θ
在一种实施方式中，步骤S5具体包括：
S5.1：将公式(4)中的两个决策变量x
subject to:
其中，变量ρ
S5.2：对上述的决定胜者问题(5)进行对偶化，松弛整数约束下的对偶问题描述为：
subject to:
其中g(t)，λ
具体来说，步骤S5是将步骤S4中的固定通信次数下的决定胜者问题重新构造，并写出对应的松弛整数约束下的对偶问题。在得出上述的决定胜者的优化问题(4)后，通过将上述两个决策变量x
在一种实施方式中，步骤S6包括：
S6.1：利用公式(7)计算每个用户竞价添加之后的有效增加的参与完成训练次数：
其中，
S6.2：根据上述计算的每个用户竞价添加之后的有效增加的参与完成训练次数，计算出每个用户竞价的有效平均成本，其中，有效平均成为：
其中
S6.3：基于经典的贪心算法框架从竞价候选集合选择当前最低有效平均成本的用户竞价，得到部署方案(i
具体来说，当计算初每个用户竞价添加之后的有效增加的参与完成训练次数后，则可以计算出每个用户竞价的有效平均成本，描述为：
在一种实施方式中，步骤S7包括：
S7.1：找出次最低有效平均成本的用户竞价(i′，l′)，计算公式描述为：
S7.2：计算用户i
其中
具体来说，为了给当前被选择用户竞价的一定的报酬同时保证报酬不小于用户竞价的价格，本发明以次最低有效平均成本来计算报酬。因此，首先需要找到次最低有效平均成本的用户竞价(i′，l′)。
在计算出被选中的用户竞价的报酬之后，执行步骤S8：判断目前已选的用户竞价是否满足联邦学习任务每个阶段的参与用户需求。若是需求尚未满足，需要继续选择用户的竞价，返回步骤S6。若是已经满足条件，则进入步骤S9。
由于整个联邦学习任务需要保证每个通信阶段都需要有至少K个用户参与训练。因此，需要满足的条件和需求就是
在一种实施方式中，在步骤S9之后，所述方法还包括：
判断通信次数的范围内所有通信次数的总社会成本是否都已获得；
如果不是都已获得，则返回步骤S5，否则对比所有已计算的通信次数下决定胜者问题的总社会成本，选择对应最小总社会成本的通信次数作为最终值，同时告知用户任务部署安排和报酬。
具体实施过程中，记录每个已选择的用户竞价的报酬p
本发明研究了联邦学习平台运营商如何激励、选择和部署移动设备用户来参与联邦学习任务训练来平衡联邦学习参与用户的计算成本和通信成本，来使得总社会成本最小化
为了便于本领域普通技术人员理解和实施本发明，下面结合具体示例进行说明，在本示例中，设置了联邦学习平台训练任务的最大通信次数为50，且每个通信阶段需要20个用户参与训练。其中每个通信阶段的时隙为60分钟。联邦学习平台共有1000个移动设备(用户)，其中每个用户提交5个竞价。每个用户竞价的竞价价格在[10，50]内随机选取；局部训练精度服从[0.3，0.8]范围的均匀分布；随机选择10个[1，T]范围内的随机数来组成每个用户竞价的可执行通信阶段，且每个用户竞价的可执行的总通信次数在1到对应的可执行通信阶段长度(d
图2a和图2b是本发明实施例实验结果图。图3a～3e是本发明实施例和其他现有算法结果的实验结果对比图。
附图中的相关字符和英文表示的解释如下：
#of Global iterations：表示不同的全局通信次数；
Performance ratio of A
#of bids per client：表示单个移动设备(用户)的竞价数量；
Number of winners：表示目前已挑选用户的数量；
Payment：表示给当前已选择用户的报酬；
Cost：表示当前已选择用户的竞价价格；
Number of clients：表示移动设备(用户)的数量；
Number of bids per client：表示单个移动设备(用户)的竞价数量；
Performance ratio：表示其中算法得到的最小总社会成本与最优社会成本的比率；
A
FCFS：用于衡量设计算法的优劣的对比算法；
Greedy：用于衡量设计算法的优劣的对比算法；
A
A
A
A
A
A
Running time(Seconds)：表示算法执行时间，单位为秒。
应当理解的是，本说明未详细阐述的部分均属于现有技术，上述针对较佳实施例的描述较为详细，并不能因此而认为是对本发明专利保护范围的限制，本领域的普通技术人员在本发明的启示下，在不脱离本发明权利要求所保护的范围情况下，还可以做出替换或变形，均落入本发明的保护范围之内，本发明的请求保护范围应以所附权利要求为准。
