在線異步聯(lián)邦學(xué)習(xí)的客戶優(yōu)化選擇與激勵

顧永跟 馮洲洋 吳小紅 陶杰

摘 要：聯(lián)邦學(xué)習(xí)能夠在保護(hù)用戶隱私的前提下，使不同的客戶端合作共同訓(xùn)練同一模型，如何激勵高質(zhì)量的客戶端參與聯(lián)邦學(xué)習(xí)是關(guān)鍵。在線聯(lián)邦學(xué)習(xí)環(huán)境中，由于參與訓(xùn)練的客戶端隨機到達(dá)和離開，每輪參與報價的客戶端動態(tài)變化，對客戶端的在線質(zhì)量評估與選擇是一個難題。針對這一挑戰(zhàn)提出了在線聯(lián)邦學(xué)習(xí)激勵算法，以優(yōu)化在線客戶端的選擇和預(yù)算分配，提高預(yù)算約束下在線環(huán)境聯(lián)邦學(xué)習(xí)的性能。該算法將預(yù)算按階段劃分并根據(jù)歷史樣本信息計算最優(yōu)的質(zhì)量密度閾值，其主要思想是對客戶端模型質(zhì)量進(jìn)行動態(tài)評估，在此基礎(chǔ)上采用質(zhì)量閾值準(zhǔn)入機制，同時對參與訓(xùn)練的客戶端數(shù)量進(jìn)行限制。從理論上證明了激勵算法滿足激勵相容性、預(yù)算可行性和個體理性。實驗結(jié)果表明，提出的在線激勵算法在不同比例搭便車客戶端的情況下都能有良好的性能，在預(yù)算充足且有搭便車和有誤標(biāo)標(biāo)簽的客戶端情況下比已有方法在EMNIST-B和CIFAR-10兩個數(shù)據(jù)集上分別提高約4%和10%。

關(guān)鍵詞：聯(lián)邦學(xué)習(xí)；激勵機制；質(zhì)量評估；在線場景；客戶端篩選

中圖分類號：TP391?? 文獻(xiàn)標(biāo)志碼：A

文章編號：1001-3695（2024）03-009-0700-06

doi：10.19734/j.issn.1001-3695.2023.08.0333

Optimization selection and incentives of client in

online asynchronous federated learning

Gu Yonggen1，2，F(xiàn)eng Zhouyang1，Wu Xiaohong1，2，Tao Jie1

（1.School of Information Engineering，Huzhou University，Huzhou Zhejiang 313000，China；2.Zhejiang Province Key Laboratory of Smart Management & Application of Modern Agricultural Resources，Huzhou Zhejiang 313000，China）

Abstract：Federated learning enables different clients to collaborate and train a shared model while preserving user privacy.Motivating high-quality clients to participate in federated learning is crucial.In online federated learning environments，clients join and leave training dynamically，evaluating and selecting clients in real-time poses a challenge.To address this challenge，this paper proposed an online federated learning incentive algorithm to optimize client selection and budget allocation，thereby enhancing the performance of federated learning under budget constraints.The proposed algorithm divided the budget into stages and computed optimal quality density thresholds based on historical sample information.The main idea was to dynamically assess the quality of client models and employ a quality threshold admission mechanism while limiting the number of participating clients.In theory，this paper proved that the incentive algorithm satisfied incentive compatibility，budget feasibility，and individual rationality.Experimental results demonstrate that the proposed online incentive algorithm achieves good performance in scenarios with different proportions of free-riding clients.Specifically，compared to existing methods，it achieves approximately 4% and 10% improvements on the EMNIST-B and CIFAR-10 datasets，respectively，under sufficient budget and in the presence of free-riding and mislabeled clients.

Key words：federated learning；incentive mechanism；quality evaluation；online environment；client selection

0 引言

機器學(xué)習(xí)作為實現(xiàn)人工智能的基本方法，已在眾多領(lǐng)域中得到應(yīng)用。隨著信息安全的普及，人們越來越注重數(shù)據(jù)的安全。而傳統(tǒng)的機器學(xué)習(xí)在隱私保護(hù)方面有所欠缺，無法滿足實際需求。隨著移動智能終端技術(shù)的發(fā)展，大量具有高分辨率傳感器的物聯(lián)網(wǎng)設(shè)備、智能手機和自動駕駛汽車都連接到高速網(wǎng)絡(luò)［1］。據(jù)統(tǒng)計，2022年全球有近144億臺聯(lián)網(wǎng)物聯(lián)網(wǎng)設(shè)備，預(yù)計到2025年將有大約270億臺聯(lián)網(wǎng)物聯(lián)網(wǎng)設(shè)備［2］。這些終端設(shè)備在使用時會收集大量的數(shù)據(jù)，這些數(shù)據(jù)對于設(shè)備或軟件廠商有很重要的研究和分析價值。在傳統(tǒng)的云中心方法中，設(shè)備收集的數(shù)據(jù)需要上傳至云服務(wù)器或數(shù)據(jù)中心進(jìn)行集中式的訓(xùn)練分析，然而這種方法不利于數(shù)據(jù)安全和隱私保護(hù)。

