史加榮 王 丹 尚凡華 張鶴于

1.西安建筑科技大學(xué)理學(xué)院 西安 710055 2.省部共建西部綠色建筑國(guó)家重點(diǎn)實(shí)驗(yàn)室 西安 710055 3.西安電子科技大學(xué)人工智能學(xué)院智能感知與圖像理解教育部重點(diǎn)實(shí)驗(yàn)室 西安 710071 4.西安電子科技大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 西安 710071

作為人工智能目前最活躍的一個(gè)研究分支,機(jī)器學(xué)習(xí)根據(jù)經(jīng)驗(yàn)數(shù)據(jù)來(lái)設(shè)計(jì)、開(kāi)發(fā)算法,其目的是探索數(shù)據(jù)的生成模式,并用來(lái)發(fā)現(xiàn)模式和進(jìn)行預(yù)測(cè)[1-2].深度學(xué)習(xí)是一類更廣的機(jī)器學(xué)習(xí)方法,允許由多個(gè)處理層組成的計(jì)算模型來(lái)學(xué)習(xí)具有多個(gè)抽象級(jí)別的數(shù)據(jù)表示[3].伴隨著深度學(xué)習(xí)的崛起,機(jī)器學(xué)習(xí)重新受到了學(xué)術(shù)界和工業(yè)界的廣泛關(guān)注.機(jī)器學(xué)習(xí)技術(shù)已廣泛地應(yīng)用在計(jì)算機(jī)視覺(jué)、推薦系統(tǒng)、語(yǔ)音識(shí)別和數(shù)據(jù)挖掘等領(lǐng)域中.

回歸與分類等監(jiān)督學(xué)習(xí)是機(jī)器學(xué)習(xí)中最常見(jiàn)的一類學(xué)習(xí)問(wèn)題,它提供了包含輸入數(shù)據(jù)和目標(biāo)數(shù)據(jù)的訓(xùn)練數(shù)據(jù)集.為了探討輸入與目標(biāo)之間的關(guān)系,需要先建立含參數(shù)的表示模型,再通過(guò)最小化所有樣本的平均損失函數(shù)來(lái)獲得最優(yōu)的參數(shù),此處的優(yōu)化模型通常為經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化(Empirical risk minimization,ERM)[4].梯度下降法是求解ERM 模型最常用的方法,也是二階方法和黎曼優(yōu)化的重要基礎(chǔ).傳統(tǒng)的梯度下降法在計(jì)算目標(biāo)函數(shù)的梯度時(shí),需計(jì)算每個(gè)樣本對(duì)應(yīng)的梯度,總計(jì)算復(fù)雜度線性地依賴于樣本數(shù)目.隨著數(shù)據(jù)規(guī)模的日益增大,求解所有樣本的梯度需要相當(dāng)大的計(jì)算量,因而傳統(tǒng)的梯度下降算法在解決大規(guī)模機(jī)器學(xué)習(xí)問(wèn)題時(shí)往往不再奏效[5].

隨機(jī)梯度下降算法(Stochastic gradient descent,SGD)源于1951年Robbins 和Monro[6]提出的隨機(jī)逼近,最初應(yīng)用于模式識(shí)別[7]和神經(jīng)網(wǎng)絡(luò)[8].這種方法在迭代過(guò)程中隨機(jī)選擇一個(gè)或幾個(gè)樣本的梯度來(lái)替代總體梯度,從而大大降低了計(jì)算復(fù)雜度.1958年Rosenblatt 等研制出的感知機(jī)采用了隨機(jī)梯度下降法的思想,即每輪隨機(jī)選取一個(gè)誤分類樣本,求其對(duì)應(yīng)損失函數(shù)的梯度,再基于給定的步長(zhǎng)更新參數(shù)[9].1986年Rumelhart 等分析了多層神經(jīng)網(wǎng)絡(luò)的誤差反向傳播算法,該算法每次按順序或隨機(jī)選取一個(gè)樣本來(lái)更新參數(shù),它實(shí)際上是小批量梯度下降法的一個(gè)特例[9].近年來(lái),隨著深度學(xué)習(xí)的迅速興起,隨機(jī)梯度下降算法已成為求解大規(guī)模機(jī)器學(xué)習(xí)優(yōu)化問(wèn)題的一類主流且非常有效的方法.目前,隨機(jī)梯度下降算法除了求解邏輯回歸、嶺回歸、Lasso、支持向量機(jī)[10]和神經(jīng)網(wǎng)絡(luò)等傳統(tǒng)的監(jiān)督機(jī)器學(xué)習(xí)任務(wù)外,還成功地應(yīng)用于深度神經(jīng)網(wǎng)絡(luò)[11-12]、主成分分析[13-14]、奇異值分解[13,15]、典型相關(guān)分析[16]、矩陣分解與補(bǔ)全[17-18]、分組最小角回歸[19-20]、稀疏學(xué)習(xí)和編碼[21-22]、相位恢復(fù)[23]以及條件隨機(jī)場(chǎng)[24]等其他機(jī)器學(xué)習(xí)任務(wù).

