欒尋，高尉

（南京大學(xué) 計(jì)算機(jī)軟件新技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室, 南京 210023）

曲線ROC下的面積(簡(jiǎn)稱AUC)是機(jī)器學(xué)習(xí)中一種重要的性能評(píng)價(jià)準(zhǔn)則[1-5]，廣泛應(yīng)用于類別不平衡學(xué)習(xí)、代價(jià)敏感學(xué)習(xí)、信息檢索等諸多學(xué)習(xí)任務(wù)。例如，在郵件協(xié)調(diào)過(guò)濾或人臉識(shí)別中，某些類別的數(shù)據(jù)顯著多于其他類別，而類別不平衡性比例[6]可能為106之多。對(duì)AUC的研究可以追溯至20世紀(jì)70年代的雷達(dá)信號(hào)探測(cè)分析，之后AUC被用于心理學(xué)、醫(yī)學(xué)檢測(cè)以及機(jī)器學(xué)習(xí)。直觀而言，AUC用于衡量一種學(xué)習(xí)算法將訓(xùn)練數(shù)據(jù)中正類數(shù)據(jù)排在負(fù)類數(shù)據(jù)之前的概率。

由于AUC的廣泛實(shí)際應(yīng)用，出現(xiàn)了很多優(yōu)化AUC學(xué)習(xí)方法，如支持向量機(jī)方法[7-8]、集成學(xué)習(xí)boosting算法[9-10]，以及梯度下降算法[11]。這些方法需要存儲(chǔ)整個(gè)訓(xùn)練數(shù)據(jù)集，算法在運(yùn)行時(shí)需要掃描數(shù)據(jù)多遍，因此難以解決大規(guī)模學(xué)習(xí)任務(wù)。在理論方面，AGARWAL和ROTH[12]給出了優(yōu)化AUC可學(xué)習(xí)性的充分條件和必要條件，而GAO和ZHOU[13]則根據(jù)穩(wěn)定性給出了可學(xué)習(xí)性的充要條件。

針對(duì)大規(guī)模AUC優(yōu)化學(xué)習(xí)，ZHAO等[14]于2011年提出優(yōu)化AUC的在線學(xué)習(xí)算法，該方法借助于輔助存儲(chǔ)器，隨機(jī)采取正樣本與負(fù)樣本。而輔助存儲(chǔ)器的大小與數(shù)據(jù)規(guī)模密切相關(guān)，因此很難應(yīng)用于大規(guī)模數(shù)據(jù)或不斷增加的數(shù)據(jù)。為此，GAO等[3]于2013年提出優(yōu)化AUC的單遍學(xué)習(xí)方法，該算法僅需遍歷數(shù)據(jù)一次，通過(guò)存儲(chǔ)一階與二階統(tǒng)計(jì)量?jī)?yōu)化AUC學(xué)習(xí)。

在實(shí)際應(yīng)用中，存儲(chǔ)與計(jì)算二階統(tǒng)計(jì)量依舊需要較高的存儲(chǔ)與計(jì)算開(kāi)銷。因此，本文提出了一種新的優(yōu)化AUC兩遍學(xué)習(xí)算法TPAUC (two-pass AUC optimization)。該算法遍歷數(shù)據(jù)兩遍：第一遍統(tǒng)計(jì)正負(fù)樣本均值，第二遍通過(guò)隨機(jī)梯度方法進(jìn)行優(yōu)化AUC學(xué)習(xí)。新算法只需計(jì)算與存儲(chǔ)一階統(tǒng)計(jì)量，而不需要存儲(chǔ)二階統(tǒng)計(jì)量，從而有效地提高效率，最后本文通過(guò)實(shí)驗(yàn)驗(yàn)證了該算法的有效性。

1 TPAUC學(xué)習(xí)方法

設(shè)示例空間 X ?Rd和 Y分別表示樣本的輸入空間和輸出空間，本文關(guān)注二分類問(wèn)題, 于是有Y={+1,?1}。 假設(shè)D表示空間 X ×Y上潛在的聯(lián)合分布。假設(shè)訓(xùn)練數(shù)據(jù)集為

其中每個(gè)訓(xùn)練樣本是根據(jù)分布 D 獨(dú)立同分布采樣所得。進(jìn)一步假設(shè)分類器 f :X→R為一個(gè)實(shí)值函數(shù)。給定樣本S和函數(shù) f， A UC(f,S)定義為

式中： I [·]為指示函數(shù)，如果判定為真，其返回值為1，否則為0；分別表示訓(xùn)練集中正、負(fù)類樣本的樣本數(shù)。

直接優(yōu)化AUC往往等價(jià)于NP難問(wèn)題，從而導(dǎo)致計(jì)算不可行。在實(shí)際應(yīng)用中，一種可行的方法是對(duì)優(yōu)化表達(dá)式(1)進(jìn)行一種替代損失函數(shù)：

式中 l :R→R+是一個(gè)連續(xù)的凸函數(shù)，常用的函數(shù)包括指數(shù)損失函數(shù)、Hinge損失函數(shù)、Logistic損失函數(shù)等。由于損失函數(shù)定義于一對(duì)正樣本和負(fù)樣本之間，該替代函數(shù)又被稱為“成對(duì)替代損失函數(shù)(pairwise surrogate loss)”。

借鑒于優(yōu)化AUC單遍學(xué)習(xí)算法[3]，本文采用最小二乘損失函數(shù)，即在式(2)中有

為簡(jiǎn)潔起見(jiàn)，不妨假設(shè)樣本總數(shù)為 T，其中正樣本數(shù)為 T+， 負(fù)樣本數(shù)為 T?，以及設(shè)優(yōu)化函數(shù)為

