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

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

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

0 引言

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

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

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

1 DKOAM方法介紹

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

1.1 核表示

(1)

那么核函數(shù)可以表示成對應于變量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)平移不變核可以表示成新特征內積的期望，其中新特征可表示為z(x)=[cos(uΤx),sin(uΤx)]。因此為了近似表示式(3)中的期望，通過從分布p(u)中獨立采樣多個隨機傅里葉樣本u1,…,um來得到輸入特征x的新特征表示：

1.2 在線AUC最大化

AUC(w)=

(3)

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

(4)

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

(5)

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

6： ifZ=1

7： 隨機從Bt中刪除一個樣本

8：Bt+1=Bt∪{zt}

9： end if

10：end if

11：輸出:Bt+1

1.3 DKOAM方法

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

圖1 中心化分布式拓撲示意圖

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

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

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

2：fort=1,2,…,T

10： else

14： end if

16：end for

中心節(jié)點：

1：輸入：學習率η

2：fort=1,2,…,T

5：end for

2 實驗驗證與分析

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

2.1 比較算法

比較算法包括以下4種：

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

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

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

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

2.2 實驗準備

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

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

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

2.3 實驗結果

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

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

注：表中每一項為：平均AUC值/平均運行時間(s)

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

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

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

3 結論

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