排序?qū)W習(xí)研究進(jìn)展與展望

李金忠 劉關(guān)俊 閆春鋼 蔣昌俊

隨著互聯(lián)網(wǎng)和云計(jì)算技術(shù)的迅猛發(fā)展以及網(wǎng)絡(luò)用戶規(guī)模的爆發(fā)式增長(zhǎng),互聯(lián)網(wǎng)已經(jīng)步入了“大數(shù)據(jù)”時(shí)代.中國(guó)互聯(lián)網(wǎng)信息中心發(fā)布第39次中國(guó)互聯(lián)網(wǎng)絡(luò)發(fā)展?fàn)顩r統(tǒng)計(jì)報(bào)告指出,截至2016年12月底,我國(guó)網(wǎng)頁(yè)數(shù)量為2360億,網(wǎng)民規(guī)模達(dá)7.31億,搜索引擎用戶規(guī)模超過5.93億.面對(duì)互聯(lián)網(wǎng)上如此海量繁雜的網(wǎng)絡(luò)大數(shù)據(jù)與千差萬別的網(wǎng)絡(luò)搜索用戶,傳統(tǒng)的信息檢索模型、機(jī)器學(xué)習(xí)方法在搜索引擎系統(tǒng)中的應(yīng)用面臨著極大的挑戰(zhàn).如何從互聯(lián)網(wǎng)上的海量數(shù)據(jù)中,準(zhǔn)確、及時(shí)、高效地獲取用戶所需信息是信息檢索研究的主要問題,其本質(zhì)即是信息的排序問題.排序是信息檢索和很多實(shí)際應(yīng)用如搜索引擎和推薦系統(tǒng)等所面臨的核心問題,排序模型在互聯(lián)網(wǎng)搜索和推薦中起著關(guān)鍵作用,其排序性能的優(yōu)劣直接影響互聯(lián)網(wǎng)用戶使用搜索引擎和推薦系統(tǒng)的體驗(yàn).因此,針對(duì)排序技術(shù)的研究是基礎(chǔ)且關(guān)鍵的研究問題之一.

傳統(tǒng)的信息檢索排序模型主要有相關(guān)性排序模型和重要性排序模型.相關(guān)性排序模型主要包括布爾模型、向量空間模型和概率檢索模型(BM25和統(tǒng)計(jì)語言模型),重要性排序模型主要包括PageRank算法[1]、HITS算法[2]、TrustRank算法[3]、BrowseRank算法[4]和ClickRank算法[5]等網(wǎng)頁(yè)排名算法模型.

這些傳統(tǒng)的排序模型的構(gòu)建過程一般通過人工依據(jù)經(jīng)驗(yàn)去調(diào)整排序模型中所涉及到的一些參數(shù),但這些經(jīng)驗(yàn)參數(shù)不易調(diào)節(jié)且易產(chǎn)生過擬合;另一方面,盡管這些不同的排序模型大體上都使得排序效果得到了一定的性能提升,但如何將不同排序模型融合在一起以構(gòu)建一個(gè)性能更優(yōu)的統(tǒng)一排序模型,并不易于處理.同時(shí),隨著影響排序性能的排序特征的不斷增加,排序特征已有成百上千種,傳統(tǒng)的排序模型的構(gòu)建方法已不再適于處理如此多維和復(fù)雜的排序特征.而機(jī)器學(xué)習(xí)方法具有能自動(dòng)調(diào)整參數(shù),融合多個(gè)模型的結(jié)果,通過規(guī)則化的方式避免過擬合等優(yōu)點(diǎn).在如此背景下,涌現(xiàn)了大量的研究者運(yùn)用不同的機(jī)器學(xué)習(xí)技術(shù)去訓(xùn)練排序模型以解決信息檢索中的排序問題,并由此產(chǎn)生了信息檢索與機(jī)器學(xué)習(xí)交叉的一個(gè)熱點(diǎn)研究領(lǐng)域—排序?qū)W習(xí)(Learning to rank).排序?qū)W習(xí)就是利用機(jī)器學(xué)習(xí)方法在排序?qū)W習(xí)數(shù)據(jù)集上進(jìn)行訓(xùn)練,自動(dòng)產(chǎn)生排序模型,從而解決排序問題.和傳統(tǒng)排序模型相比,排序?qū)W習(xí)的優(yōu)勢(shì)在于對(duì)眾多排序特征進(jìn)行組合優(yōu)化,對(duì)相應(yīng)的大量參數(shù)自動(dòng)進(jìn)行學(xué)習(xí),最終得到一個(gè)高效精準(zhǔn)、更加優(yōu)化的排序模型.

排序?qū)W習(xí)是信息檢索和機(jī)器學(xué)習(xí)交叉的一個(gè)研究熱點(diǎn).近幾年,SIGIR、WWW、WSDM、CIKM等國(guó)際頂級(jí)會(huì)議將Learning to rank作為一個(gè)主要的Session或Track,特別是在2012年的SIGIR大會(huì)上,最佳論文榮譽(yù)提名獎(jiǎng)[6]和最佳學(xué)生論文獎(jiǎng)[7]都頒給了Learning to rank方面的論文,SIGIR2015、CIKM2016、KDD2016和 WSDM2016等的最佳(學(xué)生)論文獎(jiǎng)也頒給了Learning to rank方面的論文[8?11].2010年,Springer期刊Information retrieval以特刊形式在其上刊登了“Learning to rank for information retrieval”[12].同年,Yahoo舉辦了Yahoo!Learning to Rank Challenge[13]比賽.很多知名的搜索引擎公司、推薦系統(tǒng)和大型電子商務(wù)平臺(tái)等在很大程度上依賴于排序?qū)W習(xí)方法為用戶提供高質(zhì)量的搜索和推薦結(jié)果.

對(duì)排序?qū)W習(xí)的研究方興未艾,不僅具有重要的理論研究?jī)r(jià)值,也具有廣闊的實(shí)際應(yīng)用前景.盡管排序?qū)W習(xí)在學(xué)術(shù)界取得了大量的研究成果和在工業(yè)界取得了令人矚目的成功,但在排序?qū)W習(xí)的研究領(lǐng)域中仍還有許多相關(guān)的問題有待更全面深入地探討.鑒于此,本文詳細(xì)分析了當(dāng)前排序?qū)W習(xí)的研究進(jìn)展,并重點(diǎn)對(duì)排序?qū)W習(xí)的發(fā)展趨勢(shì)和有待深入研究的重難點(diǎn)進(jìn)行了展望,以示拋磚引玉.

本文第1節(jié)描述了排序?qū)W習(xí)問題;第2節(jié)對(duì)排序?qū)W習(xí)方法進(jìn)行了分類;第3節(jié)到第5節(jié)分別歸納了排序?qū)W習(xí)的數(shù)據(jù)集、方法應(yīng)用和方法軟件包.第6節(jié)展望了發(fā)展趨勢(shì);第7節(jié)對(duì)全文進(jìn)行了總結(jié).

1 排序?qū)W習(xí)問題描述

排序?qū)W習(xí)是利用機(jī)器學(xué)習(xí)方法在數(shù)據(jù)集上對(duì)大量的排序特征進(jìn)行組合訓(xùn)練,自動(dòng)學(xué)習(xí)參數(shù),優(yōu)化評(píng)價(jià)指標(biāo)以產(chǎn)生排序模型.

圖1展示了排序?qū)W習(xí)的一個(gè)典型框架,該框架涉及排序?qū)W習(xí)的三個(gè)重要方面—數(shù)據(jù)集、方法和評(píng)價(jià)指標(biāo).排序?qū)W習(xí)數(shù)據(jù)集主要包括訓(xùn)練集(Training set)和測(cè)試集(Test set),通常也包括驗(yàn)證集(Validation set).訓(xùn)練集用來訓(xùn)練排序模型,驗(yàn)證集用來選擇排序模型(若沒有驗(yàn)證集,則訓(xùn)練集也用來選擇排序模型),而測(cè)試集則用來檢驗(yàn)最終選擇的排序模型的性能.排序?qū)W習(xí)數(shù)據(jù)集由若干維排序特征數(shù)據(jù)和若干等級(jí)的相關(guān)性標(biāo)注數(shù)據(jù)構(gòu)成.排序特征數(shù)據(jù)x描述了查詢–文檔對(duì)q,d〉的特征表示,如tf、idf、BM25、PageRank等特征值;相關(guān)性標(biāo)注數(shù)據(jù)y描述了文檔與對(duì)應(yīng)查詢的相關(guān)性程度,如兩級(jí)標(biāo)注(0和1)或多級(jí)標(biāo)注(0、1、2、3、4等).相關(guān)性標(biāo)注數(shù)據(jù)多采用人工判斷給定(顯式標(biāo)注),也可利用點(diǎn)擊數(shù)據(jù)等獲得(隱式標(biāo)注).排序?qū)W習(xí)方法從排序?qū)W習(xí)數(shù)據(jù)集中學(xué)習(xí)并獲取排序模型,其主要有Pointwise、Pairwise和Listwise三大類,而采用的機(jī)器學(xué)習(xí)技術(shù)主要有感知機(jī)、神經(jīng)網(wǎng)絡(luò)、支持向量機(jī)、Boosting、樹、極限學(xué)習(xí)機(jī)、貝葉斯和進(jìn)化算法等.排序?qū)W習(xí)評(píng)價(jià)指標(biāo)用于度量排序模型的性能,如信息檢索中常用的準(zhǔn)確率(Precesion,P)、召回率(Recall,R)、平均精度均值(Mean average precision,MAP)、歸一化折扣累積增益(Normalized discounted cumulated gain,NDCG)、期望倒數(shù)排序(Expected reciprocal rank,ERR)等.典型排序?qū)W習(xí)框架包含一個(gè)學(xué)習(xí)系統(tǒng)(Learning system)和一個(gè)排序系統(tǒng)(Ranking system).在學(xué)習(xí)系統(tǒng)中,通過排序?qū)W習(xí)方法從訓(xùn)練集中學(xué)習(xí)排序模型并最終獲得最優(yōu)排序模型;在排序系統(tǒng)中,利用訓(xùn)練出來的最優(yōu)排序模型對(duì)測(cè)試集進(jìn)行排序預(yù)測(cè),并通過信息檢索評(píng)價(jià)指標(biāo)進(jìn)行度量.從整個(gè)排序?qū)W習(xí)框架來看,最終獲得的排序模型的性能取決于訓(xùn)練集(若包含驗(yàn)證集,則取決于訓(xùn)練集和驗(yàn)證集)、排序?qū)W習(xí)方法和評(píng)價(jià)指標(biāo).在同一數(shù)據(jù)集上,不同的排序?qū)W習(xí)方法在不同評(píng)價(jià)指標(biāo)上其性能表現(xiàn)有所差異;在不同數(shù)據(jù)集上,同一排序?qū)W習(xí)方法在不同評(píng)價(jià)指標(biāo)上其性能表現(xiàn)也將會(huì)略有不同.

2 排序?qū)W習(xí)方法分類

從不同的角度,依據(jù)不同的分類標(biāo)準(zhǔn)可以將現(xiàn)有排序?qū)W習(xí)方法劃分成不同的類型,如依據(jù)輸入數(shù)據(jù)樣例或依據(jù)采用機(jī)器學(xué)習(xí)技術(shù)的不同,可劃分成如圖2所示的類別.

2.1 依輸入數(shù)據(jù)樣例的分類

按照訓(xùn)練模型時(shí)輸入數(shù)據(jù)樣例的不同,Liu[14]和Li[15]將排序?qū)W習(xí)方法分為3大類:Pointwise(單文檔)、Pairwise(文檔對(duì))、Listwise(文檔列表).

在Pointwise方法中,將訓(xùn)練集中每一個(gè)查詢下的每一個(gè)文檔看做一個(gè)訓(xùn)練樣例,其輸入是單個(gè)文檔,包括每個(gè)文檔的特征.Pointwise方法把排序問題轉(zhuǎn)換成分類問題(二值、多值)、回歸問題或序數(shù)回歸問題求解,其目的是將訓(xùn)練樣例盡可能準(zhǔn)確地映射到區(qū)間里.

在Pairwise方法中,將訓(xùn)練集中的每一個(gè)查詢下的任意兩個(gè)具有偏序關(guān)系的文檔對(duì)作為一個(gè)訓(xùn)練樣例,其輸入是文檔對(duì).Pairwise方法把排序問題主要看成為一個(gè)二分類問題,它考慮文檔對(duì)之間的偏序關(guān)系,更接近排序問題的實(shí)質(zhì).訓(xùn)練排序模型的目標(biāo)是去追求排序結(jié)果列表中不正確的偏序?qū)ΡM量的少,越少則表明越好.若學(xué)習(xí)后獲得的文檔對(duì)的偏序關(guān)系和它們的真實(shí)文檔對(duì)的偏序關(guān)系是完全一致的,則說明結(jié)果完全正確.

圖1 排序?qū)W習(xí)典型框架[14]Fig.1 A typical framework of learning to rank[14]

圖2 排序?qū)W習(xí)方法分類Fig.2 Categories of the learning to rank approaches

在Listwise方法中,輸入不再是單個(gè)文檔或文檔對(duì),而是一組文檔列表,是將每一個(gè)查詢下對(duì)應(yīng)的所有文檔的排序結(jié)果列表作為一個(gè)訓(xùn)練樣例,更加全面地考慮了同一查詢下不同文檔的序列關(guān)系.Listwise方法以不同的方式度量文檔排序序列的排序效果,訓(xùn)練排序模型的目標(biāo)是使得結(jié)果列表與真實(shí)列表中文檔排序順序越接近越好.Listwise方法也可再細(xì)分為兩類:直接優(yōu)化基于排序列表的損失的Listwise方法和直接優(yōu)化信息檢索評(píng)價(jià)指標(biāo)的Listwise方法.前類Listwise方法繼承了Pointwise和Pairwise方法的研究思路,通過定義Listwise損失函數(shù)并最優(yōu)化該損失函數(shù)而求得排序模型,其損失函數(shù)構(gòu)造為用于衡量預(yù)測(cè)的文檔序列與真實(shí)的文檔序列之間的差異.后類Listwise方法將排序模型的構(gòu)建與信息檢索中的評(píng)價(jià)指標(biāo)建立起關(guān)聯(lián),獲得了最優(yōu)評(píng)價(jià)值的排序模型被認(rèn)為是最優(yōu)排序模型,其基本思想是先定義信息檢索中某個(gè)具體的評(píng)價(jià)準(zhǔn)則(如NDCG等)的優(yōu)化目標(biāo),再選擇適當(dāng)?shù)臋C(jī)器學(xué)習(xí)方法和優(yōu)化算法去學(xué)習(xí)排序模型以構(gòu)建更能滿足用戶需求的最優(yōu)排序模型.

表1從排序?qū)W習(xí)的輸入數(shù)據(jù)、樣本復(fù)雜度、所轉(zhuǎn)化的主要問題和所具有的特點(diǎn)4個(gè)方面總結(jié)了Pointwise、Pairwise和Listwise三大類排序?qū)W習(xí)方法.實(shí)踐經(jīng)驗(yàn)結(jié)果表明,基于Listwise排序?qū)W習(xí)方法的排序模型的有效性通常要優(yōu)于Pointwise和Pairwise這兩大類排序?qū)W習(xí)方法的[14?15].當(dāng)前,Listwise排序?qū)W習(xí)方法已成為近年來被研究最多的方法.

2.2 依采用機(jī)器學(xué)習(xí)技術(shù)的分類

依據(jù)訓(xùn)練模型時(shí)所采用機(jī)器學(xué)習(xí)技術(shù)的不同,我們將排序?qū)W習(xí)方法分為以下幾類:基于感知機(jī)、基于神經(jīng)網(wǎng)絡(luò)、基于支持向量機(jī)、基于極限學(xué)習(xí)機(jī)、基于貝葉斯、基于提升、基于樹、基于進(jìn)化算法的排序?qū)W習(xí)方法和其他排序?qū)W習(xí)方法等.

2.2.1 基于感知機(jī)的排序?qū)W習(xí)方法

