基于歷史梯度平均方差縮減的協同參數更新方法

謝 濤 張春炯 徐永健

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

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

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

1 引言

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

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

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

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

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

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

2 本文提出的DisSAGD方法

2.1 方差縮減

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

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

2.2 分布式實現

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

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

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

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

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

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

2.3 具有加速因子的學習率

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

2.4 自適應采樣

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

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

圖1 分布式機器學習拓撲

表2 DisSAGD算法的偽代碼

3 性能測試

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

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

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

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

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

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

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

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

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

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

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

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

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

3.1 模型性能

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

3.2 收斂效果

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

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

表3 模型的F1值

圖2 不同加速因子在獨立節點運行損失函數值的變化

3.3 加速效果

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

3.4 等待時間

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

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

圖4 DisSAGD算法中不同工作節點數量的加速效果

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

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

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

3.5 時間差異平衡

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

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

4 結束語

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