求解邏輯回歸問題的多層鄰近擬牛頓算法

肖 斌， 周芷娟， 胡清潔

(桂林電子科技大學(xué) 數(shù)學(xué)與計算科學(xué)學(xué)院，廣西 桂林 541004)

邏輯回歸是一種廣義的線性回歸分析模型，主要用于求解二分類問題，而l1正則化邏輯回歸是具有稀疏約束的經(jīng)典邏輯回歸模型。l1正則化邏輯回歸模型通常表示為光滑凸函數(shù)與非光滑凸函數(shù)的和。邏輯回歸問題的數(shù)學(xué)模型可表示為

(1)

其中：

為平均邏輯損失函數(shù)；λ‖x‖1為l1正則化函數(shù)，λ>0。該問題的輸入數(shù)據(jù)是一個訓(xùn)練數(shù)據(jù)點集(ai,bi)∈Rn×{-1,1},i=1,2,…,N,ai為特征向量，bi為對應(yīng)的標簽，N>0。由于問題(1)中的l1正則項可以產(chǎn)生稀疏解，從而在高維數(shù)據(jù)處理中占有顯著優(yōu)勢，成為近年來研究的熱點。

邏輯回歸問題在深度學(xué)習(xí)[1]、生物信息學(xué)[2]和神經(jīng)網(wǎng)絡(luò)[3]等方面有廣泛的應(yīng)用，因此研究該問題具有很好的實際意義。目前求解邏輯回歸問題的算法有很多，如快速迭代收縮閾值算法[4]、鄰近擬牛頓算法[5]、交替方向乘子法[6]、隨機坐標下降算法[7]等,其中鄰近擬牛頓算法是求解復(fù)合凸優(yōu)化問題的一類重要方法。Becker等[8]利用對偶問題的分段線性性質(zhì)近似計算鄰近算子，并將該算法應(yīng)用在信號處理、稀疏恢復(fù)、機器學(xué)習(xí)和數(shù)據(jù)分類等方面。文獻[9]提出一種鄰近擬牛頓算法，其中Hessian矩陣采用一種特殊的取法,該算法所提出的結(jié)構(gòu)能夠有效計算鄰近算子，并應(yīng)用于正則化最小二乘問題。Zhong等[10]證明了即使在無強凸性的假設(shè)條件下，非精確鄰近擬牛頓算法也超線性收斂。在相關(guān)數(shù)值實驗中，該算法在序列標記和層次分類問題上的收斂速度比目前現(xiàn)有的算法要快得多。文獻[11]提出一種非精確鄰近擬牛頓算法，并建立了次線性全局收斂速度，在目標函數(shù)為強凸的情況下，分析了該算法在精確和非精確情況下的收斂性。文獻[12]對非精確連續(xù)二次逼近算法的迭代復(fù)雜度進行了全局分析，結(jié)果表明，在一定的精度條件下，非精確解足以保證收斂速度與精確解相同。

多層優(yōu)化算法在近年來有許多發(fā)展和應(yīng)用[13-14]。多層算法起源于偏微分方程數(shù)值解中的多重網(wǎng)格算法，它使用低維(不一定是二次)模型的解來計算搜索方向，因低維模型不但是原模型的低保真度模型，而且其構(gòu)造方式與高保真模型一致，其共同點都是求解一個低保真度模型，然后將其解作為高保真度模型的初始點。對于大規(guī)模問題，Parpas等[13]提出一種多層鄰近梯度算法來求解復(fù)合優(yōu)化問題，并給出該算法的收斂性和收斂速度分析。Nash等[15]利用子問題之間的相似結(jié)構(gòu)，使用較小子問題的解決方案來加速更大、更精細的子問題，進一步發(fā)展了一類多重網(wǎng)格算法，即多重網(wǎng)格加速非線性規(guī)劃算法。文獻[16]提出一種求解一般無約束無限維優(yōu)化問題離散化解的多網(wǎng)格線性搜索算法，在每層的每次迭代中，計算當前層上的直接搜索方向，或從較粗糙層模型中計算遞歸搜索方向。Braess等[17]提出一種求解無限維凸優(yōu)化問題的多層算法，隨后由Nash再進一步發(fā)展。

鑒于此，針對問題(1)，基于多層優(yōu)化思想和鄰近擬牛頓算法，提出了一種求解該問題的多層鄰近擬牛頓算法，并給出相應(yīng)的數(shù)值實驗。數(shù)值實驗結(jié)果表明，該算法在求解邏輯回歸問題時是有效的。

1 多層鄰近擬牛頓算法

針對問題(1)，作如下2個假設(shè)：

1)問題(1)是可求解的，即存在x*∈Rn是最小值點。

2)對矩陣Hk，假設(shè)存在正數(shù)m、M和x*∈Rn，對任意的k>0，有

mIHkMI

成立。

針對問題(1)，考慮在點y處的二階近似

QHk(u,y)=f(y)+〈f(y),u-y〉+

定義

定義鄰近擬牛頓算子：

則鄰近擬牛頓算子有以下性質(zhì)[18]：

2)設(shè)?h(x)是h在點x處的次微分，則滿足

3)鄰近擬牛頓算子滿足嚴格非擴張性，即若

則

定義搜索方向：

由性質(zhì)2)，可得

H(H-1g(x)-Δx)∈?h(x+Δx)，