感知機(jī)(Perceptron)是一種二分類的線性判別模型,對(duì)應(yīng)輸入空間中將實(shí)例劃分為正例和負(fù)例兩類的分離超平面w·x?b=0,其輸入和輸出分別為樣本實(shí)例的特征向量和類別.感知機(jī)學(xué)習(xí)旨在追求一個(gè)能夠?qū)⒂?xùn)練數(shù)據(jù)完全正確線性劃分的正、負(fù)例分離超平面,即通過學(xué)習(xí)策略最小化風(fēng)險(xiǎn)以優(yōu)化模型參數(shù)w和b,從而對(duì)新的實(shí)例實(shí)現(xiàn)準(zhǔn)確預(yù)測(cè).感知機(jī)是神經(jīng)網(wǎng)絡(luò)與支持向量機(jī)的基礎(chǔ).

PRank[16]是基于感知機(jī)的排序?qū)W習(xí)方法的代表之一,它是一種基于感知機(jī)同時(shí)在線學(xué)習(xí)線性模型的排序?qū)W習(xí)方法.該方法的基本思想是利用大量的并行感知機(jī)同時(shí)在線學(xué)習(xí)線性模型,每個(gè)模型在相鄰等級(jí)之間做分類,旨在找到一個(gè)能成功將全部訓(xùn)練樣例準(zhǔn)確映射到所定義的k個(gè)區(qū)間內(nèi)的感知機(jī)模型.PRank方法的目標(biāo)是最小化排序損失,希望預(yù)測(cè)排序盡可能接近真實(shí)排序.它通過迭代學(xué)習(xí)來實(shí)現(xiàn),在第t次迭代中,排序模型獲取與查詢q相關(guān)的文檔的排序值xt,算法預(yù)測(cè)其分值ηt=minr∈{1,···,k}{r:wt·xt?btr＜0}, 并獲取其真實(shí)排序值yt.如果排序模型將xt的分類預(yù)測(cè)為ηt而不是yt,那么wt·xt的值在btr的錯(cuò)誤方,則需修改w和b的值以更新排序規(guī)則;否則,設(shè)置wt+1=wt,?r:btr+1=btr.重復(fù)迭代,直到訓(xùn)練過程結(jié)束, 最終輸出H(x)=minr∈{1,···,k}{r:wT+1·x?bTr+1＜0}.PRank方法直觀簡(jiǎn)單,其正確性和收斂性在理論上得到了證明.

文獻(xiàn)[17?18]等也利用感知機(jī)設(shè)計(jì)排序?qū)W習(xí)方法.Gao等[17]提出了基于感知機(jī)的算法LDM(Percep)以最小化排序列表中不一致文檔對(duì)的數(shù)量.Xia等[18]針對(duì)只利用“正例”排序進(jìn)行訓(xùn)練的關(guān)系排序?qū)W習(xí)方法R-LTR,進(jìn)一步改進(jìn)關(guān)系排序模型,提出了基于結(jié)構(gòu)化感知機(jī)的排序?qū)W習(xí)方法PAMM.

基于感知機(jī)的排序?qū)W習(xí)方法簡(jiǎn)單且易于實(shí)現(xiàn),并可從數(shù)學(xué)上嚴(yán)格證明算法的收斂性,但收斂速度較慢.設(shè)計(jì)基于感知機(jī)的排序?qū)W習(xí)方法的難點(diǎn)在于損失函數(shù)的定義及如何最小化損失函數(shù).

表1 Pointwise、Pairwise和Listwise排序?qū)W習(xí)方法對(duì)比Table 1 Comparison of Pointwise,Pairwise and Listwise learning to rank approaches

2.2.2 基于神經(jīng)網(wǎng)絡(luò)的排序?qū)W習(xí)方法

神經(jīng)網(wǎng)絡(luò)(Neural network,NN)是感知機(jī)的無環(huán)網(wǎng)絡(luò),其中一些感知機(jī)的輸出結(jié)果又作為其他感知機(jī)的輸入.NN的主要思想是在給定的訓(xùn)練樣本下,通過模仿生物神經(jīng)網(wǎng)絡(luò)所出現(xiàn)的一些屬性,試圖構(gòu)建一個(gè)能優(yōu)化分離數(shù)據(jù)成正例和反例的n維決策邊界面.它根據(jù)訓(xùn)練數(shù)據(jù)來調(diào)整神經(jīng)元之間的“連接權(quán)重”以及每個(gè)功能神經(jīng)元的閾值,其學(xué)習(xí)過程中需使用一些優(yōu)化方法,如梯度下降法,以找到一個(gè)能最大限度地減少錯(cuò)誤分類數(shù)量的解.

RankNet[19]是基于神經(jīng)網(wǎng)絡(luò)的排序?qū)W習(xí)方法的代表之一,該方法依賴于每一個(gè)文檔對(duì),定義了一個(gè)基于概率的損失函數(shù),運(yùn)用神經(jīng)網(wǎng)絡(luò)和梯度下降法試圖最小化一個(gè)交叉熵?fù)p失函數(shù).在RankNet中,給定關(guān)聯(lián)于偏序文檔xu和xv,基于真實(shí)標(biāo)注構(gòu)建目標(biāo)概率,它表示文檔xu排在文檔xv前面的概率;基于由評(píng)分函數(shù)f計(jì)算文檔的評(píng)分差異定義模型概率Pu,v,即;在文檔對(duì)上定義損失函數(shù)為目標(biāo)概率和模型概率之間的交叉熵,即,最終目的是優(yōu)化C的總和,使損失函數(shù)最小.在RankNet中,神經(jīng)網(wǎng)絡(luò)用于建模,梯度下降法作為優(yōu)化算法去學(xué)習(xí)評(píng)分函數(shù).優(yōu)化過程中,在訓(xùn)練數(shù)據(jù)上使用當(dāng)前網(wǎng)絡(luò)去計(jì)算評(píng)分,使用計(jì)算損失,基于相關(guān)計(jì)算公式更新網(wǎng)絡(luò)參數(shù).由于RankNet的訓(xùn)練數(shù)據(jù)為各查詢下若干文檔對(duì),因此需針對(duì)文檔對(duì)的輸入去調(diào)整神經(jīng)網(wǎng)絡(luò)的權(quán)值.

RankNet不僅在理論上是一個(gè)很好的模型,而且是第一個(gè)應(yīng)用于互聯(lián)網(wǎng)搜索引擎的排序?qū)W習(xí)方法,微軟已經(jīng)將RankNet技術(shù)應(yīng)用于其搜索引擎必應(yīng)(Bing)中.為了改進(jìn)RankNet,研究者們又提出了FRank和LambdaRank等排序?qū)W習(xí)方法以追求更好的排序結(jié)果.FRank[20]與RankNet的區(qū)別在于所使用的損失函數(shù)不同,它采用的是 fidelity函數(shù)作為損失函數(shù).LambdaRank[21]是基于RankNet的改進(jìn)方法,對(duì)梯度的計(jì)算方式引入信息檢索評(píng)價(jià)指標(biāo)NDCG,針對(duì)迭代過程中所生成的文檔列表以及相應(yīng)的NDCG取值的變化情況來確定每個(gè)文檔對(duì)的梯度,從而體現(xiàn)如何調(diào)整文檔之間的相對(duì)順序以最大化NDCG,希望所構(gòu)建的相應(yīng)損失函數(shù)能與最終的評(píng)價(jià)準(zhǔn)則盡可能相一致.

文獻(xiàn)[22?25]等也是基于神經(jīng)網(wǎng)絡(luò)的排序?qū)W習(xí)方法.ListNet[22]是基于神經(jīng)網(wǎng)絡(luò)和梯度下降的排序?qū)W習(xí)方法,它將排序問題看作一個(gè)排列概率問題,考慮實(shí)際排序列表與真實(shí)排序列表分別對(duì)應(yīng)的概率分布之間的比較,采用K-L散度來定義排序損失函數(shù).ListMLE[23]則根據(jù)實(shí)際打分函數(shù)計(jì)算真實(shí)排序列表的概率分布,從而考慮最大化實(shí)際理想排序列表的對(duì)數(shù)似然函數(shù)來度量排序損失.Xia等[24]使用神經(jīng)張量網(wǎng)絡(luò)為搜索結(jié)果多樣化建模文檔新穎性,基于文檔新穎性的新模型,在關(guān)系排序?qū)W習(xí)框架下,設(shè)計(jì)了兩種新的多樣性排序?qū)W習(xí)方法R-LTRNTN和PAMM-NTN.Rigutini等[25]提出了一種基于比較神經(jīng)網(wǎng)絡(luò)(CmpNN)的偏序排序?qū)W習(xí)方法SortNet.

基于神經(jīng)網(wǎng)絡(luò)的排序?qū)W習(xí)方法的學(xué)習(xí)能力較強(qiáng),對(duì)噪聲數(shù)據(jù)魯棒性和容錯(cuò)性較強(qiáng),但需調(diào)節(jié)的參數(shù)較多,訓(xùn)練速度慢,容易過擬合,泛化性能較差,有可能陷入局部極小值.

2.2.3 基于支持向量機(jī)的排序?qū)W習(xí)方法

支持向量機(jī)(Support vector machine,SVM)是一種建立在統(tǒng)計(jì)學(xué)習(xí)的VC 維(Vapnikchervonenkis dimension)理論和結(jié)構(gòu)風(fēng)險(xiǎn)最小化原理之上的機(jī)器學(xué)習(xí)方法.SVM的主要思想是在給定訓(xùn)練樣本下,構(gòu)建一個(gè)n維超平面作為決策邊界曲面,最優(yōu)化分離這些數(shù)據(jù),使得正例和負(fù)例之間的隔離邊界被最大化.SVM可看成是感知機(jī)的一種改進(jìn)版本,它的目標(biāo)是構(gòu)建一個(gè)不僅能將正例和負(fù)例分開且能使得間隔最大化的分離最優(yōu)超平面.

Joachims[26]提出了一種基于SVM 的代表性排序?qū)W習(xí)方法Ranking SVM,該方法從用戶的點(diǎn)擊序列中獲取具有偏序關(guān)系的訓(xùn)練樣本對(duì),將排序問題轉(zhuǎn)換為一個(gè)二值分類問題,并使用SVM 去訓(xùn)練排序模型.給定n個(gè)訓(xùn)練查詢和每個(gè)查詢相關(guān)聯(lián)的文檔對(duì)以及對(duì)應(yīng)的相關(guān)性標(biāo)注,即訓(xùn)練數(shù)據(jù),則Ranking SVM的優(yōu)化問題可數(shù)學(xué)形式化為:.其中控制模型ω的復(fù)雜度.該問題等價(jià)于最小化正則化 Hinge損失函數(shù),即,通過解決對(duì)偶問題i=1,···,n來獲得最優(yōu)化參數(shù),最終輸出排序模型〉. 可知,Ranking SVM繼承了SVM的框架和特性,其目標(biāo)函數(shù)非常相似于SVM的,與SVM的差異主要在于約束條件.Ranking SVM的約束條件是從文檔對(duì)中構(gòu)建的,其損失函數(shù)也是定義在文檔對(duì)上的Hinge損失.

基于支持向量機(jī)的排序?qū)W習(xí)方法還有文獻(xiàn)[27?30]等.SVM-MAP[27]方法定義了評(píng)價(jià)指標(biāo)為平均精度均值(MAP)的目標(biāo)函數(shù),并以此設(shè)計(jì)了一個(gè)基于Hinge的損失函數(shù)來替代原MAP的目標(biāo)函數(shù),利用結(jié)構(gòu)化SVM的框架來設(shè)計(jì)排序方法,同時(shí)使得目標(biāo)函數(shù)中松弛變量的總和上有界約束位置敏感準(zhǔn)則(1-AP).SVM-NDCG[28]方法與SVMMAP方法類似,但要求上有界約束位置敏感準(zhǔn)則(1-NDCG).Zhao等[29]提出了一種深度特征學(xué)習(xí)結(jié)構(gòu)化SVM的排序?qū)W習(xí)方法以同時(shí)解決學(xué)習(xí)有效特征和排序?qū)W習(xí)的優(yōu)化問題,該方法在一個(gè)聯(lián)合的學(xué)習(xí)框架下,通過結(jié)構(gòu)化SVM學(xué)習(xí),可同時(shí)獲得深度線性特征集和構(gòu)建結(jié)構(gòu)化感知的排序模型.Li等[30]把排序?qū)W習(xí)問題看作為一個(gè)結(jié)構(gòu)化學(xué)習(xí)問題,基于結(jié)構(gòu)化SVM設(shè)計(jì)了一個(gè)Bregman距離函數(shù)以構(gòu)建排序模型,并為該排序模型開發(fā)了一個(gè)魯棒性結(jié)構(gòu)化學(xué)習(xí)框架,提出了魯棒性結(jié)構(gòu)化Bregman距離函數(shù)的排序?qū)W習(xí)模型.

基于支持向量機(jī)的排序?qū)W習(xí)方法具有嚴(yán)密的理論基礎(chǔ),較強(qiáng)的泛化能力,且易于使用;小樣本數(shù)據(jù)下可得到較高的準(zhǔn)確率,但處理大規(guī)模排序?qū)W習(xí)數(shù)據(jù)集時(shí)顯得效率低下.

2.2.4 基于極限學(xué)習(xí)機(jī)的排序?qū)W習(xí)方法

極限學(xué)習(xí)機(jī)(Extremelearningmachine,ELM)可視為一種新型簡(jiǎn)單、快速有效的單隱層前饋神經(jīng)網(wǎng)絡(luò)的學(xué)習(xí)方法.與前饋神經(jīng)網(wǎng)絡(luò)相比,ELM的主要特點(diǎn)是隱藏結(jié)點(diǎn)參數(shù)不僅與訓(xùn)練數(shù)據(jù)無關(guān),而且彼此獨(dú)立,還有隱藏結(jié)點(diǎn)參數(shù)在訓(xùn)練數(shù)據(jù)出現(xiàn)之前可以生成.ELM算法思想是首先給定網(wǎng)絡(luò)隱層結(jié)點(diǎn)參數(shù)和激活函數(shù),設(shè)置輸入結(jié)點(diǎn)和隱層結(jié)點(diǎn)的連接權(quán)重及隱層結(jié)點(diǎn)的閾值;然后將網(wǎng)絡(luò)輸入輸出關(guān)系變成一個(gè)矩陣向量形式H·β=O計(jì)算隱層輸出矩陣H;最后通過β=H+O求解獲得網(wǎng)絡(luò)輸出連接權(quán)重β,其中H+是H的廣義逆運(yùn)算.

傳統(tǒng)的神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)算法,如反向傳播算法,需通過人工設(shè)置較多的網(wǎng)絡(luò)訓(xùn)練參數(shù),并且很容易陷入局部最優(yōu)解.而ELM算法只需設(shè)置網(wǎng)絡(luò)中隱層結(jié)點(diǎn)的個(gè)數(shù),在其執(zhí)行過程中,無需去調(diào)整網(wǎng)絡(luò)的輸入權(quán)重以及隱元的偏置,可隨機(jī)初始化輸入權(quán)重和偏置,學(xué)習(xí)一次就可得到相應(yīng)的輸出權(quán)重,即可獲得唯一的最優(yōu)解.ELM算法實(shí)際上為廣義單隱層神經(jīng)網(wǎng)絡(luò)提供了一個(gè)統(tǒng)一的解決方案,它是從傳統(tǒng)神經(jīng)網(wǎng)絡(luò)擴(kuò)展到正則網(wǎng)絡(luò)和支持向量網(wǎng)絡(luò).

Zong等[31]應(yīng)用ELM,從Pointwise和Pairwise兩個(gè)視角分別設(shè)計(jì)了Pointwise RankELM和Pairwise RankELM兩種排序?qū)W習(xí)方法以解決相關(guān)性排序?qū)W習(xí)問題,并提出了線性隨機(jī)結(jié)點(diǎn)的ELM和線性內(nèi)核版本的ELM.在Pointwise RankELM排序?qū)W習(xí)方法中,針對(duì)線性隨機(jī)結(jié)點(diǎn)的ELM,先依據(jù)給定的訓(xùn)練樣本,產(chǎn)生L個(gè)帶有每個(gè)結(jié)點(diǎn)隨機(jī)分配參數(shù)(a,b)的隱藏結(jié)點(diǎn),再計(jì)算隱層輸出矩陣,并計(jì)算輸出權(quán)重和計(jì)算測(cè)試樣例的輸出函數(shù)f(x)=h(x)·β.而針對(duì)線性內(nèi)核的ELM,計(jì)算測(cè)試樣本的輸出函數(shù):·和. 而在Pairwise RankELM排序?qū)W習(xí)方法中,與Pointwise RankELM 不同的是:1)在線性隨機(jī)結(jié)點(diǎn)中,Pairwise RankELM是構(gòu)建矩陣w存儲(chǔ)查詢文檔關(guān)系的信息,并計(jì)算相應(yīng)的Laplacian矩陣,而計(jì)算輸出權(quán)重β時(shí),是按照進(jìn)行計(jì)算的.2)在線性內(nèi)核中,Pairwise RankELM首先構(gòu)建矩陣w存儲(chǔ)查詢文檔關(guān)系的信息,并計(jì)算相應(yīng)的Laplacian矩陣,再按照f(x)kernel=去計(jì)算測(cè)試樣本的輸出函數(shù)f(x).

