謝 濤 張春炯 徐永健

①(西南大學教育學部智慧教育研究院 重慶 400715)

②(同濟大學電子與信息工程學院 上海 201804)

③(西南大學計算機與信息科學學院 重慶 400715)

1 引言

機器學習被廣泛應用于圖像檢索、語義識別和文本信息處理，在智慧醫(yī)療、智慧城市和智慧教育等領域發(fā)揮著重要作用。許多機器學習算法的目標函數(shù)可以通過優(yōu)化問題來表示，并采用隨機梯度下降算法(Stochastic Gradient Descent, SGD)進行求解[1]。但是，局部梯度與全局平均梯度之間存在方差，會使機器學習算法中損失函數(shù)的收斂速度減慢。而且，SGD在目標函數(shù)強凸且步長遞減的情況下次線性收斂，導致模型訓練不穩(wěn)定。

近年來，分布式機器學習取得了重要進展。分布式集群的節(jié)點分為參數(shù)服務器和工作節(jié)點。工作節(jié)點從服務器中提取參數(shù)，梯度的計算由工作節(jié)點進行，更新后的參數(shù)將推送到服務器，并在服務器上聚合以更新全局參數(shù)，最后與工作節(jié)點共享[2]。其模型訓練主要分為同步和異步兩種方式。在同步方式中，所有工作節(jié)點都需要同步消息，并在服務器更新前進行匯總；而異步方式中，服務器在一次更新迭代輪次中接收到率先計算完成的工作節(jié)點的模型參數(shù)時，不再等待其他工作節(jié)點的消息就將其更新為全局模型參數(shù)，然后分發(fā)給每個工作節(jié)點進行下一輪次迭代更新。

基于傳統(tǒng)參數(shù)服務器和工作節(jié)點關系的SSP(Stale Synchronous Parallel)方法[3]在本地維護一個緩存參數(shù)池，每個工作節(jié)點可以直接從其中提取參數(shù)，并對參數(shù)服務器之間的同步進行額外處理，其缺點在于性能差的節(jié)點可能得不到及時發(fā)現(xiàn)。因此，使系統(tǒng)不被低性能節(jié)點影響的FSSP模型[4]和可動態(tài)決定節(jié)點失效閾值的DSSP模型[5]被提出。在這些模型中，節(jié)點間的通信要么采用自適應學習率來提高異步SGD的魯棒性[6,7]，要么基于參數(shù)服務器系統(tǒng)采用類似SSP的異步通信協(xié)議進行跨節(jié)點參數(shù)更新[8]。然而，由于學習率隨著迭代而衰減，導致算法的收斂速度減慢，容易出現(xiàn)過擬合。針對此，結合延遲近端梯度和隨機方差縮減梯度的快速分布式SGD[9]使用固定學習率來保證線性收斂，性能優(yōu)于傳統(tǒng)的SGD。

由于集群中分布式機器學習的參數(shù)快速增長、同步的成本高，大大減慢分布式學習的速度。充分因子廣播(SFB)計算模型被提出用于大規(guī)模矩陣參數(shù)化模型的分布式學習[10]。該方法通過在工作節(jié)點之間廣播SF并在每個本地節(jié)點重構和更新參數(shù)矩陣，可提高通信效率。此外，文獻[11]提出一種有效的小批量訓練機制，可以加速集群中的SGD；文獻[12]提出可提升訓練效率的誤差補償式隨機梯度下降算法，通過量化局部梯度來降低通信開銷，并加快收斂速度。但這些算法主要在分布式通信機制上采用隨機梯度下降算法，很少有研究兼顧考慮歷史梯度的方差。

