稀疏多元邏輯回歸問題優(yōu)化算法研究

雷大江，杜 萌，李智星，吳 渝

(1.重慶郵電大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院，重慶 400065；2.重慶郵電大學(xué) 軟件工程學(xué)院，重慶 400065；3.重慶郵電大學(xué) 網(wǎng)絡(luò)智能研究所，重慶 400065)

0 引 言

邏輯回歸算法(logistic regression, LR)作為一種經(jīng)典的分類算法，被廣泛應(yīng)用于諸如醫(yī)學(xué)檢測、地質(zhì)測量、文本分類等領(lǐng)域。它針對二分類問題被提出，用于估計事件發(fā)生的可能性，例如某用戶購買某商品的可能性，某病人患有某種疾病的可能性等。它是一種線性的分類算法，具有求解速度快、預(yù)測結(jié)果的可解釋性強(qiáng)的特點。同時，由于其實現(xiàn)簡單，在大規(guī)模數(shù)據(jù)的分類學(xué)習(xí)算法中也有不錯的表現(xiàn)，因此，在學(xué)術(shù)界和工業(yè)界都有廣泛的應(yīng)用。然而，直接使用原始邏輯回歸進(jìn)行求解容易產(chǎn)生過擬合現(xiàn)象，更常見的做法是引入正則項。正則化邏輯回歸，尤其是l1正則化邏輯回歸，也稱作稀疏邏輯回歸(sparse logistic regression, SLR)，SLR是近幾年的研究熱點[1-3]。使用正則化模型可以防止過擬合，有著重要的研究意義。此外，由于l1正則可以產(chǎn)生稀疏解，在高維數(shù)據(jù)處理中具有優(yōu)勢。

傳統(tǒng)邏輯回歸無法直接應(yīng)用于多分類問題，通常有2類方法可以將邏輯回歸拓展到多分類：①將k分類問題分解為多個二分類問題并采用one-vs-rest或者one-vs-one的策略進(jìn)行分類[4]；②稱為多元邏輯回歸(multinomial logistic regression, MLR)，它是邏輯回歸模型在多分類問題上的推廣。對于多分類問題來說，類別之間通常是互斥的。因此，使用多元邏輯回歸相較于邏輯回歸通常能得到更高的分類精度[5]。同時，多元邏輯回歸只需要訓(xùn)練一次即可，因此，它也具有較快的運行速度[5]。同理，引入了l1正則項的多元邏輯回歸稱作稀疏多元邏輯回歸(sparse multinomial logistic regression, SMLR)[6], 在繼承了稀疏邏輯回歸稀疏解的同時也較好地處理了多分類問題。SMLR已經(jīng)被廣泛應(yīng)用在圖像中的多類物體識別[7]、高光譜圖像分類[8]、生物信息學(xué)[9]等領(lǐng)域?？梢?，對SMLR問題進(jìn)行求解具有重要的現(xiàn)實意義。B. Krishnapuram等[6]首次提出了采用迭代重加權(quán)最小二乘法(iterative reweighted least squares, IRLS)來求解SMLR問題，但該算法在處理高維數(shù)據(jù)集或者類別數(shù)過多的數(shù)據(jù)集時具有較高的計算復(fù)雜度[10]，且近年來未有學(xué)者針對IRLS算法計算復(fù)雜度高的問題而展開研究。隨著凸優(yōu)化技術(shù)的發(fā)展，近年來也出現(xiàn)了很多新的優(yōu)化算法，這為本文采用多種高級優(yōu)化算法求解SMLR問題提供了更多的選擇。

本文將首先介紹SMLR問題的原始求解算法IRLS[6]，之后介紹幾種近幾年的稀疏優(yōu)化算法，包括以下幾種：①快速迭代軟閾值收縮算法(fast iterative shrinkage-thresholding algorithm, FISTA)[11];②快速自適應(yīng)收縮閾值法(fast adaptive shrinkage/thresholding, FASTA)[12]；③交替方向乘子法(alternating direction method of multipliers, ADMM)[13]，并會對上述幾種優(yōu)化算法進(jìn)行拓展以求解SMLR問題。另外，考慮到SMLR在大規(guī)模場景下的應(yīng)用，本文實現(xiàn)了SMLR問題的分布式求解，提升了算法的適用性。最后，將對各算法的性能進(jìn)行比較，給出如何根據(jù)不同的場景來選擇合適的優(yōu)化算法的一些建議。本文的貢獻(xiàn)如下。

1)提出了3種高效的SMLR問題的優(yōu)化求解算法。

2)針對大規(guī)模數(shù)據(jù)的場景，提出了一種SMLR問題的分布式優(yōu)化算法。

3)對本文提出的幾種SMLR算法進(jìn)行了實驗，總結(jié)了在不同場景下使用SMLR算法的經(jīng)驗。

1 稀疏多元邏輯回歸