Chen等[32]提出了一種新的運(yùn)用ELM的排序?qū)W習(xí)方法ELMRank,給出定理并證明了ELMRank也繼承了ELM 的計(jì)算可行性,并針對(duì)假設(shè)空間能力,確立了ELMRank的泛化分析.

基于極限學(xué)習(xí)機(jī)的排序?qū)W習(xí)方法只需設(shè)定網(wǎng)絡(luò)的隱層結(jié)點(diǎn)數(shù),無需迭代調(diào)節(jié)隱層結(jié)點(diǎn)的學(xué)習(xí),只需一次學(xué)習(xí)就可獲得唯一最優(yōu)解;具有簡(jiǎn)單易用、訓(xùn)練參數(shù)少、學(xué)習(xí)速度快和泛化性能好且廣義逼近能力強(qiáng)的優(yōu)點(diǎn),但沒有較好的魯棒性.

2.2.5 基于貝葉斯的排序?qū)W習(xí)方法

貝葉斯(Bayesian)方法是一種基于假設(shè)的先驗(yàn)概率、給定假設(shè)下觀察到不同數(shù)據(jù)的概率和觀察到的數(shù)據(jù)本身信息而計(jì)算假設(shè)概率的方法.該方法首先綜合未知參數(shù)的先驗(yàn)信息與樣本數(shù)據(jù)信息,然后依據(jù)貝葉斯公式去計(jì)算后驗(yàn)信息,最后依據(jù)所得出的后驗(yàn)信息去推斷未知參數(shù).

Guo等[33]提出了BLM-Rank,一種貝葉斯線性模型的排序?qū)W習(xí)方法,該方法在貝葉斯個(gè)性化排序標(biāo)準(zhǔn)的框架下,使用一個(gè)線性函數(shù)去評(píng)分樣本的值,依賴于樣本的評(píng)分建模樣本的Pairwise偏好,并采用了隨機(jī)梯度法去最大化BLM-Rank中的先驗(yàn)概率,且在GPU上實(shí)現(xiàn)了該方法.BLM-Rank方法首先從訓(xùn)練數(shù)據(jù)中構(gòu)建Pairwise訓(xùn)練樣本和構(gòu)建正偏序?qū)Φ挠?xùn)練集,然后混排Γ+中的Pairwise訓(xùn)練數(shù)據(jù)以便于將要遍歷的次序是無偏的和隨機(jī)的,再對(duì)每個(gè)樣例(xi,j,xi,k)∈Γ+,依條件循環(huán)執(zhí)行w=w+α·以獲得最終w,最后產(chǎn)生線性函數(shù)F(xi,j,w)=wTxi,j.

還有一些基于貝葉斯的排序?qū)W習(xí)方法,如Cossock等[34]為排序?qū)W習(xí)設(shè)計(jì)貝葉斯最優(yōu)化排序函數(shù),并對(duì)貝葉斯最優(yōu)子集排序作統(tǒng)計(jì)分析;Wang等[35]提出了一種簡(jiǎn)單快速的排序?qū)W習(xí)模型RankBayes,該模型可以應(yīng)用樸素貝葉斯算法去實(shí)現(xiàn).

基于貝葉斯的排序?qū)W習(xí)方法具有堅(jiān)實(shí)的數(shù)學(xué)基礎(chǔ),計(jì)算簡(jiǎn)單、快速;容易理解和解釋,且易構(gòu)造,估計(jì)模型參數(shù)時(shí)無需復(fù)雜的迭代;支持增量學(xué)習(xí),但需要計(jì)算先驗(yàn)概率,對(duì)輸入數(shù)據(jù)的表達(dá)形式較敏感.

2.2.6 基于提升的排序?qū)W習(xí)方法

提升(Boosting)是一類可將弱學(xué)習(xí)器提升為強(qiáng)學(xué)習(xí)器的方法,通過線性組合若干個(gè)弱學(xué)習(xí)器,有監(jiān)督的迭代以改進(jìn)弱學(xué)習(xí)器的機(jī)器學(xué)習(xí)方法.Boosting的理論基礎(chǔ)是弱可學(xué)習(xí)理論,其工作機(jī)制是:先從初始訓(xùn)練集訓(xùn)練出一個(gè)弱學(xué)習(xí)器,再根據(jù)弱學(xué)習(xí)器的性能調(diào)整訓(xùn)練樣本分布,使得當(dāng)前弱學(xué)習(xí)器做錯(cuò)的訓(xùn)練樣本在下一次迭代中受到重點(diǎn)訓(xùn)練,然后基于調(diào)整后的樣本分布去訓(xùn)練下一個(gè)弱學(xué)習(xí)器;如此循環(huán)訓(xùn)練,直至弱學(xué)習(xí)器的數(shù)目達(dá)到預(yù)先給定的值T,最終將這T個(gè)弱學(xué)習(xí)器進(jìn)行加權(quán)組合以創(chuàng)建一個(gè)單一的強(qiáng)學(xué)習(xí)器使得整體性能得到提升.

RankBoost[36]是基于AdaBoost算法的排序?qū)W習(xí)方法,通過最小化實(shí)例對(duì)的分類錯(cuò)誤而訓(xùn)練排序模型,其學(xué)習(xí)目標(biāo)是通過結(jié)合多個(gè)弱排序器構(gòu)成最終唯一的排序模型.RankBoost是Pairwise排序?qū)W習(xí)方法,實(shí)質(zhì)是在優(yōu)化文檔偏序?qū)﹂g的分類誤差,整體還是Boosting框架,在逐層迭代過程中,根據(jù)前一階段的學(xué)習(xí)情況調(diào)整各訓(xùn)練數(shù)據(jù)的權(quán)重.具體來說,RankBoost方法基于分布Dt訓(xùn)練弱學(xué)習(xí)器ht,得到弱排序器ht:x→R,而后選擇合適的αt∈R,再通過更新分布,此處Zt是一個(gè)歸一化因子.最后,輸出最終排序模型:.由上可知,RankBoost排序?qū)W習(xí)方法是基于當(dāng)前文檔對(duì)的分布Dt去學(xué)習(xí)最優(yōu)的弱排序器ht,并選擇對(duì)應(yīng)弱排序器的權(quán)重αt,以便進(jìn)行線性權(quán)值疊加.

AdaRank[37]是一種基于Boosting算法框架、能直接最小化定義在信息檢索評(píng)價(jià)準(zhǔn)則上的指數(shù)損失函數(shù)的Listwise排序?qū)W習(xí)方法,該方法在調(diào)整訓(xùn)練數(shù)據(jù)權(quán)重的基礎(chǔ)上不斷地構(gòu)造弱排序器,最終線性組合各弱排序器以用于排序預(yù)測(cè).

基于提升的排序?qū)W習(xí)方法簡(jiǎn)單易用、設(shè)置參數(shù)較少、不易過擬合、能有效降低偏差,且具有理論支持,具有較強(qiáng)的特征選擇能力和一定的泛化能力,但有效合理地選取損失函數(shù)和更緊致的泛化誤差界是兩大難點(diǎn)問題.

2.2.7 基于樹的排序?qū)W習(xí)方法

樹(Tree)是具有相同數(shù)據(jù)類型的數(shù)據(jù)元素的集合,樹狀結(jié)構(gòu)表示數(shù)據(jù)元素之間存在著“一對(duì)多”的樹形關(guān)系.一般的,一棵樹包含一個(gè)根結(jié)點(diǎn)、若干個(gè)內(nèi)部結(jié)點(diǎn)和葉子結(jié)點(diǎn).根結(jié)點(diǎn)包含樣本全集,葉子結(jié)點(diǎn)對(duì)應(yīng)于樣本實(shí)例,其他結(jié)點(diǎn)則對(duì)應(yīng)數(shù)據(jù)屬性.根據(jù)數(shù)據(jù)屬性的不同,劃分每個(gè)結(jié)點(diǎn)包含的樣本集合到葉子結(jié)點(diǎn)中.對(duì)于給定的訓(xùn)練樣本,根據(jù)數(shù)據(jù)屬性采用樹狀結(jié)構(gòu)建立模型.提升樹是以分類樹或回歸樹為基本分類器的提升方法.

基于樹的排序?qū)W習(xí)方法的代表之一是LambdaMART[38?39],該方法是基于RankNet的LambdaRank的提升樹版本.LambdaMART方法利用多重加法回歸樹(Multiple additive regression tree,MART)取代LambdaRank方法中的神經(jīng)網(wǎng)絡(luò)以優(yōu)化目標(biāo)函數(shù),優(yōu)化過程中采用近似牛頓迭代法(Newton-Raphson)確定每一個(gè)葉子節(jié)點(diǎn)的輸出值.LambdaMART方法的基本思想是訓(xùn)練一個(gè)弱模型的集成,組合每一個(gè)弱模型的預(yù)測(cè)為一個(gè)比單個(gè)模型的預(yù)測(cè)更強(qiáng)大和更準(zhǔn)確的最終模型.LambdaMART從名字上可拆分成Lambda(即λ)和MART兩部分,λ是MART學(xué)習(xí)過程中所使用的梯度,采用MART去優(yōu)化λ以訓(xùn)練排序模型.某個(gè)查詢q下的每個(gè)文檔對(duì)di,dj〉的梯度定義為,其中|?Mij|表示交換文檔di和dj的排序位置后所引起的該查詢的有效性M(M可為信息檢索中一些常用的有效性評(píng)價(jià)指標(biāo),如歸一化折扣累積增益NDCG等)的改變量.每個(gè)文檔di的梯度定義為,其中I表示某查詢q下的所有文檔對(duì)di,dj〉的下標(biāo)集合.MART直接在函數(shù)空間求解梯度函數(shù),循環(huán)構(gòu)建多棵樹,每棵樹的擬合目標(biāo)是損失函數(shù)的梯度λ,通過不斷疊加學(xué)習(xí)到的回歸樹而更新排序模型F,即,其中η表示學(xué)習(xí)率,γlk表示第k個(gè)訓(xùn)練樣例的第l個(gè)葉子結(jié)點(diǎn)的輸出值.LambdaMART方法的框架本質(zhì)是MART算法,其創(chuàng)新在于訓(xùn)練過程中使用λ梯度,其特點(diǎn)是不顯式定義損失函數(shù),而是定義損失函數(shù)的梯度函數(shù),以解決排序損失函數(shù)不易被直接優(yōu)化的問題.

LambdaMART在解決實(shí)際排序問題中已經(jīng)被證明是一個(gè)非常成功的排序?qū)W習(xí)方法的代表之一,后續(xù)出現(xiàn)了較多對(duì)該方法的深入研究.Capannini等[40]開發(fā)了一個(gè)最有效的基于樹的學(xué)習(xí)器的多線程實(shí)現(xiàn)的、開源的可提供優(yōu)化的C++框架,這些學(xué)習(xí)器包括梯度提升回歸樹 GBRT、LambdaMART、Oblivious LambdaMART、一種誘導(dǎo)Oblivious回歸樹的森林算法.Lucchese等[41]提出了一種新的有效排序?qū)W習(xí)方法X-DART,該方法借用CLEaVER方法中樹的剪枝策略以改進(jìn)DART,最終提供更魯棒和緊湊的排序模型.

還有許多工作對(duì)基于樹的排序?qū)W習(xí)方法進(jìn)行了研究.Chen等[42]使用隨機(jī)梯度提升回歸樹訓(xùn)練排序函數(shù).Kocsis等[43]提出了一種提升樹策略的排序?qū)W習(xí)方法.Asadi等[44]聚焦于使用梯度提升回歸樹進(jìn)行排序?qū)W習(xí)運(yùn)行時(shí)的性能優(yōu)化.Yin等[8]采用梯度提升決策樹和邏輯損失函數(shù)設(shè)計(jì)了排序?qū)W習(xí)方法LogisticRank以進(jìn)行搜索結(jié)果的排序.Lucchese等[11]為排序?qū)W習(xí)任務(wù)提出了一種有效的樹集成的遍歷算法QuickScorer以快速排序文檔.Dato等[45]擴(kuò)展了文獻(xiàn)[11]的工作,提出了一個(gè)利用Oblivious和Non-oblivious回歸樹加法集成建模的排序函數(shù)來對(duì)文檔進(jìn)行有效評(píng)分的新算法框架,旨在對(duì)大型Web搜索引擎返回的查詢結(jié)果進(jìn)行快速排序.Lucchese等[46]提出了一個(gè)為優(yōu)化基于回歸樹集成的機(jī)器學(xué)習(xí)排序模型的新框架,該框架是對(duì)樹集成的后期學(xué)習(xí)優(yōu)化,其目標(biāo)是去改進(jìn)排序效率而不影響排序質(zhì)量.Mohan等[47]提出了一種基于初始化梯度提升回歸樹的排序?qū)W習(xí)方法以用于Web搜索,該方法組合了隨機(jī)森林和梯度提升回歸樹,首先運(yùn)用隨機(jī)森林去學(xué)習(xí)出一個(gè)排序函數(shù),再將該函數(shù)作為梯度提升回歸樹的初始值繼續(xù)學(xué)習(xí)更優(yōu)的排序函數(shù).de S等[48]提出了一個(gè)基于Boosting和隨機(jī)森林排序?qū)W習(xí)的通用框架以平滑組合加法樹集成學(xué)習(xí).它使用隨機(jī)森林模型作為Boosting方法的弱學(xué)習(xí)器,依賴于通過隨機(jī)森林所產(chǎn)生的詞袋樣本以決定最終加法模型中每一個(gè)弱學(xué)習(xí)器的影響和通過一個(gè)更可靠的錯(cuò)誤率估計(jì)以更新樣本分布的權(quán)值.Ibrahim等[49]深度比較了基于隨機(jī)森林的Pointwise和Listwise排序?qū)W習(xí)方法,即RF-point和RF-list,設(shè)計(jì)了一種能直接優(yōu)化任意排序標(biāo)準(zhǔn)的基于隨機(jī)森林的Listwise排序?qū)W習(xí)方法,還設(shè)計(jì)了一種能融合不同分裂標(biāo)準(zhǔn)到單棵樹中的隨機(jī)森林的混合排序?qū)W習(xí)方法,該混合方法結(jié)合了樹構(gòu)建的早期的Listwise目標(biāo)和晚期的Pointwise目標(biāo).

基于樹的排序?qū)W習(xí)方法計(jì)算簡(jiǎn)單,易于理解,速度快,學(xué)習(xí)效果通常較好,但樹的分裂標(biāo)準(zhǔn)和剪枝策略對(duì)產(chǎn)生的排序模型的性能影響較大,如何選擇最優(yōu)特征來劃分特征空間是一大難點(diǎn);容易發(fā)生過擬合,不過,隨機(jī)森林可以在很大程度上減少過擬合.

2.2.8 基于進(jìn)化算法的排序?qū)W習(xí)方法

進(jìn)化算法(Evolutionary algorithm,EA)是來自于大自然的生物進(jìn)化靈感的一個(gè)“算法簇”,是一類基于遺傳和選擇等生物進(jìn)化機(jī)制的迭代優(yōu)化的搜索算法.EA的主要思想是:在搜索最優(yōu)解的過程中,一般是從原問題的一個(gè)解(或解集)進(jìn)化到另一個(gè)較好的解(或解集),再?gòu)倪@個(gè)改進(jìn)的解(或解集)繼續(xù)進(jìn)一步迭代進(jìn)化以獲得更優(yōu)化的解(或解集).EA求解問題的主要步驟是:隨機(jī)生成一個(gè)或一組初始解;評(píng)價(jià)當(dāng)前該解或該組解的性能;選擇當(dāng)前該解或從該組解中選擇給定數(shù)量的解迭代執(zhí)行進(jìn)化操作以獲取新解;若新解滿足給定的停止條件則結(jié)束迭代,否則將進(jìn)化所得到的新解作為當(dāng)前解再重新迭代執(zhí)行進(jìn)化操作.

