異質能量約束的集群學習節點選擇機制

張富春，朱孔林,2

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

0 引言

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

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

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

SL系統的節點選擇并非一個簡單的問題。首先，系統中的節點受到能量限制，每個節點都有一個長期的能量上限。其次，由于SL系統中的節點所持有的數據集、物理硬件各不相同，不恰當的節點選擇可能會對訓練效果產生負面影響[4]。最后，SL系統中的各個節點通常是通過無線網絡相互連接，而無線網絡狀態通常是時變的，因此需要考慮無線網絡質量對模型參數傳輸的影響。

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

1 相關工作

本節對相關工作進行分類和討論，然后指出本文工作與它們的不同之處。與SL系統中的節點選擇問題直接相關的文獻極少，而與之高度相關的問題是聯邦學習中的客戶端節點選擇問題，相關文獻總結如下：

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

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

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

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

2 系統描述與問題建模

2.1 系統描述

圖1 集群學習系統Fig.1 Swarm learning system

在實際的SL系統整個訓練過程前的初始化階段中，所有節點均會參與一次模型訓練以獲取各個節點的初始性能信息。在之后的每一輪訓練開始前，領導者節點基于各個節點的網絡狀態、歷史訓練時延以及能耗表現綜合選擇合適的節點組合參與本輪訓練。

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

2.2 問題建模

(1)

(2)

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

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

2.3 問題轉化

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

(3)

式中，

(4)

s.t.(1),(2)

。

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

(5)

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

(6)

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

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

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

(7)

將CMAB與李雅普諾夫優化結合，重新定義節點的質量函數如下：

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

(8)

qi(t)的估計值為：

(9)

(10)

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

s.t.(6),(2)

。

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

3 能量感知的節點選擇算法

3.1 詳細算法

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

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

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

完成節點選擇后，第4行調用算法2分配節點組合至每個全局模型。之后各個被選中的節點在本地進行模型訓練，并上傳訓練后的模型(第5行)。節點完成訓練后領導者節點會對本輪被選中的節點的訓練時延和能耗進行收集，并更新對應的質量函數(第6，7行)。

由于每個節點所持的數據不同，每個全局模型所需的數據也可能不同。因此，需要設計一個算法，盡可能將持有全局模型所需數據的節點分配給對應的模型。本文提出算法2來確定全局模型和節點組合之間的對應關系。

3.2 理論分析

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

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

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

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

在證明虛擬能量赤字隊列的穩定性之前，需要介紹一個假設：

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

(11)

式中，

證：

首先，定義如下符號：

求解Lyapunov drift的上界：

(12)

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

(13)

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

4 實驗驗證

4.1 實驗設置

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

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

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

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

4.2 實驗結果

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

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

本文評估了EANS算法在不同情況下能量消耗的表現，并與CS-UCB-Q和Random進行了比較，如圖4所示。由于CS-UCB-Q沒有考慮能量的影響[17]，在不同的參數V設置下，其能量消耗接近隨機算法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算法在不同情況下訓練時延的表現，以及與CS-UCB-Q和Random的對比。由于 CS-UCB-Q更關注訓練時延而EANS不僅考慮了訓練時延還考慮了能量消耗，需要在二者中做出權衡，因此CS-UCB-Q的總訓練時延比EANS的要小。

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

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

5 結束語

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

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

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