稀疏多元邏輯回歸算法基于多元邏輯回歸，并在多元邏輯回歸的基礎(chǔ)上引入了拉普拉斯先驗，使得它能夠自動進(jìn)行特征選擇并識別出最優(yōu)表達(dá)能力的特征子集，這讓稀疏多元邏輯回歸在一定程度上緩解了維度災(zāi)難的問題。因此，它很適合應(yīng)用在多類別及多特征的場景中。下面將對稀疏多元邏輯回歸算法進(jìn)行簡單的回顧。

假設(shè)，數(shù)據(jù)集D={X,Y}包含m個樣本，n個特征，其中，X∈Rm×n，Y∈Rk×m，k為類別數(shù)。Y為One-Hot編碼后的標(biāo)簽矩陣，即每個標(biāo)簽對應(yīng)一個k維向量，該向量中僅有1個元素取值為1，其他元素取值均為0。對于給定一個樣本X(i)∈R1×n和標(biāo)簽Y(i)∈Rk，樣本X(i)屬于類別j的概率可以表示為

(1)

且有

(2)

(1)—(2)式中：W=[w1,w2,…,wk]∈Rn×k；wi∈Rn為稀疏多元邏輯回歸的參數(shù)矩陣。當(dāng)類別數(shù)k=2時，稀疏多元邏輯回歸就退化為經(jīng)典的二分類模型，也即邏輯回歸。

假設(shè)m個樣本獨立生成，則可以使用極大似然估計(maximum likelihood, ML)對模型參數(shù)W進(jìn)行求解，即

(3)

在圖像分類或者需要處理高維數(shù)據(jù)等特定領(lǐng)域中，人們通常期望求得的解具有一定的稀疏性。通常的做法是在損失函數(shù)中引入l1正則項，也等價于為參數(shù)W引入拉普拉斯先驗p(W)。其中，p(W)∝exp(-λ‖W‖1)。此時，(3)式變?yōu)?/p>

L(W)=l(W)+log(p(W))=

(4)

(4)式中，λ>0為正則項超參數(shù)。

極大化對數(shù)似然函數(shù)等價于最小化負(fù)對數(shù)似然函數(shù)(negative log likelihood, NLL)。參數(shù)W的負(fù)對數(shù)似然函數(shù)如(5)式

(5)

將矩陣XW看作新的變量，第i個樣本屬于第j類的概率的對數(shù)可表示為

(6)

那么，所有樣本屬于某一類別的的概率可以由(7)式表示為

(7)

此時，(5)式可以重寫為矩陣形式，有

(8)

且有

L(W)=l(XW)+λ‖W‖1

(9)

(9)式中，L(W)稱為多元邏輯回歸的損失函數(shù)。

求解帶有l(wèi)1正則項的目標(biāo)函數(shù)通常可以得到稀疏解，這意味著參數(shù)W中的大部分元素取值為0，即有助于最小化代價函數(shù)的是參數(shù)中的非零項，這意味著l1正則化項起到了特征選擇的作用。由于(9)式在原點不可微，無法求得解析解，因此，通常采用迭代的方式對稀疏問題進(jìn)行求解，例如IRLS，F(xiàn)ISTA，F(xiàn)ASTA以及ADMM優(yōu)化算法。

2 稀疏多元邏輯回歸求解算法

2.1 迭代重加權(quán)最小二乘法

迭代重加權(quán)最小二乘法最早由D. Rubin等[14]于1983年提出，用于求解魯棒性回歸問題的回歸系數(shù)。其優(yōu)化求解的過程采用了極大似然法，新的解基于舊的解并不斷迭代更新，因此，稱為迭代重加權(quán)算法。而B. Krishnapuram等[6]在2005年提出的SMLR問題的原始求解算法[6]采用了類似的重加權(quán)方式來對參數(shù)進(jìn)行求解，因此，文中將其稱之為IRLS算法，后文中提到的IRLS也指SMLR問題的原始求解算法。

由于(2)式的存在，使得SMLR問題包含了一維冗余參數(shù)。在B. Krishnapuram等提出的求解方法中，IRLS算法的參數(shù)被表示為非冗余形式，也即w∈Rn(k-1)。為了統(tǒng)一符號，在本節(jié)中，l(w)表示為(3)式所示的SMLR問題的對數(shù)似然函數(shù)形式。

IRLS法通過以下方式對參數(shù)w進(jìn)行估計，即

(10)

由于(10)式中包含拉普拉斯先驗，無法直接使用迭代重加權(quán)的方式進(jìn)行求解。B. Krishnapuram等借用邊界優(yōu)化算法的思想，通過引入代理函數(shù)Q，并對代理函數(shù)Q進(jìn)行迭代最大化以達(dá)到優(yōu)化L(w)的目的，那么有

(11)

且有

(12)

由于L(w)為凸函數(shù)，一種獲得代理函數(shù)Q的方法是利用海森矩陣的下界。記B為負(fù)定矩陣且對所有的w都有H(w)≥B。那么，可以找到一個合法的代理函數(shù)，即

(13)

(13)式中，

(14)

(14)式中：符號?稱為克羅內(nèi)克積(Kronecker product)且有1=[1,1,…,1]T。