EA并非直接處理求解問題的具體參數(shù),而是針對(duì)求解問題的整個(gè)參數(shù)空間給出相應(yīng)的編碼方案.它是一種能適應(yīng)不同問題和環(huán)境的魯棒性智能優(yōu)化方法,且在大多數(shù)情況下都能進(jìn)化到用戶滿意的優(yōu)化解.EA從某個(gè)單一的或一組初始點(diǎn)開始搜索,搜索中只要有目標(biāo)函數(shù)值的信息就可優(yōu)化,可不必用到目標(biāo)函數(shù)的導(dǎo)數(shù)信息等,也不必要求目標(biāo)函數(shù)是連續(xù)的,且具有較好的全局尋優(yōu)能力,因而有較多的進(jìn)化算法應(yīng)用于排序?qū)W習(xí)問題中.將進(jìn)化算法應(yīng)用于設(shè)計(jì)排序?qū)W習(xí)方法,關(guān)鍵問題是解和排序模型的映射問題、適應(yīng)度函數(shù)或優(yōu)化目標(biāo)的相應(yīng)設(shè)計(jì)問題.

較早的基于進(jìn)化算法的排序?qū)W習(xí)的代表性方法之一是Yeh等[50]運(yùn)用遺傳編程技術(shù)設(shè)計(jì)排序?qū)W習(xí)方法RankGP,該方法將排序模型表示為種群中的個(gè)體(解),一個(gè)個(gè)體I是一個(gè)潛在的排序函數(shù),使用3個(gè)組件定義一個(gè)函數(shù)表達(dá)I=(Sv,Sc,Sop),其中Sv表示符號(hào)標(biāo)記集,指訓(xùn)練集的特征,Sc表示預(yù)定義的實(shí)數(shù)集,值域∈[0,1],Sop表示算術(shù)操作集.I被定義為一個(gè)二叉樹結(jié)構(gòu),它的葉子結(jié)點(diǎn)是特征或常量,非葉子結(jié)點(diǎn)是如+、?、×、÷等操作,利用種群的遺傳編程在樹上執(zhí)行排序模型的學(xué)習(xí).在進(jìn)化過程中,通過交叉、變異、復(fù)制和選擇等進(jìn)化操作迭代產(chǎn)生一個(gè)新種群.在每次迭代中,使用平均精度均值MAP建模適應(yīng)度函數(shù)以評(píng)價(jià)種群中每個(gè)個(gè)體在訓(xùn)練集上的性能.當(dāng)進(jìn)化結(jié)束時(shí),將會(huì)產(chǎn)生一個(gè)適應(yīng)度值最優(yōu)的個(gè)體,以此個(gè)體作為最優(yōu)排序模型.

受基于遺傳編程的排序?qū)W習(xí)方法的啟發(fā),Lin等[51]運(yùn)用分層多種群遺傳編程改進(jìn)RankGP方法,提出了排序?qū)W習(xí)方法RankMGP以學(xué)習(xí)排序函數(shù).Keyhanipour等[52]提出了一種新穎的排序?qū)W習(xí)方法MGP-Rank,該方法從任意的基準(zhǔn)數(shù)據(jù)集中,在基于點(diǎn)擊數(shù)據(jù)概念的特征產(chǎn)生框架下產(chǎn)生點(diǎn)擊特征,使用一種分層的多種群遺傳編程框架去找最優(yōu)化的排序函數(shù).

借鑒RankGP方法將遺傳編程應(yīng)用于設(shè)計(jì)排序?qū)W習(xí)方法的經(jīng)驗(yàn),越來越多的基于進(jìn)化算法的排序?qū)W習(xí)方法被提出來.Wang等[53]提出了一系列通用定義和一個(gè)為進(jìn)化計(jì)算在排序?qū)W習(xí)研究中應(yīng)用的共同框架,并基于該框架,提出了一種使用免疫規(guī)劃的排序函數(shù)發(fā)現(xiàn)方法.He等[54]提出了一種基于克隆選擇算法的排序?qū)W習(xí)方法RankCSA,直接優(yōu)化信息檢索的性能評(píng)價(jià)指標(biāo)(MAP)以學(xué)習(xí)有效的排序函數(shù).Diaz-Aviles等[55]基于粒子群優(yōu)化框架,提出了一種新穎的排序?qū)W習(xí)方法SwarmRank直接最大化信息檢索中廣泛使用的評(píng)價(jià)標(biāo)準(zhǔn)以學(xué)習(xí)排序模型.Alejo等[56]提出了一種基于粒子群優(yōu)化算法的排序?qū)W習(xí)方法RankPSO以直接優(yōu)化評(píng)價(jià)標(biāo)準(zhǔn)而訓(xùn)練排序模型.Bollegala等[57]提出了一種基于差分進(jìn)化算法的排序?qū)W習(xí)方法RankDE去學(xué)習(xí)排序函數(shù)以對(duì)所檢索的文檔進(jìn)行排序.Wang等[58]提出了一種基于協(xié)同進(jìn)化算法的并行排序?qū)W習(xí)框架CCRank,目標(biāo)是顯著改進(jìn)學(xué)習(xí)的效率且同時(shí)保持精度,并采用三種基于進(jìn)化算法(遺傳編程、免疫規(guī)劃和基于樹的幾何差分進(jìn)化)的排序?qū)W習(xí)方法(RankGP、RankIP和RankGDE)實(shí)現(xiàn)了該框架.Ibrahim 等[59]運(yùn)用進(jìn)化策略設(shè)計(jì)排序?qū)W習(xí)方法ES-Rank以解決排序?qū)W習(xí)問題.Tian等[60]利用多核處理器將B細(xì)胞算法并行化,并將克隆交叉思想融入到并行B細(xì)胞算法中,同時(shí)提出了一種抗體的先序編碼序列將樹結(jié)構(gòu)轉(zhuǎn)化為線性結(jié)構(gòu),進(jìn)一步設(shè)計(jì)了基于并行B細(xì)胞算法的排序?qū)W習(xí)方法RankBCA.Li等[61]提出了一種基于現(xiàn)代投資組合理論和歸檔式多目標(biāo)模擬退火算法框架的風(fēng)險(xiǎn)敏感的魯棒性排序?qū)W習(xí)方法R2Rank,以同時(shí)優(yōu)化增益和風(fēng)險(xiǎn)并獲取有效性和魯棒性之間的均衡.

基于進(jìn)化算法的排序?qū)W習(xí)方法可直接優(yōu)化信息檢索的評(píng)價(jià)標(biāo)準(zhǔn),往往訓(xùn)練得到的排序模型可獲得相對(duì)更優(yōu)的評(píng)價(jià)性能.但由于該類方法存在大量迭代,通常計(jì)算復(fù)雜度較高和收斂速度較慢,故需花費(fèi)的學(xué)習(xí)時(shí)間可能相對(duì)較長(zhǎng).可喜的是,由于進(jìn)化算法通常具有天然的并行性,所以可將該類方法進(jìn)行并行化,從而提高其效率.而且,進(jìn)化算法非常適合大數(shù)據(jù)分析,所以基于進(jìn)化算法的排序?qū)W習(xí)方法適合解決大數(shù)據(jù)排序?qū)W習(xí)問題.

2.2.9 其他排序?qū)W習(xí)方法

Moschitti[62]研究了一種具有語法和語義結(jié)構(gòu)的基于核理論的排序?qū)W習(xí)方法.Ailon等[63]提出了一種有效的兩階段的基于偏好的排序?qū)W習(xí)方法.Niu等[7]開發(fā)了一些混合方法來提高排序?qū)W習(xí)方法的效果和效率,他們指出排序應(yīng)是一個(gè)top-k的問題,并建立了一個(gè)完整的top-k排序框架,提出了若干種Pointwise、Pairwise和Listwise的混合排序?qū)W習(xí)方法,還闡述了如何獲得高效可靠的top-k標(biāo)注數(shù)據(jù),如何設(shè)計(jì)有效的top-k排序?qū)W習(xí)模型,對(duì)排序結(jié)果采用何種評(píng)價(jià)準(zhǔn)則進(jìn)行可靠地評(píng)價(jià)等.

還有一些研究排序?qū)W習(xí)相關(guān)問題的工作.Zhou等[64]利用輔助數(shù)據(jù)進(jìn)行排序?qū)W習(xí).Macdonald等[65]針對(duì)不同信息需求類型,不同排序?qū)W習(xí)方法和不同排序?qū)W習(xí)語料庫(kù),全面調(diào)研了如何最佳地部署排序?qū)W習(xí)以獲取有效的排序模型.Lai等[66]通過一個(gè)有效的Primal-Dual算法解決稀疏排序?qū)W習(xí)問題.Lai等[67]為排序?qū)W習(xí)提出了一種新的特征選擇方法.Ma等[68]為排序?qū)W習(xí)提出了一種新穎的訓(xùn)練查詢選擇方法.Wang等[69]研究了個(gè)性化搜索中具有選擇偏見的排序?qū)W習(xí)問題,在排序?qū)W習(xí)框架下如何利用稀疏的點(diǎn)擊數(shù)據(jù).Wu等[70]提出了一種從Listwise訓(xùn)練數(shù)據(jù)中學(xué)習(xí)非線性排序模型的分而訓(xùn)練的方法.Joachims等[71]利用有偏反饋數(shù)據(jù)提出了無偏排序?qū)W習(xí).Calumby等[72]評(píng)論了交互式信息檢索系統(tǒng)中交互式排序?qū)W習(xí)相關(guān)方面,主要集中在概述、最新進(jìn)展、重要挑戰(zhàn)和有前景的研究方向.

表2總結(jié)了一些典型排序?qū)W習(xí)方法所屬類別.從表2可以看出,同一排序?qū)W習(xí)方法,從不同角度看待,分別屬于不同類型的排序?qū)W習(xí)方法,它們之間的關(guān)系是交叉重疊的.依據(jù)不同角度,排序?qū)W習(xí)可分為不同的種類,如若按需求場(chǎng)景對(duì)排序?qū)W習(xí)進(jìn)行分類,則可分為有效性排序?qū)W習(xí)、魯棒性排序?qū)W習(xí)、多樣性排序?qū)W習(xí)、可信性排序?qū)W習(xí)、時(shí)效性排序?qū)W習(xí)、個(gè)性化排序?qū)W習(xí)和多目標(biāo)排序?qū)W習(xí)等方法.若按照所轉(zhuǎn)化的問題不同,可分為基于分類、基于回歸、基于序數(shù)回歸、基于凸優(yōu)化和基于多目標(biāo)等的排序?qū)W習(xí)方法.盡管角度不同,分類不同,但設(shè)計(jì)排序?qū)W習(xí)方法的重難點(diǎn)問題仍在于如何構(gòu)建損失函數(shù)(優(yōu)化目標(biāo))和如何對(duì)損失函數(shù)(優(yōu)化目標(biāo))進(jìn)行學(xué)習(xí)以產(chǎn)生性能優(yōu)良的排序模型.

3 排序?qū)W習(xí)數(shù)據(jù)集

目前已有公開的基準(zhǔn)排序?qū)W習(xí)數(shù)據(jù)集主要包括:LETOR、MSLR-WEB10K 和 MSLRWEB30K、Yahoo! learning to rank challenge set、Yandex internet mathematics 2009、WCL2R以及Istella LETOR和Istella-S LETOR等.

表2 排序?qū)W習(xí)方法類別及實(shí)例Table 2 Categories and instances of the learning to rank approaches

LETOR1https://research.microsoft.com/en-us/um/beijing/projects/letor是由微軟亞洲研究院開發(fā)的小規(guī)模排序?qū)W習(xí)數(shù)據(jù)集,于2008年和2009年分別發(fā)布了LETOR3.0和LETOR4.0數(shù)據(jù)集.LETOR3.0是OHSUMED和Gov中的一些數(shù)據(jù)集,如HP2003和TD2004等;LETOR4.0新發(fā)布了兩個(gè)稍較大的數(shù)據(jù)集MQ2007和MQ2008,提供了4種排序設(shè)置的數(shù)據(jù)集:監(jiān)督排序、半監(jiān)督排序、排序聚合、列表排序,則總共包括了8個(gè)數(shù)據(jù)集.Qin等[73]對(duì)排序?qū)W習(xí)數(shù)據(jù)集LETOR進(jìn)行了詳細(xì)的描述,包括如何選擇文檔語料和查詢集,如何對(duì)文檔進(jìn)行采樣,如何提取排序?qū)W習(xí)特征和元信息以及如何劃分?jǐn)?shù)據(jù)集等.

MSLR-WEB10K和MSLR-WEB30K2https://www.microsoft.com/en-us/research/project/mslr/是由微軟亞洲研究院于2010年開發(fā)的兩個(gè)相對(duì)較大規(guī)模的排序?qū)W習(xí)數(shù)據(jù)集.MSLR-WEB30K是規(guī)模較大、且公共可利用的排序?qū)W習(xí)數(shù)據(jù)集,它包含了3萬多個(gè)查詢和300多萬個(gè)文檔,具有100多維排序特征.MSLR-WEB10K是從MSLR-WEB30K中隨機(jī)采樣的一個(gè)子數(shù)據(jù)集,它包含1萬個(gè)查詢和100多萬個(gè)文檔.每個(gè)排序?qū)W習(xí)數(shù)據(jù)集都包括從查詢–文檔對(duì)中提取的排序特征向量以及相關(guān)性判斷標(biāo)注,相關(guān)性判斷標(biāo)注是從微軟的商業(yè)Web搜索引擎Bing的一個(gè)檢索標(biāo)簽集中獲得的.每個(gè)數(shù)據(jù)集被分成查詢數(shù)量約相等的5個(gè)部分以進(jìn)行5折(folds)交叉驗(yàn)證.在每個(gè)數(shù)據(jù)文件中,包含若干條記錄,每條記錄代表一個(gè)查詢–文檔對(duì),它包含查詢與文檔的相關(guān)性程度、查詢編號(hào)以及表征查詢–文檔對(duì)的136維排序特征.

Yahoo!learning to rank challenge set3http://webscope.sandbox.yahoo.com/catalog.php?datatype=c是2010年舉行的Yahoo!排序?qū)W習(xí)挑戰(zhàn)賽所采用的排序?qū)W習(xí)數(shù)據(jù)集,包含Yahoo!learning to rank challenge set 1和Yahoo!learning to rank challenge set 2.Chapelle等[13]詳細(xì)介紹了該數(shù)據(jù)集的構(gòu)建,包含查詢、文檔和相關(guān)性等級(jí)標(biāo)注的收集,但沒有揭露這些查詢、URLs和排序特征的描述,僅僅提供了特征值.

Yandex internet mathematics 2009數(shù)據(jù)集4http://imat2009.yandex.ru/en/datasets是由俄羅斯的商業(yè)Web搜索引擎Yandex所發(fā)布的用于“the Yandex internet mathematics competition”的基于機(jī)器學(xué)習(xí)的排序競(jìng)賽的排序?qū)W習(xí)數(shù)據(jù)集,這些數(shù)據(jù)由Yandex評(píng)估員將查詢–文檔對(duì)的特征向量和相關(guān)性等級(jí)標(biāo)注都用實(shí)數(shù)來表示以用于學(xué)習(xí)和測(cè)試.同Yahoo!learning to rank challenge數(shù)據(jù)集一樣,不包含原始查詢和原始文檔的URLs,并且也不能揭示特征的語義信息.

WCL2R5http://www.latin.dcc.ufmg.br/collections/wcl2r是由米納斯吉拉斯聯(lián)邦大學(xué)等單位于2010年開發(fā)的具有點(diǎn)擊特征數(shù)據(jù)的用于排序?qū)W習(xí)研究的基準(zhǔn)數(shù)據(jù)集,它是從一個(gè)現(xiàn)實(shí)生活的搜索引擎TodoCL日志中提取的點(diǎn)擊數(shù)據(jù)等顯著性特征組成的排序?qū)W習(xí)數(shù)據(jù)集.Alcntara等[74]對(duì)WCL2R 排序?qū)W習(xí)數(shù)據(jù)集提供了詳細(xì)的描述,包括如何獲取語料、查詢和相關(guān)性標(biāo)注,如何構(gòu)建可學(xué)習(xí)的數(shù)據(jù)特征和如何劃分?jǐn)?shù)據(jù)集等.

