張富春，朱孔林,2

(1.北京郵電大學(xué) 人工智能學(xué)院，北京 100876；2.紫金山實驗室，江蘇 南京 211111)

0 引言

群體智能(Swarm Intelligence,SI)起源于對社會性昆蟲，如螞蟻、蜜蜂等的群體行為的研究，具有分布式和自組織性等特征[1]。群體中的個體基于環(huán)境狀態(tài)而動，通過與環(huán)境的智能交互形成整個群體的智能。在機器學(xué)習(xí)領(lǐng)域，人們通過相關(guān)的機器學(xué)習(xí)算法讓群體中的個體采取不同的行為，并根據(jù)從環(huán)境中獲得的反饋來優(yōu)化其個體行為，使得個體獲得智能進而實現(xiàn)群體智能。未來的各種智能節(jié)點可能廣泛分布于端邊云各處，通過無線網(wǎng)絡(luò)連接在一起，并通過一定的群體智能算法來實現(xiàn)群體智能。

集群學(xué)習(xí)[2](Swarm Learning,SL)作為一種分布式的機器學(xué)習(xí)具有群體智能的部分特征，它通過無線網(wǎng)絡(luò)連接若干智能節(jié)點，以去中心化的方式來訓(xùn)練深度神經(jīng)網(wǎng)絡(luò)。典型的SL系統(tǒng)由各種智能節(jié)點以及連接各節(jié)點的無線網(wǎng)絡(luò)組成。在實際的系統(tǒng)中，各個智能節(jié)點自主完成模型訓(xùn)練，并通過無線網(wǎng)絡(luò)來共享模型參數(shù)。

本文主要關(guān)注這種分布式機器學(xué)習(xí)系統(tǒng)中的節(jié)點選擇問題，即如何決定每一輪由哪些節(jié)點參與模型的訓(xùn)練才能使整體訓(xùn)練效率最高，同時還要保證每個節(jié)點的能量消耗不超過對應(yīng)上限。之所以每一輪要選擇部分節(jié)點參與訓(xùn)練，是因為這種分布式的機器學(xué)習(xí)系統(tǒng)中參與訓(xùn)練的節(jié)點數(shù)量達到一定規(guī)模后，再增加節(jié)點數(shù)量帶來的整體收益增幅越來越小[3]。

SL系統(tǒng)的節(jié)點選擇并非一個簡單的問題。首先，系統(tǒng)中的節(jié)點受到能量限制，每個節(jié)點都有一個長期的能量上限。其次，由于SL系統(tǒng)中的節(jié)點所持有的數(shù)據(jù)集、物理硬件各不相同，不恰當?shù)墓?jié)點選擇可能會對訓(xùn)練效果產(chǎn)生負面影響[4]。最后，SL系統(tǒng)中的各個節(jié)點通常是通過無線網(wǎng)絡(luò)相互連接，而無線網(wǎng)絡(luò)狀態(tài)通常是時變的，因此需要考慮無線網(wǎng)絡(luò)質(zhì)量對模型參數(shù)傳輸?shù)挠绊憽?/p>

本文采用李雅普諾夫優(yōu)化[5](Lyapunov Optimization)管理各節(jié)點的能量消耗以使總能耗不超過長期的能量上限，并結(jié)合組合多臂賭博機[6-12](Combinatorial Multi-Armed Bandit,CMAB)動態(tài)感知各節(jié)點的性能狀況與無線網(wǎng)絡(luò)狀態(tài)，綜合多種信息選擇合適的節(jié)點組合參與模型訓(xùn)練。

1 相關(guān)工作

本節(jié)對相關(guān)工作進行分類和討論，然后指出本文工作與它們的不同之處。與SL系統(tǒng)中的節(jié)點選擇問題直接相關(guān)的文獻極少，而與之高度相關(guān)的問題是聯(lián)邦學(xué)習(xí)中的客戶端節(jié)點選擇問題，相關(guān)文獻總結(jié)如下：

