一種基于反向多維拍賣模型的聯邦學習激勵機制

郭英蕓，高博，盧宇平，張煜，熊軻

1.北京交通大學計算機與信息技術學院，交通數據分析與挖掘北京市重點實驗室，智能高速鐵路系統前沿科學中心，北京，100044；2.國網能源研究院有限公司，北京，102209

0 引言

集中式機器學習方式需要移動用戶向服務器共享其數據，數據共享會破壞數據隱私，一旦數據遭到泄露，用戶將面臨嚴重的信息安全問題。此外，大量的數據傳輸會給網絡通信帶來壓力。聯邦學習[1]（Federated Learning，FL）能夠在保護數據隱私的情況下利用移動用戶的數據。目前，聯邦學習在醫療保健[2]、金融服務[3]等領域受到了廣泛關注，并取得了初步的研究成果。

但是，基于無線網絡的聯邦學習仍面臨一些挑戰。首先，一個聯邦模型的學習過程需要多次迭代，這意味著學習期間需要頻繁的網絡通信。為減少通信負擔，避免大量用戶同時使用網絡，只能選擇部分用戶作為訓練者參與訓練，為訓練用戶分配帶寬資源。其次，模型訓練會消耗用戶的資源，因此它們通常不愿主動參與服務器的訓練任務。為提高用戶的參與積極性，需要設計合理的激勵機制，以覆蓋其訓練過程產生的成本。最后，移動用戶在數據收集能力、計算能力、通信能力等多方面的差異性意味著用戶選擇方案將影響模型的訓練質量。因此，為了提高模型訓練質量，需要設計能夠準確評估用戶貢獻、進而選擇最佳訓練用戶并支付報酬的方案，同時優化帶寬資源的分配以降低通信時間。

為提高聯邦學習的性能，一些文獻從用戶選擇和資源分配角度開展工作：文獻[4]提出了一種結合用戶選擇的聯邦學習框架FedCS，它可以管理眾多資源異構的用戶，并解決具有約束的用戶選擇問題，加快了模型學習的速度；文獻[5]提出了一種基于bandit算法的用戶選擇策略UCBCS，該策略以更低的通信開銷實現更快的收斂，同時提高選擇的公平性；文獻[6]提出了一種有偏用戶選擇策略，根據選擇偏差對收斂速度的影響進行用戶選擇，實驗表明該方案有助于加快學習速度。在用戶選擇與帶寬分配聯合優化方面，文獻[7]提出了一種能夠權衡單輪收斂時間與全局迭代次數的聯合選擇與分配算法；文獻[8]提出了一種概率選擇方案，并設計了一種基于人工神經網絡的算法完成帶寬分配，實現了收斂時間與學習時間的平衡；文獻[9]提出了基于瞬時信道狀態和基于統計粒子群優化的兩種帶寬分配方案，達到了最大化參與用戶數量的目標。但是，上述工作都沒有考慮用戶自私的問題。

為激勵用戶參與聯邦學習，一些文獻以設計激勵機制的方式提高用戶的參與積極性。文獻[10]將多維信息歸納為一維選擇標準，并基于服務器對用戶信息的不同掌握程度分析了最佳的定價方案，解決了用戶與服務器間信息不對稱的問題。針對具有不同數據隱私保護需求的用戶，文獻[11]將用戶的貢獻和隱私成本進行了分類，并通過合同理論建立與隱私類型對應的支付機制。文獻[12]分析了異構用戶對聯邦學習收斂的影響，提出了一種基于主從博弈的激勵機制來平衡每次迭代的時間延遲。考慮用戶多維私人信息如訓練成本、通信時延、數據量等的不同，文獻[13]提出一個多維合同方法來設計服務器的最優激勵機制，通過求解不同數據量和通信能力的最佳獎勵，獲得最佳數據量和最短通信時間。文獻[14]通過中繼網絡構建了支持模型傳輸及自由交易的協作通信平臺，模型通過協作中繼網絡轉發給服務器，作為中繼節點的用戶可額外獲得報酬。上述工作雖然解決了激勵問題，但未考慮如何優化網絡資源的分配。

