畢常遙 袁曉彤,2

1(南京信息工程大學(xué)自動(dòng)化學(xué)院 江蘇 南京 210044) 2(江蘇省大數(shù)據(jù)分析技術(shù)重點(diǎn)實(shí)驗(yàn)室 江蘇 南京 210044)

0 引 言

隨著社會(huì)的高速發(fā)展，各個(gè)領(lǐng)域?qū)τ谔幚砀黝悢?shù)據(jù)的要求日益上升，所要處理數(shù)據(jù)的規(guī)模也在不斷增長(zhǎng)。解決這一問(wèn)題，就需要進(jìn)行大規(guī)模的機(jī)器學(xué)習(xí)應(yīng)用。隨之而來(lái)的是模型復(fù)雜度的上升，具體體現(xiàn)在參數(shù)數(shù)量的激增。如何高效、快速地實(shí)現(xiàn)對(duì)大規(guī)模數(shù)據(jù)的分析計(jì)算是當(dāng)前研究的趨勢(shì)與挑戰(zhàn)。近年來(lái)，針對(duì)這一問(wèn)題涌現(xiàn)出了大量分布式計(jì)算的研究成果，其中既包括了各式各樣的優(yōu)化算法，也不乏分布式框架的搭建與優(yōu)化。

Lee等[1]在隨機(jī)梯度下降法的基礎(chǔ)上，引入了一個(gè)可以不斷減少上界的方差項(xiàng)，實(shí)現(xiàn)了具有線性收斂的分布式隨機(jī)方差消減梯度下降法。Zhao等[2]提出的可擴(kuò)展復(fù)合優(yōu)化的算法SCOPE是基于隨機(jī)方差消減梯度下降算法的變種。相比于分布式隨機(jī)方差消減梯度下降法，SCOPE在訓(xùn)練時(shí)僅使用本地?cái)?shù)據(jù)，并設(shè)計(jì)了特殊的參數(shù)更新方式。該算法在強(qiáng)凸的條件下效果優(yōu)于隨機(jī)方差消減梯度下降算法。此后，他們又在此基礎(chǔ)上引入了近端梯度下降法，提出了適用于分布式稀疏學(xué)習(xí)的Proximal SCOPE[3]。

Smith等[4]提出了一種分布式的對(duì)偶方法CoCoa。在該算法中，每臺(tái)機(jī)器將利用對(duì)偶性導(dǎo)出本地的子問(wèn)題進(jìn)行并行求解。該算法在SVM、線性/logistic回歸和lasso算法方面獲得了較好的效果。隨后，Ma等[5]針對(duì)CoCoa的局部?jī)?yōu)化環(huán)節(jié)重新進(jìn)行了設(shè)計(jì)，提出了CoCoa+。在CoCoa+框架下，每臺(tái)機(jī)器可以選擇不同的求解器來(lái)進(jìn)行局部?jī)?yōu)化，進(jìn)一步提高了優(yōu)化的速度。

針對(duì)分布式計(jì)算的通信環(huán)節(jié)的研究，Li等[6]提出并已應(yīng)用于深度學(xué)習(xí)框架MXNET的分布式學(xué)習(xí)框架Paramter Se-rver以及Zhu等[7]提出的一種基于稀疏參數(shù)平均和梯度量化來(lái)降低通信成本的優(yōu)化方法，該方法僅需要全通信隨機(jī)梯度下降法3%～5%的通信數(shù)據(jù)大小，就可以達(dá)到同等的收斂速度。

DANE方法是由Shamir等[8]提出的一種通信高效分布式近似牛頓算法，其既有傳統(tǒng)牛頓法相比于梯度下降法下降速度更快的優(yōu)勢(shì)，又規(guī)避了傳統(tǒng)牛頓法需要計(jì)算Hessian矩陣的逆導(dǎo)致計(jì)算復(fù)雜度高的缺點(diǎn)。該方法特別適用于大規(guī)模樣本分布式機(jī)器學(xué)習(xí)問(wèn)題，理論上可以證明其對(duì)于二次目標(biāo)函數(shù)具有隨局部樣本數(shù)增加而顯著提升的線性收斂速度，從而在局部樣本足夠多的情況下能夠保證該方法具有優(yōu)越的通信效率。

