[發明專利]基于面向聯邦學習參與用戶拍賣激勵機制的任務部署方法

有效

• 申請號: 202110717552.4
• 申請日: 2021-06-28
• 公開（公告）號: CN113379294B
• 公開（公告）日: 2022-07-05
• 發明（設計）人: 周睿婷;龐金龍
• 申請（專利權）人: 武漢大學
• 主分類號: G06Q10/06
• 分類號: G06Q10/06;G06Q30/08;G06N20/20
• 代理公司: 武漢科皓知識產權代理事務所(特殊普通合伙) 42222
• 代理人: 羅飛

1.基于面向聯邦學習參與用戶拍賣激勵機制的任務部署方法，其特征在于，包括：

步驟S1：聯邦學習平臺運營商向所有的平臺用戶發布任務信息；

步驟S2：接收用戶基于任務信息后提交的用戶信息，用戶信息包括競價信息、指定的局部聯邦學習任務訓練精度、可參與的總訓練次數以及可參與執行任務的時間范圍；

步驟S3：聯邦學習平臺運營商采用整數規劃對聯邦學習任務部署進行建模，以最小化競價價格為目標，并構建約束條件；

步驟S4：根據訓練精度和通信次數的關系計算通信次數的范圍，根據不同的通信次數，挑選出能滿足聯邦學習訓練條件的競價信息并將步驟S3中的整數規劃問題分解成一系列的決定勝者問題，再依次計算不同固定的通信次數下的決定勝者問題的總社會成本，其中，總社會成本為所有已選擇用戶競價的競價價格的總和，決定勝者問題中滿足該問題的約束條件的集合為競價候選集合；

步驟S5：將上述固定通信次數下的決定勝者問題重新構造，得到對應的松弛整數約束下的對偶問題，對偶問題包括決策變量；

步驟S6：計算每個用戶競價添加之后的有效增加的參與完成訓練次數，基于有效增加的參與完成訓練次數計算每個用戶競價的有效平均成本，基于經典的貪心算法框架從競價候選集合選擇當前最低有效平均成本的用戶競價，同時更新決策變量，更新已選勝者集合和剩余可選競價集合，其中，已選勝者集合為記錄有當前已選擇的用戶的競價集合，剩余可選競價集合為去除已選擇的和不滿足條件的用戶競價之后的剩余可以選擇的用戶競價；

步驟S7：根據有效平均成本計算被選中的用戶競價的報酬；

步驟S8：判斷目前已選的用戶競價是否滿足聯邦學習任務每個階段的參與用戶需求，如果沒有滿足，則返回步驟S6繼續進行用戶競價的選擇，如果已經滿足，則執行步驟S9；

步驟S9：記錄每個已選擇的用戶競價的報酬和部署安排，并計算對應的決定勝者問題的總社會成本；

其中，步驟S3具體包括：

采用整數規劃對聯邦學習任務部署問題進行建模，其中目標函數為：

約束條件包括(1a)～(1h)：

T_g∈{1，2，...，T}. (1h)

其中，約束(1a)用以保證所有需訓練的通信階段的參與訓練用戶個數不小于K，其中未知變量y_i(t)表示被選擇的用戶是否被安排在第t個通信階段進行訓練，即當y_it為真時值為1，當y_i(t)為假時值取0，表示{1,2,…,T_g}范圍內t的可選集合；約束條件(1b)用以保障所有已選擇的用戶競價的訓練精度能滿足通信次數的要求，其中未知變量x_ij表示用戶競價是否被選擇，即當x_ij為真時值為1，當x_ij為假時值取0，表示{1,2,…,I}范圍內所有用戶i的可選集合，表示{1,2,…,J}范圍內所有用戶競價j的可選集合；約束條件(1c)用以保障被選擇用戶的總安排訓練次數等于可執行的總通信次數；約束條件(1d)用以保證當前選擇的用戶競價單個通信階段所需要的總時間不超過單個通信階段的時隙t_max，其中，表示總計算時間，T_l(θ_ij)表示訓練精度為θ_ij下的局部訓練次數且與訓練精度有如下關系：T_l(θ_ij)＝η·log(1/θ_ij)，表示單個局部訓練所需要的計算時間，表示單個通信階段所需要的通信時間,η表示一個常數型系數；約束條件(1e)表示變量x_ij和變量y_i(t)之間的約束關系，即當且僅當用戶競價被選擇時，才能被聯邦學習平臺運營商在其可執行通信階段范圍內部署訓練；約束條件(1f)表示每個用戶至多只能有一個競價被選擇；約束條件(1g)用以保障變量x_ij、變量y_i(t)的取值為0和1；(1h)用以保證變量T_g的取值在1和T范圍內；