為綜合解決上述問題并提高聯邦學習質量，本文提出了一種基于反向多維拍賣的激勵機制，主要貢獻概括如下：

（1）設計了一種基于反向多維拍賣的激勵機制，同時解決服務器端用戶選擇、帶寬分配及報酬決策問題；

（2）通過解決社會福利函數最大化問題實現了用戶選擇，將帶寬分配納入激勵過程，進一步平衡了訓練時間，設計了一種保證用戶真實報價的支付方案；

（3）通過設計評分函數來選擇訓練用戶，該函數考慮了用戶在數據質量、訓練時間等方面的差異，并權衡了異構用戶的訓練質量、延遲和成本；

（4）將帶寬分配引入激勵過程，進一步平衡整體訓練時間和相關成本，提出了一種支持真實投標等必要經濟屬性的支付策略；

（5）證明了所提出的激勵機制滿足個體理性、激勵相容性和計算高效性等必要的經濟學屬性，仿真結果表明，與基線方案相比，所提出的IMRMA能夠有效提升訓練效果，加快收斂速度，降低訓練過程的整體時延。

1 系統模型與問題建模

1.1 IMRMA系統模型

如圖1所示，考慮包含一個中央服務器和個移動用戶的聯邦系統。在訓練任務開始之前，服務器和用戶需就訓練任務展開拍賣博弈。為了獲得更好的模型，服務器將綜合評價用戶，選擇最佳用戶作為模型訓練者。同時，服務器將對帶寬資源合理分配，并確定支付給用戶的報酬。具體地，首先由服務器根據訓練任務發起競價請求，向每個用戶廣播訓練任務及博弈過程的必要信息，其中與分別表示評分函數和數據質量評估函數，為最大時延限制，表示用戶單輪訓練時間上限。收到競價請求后，用戶需要就訓練過程的資源付出作出決策并計算投標。如果能夠滿足時延限制，則向服務器發送其投標；否則，不發送任何信息，默認放棄任務。收到用戶投標后，服務器進行用戶選擇、帶寬分配和支付決策，被選中的用戶為拍賣的贏家，即訓練用戶。

接下來服務器向訓練用戶發送初始模型，開始訓練過程。使用聯邦平均算法進行模型訓練[15]，首先由服務器向訓練用戶廣播全局模型，用戶收到后利用本地數據訓練并更新模型，訓練完成后將更新的本地模型上傳至服務器，之后服務器將所有本地模型聚合形成新的全局模型，至此完成一次模型的更新過程。更新過程將迭代多次，直到達到服務器規定的迭代次數或模型收斂。訓練任務完成后，服務器將按照拍賣階段的約定價格支付訓練用戶報酬。

1.2 社會福利與評分函數

為更好地描述用戶資源異構對訓練質量的影響，將訓練質量從訓練效果（精度）和訓練時間兩方面進行分析。

訓練效果與用戶的數據質量有很大關系，好的訓練數據往往帶來更高的學習精度。為了準確評估二者間的關系，基于MNIST數據集，進行聯邦學習仿真實驗，分析數據對訓練效果的影響。使用數據量On和非獨立同分布程度兩個指標描述用戶數據質量。使用推土機距離EMD（Earth Mover′s Distance）[19]將非獨立同分布程度定義為該用戶數據分布與自然社會中該數據集總體分布之間的差異，用戶n數據非獨立同分布程度定義為：，其中Porj表示數據中類樣本占其總樣本的比例。合理假設自然社會中該數據集的分布是獨立同分布的，即

將數據集按照不同的On與組合，進行蒙特卡洛實驗，分析數據量和非獨立同分布程度與訓練精度的關系，并根據實驗結果進行函數擬合。如圖2所示，圖中藍色部分為擬合結果。將擬合函數作為評價用戶數據質量的函數，并以數據質量作為用戶對訓練效果貢獻的衡量標準。擬合結果為，其中為擬合參數。