隨著大數(shù)據(jù)的不斷普及和對(duì)優(yōu)化算法的深入研究,衍生出隨機(jī)梯度下降算法的許多不同版本.這些改進(jìn)算法在傳統(tǒng)的隨機(jī)梯度下降算法的基礎(chǔ)上引入了許多新思想,從多個(gè)方面不同程度地提升了算法性能.搜索方向的選取和步長(zhǎng)的確定是梯度下降算法研究的核心.按照搜索方向和步長(zhǎng)選取的方式不同,將隨機(jī)梯度下降算法的改進(jìn)策略大致分為動(dòng)量、方差縮減、增量梯度和自適應(yīng)學(xué)習(xí)率等四種類型.其中,前三類方法主要是校正梯度或搜索方向,適用于邏輯回歸、嶺回歸等凸優(yōu)化問(wèn)題;第四類方法針對(duì)參數(shù)變量的不同分量自適應(yīng)地設(shè)置步長(zhǎng),適用于深度神經(jīng)網(wǎng)絡(luò)等非凸優(yōu)化問(wèn)題.

在傳統(tǒng)梯度下降算法的基礎(chǔ)上添加動(dòng)量項(xiàng)可以有效避免振蕩,加速逼近最優(yōu)解.采用動(dòng)量更新策略的方法主要包括經(jīng)典動(dòng)量算法(Classical momentum,CM)[25]和Nesterov 加速梯度算法(Nesterov＇s accelerated gradient,NAG)[26-27].簡(jiǎn)單版本的隨機(jī)梯度下降算法在隨機(jī)取樣的過(guò)程中產(chǎn)生了方差并且隨著迭代次數(shù)的增加而不斷累加,無(wú)法保證達(dá)到線性收斂.為此,研究者們相繼提出了一系列基于方差縮減的隨機(jī)梯度下降算法,主要包括隨機(jī)方差縮減梯度算法(Stochastic variance reduced gradient,SVRG)[28]、近端隨機(jī)方差縮減梯度算法(Proximal stochastic variance reduction gradient,Prox-SVRG)[29]、Katyusha[30]和MiG[31]等.前述方法沒(méi)有充分利用歷史梯度信息,而增量梯度策略通過(guò)“以新梯度替代舊梯度”的方式,充分考慮了歷史梯度且達(dá)到了減少梯度計(jì)算量的目的,該類型的主要算法包括隨機(jī)平均梯度算法(Stochastic average gradient,SAG)[32]、SAGA[33]和Point-SAGA[34].Allen-Zhu[30]根據(jù)算法在強(qiáng)凸條件下的復(fù)雜度將前三類隨機(jī)梯度下降算法分為三代,復(fù)雜度隨代數(shù)的增加而降低.在深度神經(jīng)網(wǎng)絡(luò)中,自適應(yīng)學(xué)習(xí)率的隨機(jī)梯度下降法通過(guò)使用反向傳播所計(jì)算出的梯度來(lái)更新參數(shù)[35].與前三類算法不同,自適應(yīng)算法在訓(xùn)練過(guò)程中會(huì)根據(jù)歷史梯度信息,針對(duì)參數(shù)的不同分量自動(dòng)調(diào)整其對(duì)應(yīng)的學(xué)習(xí)率.這類算法主要包括Adagrad[36]、Adadelta[37]、Adam(Adaptive moment estimation)[38]和Nadam(Nesterov-accelerated adaptive moment estimation)[39]等.

