并行效率敏感的大規(guī)模SVM數(shù)據(jù)分塊數(shù)選擇

張 闖 廖士中

(天津大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,天津，300350)

引 言

支持向量機(jī)(Support vector machines,SVMs)是基本機(jī)器學(xué)習(xí)模型和有效的數(shù)據(jù)挖掘方法之一。核SVM通過(guò)引入核技巧實(shí)現(xiàn)應(yīng)用線性方法來(lái)學(xué)習(xí)非線性關(guān)系的途徑,但SVM的求解是一個(gè)二次規(guī)劃問(wèn)題,時(shí)間復(fù)雜度為O(n3),空間復(fù)雜度為O(n2),其中n為訓(xùn)練集規(guī)模[1-2],這成為發(fā)展大規(guī)模SVM 的主要瓶頸。

為發(fā)展大規(guī)模SVM,文獻(xiàn)[3]提出基于核矩陣近似的并行SVM算法,引入核緩存策略來(lái)并行計(jì)算核矩陣,數(shù)據(jù)分塊數(shù)設(shè)為l/d,其中,l為訓(xùn)練集規(guī)模,d為核緩存區(qū)大小。近年來(lái),應(yīng)用隨機(jī)特征映射近似核方法的研究引起了廣泛關(guān)注。Rahimi等人提出利用隨機(jī)傅里葉特征映射近似高斯核函數(shù)，進(jìn)而在顯式隨機(jī)特征空間中應(yīng)用線性SVM來(lái)一致逼近核誘導(dǎo)特征空間中的高斯核SVM[4-5], 成為提升SVM可擴(kuò)展性的有效方法。Feng等人提出一種新的隨機(jī)特征映射方法[6],利用有符號(hào)循環(huán)隨機(jī)矩陣代替無(wú)結(jié)構(gòu)隨機(jī)矩陣來(lái)投影數(shù)據(jù)。該方向的工作進(jìn)一步發(fā)展了有效的近似方法,時(shí)間復(fù)雜度可降至與數(shù)據(jù)規(guī)模呈對(duì)數(shù)線性,同時(shí)也發(fā)展了大規(guī)模核方法[7]。文獻(xiàn)[8]通過(guò)引入半寬因子，構(gòu)造高斯區(qū)間核SVM模型，發(fā)展了針對(duì)區(qū)間型數(shù)據(jù)的高效分類方法。

交替方向乘子法 (Alternating direction method of multipliers, ADMM) 提供一個(gè)簡(jiǎn)單且強(qiáng)大的并行/分布式計(jì)算框架,可將大規(guī)模問(wèn)題分解為多個(gè)小規(guī)模子問(wèn)題,進(jìn)而相互協(xié)調(diào)且并行一致地求解原問(wèn)題[9]。在該框架下,文獻(xiàn)[10]提出基于并行/分布式ADMM的線性SVM算法。該算法中的數(shù)據(jù)分塊數(shù)依據(jù)經(jīng)驗(yàn)來(lái)選擇,沒(méi)有探討數(shù)據(jù)分塊數(shù)對(duì)模型泛化性和計(jì)算效率的影響。文獻(xiàn)[11]將隨機(jī)特征映射與并行/分布式ADMM相結(jié)合,提出基于核方法統(tǒng)計(jì)模型的大規(guī)模訓(xùn)練框架。該框架適合多種統(tǒng)計(jì)學(xué)習(xí)任務(wù),分塊數(shù)目經(jīng)驗(yàn)地取為D/d,其中,D為隨機(jī)特征維度,d為訓(xùn)練數(shù)據(jù)維度。矩陣分解與填充廣泛應(yīng)用于推薦系統(tǒng)中,分布式矩陣分解得到了廣泛關(guān)注。Yu等人[12]研究隨機(jī)ADMM 框架下分布式求解矩陣分解問(wèn)題,矩陣劃分塊數(shù)與集群節(jié)點(diǎn)個(gè)數(shù)相同,沒(méi)有討論分塊數(shù)目對(duì)均方根誤差的影響。Zhang等人[13]提出基于分解法的可擴(kuò)展核嶺回歸算法,通過(guò)適當(dāng)?shù)膮?shù)調(diào)節(jié)，只要分塊數(shù)目不是太多，該方法可以提高計(jì)算速度，保持統(tǒng)計(jì)最優(yōu)性,進(jìn)而得到有效的一致模型估計(jì)量。