文獻[13]使用節(jié)點反饋的信息(例如無線信道狀態(tài)、算力資源以及與當前訓(xùn)練任務(wù)相關(guān)的數(shù)據(jù)資源的大小)來估計模型下載、更新和上傳所需的時間，并設(shè)計了一種基于上述時間的算法，以在規(guī)定的時間內(nèi)使盡可能多的節(jié)點參與模型訓(xùn)練，并將問題建模為0～1背包問題使用貪婪(greedy)算法求解。類似的文獻[14]以CPU、內(nèi)存和能量等的“資源效用函數(shù)”為約束，并基于線性回歸對其進行預(yù)測。通過證明，其問題可以簡化為經(jīng)典的背包問題，并使用貪婪算法在每一輪中盡可能多地選擇滿足資源效用約束的節(jié)點來求解。

文獻[15]考慮了節(jié)點的能量上限和無線信道條件。該工作采用了李雅普諾夫優(yōu)化，定義虛擬能量隊列來管理節(jié)點的能量消耗，并定義了基于節(jié)點的數(shù)據(jù)集大小和虛擬能量隊列的效用函數(shù)。該工作定義的問題是在帶寬限制的約束下最大化效用函數(shù)的優(yōu)化。通過基于隊列長度和信道增益的“選擇優(yōu)先級”來確定每一輪選擇哪些節(jié)點。文獻[16]也考慮了帶寬限制的問題，并且更加關(guān)注無線資源分配問題，定義了節(jié)點的“經(jīng)驗損失函數(shù)”，并將其問題建模為帶寬受限的隨機優(yōu)化問題。通過引入李雅普諾夫優(yōu)化，將原問題轉(zhuǎn)化為在線問題并在每一輪求解隨機優(yōu)化問題。

文獻[17]考慮了訓(xùn)練時延、節(jié)點可用性和選擇的公平性，設(shè)計了基于訓(xùn)練時延的獎勵函數(shù)，在CMAB的理論框架下對問題進行轉(zhuǎn)化并使用經(jīng)典CMAB算法—UCB1[18]求解。文獻[19]研究了節(jié)點選擇的公平性對模型訓(xùn)練性能的影響，并定義了一個名為“模型交換時間”(Model Exchange Time)的指標，包含模型下載時間、訓(xùn)練時間和模型上傳時間。最后設(shè)計了基于上下文CMAB的算法，以保證選擇公平性為約束最小化“模型交換時間”。

本文的研究工作不同于上述文獻。文獻[15-16]主要關(guān)注無線資源分配問題，而這在SL系統(tǒng)中是不切實際的，因為無線資源相關(guān)的信息在實際SL系統(tǒng)中無法獲取。文獻[13-14]定義了類基于線性回歸預(yù)測的指標來選擇節(jié)點，而類似線性回歸方法無法很好地反映相關(guān)指標的真實狀態(tài)。與本文工作最相近的是文獻[17-19]，雖然考慮了訓(xùn)練時延和選擇的公平性，但忽略了節(jié)點的能量消耗。綜上所述，現(xiàn)有的研究都沒有考慮長期的異構(gòu)能量約束下的節(jié)點選擇問題。

2 系統(tǒng)描述與問題建模

2.1 系統(tǒng)描述

圖1 集群學(xué)習(xí)系統(tǒng)Fig.1 Swarm learning system

在實際的SL系統(tǒng)整個訓(xùn)練過程前的初始化階段中，所有節(jié)點均會參與一次模型訓(xùn)練以獲取各個節(jié)點的初始性能信息。在之后的每一輪訓(xùn)練開始前，領(lǐng)導(dǎo)者節(jié)點基于各個節(jié)點的網(wǎng)絡(luò)狀態(tài)、歷史訓(xùn)練時延以及能耗表現(xiàn)綜合選擇合適的節(jié)點組合參與本輪訓(xùn)練。

SL系統(tǒng)分為中間件和應(yīng)用層[2]，中間件負責管理無線網(wǎng)絡(luò)通信相關(guān)問題。然而，由于無線網(wǎng)絡(luò)的時變特性，參數(shù)傳輸過程可能出現(xiàn)錯誤進而影響整體訓(xùn)練的效率。為解決這一問題，將Di(t)設(shè)置為一個上限D(zhuǎn)max。如果某節(jié)點因為網(wǎng)絡(luò)問題導(dǎo)致模型傳輸失敗，則將其對應(yīng)的Di(t)設(shè)置為Dmax，同時在參數(shù)合并時忽略該節(jié)點，Dmax的值根據(jù)訓(xùn)練模型的不同由實際需要確定。