目前,各種版本的隨機(jī)梯度下降算法大多以黑箱優(yōu)化器的形式在TensorFlow、PyTorch 和Mx-Net 等各大主流平臺(tái)供用戶調(diào)用,但背后的算法原理卻鮮為人知.2017年Ruder 在文獻(xiàn)[40]中介紹了幾種深度學(xué)習(xí)領(lǐng)域中的隨機(jī)梯度下降算法,但缺乏一些最新的研究成果、算法之間的聯(lián)系以及實(shí)際數(shù)據(jù)集上的實(shí)驗(yàn)對(duì)比.國(guó)內(nèi)學(xué)者提出過(guò)一些隨機(jī)梯度下降算法的改進(jìn)策略,但尚未有人發(fā)表過(guò)此方向的綜述性論文.因此,本文的工作對(duì)于關(guān)注梯度下降算法理論及其在深度學(xué)習(xí)中應(yīng)用的研究者具有參考意義.本文針對(duì)隨機(jī)梯度下降算法展開(kāi)研究,討論了動(dòng)量、方差縮減、增量梯度和自適應(yīng)學(xué)習(xí)率等四類更新策略下主要算法的核心思想、迭代公式以及算法之間的區(qū)別與聯(lián)系.對(duì)于邏輯回歸、嶺回歸、Lasso 和深度神經(jīng)網(wǎng)絡(luò)等機(jī)器學(xué)習(xí)任務(wù),設(shè)計(jì)了相應(yīng)的數(shù)值實(shí)驗(yàn),并對(duì)比了幾種具有代表性的隨機(jī)梯度下降算法的性能.文末對(duì)研究工作進(jìn)行了總結(jié),并展望了隨機(jī)梯度下降算法面臨的挑戰(zhàn)與未來(lái)的發(fā)展方向.

1 預(yù)備知識(shí)

本節(jié)先引入經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化模型,再簡(jiǎn)要介紹凸優(yōu)化的基本知識(shí),最后給出了3 類梯度下降算法.

1.1 經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化

1.2 凸優(yōu)化基礎(chǔ)知識(shí)[41]

1.3 梯度下降算法

圖1 條件數(shù)對(duì)收斂速度的影響Fig.1 Effect of conditional number on convergence speed

圖2 FGD 和SGD 的優(yōu)化軌跡示意圖Fig.2 Schematic diagram of optimization process of FGD and SGD

2 基于動(dòng)量的隨機(jī)梯度下降算法

SGD 所生成的梯度方向常與目標(biāo)函數(shù)的峽谷長(zhǎng)軸垂直,并沿其短軸來(lái)回振蕩,因此目標(biāo)參數(shù)在長(zhǎng)軸上緩慢移動(dòng),無(wú)法快速到達(dá)目標(biāo)函數(shù)的谷底.物理學(xué)中的“動(dòng)量”可以有效地避免峽谷中的振蕩,從而加快在長(zhǎng)軸上的位移.Qian[25]證明了結(jié)合動(dòng)量的梯度下降算法與保守力場(chǎng)中的牛頓粒子運(yùn)動(dòng)具有統(tǒng)一性,從而得出了在梯度下降算法基礎(chǔ)上添加動(dòng)量項(xiàng)可以提升優(yōu)化效率的結(jié)論.

2.1 隨機(jī)經(jīng)典動(dòng)量算法

2.2 Nesterov 加速梯度算法

圖3 SGD、CM 和NAG 的參數(shù)更新示意圖Fig.3 Schematic diagram of parameters update of SGD,CM and NAG

3 基于方差縮減的隨機(jī)梯度下降算法

在SGD 中,單個(gè)樣本的梯度是全體樣本平均梯度的無(wú)偏估計(jì),但梯度方差往往隨著迭代次數(shù)的增加而不斷累加,這使得SGD 無(wú)法保證能夠達(dá)到線性收斂[49].“方差縮減” 策略通過(guò)構(gòu)造特殊的梯度估計(jì)量,使得每輪梯度的方差有一個(gè)不斷縮減的上界,從而取得較快的收斂速度.

3.1 隨機(jī)方差縮減梯度算法

3.2 近端隨機(jī)方差縮減梯度算法

SVRG 能夠加快收斂速度,但只適用于光滑的目標(biāo)函數(shù).對(duì)于添加了非光滑正則項(xiàng)的目標(biāo)函數(shù),雖然可以通過(guò)計(jì)算次梯度來(lái)近似替代梯度,但收斂速度較慢,實(shí)際意義較小.隨機(jī)近端梯度下降算法(Stochastic proximal gradient descent,SPGD)通過(guò)計(jì)算投影算子間接地估計(jì)目標(biāo)參數(shù),從而巧妙地避開(kāi)了正則項(xiàng)不光滑的問(wèn)題[50-51].近端隨機(jī)方差縮減梯度算法(Prox-SVRG)將SVRG 與SPGD 相結(jié)合,為含非光滑正則項(xiàng)的目標(biāo)函數(shù)使用方差縮減技巧提供了解決方案[29].考慮模型(1)的正則化版本

3.3 Katyusha 算法

3.4 MiG 算法

表2 幾種方差縮減算法的動(dòng)量類型Table 2 Momentum types of several variance reduced algorithms