已有的并行/分布式機(jī)器學(xué)習(xí)方法中,數(shù)據(jù)分塊工作沒(méi)有明確的分塊數(shù)選擇準(zhǔn)則,也缺乏基本的理論保證。針對(duì)這一問(wèn)題,提出大規(guī)模并行效率敏感的數(shù)據(jù)分塊數(shù)選擇準(zhǔn)則。該準(zhǔn)則以并行/分布式機(jī)器學(xué)習(xí)的泛化誤差與數(shù)據(jù)分塊數(shù)之間的關(guān)系為基礎(chǔ),折衷泛化誤差與并行效率,可在保證并行/分布式機(jī)器學(xué)習(xí)測(cè)試精度的條件下,提高計(jì)算效率。在ADMM框架下的隨機(jī)傅里葉特征空間中,采用所提出的數(shù)據(jù)分塊數(shù)選擇準(zhǔn)則實(shí)現(xiàn)一個(gè)大規(guī)模支持向量機(jī)模型。實(shí)驗(yàn)結(jié)果表明,該準(zhǔn)則在保證大規(guī)模支持向量機(jī)測(cè)試精度的同時(shí),仍可進(jìn)一步提高計(jì)算效率。

1 相關(guān)工作

1.1 交替方向乘子法

當(dāng)目標(biāo)函數(shù)滿足可加性時(shí),并行/分布式ADMM 等式約束問(wèn)題[9]為

其中:ρ>0為懲罰系數(shù),ui=y/ρ為縮放對(duì)偶變量，y為拉格朗日乘子向量。每個(gè)從進(jìn)程并行更新局部變量ωi,ui。主進(jìn)程匯聚ωi,ui,更新全局變量υ,并廣播給從進(jìn)程。并行/分布式ADMM交替優(yōu)化過(guò)程見算法1。

算法1分布式交替方向乘子法(D-ADMM)

輸入：函數(shù)f,g,矩陣A,分塊數(shù)備選集B,懲罰系數(shù)ρ>0。

(1) 初始化:ω0,υ0,y0;

(2) repeat

(6) until 滿足終止條件。

輸出：ω*,υ*,y*。

D-ADMM 的終止條件為

其中:εpri>0,εdual>0分別為原問(wèn)題和對(duì)偶可行性條件的誤差, 定義為

其中:εabs>0,εrel>0分別為絕對(duì)誤差和相對(duì)誤差[9]。

滿足如下兩個(gè)假設(shè)的條件時(shí), D-ADMM 收斂[9，14]。

假設(shè)1擴(kuò)展實(shí)值函數(shù)f:Rn→R∪{+∞},g:Rm→R∪{+∞}是封閉、適定且凸的[15]。

假設(shè)2增廣拉格朗日函數(shù)L存在鞍點(diǎn)。

1.2 隨機(jī)傅里葉特征映射

高斯核函數(shù)是一種通用的平移不變核,定義為

(1)

式中γ=1/2σ2。

可通過(guò)高斯核函數(shù)的傅里葉逆變換得到ω的概率密度函數(shù)p(ω),ω～正態(tài)分布N(0,2γI), 其中I為單位矩陣。易知

可見,〈Tω,b(x),Tω,b(y)〉是高斯核函數(shù)(1)的無(wú)偏估計(jì)。通過(guò)標(biāo)準(zhǔn)蒙特卡洛積分近似高斯核,構(gòu)造如下隨機(jī)傅里葉特征映射[4-5]

(2)

式中:D為隨機(jī)特征維度,高斯隨機(jī)矩陣T∈RD×d,Ti～N(0,2γI),b為隨機(jī)向量,bi～均勻分布U(-π,π),i=1,…,D。則k(x,y)=E〈Φ(x),Φ(y)〉。

2 并行/分布式機(jī)器學(xué)習(xí)模型泛化誤差分析