事實上，近年關于方差縮減的研究并不少見，例如SAG[13], SAGA[14], S2GD, SVRG++和Prox-SVRG[8,9,15]等。這些研究主要對模型的結構進行適當?shù)臅r空折中，從而減少隨機梯度引起的方差，有助于獲得線性收斂速度。但大多數(shù)算法是在中心服務器上實現(xiàn)的，難以滿足大規(guī)模分布式應用的要求。隨著基于方差縮減的分布式SGD得到廣泛關注，Wang等人[16]提出有效融合異步并行機制和方差縮減方法的Async-ProxSCVR算法，F(xiàn)erranti等人[17]提出基于方差縮減的隨機交替最小化算法SVR-AMA，均可解決對于強凸和一般非凸情況下的快速收斂問題。然而，大量算法主要使用閉環(huán)方式為節(jié)點中的多個線程(而非多個獨立節(jié)點)并行更新參數(shù)。其缺點是當訓練數(shù)據(jù)或參數(shù)的數(shù)量很大、不能存儲在單個節(jié)點中時，模型收斂效率會受到嚴重影響。

鑒于此，本文的主要貢獻在于采用方差縮減SGD完成分布式集群中的大規(guī)模機器學習任務，主要集中解決兩個關鍵問題：(1)將數(shù)據(jù)分塊并分配給多個工作節(jié)點后的算法“快速收斂”問題；(2)在異步通信方式下，執(zhí)行全局參數(shù)分發(fā)時因快節(jié)點等待慢節(jié)點導致的“更新滯后”問題。因此，本文提出一種基于歷史梯度平均方差縮減的分布式SGD(DisSAGD)，利用歷史迭代的梯度方差，修正每次迭代的梯度估計，不需要完全的梯度計算或額外的存儲，而是通過異步通信協(xié)議來共享跨節(jié)點參數(shù)，并在分布式集群中使用方差縮減來訓練機器學習模型。

2 本文提出的DisSAGD方法

2.1 方差縮減

盡管此方法可以避免一些算法[14]存在的“無遍歷迭代算法”額外存儲的需求，但是需要在每次迭代時對整個數(shù)據(jù)集進行梯度估計，造成昂貴的計算代價。為了解決此問題并獲得加速計算，本文在每次迭代上累積平均梯度向量，然后使用該向量進行下次迭代的梯度求解，從而避免在整個數(shù)據(jù)集上迭代循環(huán)。這些累積的平均梯度向量在機器學習算法運行時不會產生其他明顯的開銷。在每次估計梯度時用歷史梯度來做修正，在一段時間內使用t×m個樣本，經過 t輪迭代后重新選擇 m個樣本進行梯度計算?；谄骄荻认蛄糠讲羁s減的參數(shù)更新規(guī)則如式(3)

表1 基于歷史梯度平均方差縮減算法

2.2 分布式實現(xiàn)

本研究中，機器學習集群是基于分布式tensorflow框架實現(xiàn)的，集群節(jié)點劃分為服務器(節(jié)點)和工作節(jié)點。工作節(jié)點從服務器中提取參數(shù)，梯度的基礎計算由工作節(jié)點進行。工作節(jié)點的任何更新將推送到服務器，并在服務器上聚合成全局參數(shù)。最后，這些新的全局參數(shù)將與工作節(jié)點共享?？紤]到方差縮減隨機梯度主要是通過數(shù)據(jù)驅動模型收斂，本文采用數(shù)據(jù)并行，而非模型并行。通過數(shù)據(jù)并行，數(shù)據(jù)集 D被劃分為互不相交的子集，將每一個子集指定到工作節(jié)點p, p ∈{1,2,···,P}。 令Dp為第p個數(shù)據(jù)劃分?？傻玫綌?shù)據(jù)并行的更新公式為

其中， t 表示迭代輪次，W 表示模型狀態(tài)，△ (·)表示更新函數(shù)，它獨立地運行在數(shù)據(jù)集 Dp上，最后將各工作節(jié)點的中間梯度結果通過F (·)進行匯總以更新全局梯度。值得注意的是，在數(shù)據(jù)并行方式中，假設數(shù)據(jù)集是獨立同分布的，且每一個工作節(jié)點的執(zhí)行能力都相等。工作節(jié)點將計算結果傳輸?shù)椒植际骄W(wǎng)絡之前，△ (·)先在本地CPU上運行，因此在配置相同的工作節(jié)點上，△ (·)在單個節(jié)點的計算延遲可以忽略。

