劉小雨

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

1 引言

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

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

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

2 相關(guān)工作

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

2.1 FedAvg算法

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

算法1 FedAvg算法

Algorithm 1：FedAvg算法

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

1）1對(duì)于服務(wù)器端：

2）初始化θt

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

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

5）for每個(gè)客戶端k?m同時(shí)do

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

7）end for

8）end for

9）對(duì)于客戶端：

10）θk=θt

11）for從1到E的每個(gè)迭代輪次do

12）for batch b?B do

14）end for

15）end for

16）返回θk至服務(wù)器

2.2 改進(jìn)SET算法

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

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

算法2 改進(jìn)SET算法

Algorithm 2：改進(jìn)SET算法

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

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

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

4）end for

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

6）開始訓(xùn)練

7）for每一個(gè)訓(xùn)練回合do

8） 訓(xùn)練和更新相應(yīng)的權(quán)重

9）end for

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

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

12）end for

2.3 NSGA-II算法

NSGA-II 算法（Elitist Nondominated Sorting Ge?netic Algorithm-II）［13］，又被稱為精英非支配排序遺傳算法，是一種被廣泛應(yīng)用的多目標(biāo)進(jìn)化算法，由Deb 等提出，對(duì)傳統(tǒng)的NSGA 算法進(jìn)行改進(jìn)。該算法采用精英選擇策略，父、子代種群合并后擇優(yōu)產(chǎn)生下一代個(gè)體，可很好地保留父代中的優(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） 計(jì)算種群中個(gè)體的目標(biāo)函數(shù)

6）for種群Rt中每一個(gè)個(gè)體do

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

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

9）end for

10）end for

3 問(wèn)題描述

本文研究如何在保證機(jī)器學(xué)習(xí)模型測(cè)試準(zhǔn)確性（即最小化模型測(cè)試錯(cuò)誤率）的情況下盡量減少聯(lián)邦學(xué)習(xí)的通信開銷，是一個(gè)典型的多目標(biāo)優(yōu)化問(wèn)題［14］。針對(duì)該問(wèn)題，建立多目標(biāo)優(yōu)化數(shù)學(xué)模型如下。

1）目標(biāo)函數(shù)

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

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

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

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

2）決策變量

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

4 基于改進(jìn)NSGA-II 算法的多目標(biāo)聯(lián)邦學(xué)習(xí)

4.1 改進(jìn)NSGA-II算法

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

4.1.1 編碼

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

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

4.1.2 遺傳算子設(shè)計(jì)

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

4.2 多目標(biāo)優(yōu)化聯(lián)邦學(xué)習(xí)

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

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

5 實(shí)驗(yàn)

5.1 實(shí)驗(yàn)設(shè)置

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

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

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

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

5.2 實(shí)驗(yàn)結(jié)果與分析

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

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

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

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

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

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

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

6 結(jié)語(yǔ)

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