本節(jié)推導(dǎo)并行/分布式機(jī)器學(xué)習(xí)模型數(shù)據(jù)分塊數(shù)與泛化誤差之間的關(guān)系。

不失一般性,界定以下假設(shè)條件:

假設(shè)3f*∈C(X)且‖f*‖∞≤M。其中,C(X)是X上的連續(xù)函數(shù)空間, ‖·‖∞為上確界范數(shù)。

假設(shè)4損失函數(shù)l(·)為非負(fù)L-Lipschiz 連續(xù)的凸函數(shù)。HK是一再生核Hilbert 空間 (RKHS)。對(duì)任意f1,f2∈HK,存在常數(shù)L>0,使得

假設(shè)5任意g∈C(X),ε>0,存在f∈HK,使得‖f-g‖∞<ε。令BR=f∈HK,‖f‖∞≤R,R>0。存在常數(shù)C0,s>0,使得

N∞(F,r)≤expC0r-s

其中:N∞(F,r)表示集合F半徑為r球的覆蓋數(shù)。

下面分析并行/分布式機(jī)器學(xué)習(xí)模型的泛化誤差。可將泛化誤差分解為采樣誤差、假設(shè)誤差和近似誤差3部分，則有

其中:f*∈C(X),f∈HK是在樣本S上學(xué)習(xí)的結(jié)果,fB∈HK是把樣本分成B塊后學(xué)習(xí)的結(jié)果,ε(·)為期望誤差,εS(·)為經(jīng)驗(yàn)誤差。令樣本規(guī)模為N,基于以上假設(shè)和分析可給出如下泛化誤差分析結(jié)果。

引理1[16]假設(shè)3—5成立,M′=max{2M,‖f-f*‖∞}。對(duì)任意0<δ<1,有

(3)

引理2[16]假設(shè)3—5成立,對(duì)任意0<δ<1,有

(4)

式中M′,G1和G2定義同引理1。

定理1假設(shè)3—5成立,當(dāng)N足夠大時(shí),對(duì)任意0<δ<1,f∈HK,有

(5)

式中:‖f-f*‖∞≤1/N,G1和G2定義同引理1。

證明由假設(shè)3和假設(shè)5成立可知,對(duì)任意N≥1,存在f∈HK,有

‖f-f*‖∞<1/N

由假設(shè)4成立,損失函數(shù)l(·)是L-Lipschiz連續(xù)的，有

ε(f)-ε(f*)=Ez[l(f,z)-l(f*,z)]≤L‖f-f*‖∞

(6)

所以,近似誤差上界為L(zhǎng)/(N/B)τ。當(dāng)N足夠大時(shí),‖f-f*‖∞<1/N→0。那么

M′=max(2M,‖f-f*‖∞)=2M

(7)

將式(7)分別代入采樣誤差式(3)和假設(shè)誤差式(4)并與近似誤差式(6)求和,可得式(5)。

3 數(shù)據(jù)分塊數(shù)選擇準(zhǔn)則

給定訓(xùn)練數(shù)據(jù)A={ri=(xi,yi),i=1,2,…,N},其中,xi∈Rd,d為訓(xùn)練數(shù)據(jù)維度,N為訓(xùn)練集規(guī)模。

由經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化[17]可得

其中:f為再生核希爾伯特空間HK中的任意假設(shè),l(·)為非負(fù)凸損失函數(shù)。

定義分塊經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化,可得

其中l(wèi)i(·)為第i個(gè)子數(shù)據(jù)塊的平均經(jīng)驗(yàn)風(fēng)險(xiǎn)。

并行算法效率[19]定義為

其中:Ts為串行時(shí)間,Tp為并行時(shí)間,B為進(jìn)程數(shù)。

為了權(quán)衡模型的泛化性和并行效率,提出并行效率敏感的數(shù)據(jù)分塊數(shù)選擇準(zhǔn)則

其中:B為分塊數(shù)備選集,η為懲罰系數(shù),δ≤E(B)<1,δ為并行效率下界。

4 大規(guī)模支持向量機(jī)

本節(jié)采用所提出的數(shù)據(jù)分塊數(shù)選擇準(zhǔn)則來(lái)構(gòu)造一個(gè)大規(guī)模支持向量機(jī)模型。

