楊一名,王福勝
(太原師范學院 數(shù)學系,山西 晉中 030619)
在統(tǒng)計機器學習[1]和信號處理[2]等領(lǐng)域中,通??紤]如下形式的優(yōu)化問題:
其中n代表訓練樣本數(shù)目,d代表變量維度,本文假設(shè)每一個fi均是一階連續(xù)可微的.求解上述問題的傳統(tǒng)方法是梯度下降算法[3],但是當n的取值較大時,該方法在計算量上很難容忍甚至不能執(zhí)行.針對這一缺陷,基于Robbins和Monro[4]提出的隨機近似思想,研究者們提出了隨機梯度下降算法(SGD)[5],SGD算法的特點是每次迭代只選取一個或部分樣本確定迭代方向,選取一個樣本時的迭代公式如下:
ωk+1=ωk-ηk?fik(ωk),
其中,?fik(ωk)表示第ik個分量函數(shù)在ωk處的梯度,ηk>0表示步長.目前,通過引入不同技術(shù)改進SGD性能的工作被廣泛應用[6-8].事實上,SGD算法本身的收斂性取決于隨機方向與真實梯度的方差,采用梯度聚合的方式可以有效縮減方差.經(jīng)典的梯度聚合類算法通過重新使用或修改之前的梯度縮減方差,常見的有隨機方差縮減梯度算法(SVRG)[9],隨機對偶坐標上升算法(SDCA)[10],半隨機梯度下降算法(S2GD)[11],小批量半隨機梯度下降算法(mS2GD)[12],隨機遞歸梯度算法(SARAH)[13],隨機平均梯度算法(SAG)[14]和SAGA[15]等.
對于方差縮減類算法而言,步長是影響算法性能的關(guān)鍵因素,傳統(tǒng)的方法是根據(jù)人為的經(jīng)驗選擇符合某種規(guī)律的遞減步長或者較小的固定步長,并且滿足:
AdaGrad[16]和Adam[17]等采用對角修正技術(shù)為每個分量自適應地選取步長.當前,由于BB步長[18]特有的性質(zhì),許多學者創(chuàng)新性地提出將方差縮減方法與BB步長相結(jié)合以提高算法的收斂速度.受啟發(fā)于SGD-BB[19]和STSG[20]算法,本文考慮將復合BB步長(CABB)[21]與隨機方差縮減梯度算法(SVRG)[9]結(jié)合,提出SVRG-CABB.
構(gòu)造新算法之前,本節(jié)首先回顧隨機方差縮減梯度算法(SVRG)[9].事實上,SVRG包括兩層循環(huán),通常在外循環(huán)中計算全梯度,而在內(nèi)循環(huán)中計算方差縮減的隨機梯度,在迭代過程中需要隨機選取下標it∈{1,…,n}.從總體上看,該算法執(zhí)行最關(guān)鍵步驟是對于隨機梯度的更新,即:
其迭代更新規(guī)則為:
ωt+1=ωt-ηkvt.
可以發(fā)現(xiàn)SVRG算法中迭代方向vt是真實梯度的無偏估計,且算法在迭代過程中的方差在逐漸減小,以下給出SVRG算法的基本框架:
第4步:如果t>m,轉(zhuǎn)第5步;否則轉(zhuǎn)第3步;
第6步:令k:=k+1,如果k>T,停止;否則轉(zhuǎn)第2步.
第3步:如果k>0,計算復合BB步長:
第6步:令k:=k+1,如果k>T,停止;否則轉(zhuǎn)第2步.
本節(jié)將SVRG-CABB算法應用于求解帶有l(wèi)2正則化項的邏輯回歸模型,并給出實驗結(jié)果驗證算法的有效性,模型表示如下:
表1 數(shù)據(jù)集信息
實驗包括四個部分:首先,對比了SVRG-CABB算法與SVRG算法的收斂速度,驗證了SVRG-CABB的有效性;其次,對比了SVRG-CABB算法與SVRG算法的分類準確率;接著,測試了SVRG-CABB算法關(guān)于不同初始步長的步長變化趨勢;最后,對比了SVRG-CABB算法和STSG[20]算法在不同數(shù)據(jù)集上的求解目標函數(shù)時參數(shù)τ對算法性能的影響.所有的實驗結(jié)果如圖1到圖4所示.
圖1 SVRG-CABB和帶有固定步長的SVRG算法殘差對比
圖1對比了SVRG-CABB和SVRG算法的收斂速度,其中x軸代表迭代次數(shù),y軸代表求解目標函數(shù)所得的殘差損失,圖中的虛線和實線分別對應于帶有不同初始步長的SVRG-CABB算法,虛線分別對應于帶有固定步長的SVRG算法.四個子圖(a),(b),(c)和(d)分別對應于兩種算法在數(shù)據(jù)集heart,splice,ijcnn1和a9a上的實驗結(jié)果對比.從圖中可以看出,本文提出的新算法SVRG-CABB收斂速度整體上比帶有固定步長的SVRG算法快,并且當選擇不同的初始步長η0時,SVRG-CABB算法的收斂性能不受影響,可以看出使用CABB步長的優(yōu)勢是使得新算法對于步長的選取更加容易.
圖2 SVRG-CABB和固定步長的SVRG算法分類準確率對比
圖2對比了SVRG-CABB和SVRG算法在不同數(shù)據(jù)集上的求解目標函數(shù)的分類準確率,其中x軸代表迭代次數(shù),y軸代表求解分類準確率,圖中虛線和實線分別對應帶有不同初始步長的SVRG-CABB算法,虛線分別對應帶有固定步長的SVRG算法.四個子圖(a),(b),(c)和(d)分別對應兩種算法在數(shù)據(jù)集heart,splice,ijcnn1和a9a上的實驗對比.從圖中可以看出,本文提出的SVRG-CABB算法的分類準確率明顯高于帶有固定步長的SVRG算法,當選擇不同的初始步長η0時,SVRG-CABB算法的分類準確率并不受影響.在相同條件下,SVRG-CABB算法分類準確率更加穩(wěn)定且明顯高于帶有固定步長的SVRG算法.
圖3 SVRG-CABB步長變化趨勢
圖3測試了SVRG-CABB算法在不同數(shù)據(jù)集上的求解目標函數(shù)時步長的變化趨勢,其中x軸代表迭代次數(shù),y軸代表步長,圖中虛線和實線分別對應不同的初始步長,虛線分別對應不同的固定步長.兩個子圖(a)和(b)分別對應于SVRG-CABB算法在數(shù)據(jù)集heart和splice上的測試結(jié)果.從圖中可以看出,本文提出的SVRG-CABB算法的步長最終收斂于最優(yōu)步長的鄰域.這說明選取不同的初始步長,對算法收斂性能影響不大.
圖4 不同參數(shù)值τ下SVRG-CABB和STSG算法性能對比
圖4對比了SVRG-CABB算法和STSG算法在不同數(shù)據(jù)集上的求解目標函數(shù)時參數(shù)τ對算法性能的影響,其中x軸代表迭代次數(shù),y軸代表殘差損失,圖中的實線分別對應于τ∈(0,1)的SVRG-CABB算法,虛線分別對應于τ∈(0,1)的STSG算法.兩個子圖(a)和(b)分別對應于SVRG-CABB算法在數(shù)據(jù)集heart和a9a上的測試結(jié)果.從圖中可以看出,本文提出的SVRG-CABB和STSG的算法性能雖然均受參數(shù)τ值的影響,并且隨著τ值的增加算法性能總體得到提升,但是SVRG-CABB算法的收斂性能最終優(yōu)于選擇相同參數(shù)τ的STSG算法.
本文將隨機方差縮減梯度算法(SVRG)與改進的復合BB步長(CABB)有機結(jié)合,提出了一種新的SVRG-CABB算法.從實驗結(jié)果分析來看,新算法在求解問題的過程中可以動態(tài)調(diào)節(jié)步長的大小,相比于已有的使用固定步長的SVRG算法以及已有的STSG算法,新算法的收斂速度更快,并且不受初始步長選取的影響.