基于分布式核的在線AUC最大化算法

劉 鑫,潘志松,周星宇,白 瑋，尤 峻

(1.陸軍工程大學(xué) 指揮控制工程學(xué)院，江蘇 南京 210007;2.陸軍工程大學(xué) 通信工程學(xué)院，江蘇 南京 210007)

0 引言

接收者操作特性曲線下面積(Area Under ROC Curve，AUC)[1-2]是一種重要的評價(jià)分類性能的指標(biāo)，它衡量了分類器對任意正樣本比任意負(fù)樣本有更高決策值的概率。與常用的評價(jià)指標(biāo)錯(cuò)分率相比，以AUC為優(yōu)化目標(biāo)的分類器能在不均衡數(shù)據(jù)集上獲得更好的測試結(jié)果。因此AUC廣泛地應(yīng)用于處理類別不均衡問題，比如癌癥診斷[3]和異常值檢測[4]問題。

文獻(xiàn)[5]研究了采用批處理學(xué)習(xí)算法來處理AUC最大化問題，但批處理算法訓(xùn)練之前需要存儲所有訓(xùn)練數(shù)據(jù)并且在獲得新樣本后需要使用所有數(shù)據(jù)用于更新模型。因此傳統(tǒng)的批處理學(xué)習(xí)算法不適用于處理大規(guī)模的流式數(shù)據(jù)。為了解決這個(gè)問題，一些研究者利用在線學(xué)習(xí)算法來高效地處理按序達(dá)到的大規(guī)模流式數(shù)據(jù)。但與傳統(tǒng)在線算法不同，AUC最大化問題需要優(yōu)化一個(gè)不同類樣本間的成對損失，這樣就需要存儲所有接收到的訓(xùn)練樣本。為了減少存儲空間消耗，文獻(xiàn)[6]提出了一種利用抽樣來模擬歷史數(shù)據(jù)的在線AUC學(xué)習(xí)方法，該方法是用兩個(gè)固定大小的緩存空間來存儲歷史數(shù)據(jù)，并使用蓄水池抽樣方法來動(dòng)態(tài)更新緩存空間，在計(jì)算成對損失時(shí)只需要與緩存空間中的歷史數(shù)據(jù)進(jìn)行比較即可。文獻(xiàn)[7]提出了一種利用成對平方損失來處理在線AUC最大化問題，該方法利用歷史數(shù)據(jù)的均值向量和協(xié)方差矩陣的信息使得對所有數(shù)據(jù)僅需要計(jì)算一次。但以上兩類方法都是在原數(shù)據(jù)特征空間使用線性分類，對于非線性可分的數(shù)據(jù)集就難以取得理想效果。文獻(xiàn)[8]提出了利用可擴(kuò)展的核學(xué)習(xí)方法使用線性特征來近似表示核函數(shù)。但是隨著網(wǎng)絡(luò)的發(fā)展，數(shù)據(jù)產(chǎn)生的速度更快、維度更高并且數(shù)據(jù)是以分布式的形式存在。如果將所有數(shù)據(jù)發(fā)送到一個(gè)節(jié)點(diǎn)進(jìn)行結(jié)算，那么對單個(gè)節(jié)點(diǎn)的性能和處理時(shí)延就提出了很大的挑戰(zhàn)。

本文提出了一種基于分布式網(wǎng)絡(luò)結(jié)構(gòu)的核在線AUC最大化算法(Distributed Kernel-based Online AUC Maximization，DKOAM)。利用中心化分布式網(wǎng)絡(luò)結(jié)構(gòu)的特點(diǎn)，將計(jì)算分散到每個(gè)工人節(jié)點(diǎn)上，中心節(jié)點(diǎn)只需要收集工人節(jié)點(diǎn)的信息后更新模型分類器。這樣能夠更高效地處理分布式數(shù)據(jù)源數(shù)據(jù)，并且采用基于核方法的特征映射，在非線性可分的數(shù)據(jù)集上比使用原特征數(shù)據(jù)有更好的效果。

1 DKOAM方法介紹

與傳統(tǒng)在線學(xué)習(xí)算法不同，分布式在線學(xué)習(xí)算法有多個(gè)數(shù)據(jù)源。如果將多個(gè)數(shù)據(jù)源的數(shù)據(jù)匯總到一臺服務(wù)器節(jié)點(diǎn)上進(jìn)行計(jì)算，單臺服務(wù)器將難以高效處理海量的數(shù)據(jù)。因此針對多數(shù)據(jù)源的分布式計(jì)算環(huán)境，本文采用一種中心化的分布式在線學(xué)習(xí)算法來處理AUC最大化的問題。