設(shè)正、負(fù)樣例的協(xié)方差矩陣分別為

以及設(shè)正樣例與負(fù)樣例的均值分別為

因此表達(dá)式 L (w)可以進(jìn)一步化簡(jiǎn)、分解為

當(dāng) yt=1時(shí)，有

當(dāng) yt=?1時(shí)，有

考慮在損失函數(shù)中加入正則項(xiàng)，以防止模型過(guò)擬合。本文采用隨機(jī)梯度下降方法[15-19]，因此

只需得到關(guān)于 wt?1的梯度表達(dá)式，而梯度只需對(duì)式(3)中 Lt(w)表達(dá)式直接求導(dǎo)可得。

本文方法的基本流程可以分為兩步：第1步遍歷數(shù)據(jù)，統(tǒng)計(jì)正樣本和負(fù)樣本均值和；第2步遍歷將利用數(shù)據(jù)的均值計(jì)算得到梯度, 然后利用隨機(jī)梯度下降法更新 w而完成優(yōu)化AUC的學(xué)習(xí)，并在實(shí)驗(yàn)中取得很好的效果。

2 實(shí)驗(yàn)驗(yàn)證

本文將在標(biāo)準(zhǔn)真實(shí)數(shù)據(jù)集和高維數(shù)據(jù)集實(shí)驗(yàn)驗(yàn)證所提方法的有效性，其中8個(gè)標(biāo)準(zhǔn)數(shù)據(jù)集分別為diabetes、fourclass、german、splice、usps、letter、magic04、a9a。數(shù)據(jù)集中樣本數(shù)量從768～32 561不等，樣本維度的范圍從8～256。所有數(shù)據(jù)集的特征都被規(guī)范到[-1, 1]，多分類問(wèn)題被轉(zhuǎn)變?yōu)閮煞诸悊?wèn)題，隨機(jī)將類別劃分成兩類。

TPAUC算法的學(xué)習(xí)率參數(shù) η和正則化參數(shù) λ范圍都為 {2?10,2?9,2?8,···,2,4}。首先將數(shù)據(jù)集劃分為訓(xùn)練集和測(cè)試集，參數(shù)的選擇通過(guò)在訓(xùn)練集上進(jìn)行五折交叉驗(yàn)證來(lái)確定。選定參數(shù)后，再在測(cè)試集上進(jìn)行5遍五折交叉驗(yàn)證，將這25次的結(jié)果取平均值作為最終的測(cè)試結(jié)果。

本文比較了如下5種算法：

1) OPAUC：優(yōu)化AUC單遍學(xué)習(xí)算法[3]。

2) OAMseq：優(yōu)化AUC的在線學(xué)習(xí)算法[14]。

3) OAMgra：優(yōu)化AUC的在線學(xué)習(xí)算法[14]。

4) Online Uni-Exp：優(yōu)化加權(quán)單變量指數(shù)損失函數(shù)[20]。

5) Online Uni-Squ：優(yōu)化加權(quán)單變量平方損失函數(shù)[20]。

實(shí)驗(yàn)結(jié)果如表1所示，不難發(fā)現(xiàn)，本文提出的優(yōu)化AUC兩遍學(xué)習(xí)方法TPAUC性能與OPAUC相當(dāng)， 但明顯優(yōu)于 OAMseq、OAMgra、Online Uni-Exp以及Online Uni-Squ。

本文選用8個(gè)高維稀疏數(shù)據(jù)集，分別為realsim、rcv、rcv1v2、sector、sector.lvr、news20、ecml2012、news20.b。數(shù)據(jù)集中樣本數(shù)量從9 619～456 886不等。特征維度的范圍為20 985～1 355 191。實(shí)驗(yàn)設(shè)置與標(biāo)準(zhǔn)數(shù)據(jù)集相似， 實(shí)驗(yàn)結(jié)果如表2所示。可以發(fā)現(xiàn)，TPAUC算法在高維稀疏數(shù)據(jù)上與其他算法的效果具有可比性或性能更優(yōu)。

表1 TPAUC在低維數(shù)據(jù)集上性能比較Table 1 Comparisons of TPAUC on low-dim. datasets

表2 TPAUC在高維數(shù)據(jù)集上性能比較Table 2 Comparisons of TPAUC on high-dim. datasets

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

ROC曲線下的面積(簡(jiǎn)稱AUC)是機(jī)器學(xué)習(xí)中一種重要的性能評(píng)價(jià)準(zhǔn)則，由于AUC定義于正負(fù)樣本之間，傳統(tǒng)方法需存儲(chǔ)整個(gè)數(shù)據(jù)而不能適用于大數(shù)據(jù)。為此Gao等提出優(yōu)化AUC的單遍學(xué)習(xí)算法，該算法僅需遍歷數(shù)據(jù)一次，通過(guò)存儲(chǔ)一階與二階統(tǒng)計(jì)量來(lái)進(jìn)行優(yōu)化AUC學(xué)習(xí)。本文致力于減少二階統(tǒng)計(jì)量的計(jì)算與存儲(chǔ)開(kāi)銷，提出一種新的優(yōu)化AUC兩遍學(xué)習(xí)算法TPAUC。新提出的算法只需計(jì)算與存儲(chǔ)一階統(tǒng)計(jì)量，而不需要存儲(chǔ)二階統(tǒng)計(jì)量，從而有效地提高效率，最后本文通過(guò)實(shí)驗(yàn)驗(yàn)證了該算法的有效性。