為解決隱私問題，谷歌的研究團隊率先提出了一種新興的機器學(xué)習(xí)范式——聯(lián)邦學(xué)習(xí)（federated learning，F(xiàn)L）［3］。其不同于傳統(tǒng)的集中式機器學(xué)習(xí)，參與設(shè)備無須將本地數(shù)據(jù)上傳至服務(wù)器，只需從服務(wù)器接收模型參數(shù)，通過設(shè)備上的數(shù)據(jù)進(jìn)行本地訓(xùn)練，訓(xùn)練后只需將更新后的模型參數(shù)上傳給服務(wù)器，服務(wù)器會根據(jù)收到的所有模型參數(shù)更新得到新的全局模型。以此往復(fù)，直至全局模型收斂。

聯(lián)邦學(xué)習(xí)能得到成功應(yīng)用的關(guān)鍵在于大量高質(zhì)量客戶端或設(shè)備參與聯(lián)合模型訓(xùn)練。目前的研究大多假設(shè)設(shè)備無條件自愿參與聯(lián)邦學(xué)習(xí)訓(xùn)練，而現(xiàn)實中

在沒有報酬的情況下，移動設(shè)備所有者往往

缺乏參與意愿。同時，目前大部分研究關(guān)注于靜態(tài)同步更新的場景，即服務(wù)器接收到所有參與者更新后進(jìn)行聚合，然而實際場景下，設(shè)備在訓(xùn)練中可能隨機離開或加入，這給聯(lián)邦學(xué)習(xí)的訓(xùn)練過程帶來了不確定性。針對上述兩個問題，本文將考慮在跨設(shè)備聯(lián)邦學(xué)習(xí)中，如何在不確定環(huán)境下，以有限的預(yù)算招募高質(zhì)量的客戶端參與聯(lián)邦學(xué)習(xí)，得到一個性能良好的全局模型。為達(dá)到上述目標(biāo)，本文提出了基于客戶端模型質(zhì)量的在線聯(lián)邦學(xué)習(xí)激勵算法，以此激勵客戶端積極參與聯(lián)合模型訓(xùn)練。

在最初提出的聯(lián)邦學(xué)習(xí)模式中，服務(wù)器在每輪會從客戶端中隨機選擇一定數(shù)量的客戶端參與訓(xùn)練。而這樣的設(shè)定在處理non-IID數(shù)據(jù)時會導(dǎo)致準(zhǔn)確率大幅降低［4］，因此客戶端選擇算法在針對客戶端數(shù)據(jù)分布不均衡時會產(chǎn)生很大的影響。Nishio等人［1］提出了一個FedCS算法，該算法會從隨機選擇的客戶端中篩選，在每輪訓(xùn)練開始前候選設(shè)備會向服務(wù)器發(fā)送計算能力、通信能力和數(shù)據(jù)量大小，服務(wù)器根據(jù)這些數(shù)據(jù)以貪心的思想盡可能多地選擇參與者。Abdulrahman等人［5］提出FedMCCS算法，采用分層抽樣過濾客戶端，通過客戶端的本地資源來預(yù)測客戶端能否完成任務(wù)。郭佳慧等人［6］將背包模型引入客戶端選擇，結(jié)合客戶端本地更新前后本地模型的權(quán)重差異，提出了OfflineKP-FL方法應(yīng)用于離線場景。

單一的客戶端選擇算法在全局模型的精度上有所提高，但現(xiàn)實中客戶端在服務(wù)器不提供報酬的情況下會表現(xiàn)出理性，不愿免費幫助服務(wù)器訓(xùn)練，并且會出現(xiàn)搭便車等惡意行為。因此有研究將激勵機制引入聯(lián)邦學(xué)習(xí)，一個好的激勵機制既可以幫助服務(wù)器選擇優(yōu)質(zhì)的客戶端參與訓(xùn)練，同時也能激勵更多的客戶端參與到聯(lián)邦學(xué)習(xí)中。在激勵機制中，對于客戶端訓(xùn)練的本地模型的評估，是選擇參與者的重要指標(biāo)，全局模型的性能取決于每個客戶端的貢獻(xiàn)［7］。目前在聯(lián)邦學(xué)習(xí)應(yīng)用中主要有三種貢獻(xiàn)度量策略，即基于測試/自我報告的貢獻(xiàn)評估、基于邊際損失的貢獻(xiàn)評估和基于相似度的貢獻(xiàn)評估［8］。Deng等人［9］將客戶端本地訓(xùn)練時的損失作為衡量客戶端貢獻(xiàn)的基礎(chǔ)。Wang等人［10］針對水平聯(lián)邦學(xué)習(xí)提出了一種直觀的刪除法來計算不同客戶端在聯(lián)邦學(xué)習(xí)中的貢獻(xiàn)，通過對比刪除某一個客戶端后所形成的全局模型與原始模型之間的差異來衡量某個客戶端的貢獻(xiàn)。Nishio等人［11］設(shè)計一種沒有開銷流量且只有少量計算開銷的逐步貢獻(xiàn)計算的直觀方法。Zhang等人［12］提出一種計算綜合聲譽的方法，以此來衡量客戶端的訓(xùn)練和數(shù)據(jù)質(zhì)量。