1 DANE的局部?jī)?yōu)化

1.1 DANE方法

DANE是一種分布式算法，該方法在每次迭代中會(huì)執(zhí)行兩次分布式的平均計(jì)算。

算法1DANE算法

1.參數(shù)：學(xué)習(xí)率η>0,正則化項(xiàng)μ>0

2.初始化：w(0)

3.fori=1,2,…,do

5.每臺(tái)機(jī)器i計(jì)算

7.end for

(1)

式中：φi(w)為目標(biāo)函數(shù)；▽?duì)読(w(t-1))為機(jī)器i上一輪迭代的局部梯度；▽?duì)?w(t-1))為此次迭代的全局梯度。為了解決這個(gè)局部?jī)?yōu)化問(wèn)題，首先，將每臺(tái)機(jī)器的局部正則化問(wèn)題定義為：

(2)

根據(jù)Bregman散度的定義，對(duì)于一個(gè)強(qiáng)凸函數(shù)有：

Dψ(w′;w)=ψ(w′)-ψ(w)-〈▽?duì)?w),w′-w〉

(3)

而上述局部正則化問(wèn)題的Bregman散度則為：

Di(w′;w)=Dhi(w′;w)=

(4)

此時(shí)，上述局部?jī)?yōu)化式(1)可以表示成：

(5)

式中：φ(w(t-1))+〈▽?duì)?w(t-1)),w-w(t-1)〉這兩項(xiàng)并不依賴于w，所以不會(huì)對(duì)優(yōu)化過(guò)程產(chǎn)生影響。因此，這兩項(xiàng)是關(guān)于w(t-1)的整體目標(biāo)的線性近似，不受當(dāng)前所使用機(jī)器的影響。每臺(tái)機(jī)器之間的差別在于它們用于定位線性近似值的位函數(shù)hi(w)不同。式(5)實(shí)質(zhì)上是一種利用位函數(shù)hi(w)和學(xué)習(xí)率η的鏡像式下降更新。

1.2 DANE-Adam方法

分布式算法的優(yōu)化方法有很多，本文選擇DANE方法的局部?jī)?yōu)化部分為切入點(diǎn)對(duì)原方法進(jìn)行優(yōu)化。

本文將優(yōu)化后的算法稱為DANE-Adam，其中Worker流程如下。

算法2DANE-Adam算法的Worker流程

1.參數(shù)：學(xué)習(xí)率η>0,正則化項(xiàng)μ>0，批量大小m,抽樣倍率n,外循環(huán)次數(shù)T,內(nèi)循環(huán)次數(shù)H

2.初始化：w(0)

3.fort=1,2,…,do

4.從主機(jī)接收全局梯度和全局參數(shù)

5.從本地?cái)?shù)據(jù)Pi中隨機(jī)抽取nm個(gè)樣本作為本次循環(huán)練樣本Di

6.forh=1,2,…,do

7.以Adam算法計(jì)算

8.end for

10.發(fā)送梯度和參數(shù)給主機(jī)

11.end for

全局梯度▽?duì)?w(t-1))和全局參數(shù)w(t-1)的作用是改變每次外循環(huán)的局部問(wèn)題，并對(duì)當(dāng)前機(jī)器計(jì)算的梯度起到糾正作用。每隔H次內(nèi)循環(huán)更新▽?duì)?w(t-1))和w(t-1)減少了通信成本，若每次內(nèi)循環(huán)都對(duì)▽?duì)?w(t-1))和w(t-1)進(jìn)行更新，通信成本將大幅增加，會(huì)極大地影響訓(xùn)練的時(shí)間。

通過(guò)對(duì)比，可以看到DANE-Adam和原方法主要有兩點(diǎn)不同。

(1) 在DANE方法中，每臺(tái)機(jī)器在求解局部子優(yōu)化問(wèn)題時(shí)所用的優(yōu)化算法是隨機(jī)梯度下降法，該方法相比Adagrad、Adadelta、RMSprop、Adam[9]等一些自適應(yīng)方法的收斂速度存在差距，因此本文選擇了Adam算法對(duì)其進(jìn)行替代以提高收斂速度。

