基于隨機L-BFGS的二階非凸稀疏優(yōu)化算法

劉光宇，張令威，杭仁龍

(南京信息工程大學(xué)江蘇省大數(shù)據(jù)分析技術(shù)重點實驗室，江蘇 南京 210044)

1 引言

近年來隨著科學(xué)技術(shù)的發(fā)展與信息開放性的提高，社會中如電子信息、衛(wèi)星遙感和醫(yī)學(xué)成像等領(lǐng)域都隨時隨地地產(chǎn)生著海量的視頻、圖像與文本數(shù)據(jù)。通常情況下，這些數(shù)據(jù)都具有維度過高的特性，其中部分數(shù)據(jù)的維度甚至超過了樣本本身的數(shù)量。但是這些超高維的特征可能只有部分與最后的預(yù)測結(jié)果相關(guān)，所以如何挖掘到這些有用的特征成為了機器學(xué)習(xí)領(lǐng)域一項十分重要的研究內(nèi)容，同時也是稀疏學(xué)習(xí)中最重要的研究課題之一[2]。在以往的稀疏學(xué)習(xí)任務(wù)中，通常需要通過施加l0約束來實現(xiàn)模型參數(shù)的稀疏化。一般來說，一個高效且魯棒的稀疏模型對稀疏問題的解決有很大的幫助。以下是一個稀疏化模型的通用形式

(1)

2 相關(guān)工作

