一種線性的在線AUC優(yōu)化方法

朱真峰 翟艷祥 葉陽東

(鄭州大學(xué)信息工程學(xué)院 鄭州 450052)

AUC(area under the ROC curve)[1]是衡量分類算法性能的重要指標(biāo)之一，被廣泛應(yīng)用于不平衡類的學(xué)習(xí)、代價敏感學(xué)習(xí)、排序?qū)W習(xí)和異常檢測等[2-5].AUC值難以精確計算，通常采用參數(shù)假定、半?yún)?shù)假定或非參數(shù)假定方法進(jìn)行估計.機(jī)器學(xué)習(xí)領(lǐng)域常用非參數(shù)假定方法，其估計在數(shù)值上等價于排序的WMW(Wilcoxon-Mann-Whitney)統(tǒng)計[6].設(shè)計分類算法通常需要將評價指標(biāo)作為優(yōu)化目標(biāo)，使算法的優(yōu)化目標(biāo)與性能評價指標(biāo)一致，以期獲得理想的性能.基于AUC評價指標(biāo)，研究者提出諸多直接優(yōu)化AUC的批處理算法[7-11]，這類算法假設(shè)學(xué)習(xí)之前已經(jīng)得到全部訓(xùn)練數(shù)據(jù).

在線學(xué)習(xí)憑借其處理大規(guī)模數(shù)據(jù)和流數(shù)據(jù)的高效性，在機(jī)器學(xué)習(xí)領(lǐng)域受到廣泛關(guān)注[12-18].傳統(tǒng)在線學(xué)習(xí)方法的目標(biāo)函數(shù)僅需考慮由單個訓(xùn)練樣本構(gòu)成的損失函數(shù)之和;而AUC優(yōu)化的目標(biāo)函數(shù)來自不同類別的樣本對構(gòu)成的損失函數(shù)之和，與訓(xùn)練樣本數(shù)呈二次增長關(guān)系.直接將傳統(tǒng)在線學(xué)習(xí)方法應(yīng)用于AUC優(yōu)化問題，需要存儲所有歷史(舊)樣本，這對于大數(shù)據(jù)分析是不可行的.

為了實(shí)現(xiàn)在線AUC優(yōu)化，研究者提出了多種以AUC為優(yōu)化目標(biāo)的在線學(xué)習(xí)方法[19-23].這些方法可以分為2類：緩沖方法和統(tǒng)計方法.緩沖方法基于緩沖采樣思想，構(gòu)建2個固定大小的緩沖，分別存儲采樣的正負(fù)舊樣本[19-21]，把接收的新樣本存儲在相應(yīng)的緩沖中；如果緩沖滿，采用蓄水池抽樣(reservoir sampling)或先進(jìn)先出(fist-in-first-out)策略，以新樣本替換相應(yīng)緩沖中的舊樣本，并用新樣本與另一個緩沖中的所有樣本構(gòu)成的損失函數(shù)代表新樣本與另一類的所有舊樣本構(gòu)成的損失函數(shù)進(jìn)行計算，更新模型.統(tǒng)計方法通過存儲和更新一階統(tǒng)計量(平均值)和二階統(tǒng)計量(協(xié)方差矩陣)，利用隨機(jī)梯度下降方法[22]或者AdaGrad方法[23]實(shí)現(xiàn)在線AUC優(yōu)化；每次迭代的梯度由新樣本與另一類的所有舊樣本的平均值和協(xié)方差矩陣計算得到.

上述2類方法都是通過在求解過程中避免直接計算所有的損失函數(shù)，以減小問題的規(guī)模.不同之處在于，緩沖方法需要存儲并不斷地掃描緩沖中的樣本，算法的空間復(fù)雜度和每次迭代的時間復(fù)雜度與緩沖大小呈正比關(guān)系.統(tǒng)計方法不需要存儲任何舊樣本，只需要掃描一遍訓(xùn)練集，其存儲規(guī)模獨(dú)立于訓(xùn)練樣本個數(shù)；統(tǒng)計方法涉及協(xié)方差矩陣的存儲和計算，相應(yīng)算法的空間復(fù)雜度和每次迭代的時間復(fù)雜度與樣本維數(shù)平方呈正比關(guān)系，高于傳統(tǒng)在線梯度下降算法[12]、與ONS(online Newton step)[16]相同.