即

HΔx∈g(x)-?h(x+Δx)。

求解復(fù)合凸優(yōu)化問題的多層鄰近擬牛頓(MNewton)算法的具體步驟如下：

算法1MNewton算法

1)選取初始值x0、限制算子R和延拓算子P,ε>0，00，θ∈(0,1),q>0，κ∈(0，min(1,‖R‖))，q>0，Kd>0，令k=1。

2)若不滿足粗糙條件

(2)

則轉(zhuǎn)步驟3)，否則，計算粗糙方向：

dk(xk)=P(xH,NH-Rxk)，

并由Arimijo線搜索求得步長sk，即滿足

Fμ(xk+skdk)≤Fμ(xk)+cskFμ(xk)Tdk。

令yk=xk+skdk，計算

3)計算

其中Hk為黑塞矩陣估計。

4)令xk=pHk(yk)。

5)計算

6)計算相對誤差：

若er<ε，則停止計算，輸出xk，否則，令k=k+1，轉(zhuǎn)步驟2)。

2 算法分析

最小化非光滑問題的一般方法是用一系列光滑問題替換原問題[13]。此方法比用次梯度求解原問題更有效，因此引入一個光滑參數(shù)μ>0，對g(x)進行光滑化，得到gμ(x)。光滑后的目標函數(shù)為

Fμ(x)=f(x)+gμ(x)，

其中，

在該算法中，并未通過使用粗糙層的解直接延拓得到精細層的解，而是通過求解粗糙子問題構(gòu)造精細問題迭代的搜索方向。因此，為了保證算法的收斂性，必須保證粗糙層與精細層的最優(yōu)性條件一致，即在初始點時，通過添加線性項滿足最優(yōu)性條件：

FH(xH)=fH(xH)+gH(xH)+〈vH,xH〉，

其中，

vH=RFμ(x)-(fH(Rx)+gH(Rx))。

為了使信息在精細層與粗糙層之間傳遞，分別采用限制算子R和延拓算子P來實現(xiàn)。其中限制算子將當前精細層點轉(zhuǎn)移到粗糙層，延拓算子將粗糙層信息傳遞到精細層。為了保證算法的收斂性，需滿足條件σP=RT，其中，σ>0，取σ=1。

為了滿足條件

FH(Rx)=RFμ(x)，

采用初始點xH,0=Rxk開始粗糙迭代，通過求解粗糙模型，并構(gòu)造搜索方向

dk(xk)=P(xH,NH-Rxk)，

其中，xH,NH∈RH為執(zhí)行NH次迭代后粗糙模型的近似解。

在求解算法1中子問題時，用隨機坐標下降算法求解模型函數(shù)QHk(y,x)，具體算法如下。

算法2隨機坐標下降算法

1)選取初始點x0，令k=1，L>0，ε>0。

2)令p(x)=xk，對于i=1,2,…,l，隨機選擇j∈{1,2,…,n}，計算

令

xk+1=p(x)+t*ej。

3)計算相對誤差：

若er<ε，則停止計算，輸出xk+1，將其作為近似極小點，否則，轉(zhuǎn)步驟1)。

該算法是文獻[7]中的算法3的具體形式，雖然可能需要更多的坐標下降迭代以實現(xiàn)相同的精度，但它往往是求解子問題最有效的算法之一。

3 數(shù)值實驗

為了驗證算法的有效性，利用提出的MNewton算法求解邏輯回歸問題，并將本算法的數(shù)值結(jié)果與鄰近梯度法[19]、線搜索鄰近梯度法[19]、加速鄰近梯度法[4]、線搜索加速鄰近梯度法[4]求解的數(shù)值結(jié)果進行比較。所有算法在MATLAB R2018b中運行，測試環(huán)境為Windows 10操作系統(tǒng)，Intel?CoreTMi5-6500 M CPU @3.20 GHz，8.00 GiB RAM。求解問題(1)的數(shù)據(jù)集來源于https://www.csie.ntu.edu.tw/～cjlin/libsvmtools/datasets/binary.html。

在求解問題(1)時，將最大迭代次數(shù)設(shè)為200，令N=7 366，n=300，ε=10-6，取初始點x0=zeros(n,1)，算法1中的粗糙子問題采用單調(diào)快速迭代收縮閾值算法[20]，其他算法中的子問題使用閾值算子求解[4]，

Hk=

diag[min{max{2f(xk))jj,10-2},102}]j=1,2,…,n。

5種算法的運行結(jié)果如圖1、2和表1所示。由圖1、2和表1可知，5種算法經(jīng)過相同迭代次數(shù)時，MNewton算法的函數(shù)值和相對誤差下降得更快，且運行時間相近。這表明MNewton算法求解邏輯回歸問題是有效的。

4 結(jié)束語

為了更有效地求解邏輯回歸問題，基于多層優(yōu)化和鄰近擬牛頓算法，利用合適的Hessian矩陣估計，提出一種多層鄰近擬牛頓算法。數(shù)值實驗結(jié)果表明，該算法在求解稀疏邏輯回歸問題時是有效的，但關(guān)于該算法收斂性的理論分析仍有待進一步研究。

圖1 5種算法目標函數(shù)值相對誤差變化

圖2 5種算法迭代序列相對誤差變化

表1 5種算法運行時間和函數(shù)值對比