基于AdaGrad自適應(yīng)策略的對(duì)偶平均方法*

張 旭 韋洪旭

（中國(guó)人民解放軍陸軍炮兵防空兵學(xué)院信息工程系 合肥 230031）

1 引言

無(wú)論是深度學(xué)習(xí)還是機(jī)器學(xué)習(xí)中其他方法，針對(duì)分類或是回歸問題首先都要建立模型隨后進(jìn)行優(yōu)化求解，求解深度學(xué)習(xí)網(wǎng)絡(luò)模型參數(shù)可以看作是一個(gè)無(wú)約束的優(yōu)化問題，形式如下：

其中f(x)稱為目標(biāo)函數(shù)或能量函數(shù)，且f(x)為凸函數(shù)。

梯度下降法是作為求解上述優(yōu)化問題的最經(jīng)典一階梯度迭代優(yōu)化方法，每一步都沿著當(dāng)前梯度方向即損失減小最快的方向迭代，從而不斷降低目標(biāo)函數(shù)的函數(shù)值，但是傳統(tǒng)梯度下降法在每一步迭代求損失函數(shù)的梯度時(shí)都需要使用整個(gè)樣本集，得到較高的準(zhǔn)確性的同時(shí)也伴隨著巨大的計(jì)算開支。因而傳統(tǒng)的梯度下降法不適用于大規(guī)模的機(jī)器學(xué)習(xí)問題。這時(shí)，人們往往使用隨機(jī)梯度下降方法（SGD）[1]來代替?zhèn)鹘y(tǒng)的梯度下降法。SGD利用大規(guī)模的機(jī)器學(xué)習(xí)問題數(shù)據(jù)滿足獨(dú)立同分布假設(shè)的特點(diǎn)，在每次迭代中隨機(jī)抽取1個(gè)或者部分樣本求梯度，以抽取樣本的梯度作為整個(gè)數(shù)據(jù)集梯度的無(wú)偏估計(jì)，大大降低了計(jì)算的復(fù)雜度[2]。但是，SGD在每次迭代中只使用當(dāng)前梯度信息，且由于樣本的隨機(jī)性，收斂過程中存在明顯的震蕩。2009年，Nesterov在文獻(xiàn)[3]中指出SGD的固有缺陷，即收斂過程中新的梯度信息獲得不斷衰減的步長(zhǎng)致使后期收斂緩慢的問題，由此提出了對(duì)偶平均方法（DA）。DA克服梯度下降法由于引入衰減步長(zhǎng)而導(dǎo)致的固有弊端，具有步長(zhǎng)策略靈活的特點(diǎn)，同時(shí)，由于每次迭代都利用過往梯度的信息，目標(biāo)函數(shù)值在迭代過程中不會(huì)出現(xiàn)劇烈震蕩，算法具有較好的收斂穩(wěn)定性[4]。此后，學(xué)者們開始對(duì)DA方法展開研究。Xiao在文獻(xiàn)[5]中還將DA推廣到解決正則化學(xué)習(xí)問題中去，特別在L1正則化項(xiàng)的情況下，DA較SGD能夠更好地保證問題解的稀疏性。Chen等[6]提出最優(yōu)正則化對(duì)偶平均方法（Optimal RDA，ORDA），在DA每步迭代中添加一步子優(yōu)化問題求解，對(duì)一般凸、強(qiáng)凸及光滑問題，均得到O(1/)的最優(yōu)個(gè)體收斂速率。Nesterov等[7]在DA的基礎(chǔ)上添加線性插值策略，也得到一般凸問題O(1/)的最優(yōu)個(gè)體收斂速率。曲軍誼等[4]進(jìn)一步證明了對(duì)偶平均方法具有與梯度下降法相同的最優(yōu)個(gè)體收斂速率O(lnt/)。可見，無(wú)論在算法收斂穩(wěn)定性還是收斂速率上，DA方法都具有良好表現(xiàn)，而對(duì)其的改進(jìn)仍留有空間。

在深度學(xué)習(xí)中由于優(yōu)化問題維度較高，任何單一的人為指定步長(zhǎng)都不可能同時(shí)滿足各個(gè)維度的不同要求，因此各個(gè)維度需要指定各不相同的步長(zhǎng)，因此必須進(jìn)行昂貴的超參數(shù)搜索[8]，由此對(duì)深度學(xué)習(xí)自適應(yīng)方法的研究成為當(dāng)前的主流方向之一，形成了 AdaGrad[9]、Adadelta[10]、RMSProp[11]、Adam[12]等一系列自適應(yīng)優(yōu)化算法。本文旨在將AdaGrad自適應(yīng)方法與DA方法相結(jié)合，保留DA方法優(yōu)勢(shì)的同時(shí)，應(yīng)用自適應(yīng)矩陣調(diào)整步長(zhǎng)，使其也能夠適應(yīng)當(dāng)前深度學(xué)習(xí)的發(fā)展趨勢(shì)，形成一種自適應(yīng)的對(duì)偶平均方法（AdaDA）。

2 優(yōu)化算法簡(jiǎn)要介紹

