批量減數更新方差縮減梯度下降算法BSUG

宋 杰，朱 勇，許 冰

安徽大學 計算機科學與技術學院，合肥230601

1 引言

機器學習中目標函數通常使用梯度下降（Gradient Descent，GD）或者隨機梯度下降（Stochastic Gradient Descent，SGD）[1]算法進行求解。前者每次迭代都要計算所有樣本的梯度來進行權重更新，后者每次隨機選取一個訓練數據來更新參數。隨后出現改進的Mini-Batch SGD[2]算法，每次迭代通過在原始數據中隨機選取m 個數據樣本進行訓練。SGD 的優點是每一步僅僅依賴于簡單的隨機樣本梯度，因此計算消耗只有標準GD 的1/n。然而它的缺點是在隨機性引入方差情況下，恒定的步長會導致收斂緩慢。

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

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

本文提出一種新的方差縮減算法BSUG（Batch Subtraction Update Gradient），通過隨機抽取小樣本來代替計算全局樣本梯度，同時在參數更新同時對全局平均梯度進行更新。通過理論分析和實驗證明了BSUG算法在收斂速度以及檢測精度方面不弱于其他算法，并且具有較強的穩定性。

2 當前研究現狀

給定n 個訓練數據(x1,y1),(x2,y2),…,(xn,yn)，其中xi∈Rd表示輸入數據，yi∈R 表示對應的訓練標簽，求解目標函數[16]使得每個輸入數據訓練得到的輸出與已知訓練標簽誤差最小。

其中，fi表示目標函數，w 表示目標函數中的參數，w*是最優參數。

機器學習中目標函數通常使用梯度下降（GD）或者隨機梯度下降（SGD）算法進行求解，其中SGD 算法更新如下：

GD 提供了最終收斂的保證，而SGD 在收斂速度、可擴展性和實現簡便方面具有優勢。隨后出現使用式（3）進行更新改進的算法Mini-Batch SGD。

針對恒定步長，AdaGrad 是將每次更新的梯度累加，從而在訓練過程中為權重調整步長。

變量h 保存了所有梯度值的平方和，ε 防止分母為0。然后在更新參數時，通過乘以調節學習的尺度。但是AdaGrad在迭代后期由于步長過小，可能很難找到一個最優解。

為了解決AdaGrad的問題，RMSProp使用了加權平均數。

其中，β 是梯度累積權重，s 保存了所有梯度值的加權平方和，它并不會因為迭代一直累加，這樣也就不會出現后期收斂緩慢的問題。

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

其中，w ∈Rd表示模型參數，η 表示更新步長，=是使用上一輪模型參數計算出的全局平均梯度，表示函數f 在樣本點ij的梯度，是梯度的偏差，是經過修正后的無偏估計，使用來更新wj。

算法偽代碼如下：

算法1 SVRG

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

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

Lei等人提出了Mini-Batch SCSG，一種小批量樣本無偏估計算法。該方法基于SCSG的小樣本平均梯度，在計算梯度的無偏估計時，使用小批量樣本的平均梯度來代替原有單個樣本梯度，即：

Gower等人提出了b-NICE SAGA，一種針對SAGA單樣本更新平均梯度緩慢問題而提出的新算法。該方法在更新平均梯度時使用小批量樣本梯度同時替換更新，在計算梯度無偏估計時也是使用小批量樣本的平均梯度來進行計算。它通過平滑度系數設置了最優批量大小，從而總復雜度線性降低，但計算成本和內存消耗有所增加，小批量樣本梯度的計算與更新加大了整個算法的計算消耗。

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

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

3 BSUG算法

3.1 算法介紹

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

算法偽代碼如算法2。

算法2 BSUG

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

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

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

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

（4）隨機從B 中選取一個樣本進行梯度無偏估計計算，如步驟10、11所示；

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

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

3.2 算法收斂性分析

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

假設1 fi是具有L-Lipschitz梯度的凸函數：

假設2 P(w)是強凸函數：

由文獻[6]可知：

通過對j=1,2,…,k 階段的累加可得：

第二個不等式使用了強凸性質（12），因此獲得：

從而有BSUG的收斂性：

由BSUG算法的收斂性可以看出，算法的收斂速度與參數B 和k 的選取有關。關于參數B 和k 的選取對算法的穩定性以及收斂速度探究將在實驗部分詳細說明。

4 實驗