如何使AUC優(yōu)化的目標(biāo)函數(shù)不再和訓(xùn)練樣本數(shù)二次相關(guān)、僅與訓(xùn)練樣本數(shù)線性相關(guān)是一個值得研究的問題.本文在深入研究現(xiàn)有AUC優(yōu)化算法的基礎(chǔ)上，提出了一種與訓(xùn)練樣本數(shù)線性相關(guān)的目標(biāo)函數(shù)；理論推導(dǎo)證明了最小化該目標(biāo)函數(shù)等價于最小化由L2正則化項(xiàng)和最小二乘損失函數(shù)組成的AUC優(yōu)化的目標(biāo)函數(shù).基于該目標(biāo)函數(shù)，本文提出了線性的在線AUC優(yōu)化(linear online AUC maximization， LOAM)方法，并根據(jù)不同的分類器更新策略，給出2種算法：1)采用增量式最小二乘法(incremental least squares classifier， ILSC)[24-25]更新分類器的LOAMILSC算法；2)采用AdaGrad方法[17,23]更新分類器的LOAMAda算法.其中，LOAMILSC算法的空間復(fù)雜度和每次迭代的時間復(fù)雜度與ILSC算法相同，LOAMAda算法的空間復(fù)雜度和每次迭代的時間復(fù)雜度與傳統(tǒng)在線梯度下降算法相同；這2種算法都僅需掃描一遍訓(xùn)練集，不需要存儲任何舊樣本.本文通過大量的實(shí)驗(yàn)驗(yàn)證了所提算法的有效性.

1 AUC優(yōu)化問題

給定一個獨(dú)立同分布的二分類訓(xùn)練樣本集X={(xi,yi)∈d×1×{-1,+1},1≤i≤m}，其中d是樣本維數(shù)，m是樣本個數(shù).樣本集X可以劃分為2個子集：1)所有正樣本構(gòu)成的子集所有負(fù)樣本構(gòu)成的子集-1),1≤j≤m-}，其中m+和m-分別表示正樣本和負(fù)樣本的個數(shù)，m++m-=m.對于給定的決策函數(shù)f(x)，采用非參數(shù)假定的估計，AUC計算為

其中，Γ(k)為指示函數(shù)(indicator function)，如果k為真，則結(jié)果為1，否則結(jié)果為0.AUC反映了隨機(jī)抽取一個正樣本的決策值大于隨機(jī)抽取一個負(fù)樣本的決策值的概率.AUC優(yōu)化的目標(biāo)是在二分類訓(xùn)練樣本集上獲得決策函數(shù)f(x).AUC越大，代表決策函數(shù)f(x)的性能越好.由于Γ(k)非凸，也不連續(xù)，因而無法直接實(shí)現(xiàn)AUC優(yōu)化.實(shí)用的方法一般采用損失替代函數(shù)把AUC優(yōu)化問題轉(zhuǎn)化為凸優(yōu)化問題.AUC優(yōu)化等價于最小化經(jīng)驗(yàn)風(fēng)險(empirical risk)函數(shù):

本文針對二分類問題，構(gòu)建一個線性分類模型.對于線性分類器w，即決策函數(shù)f(x)=wTx，AUC計算為

為了避免過擬合，AUC優(yōu)化通常使用結(jié)構(gòu)風(fēng)險最小化(structural risk minimization, SRM)策略.本文考慮由L2正則化項(xiàng)和最小二乘損失函數(shù)組成的結(jié)構(gòu)風(fēng)險函數(shù)作為目標(biāo)函數(shù)[22-23]，即：

(1)

