機(jī)器學(xué)習(xí)中隨機(jī)方差縮減梯度算法的一種新的步長(zhǎng)規(guī)則

楊一名，王福勝

(太原師范學(xué)院 數(shù)學(xué)系，山西 晉中 030619)

0 引言

在統(tǒng)計(jì)機(jī)器學(xué)習(xí)[1]和信號(hào)處理[2]等領(lǐng)域中，通?？紤]如下形式的優(yōu)化問(wèn)題：

其中n代表訓(xùn)練樣本數(shù)目，d代表變量維度，本文假設(shè)每一個(gè)fi均是一階連續(xù)可微的.求解上述問(wèn)題的傳統(tǒng)方法是梯度下降算法[3]，但是當(dāng)n的取值較大時(shí)，該方法在計(jì)算量上很難容忍甚至不能執(zhí)行.針對(duì)這一缺陷，基于Robbins和Monro[4]提出的隨機(jī)近似思想，研究者們提出了隨機(jī)梯度下降算法(SGD)[5]，SGD算法的特點(diǎn)是每次迭代只選取一個(gè)或部分樣本確定迭代方向，選取一個(gè)樣本時(shí)的迭代公式如下：

ωk+1=ωk-ηk?fik(ωk)，

其中，?fik(ωk)表示第ik個(gè)分量函數(shù)在ωk處的梯度，ηk>0表示步長(zhǎng).目前，通過(guò)引入不同技術(shù)改進(jìn)SGD性能的工作被廣泛應(yīng)用[6-8].事實(shí)上，SGD算法本身的收斂性取決于隨機(jī)方向與真實(shí)梯度的方差，采用梯度聚合的方式可以有效縮減方差.經(jīng)典的梯度聚合類算法通過(guò)重新使用或修改之前的梯度縮減方差，常見(jiàn)的有隨機(jī)方差縮減梯度算法(SVRG)[9]，隨機(jī)對(duì)偶坐標(biāo)上升算法(SDCA)[10]，半隨機(jī)梯度下降算法(S2GD)[11]，小批量半隨機(jī)梯度下降算法(mS2GD)[12]，隨機(jī)遞歸梯度算法(SARAH)[13]，隨機(jī)平均梯度算法(SAG)[14]和SAGA[15]等.

對(duì)于方差縮減類算法而言，步長(zhǎng)是影響算法性能的關(guān)鍵因素，傳統(tǒng)的方法是根據(jù)人為的經(jīng)驗(yàn)選擇符合某種規(guī)律的遞減步長(zhǎng)或者較小的固定步長(zhǎng)，并且滿足：

AdaGrad[16]和Adam[17]等采用對(duì)角修正技術(shù)為每個(gè)分量自適應(yīng)地選取步長(zhǎng).當(dāng)前，由于BB步長(zhǎng)[18]特有的性質(zhì)，許多學(xué)者創(chuàng)新性地提出將方差縮減方法與BB步長(zhǎng)相結(jié)合以提高算法的收斂速度.受啟發(fā)于SGD-BB[19]和STSG[20]算法，本文考慮將復(fù)合BB步長(zhǎng)(CABB)[21]與隨機(jī)方差縮減梯度算法(SVRG)[9]結(jié)合，提出SVRG-CABB.

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

構(gòu)造新算法之前，本節(jié)首先回顧隨機(jī)方差縮減梯度算法(SVRG)[9].事實(shí)上，SVRG包括兩層循環(huán)，通常在外循環(huán)中計(jì)算全梯度，而在內(nèi)循環(huán)中計(jì)算方差縮減的隨機(jī)梯度，在迭代過(guò)程中需要隨機(jī)選取下標(biāo)it∈{1,…,n}.從總體上看，該算法執(zhí)行最關(guān)鍵步驟是對(duì)于隨機(jī)梯度的更新，即：

其迭代更新規(guī)則為：

ωt+1=ωt-ηkvt.

可以發(fā)現(xiàn)SVRG算法中迭代方向vt是真實(shí)梯度的無(wú)偏估計(jì)，且算法在迭代過(guò)程中的方差在逐漸減小，以下給出SVRG算法的基本框架：

第4步：如果t>m，轉(zhuǎn)第5步；否則轉(zhuǎn)第3步；

第6步：令k:=k+1，如果k>T，停止；否則轉(zhuǎn)第2步.

2 BB步長(zhǎng)

第3步：如果k>0，計(jì)算復(fù)合BB步長(zhǎng)：

第6步：令k:=k+1，如果k>T，停止；否則轉(zhuǎn)第2步.

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

本節(jié)將SVRG-CABB算法應(yīng)用于求解帶有l(wèi)2正則化項(xiàng)的邏輯回歸模型，并給出實(shí)驗(yàn)結(jié)果驗(yàn)證算法的有效性，模型表示如下：

表1 數(shù)據(jù)集信息

實(shí)驗(yàn)包括四個(gè)部分：首先，對(duì)比了SVRG-CABB算法與SVRG算法的收斂速度，驗(yàn)證了SVRG-CABB的有效性；其次，對(duì)比了SVRG-CABB算法與SVRG算法的分類準(zhǔn)確率；接著，測(cè)試了SVRG-CABB算法關(guān)于不同初始步長(zhǎng)的步長(zhǎng)變化趨勢(shì)；最后，對(duì)比了SVRG-CABB算法和STSG[20]算法在不同數(shù)據(jù)集上的求解目標(biāo)函數(shù)時(shí)參數(shù)τ對(duì)算法性能的影響.所有的實(shí)驗(yàn)結(jié)果如圖1到圖4所示.