l(w)的梯度可以表示為

?x(i)

(15)

(16)

(16)式中，

(17)

最大化(17)式中的w有

(18)

(18)式的另一種等價形式為

(19)

(19)式中，

(20)

此時，參數(shù)w就能以迭代的方式進(jìn)行更新。SMLR問題的IRLS求解算法步驟如算法1所示。

算法1：SMLR問題的IRLS求解算法

輸入：

? 初始化參數(shù)：w∈Rn(k-1)

? 最大迭代次數(shù)：Iter

? 正則項參數(shù)：λ

輸出：

? 算法最終的參數(shù)：wk+1

迭代步驟：

1: 初始化計數(shù)器k←0

2: 初始化參數(shù)wk←w

3: 使用公式(19)更新變量w

4: 當(dāng)?shù)街付ù螖?shù)時算法終止，執(zhí)行步驟5。否則，令k←k+1，返回步驟3。

5: 返回更新完成的算法參數(shù)wk+1

2.2 迭代閾值法

2.2.1 迭代軟閾值收縮法

對于等式(5)，ISTA的優(yōu)化目標(biāo)可以寫為

(21)

(21)式中，W∈Rn×k。直接對(21)式進(jìn)行求解并不容易，因此，可以先將其轉(zhuǎn)換為比較容易求解的形式。將l(W)在Wt處做二階泰勒展開，則有

(22)

取海森矩陣Hl(Wt)=I/τ，其中，I∈Rn×n的單位矩陣，變量τ為步長。則

(23)

那么，ISTA的目標(biāo)函數(shù)為

(24)

此時，最小化問題變?yōu)?/p>

(25)

通過簡單的代數(shù)變換，最小化(25)式可以被重寫為以下形式，即

(26)

(26)式忽略了與最小化W無關(guān)的常量。對于最小化問題(26)，可以快速的進(jìn)行求解。記

W′t=Wt-τl(Wt)

(27)

則(26)式的解可以表示為Sλτ(W′t)。其中，軟閾值操作Sλ:Rn→Rn被定義為

(28)

(28)式中，下標(biāo)i表示逐元素執(zhí)行軟閾值操作。

步長通?？梢匀」潭ㄖ郸?1/L，其中，L為利普希茨常數(shù)(Lipschitz constant)。但使用固定步長的一個缺點是利普希茨常數(shù)L不總是已知的，在大規(guī)模問題下其值也不易計算[11]。因此，A. Beck等給出了一個簡單的線性搜索策略，步長τ的取值可以通過線性搜索(line search)的方式確定。SMLR問題的回溯ISTA算法的迭代步驟如算法2所示。

算法2：SMLR問題的回溯ISTA算法

輸入：

? 初始化步長：τ=1/L，L>0

? 初始化參數(shù)：W∈Rn×k

? 最大迭代次數(shù)：Iter

? 回溯參數(shù)：β∈(0,1)

輸出：

? 算法最終的參數(shù)：Wt+1

迭代步驟：

1: 初始化計數(shù)器t←0

2: 初始化參數(shù)Wt←W

3:Wt+1=pτ(Wt)

4:τ=βτ

6: 返回更新完成的算法參數(shù)Wt+1

2.2.2 快速迭代軟閾值收縮法

FISTA通常被稱為快速近端梯度法(fast proximal gradient method, FPGM)。它是一種應(yīng)用廣泛的快速一階訓(xùn)練方法[11]。通過使用Nesterov加速策略對原始ISTA算法進(jìn)行加速，能夠?qū)STA算法在最壞情況的收斂率由O(1/T)優(yōu)化為O(1/T2)，其中，T為迭代次數(shù)。

ISTA算法使用I/τ來近似估計海森矩陣，而FISTA算法則利用了梯度l(Wt)的最小利普希茨常數(shù)來近似估計海森矩陣。FISTA與ISTA的另一個區(qū)別在于，F(xiàn)ISTA在最小化(26)式時并不是只使用了Wt，而是使用了前2次參數(shù){Wt-1,Wt}的線性組合?；谕瑯拥脑?，F(xiàn)ISTA也給出了帶有回溯的版本。SMLR問題的回溯FISTA算法迭代步驟如算法3所示。

算法3：SMLR問題的回溯FISTA算法

輸入：

? 初始化步長：τ=1/L，L>0

? 初始化參數(shù)：W∈Rn×k

? 最大迭代次數(shù)：Iter

? 回溯參數(shù)：β∈(0,1)

輸出：

? 算法最終的參數(shù)：Wt+1

迭代步驟：

1: 初始化計數(shù)器t←0

2: 初始化參數(shù)Wt←W

3:Wt+1=pτ(Wt)

4:τ=βτ

6: 返回更新完成的算法參數(shù)Wt+1

2.3 快速自適應(yīng)收縮閾值法