近年來，研究人員提出了很多優(yōu)秀的算法來解決問題(1)[[2]，比如，如果將式中的損失函數(shù)設(shè)置為最小二乘損失函數(shù)，那么它就是壓縮感知領(lǐng)域中一個十分重要的問題[3]。Joel 等人提出了正交匹配追蹤(OMP)算法[4]，該算法在每次迭代過程中選取和測量向量相關(guān)性數(shù)值最大的原子，然后重新更新系數(shù)以保證所選原子與殘差是正交的。在OMP算法基礎(chǔ)上，Needell等人提出壓縮采樣匹配追蹤算法(CoSaMP)[5]，論文中借鑒了多種算法思想以保證算法的收斂速度。Thomas等人提出了另外一種具有較好魯棒性特性的算法——迭代硬閾值法(IHT)[6]，該算法在每次迭代過程中只保留具有最大絕對值的元素，將其它元素設(shè)為0，取得了良好的效果，與此同時作者也提供了充分的理論來證明該算法的有效性。通過結(jié)合CoSaMP和IHT算法，F(xiàn)oucart提出了硬閾值追蹤法(HTP)[7]，該算法具有更快的收斂速度。上述算法都是壓縮感知領(lǐng)域的經(jīng)典算法，而如果問題(1)的模型是邏輯回歸模型或者圖網(wǎng)絡(luò)模型，那這個問題就轉(zhuǎn)化成機器學(xué)習(xí)領(lǐng)域的重要問題。Bahmani等人將梯度信息與參數(shù)信息都進行截斷操作，提出了梯度支持追蹤法(GraSP)[8]。上文中提到的IHT算法同樣可以被運用到機器學(xué)習(xí)領(lǐng)域，Yuan等人將IHT算法的思想與梯度下降法結(jié)合，提出了梯度硬閾值追蹤法(GraHTP)[9]。基于隨機方差縮減梯度法(SVRG)[10]，Li等人引入了IHT算法思想來解決稀疏約束問題，提出了SVR-GHT算法[11]。通過改變獨特的采樣方法，Zhou提出混合隨機梯度硬閾值法[12]。除一階優(yōu)化算法外，基于二階稀疏優(yōu)化的算法也引起了學(xué)業(yè)界的關(guān)注[13]。

本文算法受Philipp等人Stochastic L-BFGS[14]算法以及Rite Kolte工作[15]的啟發(fā)，通過在參數(shù)更新的過程中引入二階信息的方式提升模型的性能。二階優(yōu)化算法與一階優(yōu)化算法相比，可以取得更快的收斂速度。傳統(tǒng)的二階優(yōu)化算法是牛頓法[16]，在參數(shù)更新過程中算出損失函數(shù)對應(yīng)于參數(shù)的二階導(dǎo)數(shù)(即Hessian矩陣)，并將其運用到參數(shù)更新過程中去。但是牛頓法很少被運用到機器學(xué)習(xí)中，原因是要求Hessian矩陣必須是半正定，而且Hessian矩陣及其逆矩陣的計算對計算機的算力要求很高，運用到高維或者超高維的數(shù)據(jù)中不是很現(xiàn)實。例如，要是一個數(shù)據(jù)的特征維度是d，那么算出的Hessian矩陣維度d×d，如果是高維或者超高維的數(shù)據(jù)，那么其計算量將會很大，一般的個人計算機的算力是無法滿足這種要求的。所以本文采用了擬牛頓法的思想，用一階曲率信息來近似二階信息，算法采用L-BFGS算法，該算法可以通過一階信息近似Hessian矩陣，達到節(jié)省算力的目的。與此同時，本文采用迭代硬閾值(IHT)算法對參數(shù)施加稀疏約束。為了敘述方便，本論文將算法簡稱為SLH算法。

本篇論文的主要貢獻有以下幾點：①本文提出了一種新的用于稀疏約束的算法，該算法與一些經(jīng)典的稀疏優(yōu)化算法相比，有更快的收斂速度與準(zhǔn)確度； ②該算法將二階信息利用到參數(shù)更新的過程中去，所以有更快的收斂速度。與傳統(tǒng)的牛頓法相比，本算法不需要計算Hessian矩陣及其逆矩陣，大大節(jié)省了模型的運算量； ③本文算法具有良好的泛化性，可以運用到很多經(jīng)典的機器學(xué)習(xí)模型上，取得了良好的效果。

3 算法

在本節(jié)中，將首先簡要介紹優(yōu)化算法的一些知識，然后介紹隨機 L-BFGS算法與IHT算法。本文將IHT運用在隨機L-BFGS算法中來保證稀疏約束條件，提出了新的SLH算法，獲得了更好的模型性能。

3.1 預(yù)備知識

對于一般的優(yōu)化算法，將會使用如下的通用的參數(shù)更新規(guī)則

wp+1=wp-ηpHpvp

(2)

若使用的是以牛頓法為代表的二階優(yōu)化算法，式(2)中的Hp就是Hessian矩陣的逆矩陣[17]。但是由于Hessian矩陣的計算復(fù)雜度過大，常常用一階曲率信息來近似Hessian矩陣[18]-[20]。本文采用的是L-BFGS算法[19]，該算法會在下面的算法介紹中具體提到。

3.2 隨機L-BFGS算法

Stochastic L-BFGS[14]算法是SVRG算法和L-BFGS算法的結(jié)合，該算法被證明在強凸性和光滑的損失函數(shù)上可以達到線性收斂的速度。算法的參數(shù)更新規(guī)則如下

xt+1=xt-ηHvt

(3)

其中vt的獲取是通過SVRG算法得到的。

(4)

3.3 迭代硬閾值法(IHT)

迭代硬閾值法[6]是一種用于壓縮感知重構(gòu)恢復(fù)的算法，該算法是一種迭代算法，在每次迭代過程中，取向量初始值β0=0，迭代公式如下：

(5)

其中case1 指的是如果|βn，i|屬于前k個數(shù)值上最大的元素。

3.4 SLH算法

受文獻[11]中算法啟發(fā)，本文將硬閾值截斷操作放在內(nèi)循環(huán)之后，具體算法流程如下SLH算法偽代碼所示。

SLH算法

輸入：初始化參數(shù)w0；參數(shù)m，n；批量樣本個數(shù)b；步長η；稀疏化參數(shù)k

1) 初始化：H0=I，p=0，t=0

2)Forp=0，…，n-1

3) 計算全局梯度：μp=?f(wp)，依據(jù)(4)式計算Hp，β0=wp

4)Fort=0，…，m-1

5) 樣本采樣：Sp，t={1，2，…，b}

6) 計算采樣樣本梯度：?fSp，t(βt)

7) 計算方差衰減梯度：

vt=?fSp，t(βt)-?fSp，t(wp)+μp

8) 參數(shù)更新：βt+0.5=βt-ηHpvt

9) 執(zhí)行截斷操作：βt+1=HTk(βt+0.5)

Endfor

10)wp+1=βm

EndFor

輸出：wn

本算法與文獻[11]算法最大的不同就是在參數(shù)過程中引入了擬牛頓項，也就是引入了二階信息，由于二階信息較一階信息而言搜索范圍更加廣泛，所以這種操作可以有效地加速算法的收斂速度。相較于一般的牛頓算法，該算法不需要直接計算Hessian矩陣及其逆矩陣，只需用到一階曲率信息，所以計算量大大減少，收斂速度也大大加快。