Shamir[13]將方差縮減技術(shù)應(yīng)用在主成分分析中,并提出了方差縮減主成分分析(Variance reduced principal component analysis,VR-PCA).Shang 等[53]通過(guò)調(diào)整SVRG 的關(guān)鍵點(diǎn)設(shè)置,提出了適用于大步長(zhǎng)的方差縮減隨機(jī)梯度下降算法(Variance reduced SGD,VR-SGD).此外,包含方差縮減思想的隨機(jī)梯度下降算法還有隨機(jī)對(duì)偶坐標(biāo)上升(Stochastic dual coordinate ascent,SDCA)[54]以及隨機(jī)原對(duì)偶坐標(biāo)(Stochastic primal-dual coordinate,SPDC)[55]等.

4 基于增量梯度的隨機(jī)梯度下降算法

“增量梯度” 策略源于增量聚合梯度算法(Incremental aggregated gradient,IAG)[56],該算法為每個(gè)樣本保留一個(gè)相應(yīng)的梯度值,在迭代過(guò)程中,依次抽取樣本并用新梯度替代舊梯度.

4.1 隨機(jī)平均梯度算法

4.2 SAGA

4.3 Point-SAGA

表3 SVRG 與增量算法參數(shù)更新公式對(duì)比Table 3 Comparison of parameters updating formulas among SVRG and incremental algorithms

對(duì)于前述幾種非自適應(yīng)學(xué)習(xí)率的隨機(jī)梯度下降算法,Allen-Zhu[30]根據(jù)各算法在強(qiáng)凸條件下的復(fù)雜度將其分為3 代.第1 代算法包括SGD 和NAG等;第2 代包括SVRG 和Prox-SVRG 等;第3 代包括Katyusha 和Point-SAGA 等.其中,第1 代算法的復(fù)雜度最高.在多數(shù)情形下,第3 代算法的復(fù)雜度優(yōu)于第2 代算法的復(fù)雜度,當(dāng)n ＜κ時(shí)優(yōu)勢(shì)尤其顯著.對(duì)于動(dòng)量、方差縮減和增量梯度策略下的隨機(jī)梯度下降算法,表4 比較了各算法取得ε-近似解的復(fù)雜度和收斂速度,其中,常數(shù)ρ ∈(0,1),T=t/n表示全局迭代次數(shù).

表4 隨機(jī)梯度下降算法的復(fù)雜度與收斂速度Table 4 Complexity and convergence speed of stochastic gradient descent algorithms

5 自適應(yīng)調(diào)節(jié)學(xué)習(xí)率的隨機(jī)梯度下降算法

在大規(guī)模機(jī)器學(xué)習(xí)中,為了減少振蕩、提高優(yōu)化效率,每經(jīng)過(guò)數(shù)輪迭代就需要更換一個(gè)較小的學(xué)習(xí)率.手動(dòng)調(diào)節(jié)學(xué)習(xí)率工作量較大且很難快速找到當(dāng)前模型環(huán)境下的最佳值.若設(shè)置的學(xué)習(xí)率過(guò)小,會(huì)使得優(yōu)化進(jìn)程緩慢;若學(xué)習(xí)率過(guò)大,會(huì)導(dǎo)致振蕩且難以逼近最優(yōu)解甚至逐漸遠(yuǎn)離最優(yōu)解,如圖4所示.為了解決此問(wèn)題,一些學(xué)者提出了以下幾種自適應(yīng)調(diào)節(jié)學(xué)習(xí)率的隨機(jī)梯度下降算法,這些算法在深度神經(jīng)網(wǎng)絡(luò)中表現(xiàn)出了極佳性能.

圖4 學(xué)習(xí)率對(duì)優(yōu)化過(guò)程的影響Fig.4 Effect of learning rates on optimization process

5.1 Adagrad

對(duì)于數(shù)據(jù)特征不平衡的問(wèn)題,若使用SGD,則稀疏特征對(duì)應(yīng)的梯度分量的絕對(duì)值很小甚至為零,這使得目標(biāo)參數(shù)難以逼近最優(yōu)解.Adagrad[35]是一種自適應(yīng)調(diào)節(jié)學(xué)習(xí)率的隨機(jī)梯度下降算法,它將目標(biāo)參數(shù)θ的分量進(jìn)行拆分,對(duì)每個(gè)分量使用不同的學(xué)習(xí)率進(jìn)行更新.對(duì)稀疏特征相應(yīng)的參數(shù)分量使用較大的學(xué)習(xí)率進(jìn)行更新,進(jìn)而識(shí)別出那些非常具有預(yù)測(cè)價(jià)值但易被忽略的特征.