(2) 在每輪外循環(huán)中加入了隨機(jī)抽樣步驟。這樣做的目的首先是在抽樣后，每次迭代都是通過(guò)一個(gè)子問(wèn)題來(lái)模擬整個(gè)大問(wèn)題，這樣可以減少每次內(nèi)循環(huán)的計(jì)算成本，相應(yīng)地，整個(gè)外循環(huán)迭代一次的計(jì)算成本以及所耗費(fèi)的時(shí)間也減少了；其次，也能夠以此對(duì)多機(jī)計(jì)算環(huán)境進(jìn)行模擬。

1.3 收斂性

當(dāng)μ=0時(shí)，每臺(tái)機(jī)器的局部問(wèn)題相同，即hi(w)=φi(w)=φ(w)。將Bregman散度的定義代入式(5)，可以得出：

當(dāng)每臺(tái)機(jī)器上的樣本數(shù)→∞時(shí)，可以認(rèn)為對(duì)于每臺(tái)機(jī)器i都有φi(w)=φ(w)。此時(shí)，將不需要進(jìn)行分布式優(yōu)化，式(5)近似于一個(gè)理想的牛頓迭代的形式，僅需要較少次數(shù)的迭代就可以接近最優(yōu)。

當(dāng)φi(w)和φ(w)均為二次時(shí)，則有：

(6)

式(5)將可以這樣的近似形式求解：

μI)-1▽?duì)?w(t-1))

(7)

(8)

與實(shí)際的牛頓法式(9)的更新形式進(jìn)行比較，得到：

特殊車牌背后是特權(quán)車，特權(quán)車背后是特權(quán)人，特權(quán)人腦子里是特權(quán)思想。解決特權(quán)車問(wèn)題，既要停止使用遼A09號(hào)牌，清除附著其上的公車屬性，更要清除那種能讓“公交車用號(hào)碼變成公務(wù)車用號(hào)碼”的需求和力量。不清除這種需求，取消了“O”，他可以替換為“09”；不約束這種力量，取消了“09”，他還可以用“08”……

(9)

這里使用了Hessian矩陣加上一個(gè)正則項(xiàng)的逆的平均值來(lái)近似Hessian矩陣平均值的逆,這規(guī)避了在進(jìn)行機(jī)器間數(shù)據(jù)交流時(shí)需要傳輸Hessian矩陣的問(wèn)題。對(duì)于這樣的二次目標(biāo)，只要進(jìn)行一次牛頓更新，就可以收斂到最優(yōu)。

1.4 Adam方法

Adam算法是Kingma等[9]提出的一種自適應(yīng)梯度優(yōu)化算法，它能夠?qū)γ總€(gè)不同的參數(shù)設(shè)置不同的學(xué)習(xí)率。Adam算法的更新方式如算法3所示。

算法3Adam算法流程

1.參數(shù)：α，β1，β2

2.初始化：θ0,m0→0,v0→0,t→0

3.whileθt未收斂do

t←t+1

gt←▽?duì)萬(wàn)t(θt-1)

4.end while

其中：gt為隨機(jī)目標(biāo)函數(shù)的梯度;mt為偏一階矩估計(jì)；vt為偏二階矩估計(jì)；β1和β2為矩估計(jì)的指數(shù)衰減率；θt為待更新參數(shù)；α為學(xué)習(xí)率；ε是為了維持?jǐn)?shù)值穩(wěn)定性而添加的一個(gè)較小常數(shù)，通常設(shè)為10-8。

相較于隨機(jī)梯度下降法，Adam算法的優(yōu)勢(shì)在于，其通過(guò)對(duì)梯度的一階矩估計(jì)和二階矩估計(jì)的計(jì)算，為不同的參數(shù)設(shè)置獨(dú)立的自適應(yīng)性學(xué)習(xí)率，使得該算法收斂速度更快。同時(shí)，Adam算法梯度的對(duì)角縮放具有不變性，適用于解決含大規(guī)模數(shù)據(jù)和參數(shù)的優(yōu)化問(wèn)題。

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