快速自適應(yīng)收縮閾值法[12]是T. Goldstein等提出的一種快速優(yōu)化算法，它對ISTA算法做了進(jìn)一步的優(yōu)化。由于梯度的優(yōu)化算法通常對步長變化較敏感，F(xiàn)ASTA采用了自適應(yīng)步長的策略來自動調(diào)整步長大小。另外，它還使用了非單調(diào)的回溯線性搜索策略和混合的停止準(zhǔn)則來進(jìn)一步提高算法的收斂性。

2.3.1 自適應(yīng)步長

FASTA算法采用了自適應(yīng)的步長選擇策略，可以通過實時的自動調(diào)整步長來實現(xiàn)快速收斂。它使用了譜方法(Barzilai-borwein, BB)[15]來自動選擇步長τ=1/a，其中，a滿足下面的條件

a(Wt+1-Wt)≈l(Wt+1)-l(Wt)

(29)

令△Wt+1=Wt+1-Wt，△gt+1=l(Wt+1)-l(Wt)，那么有下述最小化問題：

(30)

(31)

求解最小化問題(30)和(31)，并取τt+1=1/a，那么每一次迭代的步長大小為

(32)

(33)

最終的步長更新規(guī)則為

(34)

2.3.2 回溯線性搜索

在ISTA中，其回溯線性搜索的策略要求在每一次迭代中目標(biāo)函數(shù)都要有充分的下降。但對于譜方法來說，即使是凸問題也不能保證收斂[16]。因此，在FASTA中采用了非單調(diào)的回溯線性搜索策略，該策略允許目標(biāo)函數(shù)在有限的迭代次數(shù)內(nèi)增加，而不是每一次迭代中都要求目標(biāo)函數(shù)嚴(yán)格下降。其策略如下。

定義M>0為線性搜索的參數(shù)，且有

(35)

非單調(diào)的回溯線性搜索策略在每一次迭代中檢查以下條件

(36)

當(dāng)在迭代中違反了(36)式中的條件時，F(xiàn)ASTA算法將會減小步長，直到條件滿足。

2.3.3 停止準(zhǔn)則

FASTA算法采用了基于殘差的停止準(zhǔn)則，其定義為

(37)

(37)式中，W′t+1由(27)式所定義。殘差度量了目標(biāo)函數(shù)l的梯度與l1正則項的負(fù)次梯度的差異?；?37)式，F(xiàn)ASTA算法定義了2種縮放不變型殘差，一種是相對殘差(relative residual)，定義為

(38)

(38)式中，εr為取值較小正常數(shù)。

另一種是歸一化殘差(normalized residual)，定義為

(39)

(39)式中，εn為取值較小正常數(shù)。

算法4：SMLR問題的FASTA求解算法

輸入：

? 初始化步長：τ

? 初始化參數(shù)：W∈Rn×k

? 最大迭代次數(shù)：Iter

? 回溯線性搜索變量：M,β∈(0,1)

? 初始化收斂閾值：εr>0,εn>0

輸出：

? 算法最終的參數(shù)：Wt+1

迭代步驟：

1: 初始化計數(shù)器t←0

2: 初始化變量Wt←W

3:Wt+1=pτ(Wt)

4:τ=βτ

5: 當(dāng)滿足條件(36)時，執(zhí)行步驟6。否則執(zhí)行步驟3。

6: 使用公式(34)更新步長

8: 返回更新完成的算法參數(shù)Wt+1

2.4 交替方向乘子法

2.4.1 串行SMLR求解算法

原始ADMM算法最早由D. Gabay等在70年代中期提出，主要用來解決一般形式的凸優(yōu)化問題[17]。由于其簡單性和可擴(kuò)展性，S. Boyd等在2011年將其拓展到分布式機(jī)器學(xué)習(xí)領(lǐng)域。ADMM算法整合了對偶上升法(dual ascent)的可分解性和增廣拉格朗日乘子法(augmented lagrangians and the method of multipliers)優(yōu)秀的收斂性質(zhì)[13]，可以看作是在對偶上升法和增廣拉格朗日乘子法基礎(chǔ)上發(fā)展出的新算法。

采用ADMM求解SMLR問題時，主要考慮以下形式的凸優(yōu)化問題，即

s.t.W-Z=0

(40)

(40)式中，W∈Rn×k和Z∈Rn×k為需要優(yōu)化的變量。采用增廣拉格朗日法來求解最小化問題(40)，則其增廣拉格朗日函數(shù)可以表示為

Lρ(W,Z,Y)=l(XW)+g(Z)+

(41)

(41)式中，l(XW)為(8)式所示的負(fù)對數(shù)似然函數(shù)，g(Z)=λ‖Z‖1為l1正則項。變量Y為對偶變量，ρ>0為懲罰參數(shù)。對于(41)式，ADMM的變量迭代更新公式為

(42)

(43)

Yk+1∶=Yk+ρ(Wk+1-Zk+1)

(44)

通過縮放(41)式中的對偶變量Y并合并后2項，可以將其寫為更緊湊的形式為

(45)

(45)式中，U=Y/ρ。此時，ADMM的變量迭代更新公式為

(46)