在并行/分布式ADMM框架下的隨機(jī)傅里葉特征空間中實(shí)現(xiàn)大規(guī)模支持向量機(jī)模型。給定標(biāo)簽數(shù)據(jù)集S={(x1,y1),(x2,y2),…,(xN,yN)}∈(X×Y)N,其中,X表示輸入域,Y為輸出域,xi∈Rd,標(biāo)簽yi∈{-1,+1},N為訓(xùn)練集規(guī)模。

由隨機(jī)傅里葉特征映射式(2),得到隨機(jī)特征映射矩陣Z∈RN×D,D為隨機(jī)特征維度。將Z按行隨機(jī)劃分為B塊[18],每個(gè)分塊的樣本規(guī)模為|Bj|。隨機(jī)傅里葉特征映射顯式地構(gòu)造隨機(jī)特征空間,可在該隨機(jī)特征空間中應(yīng)用線性SVM來(lái)一致逼近高斯核SVM[7]。

損失函數(shù)max(1-yiωTzi,0)2是L-Lipschiz連續(xù)的[20]。由分塊經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化,可得

此時(shí),D-ADMM 中g(shù)(·)為指示函數(shù)[21]。定義為

大規(guī)模SVM最優(yōu)分塊數(shù)選擇為

ADMM 框架下隨機(jī)傅里葉特征空間中數(shù)據(jù)分塊數(shù)選擇過(guò)程見算法2。

算法2分塊數(shù)選擇算法 (SNC)

輸入：隨機(jī)特征矩陣Z∈RN×D,分塊數(shù)備選集B,且|B|=t, 懲罰系數(shù)η, 并行效率下界δ。

(1) 初始化:E(B)=1;

(2) fork=1,2,…,tdo

(4) 更新E(B);

(6) end for

對(duì)D-ADMM 中的并行子問(wèn)題利用對(duì)偶坐標(biāo)下降算法[10,22]求解。要得到ε精確解, 迭代次數(shù)為O(log(1/ε)),時(shí)間復(fù)雜度為O(nDlog(1/ε)),其中,n為子數(shù)據(jù)塊數(shù)據(jù)規(guī)模。算法SNC的迭代次數(shù)為t,所以總的時(shí)間復(fù)雜度為O(tnDlog(1/ε))。

D-ADMM框架下大規(guī)模SVM問(wèn)題為

其中:C為超參數(shù),o為全局變量,ωj是與第j個(gè)進(jìn)程的局部變量。由D-ADMM可得

每個(gè)進(jìn)程j處理一個(gè)子問(wèn)題,各個(gè)并行子問(wèn)題利用對(duì)偶坐標(biāo)下降算法求解ωj[22]。

5 實(shí)驗(yàn)結(jié)果及分析

本節(jié)實(shí)現(xiàn)并行/分布式 ADMM 框架下隨機(jī)傅里葉特征空間中的大規(guī)模 SVM, 并實(shí)驗(yàn)驗(yàn)證所提出的數(shù)據(jù)分塊數(shù)選擇準(zhǔn)則。實(shí)驗(yàn)中使用6個(gè)標(biāo)準(zhǔn)數(shù)據(jù)集,如表1所示,其中,大規(guī)模 SVM 的超參數(shù)C和高斯核參數(shù)γ通過(guò)在11×11空間內(nèi)進(jìn)行格搜索的5-折交叉驗(yàn)證來(lái)選取,(C,γ)∈{2-9，2-7，…，27，29}。η為懲罰系數(shù),并行效率下界δ設(shè)為0.25,D-ADMM 中懲罰系數(shù)ρ設(shè)為1,絕對(duì)誤差εabs和相對(duì)誤差εrel均設(shè)為10-4,ε設(shè)為10-3。實(shí)驗(yàn)環(huán)境: 曙光“星云”高性能計(jì)算集群。采用OpenMPI 1.4.5和C++實(shí)現(xiàn)并行算法。普通隊(duì)列最多申請(qǐng)4節(jié)點(diǎn),每個(gè)節(jié)點(diǎn)32個(gè)核,每個(gè)核分配內(nèi)存2 GB,主頻2.2 GHz, 操作系統(tǒng)CentOS 5.8,作業(yè)管理系統(tǒng)Torque 4.1.5。