Dean 等[60]發(fā)現(xiàn)Adagrad 能顯著提高SGD 的魯棒性,并將其用于谷歌的大型神經(jīng)網(wǎng)絡(luò)訓(xùn)練;Pennington等[61]在訓(xùn)練詞嵌入技術(shù)時(shí)使用了Adagrad,這是因?yàn)椴怀Ｓ玫脑~比常用的詞需要更大的更新.Chen 等[62]提出了SAdagrad,它將Adagrad 看作一個(gè)子程序并周期性調(diào)用,在強(qiáng)凸條件下具有更好的收斂速度.Adagrad 的提出使人們擺脫了手動(dòng)調(diào)節(jié)學(xué)習(xí)率的困擾,但仍存在以下缺點(diǎn):1)歷史梯度無(wú)節(jié)制地累加導(dǎo)致了學(xué)習(xí)率不斷衰減至一個(gè)極小的數(shù),這使得訓(xùn)練后期優(yōu)化效率很低;2)需要預(yù)先設(shè)置全局學(xué)習(xí)率;3)保留梯度的內(nèi)存成本過(guò)大.

圖5 Adagrad 的學(xué)習(xí)率變化示意圖Fig.5 Schematic diagram of learning rate changes for adagrad

5.2 Adadelta

5.3 Adam

5.4 AdaMax

5.5 Nadam

Nadam 將Nesterov 動(dòng)量加入到Adam 中,以提升Adam 的算法性能,亦可看作是Adam 和NAG的結(jié)合[39].從表1 可以看出:要將CM 轉(zhuǎn)化為NAG,需要添加中間變量.只要統(tǒng)一Adam 與CM 的更新形式,便可使用這種修改技巧實(shí)現(xiàn)從Adam 向Nadam 的轉(zhuǎn)換.

表1 CM 與NAG 的更新公式比較Table 1 Comparison of update formulas between CM and NAG

隨著深度學(xué)習(xí)網(wǎng)絡(luò)模型越來(lái)越復(fù)雜,自適應(yīng)算法面臨著泛化性能差、學(xué)習(xí)率逐漸極端化等問(wèn)題.在最近的幾個(gè)自然語(yǔ)言處理和計(jì)算機(jī)視覺(jué)項(xiàng)目中,自適應(yīng)算法僅在訓(xùn)練初期的優(yōu)化效率較高,而在訓(xùn)練后期和測(cè)試集上常常出現(xiàn)停滯不前的情況,且整體效果不及SGD 與NAG[67-68].Reddi 等[69]認(rèn)為可以通過(guò)對(duì)過(guò)去梯度的“長(zhǎng)期記憶” 來(lái)解決自適應(yīng)算法收斂性差的問(wèn)題,并提出Adam 的改進(jìn)算法AmSGDrad,此算法有效地提升了收斂速度.Luo 等[70]提出的自適應(yīng)算法Adabound 為學(xué)習(xí)率設(shè)置了一個(gè)動(dòng)態(tài)上界,且初始化學(xué)習(xí)率上界為無(wú)窮大,隨著迭代次數(shù)的增加,學(xué)習(xí)率最終平穩(wěn)地遞減至一個(gè)恒定的值.Adabound在訓(xùn)練初期的優(yōu)化速度與Adam 相當(dāng),在訓(xùn)練后期性能穩(wěn)定且泛化能力較強(qiáng),能夠在復(fù)雜的深層網(wǎng)絡(luò)中發(fā)揮良好的性能.

6 數(shù)值實(shí)驗(yàn)

先使用動(dòng)量、方差縮減和增量梯度3 種策略下的隨機(jī)梯度下降算法解決邏輯回歸等機(jī)器學(xué)習(xí)任務(wù),再將自適應(yīng)學(xué)習(xí)率的隨機(jī)梯度下降算法應(yīng)用到深度卷積神經(jīng)網(wǎng)絡(luò)中.

6.1 非自適應(yīng)學(xué)習(xí)率算法的性能對(duì)比