(47)

Uk+1∶=Uk+Wk+1-Zk+1

(48)

由于ADMM具有可分解性，因此，通過將目標(biāo)函數(shù)分解為l(XW)和g(Z)2項，迭代地對2個變量W和Z進(jìn)行交替地更新，通過(40)式中的約束項保證2個變量趨于一致，直到收斂到最優(yōu)解。ADMM算法通過使用原始?xì)埐顁k+1和對偶?xì)埐顂k+1來確定ADMM算法的收斂情況[13]，2類殘差分別定義為

rk+1=Wk+1-Zk+1,sk+1=ρ(Zk+1-Zk)

(49)

在ADMM算法的迭代過程中，(40)式中的線性約束逐漸滿足，因此，原始?xì)埐钪饾u趨于零。同時，目標(biāo)函數(shù)接近最小值，即對偶?xì)埐钰呌诹?。一種較合理的檢測收斂性的方法是原始?xì)埐詈蛯ε細(xì)埐畋仨毢苄?，迭代可以在以下情況下終止，即

(‖rk‖2≤ε); (‖sk‖2≤ε)

(50)

(50)式中，ε>0是控制收斂精度的參數(shù)。SMLR問題的ADMM求解算法的主要迭代步驟如算法5所示。

算法5：SMLR問題的ADMM求解算法

輸入：

? 訓(xùn)練集：D={X,Y}

? 初始化參數(shù)：W,Z,U

? 最大迭代次數(shù)：Iter

? 收斂閾值：ε=10-4>0

? 超參數(shù)：λ，ρ

輸出：

? 算法最終的參數(shù)：Zk+1

迭代步驟：

1: 初始化計數(shù)器k←0

2: 初始化變量Wk←W,Zk←Z,Uk←U

5:Uk+1∶=Uk+Wk+1-Zk+1

6:rk+1←Wk+1-Zk+1

7:sk+1←ρ(Zk+1-Zk)

8: 當(dāng)滿足‖rk+1‖2<ε且‖sk+1‖2<ε，或迭代到指定次數(shù)時算法終止，執(zhí)行步驟9。否則，令k←k+1，并返回到步驟3。

9: 返回更新完成的算法參數(shù)Zk+1

2.4.2 并行SMLR求解算法

為了獨立地對多個數(shù)據(jù)塊進(jìn)行處理，可以輕易地將(40)式所示的SMLR問題的原始優(yōu)化目標(biāo)寫為(51)式的形式從而進(jìn)行分布式優(yōu)化，形式為

s.t.Wi-Z=0,i=1,…,N

(51)

(51)式中，

(52)

第i部分的目標(biāo)函數(shù)li使用來第i個數(shù)據(jù)塊來優(yōu)化局部模型參數(shù)Wi，不同計算結(jié)點優(yōu)化不同的局部變量。通過引入全局變量Z來保證局部變量與全局變量趨于一致。

最小化問題(51)的增廣拉格朗日形式為

(53)

基于樣本劃分的SMLR問題可以采用迭代的方式進(jìn)行求解，其變量迭代公式為

(54)

(55)

(56)

使用原始變量和對偶變量來判定算法的收斂情況，原始變量rk+1和對偶變量sk+1可以表示為

(57)

在(54)—(56)式中，第1步和第3步的計算可以分布在不同的計算結(jié)點。在第2步中，將會對各計算結(jié)點求得的局部變量Wi進(jìn)行聚合并對全局變量Z進(jìn)行更新。Z的更新問題可以看作Lasso問題，可以使用任何一種Lasso求解算法進(jìn)行求解。上述步驟不斷迭代以保證局部變量和全局變量趨于一致。SMLR問題的分布式ADMM求解算法的主要迭代步驟如算法6所示。

算法6：SMLR問題的分布式ADMM求解算法

輸入：

? 經(jīng)分區(qū)后的數(shù)據(jù)集：D={(X1,Y1),…,(XN,YN)}

? 初始化的算法參數(shù)矩陣：W1,…,WN,Z,U1,…,UN

? 最大迭代次數(shù)：Iter

? 收斂閾值:ε=10-4>0

? 超參數(shù)：λ，ρ

輸出：

? 算法最終的參數(shù)：Zk+1

迭代步驟：

1: 初始化計數(shù)器k←0

2: 初始化全局參數(shù)矩陣Zk←Z

3: 初始化局部和對偶參數(shù)矩陣Wik←Wi,Uik←Ui

i=1,2,…,N

4: 各分區(qū)并行地執(zhí)行步驟5和步驟6

10: 當(dāng)滿足‖rk+1‖2<ε且‖sk+1‖2<ε，或迭代到指定次數(shù)時算法終止，執(zhí)行步驟11。否則，令k←k+1，并返回步驟4。

11: 返回更新完成的算法參數(shù)Zk+1

3 實驗與結(jié)果分析

本節(jié)將比較不同優(yōu)化算法求解SMLR問題的性能。此外，為了評價ADMM的分布式優(yōu)化求解性能，本節(jié)還在大規(guī)模數(shù)據(jù)集上進(jìn)行了相關(guān)的并行實驗。

