基于Stackelberg博弈的異步聯(lián)邦學(xué)習(xí)激勵機制設(shè)計

摘? 要：聯(lián)邦學(xué)習(xí)作為能夠保護數(shù)據(jù)隱私和保證數(shù)據(jù)安全的新型分布式機器學(xué)習(xí)被廣泛關(guān)注，異步聯(lián)邦學(xué)習(xí)作為傳統(tǒng)聯(lián)邦學(xué)習(xí)的變種，能有效提高模型訓(xùn)練效率。激勵機制的引入能夠幫助異步聯(lián)邦學(xué)習(xí)有效提高模型訓(xùn)練效用。利用Stackelberg博弈構(gòu)建了一個聯(lián)邦學(xué)習(xí)激勵機制，分別對中心服務(wù)器和數(shù)據(jù)擁有者效用進行優(yōu)化。在此基礎(chǔ)上，推導(dǎo)出了整個博弈的均衡解，最后通過算例分析了模型的可行性，得到最優(yōu)的激勵效果。

關(guān)鍵詞：聯(lián)邦學(xué)習(xí)；Stackelberg博弈；魯棒優(yōu)化；數(shù)據(jù)質(zhì)量；納什均衡

中圖分類號：TP181；TP309 文獻標(biāo)識碼：A 文章編號：2096-4706（2023）24-0037-04

Design of Incentive Mechanism for Asynchronous Federated Learning Based on Stackelberg Game

LI Bingze

（School of Management Engineering and Business， Hebei University of Engineering， Handan? 056038， China）

Abstract： Federated Learning， as a new type of distributed machine learning that can protect data privacy and ensure data security， has received widespread attention. Asynchronous Federated Learning， as a variant of traditional Federated Learning， can effectively improve model training efficiency. The introduction of incentive mechanisms can help asynchronous Federated Learning effectively improve model training effectiveness. A federated learning incentive mechanism is constructed using the Stackelberg game， which optimizes the effectiveness of the central server and data owner. On this basis， we derive the equilibrium solution of the entire game， analyze the feasibility of the model through numerical examples finally， and obtain the optimal incentive effect.

Keywords： Federated Learning; Stackelberg game; Robust Optimization; data quality; Nash equilibrium

0? 引? 言

在過去幾十年中，隨著人工神經(jīng)網(wǎng)絡(luò)算法和云計算環(huán)境的發(fā)展，機器學(xué)習(xí)取得了前所未有的成功。盡管數(shù)據(jù)信息發(fā)展給生產(chǎn)發(fā)展帶來了許多便利，但同時數(shù)據(jù)安全和信息隱私也成為數(shù)據(jù)用戶關(guān)注的首要問題。用戶對數(shù)據(jù)隱私風(fēng)險更加謹(jǐn)慎，對系統(tǒng)中的交互信息更加敏感，希望個人隱私數(shù)據(jù)不會被泄露用作它用。各國開始提高對用戶個人隱私、商業(yè)機密、數(shù)據(jù)安全的重視程度。各項法規(guī)的建立、用戶隱私意識的提升對于傳統(tǒng)的分布式機器學(xué)習(xí)來說都是全新的挑戰(zhàn)。與此同時，隨著數(shù)據(jù)權(quán)利意識的提高，越來越多的實體強調(diào)數(shù)據(jù)的所有權(quán)和使用權(quán)，特別是在一些重點行業(yè)，如醫(yī)院、銀行等，并不允許彼此之間交換數(shù)據(jù)來進行機器學(xué)習(xí)。沒有用戶的同意，無法利用這些隱私數(shù)據(jù)來進行分析。這就造成了一種被稱為“數(shù)據(jù)孤島”的現(xiàn)象，它是指由于數(shù)據(jù)流通率降低，不同實體之間的數(shù)據(jù)無法有效地交流和共享，從而造成數(shù)據(jù)封閉和孤立的現(xiàn)象。這種現(xiàn)象的出現(xiàn)使得簡單的分布式機器學(xué)習(xí)無法有效解決大規(guī)模數(shù)據(jù)集的訓(xùn)練問題。