步驟S4具體包括：

S4.1：根據公式(2)計算出通信次數的具體范圍，

其中，表示固定全局訓練精度ε的計算上界，θ_max表示所有已選擇用戶的最大局部訓練精度；

S4.2：利用(2)關系公式，通過計算所有用戶的提交競價的最小局部精度θ_min計算出通信次數的初始化最小值T₀，得到更精準的通信次數范圍[T₀,T]，通過排除一部分不滿足對應通信次數下的局部訓練精度條件的競價，從而挑選出合格的滿足上述約束(1b)和約束(1d)的競價候選集合

其中表示用戶i的第j個競價在單個通信階段內所需要的總時間；

S4.3：基于挑選出的合格的競價候選集合得出一系列決定勝者問題，描述如下：

subject to:

步驟S5具體包括：

S5.1：將公式(4)中的兩個決策變量x_ij和y_i(t)進行合并并用一個新的決策變量來表示z_il來表示，其中下標l表示具體的競價和其對應的部署方案，重構后的決定勝者問題描述為：

subject to:

其中，變量ρ_il表示用戶i的部署方案l所對應的競價價格約束條件(5a)等同于約束條件(1a),用以保證所有需訓練的通信階段的參與訓練用戶個數不小于K，約束條件等同于約束條件(1f),用以表示每個用戶至多只能有一個競價被選擇；

S5.2：對上述的決定勝者問題(5)進行對偶化，松弛整數約束下的對偶問題描述為：

subject to:

其中g(t)，λ_il，q_i分別為約束條件(5a)、(5b)和(5c)所對應的對偶變量，約束條件(6a)和(6b)用于約束對偶變量的取值范圍；

步驟S6包括：

S6.1：利用公式(7)計算每個用戶競價添加之后的有效增加的參與完成訓練次數：

其中，S＝{(i₁，l₁)，(i₂，l₂)，...}}，

表示當前所有已選擇用戶競價及其對應部署方案的集合；表示當前集合和(i，l)的并集；表示的總有效參與完成訓練次數；表示的總有效參與完成訓練次數；表示當前集合所有已選擇用戶被部署在第t個通信階段訓練的總數量；表示當前集合和(i，l)的并集中所有已選擇用戶被部署在第t個通信階段訓練的總數量；

S6.2：根據上述計算的每個用戶競價添加之后的有效增加的參與完成訓練次數，計算出每個用戶競價的有效平均成本，其中，有效平均成為：通過對比得出當前最低有效平均成本對應的部署方案(i^*，l^*)，計算公式描述為：

其中表示當前剩余的可選用戶競價集合，表示用戶i的第l個部署所對應第j競價的價格，代表用戶i的第l個部署所對應第j競價添加之后的有效增加的參與完成訓練次數；

S6.3：基于經典的貪心算法框架從競價候選集合選擇當前最低有效平均成本的用戶競價，得到部署方案(i^*，l^*)，更新對應的決策變量為1，同時更新集合為和(i^*，l^*)的并集，其中，為保證滿足約束條件(1f),可選集合將去除當前被選擇用戶i^*的所有競價。