基于改進NSGA-II 算法的多目標聯邦學習?

劉小雨

（中南財經政法大學信息管理部 武漢 430205）

1 引言

聯邦學習（Federated Learning，FL）由谷歌于2016 年提出，致力于解決機器學習技術發展過程中面臨的兩大挑戰：數據隱私問題，“數據孤島”問題［1］。聯邦學習是由各個客戶端利用本地數據訓練得到本地模型，并將模型參數上傳至中心服務器，中心服務器對各個本地模型進行加權聚合，得到全局模型反饋給各個客戶端，客戶端可根據聚合后的模型信息對己方模型進行更新［2~4］。該操作無需參與訓練的各個客戶端交換己方所持有的樣本數據及其變體，僅需交換與模型相關的數據信息，有效地保證了各參與方的隱私數據的安全性，實現了融合多參與方數據的機器學習訓練［5］。然而，聯邦學習仍然面臨著巨大的挑戰，如通信開銷高的問題，各參與方需要與中心服務器不斷交換大量的模型信息，通信頻率高、傳輸數據多，帶來了極高的通信成本［6~8］。

為了解決聯邦學習通信成本高的問題，McMa?han 等提出了聯邦平均算法（Federated Averaging，FedAvg）［9］，通過控制客戶端與中心服務器交換數據前的模型迭代次數來減少通信回合數，降低通信開銷。除此之外，還可通過數據壓縮的方式，如稀疏化和量化操作來減少需要上傳或下載的模型參數信息，進一步降低通信成本。但這些操作會在一定程度上降低模型的準確性，如何在保證模型精度的情況下盡量減少通信開銷，是本文所要研究的重點問題。針對這一問題，Zhong 等［10］首先建立了聯邦學習的三目標優化模型，以聯邦學習中神經網絡參數作為決策變量，采用改進的NSGA-III 算法進行求解；同時引入層次聚類算法來解決客戶端數據非獨立同分布（Independently Identically Distribu?tion，IID）問題，加快了算法的收斂速度，提高了FL的精度。Zhu 等［11］同樣利用多目標進化NSGA-II算法來優化聯邦學習中的神經網絡模型的結構，以同時最小化通信成本和全局模型測試誤差；除此之外，該文還提出了一種改進的SET方法來對神經網絡的連通性進行間接編碼，在顯著降低通信成本的同時提升了聯邦學習的學習性能。Chai 等［12］建立了雙目標優化模型，采用基于分解的多目標優化算法（MOEA/D）對聯邦學習全局模型的結構進行優化，并將結果與NSGA-II 算法進行對比，驗證了MOEA/D算法具有更好的性能。

本文采用快速貪婪初始化和迭代后期丟棄低質量個體的策略來對傳統NSGA-II算法進行改進，使其更好地應用于優化聯邦學習中的神經網絡模型，結合改進的SET 算法，可達到在保證模型精度的前提下盡量減少通信開銷的目的。

2 相關工作

本 節 將 對FedAvg 算 法、改 進SET 算 法、NS?GA-II 算法等相關工作進行簡要介紹，為后文提出基于改進NSGA-II 算法的多目標聯邦學習做好鋪墊。

2.1 FedAvg算法

FedAvg 算法［9］由McMahan 等 于2016 年 提出，可通過較少的通信回合來訓練高質量的模型。算法主要思想是通過增加客戶端的計算來限制客戶端與中心服務器的通信頻率，具體操作為在各個客戶端在上傳更新的模型參數之前要執行多次的本地梯度下降迭代。FedAvg 算法的偽代碼如算法1所示。

算法1 FedAvg算法

Algorithm 1：FedAvg算法

K代表客戶端的總數量；B代表minibatch size；E代表訓練回合epochs；η代表學習率

1）1對于服務器端：

2）初始化θt

3）for通信回合t=1,2,…do

4） 選擇m=C×K個客戶端，其中C?( 0,1) 為比例系數

5）for每個客戶端k?m同時do

6） 客戶端k執行更新

7）end for

8）end for

9）對于客戶端：

10）θk=θt

11）for從1到E的每個迭代輪次do

12）for batch b?B do

14）end for

15）end for

16）返回θk至服務器

2.2 改進SET算法

改進SET 算法［11］由Zhu 等提出，可利用很少的超參數來映射神經網絡模型的特定結構，極大地減少了在使用多目標進化算法對神經網絡結構參數進行優化時需要編碼的參數量。改進SET 算法以初始Erdos Renyi 隨機圖來決定神經網絡兩個鄰接層之間的連接性，兩層之間的連接概率如下式所示。不同于傳統SET 算法在每個訓練回合都去除更新最小的部分權重，改進SET算法只在最后一個訓練回合執行刪除操作，去掉更新最小的部分權重。改進SET算法的偽代碼如算法2所示。

其中，nk和nk-1代表第k層和第k-1 層的神經元數，是兩層之間的稀疏權重矩陣，ε是控制連接稀疏性的參數，nW代表兩層之間的連接總數；當ε?nk且ε?nk-1時，連接概率將變得非常小。