本節(jié)實(shí)驗(yàn)對(duì)非自適應(yīng)學(xué)習(xí)率的隨機(jī)梯度下降算法在機(jī)器學(xué)習(xí)模型中的性能進(jìn)行對(duì)比.采用MATLAB 與C 語(yǔ)言混合編程,涉及的算法程序均在4 核AMD A10-7300 Radeon R6 處理器上運(yùn)行.實(shí)驗(yàn)所用的Adult 等4 個(gè)數(shù)據(jù)集均來(lái)自于UCI 機(jī)器學(xué)習(xí)庫(kù)(http://archive.ics.uci.edu/ml/datasets.html).表5給出了這些數(shù)據(jù)集的詳細(xì)信息.

表5 數(shù)據(jù)集描述Table 5 Description of datasets

建立?2邏輯回歸(?2-Logistic regression)、嶺回歸(Ridge regression)和Lasso 等3 種經(jīng)典機(jī)器學(xué)習(xí)模型.表6 列出了3 種優(yōu)化模型的公式,其中‖·‖1為向量的?1范數(shù),λ1和λ2為取正值的正則化系數(shù).顯然,前兩種是光滑且強(qiáng)凸的優(yōu)化模型,第3種是非光滑凸的優(yōu)化模型.表7 列出了4 個(gè)實(shí)驗(yàn)數(shù)據(jù)集對(duì)應(yīng)的優(yōu)化模型及正則參數(shù)設(shè)置.選取SGD、NAG、SVRG、SAGA、Katyusha 以及MiG共6 種具有代表性的方法進(jìn)行實(shí)驗(yàn),通過(guò)研究6 種算法的迭代效率和時(shí)間效率,對(duì)比、分析算法的實(shí)際性能.為公平起見(jiàn),初始化目標(biāo)參數(shù)為零向量,每種方法的超參數(shù)和學(xué)習(xí)率均先按照理論最優(yōu)值進(jìn)行設(shè)置,再結(jié)合具體實(shí)驗(yàn)進(jìn)行微調(diào),以使算法的實(shí)際性能達(dá)到最佳.

表6 3 種機(jī)器學(xué)習(xí)任務(wù)的優(yōu)化模型Table 6 Optimization models for 3 machine learning tasks

表7 數(shù)據(jù)集對(duì)應(yīng)的優(yōu)化模型與正則參數(shù)Table 7 Optimization model and regularization parameter for each dataset

圖6 比較了6 種隨機(jī)梯度下降算法的迭代效率,其中,橫坐標(biāo)表示全局迭代次數(shù),縱坐標(biāo)表示當(dāng)前目標(biāo)函數(shù)值與最優(yōu)目標(biāo)函數(shù)值之差.從圖6 可以看出,第1 代隨機(jī)梯度下降算法SGD 和NAG 的迭代效率較低,難以在較少的迭代次數(shù)內(nèi)逼近最優(yōu)解,這可能是因?yàn)樘荻鹊姆讲畈粩嗬鄯e且實(shí)際數(shù)據(jù)集存在噪聲.作為簡(jiǎn)單版本的隨機(jī)梯度下降算法,SGD迭代效率最低;NAG 添加了Nesterov 動(dòng)量,盡管在一定程度上提升了SGD 的優(yōu)化效率,但效果并不顯著.第2 代隨機(jī)梯度下降算法的迭代效率在第1 代的基礎(chǔ)上產(chǎn)生了質(zhì)的飛躍.SVRG 和SAGA 分別通過(guò)采用方差縮減與增量梯度的策略構(gòu)造相應(yīng)的梯度估計(jì)量,有效限制了方差的累積,極大地提升了算法性能,且能夠在較少的迭代次數(shù)內(nèi)逼近最優(yōu)解.第3 代隨機(jī)梯度下降算法Katyusha 和MiG 在方差縮減技術(shù)的基礎(chǔ)上添加了消極動(dòng)量,因此在目標(biāo)參數(shù)的優(yōu)化過(guò)程中更加穩(wěn)健、精準(zhǔn)、高效,能夠在極少的迭代次數(shù)內(nèi)逼近最優(yōu)解.

圖7 對(duì)比了6 種隨機(jī)梯度下降算法的時(shí)間效率,其中:橫坐標(biāo)表示運(yùn)行時(shí)間,縱坐標(biāo)表示當(dāng)前目標(biāo)函數(shù)值與最優(yōu)目標(biāo)函數(shù)值之差.從圖7 可以看出:第2 代和第3 代隨機(jī)梯度下降算法的時(shí)間效率明顯強(qiáng)于第1 代,這與圖6 中迭代效率的對(duì)比情況相似.此外,第3 代算法的整體時(shí)間效率雖然稍強(qiáng)于第2代算法,但其優(yōu)勢(shì)并不像迭代效率那樣顯著.第3代算法雖然在復(fù)雜度和收斂速度上都有明顯優(yōu)勢(shì),但由于自身結(jié)構(gòu)相對(duì)復(fù)雜,故在實(shí)際應(yīng)用中單次迭代的計(jì)算量較大、運(yùn)行時(shí)間較長(zhǎng).

圖6 隨機(jī)梯度下降算法的迭代效率對(duì)比Fig.6 Comparison of iterative efficiency of stochastic gradient descent algorithms

圖7 隨機(jī)梯度下降算法的時(shí)間效率對(duì)比Fig.7 Comparison of time efficiency of stochastic gradient descent algorithms

