線性編碼聯邦學習

作者簡介：史洪瑋（1985－），男，江蘇豐縣人，副教授，主要研究方向為智能系統；王志超（1974－），男，江蘇宿遷人，教授，主要研究方向為嵌入式與物聯網（zcwang@squ.edu.cn）；施連敏（1984－），男，浙江湖州人，博士研究生，主要研究方向為智能信息采集與高效處理；楊迎堯（1997－），男，江蘇南通人，碩士研究生，主要研究方向為物聯網與人工智能.

摘 要：聯邦學習能夠在邊緣設備的協作訓練中，保護邊緣設備的數據隱私。而在通用聯邦學習場景中，聯邦學習的參與者通常由異構邊緣設備構成，其中資源受限的設備會占用更長的時間，導致聯邦學習系統的訓練速度下降。現有方案或忽略掉隊者，或根據分布式思想將計算任務進行分發，但是分發過程中涉及到原始數據的傳遞，無法保證數據隱私。為了緩解中小型規模的多異構設備協作訓練場景下的掉隊者問題，提出了編碼聯邦學習方案，結合線性編碼的數學特性設計了高效調度算法，在確保數據隱私的同時，加速異構系統中聯邦學習系統速度。同時，在實際實驗平臺中完成的實驗結果表明，當異構設備之間性能差異較大時，編碼聯邦學習方案能將掉隊者訓練時間縮短92.85%。

關鍵詞：聯邦學習；線性編碼；邊緣計算；調度策略

中圖分類號：TP305 文獻標志碼：A 文章編號：1001－3695（2023）04－025－1113－06doi： 10.19734/j.issn.1001－3695.2022.08.0449

Abstract：Federated learning can protect the data privacy of edge devices in collaborative training of edge devices. In the general FL scenarios， the participants of FL are usually composed of heterogeneous edge devices， where resource-constrained devices will consume more time， resulting in the decline of the training speed. The existing schemes either ignore stragglers， or distribute the computing tasks according to the distributed idea， but the distribution process involves the transmission of raw data， which cannot guarantee data privacy. To alleviate the straggler problem in small or medium-sized multiple heterogeneous devices scenario， this paper proposed a coding-based FL scheme， and it designed an efficient scheduling algorithm combined with the mathematical characteristics of linear coding to ensure data privacy and accelerate the speed of heterogeneous FL system. Meanwhile， the experimental results completed in the actual experimental platform show that when the performance diffe-rence between heterogeneous devices is large， the coding-based FL scheme can shorten the training time of the straggler by 92.85%.

Key words：federated learning（FL）; linear coding; edge computing; scheduling algorithm

0 引言

聯邦學習（FL）吸引了大量學者進行研究，其包含一臺服務器和多個客戶端，同時各客戶端本地都存有可用來進行模型訓練的原始數據。在FL系統中，服務器可以調度客戶端來共同完成深度學習模型的訓練，并且服務器和客戶端、客戶端與客戶端之間不會共享各自的原始數據。與深度學習一樣，FL系統也需要經過對客戶端的多輪調度來提高模型精度［1～3］。

FL的提出，主要用來解決數據隱私和訓練性能（模型收斂速度、準確性）等問題。為了確保FL中各客戶端的數據隱私，各客戶端的本地數據均不會被通過網絡、物理等方式進行傳輸［4］。然而，實際系統中，客戶端組成通常異構，并且客戶端之間的性能差異較大，比如物聯網設備會比個人電腦、智能手機缺少數十倍的算力。這些算力、存儲資源受限的設備，即掉隊者，會限制FL系統訓練中的總體訓練速度和準確率，成為FL中的訓練瓶頸［5～7］。

掉隊者參與訓練所帶來的拖慢效果十分顯著，許多研究采用忽略掉隊者的方法來提高系統效率。而在中小型規模的聯邦學習訓練中，由于掉隊者參與FL的訓練可以增加訓練數據總量，并提高模型最終準確率，部分學習在研究中使用分布式計算（distributed machine learning，DML）來加速掉隊者訓練［8，9］。作為發展成熟的方案，DML能夠分發任務以提高系統速度，但是原始數據的交換使得其無法保護數據隱私。現有隱私保護下的任務分發多采用同態加密或差分隱私，均犧牲了系統性能來保護數據隱私［10～12］。一方面，同態加密計算開銷極高，對于算力資源較弱的掉隊者而言，這種計算開銷甚至會超出掉隊者性能上限［10］。另一方面，差分隱私方案通過對數據添加噪聲以擾動數據達到隱藏特征的效果。然而，差分隱私的保護能力與擾動程度密切相關，擾動程度較低時差分隱私無法確保隱私能夠完全保護，而擾動程度較高時甚至會掩蓋真實數據［11，12］。