3.1 實驗設(shè)置

串行實驗所使用的機(jī)器具有Intel (R) i7-7700HQ(2.8 GHz)的處理器和16 GByte的隨機(jī)存取存儲器。并行實驗所使用的大數(shù)據(jù)平臺部署在由11臺服務(wù)器搭建的真實物理集群上。單臺服務(wù)器的中央處理器為12核、主頻為2.0 GHz的Intel(R) Xeon(R) E5-2620，并且具有64 GByte的隨機(jī)存取存儲器。并行SMLR優(yōu)化算法基于Spark分布式計算框架實現(xiàn)，其中，Spark的版本號為1.5.1。

為了有效地比較不同優(yōu)化算法的性能，實驗選取了多個領(lǐng)域的不同大小的數(shù)據(jù)集，包括鳶尾花卉數(shù)據(jù)集Iris；肺部基因數(shù)據(jù)集Lung；圖像分割數(shù)據(jù)集Segment；多類物體識別數(shù)據(jù)集COIL20；小規(guī)模和大規(guī)模的手寫體數(shù)字識別數(shù)據(jù)集MNIST-S和MNIST以及人臉識別數(shù)據(jù)集Yale-B。為了驗證分布式SMLR優(yōu)化算法的性能，本節(jié)還選取了較大規(guī)模的數(shù)據(jù)集，包括路透社英文新聞文本分類數(shù)據(jù)集RCV1；經(jīng)典二分類數(shù)據(jù)集Realsim；仿真數(shù)據(jù)集Synthetic。表1列出了各數(shù)據(jù)集的描述信息。

表1 實驗數(shù)據(jù)集描述信息Tab.1 Experimental dataset information

表1中，COIL20包含20個物體以5度間隔拍攝的灰度圖像，每個物體包含72張圖像，每張圖像被下采樣為32×32像素大小。MNIST數(shù)據(jù)集包含了0-9在內(nèi)的10類不同的手寫體數(shù)字，訓(xùn)練集和測試集分別包含60 000張和10 000張28×28像素的灰度圖像。小規(guī)模的MNIST數(shù)據(jù)集來自全量MNIST數(shù)據(jù)集的子集，包含了按類別均勻采樣的4 000張訓(xùn)練樣本。Yale-B數(shù)據(jù)集由38個人的人臉構(gòu)成，每張人臉由64張圖像組成，部分人臉不足64張，原始圖像大小為192×168像素大小，本文將其下采樣為48×42像素大小。RCV1和Realsim數(shù)據(jù)集獲取自LIBSVM頁面[18]。Synthetic數(shù)據(jù)集為人工仿真的具有稀疏特性的數(shù)據(jù)集，包括了特征稀疏性和解的稀疏性。數(shù)據(jù)集采用如(58)式生成，即

y=argmax(xTW+εT)

(58)

(58)式中，樣本x∈Rn和參數(shù)矩陣W∈Rn×k都生成于稀疏的標(biāo)準(zhǔn)隨機(jī)正態(tài)分布N～(0,1)并且具有50%的非零元素，ε∈Rk是采樣自標(biāo)準(zhǔn)正態(tài)分布N～(0,1)的噪聲數(shù)據(jù)。argmax(x)操作返回x中最大值的索引。

此外，為了進(jìn)一步探索不同算法在不同數(shù)據(jù)規(guī)模下的性能，本節(jié)還生成了不同樣本規(guī)模及特征規(guī)模的仿真數(shù)據(jù)，仿真數(shù)據(jù)的生成使用了scikit-learn(scikit-learn: machine learning in python)[19]工具包中的make_classification方法。同樣的，在進(jìn)行算法性能比較時，使用了相同的隨機(jī)種子以保證仿真數(shù)據(jù)和實驗結(jié)果的一致性。

值得注意的是，當(dāng)處理高維數(shù)據(jù)時，(53)式中XiWi的計算開銷非常大。為了解決數(shù)據(jù)存儲和計算上的瓶頸，數(shù)據(jù)集Xi被組織成稀疏格式來存儲，而參數(shù)矩陣Wi仍然表示為密集矩陣的形式，XiWi的計算采用稀疏矩陣乘積操作。在實驗中，數(shù)據(jù)集RCV1,Realsim,Synthetic-SP均被表示為LIBSVM[18]的稀疏格式。

3.2 實驗與結(jié)果分析

為了保證實驗的公正性，不同算法的實驗結(jié)果均在最優(yōu)的超參下求得，實驗分別比較了不同算法在各數(shù)據(jù)集上的分類準(zhǔn)確率和運行時間，實驗結(jié)果如表2和表3所示，表中的“-”符號表示算法運行時間過長，無運行結(jié)果。

根據(jù)表2與表3的實驗結(jié)果，可以得出以下結(jié)論。