依據(jù)文獻[14]，在不執(zhí)行截斷操作時，即不執(zhí)行步驟9時，上述算法符合單調(diào)遞減的性質(zhì)。但是需要符合兩個假設(shè)：

假設(shè)1：損失函數(shù)fi是凸函數(shù)且符合二階可微條件；

假設(shè)2：存在兩個常量λ和Λ，滿足以下條件

λI≤?2fτ(w)≤ΛI，

(6)

如果符合上述兩個假設(shè)，當(dāng)m和η滿足：γλ>1/2mη+2ηΓ2Λ2，上述算法是單調(diào)遞減的，其中γ=1/(d+M)Λ，M為Stochastic L-BFGS算法關(guān)于曲率存儲量的參數(shù)，由人為設(shè)定，d為所學(xué)習(xí)參數(shù)的維數(shù)，Γ=((d+M)Λ)d+M-1/λd+M。

本算法在計算Hp時會花費大量的資源，因為算法在需要存儲必要的曲率信息，即每次更新的參數(shù)值以及參數(shù)的梯度值，同時構(gòu)造Hessian矩陣近似值也需要花費資源。所以，適當(dāng)減少Hp的計算頻率或者適當(dāng)選取M都可以減少算法的資源消耗量。

4 實驗

本部分主要證明所提出的算法的有效性，本文算法被運用到線性回歸模型(Linear Regression)和邏輯回歸模型(Logistic Regression)中，所用的數(shù)據(jù)集是RCV 1數(shù)據(jù)集以及20Newsgroup數(shù)據(jù)集，算法實驗環(huán)境為四核的2.60 GHz的CPU和8GB的RAM，使用MATLAB R2015a平臺對算法進行了編程實現(xiàn)。

4.1 實驗?zāi)Ｐ?/h3>

如上文所說，本文將提出的算法運用于線性回歸模型以及邏輯回歸模型。

4.1.1 線性回歸模型

線性回歸模型是機器學(xué)習(xí)領(lǐng)域中十分常見的一種模型，其表達方式如下所示

y=wTx+e

(7)

式中w是需要學(xué)習(xí)的參數(shù)，(x，y) 分別為監(jiān)督學(xué)習(xí)數(shù)據(jù)以及標(biāo)簽，e是服從0均值正態(tài)分布的誤差項。為學(xué)習(xí)上述模型，最常使用的方法是最小二乘法，其損失函數(shù)的形式如下

(8)

上式中n是總樣本個數(shù)，λ是正則化系數(shù)。

4.1.2 邏輯回歸模型

邏輯回歸是機器學(xué)習(xí)領(lǐng)域十分常見的分類器，該分類模型是一種廣義的線性分析模型，常用于數(shù)據(jù)挖掘等領(lǐng)域，該分類器常常運用于做二分類問題，即該機器學(xué)習(xí)任務(wù)的標(biāo)簽只有兩個值。邏輯回歸損失函數(shù)可以表示為：

(9)

式中，w是需要學(xué)習(xí)的線性模型的參數(shù)，yi∈{-1，1}是學(xué)習(xí)任務(wù)中的二值化標(biāo)簽，xi∈d是訓(xùn)練集數(shù)據(jù)中d維的特征向量。在一般的機器學(xué)習(xí)任務(wù)中，常常在邏輯回歸的損失函數(shù)后面加入l2正則化項，這么做的好處是可以有效減少過擬合的問題：

(10)

式中λ>0表示的是正則化參數(shù)，可以由人工設(shè)定，表征對參數(shù)的懲罰程度。

4.2 數(shù)據(jù)集

在本實驗中，用了兩個不同的數(shù)據(jù)集。其中RCV1數(shù)據(jù)集包含路由社(Reuters)英文文本以及對應(yīng)類別的數(shù)據(jù)[21]，該數(shù)據(jù)既可以應(yīng)用于文本分類和自然語言處理的任務(wù)，數(shù)據(jù)集中共有20242個訓(xùn)練數(shù)據(jù)以及677399個訓(xùn)練數(shù)據(jù)，每個數(shù)據(jù)共有47236個特征。在本文的實驗中選用所有的20242個訓(xùn)練樣本，并且選用20000個測試樣本。

20Newsgroup數(shù)據(jù)集[22]是由大約20000個不同的新聞文件組成的數(shù)據(jù)集，該數(shù)據(jù)集有10000個訓(xùn)練樣本和9996個測試樣本，每個樣本含有1355191個特征。