表1 標(biāo)準(zhǔn)數(shù)據(jù)集及相關(guān)參數(shù)

對(duì)比實(shí)驗(yàn)結(jié)果如表2所示。其中, Acc表示測(cè)試精度, 計(jì)算時(shí)間和測(cè)試精度為重復(fù)10次實(shí)驗(yàn)的平均值。

表2最優(yōu)分塊數(shù)目、其他分塊數(shù)目下并行計(jì)算時(shí)間(訓(xùn)練+測(cè)試)與測(cè)試精度比較

Tab.2Comparisonofparallelcomputationtime(train+test)andtestaccuracy(Acc)ofoptimalandotherblocks

數(shù)據(jù)集 時(shí)間 /sAcc/% 時(shí)間/s Acc/% 時(shí)間/sAcc/%時(shí)間/s Acc/%a9a B=2B=4^B=6B=1219.085.17±0.03 14.285.21±0.02 10.885.21±0.0312.885.17±0.02ijcnn1 B=2 ^B=8B=12B=1616.591.49±0.279.291.32±0.3410.7 91.24±0.2911.3 91.17±0.34w8a B=2^B=8B=12B=1437.498.87±0.2314.698.74±0.2618.5 98.68±0.1922.8 98.64±0.21webpam B=2B=6^B=12B=161 65792.79±0.1954292.86±0.29487 92.82±0.23508 92.75±0.25covtype B=2B=6^B=8B=141 37278.76±0.5656879.10±0.25292 79.11±0.63327 78.64±0.54SUSY B=2B=4^B=10B=1427079.16±0.0316279.16±0.0365 79.15±0.02101 79.15±0.03

實(shí)驗(yàn)結(jié)果表明,最優(yōu)分塊數(shù)相比于其他分塊數(shù)下的并行模型預(yù)測(cè)精度相當(dāng),但計(jì)算時(shí)間大幅縮減。如在 webspam數(shù)據(jù)集上, 在最優(yōu)分塊數(shù)為12,相比于B=2而言,計(jì)算時(shí)間大幅縮短。

為了驗(yàn)證不同分塊數(shù)對(duì)模型測(cè)試精度的影響,給出測(cè)試精度隨著迭代次數(shù)的變化曲線,如圖1所示。

圖1 測(cè)試精度隨著迭代次數(shù)的變化情況Fig.1 Test accuracy varies with respect to the number of iterations

結(jié)果表明,在相同迭代次數(shù)下,隨著分塊數(shù)的增多,模型的測(cè)試精度逐漸下降。這與第2節(jié)的泛化誤差分析結(jié)果一致。

6 結(jié)束語(yǔ)

現(xiàn)有并行/分布式機(jī)器學(xué)習(xí)方法缺少有理論依據(jù)的數(shù)據(jù)分塊數(shù)選擇準(zhǔn)則。針對(duì)這一問(wèn)題,推導(dǎo)并行/分布式機(jī)器學(xué)習(xí)模型的泛化誤差與分塊數(shù)目的關(guān)系,折衷泛化性與并行效率,進(jìn)而提出一個(gè)并行效率敏感的并行/分布式機(jī)器學(xué)習(xí)數(shù)據(jù)分塊數(shù)選擇準(zhǔn)則。大規(guī)模支持向量機(jī)的理論分析和實(shí)驗(yàn)結(jié)果表明,所提出的數(shù)據(jù)分塊數(shù)選擇準(zhǔn)則,可保證測(cè)試精度并提高計(jì)算效率。雖然所提出的數(shù)據(jù)分塊數(shù)選擇準(zhǔn)則適用于ADMM框架下隨機(jī)傅里葉特征空間中的大規(guī)模支持向量機(jī),該數(shù)據(jù)分塊數(shù)準(zhǔn)則及分析方法也適用于其他并行/分布式機(jī)器學(xué)習(xí)模型,如大規(guī)模核嶺回歸等。