根據(jù)不同的衡量標(biāo)準(zhǔn)，國內(nèi)外的研究團隊提出了相應(yīng)的激勵機制。目前在聯(lián)邦學(xué)習(xí)中應(yīng)用的激勵機制主要有博弈論、拍賣和契約理論三種，而拍賣方式擁有優(yōu)秀的屬性，它可以作為聯(lián)邦學(xué)習(xí)激勵機制的一個解決方案［13］。反向拍賣是一種與普通拍賣相反的拍賣形式，在反向拍賣中，有一個買家和多個賣家，在聯(lián)邦學(xué)習(xí)的架構(gòu)下，服務(wù)器可以看作是買家，而客戶端則可以看作是賣家。Fan等人［14］設(shè)計了一種基于客戶端數(shù)據(jù)量、EMD距離和報價的反向拍賣機制。但EMD距離通常包含客戶端的數(shù)據(jù)分布，屬于客戶端的私有信息，現(xiàn)實中往往不會提供給服務(wù)器。因此，Zhang等人［12］提出了一種基于聲譽的反向拍賣機制，聲譽可以間接地反映客戶端的數(shù)據(jù)質(zhì)量。

上述激勵機制的研究大多基于離線場景，會在聯(lián)邦學(xué)習(xí)開始前進(jìn)行客戶端的選擇，之后不再接受新的報價［15］。但在現(xiàn)實情況中，客戶端可能會陸續(xù)到達(dá)，也可能會提前離開，這也使得現(xiàn)實場景更加復(fù)雜，現(xiàn)有的離線算法大多無法直接應(yīng)用。動態(tài)不確定環(huán)境下的資源優(yōu)化利用問題是一個經(jīng)典的研究問題，已有大量的研究。在與聯(lián)邦學(xué)習(xí)工作流程相似的眾包領(lǐng)域，Zhao等人［16］討論了在線眾包場景下的激勵機制，基于在線拍賣模型設(shè)計了在線機制。在私有云采購領(lǐng)域，Han等人［17］提出了一種剩余資源在線順序采購拍賣，幫助云供應(yīng)商在在線環(huán)境中采購服務(wù)器。聯(lián)邦學(xué)習(xí)作為一個新的研究領(lǐng)域，同樣面臨參與訓(xùn)練者的隨機性和動態(tài)不確定，在預(yù)算約束下如何在客戶隨機到達(dá)的情況下合理分配預(yù)算，優(yōu)化選擇客戶端是提高聯(lián)邦學(xué)習(xí)效率的一個關(guān)鍵問題。Mohammed等人［18］根據(jù)秘書問題思想，選擇在測試精度方面最好的候選客戶端參與訓(xùn)練。然而這會侵犯第一階段的消費者主權(quán)，因此客戶端傾向于推遲到達(dá)，從而使得任務(wù)“饑餓”。Zhang等人［15］設(shè)計了一個反向拍賣機制，將候選者分成兩組，相互作對照組進(jìn)行參與者選擇。

為適應(yīng)現(xiàn)實中的在線場景，本文結(jié)合已有的激勵機制和在線場景的解決方案，提出了一個預(yù)算約束下的在線聯(lián)邦學(xué)習(xí)激勵算法。該算法能夠在客戶端隨機到達(dá)的情況下合理分配預(yù)算動態(tài)選擇客戶端。并對已有的質(zhì)量評估方法進(jìn)行了改進(jìn)，通過刪除法計算模型在驗證集上的損失來衡量客戶端本地訓(xùn)練的模型對于全局模型的貢獻(xiàn)，將客戶端所訓(xùn)練模型的質(zhì)量和報價作為選擇客戶端的標(biāo)準(zhǔn)。

1 系統(tǒng)模型

在線場景的定義即不同客戶端的到達(dá)和離開時間是隨機不確定的。因此，在客戶端每輪都變化的情況下選擇高質(zhì)量的客戶端參與訓(xùn)練是一個難題。

