宋 杰，朱 勇，許 冰

安徽大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，合肥230601

1 引言

機(jī)器學(xué)習(xí)中目標(biāo)函數(shù)通常使用梯度下降（Gradient Descent，GD）或者隨機(jī)梯度下降（Stochastic Gradient Descent，SGD）[1]算法進(jìn)行求解。前者每次迭代都要計(jì)算所有樣本的梯度來(lái)進(jìn)行權(quán)重更新，后者每次隨機(jī)選取一個(gè)訓(xùn)練數(shù)據(jù)來(lái)更新參數(shù)。隨后出現(xiàn)改進(jìn)的Mini-Batch SGD[2]算法，每次迭代通過(guò)在原始數(shù)據(jù)中隨機(jī)選取m 個(gè)數(shù)據(jù)樣本進(jìn)行訓(xùn)練。SGD 的優(yōu)點(diǎn)是每一步僅僅依賴于簡(jiǎn)單的隨機(jī)樣本梯度，因此計(jì)算消耗只有標(biāo)準(zhǔn)GD 的1/n。然而它的缺點(diǎn)是在隨機(jī)性引入方差情況下，恒定的步長(zhǎng)會(huì)導(dǎo)致收斂緩慢。

近年來(lái)，許多學(xué)者基于SGD 算法進(jìn)行研究，其中Sutskever 等人提出Momentum 算法[3]，它是基于梯度動(dòng)量累積的思想使用指數(shù)加權(quán)平均來(lái)減小梯度的擺動(dòng)幅度。Duchi 等人提出AdaGrad（Adaptive Gradient）[4]算法，它是通過(guò)逐漸縮小步長(zhǎng)來(lái)進(jìn)行學(xué)習(xí)。Hinton在他的機(jī)器學(xué)習(xí)神經(jīng)網(wǎng)絡(luò)課程中提出RMSProp（Root Mean Square Prop）[5]，其使用微分平方加權(quán)平均數(shù)進(jìn)一步優(yōu)化損失函數(shù)擺幅過(guò)大的問(wèn)題。而針對(duì)SGD隨機(jī)性引入方差問(wèn)題，文獻(xiàn)[6]提出了隨機(jī)方差縮減梯度法（Stochastic Variance Reduction Gradient，SVRG），其核心思想是利用全局梯度信息對(duì)每次用于模型更新的梯度進(jìn)行修正[7]。理論分析和實(shí)驗(yàn)證明，SVRG 在方差降低的情況下產(chǎn)生了線性收斂。隨后依據(jù)方差縮減思想產(chǎn)生了新型的SAGA（Stochastic Average Gradient Average）[8]、

SCSG（Stochastically Controlled Stochastic Gradient）[9]、Mini-Batch SCSG[10]、b-NICE SAGA[11-12]等一系列算法[13-15]。其中SAGA是通過(guò)保留每個(gè)樣本梯度，在計(jì)算過(guò)程中更新全局梯度平均值來(lái)縮減方差，這個(gè)過(guò)程需要儲(chǔ)存所有樣本梯度，為計(jì)算機(jī)帶來(lái)很大的存儲(chǔ)困難。SCSG 則是通過(guò)隨機(jī)抽取一部分樣本梯度作為全局梯度來(lái)計(jì)算平均梯度，但是在進(jìn)行權(quán)重更新時(shí)，隨機(jī)選取更新次數(shù)會(huì)讓計(jì)算更加多變與繁瑣，計(jì)算量大。

本文提出一種新的方差縮減算法BSUG（Batch Subtraction Update Gradient），通過(guò)隨機(jī)抽取小樣本來(lái)代替計(jì)算全局樣本梯度，同時(shí)在參數(shù)更新同時(shí)對(duì)全局平均梯度進(jìn)行更新。通過(guò)理論分析和實(shí)驗(yàn)證明了BSUG算法在收斂速度以及檢測(cè)精度方面不弱于其他算法，并且具有較強(qiáng)的穩(wěn)定性。

