一種求解稀疏邏輯回歸問題的不精確鄰近擬牛頓算法

楊 婭, 肖 斌, 胡清潔

(1.桂林電子科技大學(xué) 數(shù)學(xué)與計(jì)算科學(xué)學(xué)院,廣西 桂林 541004;2.鄭州商學(xué)院 通識(shí)教育中心,鄭州 451200)

邏輯回歸是一種針對(duì)二分類問題提出來的特殊的非線性回歸模型,主要用于解決分類問題,在醫(yī)學(xué)監(jiān)測、文本分類等領(lǐng)域具有廣泛應(yīng)用。其中稀疏邏輯回歸,也被稱為l1正則化邏輯回歸,是具有稀疏約束的經(jīng)典邏輯回歸模型,在神經(jīng)網(wǎng)絡(luò)[1-2]、深度學(xué)習(xí)[3]和生物信息學(xué)[4]等領(lǐng)域有著廣泛的應(yīng)用。

稀疏邏輯回歸問題的數(shù)學(xué)模型表示為為平均邏輯損失函數(shù);λ‖x‖1為l1正則化函數(shù),λ>0。這個(gè)問題的輸入數(shù)據(jù)是1個(gè)訓(xùn)練數(shù)據(jù)點(diǎn)集(a i,b i)∈Rn×{-1,1},i=1,2,…,N,N>0。由于問題(1)中的l1正則項(xiàng)可以產(chǎn)生稀疏解,從而在高維數(shù)據(jù)處理中占有顯著優(yōu)勢(shì),因此成為近些年來研究的熱點(diǎn)。目前求解稀疏邏輯回歸問題的算法有很多,例如快速迭代收縮閾值算法[5]、快速自適應(yīng)收縮閾值算法[6]、交替方向乘子法[7]、鄰近梯度算法[8]、鄰近擬牛頓算法[8]等。

在利用鄰近擬牛頓法求解問題(1)時(shí),需要計(jì)算鄰近算子[8],但在很多實(shí)際問題中,鄰近算子問題無明顯的解析解,或者有解析解但精確求解時(shí)計(jì)算量很大,所以很多情況下需考慮近似求解鄰近算子。因此,針對(duì)問題(1),提出了求解該問題的不精確加速鄰近擬牛頓算法,并給出相關(guān)收斂速度分析和數(shù)值實(shí)驗(yàn)。

1 不精確加速鄰近擬牛頓算法

首先給出F(x)在點(diǎn)y的復(fù)合二次近似:

為在第k次迭代時(shí)計(jì)算出的不精確鄰近算子的值。

基于Scheinberg等[8]提出的加速鄰近擬牛頓算法,給出如下不精確加速鄰近擬牛頓算法。

算法1 不精確加速鄰近擬牛頓算法

8)k=k+1,轉(zhuǎn)步驟2)。

該算法是文獻(xiàn)[8]中算法5的一個(gè)不精確形式,在步驟3)計(jì)算鄰近算子時(shí)引入不精確項(xiàng)εk。

2 算法的有關(guān)性質(zhì)

為了分析不精確鄰近擬牛頓算法的收斂速度,給出該算法的4個(gè)引理。首先給如下假設(shè)。

假設(shè)1:

1)f:Rn→R是光滑凸函數(shù)且梯度Lipschitz連續(xù),其Lipschitz常數(shù)為L。

2)問題(1)是可解的,即存在x*∈Rn是F的最小值點(diǎn)。

3)對(duì)算法中矩陣序列{H k},假設(shè)存在正數(shù)m、M,對(duì)任意的k>0,有

該引理類似于文獻(xiàn)[13]中的Remark27。

引理2[13]若f滿足假設(shè)1,ε≥0,且

將式(2)與式(3)相加,可得

則下列不等式成立:

該引理來源于文獻(xiàn)[13]中的引理3.3。

3 算法的收斂性分析

為了證明不精確加速鄰近擬牛頓算法的收斂速度,給出如下假設(shè):

假設(shè)2 給定a≥2,假設(shè)

以下給出不精確加速鄰近擬牛頓算法的收斂速度結(jié)果。

定理1 (收斂性)若假設(shè)1、假設(shè)2、假設(shè)3都成立,且σ0≤σk+1,定義

又由

故定理1得證。

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

為了檢驗(yàn)算法的有效性,將不精確加速鄰近擬牛頓算法(NEWAPQNA)的數(shù)值結(jié)果與精確加速鄰近擬牛頓算法(APQNA)[8]、不精確鄰近擬牛頓算法(NEWPQNA)[8]、精確鄰近擬牛頓算法(PQNA)[8]的數(shù)值結(jié)果進(jìn)行比較。實(shí)驗(yàn)在MATLAB R2014b中運(yùn)行,測試環(huán)境為Window 7 操作系統(tǒng),intel(R)Core(TM)i5-6500 CPU@3.20 GHz,8.0 GiB RAM。

在NEWAPQN 和NEWPQNA 中利用隨機(jī)坐標(biāo)下降算法[8]求解不精確的鄰近算子。經(jīng)過調(diào)試,將最高迭代次數(shù)設(shè)為200次,將算法的終止條件設(shè)為10-8。

令?=0.05,β=0.05,4種算法運(yùn)行結(jié)果如圖1、圖2和表1所示。

表1 算法比較結(jié)果

圖1 4種算法目標(biāo)函數(shù)值相對(duì)誤差變化

圖2 4種算法迭代序列相對(duì)誤差變化圖

從圖1、表1可看出,利用這4種算法求解稀疏邏輯回歸問題所得的目標(biāo)函數(shù)相對(duì)誤差相近,但利用NEWPQNA 求解目標(biāo)函數(shù)所需的迭代次數(shù)最少,效果更好。從圖2可看出,APQNA、NEWPQNA、PQNA求解稀疏邏輯回歸問題所得的絕對(duì)誤差相近,但利用NEWPQNA相對(duì)誤差稍優(yōu)于其它3種算法,這表明不精確鄰近擬牛頓算法效果更好。

5 結(jié)束語

為了更有效的求解稀疏邏輯回歸問題,通過利用不精確算子,提出了一種不精確鄰近擬牛頓算法,并證明了該算法的收斂速度。該算法改進(jìn)了文獻(xiàn)[8]中的加速鄰近擬牛頓算法。數(shù)值試驗(yàn)結(jié)果表明,該算法對(duì)求解稀疏邏輯回歸問題是有效的。