2.2 問題建模

(1)

(2)

式中，Ⅱ{·}為指示函數(shù)，即條件為真其值取1否則取0。約束條件(1)為長期的能耗約束，其含義為各個節(jié)點的總能耗不能超過其先驗上限。約束條件(2)表示參與每個全局模型訓(xùn)練的節(jié)點數(shù)量均為k。

問題(P1)可以簡化為一個標準的背包問題，其中各個節(jié)點的能量上限對應(yīng)于背包的容量；節(jié)點每一輪的能耗對應(yīng)于物品的重量，uj(t)是物品的價值，因此問題(P1)是一個NP難問題。此外，質(zhì)量函數(shù)的具體值只有在節(jié)點實際進行模型訓(xùn)練后才能觀察到。然而，領(lǐng)導(dǎo)者節(jié)點需要在實際的訓(xùn)練開始之前進行節(jié)點選擇，而此時質(zhì)量函數(shù)的實際值尚不可獲取。因此，問題(P1)無法離線求得最優(yōu)解。為了求解問題(P1)，本文在 CMAB 理論框架下將該離線問題轉(zhuǎn)化為逐輪在線問題并求得次優(yōu)解。

2.3 問題轉(zhuǎn)化

采用CMAB理論的思路，將問題(P1)轉(zhuǎn)化為在線形式。定義質(zhì)量函數(shù)的“置信上界”如下：

(3)

式中，

(4)

s.t.(1),(2)

。

根據(jù)文獻[21]，CMAB算法在經(jīng)過數(shù)輪迭代后會傾向于選擇某些特定的節(jié)點組合，使這些節(jié)點的能量快速耗盡而無法繼續(xù)參與訓(xùn)練。因此，本文引入李雅普諾夫優(yōu)化機制來平衡節(jié)點被選中的頻率。定義節(jié)點i的能量赤字隊列如下：

(5)

式中，[·]+=max{·,0}，Ⅱi,j(t)=Ⅱ{i∈Sj(t)}。T0為訓(xùn)練輪數(shù)的上界，實際系統(tǒng)中可將其設(shè)置為歷史訓(xùn)練的最大輪數(shù)。初始的能量赤字隊列Θi(t)為0，當某節(jié)點被頻繁選中時，其對應(yīng)的Θi(t)將快速增大，反之則Θi(t)將保持較小值。通過最小化被選中節(jié)點的總能量赤字隊列，可間接控制各個節(jié)點被選中的頻率。同時，通過最小化被選中節(jié)點的能量赤字隊列也可以控制節(jié)點的能量消耗，使其不超過能量上限。根據(jù)文獻[5]，約束條件(1)自然得到滿足只需能量赤字隊列保持穩(wěn)定，即：

(6)

本文給出定理1證明上述陳述。

定理1若整個集群學(xué)習(xí)過程中的所有節(jié)點的能量赤字隊列保持穩(wěn)定，則長期能量約束(1)始終滿足。

證：根據(jù)文獻[5]中的定理2.5，若整個集群學(xué)習(xí)過程中的所有能量赤字隊列Θi(t)保持穩(wěn)定，則有：

(7)

將CMAB與李雅普諾夫優(yōu)化結(jié)合，重新定義節(jié)點的質(zhì)量函數(shù)如下：

qi(t)=V·Di(t)+Θi(t)ci(t)。

(8)

qi(t)的估計值為：

(9)

(10)

基于上述定義，給出問題的最終形式：

s.t.(6),(2)

。

問題(P3)可以通過對所有節(jié)點的質(zhì)量函數(shù)值排序并選擇其中最小的K個求解出相應(yīng)的節(jié)點集合。

3 能量感知的節(jié)點選擇算法

3.1 詳細算法

為了求解問題(P3)，提出了能量感知的節(jié)點選擇算法(Energy Aware Node Selection,EANS)。將問題建模為異質(zhì)能量約束的 CMAB 問題，其中節(jié)點對應(yīng)多臂賭博機的“臂(arm)”，訓(xùn)練時延對應(yīng)“獎勵(reward)”，選擇節(jié)點對應(yīng)選擇arm。為了處理異質(zhì)能量約束，將李雅普諾夫優(yōu)化與 CMAB 算法結(jié)合，通過最小化本文定義的虛擬能量赤字隊列并確保其保持穩(wěn)定，使得各個節(jié)點的總能耗不超過其能量上限。

