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

顧永跟 馮洲洋 吳小紅 陶杰

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

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

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

文章編號(hào)：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 引言

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

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

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

在沒(méi)有報(bào)酬的情況下，移動(dòng)設(shè)備所有者往往

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

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

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

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

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

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

1 系統(tǒng)模型

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

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

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

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

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

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

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

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

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

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

3 實(shí)驗(yàn)分析

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

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

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

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

3.2 質(zhì)量評(píng)估

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)束語(yǔ)

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

目前質(zhì)量評(píng)估中的惡意客戶端篩選在訓(xùn)練后期識(shí)別準(zhǔn)確率較低，同時(shí)全局模型的聚合采用的是聯(lián)邦平均算法。未來(lái)將對(duì)篩選規(guī)則進(jìn)行改進(jìn)，使其在后期也能有較好的識(shí)別效果，而聚合算法的改進(jìn)也是一個(gè)后續(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é)報(bào)，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.