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

朱真峰 翟艷祥 葉陽東

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

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

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

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

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

如何使AUC優(yōu)化的目標函數(shù)不再和訓練樣本數(shù)二次相關(guān)、僅與訓練樣本數(shù)線性相關(guān)是一個值得研究的問題.本文在深入研究現(xiàn)有AUC優(yōu)化算法的基礎(chǔ)上，提出了一種與訓練樣本數(shù)線性相關(guān)的目標函數(shù)；理論推導(dǎo)證明了最小化該目標函數(shù)等價于最小化由L2正則化項和最小二乘損失函數(shù)組成的AUC優(yōu)化的目標函數(shù).基于該目標函數(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種算法都僅需掃描一遍訓練集，不需要存儲任何舊樣本.本文通過大量的實驗驗證了所提算法的有效性.

1 AUC優(yōu)化問題

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

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

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

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

(1)

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

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

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

(2)

(3)

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

定理1. 當式(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).

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

證畢.

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

由第2節(jié)的分析可知，最小化式(3)與最小化式(1)等價，且式(3)與訓練樣本數(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詳細描述了ILSC更新策略.

算法2. ILSC更新策略.

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

輸出：wmt.

② fori=1,2,…,mt

④ ifi=1

⑥ else

⑧ end if

⑨ end for

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

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

算法3. AdaGrad更新策略.

輸出：wmt.

① 初始化：w0=g0=0.

② fori=1,2,…,mt

⑦ end for

4 實驗分析

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

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

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

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

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

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

4.1 基準數(shù)據(jù)集上的實驗結(jié)果

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

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

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

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

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

隨著數(shù)據(jù)集維數(shù)的增加，LOAMILSC,AdaOAM,OPAUC算法的運行時間與LOAMAda算法運行時間之間的差距變大.例如在數(shù)據(jù)集mnist上，LOAMILSC,AdaOAM,OPAUC算法的運行時間是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種算法在基準數(shù)據(jù)集上的AUC結(jié)果

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

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

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

本節(jié)進一步在6個高維稀疏數(shù)據(jù)集(如表3所示)上驗證了LOAMAda算法在處理高維學習任務(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ōu)參數(shù)，OPAUCs算法的參數(shù)選擇范圍參照文獻[28]，步長參數(shù)選擇范圍為2[-12:10]，正則化參數(shù)選擇范圍為2[-10:2]，參數(shù)τ=50.LOAMAda算法的步長參數(shù)選擇范圍為2[-12:10]，正則化參數(shù)選擇范圍為2[-11:1].同樣對每個數(shù)據(jù)集使用5次5折交叉驗證，實驗結(jié)果為測試集上25次AUC的平均值.

Table 3 The Detailed Information of High DimensionalSparse Datasets

表4為LOAMAda和OPAUCs算法在高維稀疏數(shù)據(jù)集上的AUC結(jié)果.由表4所示，LOAMAda算法的平均值高于OPAUCs算法、標準差小于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ù)集上運行時間

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

5 總 結(jié)

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