算法2 改進SET算法

Algorithm 2：改進SET算法

1）設置ε和ξ的大小，ε是控制連接稀疏性的參數，ξ為刪除權重的比例

2）for神經網絡的每一個全連接層do

3） 用ε代替Erdos Renyi隨機圖給出的權重參數

4）end for

5）初始化權重

6）開始訓練

7）for每一個訓練回合do

8） 訓練和更新相應的權重

9）end for

10）for每個權重矩陣do

11） 刪除更新最小的部分權重，刪除比例為ξ

12）end for

2.3 NSGA-II算法

NSGA-II 算法（Elitist Nondominated Sorting Ge?netic Algorithm-II）［13］，又被稱為精英非支配排序遺傳算法，是一種被廣泛應用的多目標進化算法，由Deb 等提出，對傳統的NSGA 算法進行改進。該算法采用精英選擇策略，父、子代種群合并后擇優產生下一代個體，可很好地保留父代中的優秀基因，提高算法尋優效率。算法主要步驟如算法3所示。

算法3 NSGA-II算法

Algorithm 3：NSGA-II算法

1）初始化父代種群Pt，種群大小為M

2）for遺傳代數t=1,2,…do

3） 經選擇、交叉、變異生成種群大小為M的子代種群Qt

4） 合并父、子代種群Rt=Pt+Qt

5） 計算種群中個體的目標函數

6）for種群Rt中每一個個體do

7） 執行快速非支配排序、計算擁擠距離

8） 選出排名靠前的個體生成新的父代種群Pt

9）end for

10）end for

3 問題描述

本文研究如何在保證機器學習模型測試準確性（即最小化模型測試錯誤率）的情況下盡量減少聯邦學習的通信開銷，是一個典型的多目標優化問題［14］。針對該問題，建立多目標優化數學模型如下。

1）目標函數

（1）目標函數1：最小化全局測試誤差

在生成稀疏連接的神經網絡模型后，使用Fe?dAvg 算法對網絡進行訓練得到聯邦全局模型，可在一定的通信回合t內計算全局模型的測試精度At來評估學習性能，全局測試誤差Et=1-At。

（2）目標函數2：最小化通信開銷

當參與通信的客戶端數量、通信回合數確定時，通信開銷主要由模型復雜度，即上傳、下載的模型參數多少來決定，可以通過從第t輪通信中所有客戶端上傳的平均權重數量來衡量。上式中，K代表客戶端的總數量，Ωk代表第k個客戶端的參數數量。

2）決策變量

改進SET 算法中ε和ξ的大小決定了神經網絡的稀疏連接性，決定了模型參數量的多少；學習率η的大小控制著網絡模型的學習進度，影響模型的收斂狀態，進一步影響了聯邦學習中的通信頻率；除此之外，隱藏層的多少及隱藏層神經元的數量；卷積網絡中卷積核的大小、卷積層以及全連接層的數目同樣影響著模型參數數量，并最終決定了通信成本。因此，以上這些參數均可作為決策變量，通過對以上參數的優化，可以實現最小化全局測試誤差、最小化通信開銷這兩個目標之間的平衡。

4 基于改進NSGA-II 算法的多目標聯邦學習

4.1 改進NSGA-II算法

為了提高NSGA-II算法的求解速度，提高最終Pareto 最優集的質量，本文參考文獻［10］中對NS?GA-III 算法的改進方法，采取快速貪婪初始化、以及進化后期丟棄低質量個體的策略來對傳統NS?GA-II 算法進行改進。快速貪婪初始化的過程如下：假設種群固定大小為M，在種群初始化時，首先隨機生成l×M個解，l表示倍數。計算每個個體的f1和f2兩個目標函數值的大小，分別選取兩個目標函數下的最優解，對最優解進行混合并去除重復個體，從中隨機選出M個個體作為初代種群，記為P0，將剩余其他個體記為RS0作為保留解。丟棄低質量個體策略是指，在迭代后期可以刪除某些質量較差的個體，如當某些解f1>85%，轉而使用快速貪婪初始化的保留解RS0進行增補，以保證最終結果Pareto最優解集中解的準確性。

4.1.1 編碼

編碼的目的是為了將解空間中的解轉換為對應的染色體，在前一節所建立的FL數學模型中，改進SET 算法的參數ε和ξ、學習率η、隱藏層數目、隱藏層神經元數量等參數作為決策變量，直接或間接地影響著優化目標f1和f2的大小，選擇ε、ξ、η、隱藏層數目、隱藏層神經元數量等參數值作為染色體，對決策變量進行編碼。其中，決策變量的編碼分為兩種，二進制編碼和實值編碼。如果原決策變量是整數，則采用二進制編碼；如果原決策變量是實數，則采用實值編碼。圖1 所示為含有兩個隱藏層的MLP神經網絡的編碼示例。