聯(lián)邦學(xué)習(xí)作為一種新興的分布式機器學(xué)習(xí)模型被提出[1]。聯(lián)邦學(xué)習(xí)被認(rèn)為是最有能力能夠突破“數(shù)據(jù)孤島”的機器學(xué)習(xí)模型，并受到了廣泛的關(guān)注[2]。異步聯(lián)邦學(xué)習(xí)作為傳統(tǒng)聯(lián)邦學(xué)習(xí)的變種，通過在不同設(shè)備上的本地模型參數(shù)的異步通信來實現(xiàn)模型的訓(xùn)練。與傳統(tǒng)聯(lián)邦學(xué)習(xí)不同，異步聯(lián)邦學(xué)習(xí)不需要等待所有設(shè)備完成本地訓(xùn)練之后再發(fā)送更新參數(shù)，從而可以更快地完成訓(xùn)練。目前，異步聯(lián)邦學(xué)習(xí)的相關(guān)研究主要考慮的是異質(zhì)性、異步聯(lián)邦模型優(yōu)化等問題[3]，為提高模型效率、確保模型有效性和保證隱私安全。然而，這些研究都是在一個樂觀的前提下，即所有的數(shù)據(jù)擁有者都會無條件參與和上傳更新參數(shù)到中心服務(wù)器中。但事實上，異步聯(lián)邦學(xué)習(xí)模型訓(xùn)練效果在很大程度上取決于數(shù)據(jù)擁有者所能提供的數(shù)據(jù)質(zhì)量，并且數(shù)據(jù)擁有者需要消耗大量的計算資源和通信資源，如果沒有一定的激勵，這些數(shù)據(jù)擁有者可能不愿意使用自己的數(shù)據(jù)來參與異步聯(lián)邦學(xué)習(xí)其中涉及多方參與且參與方之間在數(shù)據(jù)質(zhì)量方面的存在差異，導(dǎo)致數(shù)據(jù)擁有者不愿參與或不愿使其自身在參與聯(lián)邦學(xué)習(xí)時處于不公平的地位。因此設(shè)計激勵機制對異步聯(lián)邦學(xué)習(xí)系統(tǒng)推廣應(yīng)用至關(guān)重要，本文考慮引入Stackelberg博弈來設(shè)計異步聯(lián)邦學(xué)習(xí)激勵機制，對數(shù)據(jù)擁有者和任務(wù)發(fā)布者的效用都起到有效激勵作用。

1? 模型構(gòu)建

我們考慮由一個任務(wù)發(fā)布者和多個數(shù)據(jù)擁有者組成的異步聯(lián)邦學(xué)習(xí)如圖1所示。其中異步聯(lián)邦學(xué)習(xí)第一步將模型訓(xùn)練任務(wù)分發(fā)給不同的數(shù)據(jù)擁有者，每個數(shù)據(jù)擁有者獨立地運行本地訓(xùn)練，并在訓(xùn)練過程中周期性地將其本地模型更新發(fā)送給中心服務(wù)器。中央服務(wù)器收到這些更新后，可以將它們合并為一個全局模型，并對更新后的全局模型進行分析，重新給數(shù)據(jù)擁有者發(fā)送新的模型訓(xùn)練任務(wù)，每個設(shè)備都可以使用最新的全局模型根據(jù)新的訓(xùn)練要求來繼續(xù)本地訓(xùn)練。具體來說，在異步聯(lián)邦學(xué)習(xí)模型訓(xùn)練中，每個數(shù)據(jù)擁有者都將各自的私有數(shù)據(jù)存儲在本地，根據(jù)中心服務(wù)器設(shè)置的初始模型和參數(shù)要求，利用局部數(shù)據(jù)進行模型訓(xùn)練。在聯(lián)邦學(xué)習(xí)中，每個數(shù)據(jù)擁有者在完成本地模型訓(xùn)練任務(wù)后，將訓(xùn)練得到的模型參數(shù)傳回聯(lián)邦學(xué)習(xí)中心服務(wù)器。服務(wù)器聚合這些更新參數(shù)，以更新全局模型，并向數(shù)據(jù)擁有者下發(fā)新的迭代任務(wù)。數(shù)據(jù)擁有者需要按照要求持續(xù)迭代訓(xùn)練，直到達到目標(biāo)性能或預(yù)設(shè)的迭代次數(shù)。這種方式可以避免集中式訓(xùn)練中的數(shù)據(jù)隱私問題，同時加快了模型訓(xùn)練的速度。