另一方面，工作節(jié)點以異步方式執(zhí)行機器學習任務，通過gRPC消息傳遞從服務器中提取參數(shù) ω，并開始機器學習模型的迭代計算。在每次迭代中，工作節(jié)點首先從訓練數(shù)據(jù)中隨機選擇一個樣本，然后使用式(1)計算梯度。在迭代過程中，所有工作節(jié)點相互獨立。當?shù)瓿蓵r，工作節(jié)點將此輪迭代訓練好的機器學習模型參數(shù)ω 推送到服務器。

假設數(shù)據(jù)分布在p 個工作節(jié)點上，這些工作節(jié)點只能與對應的服務器通信，拓撲如圖1所示。將數(shù)據(jù)索引集 {1,2,···,n} 分 解為不相交的子集{ψs}，每個 ψs表 示存儲在服務器s 上的數(shù)據(jù)索引。目標函數(shù)由式(5)給出。

本文方差縮減方法容易實現(xiàn)以異步方式分發(fā)，因為它不涉及像SVRG那樣計算目標函數(shù)的完整梯度。此外，由于算法僅需要在每次迭代結束時更新梯度的平均值，因此可以增加服務器和工作節(jié)點之間的通信時段，從而保證機器學習模型快速且穩(wěn)定的收斂。

綜上所述，本文提出的DisSAGD算法偽代碼如表2所示。具體執(zhí)行過程如下：先啟動服務器創(chuàng)建分布式集群，再啟動主工作節(jié)點，協(xié)調其余工作節(jié)點的初始化和同步等待問題(第(1)行)。工作節(jié)點由gRPC傳遞模型參數(shù)。一旦工作節(jié)點從服務器接收到消息，它就會從服務器中提取全局參數(shù)，并開始迭代過程(第(2)行)。對于所有工作節(jié)點都會調用表1中的程序，實現(xiàn)本地參數(shù)更新(第(3)0～(5)行)。當工作節(jié)點從訓練數(shù)據(jù)中隨機采樣時，它使用緩存的本地梯度更新參數(shù)(第(6)～(9)行)，最后將新學習的參數(shù)推送至服務器，匯聚成新的全局參數(shù)(第(10)行)。DisSAGD算法有效地利用了歷史梯度縮減方差，與文獻[2,3]提到的Petuum SGD算法和文獻[6]提到的Downpour SGD算法不同的是：它可以快速收斂而不會在迭代期間衰減學習速率。

2.3 具有加速因子的學習率

方差縮減技術一般使用恒定的學習速率來加速機器學習算法。雖然恒定學習率對于L-平滑和γ-強凸目標函數(shù)表現(xiàn)良好[18]，但是還可以利用一些內在屬性來加速機器學習算法的收斂[19]。因此，本研究引入加速因子σ 指導DisSAGD的學習率變化，如式(6)所示。

2.4 自適應采樣

由于DisSAGD的工作節(jié)點每次迭代需要使用采樣策略進行模型訓練，因此確定每次迭代中隨機采樣多少樣本非常重要。在表1算法中，如果 m被設置為較大的值，就需要在迭代期間花費很多時間更新本地參數(shù)；相反，如果 m值較小，DisSAGD必須進行額外的迭代次數(shù)以降低損失函數(shù)。在集群中，盡管異步通信允許延遲，但是當超過允許的延遲范圍，同次迭代中訓練速度快的工作節(jié)點必須等待慢速的工作節(jié)點，即產生“更新滯后”問題，大大地增加了DisSAGD的收斂時間。