本文算法是由Python3.6 完成，整體網絡架構參考文獻[19]完成。對于算法的實現，本文使用的設備為CPU：AMD A6-3400M APU with RadeonTMHD Graphics 1.40 GHz，內存6.00 GB。使用的是主流數據集MNIST[20]，參與訓練樣本是從MNIST數據中隨機抽取的10 000個訓練樣本，測試樣本是MNIST 自帶的10 000 個測試樣本。本文所有程序網絡結構全部為728×40×10，即輸入層728個神經元，隱含層40個神經元，輸出層為10個神經元的Softmax-with-Loss層。

實驗總共包括兩部分：第一部分主要是本文算法與當前主流算法之間的評測對比；第二部分主要是對本文算法參數關系的探究。

4.1 算法對比

使用Python3.6編程實現BSUG算法，將其與主流的Mini-Batch SGD、AdaGrad、RMSProp、SVRG 和SCSG算法進行對比評測。

從表1和圖1中可以看出以下幾點：

（1）BSUG、RMSProp 與SCSG 迭代到第一個epoch時，精度都達到了65%，而SVRG、Mini-Batch SGD 和AdaGrad只達到40%。隨著迭代進行，BSUG、RMSProp與SCSG只需7個epoch精度就達到80%，而SVRG達到65%，Mini-Batch SGD 和AdaGrad 只達到50%，可見BSUG 在收斂速度上與RMSProp、SCSG 相當，并優于SVRG、Mini-Batch SGD和AdaGrad。

（2）BSUG、RMSProp 與SCSG 都平穩快速地達到高精準度。在準確度上BSUG 與SCSG 相差0.26 個百分點，與RMSProp 相差1.13 個百分點，SVRG 的檢測準確率略低于前面三種算法，但仍然比Mini-Batch SGD和AdaGrad優秀。

（3）Mini-Batch SGD 和AdaGrad 沒有達到高準確率要求，合理猜測是由于訓練樣本不足導致的，這也間接說明Mini-Batch SGD和AdaGrad存在不能更深入學習樣本特征的缺點。

表1 算法對比結果

圖1 算法精度對比

4.2 穩定性探究

本文算法的穩定性主要受到批大小B 以及內迭代次數k 兩個因素影響。本文主要從訓練樣本數B 與n比例關系和B 與k 比例關系兩方面進行實驗探究。

4.2.1 B 與n 比例探究

在探究B 與n 比例關系對算法的影響實驗中，將從MNIST 數據中逐一抽取10 000、8 000、4 000 個樣本進行訓練，并且B ∈{n/2,n/4,n/8,n/16,n/32}，設置k=B-1 進行實驗。

表2 B 與n 比例探究結果

表3 B 與k 比例探究結果

從表2和圖2中可以看出以下幾點：

（1）B 與n 之間的比例關系與算法效果有一定的關系，B 越大訓練精度越小，同時因為k 的設置導致替代次數變多，訓練的時間也會越長。

（3）實驗樣本數過少，當樣本數更多時應該設置適當的B 來適應數據集。

圖2 B 與n 比例探究結果

4.2.2 B 與k 比例探究

探究B 與k 比例關系對算法的影響實驗中，將從MNIST 數據中抽取8 000 個樣本進行訓練。同時讓B分別為250、500、1 000，設置k ∈{B-1,0.8×B,0.6×B,0.4×B,0.2×B}進行實驗。

從表3和圖3中可以看出以下幾點：

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

（2）由數據的交叉觀測可知，當k 為常數(k=200)時，精度會隨著B 的增加而降低，更加證實上述觀點。

4.3 實驗總結

圖3 B 與k 比例探究結果

通過4.1節可以發現BSUG算法相比于Mini-Batch SGD、AdaGrad和SVRG等算法在收斂速度和精度上效果突出，并和RMSProp、SCSG效果相當。通過4.2節可以知道BSUG算法是一個相對穩定的算法，以及參數對算法精度影響的趨勢。

5 結束語

本文采用小樣本平均梯度代替全局平均梯度的思想，設計了選取小樣本進行訓練，同時更新平均梯度來實現方差縮減的算法BSUG，基于Python平臺進行算法實現，并理論證明了算法的收斂性。通過實驗證明了BSUG算法優于Mini-Batch SGD、AdaGrad和SVRG算法，與RMSProp、SCSG 算法效果相當。并且通過對超參數的探究證明了BSUG算法具有一定的穩定性，在批量較低的情況下也能達到足夠的精度。

本文由于設備原因，導致無法對更大數據集進行實驗，同時對于批大小的最低下限沒有進行更深入的討論，這將是以后繼續完善的方向。