Istella LETOR和Istella-S LETOR6http://quickrank.isti.cnr.it/istella-dataset/是由意大利ISTI-CNR的Istella團(tuán)隊(duì)等于2016年開發(fā)的兩個(gè)較大規(guī)模的、特別適用于求解排序?qū)W習(xí)問題的有關(guān)效率和可擴(kuò)展性的大規(guī)模實(shí)驗(yàn)的排序?qū)W習(xí)數(shù)據(jù)集.Istella LETOR是目前規(guī)模最大、且公共可利用的排序?qū)W習(xí)數(shù)據(jù)集,按80%、20%的模式劃分成訓(xùn)練集和測(cè)試集;Istella-S LETOR是對(duì)Istella LETOR中每個(gè)查詢平均采樣約103個(gè)樣本的無關(guān)對(duì)所形成的一個(gè)相對(duì)較小的排序?qū)W習(xí)數(shù)據(jù)集,按60%、20%、20%的模式劃分成訓(xùn)練集、驗(yàn)證集和測(cè)試集.

表3從查詢個(gè)數(shù)、文檔個(gè)數(shù)、特征個(gè)數(shù)、相關(guān)性等級(jí)標(biāo)注和來源這5個(gè)方面總結(jié)了各種排序?qū)W習(xí)數(shù)據(jù)集的相關(guān)信息.從表3中的數(shù)據(jù)來看,小規(guī)模排序?qū)W習(xí)數(shù)據(jù)集偏多,查詢、文檔和特征個(gè)數(shù)整體都相對(duì)較小,缺乏大規(guī)模排序?qū)W習(xí)數(shù)據(jù)集.

4 排序?qū)W習(xí)方法應(yīng)用

對(duì)排序?qū)W習(xí)的研究已不僅限于理論、方法和數(shù)據(jù)集方面,它正被越來越多地應(yīng)用于信息檢索等領(lǐng)域中解決實(shí)際的排序問題.排序是很多實(shí)際應(yīng)用所面臨的核心問題,如Web搜索、推薦系統(tǒng)、微博排序、多媒體檢索、專家發(fā)現(xiàn)、機(jī)器翻譯、問答系統(tǒng)、計(jì)算廣告學(xué)、摘要提取、查詢擴(kuò)展和重寫及建議、生物醫(yī)學(xué)信息學(xué)等.

4.1 Web搜索

Web搜索是排序?qū)W習(xí)方法最早也是目前最成功的實(shí)際應(yīng)用之一.研究提取查詢–文檔的哪些排序特征以及如何結(jié)合排序?qū)W習(xí)方法訓(xùn)練排序模型以提高用戶對(duì)Web搜索的結(jié)果排序的滿意度,成為基于排序?qū)W習(xí)的Web搜索的主要任務(wù).

很多知名的互聯(lián)網(wǎng)公司如 Bing、Yandex、Yahoo、百度和搜狗等搜索引擎,都依賴于排序?qū)W習(xí)方法為用戶提供高質(zhì)量的搜索結(jié)果,如排序?qū)W習(xí)方法RankNet[19]已應(yīng)用于微軟的搜索引擎Bing當(dāng)中以對(duì)Web搜索結(jié)果進(jìn)行優(yōu)化排序,排序?qū)W習(xí)方法LogisticRank[8]已應(yīng)用于雅虎搜索引擎中優(yōu)化搜索結(jié)果的排序.Zhang等[75]在網(wǎng)絡(luò)搜索實(shí)際場(chǎng)景中實(shí)證研究了包括線性回歸、RankBoost、ListNet、ListMLE 和SVM-MAP這5個(gè)代表性的排序?qū)W習(xí)方法的有效性.Macdonald等[76]為Web搜索研究了排序?qū)W習(xí)模型的可遷移性.Kang等[77]基于使用成對(duì)偏好模型的集成的排序?qū)W習(xí)模型,對(duì)Web搜索中的關(guān)聯(lián)實(shí)體進(jìn)行實(shí)體排序.

4.2 推薦系統(tǒng)

將排序?qū)W習(xí)方法應(yīng)用于推薦系統(tǒng)中主要需解決兩大關(guān)鍵問題:1)挖掘用戶和物品(對(duì)象)的哪些排序特征?2)運(yùn)用排序?qū)W習(xí)方法如何整合這些特征,構(gòu)建更加貼合用戶需求的推薦模型,以提高推薦系統(tǒng)的性能和用戶滿意度?

Karatzoglou等[78]闡述了不同類別的排序?qū)W習(xí)方法的關(guān)鍵思想如何應(yīng)用到具體的協(xié)同過濾方法中.Sun等[79]將排序?qū)W習(xí)方法RankSVM應(yīng)用于推薦系統(tǒng)中,為用戶產(chǎn)生物品的推薦列表.Yao等[80]為物品推薦應(yīng)用排序?qū)W習(xí)技術(shù),將用戶間的社交信息融入Listwise排序?qū)W習(xí)模型的訓(xùn)練中以改進(jìn)物品排序列表的質(zhì)量.Canuto等[81]應(yīng)用排序?qū)W習(xí)技術(shù)自動(dòng)地學(xué)習(xí)標(biāo)簽排序函數(shù),綜合比較了8種不同排序?qū)W習(xí)方法(包括List-Net、RankSVM、RankBoost、AdaRank、多重加法回歸樹MART、LambdaMART、隨機(jī)森林和遺傳算法)融入標(biāo)簽推薦中的效果.Ifada等[82]針對(duì)基于標(biāo)簽的項(xiàng)目推薦系統(tǒng),開發(fā)了一種新穎的排序?qū)W習(xí)方法Go-Rank以直接優(yōu)化等級(jí)平均精度GAP,從而產(chǎn)生一個(gè)推薦項(xiàng)目的最優(yōu)化列表.黃震華等[83]對(duì)近些年基于排序?qū)W習(xí)的推薦算法的研究進(jìn)展進(jìn)行了綜述,對(duì)其問題定義、關(guān)鍵技術(shù)、效用評(píng)價(jià)、應(yīng)用進(jìn)展等進(jìn)行概括、比較和分析,并對(duì)基于排序?qū)W習(xí)的推薦算法的未來發(fā)展趨勢(shì)進(jìn)行了探討和展望.

表3 排序?qū)W習(xí)數(shù)據(jù)集Table 3 Datasets of learning to rank

4.3 微博排序

隨著微博用戶的劇增和博文數(shù)量的指數(shù)級(jí)增長(zhǎng),越來越多的排序?qū)W習(xí)方法應(yīng)用于解決微博的排序問題.Berendsen等[84]研究了為微博搜索而創(chuàng)建偽測(cè)試集的方法,利用排序?qū)W習(xí)技術(shù),使用偽測(cè)試集作為訓(xùn)練集去訓(xùn)練和調(diào)節(jié)微博排序器.Dong等[85]使用具有Freshness特征的Twitter數(shù)據(jù),利用排序?qū)W習(xí)技術(shù)(梯度提升決策樹)去學(xué)習(xí)排序函數(shù)以用于改進(jìn)Recency排序.Duan等[86]提取Tweet的內(nèi)容相關(guān)性特征、Tweet用戶帳號(hào)權(quán)威性特征和Tweet的特定特征,使用排序?qū)W習(xí)方法RankSVM學(xué)習(xí)排序模型以對(duì)微博搜索結(jié)果進(jìn)行排序.

應(yīng)用排序?qū)W習(xí)方法解決微博排序問題取得了較好的效果,但仍存在一些難點(diǎn)問題:1)由于微博數(shù)據(jù)的增量變化,要求能增量地提取微博排序特征以增量構(gòu)建多維復(fù)合特征集,這就要求排序?qū)W習(xí)方法能支持微博數(shù)據(jù)集的增量學(xué)習(xí);2)由于微博用戶和信息數(shù)量過大以及各自的動(dòng)態(tài)變化,這就要求排序?qū)W習(xí)方法能支持排序模型的動(dòng)態(tài)學(xué)習(xí).而現(xiàn)有應(yīng)用于微博排序的的排序?qū)W習(xí)方法都缺乏對(duì)數(shù)據(jù)和模型的增量和動(dòng)態(tài)性支持,這是未來需要突破的重難點(diǎn).

4.4 多媒體檢索

Chelaru等[87]利用排序?qū)W習(xí)技術(shù)研究了社交特征對(duì)視頻檢索有效性的影響.Yu等[88]利用排序?qū)W習(xí)技術(shù)得到一個(gè)用于圖像檢索的排序模型,該模型共同考慮了圖像檢索中用戶的視覺特征和點(diǎn)擊特征.Zhao等[89]運(yùn)用深度神經(jīng)網(wǎng)絡(luò)和潛在的結(jié)構(gòu)化SVM,提出了一種稱為深度潛在結(jié)構(gòu)化SVM的新型聯(lián)合排序?qū)W習(xí)方法以進(jìn)行多媒體檢索.Karaoglu等[90]使用排序?qū)W習(xí)方法在計(jì)算機(jī)視覺中組合不同目標(biāo)檢測(cè)器.Wang等[91]將行人再識(shí)別任務(wù)建模為一個(gè)Listwise排序?qū)W習(xí)問題,集成卷積神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)具有自適應(yīng)Listwise約束的深度特征.

4.5 專家發(fā)現(xiàn)

Volkovs等[92]運(yùn)用排序?qū)W習(xí)方法聚合專家偏好.Moreira等[93]探索了排序?qū)W習(xí)方法和排序聚合方法對(duì)學(xué)術(shù)出版物的數(shù)字化圖書館中專家發(fā)現(xiàn)任務(wù)中的應(yīng)用.Zheng等[94]從文本內(nèi)容、專家社區(qū)中帶有引用模式的圖形結(jié)構(gòu)和有關(guān)專家的配置文件信息中,探討了使用排序?qū)W習(xí)方法組合專家們的多種評(píng)估以發(fā)現(xiàn)專家.Chen等[95]融合多特征,基于ListNet排序?qū)W習(xí)方法設(shè)計(jì)了專家列表排序方法以發(fā)現(xiàn)專家.

4.6 機(jī)器翻譯

Delpech等[96]提出了一種從語料庫(kù)中,為特定領(lǐng)域的雙語詞典提取新的組合翻譯方法,并采用排序?qū)W習(xí)技術(shù)為候選翻譯結(jié)果進(jìn)行排序.Li等[97]將Listwise排序?qū)W習(xí)方法應(yīng)用于機(jī)器翻譯的自動(dòng)評(píng)估.Lee等[98]將排序?qū)W習(xí)方法應(yīng)用于英語–韓語機(jī)器翻譯中解決謂詞參數(shù)的重排序.Farzi等[99]使用基于語法的排序?qū)W習(xí)系統(tǒng)改進(jìn)統(tǒng)計(jì)機(jī)器翻譯.

4.7 問答系統(tǒng)

Wu等[100]提出了一種新的基于意圖的語言模型,采用LambdaMART排序?qū)W習(xí)方法評(píng)估該模型參數(shù)以提高問答社區(qū)中短查詢的搜索相關(guān)性.Nguyen等[101]運(yùn)用Ranking SVM 排序?qū)W習(xí)方法為重排序問題學(xué)習(xí)的社區(qū)問答競(jìng)賽進(jìn)行排序問題學(xué)習(xí).Verberne等[102]為問答系統(tǒng)排序答案任務(wù)評(píng)估了一些排序?qū)W習(xí)方法,如Ranking SVM 和SVMMAP等.

4.8 計(jì)算廣告學(xué)

Ciaramita等[103]從機(jī)器學(xué)習(xí)的視角研究了贊助商搜索問題,從點(diǎn)擊數(shù)據(jù)中在線學(xué)習(xí)以解決贊助商搜索問題.Tagami等[104]基于排序?qū)W習(xí)方法,為上下文廣告而提出了一種點(diǎn)擊率預(yù)測(cè)算法.Karimzadehgan等[105]提出了一種隨機(jī)排序?qū)W習(xí)方法,并應(yīng)用于上下文廣告中.

4.9 摘要提取

Shen等[106]主要探討怎樣使用支持向量機(jī)來訓(xùn)練以查詢?yōu)橹鞯亩辔臋n文摘的特征權(quán)重.Zhu等[107]將他們提出的關(guān)系排序?qū)W習(xí)方法應(yīng)用于基于話題的多文檔摘要任務(wù)中.Tran等[108]采用自適應(yīng)排序?qū)W習(xí)方法為高影響事件的時(shí)間軸摘要進(jìn)行實(shí)體排序以均衡新穎性和顯著性.Tran等[109]提出了一個(gè)優(yōu)化框架,并闡述了使用排序?qū)W習(xí)方法在該優(yōu)化框架下如何從網(wǎng)絡(luò)新聞事件中自動(dòng)構(gòu)建時(shí)間軸摘要.

4.10 查詢擴(kuò)展、重寫和建議

Xu等[110]提出了一個(gè)新穎框架以探索使用排序?qū)W習(xí)方法去優(yōu)化偽相關(guān)性反饋,為查詢擴(kuò)展比較評(píng)估了一些排序?qū)W習(xí)方法.Lin等[111]基于排序?qū)W習(xí)方法從社會(huì)化標(biāo)注中進(jìn)行擴(kuò)展詞提取,并構(gòu)造詞排序模型用于社會(huì)化標(biāo)注查詢擴(kuò)展任務(wù)中.Dang等[112]提出使用排序?qū)W習(xí)方法執(zhí)行查詢重寫,用僅有的兩個(gè)特征重排序通過基于日志的查詢擴(kuò)展技術(shù)所產(chǎn)生的重寫查詢或擴(kuò)展查詢的列表.Santos等[113]提出了一種用于查詢建議問題的排序?qū)W習(xí)方法,該方法利用從候選查詢建議的結(jié)構(gòu)化表示中挖掘出的多個(gè)排序特征以產(chǎn)生高效的查詢建議.

4.11 生物醫(yī)學(xué)信息學(xué)

Liu等[114]運(yùn)用排序?qū)W習(xí)技術(shù),提出了一種廣泛應(yīng)用于蛋白質(zhì)遠(yuǎn)程同源性檢測(cè)以及蛋白質(zhì)功能和結(jié)構(gòu)預(yù)測(cè)的計(jì)算方法ProtDec-LTR,該方法在監(jiān)督學(xué)習(xí)框架下組合了三種最先進(jìn)的排序預(yù)測(cè)器以訓(xùn)練最優(yōu)排序模型.他們[115]還將基于個(gè)人配置信息的偽蛋白融入到排序?qū)W習(xí)算法框架中改進(jìn)ProtDec-LTR方法以提高預(yù)測(cè)性能.Shang等[116]將自動(dòng)摘要提取看作為一個(gè)排序問題,應(yīng)用排序?qū)W習(xí)方法自動(dòng)提取基因摘要.Jing等[117]基于排序?qū)W習(xí)算法開發(fā)了一個(gè)軟件MQAPRank以用于改進(jìn)全球蛋白質(zhì)模型質(zhì)量評(píng)價(jià).

4.12 其他應(yīng)用

Saleem等[118]使用排序?qū)W習(xí)方法進(jìn)行基于個(gè)性化決策策略的Web服務(wù)選擇.Deveaud等[119]通過使用排序?qū)W習(xí)方法以自動(dòng)配置任務(wù)算法中的參數(shù).Zhou等[120]將排序?qū)W習(xí)技術(shù)應(yīng)用于關(guān)系實(shí)體搜索.Chen等[121]將排序?qū)W習(xí)技術(shù)應(yīng)用于語義關(guān)聯(lián)排序.Kong等[122]采用排序?qū)W習(xí)方法RankBoost和Ranking SVM獲取候選抄襲源文檔以解決抄襲檢測(cè)源檢索問題.