將模型學習過程分解為計算過程（模型訓練過程）和通信過程（模型傳輸過程），并進行公式化描述。將一次全局迭代中，用戶n的計算時間定義為：

用戶n的通信時間定義表示：

用戶n的訓練時間定義為：

由于用戶在拍賣結束前無法確定實際帶寬比例，故將在拍賣過程中的帶寬分配比例記為，相應地，將訓練時間記為。

結合數據質量和訓練時間，將用戶n對訓練質量的貢獻定義為，其中表示服務器對貢獻評估的權重參數。

將服務器的效用函數定義為：

用戶在訓練期間會由于消耗資源而產生成本，將其訓練成本分解為計算成本和通信成本。將一次全局迭代中，用戶n的計算成本定義為：

用戶n的通信成本定義為：

用戶n的訓練成本可表示為：

同樣地，將拍賣過程中用戶n的成本記為。

將用戶n的效用函數定義其報酬與訓練成本的差值：

拍賣中通常使用社會福利函數表示拍賣系統的性能。將本文所描述系統的社會福利函數定義為帶寬分配前所有訓練用戶和服務器的效用函數之和：。社會福利反映了系統中所有成員的收益之和，而邊際社會福利則反映了每個成員對系統的貢獻[20]。

定義用戶n的邊際社會福利函數為：

2 用戶與服務器拍賣決策

2.1 用戶：投入資源決策

在收到包含評分函數、數據質量評估函數和最大時延限制的競價請求后，用戶n通過最大化評分函數來決定其投入計算與通信資源：

定理1：問題sub-P1存在唯一最優解。

證明：問題sub-P1的一階導數為：

二階導數為：

定理2：問題sub-P2存在唯一最優解。

證明：問題sub-P2的一階導數為：

二階導數為：

令：

由擬凸函數[21]定義可知，為上的擬凸函數。通過對求導可得，又因時，為減函數，當時，為增函數，故當時該問題存在唯一最優解，故當時，問題sub-P2存在唯一最優解。

定理1和定理2證明了兩個子問題均有唯一最優解。問題sub-P1的最優解可通過凸優化理論中的一階最優性條件得到。定理2已證明sub-P2問題的單調性，可在定義域上通過二分查找法求得最優解。交替迭代求解問題sub-P1和問題sub-P2的最優解，直至結果收斂。具體求解過程如算法1所示。在求解前用戶n會預先判斷其最大資源能否滿足延遲要求，如果不能則不進行后續求解，該用戶退出拍賣。

2.2 服務器：拍賣策略與帶寬分配策略

收到全部用戶的投標后，服務器依次進行用戶選擇、帶寬分配及報酬確定。首先，服務器通過評分函數進行用戶選擇。由邊際社會福利函數和評分函數的定義可知，選擇評分最高的用戶便是選擇邊際貢獻最大的用戶，同時也是令社會福利最大的用戶。如算法2中“用戶選擇”所述，首先根據用戶投標計算用戶評分并降序排序：

之后，為保證拍賣的激勵相容性，需確保擬定用戶數K小于或等于評分大于0的用戶數K′。若，則調整，以保證激勵相容性。最后將評分最高的前K名用戶選作訓練者。

用戶選擇完成后進行帶寬分配。服務器期望通過帶寬分配降低時延，而系統時延取決于訓練用時最長的用戶，因此將帶寬分配問題定義如下：

可將原K維優化問題轉化為滿足公式（22）約束的1維優化問題：

詳細過程如算法2中“帶寬分配”，通過二分查找算法解決最小化時間問題，并計算最佳帶寬分配。

接下來證明所提出的拍賣方案滿足個體理性、激勵相容性及計算高效性。

定理3：IMRMA滿足個體理性。

定理4：IMRMA滿足激勵相容性。

證明：通過證明IMRMA滿足單調性與關鍵支付原則證明其滿足激勵相容性[22-23]。假設贏家用戶的投標為，其中為資源報價：為成本報價：