2 當(dāng)前研究現(xiàn)狀

給定n 個(gè)訓(xùn)練數(shù)據(jù)(x1,y1),(x2,y2),…,(xn,yn)，其中xi∈Rd表示輸入數(shù)據(jù)，yi∈R 表示對(duì)應(yīng)的訓(xùn)練標(biāo)簽，求解目標(biāo)函數(shù)[16]使得每個(gè)輸入數(shù)據(jù)訓(xùn)練得到的輸出與已知訓(xùn)練標(biāo)簽誤差最小。

其中，fi表示目標(biāo)函數(shù)，w 表示目標(biāo)函數(shù)中的參數(shù)，w*是最優(yōu)參數(shù)。

機(jī)器學(xué)習(xí)中目標(biāo)函數(shù)通常使用梯度下降（GD）或者隨機(jī)梯度下降（SGD）算法進(jìn)行求解，其中SGD 算法更新如下：

GD 提供了最終收斂的保證，而SGD 在收斂速度、可擴(kuò)展性和實(shí)現(xiàn)簡(jiǎn)便方面具有優(yōu)勢(shì)。隨后出現(xiàn)使用式（3）進(jìn)行更新改進(jìn)的算法Mini-Batch SGD。

針對(duì)恒定步長(zhǎng)，AdaGrad 是將每次更新的梯度累加，從而在訓(xùn)練過(guò)程中為權(quán)重調(diào)整步長(zhǎng)。

變量h 保存了所有梯度值的平方和，ε 防止分母為0。然后在更新參數(shù)時(shí)，通過(guò)乘以調(diào)節(jié)學(xué)習(xí)的尺度。但是AdaGrad在迭代后期由于步長(zhǎng)過(guò)小，可能很難找到一個(gè)最優(yōu)解。

為了解決AdaGrad的問(wèn)題，RMSProp使用了加權(quán)平均數(shù)。

其中，β 是梯度累積權(quán)重，s 保存了所有梯度值的加權(quán)平方和，它并不會(huì)因?yàn)榈恢崩奂?，這樣也就不會(huì)出現(xiàn)后期收斂緩慢的問(wèn)題。

SVRG 的提出主要是用來(lái)解決由于方差而導(dǎo)致SGD不能快速收斂的問(wèn)題，其核心思想是利用全局的梯度信息對(duì)每次用于模型更新的梯度進(jìn)行修正。算法中每次的迭代都是通過(guò)以下公式進(jìn)行更新：

其中，w ∈Rd表示模型參數(shù)，η 表示更新步長(zhǎng)，=是使用上一輪模型參數(shù)計(jì)算出的全局平均梯度，表示函數(shù)f 在樣本點(diǎn)ij的梯度，是梯度的偏差，是經(jīng)過(guò)修正后的無(wú)偏估計(jì)，使用來(lái)更新wj。

算法偽代碼如下：

算法1 SVRG

從算法1 中可以看出，算法的主要計(jì)算在步驟2 和步驟6 中。步驟2 是計(jì)算平均梯度，步驟6 是計(jì)算修正后的梯度無(wú)偏估計(jì)，從到一輪迭代計(jì)算成本為n+2m 。隨后SAGA 和SCSG 也主要是從這兩個(gè)步驟進(jìn)行修改從而優(yōu)化算法。

在SAGA算法中，利用一塊內(nèi)存存儲(chǔ)所有樣本的原始梯度，計(jì)算出以當(dāng)前新權(quán)重為模型的新梯度?fij(wj-1),通過(guò)從而達(dá)到更新的目的，但是算法內(nèi)存占用過(guò)大。而SCSG算法主要是通過(guò)在數(shù)據(jù)集中隨機(jī)抽取B 個(gè)小樣本數(shù)據(jù)進(jìn)行全局平均梯度的估計(jì)，并且對(duì)于梯度的無(wú)偏估計(jì)迭代次數(shù)k 主要是從服從幾何分布的數(shù)列{1,2,…,m}中隨機(jī)抽取，計(jì)算成本為B+2k,小于SVRG的n+2m。