假設(shè)每個數(shù)據(jù)擁有者n ∈ N擁有相同的局部數(shù)據(jù)樣本大小來參與聯(lián)邦學(xué)習(xí)。但每個數(shù)據(jù)擁有者使用不同的CPU周期頻率來訓(xùn)練局部模型fn。在完成一項數(shù)據(jù)訓(xùn)練的CPU周期數(shù)由cn來表示。因此，本地模型訓(xùn)練計算所需時間為Tn = （scn / fn），則在完成一次局部數(shù)據(jù)訓(xùn)練時CPU消耗能量為： [4]。數(shù)據(jù)擁有者的訓(xùn)練效率表示為λn，使用log（1 / λn）來表示局部訓(xùn)練的迭代次數(shù)，則全局迭代的模型更新計算時間為：。數(shù)據(jù)傳輸過程中，傳輸速率可以表示為：rn = B ln（1 + ρnhn / N0）），B為傳輸寬帶，ρn是數(shù)據(jù)擁有者的傳輸功率，hn是傳輸信道增益，N0是背景噪聲。則局部模型更新的傳輸時間為：

假設(shè)數(shù)據(jù)擁有者獲得報酬為Rn = qn fn，其中qn為數(shù)據(jù)擁有者使用CPU頻率fn工作的單位價格[5]。數(shù)據(jù)擁有者提供更多的計算資源，局部模型訓(xùn)練速度越快，從而獲得更高回報。數(shù)據(jù)擁有者可以隨意選擇簽署合同來完成聯(lián)邦學(xué)習(xí)任務(wù)。但如果不能按照所選合同完成聯(lián)邦學(xué)習(xí)工作，則不能得到既定報酬。

將任務(wù)發(fā)布者效用定為全局迭代時長：

當(dāng)數(shù)據(jù)擁有者n從任務(wù)發(fā)布者那里獲得相應(yīng)報酬Rn時，考慮到參與學(xué)習(xí)過程中產(chǎn)生的能量損耗，而其能量損耗取決于CPU的功率大小。因此對于每個數(shù)據(jù)擁有者而言，其目標(biāo)是使其自身利潤最大化，即：

該式受到fn≤fmax約束，其中fmax為數(shù)據(jù)擁有者CPU功率的上限，μ是預(yù)設(shè)的能量消耗權(quán)重參數(shù)。

2? 基于Stackelberg博弈的激勵機制求解

運用Stackelberg博弈構(gòu)建模型，下層博弈為：

上層博弈為：

一般而言，Stackelberg博弈的均衡可以通過找出其最優(yōu)的納什均衡來獲得。在本文構(gòu)建的博弈中，給定數(shù)據(jù)擁有者CPU功率的單價后，數(shù)據(jù)擁有者之間是非合作博弈關(guān)系，對于非合作博弈，納什均衡定義為沒有任何一個參與者可以通過改變自己的策略來提高收益。對于非合作博弈，若博弈滿足：1）博弈參與雙方集合有限。2）博弈的策略空間集合數(shù)據(jù)優(yōu)勢空間的有界閉集。3）非合作博弈的利潤函數(shù)在策略空間上是連續(xù)且滿足凹函數(shù)特性。則該博弈中存在納什均衡，每個博弈方的效用都會最大化，任何參與者都無法通過自私改變自身策略來獲得更高收益。本文構(gòu)建的博弈中，博弈的參與者數(shù)量有限，中心服務(wù)器所能提供的最優(yōu)CPU頻率單價都是歐式空間中的有界閉集合，并且下層博弈的效用函數(shù)隨自變量連續(xù)變化，利潤函數(shù)滿足凹函數(shù)特性。將下層博弈的利潤函數(shù)對CPU功率求一階導(dǎo)數(shù)和二階偏導(dǎo)數(shù)可知，二階偏導(dǎo)數(shù)結(jié)果為負，利潤函數(shù)滿足嚴(yán)格凹函數(shù)特性，因此該Stackelberg博弈模型存在子博弈納什均衡解。