為了解決這一問題，本文在表2算法中采用一種自適應動態(tài)采樣策略，動態(tài)調整 m。當一個工作節(jié)點比其他工作節(jié)點更快時，它將為下一次迭代采樣更多樣本，這將使更快的工作節(jié)點有更多時間來計算局部梯度。因此，慢速的工作節(jié)點有機會趕上快速工作節(jié)點，并且等待時間顯著減少。每次迭代完成時，訓練的新本地參數(shù)將被推送到服務器，服務器將檢查所有工作節(jié)點是否獲取全局參數(shù)。如果工作節(jié)點訓練完成太快，則需要等待其他慢速工作節(jié)點?？焖俟ぷ鞴?jié)點將 m 調大為m +δ, δ是非負整數(shù)。為方便起見，令 δ =0.05m。這樣，訓練速度快的工作節(jié)點每次對更多的訓練樣本進行采樣，同時 等待慢工作節(jié)點。

圖1 分布式機器學習拓撲

表2 DisSAGD算法的偽代碼

3 性能測試

測試分為兩部分。首先，實驗對具有加速因子的學習率在獨立的工作節(jié)點上運行線性回歸任務。數(shù)據(jù)集采用由谷歌開源的街景門牌號碼SVHN[3]，它是做線性回歸任務的經典數(shù)據(jù)集。機器學習模型使用Alexnet[14]，每個網(wǎng)絡層使用Mish[15]作為激活函數(shù)。然后，實驗在集群環(huán)境中對另外兩個數(shù)據(jù)集分別使用異常檢測問題和分類問題來評估Dis-SAGD的性能。評估指標有收斂性、加速效果和平均等待時間。

異常檢測問題的損失函數(shù)模型如式(7)所示

其中， x 是訓練數(shù)據(jù)，y 是機器模型的輸出值，N 是訓練數(shù)據(jù)的大小。機器學習模型使用Resnet18[16]，激活函數(shù)也是Mish。數(shù)據(jù)集采用KDDcup99，它被認為是異常檢測問題的經典數(shù)據(jù)集，包含463, 715個樣本，每個樣本有41個維度。

分類問題的損失函數(shù)模型如式(8)所示

同樣， x 是訓練數(shù)據(jù)，y 是機器模型的輸出值，N是訓練數(shù)據(jù)的大小。機器學習模型使用Autoencoder[17]，激活函數(shù)使用Mish。數(shù)據(jù)集采用具有代表性的Cifar-100[9]。它由60000張大小為32×32的三通道彩色圖像組成，分為20個大類，每個大類包含5個小類，總共100個小類。每個小類包含600張圖像，其中500張用于訓練，100張用于測試。

本實驗在星環(huán)超融合大數(shù)據(jù)一體機集群上進行評估測試。該一體機共有32個計算節(jié)點，每個節(jié)點配備了兩個1536核CPU。m設定為1024，分布式實現(xiàn)使用第三方開源分布式機器學習系統(tǒng)tensorflow來進行性能評估。實驗采用異步通信，延遲設置為0.5 s，數(shù)據(jù)集分配在4個工作節(jié)點上。

本實驗使用以下算法進行了機器學習模型訓練性能的比較：

(1) Petuum SGD[2]：該方法是使用異步方式實現(xiàn)的分布式SGD，其學習率每次迭代結束時以固定因子0.95進行衰減，該代碼從http://petuum.github.io/下載；

(2) SSGD：該方法是SGD中最直接的分布式實現(xiàn)，其主設備簡單地在每次迭代中將負載分配給工作節(jié)點，確保工作節(jié)點使用相同的模型參數(shù)集執(zhí)行梯度計算，該代碼從https://github.com/codlife/Ssgd下載；

(3) DisSVRG[20]：改造了隨機方差縮減算法SVRG，使其從原來的串行單機版算法擴展至針對大規(guī)模數(shù)據(jù)集的分布式訓練算法；