4.3 對比算法

以下是本文采用的四種一階優(yōu)化對比實驗算法。

FCFGS：FCFGS[24]算法是一種正向貪婪選擇算法，該算法依據(jù)梯度信息來進行稀疏化操作。

GraSP：GraSP[8]算法是一種迭代貪婪算法，該算法在做稀疏化操作時同時考慮梯度以及參數(shù)大小。

GraHTP：GraHTP[9]算法在標(biāo)準(zhǔn)梯度下降法的基礎(chǔ)上加入迭代硬閾值算法的思想，從而滿足了稀疏化約束。

FoBa：FoBa[24]算法在正向傳播的基礎(chǔ)上加入自適應(yīng)反向傳播，加快了算法收斂速度。

圖1 線性回歸模型實驗結(jié)果圖

本文選取的算法均屬于一階稀疏優(yōu)化算法，通過與上述的一階稀疏優(yōu)化算法對比，可以發(fā)現(xiàn)二階優(yōu)化算法在稀疏優(yōu)化學(xué)習(xí)中的性能更優(yōu)越。本文算法(簡稱SLH)就算法運行時間(CPU Time)以及算法分類準(zhǔn)確度(Classification Error)對各種算法進行了實驗比較。

4.4 實驗結(jié)果

本節(jié)將展示SLH算法與各類對比算法在線性回歸模型以及邏輯回歸模型上面應(yīng)用的結(jié)果。

4.4.1 線性回歸模型

本小節(jié)將展示各類算法在線性回歸任務(wù)中的實驗結(jié)果。實驗采用RCV1數(shù)據(jù)集，實驗中所有的正則化參數(shù)λ均取值10-5，稀疏度k∈[100：100：1000]，實驗結(jié)果如下圖1所示，可以看出在算法收斂方面，本文提出的算法(SLH)略優(yōu)于FCFGS算法，在算法準(zhǔn)確度方面，與GraSP算法實驗結(jié)果相當(dāng)。綜上所述，在同時考慮準(zhǔn)確度與效率的情況下，本算法性能優(yōu)于其它算法。

4.4.2 邏輯回歸模型

本小節(jié)將展示各類算法在邏輯回歸任務(wù)上的實驗結(jié)果，實驗分別采用了RCV1與20Newsgroup兩個數(shù)據(jù)集，實驗中正則化參數(shù)λ均取值10-5，稀疏度在RCV1數(shù)據(jù)集上k∈[100：100：1000]，在20Newsgroup數(shù)據(jù)集上，本文分別采用了四種不同的稀疏度：k∈{1000，2000，5000，10000}。在RCV1數(shù)據(jù)集上運行的結(jié)果如圖2所示，可以看出，在算法效率方面，本算法優(yōu)于其它所有算法，在算法準(zhǔn)確度方面，本算法結(jié)果與GraHTP以及GraSP算法相當(dāng)，綜上所述，本算法在邏輯回歸分類任務(wù)中的性能優(yōu)于其它算法。在20Newsgroup數(shù)據(jù)集上，本實驗記錄分類結(jié)果以及得出該結(jié)果所用的時間，(括號內(nèi)是時間標(biāo)準(zhǔn)差)。實驗結(jié)果如表1所示，其中加粗的部分是最好的實驗結(jié)果。可以看出，GraSP可以得出最好的分類結(jié)果，但是耗時很長。而SLH算法可以在很短的時間內(nèi)便能取得僅略遜于GraSP算法的結(jié)果，所以綜合而言本算法性能仍優(yōu)于其它對比算法。

圖2 邏輯回歸模型實驗結(jié)果圖

表1 邏輯回歸在20Newsgroup數(shù)據(jù)集回歸結(jié)果

5 結(jié)論

本文提出了一種用于解決l0稀疏約束問題的優(yōu)化算法(SLH)，算法的主要思想是在隨機LBFGS算法中引入迭代硬閾值(IHT)操作，從而將二階擬牛頓算法運用到稀疏學(xué)習(xí)領(lǐng)域中，在具有二階優(yōu)化算法優(yōu)勢的同時避免了直接求取Hessian矩陣，有效的提升了模型效率。在本文中算法被運用到線性回歸任務(wù)以及邏輯回歸任務(wù)，實驗結(jié)果表明SLH算法可以在保證模型高性能的前提下更快收斂，較傳統(tǒng)一階算法擁有更高的效率，可以投入更廣泛的應(yīng)用。