1.1 核表示

(1)

那么核函數(shù)可以表示成對應(yīng)于變量u的期望函數(shù):

κ(x1,x2)=Eu[eiuΤx1·e-iuΤx2]

=Eu[cos(uΤx1)cos(uΤx2)+sin(uΤx1)sin(uΤx2)]

=Eu[[cos(uΤx1),sin(uΤx1)]·[cos(uΤx2),sin(uΤx2)]]

(2)

根據(jù)式(2)平移不變核可以表示成新特征內(nèi)積的期望，其中新特征可表示為z(x)=[cos(uΤx),sin(uΤx)]。因此為了近似表示式(3)中的期望，通過從分布p(u)中獨(dú)立采樣多個(gè)隨機(jī)傅里葉樣本u1,…,um來得到輸入特征x的新特征表示：

1.2 在線AUC最大化

AUC(w)=

(3)

其中Ι(·)為指示器函數(shù)，當(dāng)條件滿足時(shí)輸出1，否則輸出0。但是由于直接優(yōu)化式(3)是一個(gè)NP難問題，因此一般采用一個(gè)凸函數(shù)來替換指示器函數(shù)，這里采用成對的hinge損失來進(jìn)行替換：

(4)

那么可以通過最小化下面這個(gè)目標(biāo)函數(shù)來得到最優(yōu)的分類器：

(5)

但是優(yōu)化式(5)需要計(jì)算當(dāng)前樣本和所有不同標(biāo)簽訓(xùn)練樣本之間的成對損失，因此需要存儲所有已接收數(shù)據(jù)，這對于大數(shù)據(jù)條件下的在線學(xué)習(xí)需要消耗大量的存儲空間。為了解決這個(gè)問題，文獻(xiàn)[6]、[11]中引入兩個(gè)固定大小N+和N-的緩存空間B+和B-來存儲正負(fù)類的樣本。而緩存空間的更新采用蓄水池抽樣技術(shù)，通過蓄水池抽樣能夠保證緩存空間刻畫了對所有已接收數(shù)據(jù)的均勻采樣。在一個(gè)新樣本(zt,yt)到達(dá)時(shí)，當(dāng)緩存空間B的大小小于固定上限N時(shí)，就將該樣本插入緩存空間中。當(dāng)?shù)趖輪接收到的樣本大小Nt超過N時(shí)，就按照一定概率用新樣本隨機(jī)替換一個(gè)緩存空間中的老樣本。具體算法細(xì)節(jié)見算法1。

算法1：緩存空間更新算法(UpdateBuffer)

1：輸入：Bt,zt,N,Nt+1

2：if |Bt|

3：Bt+1=Bt∪{zt}

4：else

5： 按照Pr(Z=1)=N/Nt+1的概率從伯努利分布中抽取一個(gè)樣本Z

6： ifZ=1

7： 隨機(jī)從Bt中刪除一個(gè)樣本

8：Bt+1=Bt∪{zt}

9： end if

10：end if

11：輸出:Bt+1

1.3 DKOAM方法

在中心化分布式環(huán)境下，如圖1所示，存在一個(gè)中心節(jié)點(diǎn)和多個(gè)工人節(jié)點(diǎn)。工人節(jié)點(diǎn)同中心節(jié)點(diǎn)相連，工人節(jié)點(diǎn)之間沒有連接。

圖1 中心化分布式拓?fù)涫疽鈭D

在中心化在線學(xué)習(xí)中，所有工人節(jié)點(diǎn)采樣同樣的隨機(jī)傅里葉樣本。每個(gè)工人節(jié)點(diǎn)獨(dú)立接收來自不同數(shù)據(jù)源數(shù)據(jù)，本地獨(dú)立計(jì)算梯度值。中心節(jié)點(diǎn)采用同步的方式匯總所有工人節(jié)點(diǎn)的梯度值后進(jìn)行模型更新。為了解決分布式大數(shù)據(jù)環(huán)境下的線性不可分?jǐn)?shù)據(jù)的在線AUC最大化學(xué)習(xí)，本文提出了一種中心化的基于核的在線AUC最大化學(xué)習(xí)算法DKOAM，具體算法細(xì)節(jié)見算法2。

算法2：基于核的中心化在線AUC最大化學(xué)習(xí)算法(DKOAM)

工人節(jié)點(diǎn)(i=1,…,n):

2：fort=1,2,…,T

10： else

14： end if

16：end for

中心節(jié)點(diǎn)：

1：輸入：學(xué)習(xí)率η