在一個聯(lián)邦學(xué)習(xí)的系統(tǒng)中，有一個任務(wù)發(fā)布者以及中央服務(wù)器和N個客戶端（包括移動設(shè)備、物聯(lián)網(wǎng)設(shè)備等），客戶端集合用Euclid Math OneNAp={1，2，…，N}表示。任務(wù)發(fā)布者通過招募更多客戶端協(xié)助中央服務(wù)器訓(xùn)練一個高質(zhì)量的模型，任務(wù)發(fā)布者會以總預(yù)算B發(fā)布一個T輪全局迭代的聯(lián)邦學(xué)習(xí)任務(wù)?，F(xiàn)實中客戶端會在空閑時參與訓(xùn)練，當(dāng)客戶端本地任務(wù)繁忙時結(jié)束訓(xùn)練，因此站在服務(wù)器的視角，客戶端會隨機到達(dá)與離開。當(dāng)任務(wù)發(fā)布者發(fā)布任務(wù)后，空閑的客戶端可以向服務(wù)器發(fā)送報價，同時每個客戶端有參加訓(xùn)練的成本，為私有信息，bti表示第t輪客戶端i向中央服務(wù)器的報價。受到總預(yù)算的限制，任務(wù)發(fā)布者需要在每次全局迭代開始前從已經(jīng)報價的客戶端集合Nt中選擇一批客戶端St參與聯(lián)邦學(xué)習(xí)，其中StNtEuclid Math OneNAp。任務(wù)發(fā)布者會在每輪訓(xùn)練結(jié)束后給參與訓(xùn)練的客戶端相應(yīng)的報酬pti。為了能更好地選擇高質(zhì)量的客戶端參與訓(xùn)練，中央服務(wù)器會評估參與訓(xùn)練客戶端上傳模型的質(zhì)量，用qti表示客戶端i參與第t輪訓(xùn)練的模型質(zhì)量，以此來評估客戶端的訓(xùn)練質(zhì)量。詳細(xì)的聯(lián)邦學(xué)習(xí)流程如圖1所示，展現(xiàn)了一次全局迭代的流程。

其中：xti表示任務(wù)發(fā)布者是否在第t輪選擇客戶端i參與訓(xùn)練。xti=1時，客戶端i會參與第t輪的訓(xùn)練；xti=0時，客戶端i則不會參與第t輪的訓(xùn)練。設(shè)計的機制在追求客戶端模型質(zhì)量最大化的同時，需要滿足以下三個性質(zhì)：a）預(yù)算可行性，即支出不能超過總預(yù)算；b）激勵相容性，即客戶端每次報價等于其真實成本；c）個人理性，即支付給參與訓(xùn)練客戶端的報酬大于等于其報價。

2 在線聯(lián)邦學(xué)習(xí)激勵機制設(shè)計

2.1 分階段在線預(yù)算分配和質(zhì)量評估

在線環(huán)境中，每輪能夠參與聯(lián)邦學(xué)習(xí)的客戶端會隨著時間的推移而變動，傳統(tǒng)的隨機選擇客戶端方式在模型的準(zhǔn)確率和收斂速度上都會存在一定程度的影響；同時由于預(yù)算限制，服務(wù)器需要在全局迭代中合理分配預(yù)算，使得整個聯(lián)邦學(xué)習(xí)都有客戶端參與訓(xùn)練；而客戶端往往都是自私的，在沒有限制措施的情況下會出現(xiàn)搭便車、誤標(biāo)標(biāo)簽和謊報價格等情況。因此，需要同時解決預(yù)算分配、客戶端訓(xùn)練質(zhì)量評估、客戶端選擇以及報酬支付四個難題。

McMahan等人［3］在最初的聯(lián)邦學(xué)習(xí)設(shè)想中并未考慮動態(tài)變化的客戶端集合，而是假定有一群固定的客戶端集合，每輪會從這些客戶端中選擇一定比例的客戶端參與聯(lián)邦學(xué)習(xí)。然而現(xiàn)實中客戶端參與時間具有不確定性，這也使得預(yù)算的分配成為一個難題，若簡單地將總預(yù)算平均分配到每一輪，會出現(xiàn)客戶端少時的預(yù)算浪費和客戶端多時的預(yù)算不足。針對此特點，本文采用文獻(xiàn)［17］所提出的多階段采樣接收方法，將T輪聯(lián)邦學(xué)習(xí)劃分為L=log2T」+1個階段，如圖2所示，每個階段內(nèi)期望訓(xùn)練輪次是前一階段的兩倍。特別地，當(dāng)總訓(xùn)練輪數(shù)T不是2的指數(shù)次冪時，早期階段的輪數(shù)可隨實際情況變化。每一輪訓(xùn)練開始前會有一個單位時間來等待客戶端報價，然后服務(wù)器會根據(jù)接收到的客戶端報價進(jìn)行選擇參與訓(xùn)練的客戶端。本文方法將根據(jù)單位時間內(nèi)報價的客戶端數(shù)量調(diào)整訓(xùn)練輪次。預(yù)算按照階段進(jìn)行劃分，因每個階段內(nèi)期望輪次是前一階段的兩倍，所以從第一個階段開始，預(yù)算分別為21-LB，21-LB，22-LB，…，2-L+l-1，2-1B，除第一個階段外，其余階段的預(yù)算都是前一個階段的兩倍。一個階段內(nèi)的所有訓(xùn)練輪次將共享該階段的預(yù)算，在出現(xiàn)參與者數(shù)量波動時能根據(jù)選擇的參與者靈活調(diào)整支付的費用。由于存在不確定性，預(yù)算可能在階段內(nèi)提前耗盡，也可能在階段結(jié)束時還存在剩余，這些剩余的預(yù)算不會被再次分配或使用。這些歷史階段的預(yù)算使用情況和客戶端到達(dá)數(shù)據(jù)將在下一階段成為優(yōu)化客戶端選擇的依據(jù)。本文將所有客戶端每輪的報價信息保存在樣本集中，在每個階段結(jié)束時，通過樣本集中的信息計算一個客戶端質(zhì)量密度閾值，該閾值將會在下一個階段中作為客戶端選擇的參數(shù)。