(4) ASD-SVRG[21]：一種較新的分布式優(yōu)化算法，使用SVRG進行自適應采樣，基于歷史梯度局部Lipschitz常數(shù)進行估計；

(5) DisSAGD：本文提出的未采用具有加速因子學習率和未采用自適應采樣的算法；

(6) DisSAGD-tricks：本文提出的具有加速因子學習率和自適應采樣的算法。

3.1 模型性能

KDDcup99的性能評價指標為 F1, F1=2PR/(P +R), P 為準確率，R 為召回率。當 F1值越大，效果越理想。Cifar100和SVHN數(shù)據(jù)集分別使用top5的準確率作為評價指標。各模型性能比較結果如表3所示。可看出：本文提出的DisSAGD實驗結果比其他3種的模型性能更好，ASD-SVRG與本研究提出DisSAGD性能相當，而優(yōu)化的DisSAGDtricks比DisSAGD的模型效果更優(yōu)。這是由于本文考慮了歷史梯度的方差，使模型訓練較為穩(wěn)定不會出現(xiàn)像使用隨機樣本時的振蕩；而且，具有自我調節(jié)的學習率使得模型可以尋找到目標函數(shù)的鞍點，獲 得最優(yōu)的模型參數(shù)。

3.2 收斂效果

圖2顯示了具有加速因子的多個學習率在獨立工作節(jié)點上的測試結果。橫軸表示訓練時間，縱軸為損失函數(shù)。結果顯示：即使固定值部分很大，加速因子對算法的加速效果依然明顯。具有加速因子的學習速率使得基礎機器學習算法比沒有加速因子的恒定學習速率收斂得更快。當學習率固定值部分取值較小時，機器學習模型收斂效果更顯著，因此在本實驗中可以設置λ =10-3。

圖3顯示了在分布式集群中算法的收斂效果。DisSAGD-tricks在兩個數(shù)據(jù)集上的收斂性能均優(yōu)于其他算法。在KDDcup99上，該算法的損失值隨著時間的增加迅速下降，收斂的時間少于50 s；在Cifar100上具有類似表現(xiàn)。DisSAGD算法性能依賴于具體數(shù)據(jù)集，即在KDDcup99上不超過SSGD，而在Cifar100上則優(yōu)于SSGD，但總體上的收斂性能好于PetuumSGD。ASD-SVRG的性能明顯優(yōu)于PetuumSGD和SSGD，并和DisSAGD的性能十分接近(在特定的時間二者損失函數(shù)值相等，但隨著時間的增加ASD-SVRG的性能變得越來越好)；另一方面，ASD-SVRG的性能與本文提出的Dis-SAGD相當，但明顯次于優(yōu)化的DisSAGD(即本文的DisSAGD-tricks)算法。實驗結果表明：DisSAGD采用異步方式以及基于平均梯度向量方差縮減來更新參數(shù)，具有加速因子的學習速率加速了收斂，同時自適應采樣策略顯著減少了服務器分發(fā)全局參數(shù)的等待時間。

表3 模型的F1值

圖2 不同加速因子在獨立節(jié)點運行損失函數(shù)值的變化

3.3 加速效果

通過改變分布式集群中的工作節(jié)點數(shù)量，算法的加速效果如圖4所示。DisSAGD工作節(jié)點數(shù)量越多時其加速越近似線性。當使用32個工作節(jié)點時，DisSAGD在KDDcup99數(shù)據(jù)集上的加速相對于4個工作節(jié)點提高了19倍。在Cifar100數(shù)據(jù)集上使用32個工作節(jié)點時，DisSAGD可以保持接近線性的加速。這種效果主要歸功于異步通信方式和方差縮減技術。異步方式使得工作節(jié)點之間相互獨立，不存在滯后問題，從而減少了工作節(jié)點之間的等待時間。方差縮減技術減少了SGD的方差，并使DisSAGD以恒定速率收斂。

