一種聯(lián)邦學(xué)習(xí)中的公平資源分配方案

田家會(huì) 呂錫香 鄒仁朋 趙 斌 李一戈

(西安電子科技大學(xué)網(wǎng)絡(luò)與信息安全學(xué)院 西安 710071)

隨著物聯(lián)網(wǎng)、大數(shù)據(jù)、5G網(wǎng)絡(luò)架構(gòu)的發(fā)展，機(jī)器學(xué)習(xí)(machine learning, ML)在自動(dòng)駕駛、信息檢索、能源檢測等領(lǐng)域得到了廣泛應(yīng)用.機(jī)器學(xué)習(xí)通過訓(xùn)練模型對(duì)數(shù)據(jù)進(jìn)行分析，提取有用的信息.隨著手機(jī)等智能設(shè)備的快速發(fā)展，數(shù)據(jù)分布趨向于本地化.單個(gè)用戶或機(jī)構(gòu)通常擁有較小規(guī)?；蜉^低質(zhì)量的數(shù)據(jù)，僅使用這些數(shù)據(jù)進(jìn)行訓(xùn)練容易導(dǎo)致模型過擬合，所以需要將參與方數(shù)據(jù)匯集到一起來訓(xùn)練模型.然而，出于數(shù)據(jù)的隱私考慮，各方通常不愿意將自己的數(shù)據(jù)直接共享給別人，從而形成數(shù)據(jù)孤島問題.聯(lián)邦學(xué)習(xí)(federated learning, FL)是面向這種數(shù)據(jù)孤島現(xiàn)實(shí)場景而設(shè)計(jì)的機(jī)器學(xué)習(xí)范式.通過分享模型參數(shù)或梯度的方式，聯(lián)邦學(xué)習(xí)參與方可在保持?jǐn)?shù)據(jù)本地私有的情況下協(xié)作訓(xùn)練一個(gè)高性能的共同模型[1].

聯(lián)邦學(xué)習(xí)自2016年由谷歌提出以后，就引起了學(xué)術(shù)界和信息產(chǎn)業(yè)界的巨大關(guān)注.這使得聯(lián)邦學(xué)習(xí)場景下的許多方向也都得到了迅速發(fā)展，如安全和隱私保護(hù).研究表明，僅上傳部分參數(shù)或梯度，本地訓(xùn)練數(shù)據(jù)仍有可能會(huì)泄露給誠實(shí)但好奇的服務(wù)器[2].因此聯(lián)邦學(xué)習(xí)通常與差分隱私[3]、同態(tài)加密[4]、安全多方計(jì)算[5]等技術(shù)結(jié)合來保護(hù)數(shù)據(jù)隱私[6].當(dāng)聯(lián)邦學(xué)習(xí)應(yīng)用于銀行借貸、預(yù)測警務(wù)、犯罪評(píng)估等重大決策場景時(shí)，公平性也引起了人們的重視.然而，傳統(tǒng)的聯(lián)邦學(xué)習(xí)并沒有考慮公平性的問題，聚合模型可能會(huì)潛在地歧視一些特殊群體，特別是當(dāng)訓(xùn)練數(shù)據(jù)本身就存在偏見時(shí).一個(gè)典型的例子是在“替代性制裁的懲罰性罪犯管理分析”(correctional offender management profiling for alternative sanctions, COMPAS)算法中.美國法院使用該算法預(yù)測一個(gè)人再次犯罪的概率，從而對(duì)罪犯做出假釋審核.研究發(fā)現(xiàn)，在同等條件下使用該軟件，與白種人相比，非裔美國人會(huì)得到更高的犯罪評(píng)分[7].

造成聯(lián)邦學(xué)習(xí)中這種不公平現(xiàn)象的原因之一是它的目標(biāo)函數(shù)，聯(lián)邦學(xué)習(xí)的目標(biāo)函數(shù)是最小化各個(gè)參與者的局部損失和樣本比例的加權(quán)平均，從而使模型可以擬合大多數(shù)設(shè)備的本地?cái)?shù)據(jù).在真實(shí)場景中，參與者之間的數(shù)據(jù)通常是高度異構(gòu)的.且因?yàn)榫W(wǎng)絡(luò)、設(shè)備、用戶習(xí)慣等因素的影響，參與者擁有的數(shù)據(jù)量差距也比較大.因此簡單使用上述方式可能得到較高的平均準(zhǔn)確率，但不能保證單個(gè)參與者的性能.即最終聚合模型在參與者本地?cái)?shù)據(jù)之間的準(zhǔn)確率懸殊較大，這是不公平的，可能會(huì)影響聚合效果.因此設(shè)計(jì)一種優(yōu)化算法來使聯(lián)邦學(xué)習(xí)參與者之間性能分布更公平是非常重要的.

