陳洪

華中農(nóng)業(yè)大學(xué)理學(xué)院, 湖北武漢430070

排序?qū)W習(xí)算法的一般模型研究

陳洪

華中農(nóng)業(yè)大學(xué)理學(xué)院, 湖北武漢430070

排序?qū)W習(xí)問題是機器學(xué)習(xí)與數(shù)據(jù)挖掘領(lǐng)域近來的研究熱點之一。 本文通過分析和比較幾種排序?qū)W習(xí)模型，提出基于這些模型的一般框架，從而為進一步的算法設(shè)計和理論分析奠定基礎(chǔ)。

排序; 機器學(xué)習(xí); 模型選擇

隨著排序機器學(xué)習(xí)算法在信息抽取，信用評價，產(chǎn)品推薦以及病理分析等領(lǐng)域的廣泛應(yīng)用，排序?qū)W習(xí)算法的設(shè)計和理論分析成為機器學(xué)習(xí)研究的熱點課題之一。本文著重研究排序算法設(shè)計中的優(yōu)化目標(biāo)函數(shù)的選擇問題。

一、排序?qū)W習(xí)的一般前提[3]

給定訓(xùn)練數(shù)據(jù)集合A，我們采用有向關(guān)系圖G=(V,E)來表示數(shù)據(jù)間的序關(guān)系。同時用表示假設(shè)函數(shù)集合。詳細來說，關(guān)系如下：

1.訓(xùn)練數(shù)據(jù)

這里描述的排序背景適合于分析和處理許多不同類型的經(jīng)典排序模型。

二、幾種排序模型

本節(jié)介紹幾種常見的排序?qū)W習(xí)的目標(biāo)函數(shù)，基于這些目標(biāo)函數(shù)設(shè)計的排序?qū)W習(xí)算法在經(jīng)驗數(shù)據(jù)實驗中顯示了良好的性能。

1.二劃分排序[1]

二劃分排序問題是一種經(jīng)典的排序問題，這里類別數(shù)只有兩類。學(xué)習(xí)的目的就是使兩類數(shù)據(jù)能順利的區(qū)分開來。其對應(yīng)的優(yōu)化目標(biāo)函數(shù)為

2.K-劃分排序（詳見[2]）

在K-劃分排序排序問題中，給定的樣本往往具有K個序標(biāo)。因此，對應(yīng)的優(yōu)化目標(biāo)函數(shù)為二排序優(yōu)化目標(biāo)函數(shù)的推廣，其表達式如下

雖然基于此目標(biāo)的推廣誤差的界已經(jīng)在[2]中建立，但是該目標(biāo)僅適合處理全相關(guān)的排序情形，在實際應(yīng)用中受到很多限制。

3.推廣的Wilcoxon-Mann-Whitney（WMW）統(tǒng)計

WMW統(tǒng)計原用于獲得分類學(xué)習(xí)問題大偏差的界，近來被引入排序?qū)W習(xí)問題中。推廣的WMW定義如下

基于此目標(biāo)，一類快速的梯度下降算法在[3]中被提出，并且在數(shù)據(jù)實驗中顯示了良好的性能。然而，在實際排序問題中，往往更關(guān)注頂端的排序準(zhǔn)確性，因而推廣該目標(biāo)到關(guān)注頂端排序問題是很有意義的一個課題。

4.p模排序

在文獻[4]中，作者提出了一種新的優(yōu)化目標(biāo)函數(shù)，其優(yōu)點在于能有效的強調(diào)排序問題頂端的排序性能。對應(yīng)的目標(biāo)函數(shù)定義為：

顯然p模排序是基于二排序問題，其應(yīng)用范圍因此也受到較大限制。

三、排序?qū)W習(xí)的一般模型

基于以上幾種排序優(yōu)化函數(shù)，提出如下排序?qū)W習(xí)算法的一般模型：

該目標(biāo)函數(shù)不僅能通過調(diào)整 p值的大小來強調(diào)頂端排序的準(zhǔn)確性，也適合于處理各種排序關(guān)系問題，從而有更廣泛的前景。

同時，從算法的理論分析來看，通過該模型的研究，有助于建立排序?qū)W習(xí)算法推廣性能分析的統(tǒng)一理論基礎(chǔ)，為進一步模型選擇，算法設(shè)計以及參數(shù)選擇提供理論指導(dǎo)。

該目標(biāo)函數(shù)與前面幾種目標(biāo)函數(shù)的關(guān)系總結(jié)如下表：

?

四、小結(jié)

排序?qū)W習(xí)的理論和應(yīng)用研究是近來機器學(xué)習(xí)和數(shù)據(jù)挖掘研究的熱點問題之一。如何設(shè)計合理的算法模型是排序問題的關(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