EANS算法由初始化和主循環(huán)2個階段構(gòu)成。在第1行所示的初始化階段中，領(lǐng)導(dǎo)者節(jié)點選擇所有節(jié)點進行一次模型訓(xùn)練并收集各節(jié)點反饋的時延Di(t)和能量消耗ci(t)，用以初始化算法。如第 3 行所示，此后的每一輪領(lǐng)導(dǎo)者節(jié)點對所有節(jié)點上一輪的質(zhì)量函數(shù)值進行排序，選擇上一輪質(zhì)量函數(shù)值最小的K個節(jié)點參與本輪的模型訓(xùn)練。這K個節(jié)點按照質(zhì)量函數(shù)值升序分成每k個一組，如圖2所示。

圖2 節(jié)點組合的劃分方式Fig.2 Assignment of node groups

完成節(jié)點選擇后，第4行調(diào)用算法2分配節(jié)點組合至每個全局模型。之后各個被選中的節(jié)點在本地進行模型訓(xùn)練，并上傳訓(xùn)練后的模型(第5行)。節(jié)點完成訓(xùn)練后領(lǐng)導(dǎo)者節(jié)點會對本輪被選中的節(jié)點的訓(xùn)練時延和能耗進行收集，并更新對應(yīng)的質(zhì)量函數(shù)(第6，7行)。

由于每個節(jié)點所持的數(shù)據(jù)不同，每個全局模型所需的數(shù)據(jù)也可能不同。因此，需要設(shè)計一個算法，盡可能將持有全局模型所需數(shù)據(jù)的節(jié)點分配給對應(yīng)的模型。本文提出算法2來確定全局模型和節(jié)點組合之間的對應(yīng)關(guān)系。

3.2 理論分析

證明圖2所示的劃分方式是問題(P3)的可行解，同時給出虛擬能量赤字隊列的上界以證明虛擬能量赤字隊列的穩(wěn)定性。

證：設(shè)任意一種將K個被選節(jié)點分為k個一組的序列為S′j(t),j=1,2,…,J。為描述方便，不妨設(shè)任意S′j(t)中的節(jié)點按其質(zhì)量函數(shù)值升序排列，則有：

由于SGmj(t)序列按質(zhì)量函數(shù)值升序得到，因此顯然存在以下關(guān)系：

由S′j(t)序列的任意性可得出SGmj(t)序列是問題(P3)的一種可行解。定理2證畢。

在證明虛擬能量赤字隊列的穩(wěn)定性之前，需要介紹一個假設(shè)：

假設(shè) 1 的含義為節(jié)點有足夠的能量參與全程SL的訓(xùn)練過程。有了上面的假設(shè)，給出式(6)的嚴格上界，如下所示：

(11)

式中，

證：

首先，定義如下符號：

求解Lyapunov drift的上界：

(12)

對式(12)兩端從t=1,2,…,T求和，除以T再放縮可得：

(13)

對式(13)中的T取極限，兩端除以ε即可得定理3。定理3證畢。

4 實驗驗證

4.1 實驗設(shè)置

本文實驗在一臺搭載Intel Xeon E5 CPU、32 GB RAM、2 TB HDD、512 GB SSD和Ubuntu 16.04.1 LTS 操作系統(tǒng)的桌面服務(wù)器上進行。使用Flower[23]平臺構(gòu)建SL框架。采用Docker容器模擬了20個節(jié)點，各節(jié)點的能量上限1 300～1 600 J隨機變化。使用擴展的手寫數(shù)字分類數(shù)據(jù)集 EMNIST[24]進行模型訓(xùn)練。EMNIST 的數(shù)字部分包含10個類別的28 pixel×28 pixel灰度圖像，訓(xùn)練集包含240 000條數(shù)據(jù)，測試集包含40 000條數(shù)據(jù)。本文將訓(xùn)練集中的240 000條數(shù)據(jù)和測試集中的 32 000條數(shù)據(jù)組合在一起，并將其分成 20 組作為20個節(jié)點的訓(xùn)練集。剩余的8 000條數(shù)據(jù)用作所有節(jié)點的測試集。