Lei等人提出了Mini-Batch SCSG，一種小批量樣本無(wú)偏估計(jì)算法。該方法基于SCSG的小樣本平均梯度，在計(jì)算梯度的無(wú)偏估計(jì)時(shí)，使用小批量樣本的平均梯度來(lái)代替原有單個(gè)樣本梯度，即：

Gower等人提出了b-NICE SAGA，一種針對(duì)SAGA單樣本更新平均梯度緩慢問(wèn)題而提出的新算法。該方法在更新平均梯度時(shí)使用小批量樣本梯度同時(shí)替換更新，在計(jì)算梯度無(wú)偏估計(jì)時(shí)也是使用小批量樣本的平均梯度來(lái)進(jìn)行計(jì)算。它通過(guò)平滑度系數(shù)設(shè)置了最優(yōu)批量大小，從而總復(fù)雜度線性降低，但計(jì)算成本和內(nèi)存消耗有所增加，小批量樣本梯度的計(jì)算與更新加大了整個(gè)算法的計(jì)算消耗。

Allen-Zhu 等人提出了Natasha[17]，一種新的參數(shù)更新方法。該方法主要是對(duì)參數(shù)隨機(jī)抽樣更新。通過(guò)每輪參數(shù)抽樣對(duì)部分參數(shù)進(jìn)行更新，同時(shí)使用小批量樣本進(jìn)行梯度計(jì)算。

Zou 等人提出的SVR-HMC[18]則是在迭代過(guò)程中對(duì)參數(shù)利用哈密爾頓蒙特卡羅方法進(jìn)行錯(cuò)位更新，但其本質(zhì)也是一種比較復(fù)雜的無(wú)偏估計(jì)計(jì)算方式。

3 BSUG算法

3.1 算法介紹

SCSG算法中的小批量平均梯度以及SAGA算法中的無(wú)偏估計(jì)更新為本文的算法帶來(lái)靈感。這里使用更新的平均梯度是由SCSG計(jì)算出的小批量平均梯度，即n →B，這樣可以減少存儲(chǔ)成本。同時(shí)改變SAGA 平均梯度的更新形式，由原來(lái)的改為，即將過(guò)去模型計(jì)算出的樣本梯度直接舍去，通過(guò)直接舍去樣本梯度來(lái)減少梯度方差。不可避免的，計(jì)算梯度無(wú)偏估計(jì)的迭代次數(shù)也要相應(yīng)地減少為小于B，間接地減少計(jì)算成本。

算法偽代碼如算法2。

算法2 BSUG

BSUG算法主要包括以下部分：

（1）從n 個(gè)樣本中隨機(jī)抽取樣本Ht,| Ht|=B，如步驟2所示；

（2）計(jì)算Ht中所有樣本梯度并保存，如步驟3～6所示；

（3）計(jì)算每次更新的平均梯度，如步驟9所示；

（4）隨機(jī)從B 中選取一個(gè)樣本進(jìn)行梯度無(wú)偏估計(jì)計(jì)算，如步驟10、11所示；

（5）將選取樣本所在的梯度刪除，重新計(jì)算平均梯度，如步驟12、9所示。

從步驟12可以看出，?fij(w[ij])是有限的，且刪除后不再擁有，為避免錯(cuò)誤重復(fù)刪除，在程序編程時(shí)會(huì)將B中的樣本隨機(jī)排序后依次抽取。

3.2 算法收斂性分析

為了簡(jiǎn)單起見，本文只考慮每個(gè)fi(w)的情況是凸面平滑，P(w)是強(qiáng)凸問(wèn)題。下面的假設(shè)將在本文的各種情況下使用。

假設(shè)1 fi是具有L-Lipschitz梯度的凸函數(shù)：

假設(shè)2 P(w)是強(qiáng)凸函數(shù)：

