基于Stackelberg博弈的異步聯(lián)邦學習激勵機制設計

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

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

中圖分類號：TP181；TP309 文獻標識碼：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? 引? 言

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

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

1? 模型構建

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

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

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

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

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

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

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

運用Stackelberg博弈構建模型，下層博弈為：

上層博弈為：

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

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

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

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

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

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

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

結合上述KKT條件中：

可知：

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

3? 數(shù)值分析

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

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

4? 結? 論

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

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

參考文獻：

[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—），男，漢族，山西運城人，碩士在讀，研究方向：不確定處理與決策。