為了解決上述問題，部分學者提出了編碼分布式計算（coded distributed computing，CDC）方案。CDC方案不僅能夠緩解掉隊者帶來的速度降低影響，而且以極少的額外資源消耗完成對DML中的數據隱私保護［13，14］。文獻［13］將線性編碼應用到FL系統中來訓練線性回歸模型，并且精心設計的線性編碼方案巧妙去除了解碼過程。此方案通過線性編碼的應用，完成了對模型訓練中原始數據（輸入和輸出）的隱私保護，并且由于線性編碼帶來的誤差可忽略不計。文獻［14］將文獻［13］應用到非線性回歸網絡中。而非線性回歸網絡編碼方案中，首先通過隨機傅里葉特征映射（random Fourier feature mapping，RFFM）內核來轉換待訓練數據，轉換后的數據可用于訓練具有正則化的線性回歸模型［15］。盡管上述兩種方案均可行，但是編碼過程帶來的誤差會影響模型精度。而且，上述方案不能應用到如卷積神經網絡（convolutional nerual networks，CNN）等通用深度學習模型中。因此，本文旨在研究一種可應用于FL的編碼計算方案，能夠在保護隱私的同時獲取高精度模型，并且此方案能夠適用于線性編碼、非線性編碼等通用深度學習模型中。

除去參與者數據隱私保護之外，單輪訓練中客戶端的調度數量也是FL中研究點之一。經典的FL系統中，調度全部客戶端進行訓練的策略會受到掉隊者影響，導致經典FL方案性能表現不佳。因此對于異構場景，則需要進一步考慮訓練過程中的客戶端調度比例［16～20］。文獻［19］在包含百萬數量級客戶端的大規模FL場景下，單輪訓練中選取50～5 000個客戶端參與訓練，并通過優化模型與客戶端數量比例來提高系統性能。除了客戶端選取比例之外，現有研究還提出了監控所有客戶端的運行速度，并減少調度掉隊者頻率的方案［20］。客戶端調度比例影響FL運行效率，當部分客戶端資源受限或無線信道質量較低時，FL訓練效率因此降低，合理的客戶端調度策略可以讓FL系統根據客戶端資源狀況主動約束和管理用戶以達到性能改進。經典FL中的全部調度策略不適用于本文異構場景，因此本文在考慮客戶端比例情況下，針對隱私保護下的FL性能提升進行研究。

本文提出了一種適用于異構計算環境下的線性編碼聯邦學習（linear coded-based federated learning）系統框架，能夠加速異構FL中的模型收斂速度以及提供一定級別的隱私保護。本文在LCFL框架內，對如圖1所示的CNN模型，將各輪訓練分割為多個訓練階段，如卷積計算階段、池化計算階段、全連接計算階段等，并在各訓練階段中單獨處理本階段的輸入和輸出。在深度學習的一輪訓練中，各訓練階段順序執行，LCFL方案會判斷當前訓練階段是否需要進行任務分發。對于計算復雜度較低的訓練階段，如使用ReLU（rectied linear unit）的激活階段，LCFL方案不會將簡單計算任務分發，以節省客戶端之間的通信時間。對于復雜計算任務，如卷積計算和全連接計算，LCFL能夠通過任務分發提高計算速度。本文的主要貢獻如下：

a）本文研究并設計了可適用于異構計算環境下的編碼聯邦學習系統框架。

b）在此FL系統框架內，提出了協作客戶端選擇算法，能夠在掉隊者的任務分發過程中確定待分發任務以及協作客戶端數量的具體值，以加快FL中的深度學習訓練過程。

c）本文設計并實現了實際實驗平臺，其中包含資源受限的客戶端，如樹莓派。實驗結果表明，LCFL方案可以顯著減少異構場景下的FL系統訓練時間。

以上步驟為異構計算環境下傳統FL的模型訓練過程。在前向傳播過程中，式（1）和（2）中的卷積運算和全連接運算具有高計算復雜度，同時這兩類函數在計算過程中需要占用大量存儲空間。因此，對于掉隊者而言，算力需求高昂的函數計算任務需要被分發。

1.2 編碼分布式CNN計算