計算質(zhì)量密度閾值的基礎(chǔ)是客戶端質(zhì)量評估。質(zhì)量評估是客戶端選擇的一個重要指標(biāo)，它不僅在每輪客戶端選擇時會用到，同時在每個階段結(jié)束時的閾值計算中也會用到。在第1章相關(guān)工作中已經(jīng)介紹了目前已有的客戶端貢獻(xiàn)的評估方法。文獻(xiàn)［10］提出的刪除法能夠直觀地展現(xiàn)出各個客戶端使用本地數(shù)據(jù)更新的本地模型對于全局模型的貢獻(xiàn)，其將客戶端i的影響定義為influence-i=1n∑nj=1|j--ij|，其中n是數(shù)據(jù)集的大小，j是所有客戶端訓(xùn)練的模型聚合的全局模型對第j個實例的預(yù)測結(jié)果，-ij是除了客戶端i外其他客戶端的模型聚合后的模型對第j個實例的預(yù)測結(jié)果。然而計算預(yù)測值在某些情況下會出現(xiàn)較大的波動，本文將除去客戶端i聚合后的模型在驗證集上的損失作為衡量客戶端影響的標(biāo)準(zhǔn)。該模型損失越大則代表客戶端i對全局模型的影響越大，即客戶端i的模型質(zhì)量較好；損失越小則代表客戶端i對全局模型的影響越小，即客戶端i的模型質(zhì)量較差。本文具體的質(zhì)量評估方法將在3.2節(jié)詳細(xì)介紹。

2.2 預(yù)算約束下的在線聯(lián)邦學(xué)習(xí)激勵算法

在線環(huán)境中，每輪能夠參與聯(lián)邦學(xué)習(xí)的客戶端是動態(tài)變化的，預(yù)算分配成為難題。同時，客戶端是自私的，如果沒有合適的激勵機制，客戶端存在搭便車、誤標(biāo)標(biāo)簽和謊報價格等情況。針對上述難點，本文參考文獻(xiàn)［17］中所提出的在線順序采購機制（online sequential procurement with budget constraint，OSPB），針對聯(lián)邦學(xué)習(xí)場景，優(yōu)化機制并提出了預(yù)算約束下的在線聯(lián)邦學(xué)習(xí)激勵算法（incentive algorithm for online federated learning，IAOFL）。OSPB機制是一個云服務(wù)器資源采購的算法，雖然與在線聯(lián)邦學(xué)習(xí)場景類似，但無法直接將該算法應(yīng)用于聯(lián)邦學(xué)習(xí)場景。因此，本文對OSPB機制進(jìn)行了改進(jìn)，使其能夠適用于聯(lián)邦學(xué)習(xí)的場景。改進(jìn)點如下：a）引入客戶端模型質(zhì)量代替原算法中的邊際需求估值；b）設(shè)計min_num和max_num兩個參數(shù)來限制參與聯(lián)邦學(xué)習(xí)的客戶端數(shù)量，以此避免由閾值選擇客戶端數(shù)量的波動而造成模型精度的波動。

3 實驗分析

3.1 實驗設(shè)置

本節(jié)將會評估IAOFL與其他激勵機制在在線環(huán)境下的性能。實驗將采用EMNIST-Balanced［20］和CIFAR-10［21］兩個數(shù)據(jù)集進(jìn)行實驗。其中EMNIST-Balanced有47個標(biāo)簽類別，包含數(shù)字和字母，圖片大小為28×28的灰度圖像。數(shù)據(jù)集中共包含112 800個訓(xùn)練樣本和18 800個測試樣本。數(shù)據(jù)集的訓(xùn)練采用卷積神經(jīng)網(wǎng)絡(luò)架構(gòu)，包括兩層5×5的卷積層，每個卷積層后是ReLU激活函數(shù)和2×2的最大池化層。CIFAR-10包含10類不同類別的圖像，圖片大小為32×32的彩色圖像。數(shù)據(jù)集共包含50 000個訓(xùn)練樣本和10 000個測試樣本。數(shù)據(jù)集的訓(xùn)練采用三層5×5的卷積層，每個卷積層后是ReLU激活函數(shù)和2×2的最大池化層。