6.2 自適應(yīng)學(xué)習(xí)率算法的性能對(duì)比

本節(jié)實(shí)驗(yàn)對(duì)自適應(yīng)學(xué)習(xí)率的隨機(jī)梯度下降算法在深度學(xué)習(xí)中的性能進(jìn)行對(duì)比.實(shí)驗(yàn)環(huán)境為MxNetgluon 1.0,工作站配置了10 核Intel Xeon E5-2640v4處理器和兩塊GTX 1080ti 11 GB 顯卡.使用的CIFAR-10 數(shù)據(jù)集(http://www.cs.toronto.edu/～kriz/cifar.html)包含60 000 幅32 × 32 × 3 的彩色圖像.根據(jù)圖像內(nèi)容可將其分為“飛機(jī)”、“鳥(niǎo)” 和“貓”等10 個(gè)類別,其中每個(gè)類別均包含6 000 幅圖像.從每類圖像中隨機(jī)選取5 000 幅作為訓(xùn)練樣本,剩余的1 000 幅作為測(cè)試樣本,并在實(shí)驗(yàn)過(guò)程中采取數(shù)據(jù)增廣策略.

在ResNet-18 卷積神經(jīng)網(wǎng)絡(luò)模型[71]下,對(duì)Adagrad、Rmsprop、Adadelta 以及Adam 的實(shí)際性能進(jìn)行比較.此外,實(shí)驗(yàn)還考慮了SGD 和CM 兩種非自適應(yīng)算法.ResNet-18 網(wǎng)絡(luò)模型的權(quán)重參數(shù)按均值為0、標(biāo)準(zhǔn)差為0.01 的正態(tài)分布隨機(jī)初始化.訓(xùn)練時(shí)采用交叉熵?fù)p失函數(shù),批容量為32,除Adadelta 外,其余算法全局學(xué)習(xí)率的初始值均為 10-3,且每隔30 代衰減至之前的1/10,共訓(xùn)練90 代.

圖8 展示了實(shí)驗(yàn)中訓(xùn)練集損失函數(shù)值、訓(xùn)練集精度以及測(cè)試集精度的變化情況.從此圖可以看出,4 種自適應(yīng)學(xué)習(xí)率的梯度下降算法在實(shí)驗(yàn)中的性能整體優(yōu)于SGD.Adagrad 的性能最差,僅略優(yōu)于SGD,這可能是因?yàn)锳dagrad 生成的自適應(yīng)學(xué)習(xí)率無(wú)節(jié)制減小,從而導(dǎo)致后期學(xué)習(xí)率微小,以至于無(wú)法突破局部最優(yōu)點(diǎn).Rmsprop 與Adadelta 的性能比較接近,且優(yōu)于Adagrad.Adam 在訓(xùn)練集與測(cè)試集中的優(yōu)化效率都是最高的,這說(shuō)明矩估計(jì)思想和自動(dòng)退火形式在隨機(jī)梯度下降算法中起到了提升算法性能的作用.此外,CM 在訓(xùn)練集中的表現(xiàn)與Rmsprop相當(dāng),在測(cè)試集中的性能甚至略優(yōu)于Rmsprop.

圖8 自適應(yīng)學(xué)習(xí)率的隨機(jī)梯度下降算法性能比較Fig.8 Performance comparison of stochastic gradient descent algorithms with adaptive learning rates

7 總結(jié)與展望

本文對(duì)近年來(lái)隨機(jī)梯度下降算法的研究進(jìn)展及主要研究成果進(jìn)行了綜述.根據(jù)算法的更新策略,將幾種具有代表性的隨機(jī)梯度下降算法分為四類,包括基于動(dòng)量的算法、基于方差縮減的算法、基于增量梯度的算法以及自適應(yīng)學(xué)習(xí)率的算法.本文介紹了這些算法的原理、核心思想以及相互之間的區(qū)別與聯(lián)系,并通過(guò)數(shù)值實(shí)驗(yàn)對(duì)算法的實(shí)際性能進(jìn)行了對(duì)比.實(shí)驗(yàn)結(jié)果表明:在邏輯回歸等經(jīng)典機(jī)器學(xué)習(xí)任務(wù)中,Katyusha 和MiG 等第3 代算法普遍具有較好的性能,而SGD 和NAG 等第1 代算法的實(shí)驗(yàn)性能最差;在深度卷積神經(jīng)網(wǎng)絡(luò)中,Adam 的實(shí)驗(yàn)性能最好.當(dāng)前,國(guó)內(nèi)外提出的隨機(jī)梯度下降算法種類繁多,但理論不完善且評(píng)價(jià)標(biāo)準(zhǔn)尚未統(tǒng)一.因此,隨機(jī)梯度下降算法仍將是未來(lái)的研究熱點(diǎn).