目前有許多文獻(xiàn)致力于聯(lián)邦學(xué)習(xí)公平研究，如文獻(xiàn)[8]提出了一種名為AFL(agnostic federated learning)的聯(lián)邦學(xué)習(xí)框架，在此框架下全局模型可以優(yōu)化任何客戶分布混合而成的目標(biāo)函數(shù)但是它們僅優(yōu)化單個(gè)最差客戶的性能，適用于小規(guī)?？蛻羟胰狈`活性.文獻(xiàn)[9]中作者提出了一種新的目標(biāo)函數(shù)q-FFL(q-Fair Federated Learning)來使參與者準(zhǔn)確率分布更均勻，但該方法無法提前確定最佳的參數(shù)q值來達(dá)到公平性和有效性的平衡，且算法在本地?cái)?shù)據(jù)異構(gòu)較強(qiáng)時(shí)較難收斂.

在本文中我們提出了α-FedAvg算法，引入Jain’s Index和α-fairness來研究聯(lián)邦學(xué)習(xí)模型公平性和有效性的平衡.該算法可以在保持聯(lián)邦學(xué)習(xí)模型整體性能不損失的情況下，有效減小各參與方準(zhǔn)確率分布的方差，使準(zhǔn)確率分布更均衡.與文獻(xiàn)[9]相比，我們的方法更簡單，并且可通過算法在訓(xùn)練之前確定參數(shù)α的取值，而不需要該文中所述使用多個(gè)參數(shù)值訓(xùn)練獲得全局模型后，驗(yàn)證模型性能再從中選擇表現(xiàn)較好的參數(shù)值.

在本文的設(shè)定中，參與者是誠實(shí)的，它會(huì)如實(shí)地執(zhí)行協(xié)議并向服務(wù)器上傳最新的梯度和準(zhǔn)確率.以合作的方式，獲得比單獨(dú)訓(xùn)練較好的本地模型.服務(wù)器是誠實(shí)但好奇的，它在誠實(shí)執(zhí)行協(xié)議的同時(shí)可能會(huì)從參與者上傳的參數(shù)中推測出一些敏感信息.因此我們的算法中也有相應(yīng)的隱私保護(hù)機(jī)制.我們的應(yīng)用場景為一些金融或醫(yī)療機(jī)構(gòu).在這些機(jī)構(gòu)中，協(xié)同訓(xùn)練中謊報(bào)參數(shù)可能會(huì)付出沉重的法律代價(jià).對(duì)于法律約束較弱的一般場景，參與者可能是自私的，會(huì)通過謊報(bào)模型在本地?cái)?shù)據(jù)上的準(zhǔn)確率來影響聚合過程的情況，我們?cè)?.4節(jié)擴(kuò)展部分也給出了解決方案.

本文的主要貢獻(xiàn)包括4個(gè)方面:

1) 將Jain’s Index引入聯(lián)邦學(xué)習(xí)領(lǐng)域來度量公平，并同時(shí)給出了系統(tǒng)有效性的度量.

2) 通過研究α-fairness中參數(shù)α對(duì)聯(lián)邦學(xué)習(xí)模型公平性和有效性的影響，我們采用一種基于梯度的算法來確定最佳α值達(dá)到二者之間的權(quán)衡.

3) 提出了α-FedAvg算法，在保證原有模型性能的基礎(chǔ)上有效提高公平性，且該算法具有可擴(kuò)展性，可與已有的隱私保護(hù)技術(shù)相結(jié)合.

4) 我們?cè)?個(gè)標(biāo)準(zhǔn)數(shù)據(jù)集MNIST和CIFAR-10上評(píng)估了α-FedAvg算法.并分別在圖像、表格、文本類的數(shù)據(jù)集上與最新的其他3種公平方案進(jìn)行了對(duì)比.實(shí)驗(yàn)結(jié)果表明，本文提出的算法實(shí)現(xiàn)了聯(lián)邦學(xué)習(xí)模型公平性和有效性的平衡，且效果優(yōu)于其他方案.

1 相關(guān)工作

近幾年，機(jī)器學(xué)習(xí)算法的公平性得到了人們的高度重視，公平方向的研究不斷涌現(xiàn).總的來說，一個(gè)公平的算法不會(huì)基于其需要的特征歧視或者偏向于某些特定群體.通常機(jī)器學(xué)習(xí)算法消除歧視追求公平的方法可分為3類[10]：

1) 預(yù)處理(pre-processing).預(yù)處理考慮到算法不公平的原因可能是訓(xùn)練數(shù)據(jù)的問題，即受保護(hù)變量的分布是有歧視/不平衡的，因此預(yù)處理通常會(huì)改變受保護(hù)變量的樣本分布來消除歧視.如文獻(xiàn)[11]中作者提出了一種歧視意識(shí)(discrimination-aware)的審計(jì)過程，它與常規(guī)訓(xùn)練分類器的過程類似，主要是增加了歧視測試模型.文獻(xiàn)[12]中作者借用了生成對(duì)抗網(wǎng)絡(luò)(GAN)的思想，提出了FairGAN，它可以從在保證數(shù)據(jù)可用性的基礎(chǔ)上從原始數(shù)據(jù)中生成更公平的數(shù)據(jù)用于訓(xùn)練，從而產(chǎn)生公平的模型.

2) 中處理(in-processing).中處理考慮到算法本身可能會(huì)產(chǎn)生偏見，因此中處理通常會(huì)嘗試修改算法或增加一些公平約束，從而消除模型訓(xùn)練過程的歧視.如文獻(xiàn)[13]中作者針對(duì)回歸問題損失函數(shù)引入了公平正則器(fairness regularizers)，且通過改變正則化權(quán)重來權(quán)衡給定數(shù)據(jù)集的準(zhǔn)確性和公平性.文獻(xiàn)[14]中作者通過增加約束來從訓(xùn)練集中學(xué)習(xí)到一個(gè)非歧視預(yù)測器.

3) 后處理(post-processing).后處理中將算法和模型視為黑盒，它傾向于對(duì)模型輸出進(jìn)行一定變換來提高預(yù)測的公平性.如文獻(xiàn)[15]中作者介紹了一個(gè)開源的Python工具包AIF360(AI Fairness 360)，為公平研究者提供一套共享和評(píng)估算法的通用框架，它包括一套完整的數(shù)據(jù)和模型公平度量標(biāo)準(zhǔn)以及緩解歧視的辦法，研究人員可根據(jù)需求選擇最適合的工具應(yīng)用.

先前的機(jī)器學(xué)習(xí)公平研究大都聚焦于中心化設(shè)置而沒有考慮分布式情況.聯(lián)邦學(xué)習(xí)作為一種有前景的分布式機(jī)器學(xué)習(xí)范式，近幾年也吸引了大量公平研究者的目光.由于應(yīng)用場景不同，對(duì)公平的需求也不一樣.總的來說，以聯(lián)邦學(xué)習(xí)為主的分布式機(jī)器學(xué)習(xí)公平性研究也可分為2個(gè)方向：

1) 引入激勵(lì)機(jī)制，參與者根據(jù)自己在聚合中的貢獻(xiàn)得到不同的獎(jiǎng)勵(lì)(如金錢激勵(lì)或得到不同的最終模型).如文獻(xiàn)[16-17]中作者都設(shè)計(jì)了一種本地信譽(yù)互評(píng)機(jī)制，這種機(jī)制會(huì)評(píng)估參與者在學(xué)習(xí)過程中的貢獻(xiàn)并迭代更新信譽(yù)值，使得參與者最終獲得與其貢獻(xiàn)相匹配的聚合模型.不同的是文獻(xiàn)[17]中作者使用區(qū)塊鏈進(jìn)行交易，改變了傳統(tǒng)聯(lián)邦學(xué)習(xí)的B/S模式，且設(shè)計(jì)了一種3層洋蔥式加密方案來保護(hù)參與者隱私.文獻(xiàn)[18]中作者提出了一種分層聯(lián)邦學(xué)習(xí)框架，首先基于參與者本地?cái)?shù)據(jù)量的多少將其分為幾個(gè)不同的貢獻(xiàn)水平，在此框架下進(jìn)行訓(xùn)練，不同水平的用戶將收到不同的模型更新.

2) 參與者獲得有效模型的機(jī)會(huì)均等.減小參與方之間或參與者內(nèi)部訓(xùn)練和測試數(shù)據(jù)準(zhǔn)確率分布的方差[8-9,19-21].本文的工作也屬于這一方向.在文獻(xiàn)[20]中作者證明了經(jīng)驗(yàn)風(fēng)險(xiǎn)損失最小隨著時(shí)間的推移會(huì)擴(kuò)大群體之間的差異，因此作者開發(fā)了一種基于分布式魯棒性的優(yōu)化方法.與文獻(xiàn)[7]相似，這種方法通過優(yōu)化少數(shù)最壞群體的風(fēng)險(xiǎn)損失來達(dá)到公平.文獻(xiàn)[19]中作者提出了AgnosticFair框架，解決當(dāng)測試數(shù)據(jù)與訓(xùn)練數(shù)據(jù)分布不同時(shí)，在未知測試數(shù)據(jù)上達(dá)到公平的問題.文獻(xiàn)[21]中作者提出了一種算法FedFa，它基于雙動(dòng)量梯度，可以加快模型收斂，并且采用了一種基于參與者訓(xùn)練數(shù)據(jù)準(zhǔn)確率和訓(xùn)練頻率的權(quán)重選擇算法來達(dá)到公平.

2 理論基礎(chǔ)

在本節(jié)中，我們主要介紹本文用到的相關(guān)理論，包括聯(lián)邦學(xué)習(xí)和公平度量(fairness measure).

2.1 聯(lián)邦學(xué)習(xí)

聯(lián)邦學(xué)習(xí)是一種分布式機(jī)器學(xué)習(xí)框架，旨在保護(hù)數(shù)據(jù)隱私.聯(lián)邦學(xué)習(xí)中通常有2種實(shí)體：參與者(數(shù)據(jù)擁有者)和服務(wù)器(模型聚合者).參與者有多個(gè)，記為{P1,P2,…,PN}.他們擁有各自的數(shù)據(jù)集{D1,D2,…,DN}.在聯(lián)邦學(xué)習(xí)框架下，參與者之間不需要交換原始私有數(shù)據(jù)集，通過本地訓(xùn)練更新模型參數(shù)，并上傳參數(shù)至中央服務(wù)器聚合的方式協(xié)同訓(xùn)練模型.

在聯(lián)邦學(xué)習(xí)框架中，令K表示每輪聚合時(shí)的參與者個(gè)數(shù)，Dk表示第k個(gè)參與者擁有的數(shù)據(jù)集，其元素個(gè)數(shù)為|Dk|=nk，n表示所有參與者的樣本總數(shù)，則聯(lián)邦學(xué)習(xí)的目標(biāo)是優(yōu)化全局損失函數(shù)[1]：

(1)

2.2 公平度量

在資源分配中，決策者進(jìn)行資源分配時(shí)，不僅要考慮資源分配的有效性，還需考慮它的公平性.公平度量是資源分配中量化當(dāng)前分配方式公平程度的方法，它通過一個(gè)函數(shù)f(x)將向量x∈映射為一個(gè)實(shí)數(shù)，且需滿足5個(gè)性質(zhì)[22]：

1) 連續(xù)性.公平度量f(x)是關(guān)于變量x∈的連續(xù)函數(shù).

2) 單調(diào)性.當(dāng)有2個(gè)用戶時(shí)，公平性f(θ,1-θ)隨著2元素之間差異|1-2θ|的增加而減小.

3) 同質(zhì)性(homogeneity).公平度量f(x)的值與x代表的數(shù)學(xué)含義無關(guān)，只需統(tǒng)一即可.f(x)是一個(gè)齊次函數(shù)，滿足f(x)=f(x)×t0=f(x×t),?t>0，且對(duì)于任何單個(gè)用戶都有|f(x)|=1.

5) 劃分無關(guān)(irrelevance of partition).f(x)的值與x的劃分無關(guān)，如果對(duì)x進(jìn)行劃分，可通過一定公式遞歸計(jì)算得到最終結(jié)果.

受到公平資源分配的啟示，在本文中我們將聯(lián)邦學(xué)習(xí)中的全局模型作為一種資源，其在各個(gè)參與者本地?cái)?shù)據(jù)集上的準(zhǔn)確率分布組成向量，使用Jain’s Index和α-fairness公平度量，保證聯(lián)邦學(xué)習(xí)的公平性和有效性.Jain’s Index的定義為

(2)

α-fairness通過改變參數(shù)α的取值來達(dá)到系統(tǒng)公平和效率之間的權(quán)衡，α值越高代表分配越公平，但同時(shí)系統(tǒng)有效性可能隨之減小.在此框架下單個(gè)用戶效用定義為

(3)

3 方案設(shè)計(jì)

在本節(jié)，我們首先會(huì)給出聯(lián)邦學(xué)習(xí)過程中公平性和有效性的度量方法；然后提出一種算法確定最佳的α值，達(dá)到二者之間的權(quán)衡；最后我們利用求出的α值對(duì)聯(lián)邦學(xué)習(xí)聚合過程重新加權(quán)，提出了一種α-FedAvg算法來產(chǎn)生更加公平的全局模型，并在擴(kuò)展部分給出了應(yīng)對(duì)自私參與者的解決方案.

3.1 聯(lián)邦學(xué)習(xí)公平性和有效性的度量方法

參考2.1節(jié)所述的聯(lián)邦學(xué)習(xí)的訓(xùn)練過程，我們用K表示每輪聚合時(shí)的參與者個(gè)數(shù)，pk表示參與者k本地訓(xùn)練的模型在中央服務(wù)器聚合時(shí)所占的權(quán)重，集合{a1,a2,…,aK}表示聚合后的全局模型wg用于各參與者本地?cái)?shù)據(jù)上的準(zhǔn)確率，用Rk=akpk表示聚合后參與者k獲得的實(shí)際效用(utility)，則本次訓(xùn)練過程中系統(tǒng)有效性(effificiency)量化為

(4)

系統(tǒng)公平性量化為

(5)

E和J都是0～1之間的實(shí)數(shù)，E值越大代表聚合模型越有效，加權(quán)平均準(zhǔn)確率越高.J值越大表示聚合模型越公平，參與者之間準(zhǔn)確率分布越均勻.

3.2 聯(lián)邦學(xué)習(xí)公平性和有效性的權(quán)衡

(6)

(7)

為了研究函數(shù)J(α)和E(α)的單調(diào)性，我們?cè)讦恋亩x域內(nèi)分別對(duì)這2個(gè)式子求導(dǎo)，判斷導(dǎo)數(shù)的正負(fù).當(dāng)α>1時(shí)，得到了2條定理，詳細(xì)證明過程參考附錄部分.

定理1.聯(lián)邦學(xué)習(xí)系統(tǒng)公平性J(α)隨α的增大而增大.

定理2.聯(lián)邦學(xué)習(xí)系統(tǒng)有效性E(α)隨α的增大而減小.

類似的工作在資源分配領(lǐng)域已經(jīng)取得了巨大的進(jìn)展，如文獻(xiàn)[23-24].通過定理1、定理2可知，α取值會(huì)影響聯(lián)邦學(xué)習(xí)系統(tǒng)有效性和公平性，因此我們需確定最佳的α取值來達(dá)到二者之間的平衡.我們的目標(biāo)是在確保達(dá)到經(jīng)典聯(lián)邦學(xué)習(xí)最終模型同等有效性ET(閾值)的基礎(chǔ)上，最大化系統(tǒng)公平性，即可以被描述為優(yōu)化問題：

(8)

由定理1,2可知，當(dāng)E(α)=ET時(shí)，α的取值為最優(yōu)解.因?yàn)榈仁紼(α)=ET中α在指數(shù)位置直接求解較為困難，利用該函數(shù)的單調(diào)性，我們使用一種更為簡單有效的基于梯度的方法求解，通過逼近閾值ET來確定最佳α的取值.該方法可總結(jié)為算法1，其中{a1,a2,…,aK}為準(zhǔn)確率，ET為有效性閾值;參數(shù)λ表示容忍誤差，Λ表示改變步長大小，τ表示迭代過程中當(dāng)α取負(fù)數(shù)時(shí)代替它的最小正實(shí)數(shù)，i表示迭代次數(shù).

算法1.基于梯度的逼近算法.

輸入：{a1,a2,…,aK}，ET；

輸出：α.

① 初始化λ=10-5，Λ=1，τ=10-10，α0=1,i=0；

② repeat

④ if (E(αi+1)-ET)(E(αi)-ET)<0 then

⑤Λ←Λ/2；

⑥ end if

⑦i←i+1；

⑧ until (|E(αi)-ET|<λ).

3.3 公平聯(lián)邦學(xué)習(xí)算法(α-FedAvg)

Fig. 1 Fair federated learning framework圖1 公平聯(lián)邦學(xué)習(xí)框架

算法2.α-FedAvg.

輸入：參與者個(gè)數(shù)K，聚合次數(shù)T，本地批大小B，本地時(shí)期數(shù)E，學(xué)習(xí)率η，參數(shù)α；

輸出：全局模型wg.

服務(wù)器執(zhí)行:

② for輪數(shù)t從0～T-1

③SK←選擇K個(gè)參與者；

④ for參與者k∈SK，并行執(zhí)行

⑤ ift≠0

⑦ end if

⑨ end for

⑩ for參與者k從1～K

參與者k執(zhí)行:

②Bk←將數(shù)據(jù)集Dk劃分為小批量；

③ for時(shí)期e從1～E

④ for批量b∈Bk

⑥ end for

⑦ end for

⑨ end function

3.4 算法擴(kuò)展

α-FedAvg算法設(shè)定每輪中所有參與者都會(huì)誠實(shí)地向服務(wù)器匯報(bào)本地模型參數(shù)和準(zhǔn)確率，這使得它的應(yīng)用場景具有很大的局限性.對(duì)于一般場景中可能存在的會(huì)謊報(bào)準(zhǔn)確率的參與者,我們也給出了解決方案：通過參與者提交部分合成數(shù)據(jù)、服務(wù)器進(jìn)行驗(yàn)證的方式，保證參與者匯報(bào)準(zhǔn)確率的真實(shí)性.同時(shí)服務(wù)器可通過設(shè)定容忍參數(shù)將超出閾值的參與者踢出聚合過程.

合成數(shù)據(jù)發(fā)布技術(shù)是通過發(fā)布合成的數(shù)據(jù)集，來取代對(duì)原始數(shù)據(jù)集的查詢結(jié)果，且生成的合成數(shù)據(jù)可以隱藏原始數(shù)據(jù)中的敏感信息.目前，該領(lǐng)域的發(fā)展已經(jīng)非常成熟.我們可使用文獻(xiàn)[26]中提出的基于貝葉斯網(wǎng)絡(luò)的差分隱私合成數(shù)據(jù)發(fā)布方法.在預(yù)處理階段，每個(gè)參與者都先與服務(wù)器約定好密鑰，使用該方法，以本地測試數(shù)據(jù)為原型生成合成數(shù)據(jù)集并將加密后的數(shù)據(jù)發(fā)送給服務(wù)器.服務(wù)器端收到后解密并存儲(chǔ)數(shù)據(jù).服務(wù)器端設(shè)定2個(gè)參數(shù)：容忍誤差λg和容忍次數(shù)閾值Tg.服務(wù)器可在每輪中選取部分參與者，驗(yàn)證全局模型在該參與者的合成數(shù)據(jù)集上的準(zhǔn)確率與參與者提交的準(zhǔn)確率是否一致，誤差超過λg則容忍次數(shù)加1，容忍次數(shù)超出閾值Tg則將會(huì)被服務(wù)器標(biāo)記為不可信，無法參與后續(xù)的聚合過程.該方法有效地保證了參與者提交準(zhǔn)確率的真實(shí)性，保障了存在自私參與者中的α-FedAvg算法的公平性.

3.5 通信和計(jì)算開銷

表1展示了每一輪迭代中2種算法的計(jì)算和通信開銷對(duì)比，其中K代表參與者個(gè)數(shù)，n代表模型參數(shù)個(gè)數(shù)，t1代表前向傳播計(jì)算時(shí)間，t2代表反向傳播時(shí)間，E代表本地訓(xùn)練輪數(shù).

1) 通信開銷.對(duì)于傳統(tǒng)的FedAvg算法，服務(wù)器需要與K個(gè)參與者通信，因此其通信開銷為O(K).每個(gè)參與者僅需與服務(wù)器通信，因此其通信開銷為O(1)，本文所提的α-FedAvg算法也是如此.

2) 計(jì)算開銷.傳統(tǒng)的FedAvg算法中，服務(wù)器基于參與者上傳的K個(gè)模型計(jì)算全局模型，每個(gè)模型包含n個(gè)參數(shù)，對(duì)于每個(gè)參數(shù)計(jì)算其平均值，因此時(shí)間復(fù)雜度為O(Kn).我們提出的α-FedAvg算法在此基礎(chǔ)上，通過K個(gè)準(zhǔn)確率計(jì)算對(duì)應(yīng)的模型權(quán)重，其時(shí)間復(fù)雜度為O(2K)，因此總的時(shí)間復(fù)雜度為O(2K+Kn).傳統(tǒng)的FedAvg算法中，參與者基于本地?cái)?shù)據(jù)優(yōu)化模型，本地訓(xùn)練輪數(shù)為E，每一輪中，通過神經(jīng)網(wǎng)絡(luò)優(yōu)化算法更新模型參數(shù)，包括一次前向傳播和反向傳播，因此其時(shí)間復(fù)雜度為O(E(t1+t2)).我們所提的α-FedAvg算法在此基礎(chǔ)上，需要根據(jù)全局模型計(jì)算準(zhǔn)確率，其相當(dāng)于一次前向傳播過程，時(shí)間復(fù)雜度為O(t1)，因此總的時(shí)間復(fù)雜度為O(E((t1+t2)+t1).

Table 1 Communication Cost and Computation Cost表1 通信開銷和計(jì)算開銷

我們?cè)趯?shí)驗(yàn)過程中記錄了相同條件下多次運(yùn)行100輪經(jīng)典聯(lián)邦學(xué)習(xí)FedAvg和本文算法所需要的平均運(yùn)行時(shí)間，它們的差值約在2 min以內(nèi).總的來說，我們所提的算法在保證聯(lián)邦學(xué)習(xí)公平性和有效性的基上，復(fù)雜度與原來相差不大，不會(huì)引入過多的計(jì)算開銷和通信開銷.

4 實(shí)驗(yàn)結(jié)果

在本節(jié)中，我們?cè)u(píng)估了本文所提算法α-FedAvg的性能.首先我們描述了實(shí)驗(yàn)設(shè)置，包括數(shù)據(jù)集和本地模型；然后展示了α-FedAvg相比于經(jīng)典聯(lián)邦學(xué)習(xí)算法FedAvg的有效性；最后將α-FedAvg和已有的其他公平聯(lián)邦學(xué)習(xí)算法作了對(duì)比.

4.1 實(shí)驗(yàn)配置

1) 數(shù)據(jù)集.我們?cè)谏疃葘W(xué)習(xí)常用的2個(gè)基準(zhǔn)數(shù)據(jù)集上實(shí)現(xiàn)了我們的算法，第1個(gè)是手寫數(shù)字識(shí)別數(shù)據(jù)集MNIST，它包含了60 000個(gè)訓(xùn)練樣本和10 000個(gè)測試樣本，每張圖片為數(shù)字0～9中的1個(gè)，且數(shù)字位于圖片中央.為了提高算法的泛化能力，我們?cè)谟?xùn)練之前對(duì)原始數(shù)據(jù)做了一些增強(qiáng)處理，如將每張圖片旋轉(zhuǎn)任意角度或進(jìn)行平移變換.為了更好地模擬真實(shí)世界，將數(shù)據(jù)集在參與者間進(jìn)行劃分時(shí)采用non-IID不平衡劃分方式.首先我們將數(shù)據(jù)集按照數(shù)字標(biāo)簽排序，然后將其劃分為1 200個(gè)分片，每個(gè)分片包含50張數(shù)據(jù)，設(shè)定每個(gè)參與者擁有的最大分片數(shù)為30，最小分片數(shù)為1.實(shí)驗(yàn)中共100個(gè)參與者，每個(gè)參與者擁有一定分片的數(shù)據(jù)，且所有參與者分片總數(shù)一定.這種劃分方式保證了每個(gè)參與者最多擁有3個(gè)類別的數(shù)字樣本，且相互之間樣本數(shù)量差距懸殊.第2個(gè)是CIFAR-10數(shù)據(jù)集，它包含50 000個(gè)訓(xùn)練樣本和10 000個(gè)測試樣本，共10個(gè)類別，每個(gè)類別有6 000個(gè)圖像，每張樣本是由32×32個(gè)像素點(diǎn)組成的彩色圖像，這個(gè)數(shù)據(jù)集最大的特點(diǎn)在于將識(shí)別遷移到了普適物體，數(shù)據(jù)中需要提取的特征較大且含有大量噪聲，識(shí)別物體的比例也不一樣，因此CIFAR-10數(shù)據(jù)集對(duì)于圖像識(shí)別任務(wù)更具有挑戰(zhàn)性.CIFAR-10數(shù)據(jù)集在參與者間的劃分方式也采用non-IID不平衡設(shè)定，實(shí)現(xiàn)細(xì)節(jié)和MNIST類似.

2) 模型.如圖2所示,我們?cè)趯?shí)驗(yàn)中用到了2種模型:①一個(gè)最簡單的多層感知器(MLP)，包含一個(gè)隱藏層;②一個(gè)經(jīng)歷2次卷積和最大池化的卷積神經(jīng)網(wǎng)絡(luò)(CNN).2種模型中激活函數(shù)都使用ReLU并加入Dropout層緩解過擬合的發(fā)生.

Fig. 2 Neural network architectures圖2 神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)

3) 實(shí)現(xiàn).我們?cè)谏疃葘W(xué)習(xí)框架Pytorch上實(shí)現(xiàn)了我們的代碼，用電腦模擬了聯(lián)邦學(xué)習(xí)的訓(xùn)練過程，虛擬對(duì)象包括一臺(tái)服務(wù)器和100個(gè)參與者.

4.2 實(shí)驗(yàn)和結(jié)果

Fig. 3 Changes of the number of participants under different test accuracy intervals in two algorithms圖3 2種算法中參與者個(gè)數(shù)在不同測試準(zhǔn)確率區(qū)間的變化

為了突出本文所提算法α-FedAvg的公平和有效性，我們將其與經(jīng)典聯(lián)邦學(xué)習(xí)算法FedAvg做了比對(duì).為了排除無關(guān)因素的影響，我們控制2種算法的實(shí)現(xiàn)條件基本相同，包括參與者之間的數(shù)據(jù)劃分、全局模型初始化數(shù)值和一些參數(shù)設(shè)置.實(shí)驗(yàn)中，我們?cè)O(shè)置每輪聚合中參與者個(gè)數(shù)K=10,本地批大小B=5,本地時(shí)期E=5,學(xué)習(xí)率n=0.01.我們用MNIST和CIFAR-10數(shù)據(jù)集及其模型組合共進(jìn)行了4組實(shí)驗(yàn)，分別測試最終模型在各個(gè)參與者本地?cái)?shù)據(jù)集上的準(zhǔn)確率，得到1組數(shù)值.我們將整個(gè)準(zhǔn)確率區(qū)間0～1共分為50份，統(tǒng)計(jì)這組數(shù)值落入對(duì)應(yīng)區(qū)間的客戶數(shù)目，畫出頻數(shù)分布直方圖.圖3展示了α-FedAvg和FedAvg算法經(jīng)過100輪聚合后，最終模型在各個(gè)參與者的準(zhǔn)確率分布圖，曲線部分為準(zhǔn)確率數(shù)組的核密度估計(jì)，通過核密度估計(jì)圖可以比較直觀地看出數(shù)據(jù)樣本本身的分布特征.以圖3(a)為例，通過左右2部分子圖對(duì)比，我們可以看出α-FedAvg算法中參與者準(zhǔn)確率分布更集中，曲線更陡峭，從而反映出參與者之間準(zhǔn)確率方差更小，系統(tǒng)更公平.

表2進(jìn)一步描述了2種算法得到的參與者準(zhǔn)確率的統(tǒng)計(jì)分布和系統(tǒng)度量對(duì)比，其中T表示中央聚合次數(shù),E表示有效度量，J表示公平度量.我們選取了T=5和T=100的情況研究聚合次數(shù)是否對(duì)算法表現(xiàn)造成影響.從表2中可以看出，無論是T=5或T=100，本文所提的α-FedAvg算法都可以提升聚合模型的公平和有效性，且在保持參與者的平均準(zhǔn)確率不變或略有增加的情況下，提升最壞參與者的準(zhǔn)確率，降低最好參與者的準(zhǔn)確率，減小參與者之間準(zhǔn)確率分布的方差，即α-FedAvg算法可在達(dá)到公平需求的同時(shí)保持總體性能不受影響.

Table 2 Statistics of the Test Accuracy Distribution for Our Algorithm Compared with Normal Federated Learning Algorithm FedAvg表2 本文算法與常規(guī)聯(lián)邦學(xué)習(xí)算法FedAvg相比在測試集上的準(zhǔn)確率分布

Fig. 4 Training loss and average accuracy changing with the communication rounds圖4 訓(xùn)練損失和平均準(zhǔn)確率隨聚合次數(shù)的變化

α-FedAvg算法取得的公平性已在圖3和表2得到了論證.接下來我們會(huì)進(jìn)一步研究它的有效性.在訓(xùn)練中，我們記錄每一輪聚合后的模型在參與者本地訓(xùn)練數(shù)據(jù)上的平均準(zhǔn)確率和損失函數(shù)值，畫出圖4所示曲線.從圖4(a)中可以看出，本文提出的α-FedAvg算法與經(jīng)典聯(lián)邦學(xué)習(xí)算法FedAvg的收斂速度基本一致；從圖4(b)中可以看出，2種算法在訓(xùn)練集上的平均準(zhǔn)確率變化情況也大致相同.圖4再一次說明我們的算法是有效的，在追求公平需求的同時(shí)不會(huì)影響聯(lián)邦學(xué)習(xí)的整體性能.

4.3 其他對(duì)比實(shí)驗(yàn)

Fig. 5 Changes of the number of participants under different test accuracy intervals in three algorithms圖5 3種算法中參與者個(gè)數(shù)在不同測試準(zhǔn)確率區(qū)間的變化

在本節(jié)中，我們將α-FedAvg與已發(fā)表的其他在聯(lián)邦學(xué)習(xí)中施加公平約束的方案作了對(duì)比，與我們工作相似的最新成果是2020年發(fā)表的文獻(xiàn)[9，21].在文獻(xiàn)[9]中，該文作者提出了一種新的更公平的聯(lián)邦學(xué)習(xí)優(yōu)化目標(biāo)q-FFL,為了解決這一優(yōu)化目標(biāo)，設(shè)計(jì)了一種高效的學(xué)習(xí)算法q-FedAvg,它能有效降低學(xué)習(xí)到的最終模型在設(shè)備間準(zhǔn)確率分布的方差，同時(shí)保證平均準(zhǔn)確率不受影響.文獻(xiàn)[21]中作者提出了算法FedFa,它通過參與者的頻率和準(zhǔn)確率來調(diào)整聚合權(quán)重，使最終模型對(duì)參與者來說更公平.我們分別復(fù)現(xiàn)它們?cè)赩ehicle，Sent140，Synthetic，F(xiàn)emnist[27]數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果，并在此基礎(chǔ)上實(shí)現(xiàn)了我們的算法和基準(zhǔn)算法FedAvg.其中Vehicle為圖像數(shù)據(jù)集，由23個(gè)傳感器中收集的聲學(xué)、地震和紅外傳感器數(shù)據(jù)組成.我們將每個(gè)傳感器作為一個(gè)參與者，模型使用SVM完成基本的二分類問題.Sent140數(shù)據(jù)集是用于情感分析任務(wù)的文本數(shù)據(jù)集，模型使用2層長短期記憶網(wǎng)絡(luò)(LSTM)和一個(gè)密集連接層.Synthetic是一個(gè)采用文獻(xiàn)[28]中設(shè)定的合成數(shù)據(jù)集，使用簡單的回歸模型來做分類任務(wù).Femnist是一個(gè)衣物圖像數(shù)據(jù)集，模型使用MLP.圖5展示了α-FedAvg與其他2種算法在相同條件下訓(xùn)練得到的最終模型在參與者本地?cái)?shù)據(jù)集上準(zhǔn)確率的分布情況.可以看出相比于FedAvg,α-FedAvg的曲線更陡峭，直方圖更集中，方差更??；q-FFL與α-FedAvg結(jié)果較為接近.

我們?cè)诒?中進(jìn)一步報(bào)告了最終準(zhǔn)確率的統(tǒng)計(jì)分布，包括平均準(zhǔn)確率、最壞10%準(zhǔn)確率、最好10%準(zhǔn)確率和方差.可以看出，在其他3個(gè)數(shù)據(jù)集上，α-FedAvg算法在保證平均準(zhǔn)確率與基準(zhǔn)算法FedAvg相似甚至略好的情況下，參與者之間的準(zhǔn)確率方差都比其他2種公平算法更小一點(diǎn).而q-FFL雖然在Sent140上方差小于α-FedAvg，但相較于基準(zhǔn)算法，損失了準(zhǔn)確率.而α-FedAvg算法既保證了有效性又保證了公平性.

Table 3 Statistics of the Test Accuracy Distribution for Our Algorithm Compared with q-FFL and FedFa表3 本文算法與q-FFL, FedAvg和FedFa相比在測試集上的準(zhǔn)確率分布統(tǒng)計(jì)

Table 4 Model Performance Under Data Distribution Shift表4 在數(shù)據(jù)分布轉(zhuǎn)移下的模型性能

從表4中可以看出，我們的算法測試準(zhǔn)確率和公平性都介于不加公平約束的AgnosticFair-a和AgnosticFair算法之間.這說明算法α-FedAvg在測試集存在分布轉(zhuǎn)移時(shí)也是有一定公平作用的，因?yàn)槲覀冊(cè)诿枯喼惺占藴y試集上的準(zhǔn)確率來調(diào)整權(quán)重.AgnosticFair算法在該場景下能達(dá)到較好的公平性，但是可能會(huì)以犧牲準(zhǔn)確率為代價(jià).

5 總結(jié)和未來展望

在本文中，我們提出了一種新的聯(lián)邦學(xué)習(xí)算法α-FedAvg，使聚合模型在參與者本地?cái)?shù)據(jù)上的準(zhǔn)確率分布更均衡.首先，類比資源分配領(lǐng)域，我們給出了聯(lián)邦學(xué)習(xí)系統(tǒng)公平和有效性的度量方法；然后我們引入了α-fairness并研究了參數(shù)α對(duì)公平和有效性的影響，通過一種算法確定了我們需要的α值；最后根據(jù)求得的α值和權(quán)重pk計(jì)算公式對(duì)聚合過程重新加權(quán)，提出了α-FedAvg算法.α-FedAvg可在保持與經(jīng)典聯(lián)邦學(xué)習(xí)算法FedAvg同等有效性的基礎(chǔ)上，使參與者之間準(zhǔn)確率方差更小，即聚合結(jié)果更公平，實(shí)驗(yàn)結(jié)果證明了我們提出的方法是有效的.進(jìn)一步的工作也非常具有吸引力.特別是，研究如何抵御上傳偽造模型參數(shù)來影響聚合模型公平的惡意攻擊者，并設(shè)計(jì)適用于本文算法的激勵(lì)機(jī)制，鼓勵(lì)更多的參與者加入我們的聚合過程.

作者貢獻(xiàn)聲明：田家會(huì)提出研究思路，設(shè)計(jì)研究方案，負(fù)責(zé)實(shí)驗(yàn)設(shè)計(jì)和撰寫論文；趙斌提出研究思路，設(shè)計(jì)研究方案；呂錫香、鄒仁朋和李一戈參與論文修訂.