前文指出，掉隊者中的復雜計算任務，即前向傳播和反向傳播中的卷積運算和全連接運算任務需要被分發。其中，卷積運算可以被無損轉換為矩陣相乘的形式。傳統卷積運算是將卷積核以滑動窗口的方式在輸入圖片矩陣上滑動，當前窗口對應元素相乘然后求和得到結果，當全部滑動計算完后則得出本次卷積結果。而單個窗口中的相乘后再求和同樣也是向量內積的計算方式，所以可以將每個窗口內的元素拉成向量，通過向量內積進行運算，多個窗口的向量堆疊后成為矩陣；每個卷積核也拉伸成為向量，多個卷積核的向量排在一起也成了矩陣，此時卷積運算轉換成了矩陣運算［21］。

3 實驗

本章將通過實驗驗證和評估LCFL，其中涉及的兩個評價指標為模型準確率和訓練完成時間。LCFL系統旨在加速異構邊緣設備群的整體模型訓練速度，設備的主體以嵌入式設備等邊緣設備為主。由于邊緣設備的算力較低，并存在電量告警、網絡不佳的風險，所以訓練時間在邊緣設備的模型訓練指標中尤為重要。而準確率是圖像識別中衡量模型優劣的重要標準之一，不同于模型訓練過程中的損失或誤差大小，準確率是從未被訓練過的測試集中獲取，能夠更直觀地驗證模型的當前效果。

3.1 實驗環境配置

為了滿足通用性，系統中的神經網絡采用CPU進行訓練和推理。異構實驗環境中的設備包括多臺配置不同的電腦、一臺樹莓派4B和一臺樹莓派3B+。實驗設置如下：

a）實驗場景1使用八臺電腦和一臺樹莓派訓練；

b）實驗配置2使用九臺電腦和一臺樹莓派訓練。

選用CNN對MNIST手寫數字集進行訓練。實驗過程中，服務器將從上述設備中選取十臺作為客戶端，各客戶端均擁有MNIST中6 000張手寫數字圖片。CNN具體組成如圖1所示。服務器各輪調度30%總客戶端數量的設備，即三個客戶端進行訓練。

3.2 數據規模與準確率驗證

首先使用異構環境下的多種設備對神經網絡進行訓練，測試各類型客戶端完成各自本地圖片的訓練所用時間。其中，兩款樹莓派所需的訓練時間分別為63.2 s和71.9 s，各類型電腦的訓練時間為6.4 s～9.95 s，樹莓派所需訓練時間為筆記本電腦、臺式機訓練時間的6～7倍，因此當前異構環境下樹莓派為掉隊者。

數據集規模是限制模型準確率的重要因素之一，而不少研究方案中選擇忽略掉隊者中存儲的數據，以加快FL系統整體速度。本節從掉隊者數據集占總數據量的比例出發來驗證中小型規模FL中掉隊者的不可忽略性。在此驗證實驗中，通過調度一臺樹莓派以及若干臺電腦設備，來控制掉隊者中數據集占比分別為50%、20%以及10%，同時參與訓練的各設備均擁有6 000張十分類數據集MNIST中覆蓋所有類別的圖片數據，實驗結果如圖3所示。

顯然，當掉隊者擁有數據量占比較高，如20%、50%時，忽略掉隊者會導致模型訓練速度和最終準確率急速下降。而由于所有設備均擁有所有類別的數據，所以當掉隊者中數據量占比僅為10%時，忽略掉隊者對模型帶來的負面影響較小，但是依舊帶來了約5.6%的速度下降效果。而當數據集規模擴大、分布方式改變時，忽略掉隊者的負面影響會更顯著。

3.3 LCFL性能評估

本節將在實驗配置1中將LCFL與其余兩種方案進行對比。此時，實驗配置中網絡下載速度為7 MBps，網絡上傳速度為6.9 MBps，掉隊者將在調度中選取兩個協作客戶端進行訓練。

兩種對比方案分別為經典FL以及基于年齡更新的FL。在調度策略方面，經典FL會通過不斷調度全部客戶端訓練來完成模型的擬合；基于年齡策略更新的FL則會通過調度部分客戶端的方式來完成各輪次訓練，同時會根據所提出的年齡算法保證掉隊者會以較低的頻率被服務器調度［20］，對比方案與LCFL的對比如圖4所示。實驗中LCFL和基于年齡更新的FL在達到300 s的訓練時間后模型擬合趨向平穩，同時經典FL由于被掉隊者拖慢，導致其在前60 s中未完成一次完整的訓練，因此圖4中僅展示了60～300 s訓練時間區間結果。從最終準確率和訓練速度觀察，顯然LCFL的訓練效率為三者最高，當訓練時間為300 s時，可將針對MNIST數據集的模型準確率提升到97.92%。而經典FL訓練受掉隊者影響，當訓練時間為280 s時，準確率僅為94.85%。同時，從經典FL的模型準確率曲線可以看出，經典FL所需的訓練時間為三者最久。而在80～120 s的訓練時間區間內，由于基于年齡更新的FL調度到了掉隊者，需要的訓練時間拉長，導致此方案在訓練時間達到300 s時，模型準確率僅為97.34%。由于LCFL中任務分發機制帶來的掉隊者速度提升，使得LCFL為三方案中效果最佳。當網絡速度優異時，LCFL方案比基于年齡更新的FL方案訓練速度快28.4%。