下面幾個(gè)方向在今后的研究中值得關(guān)注.

1)與二階算法相比,隨機(jī)梯度下降算法的收斂速度相對(duì)較慢,且需要更多的迭代次數(shù).第2 代和第3 代改進(jìn)算法雖然有效地提升了收斂速度,但耗費(fèi)了較大的時(shí)間成本和內(nèi)存成本.隨著數(shù)據(jù)規(guī)模的擴(kuò)大和模型復(fù)雜度的提升,單線程下的隨機(jī)梯度下降算法已經(jīng)不能滿足大規(guī)模機(jī)器學(xué)習(xí)應(yīng)用的需求[72-73].Zinkevich 等[74]提出了首個(gè)并行式隨機(jī)梯度下降算法SimuParallelSGD,這種方法適合于大規(guī)模學(xué)習(xí)范式和MapReduce 框架.文獻(xiàn)[75]提出了Hogwild ! 算法,它對(duì)稀疏數(shù)據(jù)采用無(wú)鎖異步更新策略,從而有效地減少了特征更新時(shí)的沖突.陳振宏等[76]提出了一種基于差異合并的分布式隨機(jī)梯度下降算法DA-DSGD,從性能的加權(quán)合并、模型規(guī)范化兩方面提高了算法性能.目前,研究者們已經(jīng)實(shí)現(xiàn)了SVRG、SAGA 和MiG 等改進(jìn)算法的分布式和并行化版本,但收斂速度卻有待進(jìn)一步提升[31,77-78].如何根據(jù)算法特點(diǎn)、數(shù)據(jù)對(duì)象和應(yīng)用平臺(tái),設(shè)計(jì)并實(shí)現(xiàn)不同改進(jìn)策略下的隨機(jī)梯度下降算法的分布式與并行化版本,使其在實(shí)際應(yīng)用中發(fā)揮出較高的性能水平,這是未來(lái)值得探索的問(wèn)題.

2)學(xué)習(xí)率是隨機(jī)梯度下降算法中一個(gè)非常重要的超參數(shù),直接影響算法在實(shí)際應(yīng)用中的性能.一些學(xué)者按照αt=c1/(tv+c2)的形式對(duì)每輪學(xué)習(xí)率進(jìn)行設(shè)置,但這種形式在實(shí)際應(yīng)用中收斂速度較慢,且c1,c2和v的取值仍難以確定[79].另一些學(xué)者則認(rèn)為應(yīng)先在固定步長(zhǎng)下快速尋找最優(yōu)解的鄰域,再考慮更為精確的優(yōu)化方案[80].目前,尋找最優(yōu)學(xué)習(xí)率在理論和實(shí)踐上仍是一個(gè)巨大的挑戰(zhàn).

3)隨機(jī)梯度下降算法在每輪迭代過(guò)程中計(jì)算復(fù)雜度較低,但只利用了一階梯度,忽略了目標(biāo)函數(shù)的二階信息及曲率,從而限制了實(shí)際性能和收斂速度[81].如何結(jié)合一階與二階方法各自的長(zhǎng)處，進(jìn)一步設(shè)計(jì)迭代效率俱佳的隨機(jī)梯度下降算法，是未來(lái)值得研究的問(wèn)題.

4)近年來(lái),研究者們將目光投向非凸的ERM模型,并且提出了一些行之有效的解決方案[82-85],其中具有代表性的策略包括添加動(dòng)量跳出局部最優(yōu)解[86]、使用方差縮技術(shù)減少梯度方差[87]和添加梯度噪聲逃離鞍點(diǎn)[88]等.然而,對(duì)于更為一般的非凸、非光滑的優(yōu)化問(wèn)題卻并未取得太大的突破,目前僅有Prox-SAGA[89]、Prox-SVRG+[90]等算法,但性能并不理想.隨機(jī)梯度下降算法在非凸、非光滑條件下的策略研究,不僅是當(dāng)前面臨的困局,也是未來(lái)最具有應(yīng)用價(jià)值的研究方向.

5)對(duì)于非凸的優(yōu)化問(wèn)題,梯度下降法通常存在兩個(gè)缺陷:易于陷入局部最優(yōu)、無(wú)法逃離鞍點(diǎn).而演化計(jì)算/智能計(jì)算無(wú)需計(jì)算梯度和確定步長(zhǎng),且往往具有較好的全局收斂性.如何將隨機(jī)梯度下降算法與演化計(jì)算/智能計(jì)算方法相結(jié)合,將是一個(gè)非常值得關(guān)注的研究方向.