陳洪
華中農(nóng)業(yè)大學(xué)理學(xué)院, 湖北武漢430070
排序?qū)W習(xí)算法的一般模型研究
陳洪
華中農(nóng)業(yè)大學(xué)理學(xué)院, 湖北武漢430070
排序?qū)W習(xí)問題是機(jī)器學(xué)習(xí)與數(shù)據(jù)挖掘領(lǐng)域近來的研究熱點(diǎn)之一。 本文通過分析和比較幾種排序?qū)W習(xí)模型,提出基于這些模型的一般框架,從而為進(jìn)一步的算法設(shè)計(jì)和理論分析奠定基礎(chǔ)。
排序; 機(jī)器學(xué)習(xí); 模型選擇
隨著排序機(jī)器學(xué)習(xí)算法在信息抽取,信用評(píng)價(jià),產(chǎn)品推薦以及病理分析等領(lǐng)域的廣泛應(yīng)用,排序?qū)W習(xí)算法的設(shè)計(jì)和理論分析成為機(jī)器學(xué)習(xí)研究的熱點(diǎn)課題之一。本文著重研究排序算法設(shè)計(jì)中的優(yōu)化目標(biāo)函數(shù)的選擇問題。
給定訓(xùn)練數(shù)據(jù)集合A,我們采用有向關(guān)系圖G=(V,E)來表示數(shù)據(jù)間的序關(guān)系。同時(shí)用表示假設(shè)函數(shù)集合。詳細(xì)來說,關(guān)系如下:
這里描述的排序背景適合于分析和處理許多不同類型的經(jīng)典排序模型。
本節(jié)介紹幾種常見的排序?qū)W習(xí)的目標(biāo)函數(shù),基于這些目標(biāo)函數(shù)設(shè)計(jì)的排序?qū)W習(xí)算法在經(jīng)驗(yàn)數(shù)據(jù)實(shí)驗(yàn)中顯示了良好的性能。
二劃分排序問題是一種經(jīng)典的排序問題,這里類別數(shù)只有兩類。學(xué)習(xí)的目的就是使兩類數(shù)據(jù)能順利的區(qū)分開來。其對(duì)應(yīng)的優(yōu)化目標(biāo)函數(shù)為
在K-劃分排序排序問題中,給定的樣本往往具有K個(gè)序標(biāo)。因此,對(duì)應(yīng)的優(yōu)化目標(biāo)函數(shù)為二排序優(yōu)化目標(biāo)函數(shù)的推廣,其表達(dá)式如下
雖然基于此目標(biāo)的推廣誤差的界已經(jīng)在[2]中建立,但是該目標(biāo)僅適合處理全相關(guān)的排序情形,在實(shí)際應(yīng)用中受到很多限制。
WMW統(tǒng)計(jì)原用于獲得分類學(xué)習(xí)問題大偏差的界,近來被引入排序?qū)W習(xí)問題中。推廣的WMW定義如下
基于此目標(biāo),一類快速的梯度下降算法在[3]中被提出,并且在數(shù)據(jù)實(shí)驗(yàn)中顯示了良好的性能。然而,在實(shí)際排序問題中,往往更關(guān)注頂端的排序準(zhǔn)確性,因而推廣該目標(biāo)到關(guān)注頂端排序問題是很有意義的一個(gè)課題。
在文獻(xiàn)[4]中,作者提出了一種新的優(yōu)化目標(biāo)函數(shù),其優(yōu)點(diǎn)在于能有效的強(qiáng)調(diào)排序問題頂端的排序性能。對(duì)應(yīng)的目標(biāo)函數(shù)定義為:
顯然p模排序是基于二排序問題,其應(yīng)用范圍因此也受到較大限制。
基于以上幾種排序優(yōu)化函數(shù),提出如下排序?qū)W習(xí)算法的一般模型:
該目標(biāo)函數(shù)不僅能通過調(diào)整 p值的大小來強(qiáng)調(diào)頂端排序的準(zhǔn)確性,也適合于處理各種排序關(guān)系問題,從而有更廣泛的前景。
同時(shí),從算法的理論分析來看,通過該模型的研究,有助于建立排序?qū)W習(xí)算法推廣性能分析的統(tǒng)一理論基礎(chǔ),為進(jìn)一步模型選擇,算法設(shè)計(jì)以及參數(shù)選擇提供理論指導(dǎo)。
該目標(biāo)函數(shù)與前面幾種目標(biāo)函數(shù)的關(guān)系總結(jié)如下表:
?
排序?qū)W習(xí)的理論和應(yīng)用研究是近來機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘研究的熱點(diǎn)問題之一。如何設(shè)計(jì)合理的算法模型是排序問題的關(guān)鍵。本文結(jié)合已有的模型,給出了一般條件下的優(yōu)化目標(biāo)模型。該模型適用更廣泛的應(yīng)用領(lǐng)域,且有助于建立排序?qū)W習(xí)算法統(tǒng)一的理論基礎(chǔ)。
[1]S.Agarwal, et.al.Generalization bounds for the area under the ROC curve[J].JMLR,2005,6:393-425
[2]S.Rajaram,S.Agarwal.Generalization bounds for k-partite ranking[J].In NIPS, 2005
[3]V.C.Raykar, et.al.A fast algorithm for learning a ranking function from large-scale data sets[J].TPAMI, 2009, 30:1158--1170
[4]C.Rudin.The p-norm push: a simple convex ranking algorithm that concentates at the top of the list[J].JMLR, 2009,10:2233--2271
TP181
A
10.3969/j.issn.1001-8972.2011.13.081