2.1 數(shù)據(jù)集

本文使用的數(shù)據(jù)集為MNIST、Fashion-MNIST和Cifar10。MNIST是一個(gè)手寫(xiě)數(shù)字?jǐn)?shù)據(jù)集，包含了60 000幅訓(xùn)練圖像和10 000幅測(cè)試圖像。Fashion-MNIST是一個(gè)類似MNIST的時(shí)尚產(chǎn)品數(shù)據(jù)集，其中的每幅圖片都以灰度顯示。共有10類，同樣包含了60 000幅訓(xùn)練圖像和10 000幅測(cè)試圖像。Cifar-10則是一個(gè)包含10類的彩色圖像數(shù)據(jù)集，包含了50 000幅訓(xùn)練圖像和10 000幅測(cè)試圖像。

2.2 參數(shù)設(shè)置

實(shí)驗(yàn)所使用的網(wǎng)絡(luò)為L(zhǎng)eNet，原算法的學(xué)習(xí)率設(shè)置α為0.01，本文的DANE-Adam取值0.001，Adam算法的一階矩估計(jì)的指數(shù)衰減率β1設(shè)為0.9，二階矩估計(jì)的指數(shù)衰減率β2設(shè)為0.999。MNIST與Fashion-MNIST實(shí)驗(yàn)設(shè)置的批量大小為100，Cifar10的批量大小為64。MNIST實(shí)驗(yàn)設(shè)置的內(nèi)循環(huán)數(shù)為2，F(xiàn)ashion-MNIST取5，Cifar-10取16。抽樣的倍率n分別為100、200和300。實(shí)驗(yàn)的目的是對(duì)DANE-Adam和DANE方法的求解局部問(wèn)題的能力進(jìn)行對(duì)比，所以實(shí)驗(yàn)中只使用一臺(tái)機(jī)器。

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

圖1給出了DANE與DANE-Adam在三組數(shù)據(jù)下的性能對(duì)比。表1給出了DANE和DANE-Adam的測(cè)試準(zhǔn)確率。

(a) MNIST

(c) Cifar10圖1 DANE與DANE-Adam的性能對(duì)比

從實(shí)驗(yàn)結(jié)果分析得到：

(1) 在訓(xùn)練最初期，n=100這組實(shí)驗(yàn)的收斂速度是最快的。這得益于n=100時(shí)每次內(nèi)循環(huán)訓(xùn)練樣本數(shù)量最少，在相同時(shí)間內(nèi)，迭代次數(shù)更多。但達(dá)到一定的精度時(shí)，n=100的收斂速度就會(huì)被n=200和n=300這2組超過(guò)。n=100的測(cè)試準(zhǔn)確率在4組實(shí)驗(yàn)中是最低的，特別與DANE方法的結(jié)果相比存在明顯差距。

(2) 當(dāng)n=200或n=300時(shí)，DANE-Adam在收斂速度上明顯優(yōu)于DANE方法，同時(shí)，在精度上能夠幾乎保持不變。

(3) 在n=200接近收斂前，其收斂速度比n=300更快；接近收斂后，則被n=300超過(guò)。從表1可以看到，兩者最終的測(cè)試準(zhǔn)確率相近，n=300時(shí)要略高出一點(diǎn)。

(4) DANE-Adam幾組實(shí)驗(yàn)的曲線相比DANE方法有較為明顯的波動(dòng)。這主要是由于取樣的隨機(jī)性導(dǎo)致每次取樣的分布存在差異，因此對(duì)一組樣本訓(xùn)練到最優(yōu)時(shí)，對(duì)另一組樣而言是輕微的過(guò)擬合。

2.4 低泛化性能分析

導(dǎo)致n=100時(shí)泛化性能較低的主要原因可能有以下兩點(diǎn)：

(1) 每次局部樣本數(shù)量過(guò)小，導(dǎo)致無(wú)法找到準(zhǔn)確的下降方向。