上個實驗設置中的網絡速度優異，LCFL也因此有較快的訓練速度。為了進一步驗證LCFL方案中各參數對其性能的影響，系統通過控制協作客戶端數量以及網絡速度的方式來評估LCFL，多種對比結果如圖5所示。在圖4的實驗基礎上，分別增加協作客戶端數量至3和4后，能夠明顯看出LCFL方案的效率得到大幅度提升，協作客戶端數量為4時的LCFL方案性能較協作客戶端數量為3時的性能能夠提升18%。而當協作客戶端數量限制為固定值2時，隨著數據傳輸速度的降低，LCFL在數據分發過程需要消耗更多的時間，導致LCFL的性能優勢逐漸下降。然而，盡管協作客戶端數量為2、數據傳輸速度僅為1 MBps時，LCFL方案依舊比基于年齡更新的FL方案快18.4%。

3.4 客戶端選擇算法評估

在上述已完成的實驗中，驗證了LCFL方案的整體性能。本節將在實驗配置2中，從各細節方面對LCFL方案中的客戶端選擇算法進行實驗。

根據客戶端選擇算法中的各參數變量以及實際實驗平臺中的開發流程，客戶端選擇算法中的總訓練時間由以下部分組成：傳輸時間、矩陣打包和解包時間、編碼時間、解碼時間以及網絡訓練和推理時間，其中矩陣打包和解包是數據傳輸的前提，通過矩陣打包的方式將數據矩陣轉換為字節流從而進行網絡流傳輸，解包則是將字節流轉換為原始矩陣的過程。

實驗結果如圖6所示。實驗中，掉隊者分別在搭載客戶端選擇算法和不使用算法的情況下，在不同協作客戶端數量下完成模型訓練。在協作客戶端數量相同時的各項對比中，客戶端選擇算法的搭載能夠節省7.82%的訓練時間，此時訓練時間的縮短主要體現在編碼時間以及解碼時間中。而隨著協作客戶端數量的增加，掉隊者的任務能夠同時被更多客戶端協作完成計算，因此掉隊者中的神經網絡訓練推理時間成倍降低。通過在五種不同數量協作客戶端下的平均訓練所需時間，相比于掉隊者直接進行本地訓練所需的71.9 s訓練時間，LCFL能夠平均降低其92.85%的訓練時間。同時，當協作客戶端數量為5時，LCFL方案的性能提升和客戶端資源需求達到最佳平衡狀態。

當協作客戶端數量相同時，客戶端選擇算法的擴展可以顯著縮短訓練時間。與未搭載客戶端選擇算法的方案相比，客戶端選擇算法通過減少需要分發的數據量降低了7.56%的總訓練時間。當數量為2時，客戶端選擇算法可以降低3.95%的時間。當協作客戶端數量上升時，網絡訓練和推理時間極速減少，客戶端選擇算法的效率提升比例更為明顯。從圖6的總體結果觀察，LCFL方案的訓練時間相比樹莓派單獨計算的訓練時間降低92.85%。

4 結束語

本文提出了一個高效的編碼聯邦學習框架，在加快異構環境下聯邦學習的模型收斂速度的同時，保護作為參與者的客戶端本地數據隱私。LCFL通過客戶端選擇算法，在各輪調度中選取合適的客戶端，并將速度最慢的客戶端中的計算任務分發給被選擇的客戶端。最后，大量的實驗從多角度對LCFL框架進行評估。實驗結果表明，當客戶端之間性能差異較大時，所提LCFL方案能夠將系統訓練時間減少92.85%。LCFL系統從異構場景出發，以嵌入式設備為對象進行了研究與實驗，對多邊緣設備的高效隱私協作計算作出了探索與貢獻。

參考文獻：

［1］Li Tian，Sahu A K，Talwalkar A，et al. Federated learning： challenges，methods，and future directions［J］. IEEE Signal Processing Magazine，2020，37（3）： 50－60.