其中，λ>0是L2正則化參數(shù)，用來控制學(xué)習(xí)模型的復(fù)雜度，常數(shù)12用于在求導(dǎo)時抵消常數(shù)項(xiàng).式(1)有2個優(yōu)點(diǎn)：1)最小二乘損失函數(shù)對AUC優(yōu)化具有一致性；2)可以求得解析解.

2 AUC優(yōu)化的新目標(biāo)函數(shù)

由于傳統(tǒng)分類算法的經(jīng)驗(yàn)風(fēng)險函數(shù)是m個單個樣本構(gòu)成的損失函數(shù)之和的均值，為了減少AUC優(yōu)化問題的規(guī)模，本文把式(1)調(diào)整為分母為m的形式：

(2)

(3)

為了分析式(1)和式(3)之間的關(guān)系，本文采用

定理1. 當(dāng)式(3)的正則化參數(shù)是式(1)的正則化參數(shù)的12時，即最小化式(3)等價于最小化式(1).

證明. 為了區(qū)分式(1)和式(3)，記:

(4)

(5)

對式(4)求偏導(dǎo)，其梯度為

由協(xié)方差矩陣的性質(zhì)可知Cov+,Cov-都是半正定矩陣，又因λI為正定矩陣，CCT為半正定矩陣，所以A和A+CCT為正定矩陣，即A和A+CCT可逆.

對式(5)，同樣求偏導(dǎo)，其梯度:

其中:

所以:

解析解:

同理:

其中，

α1=1(1+CTA-1C)，
α2=2(1+2CTA-1C).

因?yàn)锳是正定矩陣，所以A-1也是正定矩陣.由正定矩陣的性質(zhì)可知，對于任意非0向量C，有CTA-1C>0，因此，α1>0，α2>0.

證畢.

3 在線AUC優(yōu)化的線性方法

由第2節(jié)的分析可知，最小化式(3)與最小化式(1)等價，且式(3)與訓(xùn)練樣本數(shù)線性相關(guān).令:

則式(3)可以轉(zhuǎn)化為

(6)

(7)

在上述分析基礎(chǔ)上，LOAM算法描述見算法1.

算法1. LOAM算法.

輸出：wmt.

② fori=1,2,…,mt

③ 接收新樣本(xi,yi);

④ ifyi=+1

⑥ else

⑧ end if

⑩ 采用ILSC或AdaGrad策略更新分類器wi;

算法2詳細(xì)描述了ILSC更新策略.

算法2. ILSC更新策略.

輸入：正則化參數(shù)λ;

輸出：wmt.

② fori=1,2,…,mt

④ ifi=1

⑥ else

⑧ end if

⑨ end for

第2種分類器更新策略為AdaGrad方法.記gi為第i次迭代時的梯度，gi,j為gi的第j維，η為學(xué)習(xí)率.與在線梯度下降方法對每個特征設(shè)置相同的學(xué)習(xí)率不同，AdaGrad方法使得出現(xiàn)頻率較低的特征具有較高的學(xué)習(xí)率，出現(xiàn)頻率較高的特征具有較低的學(xué)習(xí)率，每一維的迭代更新規(guī)則為

其中，δ>0是平滑參數(shù)，用于避免分母為0，通常設(shè)置一個非常小的值.算法3詳述了AdaGrad更新策略.

算法3. AdaGrad更新策略.

輸出：wmt.

① 初始化：w0=g0=0.

② fori=1,2,…,mt

⑦ end for

4 實(shí)驗(yàn)分析

本文通過基準(zhǔn)數(shù)據(jù)集和高維稀疏數(shù)據(jù)集上的大量實(shí)驗(yàn)驗(yàn)證新算法的有效性，數(shù)據(jù)集來自LIBSVM①,UCI②,SVMLin③.由第2節(jié)分析知，最小化式(3)等價于最小化式(1)，因此本文對比了新算法LOAM和優(yōu)化式(1)的多個在線算法.實(shí)驗(yàn)對比了5個算法：

1) AdaOAM算法.利用AdaGrad方法對式(1)進(jìn)行優(yōu)化求解[23].

