[發(fā)明專利]基于面向聯(lián)邦學(xué)習(xí)參與用戶拍賣激勵(lì)機(jī)制的任務(wù)部署方法

有效

• 申請(qǐng)?zhí)枺?/td>: 202110717552.4
• 申請(qǐng)日: 2021-06-28
• 公開（公告）號(hào): CN113379294B
• 公開（公告）日: 2022-07-05
• 發(fā)明（設(shè)計(jì)）人: 周睿婷;龐金龍
• 申請(qǐng)（專利權(quán)）人: 武漢大學(xué)
• 主分類號(hào): G06Q10/06
• 分類號(hào): G06Q10/06;G06Q30/08;G06N20/20
• 代理公司: 武漢科皓知識(shí)產(chǎn)權(quán)代理事務(wù)所(特殊普通合伙) 42222
• 代理人: 羅飛

本發(fā)明公開了一種基于面向聯(lián)邦學(xué)習(xí)參與用戶拍賣激勵(lì)機(jī)制的任務(wù)部署方法，能夠在聯(lián)邦學(xué)習(xí)任務(wù)通信次數(shù)未知的情況下，對(duì)預(yù)參與聯(lián)邦學(xué)習(xí)任務(wù)訓(xùn)練的用戶進(jìn)行選擇和部署，以達(dá)到總社會(huì)成本最小化目的同時(shí)盡可能減小聯(lián)邦學(xué)習(xí)任務(wù)的通信次數(shù)。聯(lián)邦學(xué)習(xí)平臺(tái)運(yùn)營商根據(jù)本發(fā)明可以進(jìn)行挑選出合適的用戶并進(jìn)行部署，以謀得最小化成本。本發(fā)明結(jié)合了線性規(guī)劃建模。經(jīng)典的拍賣理論(Auction)和貪心算法等，從理論上證明了其有效性和合理性。本發(fā)明能夠在不需要知道單個(gè)聯(lián)邦學(xué)習(xí)任務(wù)的完成通信次數(shù)情況下，趨向最優(yōu)地對(duì)用戶進(jìn)行選擇和部署，達(dá)到讓滿足聯(lián)邦學(xué)習(xí)任務(wù)訓(xùn)練地同時(shí)最小化總成本。

技術(shù)領(lǐng)域

本發(fā)明涉及聯(lián)邦學(xué)習(xí)技術(shù)領(lǐng)域，具體涉及一種基于面向聯(lián)邦學(xué)習(xí)參與用戶拍賣激勵(lì)機(jī)制的任務(wù)部署方法。

背景技術(shù)

聯(lián)邦學(xué)習(xí)需要選取一定數(shù)量移動(dòng)設(shè)備(用戶)作為計(jì)算節(jié)點(diǎn)來參與聯(lián)邦學(xué)習(xí)任務(wù)訓(xùn)練。當(dāng)下，聯(lián)邦學(xué)習(xí)選取移動(dòng)設(shè)備(用戶)的方式一般為隨機(jī)選取，完全是處于一種理想狀態(tài)下進(jìn)行對(duì)移動(dòng)設(shè)備(用戶)的選取。但是這種選擇方式不適合于真正的聯(lián)邦學(xué)習(xí)用戶，原因如下：首先，不同移動(dòng)設(shè)備(用戶)參與聯(lián)邦學(xué)習(xí)任務(wù)訓(xùn)練并非出于自愿。移動(dòng)設(shè)備(用戶)參與聯(lián)邦學(xué)習(xí)訓(xùn)練需要消耗移動(dòng)設(shè)備電量和占用移動(dòng)設(shè)備一部分的時(shí)間。因此，移動(dòng)設(shè)備(用戶)會(huì)索要一定數(shù)量的金錢。其次，移動(dòng)設(shè)備(用戶)有自身的時(shí)間安排，即不一定能全程參與到聯(lián)邦學(xué)習(xí)任務(wù)訓(xùn)練當(dāng)中。這會(huì)影響聯(lián)邦學(xué)習(xí)任務(wù)的訓(xùn)練。

從一個(gè)聯(lián)邦學(xué)習(xí)平臺(tái)運(yùn)營商的角度出發(fā)，假設(shè)他有一個(gè)聯(lián)邦學(xué)習(xí)任務(wù)需要訓(xùn)練。聯(lián)邦學(xué)習(xí)平臺(tái)運(yùn)營商首先向所有的平臺(tái)用戶發(fā)布任務(wù)的信息。用戶接收到任務(wù)信息并向聯(lián)邦學(xué)習(xí)平臺(tái)運(yùn)營商提供競(jìng)價(jià)信息，以及指定的局部聯(lián)邦學(xué)習(xí)任務(wù)訓(xùn)練精度、可參與的總訓(xùn)練次數(shù)和可參與執(zhí)行任務(wù)的時(shí)間范圍。即使是不考慮用戶聯(lián)邦學(xué)習(xí)訓(xùn)練精度的前提下，對(duì)用戶進(jìn)行選擇和部署已經(jīng)是一個(gè)NP-hard問題。如果考慮一個(gè)更實(shí)際的情況，每個(gè)用戶指定了聯(lián)邦學(xué)習(xí)任務(wù)訓(xùn)練精度(現(xiàn)實(shí)中這些信息與移動(dòng)設(shè)備相關(guān)，一般需要指定)，要求聯(lián)邦學(xué)習(xí)平臺(tái)運(yùn)營商考慮聯(lián)邦學(xué)習(xí)任務(wù)的通信成本和計(jì)算成本的平衡問題，問題將會(huì)變得更加復(fù)雜。

由此可知，現(xiàn)有技術(shù)中聯(lián)邦學(xué)習(xí)任務(wù)部署的實(shí)現(xiàn)較為復(fù)雜。

發(fā)明內(nèi)容

有鑒于此，本發(fā)明提供了一種基于面向聯(lián)邦學(xué)習(xí)參與用戶拍賣激勵(lì)機(jī)制的任務(wù)部署方法，用以解決或者至少部分解決現(xiàn)有技術(shù)中的聯(lián)邦學(xué)習(xí)任務(wù)部署的實(shí)現(xiàn)較為復(fù)雜的技術(shù)問題。

本發(fā)明提供了一種基于面向聯(lián)邦學(xué)習(xí)參與用戶拍賣激勵(lì)機(jī)制的任務(wù)部署方法，包括：

步驟S1：聯(lián)邦學(xué)習(xí)平臺(tái)運(yùn)營商向所有的平臺(tái)用戶發(fā)布任務(wù)信息；

步驟S2：接收用戶基于任務(wù)信息后提交的用戶信息，用戶信息包括競(jìng)價(jià)信息、指定的局部聯(lián)邦學(xué)習(xí)任務(wù)訓(xùn)練精度、可參與的總訓(xùn)練次數(shù)以及可參與執(zhí)行任務(wù)的時(shí)間范圍；

步驟S3：聯(lián)邦學(xué)習(xí)平臺(tái)運(yùn)營商采用整數(shù)規(guī)劃對(duì)聯(lián)邦學(xué)習(xí)任務(wù)部署進(jìn)行建模，以最小化競(jìng)價(jià)價(jià)格為目標(biāo)，并構(gòu)建約束條件；

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

步驟S5：將上述固定通信次數(shù)下的決定勝者問題重新構(gòu)造，得到對(duì)應(yīng)的松弛整數(shù)約束下的對(duì)偶問題，對(duì)偶問題包括決策變量；

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