實驗中共有100個客戶端，數(shù)據(jù)集中的訓(xùn)練樣本將以獨立同分布的方式平均分配給這100個客戶端。為體現(xiàn)不同客戶端的質(zhì)量，實驗中將會設(shè)置部分搭便車和存在誤標(biāo)標(biāo)簽的低質(zhì)量客戶端。搭便車客戶端不會進(jìn)行本地訓(xùn)練，包含誤標(biāo)標(biāo)簽的客戶端會有30％標(biāo)簽存在誤標(biāo)。每個客戶端的到達(dá)符合泊松分布，會在每輪加入適當(dāng)?shù)脑肼晛頂U大不同輪次客戶端到達(dá)數(shù)量的差異。到達(dá)后的報價在［0，1］隨機生成，由于客戶端的數(shù)據(jù)量是相同的，所以報價可以代表每個客戶端所有數(shù)據(jù)的價值。

為了在在線環(huán)境中進(jìn)行比較，共挑選了兩個基準(zhǔn)：第一個是OSPB機制（未改進(jìn)的應(yīng)于云服務(wù)器資源采購的在線算法）；第二個是OSPM（online selection and payment mechanism）機制［15］，該機制通過客戶端的聲譽與報價進(jìn)行選擇。為方便比較，將算法中的客戶端聲譽替換為客戶端質(zhì)量，并將客戶端的報價調(diào)整為與本文場景一致。

3.2 質(zhì)量評估

為了評估模型質(zhì)量，將兩個數(shù)據(jù)集中測試樣本劃分一半作為驗證集，用于評估客戶端訓(xùn)練質(zhì)量，剩余一半樣本用作全局模型的測試。第3.1節(jié)中已經(jīng)闡述了可以運用刪除客戶端i后聚合的模型在驗證集上的損失大小代表客戶端i對全局模型的貢獻(xiàn)，因此將貢獻(xiàn)定義為

lossti=L（ωt-i）=1n∑ni=1L（xi，yi：ωt-i）（2）

其中：ωt-i表示除客戶端i外其他參與訓(xùn)練客戶端所聚合的模型；n為驗證集的大小。而losst={lossti|i∈St}表示第t輪所有參與訓(xùn)練客戶端貢獻(xiàn)的集合。然而隨著模型的訓(xùn)練，用刪除法計算的損失會逐漸減小，直接使用該損失會對整個算法造成影響，因此在實驗中會對損失進(jìn)行歸一化處理：

qti=min（lossti-min（losst）max（losst）-min（losst），ε）（3）

其中：ε是一個很小的正數(shù)，使得質(zhì)量大于0。處理之后的質(zhì)量將會映射到［ε，1］。而客戶端i的最新質(zhì)量定義為qlatesti=average（qi），qi是客戶端i歷史質(zhì)量集合，即計算客戶端歷史質(zhì)量的平均值。在選擇客戶端時會使用qlatesti進(jìn)行比較和計算，通過所有歷史質(zhì)量計算出的結(jié)果更能表示客戶端的質(zhì)量。

由于L（ωt-i）能夠在一定程度上代表客戶端i在第t輪對全局模型的貢獻(xiàn)，所以可以通過比較L（ωt-i）和L（ωt）來判斷客戶端i是否對全局模型有正向貢獻(xiàn)。當(dāng)L（ωt-i）

3.3 實驗結(jié)果

本文進(jìn)行了兩組對比實驗來驗證IAOFL算法在不同場景和不同數(shù)據(jù)集上的表現(xiàn)。

a）如圖3所示，是在預(yù)算256的情況下進(jìn)行512輪聯(lián)邦學(xué)習(xí)后得到的模型精度。設(shè)置了不同百分比搭便車客戶端，用這些客戶端模擬現(xiàn)實中的客戶端。從圖3（a）可以看出，IAOFL算法和OSPB機制通過動態(tài)選擇客戶端能夠得到比OSPM更高的準(zhǔn)確率，而改進(jìn)后的IAOFL算法對比OSPB機制也有一定的提升。綜合來看，在EMNIST-B數(shù)據(jù)集上，本文提出的IAOFL算法的平均精度比OSPM和OSPB機制分別高出5%和1%。圖3（b）則是在相對較難的數(shù)據(jù)集CIFAR-10上的表現(xiàn)，可以看出本文IAOFL算法有較好的性能，在不同比例的搭便車客戶端情況下都能訓(xùn)練出優(yōu)于基準(zhǔn)的模型。IAOFL算法的平均精度比OSPM和OSPB機制分別高出14%和6%。