由上述歸納可知,排序?qū)W習(xí)方法已經(jīng)在不同應(yīng)用領(lǐng)域中取得了大量的研究成果.概括起來,將排序?qū)W習(xí)方法用于解決一些實(shí)際應(yīng)用領(lǐng)域中的排序問題時(shí),需要解決兩大難點(diǎn)問題:1)針對(duì)實(shí)際應(yīng)用,提取哪些排序特征以更好地表征該應(yīng)用;2)如何針對(duì)實(shí)際應(yīng)用,構(gòu)建損失函數(shù)或優(yōu)化目標(biāo)以指導(dǎo)排序?qū)W習(xí)方法訓(xùn)練出更優(yōu)的排序模型.

5 排序?qū)W習(xí)方法軟件包

近年來,排序?qū)W習(xí)方法得以迅速發(fā)展,并能夠廣泛地運(yùn)用于眾多的實(shí)際應(yīng)用中解決排序問題,離不開許多精心設(shè)計(jì)和實(shí)現(xiàn)的排序?qū)W習(xí)方法的開源軟件包.目前常用的排序?qū)W習(xí)方法軟件包有RankLib、QuickRank、Lerot、L2RLab、ESRank、LTR、MLR-master和SVMrank等.

RankLib7https://sourceforge.net/p/lemur/code/HEAD/tree/RankLib/是一個(gè)優(yōu)秀的基于Java語言的排序?qū)W習(xí)方法庫(kù)的開源實(shí)現(xiàn),隸屬于美國(guó)的馬薩諸塞大學(xué)和卡內(nèi)基梅隆大學(xué)合作項(xiàng)目Lemur,該款軟件被廣泛采用.RankLib是由馬薩諸塞大學(xué)的研究者vdang開發(fā)的一個(gè)排序?qū)W習(xí)方法軟件包,當(dāng)前已經(jīng)實(shí)現(xiàn)了 8種流行的方法,包括 MART、RankNet、RankBoost、AdaRank、ListNet、Coordinate ascent、LambdaMART 和Random forests.它實(shí)現(xiàn)了許多信息檢索的評(píng)價(jià)標(biāo)準(zhǔn),同時(shí)還提供了多種執(zhí)行方式去實(shí)施評(píng)價(jià).

QuickRank8https://github.com/hpclab/quickrank,9http://quickrank.isti.cnr.it是一款高性能排序?qū)W習(xí)工具箱,提供了一些排序?qū)W習(xí)方法的C++多線程實(shí)現(xiàn),能將基于學(xué)習(xí)樹的模型翻譯為可用于快速評(píng)分文檔的高效的C++源代碼,注重于效率方面的設(shè)計(jì)和開發(fā).目前,在該套裝工具箱中實(shí)現(xiàn)了GBRT、LamdaMART、Oblivious GBRT/LamdaMART、Coordinate ascent、Line search、RankBoost、CLEAVER、X-CLEAVER 和X-DART等方法.QuickRank還引入了前期和后期學(xué)習(xí)的優(yōu)化器理念,即排序?qū)W習(xí)方法可在執(zhí)行訓(xùn)練階段之前或之后被執(zhí)行.優(yōu)化器可以根據(jù)其定義處理數(shù)據(jù)集或模型,可以通過設(shè)置相應(yīng)的選項(xiàng)同訓(xùn)練階段一起在流水線上執(zhí)行,或作為一個(gè)獨(dú)立的進(jìn)程工作在以前受過訓(xùn)練的模型或數(shù)據(jù)集上.目前,在QuickRank中已實(shí)現(xiàn)了CLEAVER優(yōu)化器,該優(yōu)化器在后期學(xué)習(xí)中剪枝一個(gè)集成模型以提高優(yōu)化器的效率而不會(huì)妨礙其有效性.

Lerot10https://bitbucket.org/ilps/lerot軟件包是由微軟劍橋研究院Katja Hofmann和荷蘭的阿姆斯特丹大學(xué)Anne Schuth等為信息檢索而開發(fā)的一個(gè)在線排序?qū)W習(xí)方法框架,該框架是為在線排序?qū)W習(xí)方法運(yùn)行實(shí)驗(yàn)而設(shè)計(jì).Lerot提供了一個(gè)對(duì)在線排序?qū)W習(xí)方法進(jìn)行評(píng)估和實(shí)驗(yàn)的解決方案,是一個(gè)開源的軟件,其代碼易于加入新的在線排序?qū)W習(xí)方法和/或反饋機(jī)制而被擴(kuò)展.目前,包括了一些在線學(xué)習(xí)算法、交互方法和一套完整的評(píng)價(jià)方法,并已有在線排序?qū)W習(xí)方法作為插件集成到搜索引擎solr中.

LTR11https://github.com/yaschool/ltr,12http://yaschool.github.io/ltr/index.html軟件包是一個(gè)用于解決機(jī)器學(xué)習(xí)問題的開源C++算法庫(kù),包括排序、分類和回歸問題.LTR的主要思想是源代碼的易于擴(kuò)展性和泛化性,通過廣泛使用C++模板和多態(tài)性而實(shí)現(xiàn)的.在當(dāng)前的LTR算法庫(kù)中,實(shí)現(xiàn)了以下算法:分類 (kNN、Naive Bayes、QDA、Fisher LDA)、回歸(LSM)、排序(RankGP 和Linear ranker)、集成(Boosting、Bagging和RSM).用戶可以在該軟件包中添加自己編寫的代碼以執(zhí)行學(xué)習(xí)和測(cè)試,也可以使用該軟件包中帶有人工可讀的配置文件的控制臺(tái)應(yīng)用程序.每一個(gè)訓(xùn)練有素的排序器/分類器/回歸器可以在C++代碼中被序列化,以便不依賴于LTR算法庫(kù)而被使用在其他項(xiàng)目上.

L2RLab[123]是為排序?qū)W習(xí)所開發(fā)的一個(gè)集成的實(shí)驗(yàn)環(huán)境,它集成了新排序?qū)W習(xí)模型的開發(fā)、評(píng)估、比較和分析性能以輔助排序?qū)W習(xí)研究者開展實(shí)驗(yàn).L2RLab軟件包主要由兩大模塊構(gòu)成:可視化應(yīng)用程序界面和一個(gè)有助于添加由研究人員所開發(fā)的新算法和性能度量指標(biāo)的框架,其主要功能包括數(shù)據(jù)集的預(yù)處理、模型的訓(xùn)練和測(cè)試、模型的分析和比較.L2RLab易于添加新的排序?qū)W習(xí)方法,提供了易于使用的接口以避免實(shí)驗(yàn)應(yīng)用的重新編碼,其系統(tǒng)接口允許用戶去設(shè)置和控制實(shí)驗(yàn)執(zhí)行,執(zhí)行的結(jié)果可以數(shù)字和圖形的可視化方式展現(xiàn).目前,L2RLab中包含RankPSO等很少量的排序?qū)W習(xí)方法.

ESRank13http://www.cs.nott.ac.uk/psxoi/ESRank.zip是英國(guó)諾丁漢大學(xué)和米尼亞大學(xué)的Osman Ali Sadek Ibrahim等實(shí)現(xiàn)的基于進(jìn)化策略的排序?qū)W習(xí)方法ES-Rank的JAR包.

MLR-master14https://github.com/bmcfee/mlr/軟件包由美國(guó)加利福尼亞大學(xué)的Brian McFee和Daryl Lim開發(fā)的一款排序?qū)W習(xí)方法的工具,包括Metric learning to rank(MLR)和Robust MLR的代碼.該軟件包基于結(jié)構(gòu)化SVM框架,支持不同排序評(píng)價(jià)準(zhǔn)則,如AUC,Precision@k,MRR,MAP和NDCG.

SVMrank15http://www.cs.cornell.edu/People/tj/svm light/svmrank.html#References是為有效地訓(xùn)練排序SVM 的結(jié)構(gòu)化SVM 的一個(gè)實(shí)例,由美國(guó)康乃爾大學(xué)的Thorsten Joachims在具有GNU編譯器套件(GCC)的Linux操作系統(tǒng)上開發(fā)實(shí)現(xiàn)的一個(gè)早期的排序?qū)W習(xí)方法Ranking SVM 的開源軟件.后期有研究者開發(fā)實(shí)現(xiàn)了該方法的C++版16http://dlib.net/svmrankex.cpp.html和Python版17http://dlib.net/svm rank.py.html的代碼.

表4從開發(fā)語言、特點(diǎn)和來源這3個(gè)方面歸納了各種排序?qū)W習(xí)方法軟件包的相關(guān)信息.

表4 排序?qū)W習(xí)方法軟件包Table 4 Software packages of the learning to rank approaches

6 排序?qū)W習(xí)發(fā)展趨勢(shì)

排序?qū)W習(xí)不僅在學(xué)術(shù)界得到了積極的研究,而且在工業(yè)界也取得了廣泛的發(fā)展.在排序?qū)W習(xí)理論與方法方面,研究人員豐富了機(jī)器學(xué)習(xí)的相關(guān)理論并提出了多種不同的排序?qū)W習(xí)方法;在排序?qū)W習(xí)實(shí)際產(chǎn)品應(yīng)用方面,已經(jīng)成為各個(gè)互聯(lián)網(wǎng)搜索引擎和推薦系統(tǒng)等應(yīng)用中網(wǎng)頁(yè)、物品等對(duì)象排序的核心技術(shù),很多知名的互聯(lián)網(wǎng)公司如Bing、Yandex、Yahoo、百度和搜狗等搜索引擎和大型電子商務(wù)平臺(tái)如eBay、亞馬遜、淘寶天貓、1號(hào)店、國(guó)美等,在很大程度上都依賴于排序?qū)W習(xí)方法為用戶提供高質(zhì)量的搜索、推薦和廣告等排序結(jié)果.盡管,排序?qū)W習(xí)已取得了較多的成果和較大的成功,但在排序?qū)W習(xí)領(lǐng)域中仍還有許多相關(guān)的問題尚未完全探討,下面分別從排序?qū)W習(xí)的理論、方法、應(yīng)用、需求場(chǎng)景、數(shù)據(jù)集和評(píng)價(jià)指標(biāo)等方面總結(jié)在未來值得做進(jìn)一步研究的排序?qū)W習(xí)問題.

6.1 排序?qū)W習(xí)理論研究

Chapelle等[124]指出:通過基準(zhǔn)實(shí)驗(yàn),許多排序?qū)W習(xí)方法已被證明是有效的.然而,因?yàn)樾∫?guī)模測(cè)試數(shù)據(jù)和訓(xùn)練,有時(shí)基準(zhǔn)實(shí)驗(yàn)是不可靠的.在這種情況下,排序?qū)W習(xí)理論是必要的,以保證在無限未知的數(shù)據(jù)訓(xùn)練中排序?qū)W習(xí)方法的性能.他還指出排序?qū)W習(xí)理論已經(jīng)有了一些嘗試,但仍還有很大的發(fā)展空間去探索以解決以下難點(diǎn)問題:1)關(guān)于數(shù)據(jù)生成(例如,查詢和文檔)的一個(gè)合理假設(shè);2)關(guān)于代理?yè)p失函數(shù)的一個(gè)泛化界;3)代理?yè)p失函數(shù)和排序度量標(biāo)準(zhǔn)之間的關(guān)系;4)當(dāng)文檔的數(shù)量接近于無限時(shí),排序度量標(biāo)準(zhǔn)的極限的存在性等.

6.2 排序?qū)W習(xí)方法展望

隨著機(jī)器學(xué)習(xí)技術(shù)的不斷發(fā)展和改進(jìn),排序?qū)W習(xí)方法也需不斷跟進(jìn)和完善.基于一些新興的智能優(yōu)化算法、深度學(xué)習(xí)或其他新型機(jī)器學(xué)習(xí)技術(shù),在未來可嘗試運(yùn)用它們開發(fā)出新的排序?qū)W習(xí)方法以追求更高的效果和效率.

6.2.1 基于新興或混合型智能優(yōu)化算法的排序?qū)W習(xí)

當(dāng)前,雖已有較多的研究成果運(yùn)用進(jìn)化算法去設(shè)計(jì)排序?qū)W習(xí)方法,但運(yùn)用新近開發(fā)的智能優(yōu)化算法設(shè)計(jì)排序?qū)W習(xí)方法的研究仍還較少.近年來不斷涌現(xiàn)出了一些新興的智能優(yōu)化算法,如煙花算法、螢火蟲算法、布谷鳥搜索算法、隨機(jī)蛙跳算法、猴子搜索算法、蝙蝠算法、花朵授粉算法、細(xì)菌覓食優(yōu)化算法、稻田算法和智能水滴算法等,如何結(jié)合排序?qū)W習(xí)問題,基于這些新興的智能優(yōu)化算法或與已有的智能優(yōu)化算法融合成更為高效的新型混合智能優(yōu)化算法去設(shè)計(jì)排序?qū)W習(xí)方法,從而更高效地解決信息檢索中的排序?qū)W習(xí)問題,是一個(gè)值得去開辟和嘗試的研究方向.

6.2.2 基于深度學(xué)習(xí)的排序?qū)W習(xí)

深度學(xué)習(xí)是近年來最受矚目的技術(shù)熱點(diǎn)之一,它已經(jīng)成為了工業(yè)界解決眾多應(yīng)用問題的神器.目前,深度學(xué)習(xí)的主要模型有卷積神經(jīng)網(wǎng)絡(luò)、遞歸神經(jīng)網(wǎng)絡(luò)、深度信念網(wǎng)絡(luò)、限制玻爾茲曼機(jī)、自動(dòng)編碼器、長(zhǎng)短時(shí)記憶網(wǎng)絡(luò)和生成式對(duì)抗網(wǎng)絡(luò)[125]等.還有一些蓄勢(shì)待發(fā)的基于深度學(xué)習(xí)與其他方法結(jié)合的混合學(xué)習(xí)方法正在引領(lǐng)前沿,如深度強(qiáng)化學(xué)習(xí)、深度遷移學(xué)習(xí)、深度貝葉斯學(xué)習(xí)和深度森林等.

國(guó)際學(xué)術(shù)界公認(rèn)的“排序?qū)W習(xí)”領(lǐng)域的代表人物L(fēng)i等[126]指出深度學(xué)習(xí)的一些基本技術(shù)(如單詞嵌入、遞歸神經(jīng)網(wǎng)絡(luò)和卷積神經(jīng)網(wǎng)絡(luò))已經(jīng)應(yīng)用于圖像和語音領(lǐng)域、自然語言處理和信息檢索領(lǐng)域,如圖像搜索、機(jī)器翻譯和知識(shí)問答等.最近有些研究者對(duì)深度學(xué)習(xí)在自然語言處理[127]、控制領(lǐng)域[128]、人體行為識(shí)別[129]、視頻目標(biāo)跟蹤[130]等領(lǐng)域進(jìn)行了綜述.Wang等[131]為L(zhǎng)istwise排序?qū)W習(xí)方法提出了一種基于注意力的深層神經(jīng)網(wǎng)絡(luò),可更好地將查詢和搜索結(jié)果的不同嵌入(如卷積神經(jīng)網(wǎng)絡(luò)或word2vec模型)與基于注意力的機(jī)制進(jìn)行融合.Severyn等[132]用卷積深神經(jīng)網(wǎng)絡(luò)對(duì)短文本進(jìn)行排序?qū)W習(xí).程學(xué)旗等[133]指出利用深度學(xué)習(xí)方法自動(dòng)學(xué)習(xí)多樣性排序特征和樣本之間的依賴關(guān)系也是一個(gè)非常有前景的方向.

這些研究為深度學(xué)習(xí)技術(shù)運(yùn)用于排序?qū)W習(xí)問題中開辟了思路,期待開發(fā)出更多基于深度學(xué)習(xí)的排序?qū)W習(xí)方法以增強(qiáng)大規(guī)模排序?qū)W習(xí)的效果和效率.

6.2.3 基于其他新型機(jī)器學(xué)習(xí)技術(shù)的排序?qū)W習(xí)