本節(jié)主要對(duì)SGD、DA以及AdaGrad算法進(jìn)行必要的介紹，說明它們?cè)谇蠼馐剑?）問題的主要差異。我們首先對(duì)符號(hào)進(jìn)行明確，k表示算法的迭代步驟，gk表示凸函數(shù)f(x)在xk處的梯度?f(xk)或凸函數(shù)f(x)在xk處的次梯度，即gk∈?f(xk)。

2.1 隨機(jī)梯度下降法

SGD的迭代過程如下：

其中γk為步長(zhǎng)或?qū)W習(xí)率。一般時(shí)，達(dá)到收斂。

2.2 對(duì)偶平均方法

DA的迭代過程如下：

其中λk為對(duì)歷史梯度的加權(quán)，βk+1為步長(zhǎng)，ψ(x)為近端函數(shù)。在λk和βk+1的選擇上，DA具有靈活的步長(zhǎng)策略。基本型的DA方法，即，為了方便與式（2）比較，其可以寫為

2.3 AdaGrad算法

過去的許多優(yōu)化算法往往在步長(zhǎng)或者學(xué)習(xí)率上采用的都是常數(shù)，對(duì)梯度的每一維都進(jìn)行相同的步長(zhǎng)更新。但事實(shí)上，樣本在不同特征（梯度的不同維度）上的變化速度往往是不相同的，有些維度上梯度信息更新的過快，有的維度上梯度信息更新的過慢，自適應(yīng)方法的主要思想就是結(jié)合歷史梯度信息在不同維度上的變化速度給予不同的步長(zhǎng)或權(quán)重，對(duì)變化快的給予較小的權(quán)重限制更新速度，對(duì)變化慢的給予較大的權(quán)重加快更新速度。

AdaGrad第一次使用對(duì)角矩陣來對(duì)梯度的不同維度分配不同的步長(zhǎng)，其他許多自適應(yīng)方法的研究都是在AdaGrad的基礎(chǔ)之上。其迭代過程如下：

3 AdaDA算法分析

3.1 步長(zhǎng)策略

3.2 自適應(yīng)矩陣的引入分析

3.3 AdaDA

4 實(shí)驗(yàn)

本節(jié)通過凸優(yōu)化實(shí)驗(yàn)來檢驗(yàn)AdaDA算法的可行性與收斂效果。

4.1 實(shí)驗(yàn)?zāi)Ｐ秃蛿?shù)據(jù)集

凸優(yōu)化實(shí)驗(yàn)中的問題模型，為支持向量機(jī)中常見的hinge損失，所采用的6個(gè)標(biāo)準(zhǔn)數(shù)據(jù)集，分別為astro，CCAT，covtype ，ijcnn1，rcv1，a9a均來源于LIBSVM網(wǎng)站，詳細(xì)數(shù)據(jù)見表1。

表1 標(biāo)準(zhǔn)數(shù)據(jù)集

4.2 比較算法和超參數(shù)設(shè)置

實(shí)驗(yàn)中選取三種目前使用較多且效果較好的算法：SGD算法、AdaGrad算法、Adam算法以及基本型的DA方法與本文的AdaDA算法進(jìn)行對(duì)比。DA算法采用文獻(xiàn)[2]中的基本型，其他算法步長(zhǎng)及參數(shù)設(shè)置分別為SGD算法使用，AdaGrad算法使用，ε=1e-8，Adam算法使用，ε=1e-8，β1=0.9，β2=0.99，AdaDA算法使用。對(duì)于共同超參數(shù)γ，我們采取了從｛1，0.1，0.01，0.001，0.0001｝中線性搜索的方式，并取其中最好的一次實(shí)驗(yàn)結(jié)果，作為該算法的最終輸出。為了降低隨機(jī)因素產(chǎn)生的影響，各算法在每個(gè)數(shù)據(jù)集上均運(yùn)行5次，并取平均值作為最后的輸出。

4.3 實(shí)驗(yàn)效果及結(jié)論

圖1（a）到圖1（f）為六種算法在六種標(biāo)準(zhǔn)數(shù)據(jù)集下的收斂速率對(duì)比圖，橫坐標(biāo)表示迭代步數(shù)，縱坐標(biāo)為當(dāng)前目標(biāo)函數(shù)值與最優(yōu)目標(biāo)函數(shù)值的差，綠色、黃色、黑色、藍(lán)色、紅色曲線分別代表Adam、DA、AdaGrad、SGD、AdaDA 算法。圖中可見在迭代10000步后，6種算法在6個(gè)標(biāo)準(zhǔn)數(shù)據(jù)集上都達(dá)到了10-4次方的精度，且具有相同的收斂趨勢(shì)，AdaDA收斂速度相對(duì)較快，而且精度相對(duì)較高。

圖1 六種標(biāo)準(zhǔn)數(shù)據(jù)集

5 結(jié)語(yǔ)

本文提出一種名為AdaDA的自適應(yīng)對(duì)偶平均方法，通過一般凸函數(shù)分類優(yōu)化實(shí)驗(yàn)驗(yàn)證了該方法的可行性，達(dá)到了預(yù)期的實(shí)驗(yàn)效果，但尚缺乏理論分析。后續(xù)，我們將繼續(xù)對(duì)AdaDA算法的平均收斂速率及個(gè)體收斂速率進(jìn)行理論研究。