［2］楊強. AI與數據隱私保護： 聯邦學習的破解之道［J］. 信息安全研究，2019，5（11）： 961－965. （Yang Qiang. AI and data privacy protection： a solution to federal learning［J］. Journal of Information Security Research，2019，5（11）： 961－965.）

［3］史鼎元，王晏晟，鄭鵬飛，等. 面向企業數據孤島的聯邦排序學習［J］. 軟件學報，2021，32（3）： 669－688. （Shi Dingyuan，Wang Yansheng，Zheng Pengfei，et al. Federated sorting learning for enterprise data island［J］. Journal of Software，2021，32（3）： 669－688.）

［4］譚作文，張連福. 機器學習隱私保護研究綜述［J］. 軟件學報，2020，31（7）： 2127－2156. （Tan Zuowen，Zhang Lianfu. A survey of privacy protection in machine learning［J］. Journal of Software，2020，31（7）： 2127－2156.）

［5］Li Tian，Sahu A K，Zaheer M，et al. Federated optimization in hetero-geneous networks ［EB/OL］. （2020－04－21）. https：//arxiv.org/abs/1812.06127.

［6］Caldas S，Koneny J，McMahan H B，et al. Expanding the reach of federated learning by reducing client resource requirements ［EB/OL］. （2019－01－08）. https：//arxiv.org/abs/1812.07210.

［7］趙羽，楊潔，劉淼，等. 面向視頻監控基于聯邦學習的智能邊緣計算技術［J］. 通信學報，2020，41（10）： 109－115. （Zhao Yu，Yang Jie，Liu Miao，et al. Intelligent edge computing technology based on federated learning for video surveillance［J］. Journal on Communications，2020，41（10）： 109－115.）

［8］Verbraeken J，Wolting M，Katzy J，et al. A survey on distributed machine learning［J］. ACM Computing Surveys，2020，53（2）： 1－33.

［9］Yang H，Lee J. Secure distributed computing with straggling servers using polynomial codes［J］. IEEE Trans on Information Forensics and Security，2018，14（1）： 141－150.

［10］楊亞濤，趙陽，張卷美，等. 同態密碼理論與應用進展［J］. 電子與信息學報，2021，43（2）： 475－487. （Yang Yatao，Zhao Yang，Zhang Juanmei，et al. Advances in homomorphic cryptography theory and applications［J］. Journal of Electronics amp; Information Technology，2021，43（2）： 475－487.）

［11］Geyer R C，Klein T，Nabi M. Differentially private federated learning： a client level perspective ［EB/OL］. （2018－03－01）. https：//arxiv.org/abs/1712.07557.

［12］Wu Youke，Huang Haiyang，Wu Ningyun，et al. An incentive-based protection and recovery strategy for secure big data in social networks［J］. Information Sciences，2020，508： 79－91.

［13］Dhakal S，Prakash S，Yona Y，et al. Coded federated learning［C］// Proc of IEEE Globecom Workshops. 2019： 1－6.

［14］Prakash S，Dhakal S，Akdeniz M，et al. Coded computing for federated learning at the edge ［EB/OL］. （2021－05－09）. https：//arxiv.org/abs/2007.03273.

［15］Rahimi A，Recht B. Random features for large-scale kernel machines［C］// Proc of the 21st Annual Conference on Neural Information Processing Systems. 2007： 1177－1184.

［16］Zhao Zhongyuan，Feng Chenyuan，Yang H H，et al. Federated-lear-ning-enabled intelligent fog radio access networks： fundamental theory，key techniques，and future trends［J］. IEEE Wireless Communications，2020，27（2）： 22－28.

［17］朱建明，張沁楠，高勝，等. 基于區塊鏈的隱私保護可信聯邦學習模型［J］. 計算機學報，2021，44（12）： 2464－2484. （Zhu Jianming，Zhang Qinnan，Gao Sheng，et al. Blockchain based trusted fede-ration learning model for privacy protection［J］. Chinese Journal of Computers，2021，44（12）： 2464－2484.）

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

［19］Kairouz P，Mcmahan H B，Avent B，et al. Advances and open problems in federated learning ［EB/OL］. （2021－03－09）. https：//arxiv.org/abs/1912.04977.

［20］Yang H H，Arafa A，Quek T Q S，et al. Age-based scheduling policy for federated learning in mobile edge networks ［C］// Proc of IEEE International Conference on Acoustics，Speech and Signal Processing. Piscataway，NJ： IEEE Press，2020： 8743－8747.

［21］Chellapilla K，Puri S，Simard P. High performance convolutional neural networks for document processing［C］// Proc of the 10th International Workshop on Frontiers in Handwriting Recognition. 2006.