在線AUC優(yōu)化的線性方法研究.pdf

1、AUC是衡量分類算法性能的重要指標(biāo)之一，被廣泛應(yīng)用于類不平衡學(xué)習(xí)、排序?qū)W習(xí)、異常檢測(cè)和代價(jià)敏感學(xué)習(xí)等任務(wù)中。在線學(xué)習(xí)憑借其處理大規(guī)模數(shù)據(jù)和流數(shù)據(jù)的高效性在機(jī)器學(xué)習(xí)領(lǐng)域受到廣泛關(guān)注。針對(duì)大數(shù)據(jù)環(huán)境下的AUC優(yōu)化問題，研究者提出了諸多在線AUC優(yōu)化算法。
　　在線AUC優(yōu)化的難點(diǎn)在于AUC優(yōu)化的損失函數(shù)由來自不同類別的兩個(gè)樣本構(gòu)成，這使得依賴于損失函數(shù)之和的目標(biāo)函數(shù)與訓(xùn)練樣本數(shù)二次相關(guān)，不能直接使用傳統(tǒng)在線學(xué)習(xí)方法求解。當(dāng)前的在線AU

2、C優(yōu)化算法聚焦于通過在求解過程中避免直接計(jì)算所有的損失函數(shù)，從而減少問題規(guī)模，實(shí)現(xiàn)在線AUC優(yōu)化，但其復(fù)雜度仍然高于同類型的傳統(tǒng)在線學(xué)習(xí)算法。如何能使AUC優(yōu)化的目標(biāo)函數(shù)不再和訓(xùn)練樣本數(shù)二次相關(guān)，僅和訓(xùn)練樣本數(shù)線性相關(guān)，是一個(gè)值得研究的問題。
　　基于最小二乘損失函數(shù)，本文提出了一種AUC優(yōu)化的新目標(biāo)函數(shù)，該目標(biāo)函數(shù)僅與訓(xùn)練樣本數(shù)線性相關(guān)。理論分析表明，最小化該目標(biāo)函數(shù)等價(jià)于最小化由L2正則化項(xiàng)和最小二乘損失函數(shù)組成的AUC優(yōu)化的

3、目標(biāo)函數(shù)。基于該目標(biāo)函數(shù)，本文提出了在線AUC優(yōu)化的線性方法（LOAM）。并根據(jù)不同優(yōu)化求解策略，提出兩種算法：一是使用增量式最小二乘法（ILSC）進(jìn)行優(yōu)化求解的LOAMILSC算法；另一種是使用AdaGrad方法進(jìn)行優(yōu)化求解的LOAMAda算法。其中，LOAMILSC算法的空間復(fù)雜度和每次迭代的復(fù)雜度與ILSC算法相同，LOAMAda算法的空間復(fù)雜度和每次迭代的時(shí)間復(fù)雜度與傳統(tǒng)在線梯度下降算法相同；同時(shí)，這兩種算法都不需要存儲(chǔ)任何歷史