b）圖4是三種算法在預(yù)算為320的情況下經(jīng)過512輪訓(xùn)練后的結(jié)果，100個客戶端中有10%的搭便車客戶端和10%存在誤標(biāo)標(biāo)簽的客戶端。IOAFL算法由于加入了客戶端數(shù)量限制和惡意客戶端篩選，能在聯(lián)邦學(xué)習(xí)的過程中跟隨客戶端到達(dá)的數(shù)量和訓(xùn)練的質(zhì)量進(jìn)行動態(tài)調(diào)整，從而聚合出模型精度更高的模型。在EMNIST-B數(shù)據(jù)集上，本文提出的IAOFL算法對比其他兩個基準(zhǔn)能有4%的精度提升；在CIFAR-10數(shù)據(jù)集上，IAOFL算法對比基準(zhǔn)分別有10%和8%的精度提升。

表1中總結(jié)了不同場景中三種機制的性能表現(xiàn)，能夠看出，本文提出的IAOFL算法在不同預(yù)算和惡意客戶端類型的情況下都能取得更高的準(zhǔn)確率。同時，在較難的數(shù)據(jù)集上會有比簡單數(shù)據(jù)集上更大的優(yōu)勢，在CIFAR-10數(shù)據(jù)集的訓(xùn)練任務(wù)中，由于訓(xùn)練任務(wù)相對較難，任何惡意客戶端都會對全局模型的聚合產(chǎn)生嚴(yán)重的負(fù)面影響，IAOFL則能夠?qū)Σ糠謵阂饪蛻舳诉M(jìn)行識別，能在一定程度上解決惡意客戶端對全局模型的影響。

3.4 算法應(yīng)用討論

Damaskinos等人［22］指出在線學(xué)習(xí)系統(tǒng)是許多流行應(yīng)用的基礎(chǔ)，比如新聞推薦或交互式社交網(wǎng)絡(luò)（如Facebook、Twitter、Linkedin），這些系統(tǒng)涉及大量具有高時效性的數(shù)據(jù)，通常在幾小時甚至幾分鐘內(nèi)就會過時，意味著數(shù)據(jù)的實時性和及時處理對于這些應(yīng)用至關(guān)重要。本文提出的IAOFL算法在這種環(huán)境中具有顯著的應(yīng)用潛力，算法的核心功能之一是幫助這些軟件公司以合適的價格選擇高質(zhì)量的客戶端進(jìn)行本地訓(xùn)練。由于軟件的使用者遍布全世界，各個地區(qū)的設(shè)備空閑時間存在差異，設(shè)備參與聯(lián)邦學(xué)習(xí)的時間也存在較大差異，這導(dǎo)致不同時間段的參與者數(shù)量會波動。而IAOFL算法能夠很好地適應(yīng)這種環(huán)境，根據(jù)實時的客戶端數(shù)量進(jìn)行自適應(yīng)的聯(lián)邦學(xué)習(xí)，確保在不同時間和地點都能夠高效地利用參與者的計算資源。通過IAOFL算法，能夠選擇高質(zhì)量的客戶端參與訓(xùn)練，且算法始終將客戶端的數(shù)量控制在合理區(qū)間，這能幫助軟件公司訓(xùn)練出更加穩(wěn)健的模型。

在新聞推薦和社交網(wǎng)絡(luò)等領(lǐng)域，IAOFL算法的應(yīng)用有望為實時數(shù)據(jù)處理和個性化推薦帶來顯著的改進(jìn)。通過適應(yīng)性和高效性，它可以提供更快速和精確的結(jié)果，有助于提高用戶體驗和滿足高時效性數(shù)據(jù)應(yīng)用的需求。

4 結(jié)束語

本文針對更加符合實際應(yīng)用的在線場景，提出了預(yù)算約束下的在線聯(lián)邦學(xué)習(xí)激勵算法，更好地幫助任務(wù)發(fā)布者在客戶端動態(tài)變化的場景下選擇高質(zhì)量的客戶端參與聯(lián)邦學(xué)習(xí)。對選擇的客戶端數(shù)量和質(zhì)量進(jìn)行了有效地篩選，以此降低客戶端數(shù)量和惡意客戶端對全局模型的影響。同時，從理論上證明了本文算法具有激勵相容性、個人理性和預(yù)算可行性，并通過實驗驗證了本文算法在有惡意客戶端的情況下可以得到精度更高的模型。

目前質(zhì)量評估中的惡意客戶端篩選在訓(xùn)練后期識別準(zhǔn)確率較低，同時全局模型的聚合采用的是聯(lián)邦平均算法。未來將對篩選規(guī)則進(jìn)行改進(jìn)，使其在后期也能有較好的識別效果，而聚合算法的改進(jìn)也是一個后續(xù)研究的方向。

參考文獻(xiàn)：

［1］Nishio T，Yonetani R.Client selection for federated learning with heterogeneous resources in mobile edge［C］//Proc of IEEE International Conference on Communications.Piscataway，NJ：IEEE Press，2019：1-7.