通過實驗評估了EANS的能量赤字隊列、總能量消耗、訓(xùn)練時延等指標。由于本文算法采用了CMAB框架，則對比算法也應(yīng)該在CMAB的框架下，否則不具有可比性。因此本文與以下2種常見算法比較以評估EANS算法的性能。

(1) 隨機算法Random：隨機選擇每一輪由哪K個節(jié)點參與訓(xùn)練；

(2) 文獻[17]提出的用于聯(lián)邦學(xué)習(xí)中客戶端節(jié)點選擇的CS-UCB-Q算法：中心服務(wù)器在fairness約束下選擇延遲最小的節(jié)點(參見文獻[17]中的不等式6)。

4.2 實驗結(jié)果

圖3 展示了能量赤字隊列隨輪次t的趨勢。由圖3可見，能量赤字隊列先增加后減小，最后趨于穩(wěn)定。此外，隨著參數(shù)V的增加，能量赤字隊列的上界也增加，這證明定理3是正確的。

圖3 能量赤字隊列在不同V值下的趨勢Fig.3 Trend of energy deficit queue vs round under different V

本文評估了EANS算法在不同情況下能量消耗的表現(xiàn)，并與CS-UCB-Q和Random進行了比較，如圖4所示。由于CS-UCB-Q沒有考慮能量的影響[17]，在不同的參數(shù)V設(shè)置下，其能量消耗接近隨機算法Random，并且明顯高于EANS算法。

圖4 幾種算法的能量消耗趨勢Fig.4 Trend of energy consumption of different algorithms vs round

由圖4可以看出，當V=200時，EANS算法的能耗為CS-UCB-Q算法能耗的54.6%，而當V=10時，能耗僅為CS-UCB-Q的45.5%。與隨機算法Random相比，EANS算法在V=200時能耗僅為Random能耗的54.0%，在V=10時為45.0%。

圖5展示了EANS算法在不同情況下訓(xùn)練時延的表現(xiàn)，以及與CS-UCB-Q和Random的對比。由于 CS-UCB-Q更關(guān)注訓(xùn)練時延而EANS不僅考慮了訓(xùn)練時延還考慮了能量消耗，需要在二者中做出權(quán)衡，因此CS-UCB-Q的總訓(xùn)練時延比EANS的要小。

圖5 幾種算法的訓(xùn)練時延在不同V值下的趨勢Fig.5 Trend of training delay of different algorithms vs round under different V

由圖5可以看出，EANS算法的總訓(xùn)練時延比參數(shù)V=10時的CS-UCB-Q多44%，而當參數(shù)V=200時，EANS算法的總訓(xùn)練時延僅比CS-UCB-Q多19%。同樣地，由于EANS算法在參數(shù)V較小時更關(guān)注能量消耗的影響，因此EANS的訓(xùn)練時延比隨機算法Random大，而當參數(shù)V變大時，EANS算法的訓(xùn)練時延表現(xiàn)則優(yōu)于隨機算法Random。

5 結(jié)束語

本文提出一種新的用于集群學(xué)習(xí)的節(jié)點選擇算法——EANS算法，該算法考慮了無線網(wǎng)絡(luò)質(zhì)量對集群學(xué)習(xí)系統(tǒng)整體訓(xùn)練效率的影響，著重關(guān)注了模型訓(xùn)練時延和能量消耗。采用CMAB理論結(jié)合李雅普諾夫優(yōu)化的方法在無需節(jié)點詳細性能信息的情況下為模型訓(xùn)練選擇次優(yōu)的節(jié)點組合，在保證整體訓(xùn)練效率的同時控制節(jié)點能量消耗不超過其能量上限。

從實驗結(jié)果可以看出，EANS算法可達到接近最優(yōu)解的性能。在能耗方面，當V=200時，EANS的能耗為CS-UCB-Q的54.6%，而當V=10時僅為CS-UCB-Q的45.5%。與隨機算法Random相比，EANS算法的能耗是隨機算法的54.0%而V=10時僅為其45.0%。

未來的工作，將考慮在節(jié)點選擇的目標函數(shù)中引入模型的準確度，更加真實地反映節(jié)點的性能。同時，考慮對節(jié)點的能耗進行更加精確的建模，以使目標函數(shù)能更加全面地反映節(jié)點的真實狀態(tài)。