劉光宇，張令威，杭仁龍

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

1 引言

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

(1)

2 相關(guān)工作

近年來，研究人員提出了很多優(yōu)秀的算法來解決問題(1)[[2]，比如，如果將式中的損失函數(shù)設(shè)置為最小二乘損失函數(shù)，那么它就是壓縮感知領(lǐng)域中一個(gè)十分重要的問題[3]。Joel 等人提出了正交匹配追蹤(OMP)算法[4]，該算法在每次迭代過程中選取和測(cè)量向量相關(guān)性數(shù)值最大的原子，然后重新更新系數(shù)以保證所選原子與殘差是正交的。在OMP算法基礎(chǔ)上，Needell等人提出壓縮采樣匹配追蹤算法(CoSaMP)[5]，論文中借鑒了多種算法思想以保證算法的收斂速度。Thomas等人提出了另外一種具有較好魯棒性特性的算法——迭代硬閾值法(IHT)[6]，該算法在每次迭代過程中只保留具有最大絕對(duì)值的元素，將其它元素設(shè)為0，取得了良好的效果，與此同時(shí)作者也提供了充分的理論來證明該算法的有效性。通過結(jié)合CoSaMP和IHT算法，F(xiàn)oucart提出了硬閾值追蹤法(HTP)[7]，該算法具有更快的收斂速度。上述算法都是壓縮感知領(lǐng)域的經(jīng)典算法，而如果問題(1)的模型是邏輯回歸模型或者圖網(wǎng)絡(luò)模型，那這個(gè)問題就轉(zhuǎn)化成機(jī)器學(xué)習(xí)領(lǐng)域的重要問題。Bahmani等人將梯度信息與參數(shù)信息都進(jìn)行截?cái)嗖僮鳎岢隽颂荻戎С肿粉櫡?GraSP)[8]。上文中提到的IHT算法同樣可以被運(yùn)用到機(jī)器學(xué)習(xí)領(lǐng)域，Yuan等人將IHT算法的思想與梯度下降法結(jié)合，提出了梯度硬閾值追蹤法(GraHTP)[9]?；陔S機(jī)方差縮減梯度法(SVRG)[10]，Li等人引入了IHT算法思想來解決稀疏約束問題，提出了SVR-GHT算法[11]。通過改變獨(dú)特的采樣方法，Zhou提出混合隨機(jī)梯度硬閾值法[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ù)對(duì)應(yīng)于參數(shù)的二階導(dǎo)數(shù)(即Hessian矩陣)，并將其運(yùn)用到參數(shù)更新過程中去。但是牛頓法很少被運(yùn)用到機(jī)器學(xué)習(xí)中，原因是要求Hessian矩陣必須是半正定，而且Hessian矩陣及其逆矩陣的計(jì)算對(duì)計(jì)算機(jī)的算力要求很高，運(yùn)用到高維或者超高維的數(shù)據(jù)中不是很現(xiàn)實(shí)。例如，要是一個(gè)數(shù)據(jù)的特征維度是d，那么算出的Hessian矩陣維度d×d，如果是高維或者超高維的數(shù)據(jù)，那么其計(jì)算量將會(huì)很大，一般的個(gè)人計(jì)算機(jī)的算力是無法滿足這種要求的。所以本文采用了擬牛頓法的思想，用一階曲率信息來近似二階信息，算法采用L-BFGS算法，該算法可以通過一階信息近似Hessian矩陣，達(dá)到節(jié)省算力的目的。與此同時(shí)，本文采用迭代硬閾值(IHT)算法對(duì)參數(shù)施加稀疏約束。為了敘述方便，本論文將算法簡(jiǎn)稱為SLH算法。

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

3 算法

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

3.1 預(yù)備知識(shí)

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

wp+1=wp-ηpHpvp

(2)

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

3.2 隨機(jī)L-BFGS算法

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

xt+1=xt-ηHvt

(3)

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

(4)

3.3 迭代硬閾值法(IHT)

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

(5)

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

3.4 SLH算法

受文獻(xiàn)[11]中算法啟發(fā)，本文將硬閾值截?cái)嗖僮鞣旁趦?nèi)循環(huán)之后，具體算法流程如下SLH算法偽代碼所示。

SLH算法

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

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

2)Forp=0，…，n-1

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

4)Fort=0，…，m-1

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

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

7) 計(jì)算方差衰減梯度：

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

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

9) 執(zhí)行截?cái)嗖僮鳎害聇+1=HTk(βt+0.5)

Endfor

10)wp+1=βm

EndFor

輸出：wn

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

依據(jù)文獻(xiàn)[14]，在不執(zhí)行截?cái)嗖僮鲿r(shí)，即不執(zhí)行步驟9時(shí)，上述算法符合單調(diào)遞減的性質(zhì)。但是需要符合兩個(gè)假設(shè)：

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

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

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

(6)

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

本算法在計(jì)算Hp時(shí)會(huì)花費(fèi)大量的資源，因?yàn)樗惴ㄔ谛枰鎯?chǔ)必要的曲率信息，即每次更新的參數(shù)值以及參數(shù)的梯度值，同時(shí)構(gòu)造Hessian矩陣近似值也需要花費(fèi)資源。所以，適當(dāng)減少Hp的計(jì)算頻率或者適當(dāng)選取M都可以減少算法的資源消耗量。

4 實(shí)驗(yàn)

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

4.1 實(shí)驗(yàn)?zāi)Ｐ?/h3>

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

4.1.1 線性回歸模型

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

y=wTx+e

(7)

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

(8)

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

4.1.2 邏輯回歸模型

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

(9)

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

(10)

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

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

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

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

4.3 對(duì)比算法

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

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

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

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

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

圖1 線性回歸模型實(shí)驗(yàn)結(jié)果圖

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

4.4 實(shí)驗(yàn)結(jié)果

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

4.4.1 線性回歸模型

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

4.4.2 邏輯回歸模型

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

圖2 邏輯回歸模型實(shí)驗(yàn)結(jié)果圖

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

5 結(jié)論

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