3.4 等待時間

圖5顯示了在獨立工作節(jié)點上自適應采樣的運行結果。在圖5(a)中，調整后的m值使目標函數(shù)得到快速收斂。由于等待時間與節(jié)點數(shù)量相關，算法運行在由5個節(jié)點組成的集群中，其結果如圖5(b)所示。通過改變m來評估平均等待時間。延遲設置為0.05 s。很明顯，自適應采樣策略減少了迭代期間的平均等待時間，這樣對時間折中處理使模型訓練更加精準。

圖3 不同算法之間收斂性能比較

圖4 DisSAGD算法中不同工作節(jié)點數(shù)量的加速效果

圖5 自適應采樣對收斂和等待時間影響

圖6 不同延遲時間對平均等待時間和平均計算時間的影響

圖6顯示通過改變延遲τ的值，本文所提出算法的平均時間消耗。由于小延遲意味著工作節(jié)點之間的聯(lián)系緊密，通常會導致快速工作節(jié)點因異步通信而等待。當延遲τ很小時，平均等待時間很長。例如，當延遲設置為0時，每次迭代中服務器需要將全局參數(shù)分發(fā)到所有工作節(jié)點，從而增加了等待時間。當延遲變大時，工作節(jié)點變得稀疏，等待時間急劇減少。因此，設定合理的通信延遲可以有效減少平均等待時間。盡管快速工作節(jié)點有更多的自由時間來進行迭代，但是慢速工作節(jié)點不能在大延遲內從服務器中獲得新的全局參數(shù)，無法從快工作節(jié)點中受益。因而延遲不應該設置太小或太大，它是工作節(jié)點等待時間和計算時間之間的折中。設置的延遲應該使DisSAGD的總時間消耗達到最小。本實驗中，KDDcup99數(shù)據(jù)集訓練時的延遲τ應設置為200，Cifar100數(shù)據(jù)集訓練時的延遲τ應設置為50。

3.5 時間差異平衡

為了研究設定多少個工作節(jié)點與服務器交互可以更好地平衡計算和等待時間的差異，本文將服務器收集到特定數(shù)量工作節(jié)點的模型參數(shù)開始進行全局參數(shù)的計算，然后在整個分布式集群中迭代，結果如圖7所示。當服務器對工作節(jié)點聚合數(shù)量為2～16 h，其平均等待時間隨著節(jié)點數(shù)量的增加逐漸減小、平均計算時間逐漸增大。對于3個數(shù)據(jù)集，其平均等待時間和平均計算時間在特定數(shù)量的工作節(jié)點上有交匯點?？傮w上，平均等待時間的下降幅度大于平均計算時間的上升幅度，說明通過指定工作節(jié)點數(shù)量的方式不如通過設置延遲時間獲得的增益大。工作節(jié)點在延遲時間內可以自適應采樣進行模型訓練，從而達到較好的效率和收斂性能。

圖7 平均等待時間和平均計算時間的平衡

4 結束語

針對將數(shù)據(jù)分配給多個工作節(jié)點后的算法收斂問題和在異步通信方式下執(zhí)行全局參數(shù)分發(fā)時存在的“更新滯后”問題，本文提出了DisSAGD算法。該算法結合方差縮減技術，不需要完整數(shù)據(jù)集的梯度計算或額外的存儲，并利用損失函數(shù)的凸平滑特性，使用具有加速因子的學習率進行優(yōu)化。本文在迭代期間采用自適應采樣策略，使慢速工作節(jié)點有機會在迭代期間趕上快速工作節(jié)點，從而減少了由滯后問題引起的等待時間。本文的局限在于：由于工作節(jié)點硬件限制，當單一節(jié)點上數(shù)據(jù)量過多時訓練會出現(xiàn)內存溢滿問題；某一節(jié)點上出現(xiàn)較少數(shù)據(jù)時，該節(jié)點模型不能快速收斂。