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

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

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

0 引言

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

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

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

1 DKOAM方法介紹

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

1.1 核表示

(1)

那么核函數可以表示成對應于變量u的期望函數:

κ(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)

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

1.2 在線AUC最大化

AUC(w)=

(3)

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

(4)

那么可以通過最小化下面這個目標函數來得到最優的分類器：

(5)

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

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

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

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

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

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

2：fort=1,2,…,T

10： else

14： end if

16：end for

中心節點：

1：輸入：學習率η

2：fort=1,2,…,T

5：end for

2 實驗驗證與分析

本節對提出的DKOAM算法在3個標準數據集上與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種標準數據集上進行測試。數據集的特征都重新調整到[-1,1]之間。多分類數據集(letter和acoustic)轉化為二分類數據集，即隨機選擇一類作為正樣本，其他類作為負樣本。數據集的具體特征見表1。

表1 數據集特征

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

2.3 實驗結果

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

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

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

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

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

圖2 在數據集letter上的收斂速率比較

3 結論

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