由文獻(xiàn)[6]可知：

通過(guò)對(duì)j=1,2,…,k 階段的累加可得：

第二個(gè)不等式使用了強(qiáng)凸性質(zhì)（12），因此獲得：

從而有BSUG的收斂性：

由BSUG算法的收斂性可以看出，算法的收斂速度與參數(shù)B 和k 的選取有關(guān)。關(guān)于參數(shù)B 和k 的選取對(duì)算法的穩(wěn)定性以及收斂速度探究將在實(shí)驗(yàn)部分詳細(xì)說(shuō)明。

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

本文算法是由Python3.6 完成，整體網(wǎng)絡(luò)架構(gòu)參考文獻(xiàn)[19]完成。對(duì)于算法的實(shí)現(xiàn)，本文使用的設(shè)備為CPU：AMD A6-3400M APU with RadeonTMHD Graphics 1.40 GHz，內(nèi)存6.00 GB。使用的是主流數(shù)據(jù)集MNIST[20]，參與訓(xùn)練樣本是從MNIST數(shù)據(jù)中隨機(jī)抽取的10 000個(gè)訓(xùn)練樣本，測(cè)試樣本是MNIST 自帶的10 000 個(gè)測(cè)試樣本。本文所有程序網(wǎng)絡(luò)結(jié)構(gòu)全部為728×40×10，即輸入層728個(gè)神經(jīng)元，隱含層40個(gè)神經(jīng)元，輸出層為10個(gè)神經(jīng)元的Softmax-with-Loss層。

實(shí)驗(yàn)總共包括兩部分：第一部分主要是本文算法與當(dāng)前主流算法之間的評(píng)測(cè)對(duì)比；第二部分主要是對(duì)本文算法參數(shù)關(guān)系的探究。

4.1 算法對(duì)比

使用Python3.6編程實(shí)現(xiàn)BSUG算法，將其與主流的Mini-Batch SGD、AdaGrad、RMSProp、SVRG 和SCSG算法進(jìn)行對(duì)比評(píng)測(cè)。

從表1和圖1中可以看出以下幾點(diǎn)：

（1）BSUG、RMSProp 與SCSG 迭代到第一個(gè)epoch時(shí)，精度都達(dá)到了65%，而SVRG、Mini-Batch SGD 和AdaGrad只達(dá)到40%。隨著迭代進(jìn)行，BSUG、RMSProp與SCSG只需7個(gè)epoch精度就達(dá)到80%，而SVRG達(dá)到65%，Mini-Batch SGD 和AdaGrad 只達(dá)到50%，可見BSUG 在收斂速度上與RMSProp、SCSG 相當(dāng)，并優(yōu)于SVRG、Mini-Batch SGD和AdaGrad。

（2）BSUG、RMSProp 與SCSG 都平穩(wěn)快速地達(dá)到高精準(zhǔn)度。在準(zhǔn)確度上BSUG 與SCSG 相差0.26 個(gè)百分點(diǎn)，與RMSProp 相差1.13 個(gè)百分點(diǎn)，SVRG 的檢測(cè)準(zhǔn)確率略低于前面三種算法，但仍然比Mini-Batch SGD和AdaGrad優(yōu)秀。

（3）Mini-Batch SGD 和AdaGrad 沒(méi)有達(dá)到高準(zhǔn)確率要求，合理猜測(cè)是由于訓(xùn)練樣本不足導(dǎo)致的，這也間接說(shuō)明Mini-Batch SGD和AdaGrad存在不能更深入學(xué)習(xí)樣本特征的缺點(diǎn)。

表1 算法對(duì)比結(jié)果

圖1 算法精度對(duì)比

4.2 穩(wěn)定性探究

本文算法的穩(wěn)定性主要受到批大小B 以及內(nèi)迭代次數(shù)k 兩個(gè)因素影響。本文主要從訓(xùn)練樣本數(shù)B 與n比例關(guān)系和B 與k 比例關(guān)系兩方面進(jìn)行實(shí)驗(yàn)探究。