圖1 SVRG-CABB和帶有固定步長(zhǎng)的SVRG算法殘差對(duì)比

圖1對(duì)比了SVRG-CABB和SVRG算法的收斂速度，其中x軸代表迭代次數(shù)，y軸代表求解目標(biāo)函數(shù)所得的殘差損失，圖中的虛線和實(shí)線分別對(duì)應(yīng)于帶有不同初始步長(zhǎng)的SVRG-CABB算法，虛線分別對(duì)應(yīng)于帶有固定步長(zhǎng)的SVRG算法.四個(gè)子圖(a)，(b)，(c)和(d)分別對(duì)應(yīng)于兩種算法在數(shù)據(jù)集heart，splice，ijcnn1和a9a上的實(shí)驗(yàn)結(jié)果對(duì)比.從圖中可以看出，本文提出的新算法SVRG-CABB收斂速度整體上比帶有固定步長(zhǎng)的SVRG算法快，并且當(dāng)選擇不同的初始步長(zhǎng)η0時(shí)，SVRG-CABB算法的收斂性能不受影響，可以看出使用CABB步長(zhǎng)的優(yōu)勢(shì)是使得新算法對(duì)于步長(zhǎng)的選取更加容易.

圖2 SVRG-CABB和固定步長(zhǎng)的SVRG算法分類準(zhǔn)確率對(duì)比

圖2對(duì)比了SVRG-CABB和SVRG算法在不同數(shù)據(jù)集上的求解目標(biāo)函數(shù)的分類準(zhǔn)確率，其中x軸代表迭代次數(shù)，y軸代表求解分類準(zhǔn)確率，圖中虛線和實(shí)線分別對(duì)應(yīng)帶有不同初始步長(zhǎng)的SVRG-CABB算法，虛線分別對(duì)應(yīng)帶有固定步長(zhǎng)的SVRG算法.四個(gè)子圖(a)，(b)，(c)和(d)分別對(duì)應(yīng)兩種算法在數(shù)據(jù)集heart，splice，ijcnn1和a9a上的實(shí)驗(yàn)對(duì)比.從圖中可以看出，本文提出的SVRG-CABB算法的分類準(zhǔn)確率明顯高于帶有固定步長(zhǎng)的SVRG算法，當(dāng)選擇不同的初始步長(zhǎng)η0時(shí)，SVRG-CABB算法的分類準(zhǔn)確率并不受影響.在相同條件下，SVRG-CABB算法分類準(zhǔn)確率更加穩(wěn)定且明顯高于帶有固定步長(zhǎng)的SVRG算法.

圖3 SVRG-CABB步長(zhǎng)變化趨勢(shì)

圖3測(cè)試了SVRG-CABB算法在不同數(shù)據(jù)集上的求解目標(biāo)函數(shù)時(shí)步長(zhǎng)的變化趨勢(shì)，其中x軸代表迭代次數(shù)，y軸代表步長(zhǎng)，圖中虛線和實(shí)線分別對(duì)應(yīng)不同的初始步長(zhǎng)，虛線分別對(duì)應(yīng)不同的固定步長(zhǎng).兩個(gè)子圖(a)和(b)分別對(duì)應(yīng)于SVRG-CABB算法在數(shù)據(jù)集heart和splice上的測(cè)試結(jié)果.從圖中可以看出，本文提出的SVRG-CABB算法的步長(zhǎng)最終收斂于最優(yōu)步長(zhǎng)的鄰域.這說(shuō)明選取不同的初始步長(zhǎng)，對(duì)算法收斂性能影響不大.

圖4 不同參數(shù)值τ下SVRG-CABB和STSG算法性能對(duì)比

圖4對(duì)比了SVRG-CABB算法和STSG算法在不同數(shù)據(jù)集上的求解目標(biāo)函數(shù)時(shí)參數(shù)τ對(duì)算法性能的影響，其中x軸代表迭代次數(shù)，y軸代表殘差損失，圖中的實(shí)線分別對(duì)應(yīng)于τ∈(0,1)的SVRG-CABB算法，虛線分別對(duì)應(yīng)于τ∈(0,1)的STSG算法.兩個(gè)子圖(a)和(b)分別對(duì)應(yīng)于SVRG-CABB算法在數(shù)據(jù)集heart和a9a上的測(cè)試結(jié)果.從圖中可以看出，本文提出的SVRG-CABB和STSG的算法性能雖然均受參數(shù)τ值的影響，并且隨著τ值的增加算法性能總體得到提升，但是SVRG-CABB算法的收斂性能最終優(yōu)于選擇相同參數(shù)τ的STSG算法.

4 結(jié)論

本文將隨機(jī)方差縮減梯度算法(SVRG)與改進(jìn)的復(fù)合BB步長(zhǎng)(CABB)有機(jī)結(jié)合，提出了一種新的SVRG-CABB算法.從實(shí)驗(yàn)結(jié)果分析來(lái)看，新算法在求解問(wèn)題的過(guò)程中可以動(dòng)態(tài)調(diào)節(jié)步長(zhǎng)的大小，相比于已有的使用固定步長(zhǎng)的SVRG算法以及已有的STSG算法，新算法的收斂速度更快，并且不受初始步長(zhǎng)選取的影響.