對于上述構(gòu)建的博弈模型，我們考慮求得任務(wù)發(fā)布者與數(shù)據(jù)擁有者的Stackelberg均衡解問題。針對考慮未知數(shù)據(jù)質(zhì)量的Stackelberg博弈，利用反向歸納法來確定上下層博弈均衡解[6]。首先針對下層博弈，根據(jù)一階最優(yōu)性條件來求其均衡解。之后，將得到的下層均衡解帶入上層博弈中來尋求博弈解決方案。異步聯(lián)邦學(xué)習(xí)的Stackelberg博弈如圖2所示。

為求出數(shù)據(jù)擁有者在下層博弈中的均衡解，取下層博弈中的利潤函數(shù)對CPU功率fn進行一階求導(dǎo)可得：

令上述等式為零，可得到數(shù)據(jù)擁有者的CPU功率為：

首先將下層博弈達到均衡解時數(shù)據(jù)擁有者的最佳CPU功率替換到上層博弈的效用最大化問題中。因上層博弈問題的約束條件是線性的，因此采用拉格朗日法求解。優(yōu)化問題的拉格朗日函數(shù)為：

為了得到最優(yōu)解，對上述拉格朗日函數(shù)? 中的qn進行一階求導(dǎo)，并通過KKT條件得出拉格朗日乘子α在最佳點的值為：

對上層博弈的效用函數(shù)求一階導(dǎo)數(shù)可知，上層博弈效用函數(shù)與數(shù)據(jù)擁有者提供的CPU功率fn為負相關(guān)。任務(wù)發(fā)布者支付報酬時的CPU功率單位價格與數(shù)據(jù)擁有者提供的CPU功率之間為正相關(guān)。由此可知上述等式右側(cè)第一項為正，又因第二項恒為正，綜上可知，拉格朗日乘子α＞0恒成立。

結(jié)合上述KKT條件中：

可知：

因此根據(jù)KKT的互補松弛條件，該博弈的納什均衡解存在于邊界上。因此對于所有n ∈ N，上層博弈的均衡解為：

3? 數(shù)值分析

在仿真實驗中，我們使用MNIST數(shù)據(jù)集和廣泛使用的軟件環(huán)境TensorFlow來執(zhí)行數(shù)字分類任務(wù)，來評估上文構(gòu)建的激勵方案。在聯(lián)邦學(xué)習(xí)任務(wù)中，我們設(shè)置10個任務(wù)發(fā)布者和100個數(shù)據(jù)擁有者，其中數(shù)據(jù)擁有者按照數(shù)據(jù)質(zhì)量名義值不同均分為十種，并且所提供的數(shù)據(jù)質(zhì)量好壞存在不確定性。為了真實反映數(shù)據(jù)擁有者在本地訓(xùn)練模型時的異質(zhì)性，我們通過重復(fù)訓(xùn)練次數(shù)來對參與的數(shù)據(jù)擁有者進行隨機選擇。我們規(guī)定單個數(shù)據(jù)擁有者的最大CPU功率fmax為15，規(guī)定任務(wù)發(fā)布者提供的最大CPU頻率單位價格qmax為100。表1中給出了仿真實驗中的其他參數(shù)。

在本文中，上層博弈的效用為最小化全局迭代時長，我們將100個按照數(shù)據(jù)質(zhì)量分類的數(shù)據(jù)擁有者參與模型訓(xùn)練，通過求解其迭代時長均值來分析數(shù)據(jù)擁有者不同數(shù)據(jù)質(zhì)量對任務(wù)發(fā)布者效用的影響。如圖1所示，上下層博弈達到均衡最優(yōu)解時，隨著數(shù)據(jù)質(zhì)量的提高，數(shù)據(jù)擁有者提供的CPU頻率在不斷提高，并且任務(wù)發(fā)布者的模型全局迭代時長不斷降低，并且降低速度不斷變緩，任務(wù)發(fā)布者的模型全局迭代時長變化呈現(xiàn)擬凹性。造成這種現(xiàn)象的原因主要是由于隨著數(shù)據(jù)擁有者數(shù)據(jù)質(zhì)量的提升，數(shù)據(jù)擁有者自身為達到相同的模型精度的耗能降低，并且為了能夠使自身獲得更高的報酬，提高自身的CPU頻率，因此圖3、圖4中，隨著數(shù)據(jù)質(zhì)量的提升，數(shù)據(jù)擁有者的最優(yōu)CPU頻率在不斷提高，但由于數(shù)據(jù)質(zhì)量對模型計算時間的影響越來越小，使得數(shù)據(jù)擁有者提高CPU的幅度也在不斷變小。而任務(wù)發(fā)布者的全局迭代時長也隨著數(shù)據(jù)擁有者的最優(yōu)CPU頻率提高而不斷縮短，并且在最優(yōu)CPU頻率變化放緩時，任務(wù)發(fā)布者的模型全局迭代時長的降幅也在不斷變小。因此，在對異步聯(lián)邦學(xué)習(xí)中模型訓(xùn)練參與的數(shù)據(jù)擁有者進行選擇時，我們應(yīng)盡量選擇數(shù)據(jù)質(zhì)量較好，并且愿意提供將其用作模型訓(xùn)練的數(shù)據(jù)擁有者，以此來提高模型整體的訓(xùn)練效用，并且提高數(shù)據(jù)擁有者自身的報酬，降低能耗，從而達到雙方的相對最優(yōu)。