(2) Adam算法的學(xué)習(xí)率會(huì)出反復(fù)震蕩的情況，在通常情況下，泛化能力不如隨機(jī)梯度下降法加上動(dòng)量[9]。

從表1可以看到，n=100、n=200，以及n=300時(shí)的測(cè)試準(zhǔn)確率均存在比較明顯的差距?？梢耘袛?，局部樣本數(shù)量過(guò)小確實(shí)會(huì)導(dǎo)致泛化性能的下降。

為了驗(yàn)證Adam算法是否對(duì)泛化性能產(chǎn)生了影響，可以在對(duì)原DANE方法在保留隨機(jī)梯度下降法的前提下，同樣加入隨機(jī)抽樣步驟進(jìn)行實(shí)驗(yàn)。實(shí)驗(yàn)設(shè)置的學(xué)習(xí)率、批量大小和各數(shù)據(jù)集訓(xùn)練的內(nèi)循環(huán)數(shù)均與上文中DANE實(shí)驗(yàn)的設(shè)置保持一致，n設(shè)為100。性能對(duì)比和準(zhǔn)確率見(jiàn)圖2和表2所示。

(c) Cifar10圖2 n=100時(shí)，DANE與DANE-Adam的性能對(duì)比

從MNIST的實(shí)驗(yàn)結(jié)果來(lái)看，使用Adam算法非但沒(méi)有造成測(cè)試準(zhǔn)確率的下降，反而有所上升。這要?dú)w功于Adam算法對(duì)不同的參數(shù)設(shè)置的自適應(yīng)性學(xué)習(xí)率，使得在訓(xùn)練集較小的情況下，相比于隨機(jī)梯度下降法能更準(zhǔn)確地找到梯度下降的方向。

而從Fashion-MNIST的實(shí)驗(yàn)結(jié)果來(lái)看，使用Adam算法對(duì)測(cè)試準(zhǔn)確率雖然有所下降，但幅度較小，可以認(rèn)為使用Adam算法沒(méi)有對(duì)泛化性能產(chǎn)生明顯影響。

Cifar10的實(shí)驗(yàn)結(jié)果則是DANE方法的精度明顯更高。這可能是由于LeNet網(wǎng)絡(luò)用于訓(xùn)練Cifar10略顯不足，在網(wǎng)絡(luò)參數(shù)不足的情況下，具有更強(qiáng)泛化性能的隨機(jī)梯度下降法的優(yōu)勢(shì)被凸顯了出來(lái)。

3 結(jié) 語(yǔ)

本文提出了一種基于DANE算法框架的通信高效分布式深度神經(jīng)網(wǎng)絡(luò)訓(xùn)練方法。其核心思想是針對(duì)DANE方法的計(jì)算開(kāi)銷大都集中在局部單機(jī)優(yōu)化這一特點(diǎn)，采用深度學(xué)習(xí)中廣泛使用的Adam算法替換常用的隨機(jī)梯度下降法并引入隨機(jī)抽樣環(huán)節(jié)以更加高效地實(shí)現(xiàn)單機(jī)局部子問(wèn)題優(yōu)化訓(xùn)練。實(shí)驗(yàn)結(jié)果表明，本文所提出的方法在泛化精度幾乎保持不變的情況下，其計(jì)算性能可以得到顯著提升。

本研究尚存一些需要完善之處，包括：(1) 目前還缺少在使用深層次網(wǎng)絡(luò)情況下進(jìn)行的實(shí)驗(yàn)。例如在n=100的條件下，如果使用ResNet網(wǎng)絡(luò)對(duì)Cifar10數(shù)據(jù)集進(jìn)行訓(xùn)練是否會(huì)呈現(xiàn)出同樣的結(jié)果很值得研究。(2) 在目前大數(shù)據(jù)的環(huán)境下通常要面對(duì)更大規(guī)模、更高維度的數(shù)據(jù)。當(dāng)面對(duì)這些更復(fù)雜的數(shù)據(jù)時(shí)，抽樣的大小會(huì)對(duì)訓(xùn)練的過(guò)程以及結(jié)果產(chǎn)生怎樣的影響也是我們后續(xù)的研究工作之一。