4.2.1 B 與n 比例探究

在探究B 與n 比例關(guān)系對(duì)算法的影響實(shí)驗(yàn)中，將從MNIST 數(shù)據(jù)中逐一抽取10 000、8 000、4 000 個(gè)樣本進(jìn)行訓(xùn)練，并且B ∈{n/2,n/4,n/8,n/16,n/32}，設(shè)置k=B-1 進(jìn)行實(shí)驗(yàn)。

表2 B 與n 比例探究結(jié)果

表3 B 與k 比例探究結(jié)果

從表2和圖2中可以看出以下幾點(diǎn)：

（1）B 與n 之間的比例關(guān)系與算法效果有一定的關(guān)系，B 越大訓(xùn)練精度越小，同時(shí)因?yàn)閗 的設(shè)置導(dǎo)致替代次數(shù)變多，訓(xùn)練的時(shí)間也會(huì)越長(zhǎng)。

（3）實(shí)驗(yàn)樣本數(shù)過(guò)少，當(dāng)樣本數(shù)更多時(shí)應(yīng)該設(shè)置適當(dāng)?shù)腂 來(lái)適應(yīng)數(shù)據(jù)集。

圖2 B 與n 比例探究結(jié)果

4.2.2 B 與k 比例探究

探究B 與k 比例關(guān)系對(duì)算法的影響實(shí)驗(yàn)中，將從MNIST 數(shù)據(jù)中抽取8 000 個(gè)樣本進(jìn)行訓(xùn)練。同時(shí)讓B分別為250、500、1 000，設(shè)置k ∈{B-1,0.8×B,0.6×B,0.4×B,0.2×B}進(jìn)行實(shí)驗(yàn)。

從表3和圖3中可以看出以下幾點(diǎn)：

（1）k 與B 的大小關(guān)系對(duì)算法效果有直接影響，k越接近于B，算法的測(cè)試精度越高，反之，精度下降，且這種現(xiàn)象不隨B 的增加發(fā)生變化。

（2）由數(shù)據(jù)的交叉觀測(cè)可知，當(dāng)k 為常數(shù)(k=200)時(shí)，精度會(huì)隨著B 的增加而降低，更加證實(shí)上述觀點(diǎn)。

4.3 實(shí)驗(yàn)總結(jié)

圖3 B 與k 比例探究結(jié)果

通過(guò)4.1節(jié)可以發(fā)現(xiàn)BSUG算法相比于Mini-Batch SGD、AdaGrad和SVRG等算法在收斂速度和精度上效果突出，并和RMSProp、SCSG效果相當(dāng)。通過(guò)4.2節(jié)可以知道BSUG算法是一個(gè)相對(duì)穩(wěn)定的算法，以及參數(shù)對(duì)算法精度影響的趨勢(shì)。

5 結(jié)束語(yǔ)

本文采用小樣本平均梯度代替全局平均梯度的思想，設(shè)計(jì)了選取小樣本進(jìn)行訓(xùn)練，同時(shí)更新平均梯度來(lái)實(shí)現(xiàn)方差縮減的算法BSUG，基于Python平臺(tái)進(jìn)行算法實(shí)現(xiàn)，并理論證明了算法的收斂性。通過(guò)實(shí)驗(yàn)證明了BSUG算法優(yōu)于Mini-Batch SGD、AdaGrad和SVRG算法，與RMSProp、SCSG 算法效果相當(dāng)。并且通過(guò)對(duì)超參數(shù)的探究證明了BSUG算法具有一定的穩(wěn)定性，在批量較低的情況下也能達(dá)到足夠的精度。

本文由于設(shè)備原因，導(dǎo)致無(wú)法對(duì)更大數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，同時(shí)對(duì)于批大小的最低下限沒(méi)有進(jìn)行更深入的討論，這將是以后繼續(xù)完善的方向。