近年來,隨著云計(jì)算技術(shù)和大數(shù)據(jù)的發(fā)展,互聯(lián)網(wǎng)數(shù)據(jù)量的劇增和機(jī)器計(jì)算能力的提高,人工智能再次飛速發(fā)展,新型機(jī)器學(xué)習(xí)技術(shù)和新的機(jī)器學(xué)習(xí)理論框架也不斷被提出,比如在線機(jī)器學(xué)習(xí)、對(duì)偶學(xué)習(xí)、對(duì)抗學(xué)習(xí)、指示學(xué)習(xí)、多視圖學(xué)習(xí)、終身學(xué)習(xí)、元學(xué)習(xí)和平行學(xué)習(xí)[134]等.基于這些新型的機(jī)器學(xué)習(xí)技術(shù)和理論框架,結(jié)合排序?qū)W習(xí)問題的特點(diǎn),開發(fā)新型排序?qū)W習(xí)方法,提高排序?qū)W習(xí)方法的效果和效率,也許有些新的排序?qū)W習(xí)方法還是應(yīng)對(duì)大數(shù)據(jù)時(shí)代搜索引擎和推薦系統(tǒng)等實(shí)際應(yīng)用中排序問題的有效途徑.

設(shè)計(jì)排序?qū)W習(xí)方法關(guān)鍵在于依據(jù)排序?qū)W習(xí)問題所轉(zhuǎn)化為分類、回歸、序數(shù)回歸和凸優(yōu)化等問題,如何定義輸入輸出空間、假設(shè)空間、損失函數(shù)或優(yōu)化目標(biāo).而設(shè)計(jì)新的排序?qū)W習(xí)方法的難點(diǎn)問題是如何依據(jù)排序?qū)W習(xí)問題的特點(diǎn),結(jié)合新的機(jī)器學(xué)習(xí)技術(shù),設(shè)計(jì)出新穎高效的排序?qū)W習(xí)方法.

6.3 排序?qū)W習(xí)方法應(yīng)用領(lǐng)域的拓展及不同排序?qū)W習(xí)方法的應(yīng)用檢驗(yàn)

目前,有些排序?qū)W習(xí)方法已經(jīng)成功應(yīng)用于較多領(lǐng)域解決相應(yīng)的一些排序問題,如Web搜索和推薦系統(tǒng)等,渴望能拓展到更多的應(yīng)用領(lǐng)域中,如資源配置、模式識(shí)別等.對(duì)于需要排序的應(yīng)用問題,只要能提取出若干排序特征以構(gòu)建排序?qū)W習(xí)數(shù)據(jù)集,都可嘗試運(yùn)用排序?qū)W習(xí)方法去解決.針對(duì)實(shí)際應(yīng)用問題,提取什么樣的排序特征以及如何合理度量排序特征設(shè)計(jì)損失函數(shù)或優(yōu)化目標(biāo)是需要解決的難點(diǎn)問題.

雖然排序?qū)W習(xí)方法已經(jīng)成功地應(yīng)用于如Bing,雅虎搜索、百度和Yandex等搜索引擎公司和如eBay、淘寶天貓、1號(hào)店、美團(tuán)和國(guó)美等大型電子商務(wù)平臺(tái),但真正用于具體的排序系統(tǒng)中的排序?qū)W習(xí)方法卻很少,主要是RankNet和LambdaMART等,大部分排序?qū)W習(xí)方法并沒有在實(shí)際的排序應(yīng)用場(chǎng)景中得到相應(yīng)檢驗(yàn),期待更多真實(shí)的搜索引擎或推薦系統(tǒng)等應(yīng)用中的排序系統(tǒng)將更多的排序?qū)W習(xí)方法進(jìn)行性能檢驗(yàn),并將性能最優(yōu)秀的排序?qū)W習(xí)方法融入其中.

6.4 排序?qū)W習(xí)需求場(chǎng)景的探討

隨著互聯(lián)網(wǎng)上千差萬別的網(wǎng)民涌現(xiàn)、排序?qū)W習(xí)應(yīng)用領(lǐng)域的不斷擴(kuò)展,所需求的排序場(chǎng)景也趨于多樣化,不再只是僅僅追求排序模型的有效性,對(duì)排序模型的魯棒性、多樣性和可信性等以及排序?qū)W習(xí)方法的自適應(yīng)性和高效率等,在一些實(shí)際的應(yīng)用場(chǎng)景中也是非常重要的.為此,不同排序場(chǎng)景需求的排序?qū)W習(xí)是未來迫切需要探討、解決的問題.

6.4.1 魯棒性排序?qū)W習(xí)

當(dāng)前,排序?qū)W習(xí)方法方面,已有的絕大部分工作中,是去比較和評(píng)估多個(gè)排序函數(shù),基于一些信息檢索度量指標(biāo)(如NDCG、ERR等)選擇一個(gè)最佳的排序函數(shù),通過制定先進(jìn)的排序功能和/或開發(fā)復(fù)雜的排序?qū)W習(xí)方法提高檢索結(jié)果的平均有效性.然而,相對(duì)于簡(jiǎn)單的基準(zhǔn),這些方法通常會(huì)提高搜索結(jié)果的平均性能,但往往忽視了魯棒性的重要問題[6].而對(duì)于一個(gè)商業(yè)搜索引擎公司,其真實(shí)的場(chǎng)景是更復(fù)雜的:伴隨著更多的訓(xùn)練數(shù)據(jù)、新近開發(fā)的排序特征、或更神奇的排序算法,需要周期性地更新和改進(jìn)排序函數(shù),但排序結(jié)果不應(yīng)顯著性地發(fā)生改變.如此需求將對(duì)排序?qū)W習(xí)領(lǐng)域的魯棒性帶來新的挑戰(zhàn)[124]:1)如何度量排序模型的魯棒性?2)如何學(xué)習(xí)一個(gè)強(qiáng)魯棒性的排序模型?

研究者們對(duì)排序模型的魯棒性問題進(jìn)行了積極的探索.TREC 2013 web track和TREC 2014 web track都為Web評(píng)價(jià)算法提出了一個(gè)風(fēng)險(xiǎn)敏感的檢索任務(wù).Wang等[6]討論了排序?qū)W習(xí)中的魯棒性問題.Din?cer等[135?137]從風(fēng)險(xiǎn)敏感參數(shù)加權(quán)線性組合、學(xué)生t檢驗(yàn)和卡方統(tǒng)計(jì)等理論中提出了一些風(fēng)險(xiǎn)敏感的度量和選擇單/多基準(zhǔn)來研究檢索系統(tǒng)的魯棒性.Ding等[138]從噪音數(shù)據(jù)中進(jìn)行排序?qū)W習(xí).Li等[61]提出了一種風(fēng)險(xiǎn)敏感的魯棒性排序?qū)W習(xí)方法以均衡有效性和魯棒性.盡管已取得了一些研究成果,但更合理地度量排序模型的魯棒性和更好地學(xué)習(xí)一個(gè)強(qiáng)魯棒性的排序模型是值得進(jìn)一步作深入探討的研究問題.因此,設(shè)計(jì)更優(yōu)秀的魯棒性排序?qū)W習(xí)方法是一項(xiàng)具有挑戰(zhàn)性的創(chuàng)新工作.

6.4.2 多樣性排序?qū)W習(xí)

現(xiàn)有排序?qū)W習(xí)方法主要關(guān)注于檢索結(jié)果的有效性,大部分缺乏考慮多樣性等質(zhì)量指標(biāo),導(dǎo)致所呈現(xiàn)給用戶的檢索結(jié)果較單一,難以滿足用戶的不同信息需求.考慮多樣性質(zhì)量指標(biāo)也逐漸成為衡量搜索引擎和推薦系統(tǒng)好壞的重要因素,為此有必要建立符合實(shí)際需求的優(yōu)化目標(biāo).考慮多樣性質(zhì)量指標(biāo)時(shí),難以合理有效地度量和均衡.這也將帶來新的挑戰(zhàn):如何度量排序模型的多樣性?如何學(xué)習(xí)相應(yīng)的多樣性排序函數(shù)?

在排序結(jié)果的多樣化方法方面,Liang等[139]提出多元數(shù)據(jù)融合方法以提升搜索結(jié)果的多樣性.Liang等[140]使用監(jiān)督學(xué)習(xí)策略解決個(gè)性化的搜索結(jié)果多樣化問題.Wu等[141]提出了一類支持結(jié)果多樣化的數(shù)據(jù)融合方法.Deng等[142]調(diào)研了查詢結(jié)果多樣化的復(fù)雜性問題.

中科院計(jì)算所研究員程學(xué)旗團(tuán)隊(duì)在多樣性排序?qū)W習(xí)方面做出了突出的貢獻(xiàn).他們考慮排序結(jié)果的多樣化,提出了一種通過直接優(yōu)化任意多樣性評(píng)估度量指標(biāo)學(xué)習(xí)關(guān)系排序模型的新的多樣性排序?qū)W習(xí)的通用框架[143]和3種多樣性排序?qū)W習(xí)方法[18,24,144],他們分別采用隨機(jī)梯度下降法、感知機(jī)和神經(jīng)張量網(wǎng)絡(luò)去學(xué)習(xí)排序模型,取得了很好的效果.同時(shí),他們團(tuán)隊(duì)[133,145]指出由于搜索結(jié)果多樣化任務(wù)本身的復(fù)雜性,多樣化評(píng)價(jià)準(zhǔn)則本身不可導(dǎo)和不連續(xù),使得直接對(duì)其進(jìn)行優(yōu)化仍然存在許多有待解決的困難,并指出多樣化是排序?qū)W習(xí)發(fā)展的一個(gè)新方向,還面臨很多挑戰(zhàn),需要不斷探索.

6.4.3 可信性排序?qū)W習(xí)

互聯(lián)網(wǎng)中蘊(yùn)藏著海量的網(wǎng)頁(yè)資源,其中不乏作弊、不可信和惡意網(wǎng)頁(yè)(Web spam),其信息良莠不齊,將嚴(yán)重影響排序結(jié)果的質(zhì)量.同時(shí),網(wǎng)頁(yè)信息的可信與否難以確定、可信與不可信也不好度量.若一個(gè)檢索結(jié)果中充斥了大量的不可信信息,將增加用戶檢索有用信息的難度,嚴(yán)重惡化用戶的檢索體驗(yàn),是互聯(lián)網(wǎng)信息檢索所面臨的最大挑戰(zhàn)之一.因此,研究可信性排序?qū)W習(xí)問題,設(shè)計(jì)可信性度量指標(biāo)和可信性排序?qū)W習(xí)方法以訓(xùn)練可信性排序模型,從而提高排序結(jié)果的可信性,對(duì)改善用戶體驗(yàn)具有重要意義.

現(xiàn)有相關(guān)工作往往忽略了網(wǎng)頁(yè)信息的可信性,已公開發(fā)表的考慮可信性質(zhì)量指標(biāo)的排序?qū)W習(xí)問題的研究成果較少,大多是對(duì)Web spam進(jìn)行檢測(cè)過濾,即使有的研究考慮到搜索結(jié)果的可信性,但大多是將可信性和相關(guān)性各質(zhì)量指標(biāo)聚合在單個(gè)目標(biāo)中,掩蓋了各單個(gè)質(zhì)量指標(biāo)的值.針對(duì)可信性排序?qū)W習(xí)問題,所要解決的重難點(diǎn)問題主要是可信和不可信排序特征的提取和度量、排序模型的可信性度量以及高可信排序模型的學(xué)習(xí).

6.4.4 多目標(biāo)排序?qū)W習(xí)

近年來,為了更進(jìn)一步提高用戶對(duì)信息需求的滿意度,研究人員不僅考慮搜索結(jié)果質(zhì)量的相關(guān)性,且更多地關(guān)注于排序結(jié)果的多樣性、新鮮性等方面,也掀起了一些多目標(biāo)排序?qū)W習(xí)方面的研究.Dai等[146]指出監(jiān)督排序?qū)W習(xí)方法通常追求高相關(guān)性的優(yōu)化而忽略搜索結(jié)果質(zhì)量的其他方面,如新鮮性和多樣性.他們通過開采混合標(biāo)注,將多個(gè)方面(如新鮮性與相關(guān)性)的目標(biāo)進(jìn)行組合以產(chǎn)生總的質(zhì)量,使用排序?qū)W習(xí)方法RankSVM去優(yōu)化模型參數(shù).Svore等[147]考慮了多個(gè)度量策略作為訓(xùn)練目標(biāo),提供了在多個(gè)被分級(jí)的度量策略上進(jìn)行優(yōu)化的解決方案,將多種度量合并成可以學(xué)習(xí)的一個(gè)單一的梯度度量,采用LambdaMART排序?qū)W習(xí)方法去優(yōu)化.Kang等[148]提出了一種在排序?qū)W習(xí)場(chǎng)景中垂直搜索的多方面(如匹配度、距離、聲譽(yù)等)相關(guān)性構(gòu)想.還有如前所指出的魯棒性排序?qū)W習(xí)、多樣性排序?qū)W習(xí)和可信性排序?qū)W習(xí),都可考慮轉(zhuǎn)化為多目標(biāo)排序?qū)W習(xí).

上述研究雖然在排序?qū)W習(xí)方法中同時(shí)考慮了相關(guān)性和其他多方面質(zhì)量指標(biāo),但其優(yōu)化的目標(biāo)僅為一個(gè)融合多方面質(zhì)量指標(biāo)的目標(biāo)函數(shù),這帶來了如何為各質(zhì)量指標(biāo)合理設(shè)置權(quán)重的難點(diǎn)問題,在用戶缺乏先驗(yàn)知識(shí)的情況下難以處理.因此,為有效地均衡相關(guān)性和多方面質(zhì)量指標(biāo),需尋求可同時(shí)優(yōu)化多個(gè)獨(dú)立的目標(biāo)函數(shù)的多目標(biāo)排序?qū)W習(xí)方法,這也是一項(xiàng)具有挑戰(zhàn)性的創(chuàng)新工作.設(shè)計(jì)多目標(biāo)排序?qū)W習(xí)方法的難點(diǎn)在于排序模型的多個(gè)優(yōu)化目標(biāo)函數(shù)的合理設(shè)計(jì)和均衡以及排序模型的效果和排序?qū)W習(xí)的效率之間的均衡.

6.4.5 自適應(yīng)排序?qū)W習(xí)

現(xiàn)有主流的檢索系統(tǒng)通常只有一個(gè)通用的排序特征集和從這些特征集中所學(xué)到的或經(jīng)驗(yàn)得到的相同排序模型.不同的查詢?cè)~在同一排序模型下的性能表現(xiàn)大體上也是不同的,采用同一排序模型是難以保證為所有的用戶和查詢都能較好的工作,缺少針對(duì)不同場(chǎng)景的不同排序模型.為此,可針對(duì)不同場(chǎng)景(如凸顯魯棒性、多樣性、可信性和馬太效應(yīng)等)應(yīng)用不同排序特征去訓(xùn)練相應(yīng)排序模型,依據(jù)查詢?cè)~所屬場(chǎng)景選擇不同的排序模型.那么,如何使檢索信息匹配檢索場(chǎng)景,以感知不同的應(yīng)用場(chǎng)景而自適應(yīng)地調(diào)用不同的排序模型?為此,需提出基于多維度質(zhì)量指標(biāo)的自適應(yīng)排序?qū)W習(xí)以感知不同需求場(chǎng)景而自適應(yīng)地調(diào)用不同場(chǎng)景的排序模型.如何正確地識(shí)別需求場(chǎng)景,并能自適應(yīng)地調(diào)用對(duì)應(yīng)場(chǎng)景的排序模型是需解決的難點(diǎn)問題.期待出現(xiàn)更多應(yīng)用場(chǎng)景、更炫的自適應(yīng)排序?qū)W習(xí)方法,推動(dòng)排序?qū)W習(xí)研究向?qū)嵱没~進(jìn),以應(yīng)對(duì)更復(fù)雜的真實(shí)搜索、推薦場(chǎng)景,以進(jìn)一步提高排序結(jié)果質(zhì)量和用戶滿意度.

6.4.6 大數(shù)據(jù)排序?qū)W習(xí)