［2］Hasan M.State of IoT 2022：number of connected IoT devices growing 18% to 14.4 billion globally［EB/OL］.（2022）.https：//iot-analy-tics.com/number-connected-iot-devices/.

［3］McMahan B，Moore E，Ramage D，et al.Communication-efficient learning of deep networks from decentralized data［C］//Proc of the 20th International Conference on Artificial Intelligence and Statistics.2017：1273-1282.

［4］Zhao Yue，Li Meng，Lai Liangzhen，et al.Federated learning with non-IID data［EB/OL］.（2022）［2023-07-01］.https：//arxiv.org/pdf/1806.00582.pdf.

［5］Abdulrahman S，Tout H，Mourad A，et al.FedMCCS：multicriteria client selection model for optimal IoT federated learning［J］.IEEE Internet of Things Journal，2021，8（6）：4723-4735.

［6］郭佳慧，陳卓越，高瑋，等.基于背包模型的聯(lián)邦學(xué)習(xí)客戶端選擇方法［J］.物聯(lián)網(wǎng)學(xué)報，2022，6（4）：158-168.（Guo Jiahui，Chen Zhuoyue，Gao Wei，et al.Clients selection method based on knapsack model in federated learning［J］.Journal of Internet of Things，2022，6（4）：158-168.）

［7］Warrier L C，Ragesh G K.A review on game theoretical incentive mechanism for federated learning［C］//Proc of the 19th IEEE India Council International Conference.Piscataway，NJ：IEEE Press，2022：1-5.

［8］Huang Jiyue，Talbi R，Zhao Zilong，et al.An exploratory analysis on userscontributions in federated learning［C］//Proc of the 2nd IEEE International Conference on Trust，Privacy and Security in Intelligent Systems and Applications.Piscataway，NJ：IEEE Press，2020：20-29.

［9］Deng Yongheng，Lyu Feng，Ren Ju，et al.FAIR：quality-aware federated learning with precise user incentive and model aggregation［C］//Proc of IEEE Conference on Computer Communications.Piscataway，NJ：IEEE Press，2021：1-10.

［10］Wang Guan，Dang C X，Zhou Ziye.Measure contribution of participants in federated learning［C］//Proc of IEEE International Confe-rence on Big Data.Piscataway，NJ：IEEE Press，2019：2597-2604.

［11］Nishio T，Shinkuma R，Mandayam N B.Estimation of individual device contributions for incentivizing federated learning［C］//Proc of IEEE Globecom Workshops.Piscataway，NJ：IEEE Press，2020：1-6.

［12］Zhang Jingwen，Wu Yuezhou，Pan Rong.Incentive mechanism for horizontal federated learning based on reputation and reverse auction［C］//Proc of Web Conference.New York：ACM Press，2021：947-956.

［13］Tu Xuezhen，Zhu Kun，Luong N C，et al.Incentive mechanisms for federated learning：from economic and game theoretic perspective［J］.IEEE Trans on Cognitive Communications and Networking，2022，8（3）：1566-1593.

［14］Fan Sizheng，Zhang Hongbo，Zeng Yuchun，et al.Hybrid blockchain-based resource trading system for federated learning in edge computing［J］.IEEE Internet of Things Journal，2021，8（4）：2252-2264.

［15］Zhang Jingwen，Wu Yuezhou，Pan Rong.Online auction-based incentive mechanism design for horizontal federated learning with budget constraint［EB/OL］.（2022）［2023-07-01］.https：//arxiv.org/pdf/2201.09047.pdf.

［16］Zhao Dong，Li Xiangyang，Ma Huadong.How to crowdsource tasks truthfully without sacrificing utility：online incentive mechanisms with budget constraint［C］//Proc of IEEE Conference on Computer Communications.Piscataway，NJ：IEEE Press，2014：1213-1221.

［17］Han Jingti，Wu Xiaohong，Liu Jianguo.An online sequential procurement mechanism under uncertain demands in multi-cloud environment［J］.International Journal of Approximate Reasoning，2018，103：152-167.

［18］Mohammed I，Tabatabai S，Al-Fuqaha A，et al.Budgeted online selection of candidate IoT clients to participate in federated learning［J］.IEEE Internet of Things Journal，2020，8（7）：5938-5952.

［19］Myerson R B.Optimal auction design［J］.Mathematics of Operations Research，1981，6（1）：58-73.

［20］Cohen G，Afshar S，Tapson J，et al.EMNIST：extending MNIST to handwritten letters［C］//Proc of International Joint Conference on Neural Networks.Piscataway，NJ：IEEE Press，2017：2921-2926.

［21］Krizhevsky A，Hinton G.Learning multiple layers of features from tiny images［M］//Handbook of Systemic Autoimmune Diseases.2009：158.

［22］Damaskinos G，Guerraoui R，Kermarrec A M，et al.Fleet：online fede-rated learning via staleness awareness and performance prediction［J］.ACM Trans on Intelligent Systems and Technology，2022，13（5）：1-30.