4? 結(jié)? 論

本文提出了一個基于Stackelberg博弈的異步聯(lián)邦學(xué)習(xí)激勵機制的設(shè)計來分析異步聯(lián)邦學(xué)習(xí)中任務(wù)發(fā)布者與不同數(shù)據(jù)擁有者之間的利益分配問題。我們所做的工作是將Stackelberg博弈引入激勵機制設(shè)計，將任務(wù)雙方的效用關(guān)系及相互作用過程能夠更好地體現(xiàn)，以此尋求任務(wù)發(fā)布者與數(shù)據(jù)擁有者參與雙方的相對最優(yōu)解。具體而言，我們首先根據(jù)異步聯(lián)邦學(xué)習(xí)的訓(xùn)練模型分別構(gòu)建了上下層博弈的效用目標(biāo)及約束，并分別對下層博弈和上層博弈的均衡解進行求解。通過模擬實驗證明和分析了不同數(shù)據(jù)質(zhì)量的數(shù)據(jù)擁有者對模型迭代全局時長和自身的最優(yōu)CPU頻率的影響。

本文僅考慮了理想狀態(tài)下異步聯(lián)邦學(xué)習(xí)的激勵機制設(shè)計，而現(xiàn)實情況中，可能存在數(shù)據(jù)質(zhì)量不確定，傳輸損耗等不確定因素。而這些因素也都會影響激勵機制對異步聯(lián)邦學(xué)習(xí)的效果，因此考慮存在不確定因素的基于Stackelberg博弈的異步聯(lián)邦學(xué)習(xí)激勵機制設(shè)計將是進一步的研究方向。

參考文獻：

[1] ROBERTS M，DRIGGS D，THORPE M，et al. Common pitfalls and recommendations for using machine learning to detect and prognosticate for COVID-19 using chest radiographs and CT scans [J].Nature Machine Intelligence，2021，3（3）：199-217.

[2] GONG L，LIN H，LI Z，et al. Systematically Landing Machine Learning onto Market-Scale Mobile Malware Detection [C]//EuroSys'20：Proceedings of the Fifteenth European Conference on Computer Systems，2020：1-14.

[3] YANG Q，LIU Y，CHEN T，et al. Federated Machine Learning：Concept and Applications [J].ACM Transactions on Intelligent Systems and Technology，2019，10（2）：1-19.

[4] LU Y，HUANG X，DAI Y，et al. Blockchain and Federated Learning for Privacy-Preserved Data Sharing in Industrial IoT [J].IEEE Transactions on Industrial Informatics，2020，16（6）：4177-4186.

[5] SATTLER F，WIEDEMANN S，MUELLER K，et al. Robust and Communication-Efficient Federated Learning From Non-i.i.d. Data [J].IEEE Transactions on Neural Networks and Learning Systems，2020，31（9）：3400-3413.

[6] WANG S，TUOR T，SALONIDIS T，et al. Adaptive Federated Learning in Resource Constrained Edge Computing Systems [J].IEEE Journal on Selected Areas in Communications，2019，37（6）：1205-1221.

作者簡介：李炳澤（1996.11—），男，漢族，山西運城人，碩士在讀，研究方向：不確定處理與決策。