圖1 MLP神經網絡編碼示例

4.1.2 遺傳算子設計

遺傳算子包括選擇算子、交叉算子、變異算子這三種，其中選擇算子用于選出遺傳至下一代的個體，該操作可有效避免有用遺傳信息的丟失；交叉算子模仿生物遺傳進化過程中的染色體交配重組現象，主要用于產生子代個體；變異算子針對交叉后產生的子代個體，模擬生物的基因變異現象，執行變異操作可有效豐富種群的多樣性。本文采用二元錦標賽選擇算子，每次從種群中隨機取出兩個個體，選擇其中更好的一個。編碼包括二進制編碼以及實值編碼兩種，對于二進制編碼，采用一點交叉算子和翻轉突變算子；對于實值編碼，采用模擬二進制交叉（SBX）和多項式突變。

4.2 多目標優化聯邦學習

采用改進的NSGA-II 算法來對聯邦學習雙目標優化問題進行求解，在進化算法每一次的遺傳迭代中，均需計算每個個體的優化目標函數值，并以此作為個體之間優劣性的判定依據，選擇更優秀的個體進入下一代。基本的計算步驟如下，首先獲取改進NSGA-II 算法種群中個體，獲取各決策變量值；其次，結合改進SET 算法進行聯邦學習全局模型初始化，該算法將根據ε和ξ參數值對全局模型進行稀疏連接，盡可能減少上傳、下載的參數量。進一步地，采用FedAvg 算法對模型進行訓練，當更新結束時，獲取最終全局模型。最后，計算全局測試誤差和通信復雜度，作為當前個體的兩個優化目標函數值，返回改進NSGA-II算法主體。該計算過程的步驟圖如圖2所示。

圖2 優化目標函數值計算流程

5 實驗

5.1 實驗設置

為了驗證本文改進NSGA-II 算法在聯邦學習多目標優化問題求解中的有效性，選取MOEA/D 算法與本文方法進行對比，采用MNIST數據集作為基準數據集，選取MLP 和CNN 兩種常用的神經網絡模型進行訓練，實驗中一些基本的參數設置如表1~2 所示。其中，稀疏性控制參數ε和ξ的設置參考文獻［15］，將ε設為20，ξ設為0.3。設置聯邦學習中相關參數，將客戶端總數設為100；當本地客戶端進行訓練時，訓練回合數為5。同時，還將MNIST 數據集劃分為IID 數據和非IID 數據兩種，分給各客戶端。

表1 初始模型參數設置

設置兩種多目標優化算法的相關參數如表2所示。

表2 優化算法參數設置

5.2 實驗結果與分析

設置對比實驗來驗證本文改進NSGA-II 算法在求解多目標優化聯邦學習問題上的有效性，選擇MOEA/D 算法與本文方法進行對比，比較最終生成的Pareto 解集、優化目標函數值等，以分析和評價本文改進算法的優勢與不足。

以同樣的初始實驗設置將MOEA/D 算法、本文改 進NSGA-II 算 法 在MLP-IID、MLP-nonIID、CNN-IID、CNN-nonIID 這四種情況下各自獨立運行20次，記錄每次最終Pareto前沿結果中目標函數Et、Ωt的最小值，表3、表4 展示了20 次結果中兩目標函數的最優值、最差值、以及中位值。由表3、表4 可以看出這四種情況下，MOEA/D 算法和本文改進NSGA-II 算法所得到的全局測試誤差相差不大的情況下，本文方法的模型復雜度更小，通信開銷更少。

表3 MLP結構下兩種算法的目標函數結果對比

表4 CNN結構下兩種算法的目標函數結果對比

任意選取20 次實驗中的一次結果進行展示，當采用MLP 網絡結構作為聯邦學習訓練的全局模型時，在IID 數據集和非IID 數據集條件下，兩種算法所得到的Pareto最優解集如圖3所示。而當采用CNN網絡結構作為聯邦學習訓練的全局模型時，在IID 數據集和非IID數據集條件下，兩種算法所得到的Pareto最優解集如圖4 所示。由圖3、圖4 可以看出，相比于MOEA/D方法，本文改進NSGA-II算法在目標空間的分布更為均勻，所得到的Pareto最優解集更好，目標函數值更小，驗證了本文方法的有效性。

圖3 MLP網絡下兩種算法的Pareto前沿

圖4 CNN網絡下兩種算法的Pareto前沿

6 結語

為了在聯邦學習訓練中保證全局模型精度的同時盡量減少通信消耗，本文首先建立了聯邦學習雙目標優化數學模型，提出一種改進的NSGA-II算法對模型進行求解，引入快速貪婪初始化和丟棄低質量個體的策略來對傳統NSGA-II算法進行改進，并通過實驗驗證了本文改進算法的性能。實驗結果表明，與MOEA/D 算法相比，本文所提出的改進NSGA-II 算法在多目標優化聯邦學習問題求解中性能表現更優，可獲得更好的Pareto最優集。