1)SMLR問題的原始求解算法IRLS在Iris或者Segment等小規(guī)模數(shù)據(jù)集上運行才能得到結(jié)果，當(dāng)樣本數(shù)或者特征數(shù)增加時，其算法的運行時間會顯著增加。例如，在規(guī)模不大的Segment數(shù)據(jù)集上，其樣本數(shù)、特征數(shù)以及類別數(shù)分別為2 310,19,7，但I(xiàn)RLS算法的運行時間卻超過了900 s。在Lung或者COIL20數(shù)據(jù)集上，算法的運行時間甚至已經(jīng)超過1 000 s以上。當(dāng)數(shù)據(jù)集規(guī)模更大時，例如在MNIST或者Yale-B數(shù)據(jù)集上，IRLS算法因為迭代時間過長而無法得到結(jié)果。由于對于特征數(shù)為n的k分類問題中，IRLS算法的計算復(fù)雜度為O((nk)3)，IRLS也不適合處理類別數(shù)較多的數(shù)據(jù)集。因此，使用IRLS算法對SMLR問題進(jìn)行求解時，對數(shù)據(jù)集有很高的要求。

表2 各優(yōu)化算法在不同數(shù)據(jù)集下的分類準(zhǔn)確率Tab.2 Classification accuracy of each algorithm under different datasets %

表3 各優(yōu)化算法在不同數(shù)據(jù)集下的運行時間Tab.3 Running time of each algorithm under different datasets s

2)ISTA和FISTA的分類準(zhǔn)確率在不同數(shù)據(jù)集的表現(xiàn)相當(dāng)，在多數(shù)數(shù)據(jù)集上都沒有取得最優(yōu)的結(jié)果。而在算法迭代時間上，F(xiàn)ISTA要遠(yuǎn)快于ISTA算法，是由于FISTA在每一次迭代時并非只使用了Wt，而是使用了前2次參數(shù){Wt-1,Wt}的線性組合，因此，其迭代速度要遠(yuǎn)快于ISTA算法。

3)對于ADMM算法，它在Iris，Lung，Segment，COIL20以及MNIST等不同規(guī)模的數(shù)據(jù)集上都取得了最優(yōu)。另外，雖然ADMM算法沒有在運行時間上取得最優(yōu)，但可以看到它在小規(guī)模數(shù)據(jù)集上如Iris，Lung，Segment數(shù)據(jù)集上的運行時間與FISTA和FASTA算法相差不大。當(dāng)應(yīng)用于較大規(guī)模數(shù)據(jù)集時，ADMM算法與FISTA算法運行時間相當(dāng)，但都略慢于FASTA算法。

4)FASTA算法在數(shù)據(jù)集規(guī)模不大時，其在運行時間上具有一定的優(yōu)勢，并在7個數(shù)據(jù)集中的5個中都取得了最優(yōu)。而從分類準(zhǔn)確率的角度來講，F(xiàn)ASTA算法的準(zhǔn)確率僅在Iris，COIL20，Yale-B數(shù)據(jù)集取得了最優(yōu)。因此，當(dāng)數(shù)據(jù)集較大時，采用FASTA能夠在損失一定精度的同時以較快速度求解。

為了進(jìn)一步驗證各算法在不同數(shù)據(jù)集下的性能，本文在不同樣本和特征規(guī)模的仿真數(shù)據(jù)下進(jìn)行了實驗，實驗結(jié)果如圖1。由于在仿真數(shù)據(jù)集下各算法的分類準(zhǔn)確率較接近，因此，這里只對各算法的運行時間進(jìn)行了繪制。在圖1a中，選取特征數(shù)為10，類別數(shù)為3，通過改變樣本大小從28到218，得到各算法在不同樣本規(guī)模下的運行時間。在圖1b中，選取樣本數(shù)為214，類別數(shù)為3，通過改變特征維度從10到500，得到各算法在不同特征規(guī)模下的運行時間。其中，IRLS算法在各數(shù)據(jù)集下的運行時間均較長，因此，在繪制結(jié)果時省略了IRLS的結(jié)果。

圖1 各算法在不同樣本數(shù)及特征數(shù)下的運行時間Fig.1 Running time of each algorithm under different example sizes and feature sizes

從圖1a中可以看到，當(dāng)樣本規(guī)模較小時，各算法在時間性能上的差異較小，而當(dāng)樣本量逐漸增大時，ISTA算法的運行時間顯著增加。在圖1b中，隨著特征規(guī)模的增加，除了ISTA算法外，各算法的運行時間差異較小。FISTA，ADMM以及FASTA算法在不同樣本規(guī)模與不同特征規(guī)模的數(shù)據(jù)集上的運行時間較接近，當(dāng)樣本規(guī)模或者特征規(guī)模增加時，ADMM算法的時間性能較差，而FASTA算法則在大規(guī)模樣本和較大規(guī)模特征的數(shù)據(jù)集下的時間性能更優(yōu)。