隨著互聯(lián)網(wǎng)大數(shù)據(jù)的快速發(fā)展,可構(gòu)建的排序?qū)W習(xí)大數(shù)據(jù)越來越大,其類型也越來越多.現(xiàn)有排序?qū)W習(xí)方法絕大部分存在高度迭代,面對(duì)大數(shù)據(jù),如此排序?qū)W習(xí)方法訓(xùn)練排序模型時(shí)間較長(zhǎng),內(nèi)存消耗較大,效率低下,尤其是在需要實(shí)時(shí)處理數(shù)據(jù)的領(lǐng)域,問題尤為突出.為了維持在大數(shù)據(jù)上的排序速度,傳統(tǒng)的以效果為中心的排序?qū)W習(xí)方法需要額外的硬件和能耗,所付出的代價(jià)昂貴[149].為了取得排序的效果和效率的持續(xù)改進(jìn),在保證一定排序效果的前提下,并行化排序?qū)W習(xí)方法以加快排序模型的訓(xùn)練速度,可提高排序?qū)W習(xí)方法的效率.Wang等[149]針對(duì)大數(shù)據(jù)環(huán)境,提出了一個(gè)共同優(yōu)化有效性(相關(guān)性)和效率(速度)的排序?qū)W習(xí)的統(tǒng)一框架和能捕獲這兩個(gè)競(jìng)爭(zhēng)目標(biāo)間均衡的新度量標(biāo)準(zhǔn).Cao等[150]提出了一種大數(shù)據(jù)環(huán)境下的分布式排序?qū)W習(xí)方法.

由于現(xiàn)有排序?qū)W習(xí)方法大多是基于內(nèi)存的,無法將大數(shù)據(jù)一次性裝載進(jìn)計(jì)算機(jī)內(nèi)存,故需提出新型數(shù)據(jù)并行、模型并行的排序?qū)W習(xí)方法以適應(yīng)大數(shù)據(jù)處理的需求.在大數(shù)據(jù)時(shí)代,大數(shù)據(jù)排序?qū)W習(xí)是未來的發(fā)展趨勢(shì)之一,其關(guān)鍵在于突破內(nèi)存限制,設(shè)計(jì)能快速有效均衡效果和效率的大數(shù)據(jù)排序?qū)W習(xí)方法.

6.4.7 大規(guī)模分布式并行排序?qū)W習(xí)

現(xiàn)有大部分排序?qū)W習(xí)方法是以串行方式訓(xùn)練排序模型的,當(dāng)面對(duì)大規(guī)模排序?qū)W習(xí)數(shù)據(jù)集時(shí),這是很難去保證其學(xué)習(xí)效率.隨著多核處理器、云計(jì)算技術(shù)、并行編程模型等的快速發(fā)展,為開發(fā)大規(guī)模分布式并行排序?qū)W習(xí)方法提供了一條可行之道.可將適用于處理大規(guī)模數(shù)據(jù)的機(jī)器學(xué)習(xí)方法,如感知機(jī)、神經(jīng)網(wǎng)絡(luò)、支持向量機(jī)、梯度提升決策樹、隨機(jī)森林和進(jìn)化算法等在并行編程模型如MapReduce和Spark等框架下,將它們并行化,設(shè)計(jì)分布式并行排序?qū)W習(xí)方法.目前,研究者們已開發(fā)了少量的分布式并行排序?qū)W習(xí)方法.Sculley[151]關(guān)注于在大規(guī)模數(shù)據(jù)集上進(jìn)行學(xué)習(xí)的排序?qū)W習(xí)方法.通過從一個(gè)隱式的Pairwise擴(kuò)展索引中采樣樣本對(duì),并應(yīng)用有效的隨機(jī)梯度下降學(xué)習(xí)器去學(xué)習(xí)排序模型,從而提高大規(guī)模排序?qū)W習(xí)的效率.Shukla等[152]在Spark分布式集群計(jì)算系統(tǒng)上并行化ListNet排序?qū)W習(xí)方法.Wang等[59]提出了一種基于協(xié)同進(jìn)化算法的并行排序?qū)W習(xí)框架.Tian等[60]設(shè)計(jì)了基于并行B細(xì)胞算法的排序?qū)W習(xí)方法以改進(jìn)收斂率和運(yùn)行速度,提高最優(yōu)解的質(zhì)量.

再者,由于現(xiàn)實(shí)世界中待排序樣本大量涌現(xiàn),因此算法的可擴(kuò)展性成為更加棘手的問題,目前隨機(jī)、在線等優(yōu)化策略已經(jīng)在解決大規(guī)模分類問題中表現(xiàn)出優(yōu)越性,如何結(jié)合這些技術(shù)并且有針對(duì)性地設(shè)計(jì)大規(guī)模分布式并行排序?qū)W習(xí)方法也將是我們今后的研究方向,其思路可從數(shù)據(jù)并行、算法并行和數(shù)據(jù)算法混合并行三方面去開展該研究.

6.4.8 在線增量式排序?qū)W習(xí)

傳統(tǒng)上,排序?qū)W習(xí)方法以批處理模式在一個(gè)由查詢和文檔對(duì)以及與它們相關(guān)聯(lián)的手動(dòng)創(chuàng)建的相關(guān)性標(biāo)注所構(gòu)建的完整數(shù)據(jù)集上被訓(xùn)練,是一種離線方式.這種方式有許多缺點(diǎn),且在許多情況下是不切實(shí)際的.首先,創(chuàng)建如此數(shù)據(jù)集是昂貴的,因此對(duì)于較小的搜索引擎,比如小的網(wǎng)絡(luò)存儲(chǔ)搜索引擎,是不可行的.其次,對(duì)于專家標(biāo)注文檔相關(guān)性,如在個(gè)性化搜索的情況下,它也許是不可能的.再者,文檔對(duì)查詢的相關(guān)性會(huì)隨著時(shí)間的推移而改變,如在新聞搜索引擎中[153].因此,許多在線排序?qū)W習(xí)方法開發(fā)出來以解決此問題.

Suhara等[154]提出了在線排序?qū)W習(xí)方法.Hofmann等[155]給出了如何平衡信息檢索中Listwise和Pairwise在線排序?qū)W習(xí)的勘探和開采.Chen等[156]提出了在線排序?qū)W習(xí)方法,并比較了在線排序?qū)W習(xí)的絕對(duì)反饋和相對(duì)反饋方法.Grotov等[153]總結(jié)了在線排序?qū)W習(xí)所使用的一些算法,如Bandit算法、決斗強(qiáng)盜梯度下降(Dueling bandit gradient descent,DBGD)等.Schuth等[157]擴(kuò)展了DBGD為概率多級(jí)梯度下降,提出了一種多級(jí)梯度下降的快速在線排序?qū)W習(xí)方法.Zhao等[10]通過構(gòu)建魯棒的梯度探索方向,提出了兩種方法改進(jìn)在線排序?qū)W習(xí)方法.

通常,在線排序?qū)W習(xí)方法是從用戶的交互數(shù)據(jù)中而不是從已標(biāo)注的數(shù)據(jù)集中學(xué)習(xí),基于用戶實(shí)時(shí)點(diǎn)擊反饋數(shù)據(jù)進(jìn)行增量學(xué)習(xí),它能快速學(xué)習(xí)原始排序列表的前端的最佳重排序.增量學(xué)習(xí)強(qiáng)調(diào)如何基于環(huán)境而行動(dòng),以取得最大化的預(yù)期利益.Keyhanipour等[158]提出了一種在增量學(xué)習(xí)框架下具有點(diǎn)擊特征的排序?qū)W習(xí)方法.盡管現(xiàn)已開發(fā)出一些在線排序?qū)W習(xí)方法,但由于用戶交互數(shù)據(jù)具有偏見和噪音,如何盡可能地消除偏見和噪音的影響,開發(fā)更優(yōu)秀的在線增量式排序?qū)W習(xí)方法以快速可靠地從用戶交互數(shù)據(jù)中學(xué)習(xí)仍是一個(gè)主要挑戰(zhàn).

6.4.9 基于用戶行為的個(gè)性化排序?qū)W習(xí)

傳統(tǒng)搜索引擎對(duì)不同用戶的查詢所返回的搜索結(jié)果的排序是相同的,然而有時(shí)不同用戶對(duì)相同查詢會(huì)有不同的意圖,這就要求排序?qū)W習(xí)方法能適應(yīng)個(gè)性化搜索和推薦等服務(wù),能針對(duì)不同用戶的查詢和信息需求,呈現(xiàn)出可滿足不同用戶個(gè)性化偏好的排序結(jié)果.為此,可將個(gè)人信息和用戶行為等融入到排序?qū)W習(xí)中,設(shè)計(jì)基于用戶行為的個(gè)性化排序?qū)W習(xí)方法,最終達(dá)到個(gè)性化排序的要求,這是一個(gè)有挑戰(zhàn)的任務(wù),其關(guān)鍵是要解決如何正確地從用戶行為中識(shí)別用戶真實(shí)意圖以及如何融入用戶行為設(shè)計(jì)感知用戶意圖的個(gè)性化排序?qū)W習(xí)方法這兩個(gè)重點(diǎn)問題.

6.4.10 其他需求場(chǎng)景

時(shí)效性排序?qū)W習(xí)、交互式排序?qū)W習(xí)、上下文排序?qū)W習(xí)、多任務(wù)排序?qū)W習(xí)、稀疏排序?qū)W習(xí)、關(guān)聯(lián)排序?qū)W習(xí)、語義感知的排序?qū)W習(xí)、地理位置感知的排序?qū)W習(xí)等都值得作進(jìn)一步的研究.

總之,設(shè)計(jì)不同需求場(chǎng)景的排序?qū)W習(xí)方法的難點(diǎn)在于如何將不同需求場(chǎng)景的實(shí)際情況與構(gòu)建的損失函數(shù)或優(yōu)化目標(biāo)有機(jī)融合,從而指導(dǎo)排序?qū)W習(xí)方法學(xué)得一個(gè)能滿足需求場(chǎng)景的更優(yōu)的排序模型.

6.5 大規(guī)模排序?qū)W習(xí)數(shù)據(jù)集的構(gòu)建

從表2中總結(jié)的排序?qū)W習(xí)數(shù)據(jù)集可看出,現(xiàn)有排序?qū)W習(xí)數(shù)據(jù)集的查詢和文檔總數(shù)并不多,總體規(guī)模比較小,最大的數(shù)據(jù)集也難以滿足網(wǎng)絡(luò)大數(shù)據(jù)的要求,難以全面可靠地反映出排序?qū)W習(xí)方法的真實(shí)性能.為了更準(zhǔn)確可靠地評(píng)價(jià)排序?qū)W習(xí)方法的整體性能和提高排序?qū)W習(xí)方法在實(shí)際應(yīng)用場(chǎng)景中的性能,應(yīng)在大規(guī)模的排序?qū)W習(xí)數(shù)據(jù)集上進(jìn)行訓(xùn)練和測(cè)試.更大的數(shù)據(jù)量、更豐富的數(shù)據(jù)多樣性,可以保障算法獲得足夠多的訓(xùn)練,讓它們變得更加智能.為此,需盡可能開采互聯(lián)網(wǎng)上廣泛的信息資源,使用更多數(shù)量和種類的查詢,更多數(shù)量和種類的網(wǎng)頁(yè)信息,提取更豐富的排序特征(如多樣性、時(shí)效性、可信性特征,語義特征,基于點(diǎn)擊、瀏覽、Session等用戶行為特征,社交關(guān)系特征等)以及未標(biāo)簽的數(shù)據(jù)去構(gòu)建大規(guī)模排序?qū)W習(xí)數(shù)據(jù)集.基于大規(guī)模排序?qū)W習(xí)數(shù)據(jù)集訓(xùn)練準(zhǔn)確可靠的排序模型,為測(cè)試未知數(shù)據(jù)的排序提供保障.目前,如此大規(guī)模排序?qū)W習(xí)數(shù)據(jù)集仍還非常稀缺,其難點(diǎn)在于如何從大規(guī)模查詢–文檔對(duì)中提取豐富多樣的排序特征和設(shè)計(jì)新的排序特征以更好地描述數(shù)據(jù)集,以及如何最小化噪音數(shù)據(jù).解決好這些難點(diǎn)問題,有利于構(gòu)建高質(zhì)量的排序?qū)W習(xí)數(shù)據(jù)集,從而可更有效地構(gòu)建高效的排序模型.因此,構(gòu)建大規(guī)模排序?qū)W習(xí)數(shù)據(jù)集仍是一個(gè)開放問題.

6.6 排序?qū)W習(xí)評(píng)價(jià)指標(biāo)

排序?qū)W習(xí)性能的評(píng)價(jià)是一個(gè)非常重要的問題,它是衡量各種排序?qū)W習(xí)方法優(yōu)劣的量化指標(biāo).在信息檢索領(lǐng)域,傳統(tǒng)評(píng)價(jià)指標(biāo)主要有精度(P)、平均精度(Average precision,AP)、平均精度均值(MAP)、召回率(R)、調(diào)和平均值F指標(biāo)(F-measure)、排序倒數(shù)(Reciprocal rank,RR)、平均排序倒數(shù)(Mean reciprocal rank,MRR)、期望排序倒數(shù)(ERR)、排序偏好精度(Rank biased precision,RBP)、累積增益(Cumulated gain,CG)、折扣累積增益(Discounted cumulated gain,DCG)、理想折扣累積增益(Ideal discounted cumulated gain,IDCG)和歸一化折扣累積增益(NDCG)以及一些意圖感知(Intent aware,IA)的多樣性評(píng)價(jià)指標(biāo),如Precision-IA、MAP-IA、α-NDCG、ERR-IA等.這些信息檢索的評(píng)價(jià)指標(biāo)都可用于評(píng)價(jià)排序?qū)W習(xí)方法的性能.

隨著排序?qū)W習(xí)場(chǎng)景需求的增多,需更多新的評(píng)價(jià)指標(biāo)來評(píng)估排序?qū)W習(xí)方法的優(yōu)劣,如可信性排序?qū)W習(xí)場(chǎng)景需求中就需要評(píng)價(jià)排序模型的可信性指標(biāo),而在馬太效應(yīng)需求的排序場(chǎng)景中需要能評(píng)價(jià)排序模型的馬太效應(yīng)的指標(biāo)等.為此,我們需針對(duì)不同需求場(chǎng)景來設(shè)計(jì)一些新的評(píng)價(jià)指標(biāo)以衡量排序模型的優(yōu)劣.如何將排序?qū)W習(xí)的需求場(chǎng)景特性融入評(píng)價(jià)標(biāo)準(zhǔn)中以設(shè)計(jì)出能合理有效度量排序模型性能的新評(píng)價(jià)指標(biāo),是一個(gè)關(guān)鍵難點(diǎn).

總之,對(duì)排序?qū)W習(xí)的研究,既要注重對(duì)排序?qū)W習(xí)的理論研究,也要注重對(duì)排序?qū)W習(xí)方法和排序?qū)W習(xí)數(shù)據(jù)集的研究,還要檢驗(yàn)和拓寬排序?qū)W習(xí)方法在實(shí)際排序場(chǎng)景中的應(yīng)用.應(yīng)加強(qiáng)應(yīng)用于排序?qū)W習(xí)中統(tǒng)計(jì)學(xué)習(xí)理論的推導(dǎo)和證明,各種排序?qū)W習(xí)方法之間的對(duì)比和集成,各種排序?qū)W習(xí)數(shù)據(jù)集中查詢量、文檔量和特征維數(shù)等之間的對(duì)比和分析,改進(jìn)和完善已有的各種排序?qū)W習(xí)方法和盡可能開發(fā)新的具有更強(qiáng)表征力的排序特征,繼續(xù)探索和開發(fā)更高級(jí)的新排序?qū)W習(xí)方法,使排序?qū)W習(xí)方法不斷得到豐富和發(fā)展,并在實(shí)際應(yīng)用中得到檢驗(yàn).

7 結(jié)束語

排序?qū)W習(xí)是信息檢索、機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘等領(lǐng)域中的一個(gè)重要問題,它在當(dāng)代搜索引擎和推薦系統(tǒng)等實(shí)際應(yīng)用中占有舉足輕重的地位.本文對(duì)排序?qū)W習(xí)所涉及的較多方面的研究現(xiàn)狀和進(jìn)展進(jìn)行了歸納和分析,并詳細(xì)探討了排序?qū)W習(xí)的未來發(fā)展趨勢(shì),希望能起到拋磚引玉的作用,能對(duì)學(xué)術(shù)界和工業(yè)界的相關(guān)研究人員提供有益幫助.期待學(xué)術(shù)界和工業(yè)界的研究者們應(yīng)用更富有創(chuàng)造性的機(jī)器學(xué)習(xí)算法,更神奇的排序特征,以及更加強(qiáng)大的計(jì)算力,開發(fā)高效且接地氣的排序?qū)W習(xí)方法,開創(chuàng)排序?qū)W習(xí)的一片新天地.