2：fort=1,2,…,T

5：end for

2 實(shí)驗(yàn)驗(yàn)證與分析

本節(jié)對提出的DKOAM算法在3個(gè)標(biāo)準(zhǔn)數(shù)據(jù)集上與4種在線AUC最大化算法進(jìn)行比較。

2.1 比較算法

比較算法包括以下4種：

(1)OAMseq：基于蓄水池抽樣和序列更新算法的在線AUC最大化算法[6]。

(2)OAMgra:基于蓄水池抽樣和在線梯度更新算法的在線AUC最大化算法[6]。

(3)OPAUC：基于平方損失的單遍AUC最大化算法[7]。

(4)FOAM：基于隨機(jī)傅里葉特征方法的核在線AUC最大化算法[8]。

2.2 實(shí)驗(yàn)準(zhǔn)備

為了比較DKOAM與其他4種在線AUC最大化算法之間的性能，本文實(shí)驗(yàn)在3種標(biāo)準(zhǔn)數(shù)據(jù)集上進(jìn)行測試。數(shù)據(jù)集的特征都重新調(diào)整到[-1,1]之間。多分類數(shù)據(jù)集(letter和acoustic)轉(zhuǎn)化為二分類數(shù)據(jù)集，即隨機(jī)選擇一類作為正樣本，其他類作為負(fù)樣本。數(shù)據(jù)集的具體特征見表1。

表1 數(shù)據(jù)集特征

DKOAM使用4個(gè)工人節(jié)點(diǎn)和1個(gè)中心節(jié)點(diǎn)的中心化分布式網(wǎng)絡(luò)，每個(gè)節(jié)點(diǎn)運(yùn)行在一個(gè)CPU核心上，算法使用MPI完成節(jié)點(diǎn)間通信。DKOAM的學(xué)習(xí)率η和高斯核σ參數(shù)的尋參空間分別為[2-10,210]和[1,20]。參數(shù)通過五折交叉驗(yàn)證確定，即隨機(jī)將數(shù)據(jù)集分成5份，4份用于訓(xùn)練，1份用于測試。其他算法的參數(shù)按照推薦參數(shù)進(jìn)行設(shè)置。

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

調(diào)參結(jié)束后，采用4次五折算法進(jìn)行測試以進(jìn)一步減少隨機(jī)分割數(shù)據(jù)集帶來的隨機(jī)性。對20次測試結(jié)果取平均值作為測試結(jié)果。為了比較算法的運(yùn)行效率，對25次測試運(yùn)行時(shí)間取平均值。測試結(jié)果見表2。

表2 DKOAM與4種在線AUC最大化算法測試結(jié)果

注：表中每一項(xiàng)為：平均AUC值/平均運(yùn)行時(shí)間(s)

從表2的結(jié)果可以看出，使用核方法的FOAM和DKOAM相較于使用原特征的其他在線AUC最大化算法有更高的精度。這驗(yàn)證了在數(shù)據(jù)線性不可分的情況下，將原數(shù)據(jù)特征通過核方法映射到新的核特征空間有更好的分類效果。而DKOAM和FOAM相比，兩者精度相當(dāng)。從算法時(shí)間復(fù)雜性方面分析，基于分布式計(jì)算框架的DKOAM相較于FOAM有更高的效率。這驗(yàn)證了分布式計(jì)算框架在處理分布式多數(shù)據(jù)的問題中相較于單節(jié)點(diǎn)的算法有更高的運(yùn)算效率。

從圖2中能夠看出，DKOAM和FOAM兩種基于核方法的算法相較于其他在原特征空間的線性模型算法有更快的收斂速率。本文提出的DKOAM相較于FOAM收斂更快，并且相較于OAMseq和OAMgra兩種方法收斂更穩(wěn)定，波動(dòng)更小。這也驗(yàn)證了采用小批量更新方法對模型更新過程中的噪音更加魯棒。

圖2 在數(shù)據(jù)集letter上的收斂速率比較

3 結(jié)論

本文提出了一種基于中心化分布式網(wǎng)絡(luò)結(jié)構(gòu)和核方法的在線AUC最大化算法DKOAM。該算法利用隨機(jī)傅里葉映射來近似核函數(shù)并采用分布式網(wǎng)絡(luò)來處理分布式數(shù)據(jù)源。通過使用在線學(xué)習(xí)算法高效處理大規(guī)模流式數(shù)據(jù)。通過與4個(gè)在線AUC算法在3個(gè)標(biāo)準(zhǔn)數(shù)據(jù)集上的性能比較，驗(yàn)證了DKOAM的有效性。