在實際中，人們不可避免地會遇到大規(guī)模的數(shù)據(jù)集，因此，有必要探討SMLR的分布式優(yōu)化問題。選取RCV1，Realsim以及仿真的Synthetic數(shù)據(jù)集作為分布式優(yōu)化數(shù)據(jù)集，圖2—圖4顯示了在不同數(shù)據(jù)集下，ADMM的分類準(zhǔn)確率、運行時間及加速比隨分塊數(shù)的變化情況。

圖2 并行ADMM算法在RCV1數(shù)據(jù)集上的實驗結(jié)果Fig.2 Results of the parallel ADMM algorithm on RCV1 dataset

圖3 并行ADMM算法在Realsim數(shù)據(jù)集上的實驗結(jié)果Fig.3 Results of the parallel ADMM algorithm on Realsim dataset

從圖2—圖4左側(cè)的分類準(zhǔn)確率隨分塊數(shù)變化的曲線中可以看到，分布式ADMM算法在Synthetic數(shù)據(jù)集上的分類準(zhǔn)確率呈現(xiàn)先增后減的趨勢，而在RCV1和Realsim數(shù)據(jù)集上，其分類正確率則隨分塊數(shù)目的增加而增加。分布式ADMM算法的實驗結(jié)果可以從集成學(xué)習(xí)角度去理解，即基分類器為一個ADMM模型，每個模型使用不相交的子訓(xùn)練集進(jìn)行訓(xùn)練，最終的預(yù)測結(jié)果為多個模型預(yù)測結(jié)果的平均。當(dāng)分塊數(shù)不是很多時，各計算節(jié)點有足夠的訓(xùn)練數(shù)據(jù)來訓(xùn)練基分類器，分塊數(shù)越多則集成的效果越明顯。當(dāng)分塊數(shù)達(dá)到某一臨界值時，各計算節(jié)點用于訓(xùn)練的數(shù)據(jù)變少，過擬合的風(fēng)險增加，這也使得模型泛化能力降低從而導(dǎo)致分類準(zhǔn)確率下降。從RCV1和Realsim數(shù)據(jù)集的實驗結(jié)果中可以看到，當(dāng)分塊數(shù)達(dá)到128后，算法的分類準(zhǔn)確率仍呈現(xiàn)增加的趨勢。一種可能的解釋是這2個數(shù)據(jù)集的特征具有很好的表達(dá)能力，即使訓(xùn)練數(shù)據(jù)很小時也可以訓(xùn)練的很好。

圖4 并行ADMM算法在Synthetic數(shù)據(jù)集上的實驗結(jié)果Fig.4 Results of the parallel ADMM algorithm on Synthetic dataset

圖2—圖4的中間部分顯示了算法運行時間隨分塊數(shù)變化的曲線?？梢钥吹剑植际紸DMM算法算法在RCV1，Realsim以及Synthetic數(shù)據(jù)集上的運行時間呈現(xiàn)出隨著分塊數(shù)增加而減少的趨勢。當(dāng)分塊數(shù)，也即并行度，逐漸地增長到某個飽和點時，集群上節(jié)點之間的通信時間增加，算法的時間性能趨于平緩，甚至出現(xiàn)運行時間隨并行度增加的情況。

另外，可以看出，當(dāng)分塊數(shù)為1時，分布式ADMM算法實際是以串行方式運行，因此，可以據(jù)此畫出算法在不同分塊數(shù)下的加速比，如圖2—圖4的右側(cè)圖像所示。結(jié)合分類準(zhǔn)確率曲線可以發(fā)現(xiàn)，當(dāng)選擇合適的并行度時，分布式ADMM算法能夠在保持分類準(zhǔn)確率的同時極大地加速訓(xùn)練過程。

4 結(jié)束語

本文回顧了幾種經(jīng)典的稀疏優(yōu)化算法，如ISTA，F(xiàn)ISTA，F(xiàn)ASTA和ADMM，并將其推廣應(yīng)用于求解SMLR問題。在不同數(shù)據(jù)集上的實驗結(jié)果表明，ADMM算法在小規(guī)模數(shù)據(jù)集上具有較好的分類精度和運行時間，而FASTA算法在中小規(guī)模數(shù)據(jù)集上具有較快的求解速度。然而，F(xiàn)ASTA算法在處理大規(guī)模數(shù)據(jù)集時不能充分發(fā)揮其優(yōu)勢。本文將ADMM擴(kuò)展到分布式優(yōu)化領(lǐng)域，這使得SMLR的分布式優(yōu)化求解成為可能。通過選擇合適的分塊數(shù)，分布式ADMM算法可以在很短的時間內(nèi)求解，并保持較高的分類準(zhǔn)確率。

因此，本文建議，如果研究者對算法的準(zhǔn)確率要求不是特別高，但是期望算法具有較快的運行速度，那么可以選擇FASTA算法。當(dāng)處理較大規(guī)模數(shù)據(jù)集時，根據(jù)上面的分析，本文更建議使用FASTA算法。當(dāng)數(shù)據(jù)集規(guī)模很大，甚至無法由單機(jī)處理時，則采用并行ADMM算法則具有更大的優(yōu)勢。