2) OPAUC算法.利用隨機(jī)梯度下降方法對式(1)進(jìn)行優(yōu)化求解[22].

3) OPAUCs算法.OPAUC算法的變體，用來處理高維稀疏數(shù)據(jù)任務(wù)[28].

4) LOAMILSC算法.采用增量式最小二乘法更新分類器.

5) LOAMAda算法.采用AdaGrad方法更新分類器.

4.1 基準(zhǔn)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果

16個基準(zhǔn)數(shù)據(jù)集如表1所示包含二類數(shù)據(jù)集和多類數(shù)據(jù)集.AUC是衡量二分類算法性能的評價指標(biāo)，實(shí)驗(yàn)中將多類數(shù)據(jù)集轉(zhuǎn)化為二類數(shù)據(jù)集，表1中的不平衡率(imbalance ratio)統(tǒng)計出了多樣本類與少樣本類的樣本數(shù)之比.

Table 1 The Detailed Information of Benchmark Datasets表1 基準(zhǔn)數(shù)據(jù)集詳細(xì)信息

為了減少隨機(jī)分組對實(shí)驗(yàn)結(jié)果的影響，對每個數(shù)據(jù)集使用5次5折交叉驗(yàn)證，總共實(shí)驗(yàn)25次，實(shí)驗(yàn)結(jié)果是測試集上25次AUC的平均值，記錄方式為“平均值±標(biāo)準(zhǔn)差”.

表2為4種算法在基準(zhǔn)數(shù)據(jù)集上的AUC結(jié)果.由表2知：1)LOAMILSC算法在多數(shù)數(shù)據(jù)集上顯著優(yōu)于LOAMAda,AdaOAM,OPAUC算法.由標(biāo)準(zhǔn)差知，與后者相比，LOAMILSC算法更加穩(wěn)定.2)LOAMAda算法與AdaOAM和OPAUC算法的性能基本相當(dāng).

圖1顯示了4種算法在基準(zhǔn)數(shù)據(jù)集上的運(yùn)行時間(單位ms).其中，橫軸為各個基準(zhǔn)數(shù)據(jù)集，縱軸為對數(shù)坐標(biāo)(log-scale)，4條柱狀圖從左至右依次表示LOAMAda,LOAMILSC,AdaOAM,OPAUC算法的運(yùn)行時間.由圖1知：LOAMAda算法的運(yùn)行效率最高，其次為LOAMILSC算法；AdaOAM和OPAUC算法的運(yùn)行效率最低，且基本相當(dāng).

隨著數(shù)據(jù)集維數(shù)的增加，LOAMILSC,AdaOAM,OPAUC算法的運(yùn)行時間與LOAMAda算法運(yùn)行時間之間的差距變大.例如在數(shù)據(jù)集mnist上，LOAMILSC,AdaOAM,OPAUC算法的運(yùn)行時間是LOAMAda算法的幾十倍甚至上百倍.這是由于LOAMILSC算法涉及逆矩陣的存儲和計算，AdaOAM和OPAUC算法涉及協(xié)方差矩陣的存儲和計算；這3個算法的空間復(fù)雜度和每次迭代的時間復(fù)雜度均為O(d2).對比而言，LOAMAda算法只需要存儲平均值，其空間復(fù)雜度和每次迭代的時間復(fù)雜度僅為O(d).總之，LOAMAda算法的空間復(fù)雜度和每次迭代的時間復(fù)雜度比LOAMILSC,AdaOAM,OPAUC算法低一個量級.

Table 2 The AUC Results of Four Algorithms on Benchmark Datasets表2 4種算法在基準(zhǔn)數(shù)據(jù)集上的AUC結(jié)果

Fig. 1 The runtime of four algorithms on benchmark datasets圖1 4種算法在基準(zhǔn)數(shù)據(jù)集上的運(yùn)行時間

圖1和表2所示的實(shí)驗(yàn)結(jié)果對比表明:LOAMILSC算法的AUC性能最優(yōu)最穩(wěn)定；LOAMAda算法的運(yùn)行效率最高，更適合處理實(shí)時或者高維學(xué)習(xí)任務(wù).

