基于改進NSGA-II 算法的多目標聯(lián)邦學習?

劉小雨

（中南財經(jīng)政法大學信息管理部 武漢 430205）

1 引言

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

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

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

2 相關(guān)工作

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

2.1 FedAvg算法

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

算法1 FedAvg算法

Algorithm 1：FedAvg算法

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

1）1對于服務器端：

2）初始化θt

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

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

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

6） 客戶端k執(zhí)行更新

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 等提出，可利用很少的超參數(shù)來映射神經(jīng)網(wǎng)絡模型的特定結(jié)構(gòu)，極大地減少了在使用多目標進化算法對神經(jīng)網(wǎng)絡結(jié)構(gòu)參數(shù)進行優(yōu)化時需要編碼的參數(shù)量。改進SET 算法以初始Erdos Renyi 隨機圖來決定神經(jīng)網(wǎng)絡兩個鄰接層之間的連接性，兩層之間的連接概率如下式所示。不同于傳統(tǒng)SET 算法在每個訓練回合都去除更新最小的部分權(quán)重，改進SET算法只在最后一個訓練回合執(zhí)行刪除操作，去掉更新最小的部分權(quán)重。改進SET算法的偽代碼如算法2所示。

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

算法2 改進SET算法

Algorithm 2：改進SET算法

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

2）for神經(jīng)網(wǎng)絡的每一個全連接層do

3） 用ε代替Erdos Renyi隨機圖給出的權(quán)重參數(shù)

4）end for

5）初始化權(quán)重

6）開始訓練

7）for每一個訓練回合do

8） 訓練和更新相應的權(quán)重

9）end for

10）for每個權(quán)重矩陣do

11） 刪除更新最小的部分權(quán)重，刪除比例為ξ

12）end for

2.3 NSGA-II算法

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

算法3 NSGA-II算法

Algorithm 3：NSGA-II算法

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

2）for遺傳代數(shù)t=1,2,…do

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

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

5） 計算種群中個體的目標函數(shù)

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

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

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

9）end for

10）end for

3 問題描述

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

1）目標函數(shù)

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

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

（2）目標函數(shù)2：最小化通信開銷

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

2）決策變量

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

4 基于改進NSGA-II 算法的多目標聯(lián)邦學習

4.1 改進NSGA-II算法

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

4.1.1 編碼

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

圖1 MLP神經(jīng)網(wǎng)絡編碼示例

4.1.2 遺傳算子設計

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

4.2 多目標優(yōu)化聯(lián)邦學習

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

圖2 優(yōu)化目標函數(shù)值計算流程

5 實驗

5.1 實驗設置

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

表1 初始模型參數(shù)設置

設置兩種多目標優(yōu)化算法的相關(guān)參數(shù)如表2所示。

表2 優(yōu)化算法參數(shù)設置

5.2 實驗結(jié)果與分析

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

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

表3 MLP結(jié)構(gòu)下兩種算法的目標函數(shù)結(jié)果對比

表4 CNN結(jié)構(gòu)下兩種算法的目標函數(shù)結(jié)果對比

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

圖3 MLP網(wǎng)絡下兩種算法的Pareto前沿

圖4 CNN網(wǎng)絡下兩種算法的Pareto前沿

6 結(jié)語

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