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

劉光宇，張令威，杭仁龍

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

1 引言

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

(1)

2 相關工作

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

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

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

3 算法

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

3.1 預備知識

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

wp+1=wp-ηpHpvp

(2)

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

3.2 隨機L-BFGS算法

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

xt+1=xt-ηHvt

(3)

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

(4)

3.3 迭代硬閾值法(IHT)

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

(5)

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

3.4 SLH算法

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

SLH算法

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

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

2)Forp=0，…，n-1

3) 計算全局梯度：μp=?f(wp)，依據(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) 參數更新：βt+0.5=βt-ηHpvt

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

Endfor

10)wp+1=βm

EndFor

輸出：wn

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

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

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

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

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

(6)

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

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

4 實驗

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

4.1 實驗模型

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

4.1.1 線性回歸模型

線性回歸模型是機器學習領域中十分常見的一種模型，其表達方式如下所示

y=wTx+e

(7)

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

(8)

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

4.1.2 邏輯回歸模型

邏輯回歸是機器學習領域十分常見的分類器，該分類模型是一種廣義的線性分析模型，常用于數據挖掘等領域，該分類器常常運用于做二分類問題，即該機器學習任務的標簽只有兩個值。邏輯回歸損失函數可以表示為：

(9)

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

(10)

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

4.2 數據集

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

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

4.3 對比算法

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

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

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

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

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

圖1 線性回歸模型實驗結果圖

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

4.4 實驗結果

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

4.4.1 線性回歸模型

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

4.4.2 邏輯回歸模型

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

圖2 邏輯回歸模型實驗結果圖

表1 邏輯回歸在20Newsgroup數據集回歸結果

5 結論

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