4.2 高維稀疏數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果

本節(jié)進(jìn)一步在6個高維稀疏數(shù)據(jù)集(如表3所示)上驗(yàn)證了LOAMAda算法在處理高維學(xué)習(xí)任務(wù)時的高效性.對于其中的多類數(shù)據(jù)集，將其轉(zhuǎn)為二類不平衡數(shù)據(jù)集.

由于LOAMILSC,AdaOAM,OPAUC算法的空間復(fù)雜度和每次迭代的時間復(fù)雜度均為O(d2)，而6個高維稀疏數(shù)據(jù)集的維數(shù)均超過20 000維，考慮到時間和存儲開銷，本節(jié)只對比了LOAMAda和OPAUCs算法.

與4.1節(jié)相同，本節(jié)采用1次5折交叉驗(yàn)證選擇最優(yōu)參數(shù)，OPAUCs算法的參數(shù)選擇范圍參照文獻(xiàn)[28]，步長參數(shù)選擇范圍為2[-12:10]，正則化參數(shù)選擇范圍為2[-10:2]，參數(shù)τ=50.LOAMAda算法的步長參數(shù)選擇范圍為2[-12:10]，正則化參數(shù)選擇范圍為2[-11:1].同樣對每個數(shù)據(jù)集使用5次5折交叉驗(yàn)證，實(shí)驗(yàn)結(jié)果為測試集上25次AUC的平均值.

Table 3 The Detailed Information of High DimensionalSparse Datasets

表4為LOAMAda和OPAUCs算法在高維稀疏數(shù)據(jù)集上的AUC結(jié)果.由表4所示，LOAMAda算法的平均值高于OPAUCs算法、標(biāo)準(zhǔn)差小于OPAUCs算法.這表明LOAMAda算法的AUC性能優(yōu)于OPAUCs算法且更加穩(wěn)定.

Table 4 The AUC Results of LOAMAda and OPAUCs onHigh Dimensional Sparse Datasets

Fig. 2 The runtime of LOAMAda and OPAUCs on high dimensional sparse datasets圖2 算法LOAMAda和OPAUCs在高維稀疏數(shù)據(jù)集上運(yùn)行時間

圖2為LOAMAda和OPAUCs算法在高維稀疏數(shù)據(jù)集上的運(yùn)行時間(單位s)，其中橫軸為各個高維稀疏數(shù)據(jù)集，縱軸為對數(shù)坐標(biāo)，2條柱狀圖從左至右依次表示LOAMAda,OPAUCs算法的運(yùn)行時間.圖2說明：LOAMAda算法的運(yùn)行時間遠(yuǎn)低于OPAUCs算法的運(yùn)行時間.對比結(jié)果表明LOAMAda算法更為高效，更適合處理高維數(shù)據(jù).

5 總 結(jié)

本文提出一種AUC優(yōu)化的目標(biāo)函數(shù)，最小化該目標(biāo)函數(shù)等價于最小化由L2正則化項(xiàng)和最小二乘損失函數(shù)組成的AUC優(yōu)化的目標(biāo)函數(shù)，但該目標(biāo)函數(shù)僅與訓(xùn)練樣本數(shù)線性相關(guān).基于該目標(biāo)函數(shù)，提出了在線AUC優(yōu)化的線性方法LOAM，并分化出2種LOAM算法：采用增量式最小二乘法更新分類器的LOAMILSC算法和采用AdaGrad方法更新分類器的LOAMAda算法.LOAMILSC算法和LOAMAda算法僅需掃描一遍訓(xùn)練集，不需要存儲任何舊樣本；它們的空間和時間復(fù)雜度分別與ILSC和傳統(tǒng)在線梯度下降算法相同.實(shí)驗(yàn)對比表明，LOAMILSC算法的AUC性能最優(yōu)也最穩(wěn)定，而對于實(shí)時或高維學(xué)習(xí)任務(wù)，LOAMAda算法則更加高效.