（1）單調性。當其他用戶不改變其策略時，用戶n以更好的投標參與競標時，其評分將滿足：，則此時用戶n的評分排名更靠前，故用戶仍可贏得拍賣。故滿足單調性。

（2）關鍵支付原則。當其他用戶不改變其策略時，用戶n以高于其真實投標所對應的報酬報告成本（即）時，有則有那么此時用戶n在公式（20）中的位置將在用戶之后，故用戶將成為第個K贏家，而用戶n將無法贏得拍賣。故滿足關鍵支付原則。得證滿足激勵相容性。

定理5：IMRMA滿足計算高效性。

證明：服務器的決策分三部分。用戶選擇的時間復雜取決于排序算法的時間復雜度；帶寬分配的時間復雜度為；報酬確定的時間復雜度為。故IMRMA的時間復雜度為，滿足多項式時間要求。得證滿足計算高效性。

3 實驗結果與分析

3.1 實驗設置

設置一個與基站相連的服務器，并在其100米范圍內隨機生成20個移動用戶，總帶寬B=5MHz，噪聲ZO=-114dBm。小尺度衰落為方差為1的瑞利分布，陰影衰落為標準差為8dBm的對數正態分布，路徑損耗模型為為基站與用戶發射端的歐幾里得距離。模型的大小為3.4×106bits，單位樣本大小為6272bits，處理單位比特所需CPU周期數，用戶數據量介于[100，1500]個之間，所有用戶數據均為非獨立同分布。基于MNIST數據集進行聯邦訓練任務，模型為帶有ReLu激活函數的三層全連接層網絡。

3.2 實驗結果與分析

首先，將所提出的IMRMA拍賣方案與資源無限的用戶選擇方案和隨機選擇用戶方案作比較，其中資源無限為理想狀態，網絡條件允許所有用戶參與訓練；隨機選擇用戶即按照傳統的聯邦平均算法隨機選擇K個用戶。圖3為在N=20，K=10設置下完成100次迭代的學習結果，可以看出，拍賣方案的訓練精度與理想狀態下的選擇方案相當。相比于隨機選擇方案，拍賣方案具有更高的收斂精度與更快的收斂速度。

為分析三種選擇方案在收斂速度方面的不同，以精度0.9為目標，統計了三種選擇方案測試精度達到0.9所需的迭代次數（設置最大迭代次數為250次）。結果如圖4所示，橫坐標代表實驗任務的重復次數。結果表明，相比于隨機選擇，IMRMA拍賣方案的收斂速度更接近理想狀態下的收斂速度，受環境中用戶隨機性的影響更小，整體更穩定。

為分析所提出的激勵方案中融入帶寬分配對系統訓練時間的影響，設置兩個對照組進行對比實驗：（1）平均帶寬分配；（2）隨機帶寬分配。對照組在決策過程中僅帶寬分配方式與IMRMA不同，完成用戶選擇后，平均分配方式將帶寬資源平均分配給訓練用戶，隨機分配方式將帶寬資源隨機分配給訓練用戶。進行了1000次重復實驗并取三種方式下單輪訓練時間的平均值，結果如圖5所示，可以看出，隨機分配的訓練時間最長，平均分配次之，以最小化單輪訓練時間為目標的分配方式訓練時間最短。每個學習任務都需要多次迭代方可達到收斂，因此三種選擇方案的時間差將會更大，故所提出的引入帶寬分配的激勵機制能夠有效降低訓練時間，提高學習效率。

4 結語

為解決聯邦學習中激勵與資源分配問題，本文設計了一種基于反向多維拍賣的激勵機制IMRMA。在IMRMA中，用戶通過最大化評分函數確定其資源貢獻，以提高其贏得拍賣的機會；服務器通過綜合考慮用戶的訓練數據、計算和通信能力及成本來選擇最佳訓練用戶以提高訓練質量，通過帶寬分配進一步優化訓練時延，通過合理的報酬確定方案保證用戶的誠實報價。最后，從理論上證明了IMRMA滿足必要的拍賣屬性，實驗結果表明，IMRMA可以有效地提高訓練精度，降低訓練時間。