張瀟霄

摘要：排序?qū)W習(xí)是信息檢索、機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘等領(lǐng)域的重要研究課題，其核心任務(wù)是建立排序損失函數(shù)并進(jìn)行優(yōu)化而獲得排序模型。近年來，排序支持向量機(jī)RSVM（ranking support vector machine）以其理論性和有效性，被廣泛應(yīng)用到如文本檢索、網(wǎng)頁搜索、自然語言處理等領(lǐng)域。然而，基于排序偏序?qū)?gòu)建損失函數(shù)的排序支持向量機(jī)算法具有以下不足：1）在不同的查詢偏序?qū)?shù)目不同時，模型訓(xùn)練過程將偏向偏序?qū)Χ嗟牟樵儯?）其損失函數(shù)的優(yōu)化過程并未考慮到排序性能評價指標(biāo)。上述缺點導(dǎo)致排序支持向量機(jī)在實際應(yīng)用中性能受到局限。因此，本文提出基于查詢關(guān)聯(lián)模型的排序支持向量機(jī)模型，在查詢的偏序?qū)?shù)目均一化的基礎(chǔ)上，加入反映排序性能評價指標(biāo)的查詢關(guān)聯(lián)模型對排序模型進(jìn)行正則化，并推導(dǎo)出高效的策略獲取排序模型。實驗結(jié)果表明，本文提出的方法在多個數(shù)據(jù)集上排序性能較好，優(yōu)于傳統(tǒng)排序支持向量機(jī)、均一化偏序?qū)?shù)目的排序支持向量機(jī)等算法。

關(guān)鍵詞：信息檢索；排序?qū)W習(xí)；查詢關(guān)聯(lián)模型；排序支持向量機(jī)

排序在信息檢索和數(shù)據(jù)挖掘等領(lǐng)域中諸多應(yīng)用中均占據(jù)重要地位[1]。近年來，使用機(jī)器學(xué)習(xí)技術(shù)來進(jìn)行排序已發(fā)展為新的研究分支“排序?qū)W習(xí)”，是目前信息檢索、數(shù)據(jù)挖掘、機(jī)器學(xué)習(xí)和生物計算等領(lǐng)域研究的熱點問題。不失一般性，本文以信息檢索為例進(jìn)行排序?qū)W習(xí)的研究。

在信息檢索中，排序?qū)W習(xí)的主要過程為：“查詢-文檔”對集合被標(biāo)注后，分為訓(xùn)練集、驗證集、測試集；排序模型由訓(xùn)練集訓(xùn)練生成，通過驗證集進(jìn)行參數(shù)調(diào)節(jié)，最終由測試集進(jìn)行測試并采用MAP[1]和NDCG[2]等指標(biāo)進(jìn)行評估。排序?qū)W習(xí)將傳統(tǒng)排序問題轉(zhuǎn)化為從排序特征到標(biāo)注的學(xué)習(xí)問題，通過對不同任務(wù)或應(yīng)用進(jìn)行具體分析，建立不同的排序數(shù)學(xué)模型和損失函數(shù)并進(jìn)行優(yōu)化，可以獲得適用于不同任務(wù)或應(yīng)用的排序模型。

現(xiàn)有的眾多排序算法如Prank[3]、Rank SVM等，排序支持向量機(jī)（RSVM）是主流的方法之一，其排序性能好而且理論性強(qiáng)。RSVM也具有不足之處：1）當(dāng)不同的查詢偏序?qū)?shù)目不同時，模型訓(xùn)練過程將偏向偏序?qū)Χ嗟牟樵儯?）其損失函數(shù)的優(yōu)化過程并未考慮到排序性能評價指標(biāo)。上述缺點導(dǎo)致RSVM在實際應(yīng)用中性能受到局限。

本文在IRSVM的工作基礎(chǔ)上，提出基于查詢關(guān)聯(lián)模型的排序支持向量機(jī)來彌補(bǔ)第二個不足之處。具體地，在查詢偏序?qū)?shù)目均一化的基礎(chǔ)上，加入反映排序性能評價指標(biāo)的查詢關(guān)聯(lián)模型對排序模型進(jìn)行正則化。實驗結(jié)果表明，本文提出的方法在多個數(shù)據(jù)集合上排序性能較好，優(yōu)于傳統(tǒng)排序支持向量機(jī)（RSVM）、均一化偏序?qū)?shù)目的排序支持向量機(jī)（IRSVM）等算法。

1 排序支持向量機(jī)模型及分析

1.1 排序支持向量機(jī)模型

令 為“查詢-文檔”對的特征向量空間， 代表特征維數(shù)，

代表特征向量空間對應(yīng)的標(biāo)注值， 代表標(biāo)注等級，用

表示一個“查詢-文檔”對的特征和標(biāo)注。

給定訓(xùn)練集合 ，每一個查詢 均對應(yīng)自身的文檔集合，可表示為 ，整個訓(xùn)練集合可表示為 。

排序?qū)W習(xí)模型通過訓(xùn)練集上學(xué)習(xí)得到排序函數(shù) ，滿足當(dāng)標(biāo)注

時， ，其中 表示偏序關(guān)系。整個訓(xùn)練過程在排序函數(shù)空間 中尋找最小化損失的函數(shù) ：

（1）

在排序支持向量機(jī)（RSVM）模型中 是特征 的線性函數(shù) ，其中 表示點積?；谝延杏?xùn)練集合S，RSVM生成新的訓(xùn)練數(shù)據(jù)集S'，對S中同一查詢下的具有不同標(biāo)簽 ， 的特征 ，構(gòu)建 ，滿足當(dāng) 時 ，否則為 。為表示簡便，將 表示為 ，其中 代表所有生成偏序?qū)€數(shù)。RSVM的模型如下[4][5]：

（2）

其中 為 范數(shù)的模型復(fù)雜度懲罰項， 為松弛變量， 為用于平衡模型復(fù)雜度和偏序?qū)p失的參數(shù)，訓(xùn)練優(yōu)化后會得到排序模型w*，最終用于測試時 。

1.2 模型分析討論

對公式（2）的分析得出，RSVM存在以下問題：

1）當(dāng)不同的查詢其偏序?qū)?shù)目不同時，模型訓(xùn)練過程將偏向偏序?qū)Χ嗟牟樵儭?/p>

針對上述問題，Cao[6]等人提出IRSVM算法，對不同查詢下的文檔偏序?qū)€數(shù)進(jìn)行均一化，從而使得所有查詢在優(yōu)化時被同等對待，其模型描述如下[4]：

（3）

其中 表示樣本 所在查詢的偏序?qū)€數(shù)。

2）RSVM損失函數(shù)的優(yōu)化過程并未考慮到排序性能評價指標(biāo)。由公式（2）的形式化描述可知，在損失函數(shù)中并未考慮到通用的評價指標(biāo)，如MAP[1]，NDCG[2]等因素，模型的損失和懲罰都建立在偏序?qū)Φ幕A(chǔ)上。另一方面，現(xiàn)有工作中并無在RSVM上加入性能評價指標(biāo)優(yōu)化項。本文基于實驗，提出利用查詢關(guān)聯(lián)模型替代排序評價指標(biāo)，選擇出反映排序評價指標(biāo)的關(guān)聯(lián)模型并直接融入RSVM 的優(yōu)化目標(biāo)，且推導(dǎo)出高效的優(yōu)化策略得出最終模型。

2 查詢關(guān)聯(lián)模型評估及改進(jìn)排序支持向量機(jī)模型

2.1 查詢關(guān)聯(lián)模型評估策略

對于訓(xùn)練集中每一個查詢 ，利用RSVM等排序?qū)W習(xí)算法可學(xué)習(xí)得到模型 ，我們稱之為查詢關(guān)聯(lián)模型。在訓(xùn)練集和測試集獨立同分布的前提下，訓(xùn)練數(shù)據(jù)集上獲得較好排序性能查詢關(guān)聯(lián)模型 ，在測試數(shù)據(jù)集上的性能也較好，我們通過實驗發(fā)現(xiàn)，該結(jié)論在多個真實數(shù)據(jù)集上成立。

另一方面，在實驗中我們還發(fā)現(xiàn)，排序關(guān)聯(lián)模型之間的余弦相似性與排序性能之間具有相關(guān)性。

本文指出，在訓(xùn)練集上，每一個查詢關(guān)聯(lián)模型的排序性能以及與其它查詢關(guān)聯(lián)模型的余弦相似度可以用于衡量排序模型在測試集上的性能，進(jìn)而可以利用查詢關(guān)聯(lián)模型反映性能評價指標(biāo)，且上述兩種方法均可以用于對查詢關(guān)聯(lián)模型進(jìn)行評估：1）根據(jù)查詢關(guān)聯(lián)模型在訓(xùn)練集上的排序性能評價進(jìn)行評估；2）根據(jù)查詢關(guān)聯(lián)模型與訓(xùn)練集上其它查詢關(guān)聯(lián)模型的余弦相似度進(jìn)行評估。

2.2 基于查詢關(guān)聯(lián)模型正則化的排序支持向量機(jī)

利用上述評估策略，可以對訓(xùn)練集合上的所有查詢的關(guān)聯(lián)模型進(jìn)行評分，獲取得分最高的前 個查詢關(guān)聯(lián)模型，利用其線性加權(quán)和，對IRSVM進(jìn)行改進(jìn)，反映出排序性能評價指標(biāo)的影響。具體地，采用前 個查詢關(guān)聯(lián)模型的線性加權(quán)和，對排序模型進(jìn)行正則化：

（4）

公式（4）中，在 范數(shù)的模型復(fù)雜度懲罰項基礎(chǔ)上加入了前 個查詢關(guān)聯(lián)模型進(jìn)行正則化，保證最終訓(xùn)練得到的模型與前 個查詢關(guān)聯(lián)模型相近，從而調(diào)節(jié)偏序?qū)p失與反映性能評價指標(biāo)的查詢關(guān)聯(lián)模型。其中 可以進(jìn)行調(diào)節(jié)。對于公式（4）的求解，結(jié)合KKT條件，可以轉(zhuǎn)化為其對偶形式，利用二次規(guī)劃進(jìn)行求解[5]：

（5）

其中， 是拉格朗日乘子， 代表數(shù)據(jù)集中所有偏序?qū)€數(shù)， ，

。由于篇幅所限，從公式（4）推導(dǎo)至公式（5）的過程不詳細(xì)展開。

在具體實驗中，由于需要驗證集進(jìn)行調(diào)參，直接采用公式（5）進(jìn)行優(yōu)化的復(fù)雜度較高，因此，我們對公式（4）進(jìn)行了簡化。具體地，將公式（3）訓(xùn)練得到的模型表示為 ，將前K個查詢關(guān)聯(lián)模型之和 表示為 ，則公式（4）的其最優(yōu)解的形式可以簡化為： ， 的范圍為[0，1]。

定理一：公式（5）等價于下式：

（6）

證明：展開公式（4）中優(yōu)化目標(biāo)的第一項

其中 ，在優(yōu)化過程中是常數(shù)，可被約去，故整體優(yōu)化目標(biāo)（5）式可轉(zhuǎn)化成：

（10）

可進(jìn)一步轉(zhuǎn)化為：

（11）

由于C為可調(diào)節(jié)參數(shù)，故第二項中分子k可被省略。

證畢。

此時，從（6）式可以得出優(yōu)化模型結(jié)果將為公式（4）中的最優(yōu)模型 與前 個查詢關(guān)聯(lián)模型的線性加權(quán)和 的組合，故可以進(jìn)一步簡化為 ，其中公式（6）中 之前的系數(shù)分子 可被 替代。此時，參數(shù) 的調(diào)節(jié)轉(zhuǎn)化為參數(shù) 的調(diào)節(jié)，從優(yōu)化原來的由訓(xùn)練集合中的樣本的二次規(guī)劃問題轉(zhuǎn)化為簡單的線性組合，大大減少了時間復(fù)雜度。從時間上，對于具有N個查詢的訓(xùn)練集，設(shè)平均每個查詢的樣本個數(shù)為 ，則訓(xùn)練N個查詢關(guān)聯(lián)模型的時間復(fù)雜度為 ，通常情況下大大小于訓(xùn)練RSVM的時間 ，因為后者為前者的N倍，故加入 的時間復(fù)雜度較小。

簡化后的 ，結(jié)合均一化后偏序?qū)p失的

和反映性能評價指標(biāo)的 ，在大多數(shù) 不能達(dá)到最優(yōu)排序性能的情況下利用 進(jìn)行正則，通過調(diào)節(jié)參數(shù) ，減少過擬合，增加模型泛化性，達(dá)到更好的排序效果。

3 實驗結(jié)果與分析

本文在公共數(shù)據(jù)平臺LETOR[7]上的4個數(shù)據(jù)集進(jìn)行實驗和分析，驗證本文提出方法的有效性。

3.1 數(shù)據(jù)集介紹

本文實驗采用的數(shù)據(jù)集分別為OHSUMED，TREC Topic Distillation 2004（TD2004），Named page finding 2004（NP2004），Homepage Finding 2004（HP2004）。其中，OHSUMED具有106個查詢與16，140個“查詢-文檔”標(biāo)注對，其中標(biāo)注分為3個等級：相關(guān)，半相關(guān)，不相關(guān)。TD2004，NP2004和HP2004均具有75個查詢，其中“查詢-文檔”對的標(biāo)注分為2個等級：相關(guān)與不相關(guān)。每個數(shù)據(jù)集上的排序特征不盡相同，以詞頻（TF），逆文獻(xiàn)詞頻（IDF），Pagerank等排序因子為特征，具體可參見文獻(xiàn)[7]。每個數(shù)據(jù)集均采取5折交叉驗證的方式進(jìn)行實驗，并取5折平均結(jié)果作為最終實驗結(jié)果進(jìn)行對比。

3.2 評價指標(biāo)

在本文的實驗中，主要使用MAP和NDCG來評價排序的性能。

MAP（Mean Average Precision）[1]是在查準(zhǔn)率、召回率的基礎(chǔ)上派生出的評價指標(biāo)，用來衡量算法對多個查詢的平均排序結(jié)果。MAP的計算公式為：

（12）

其中j表示排序的位置，M是檢索到的文檔總數(shù)，Precision（j）是前j個檢索到的文檔的查準(zhǔn)率，pos（j）是一個0-1函數(shù)，如果排在第j個文檔是相關(guān)的，其值為1，否則為0。

NDCG[2]（Normalized Discounted Cumulative Gain）在傳統(tǒng)評價標(biāo)準(zhǔn)的基礎(chǔ)上，考慮了相關(guān)性的等級和排序位置的影響，強(qiáng)調(diào)評價排序結(jié)果中頂部序列的準(zhǔn)確性。對于給定一個查詢q，第k位的NDCG值NDCG@k的計算公式為：

（13）

其中r（j）是第j個文檔的級別，Nk是歸一化參數(shù)，使得在第k位上的最優(yōu)排序的NDCG@r的值始終為1。

3.3 實驗結(jié)果

本文采用的基準(zhǔn)方法有RSVM，IRSVM，RBoost，ListNet。為簡便起見，本文提出的算法表示為Top-K。其中C參數(shù)在一個數(shù)據(jù)集合上相近，在5個交叉集上略有不同，在OHSUMED上約為10，TD2004上約為1，NP2004上約為0.5，HP2004上約為10。k的設(shè)定在OHSUMED和HP2004上為10，TD2004和NP2004上為40。對于查詢關(guān)聯(lián)模型的評估策略，OHSUMED采用NDCG@5，TD2004和HP2004采用MAP，而NP2004采用NDCG@10，評估策略均通過驗證集進(jìn)行調(diào)整，從驗證集中挑選達(dá)到MAP指標(biāo)最高的策略進(jìn)行最終測試。a的選取，在OHSUMED為0.2，在TD2004上為0.1，在NP2004上為0.8，在HP2004上為0.05。在上述4個數(shù)據(jù)集上的實驗參數(shù)調(diào)節(jié)表明，使用評價指標(biāo)的評估策略在驗證集與測試集MAP的性能表現(xiàn)均優(yōu)于余弦相似度的評估策略。

表1列舉出4個數(shù)據(jù)集上，不同算法的MAP的對比值，每個數(shù)據(jù)集上最高性能被加粗顯示。從表1可知，Top-K算法的MAP在NP2004和HP2004上較好，在TD2004數(shù)據(jù)集上高于RSVM，IRSVM，且與ListNet具有可比性。IRSVM在所有數(shù)據(jù)集上MAP均高于RSVM，且從后面的實驗結(jié)果中可知，IRSVM在大部分?jǐn)?shù)據(jù)集上的NDCG性能也高于RSVM。

圖1分別給出在四個數(shù)據(jù)集上所有算法的NDCG對比情況，橫坐標(biāo)中1，3，5，10分別代表NDCG@1，3，5和10，縱坐標(biāo)代表其值。由圖1可知，IRSVM和Top-K在NDCG@1上優(yōu)勢較為明顯，而ListNet與Top-k算法在所有數(shù)據(jù)集上性能均較好，無明顯優(yōu)劣之分。

3.4 實驗結(jié)果分析

為進(jìn)一步探討Top-K中參數(shù)k和a的設(shè)定，以及參數(shù)變化導(dǎo)致實驗結(jié)果和性能變化的情況，本文進(jìn)行了進(jìn)一步實驗分析和討論。不失一般性，以部分?jǐn)?shù)據(jù)集為例，且采用基于評價指標(biāo)的查詢關(guān)聯(lián)模型評估策略。

對于K的影響，以TD2004為例，采用MAP作為關(guān)聯(lián)模型選擇策略，設(shè)定a=0.1，獲取k為0，5，10，15，20，25，30，35，40，45時驗證集和測試集的排序性能MAP進(jìn)行對比。k=0對應(yīng)IRSVM，k=45時選擇全部查詢關(guān)聯(lián)模型。圖2給出對比曲線，藍(lán)色表示測試集，紅色表示驗證集，其中橫坐標(biāo)表示 的取值，縱坐標(biāo)表示性能評價指標(biāo)MAP的值。由圖2可知，k=40是排序性能在驗證集上趨于最佳且測試集上性能也較好。同時可看出，固定a取值時，當(dāng)k的取值發(fā)生較小變化（±5）時，驗證集和測試集的排序性能也會有一定的變化，且變化趨勢基本一致。

下一步，進(jìn)行實驗展示a變化導(dǎo)致的排序性能變化，令a從[0，1] 范圍內(nèi)以間隔為0.1變化。圖3給出NP2004（k=40，a=0.8時驗證集MAP最優(yōu)）的驗證和測試集合上，MAP性能評價指標(biāo)的對比曲線，藍(lán)色表示測試集，紅色表示驗證集，其中橫坐標(biāo)表示a的取值，縱坐標(biāo)表示MAP性能。由圖可知，a=0代表IRSVM，Top-K算法當(dāng)a在對應(yīng)取值時在驗證集和測試集上時線性組合w*=（1-a）·WIRSVM+a·WOPT的性能較好，且實驗結(jié)果對參數(shù)a（±0.1）變化不太敏感，且驗證集與測試集隨a改變，其變化趨勢不太一致。

實驗結(jié)果分析過程中，我們還發(fā)現(xiàn)，采取哪種排序性能指標(biāo)來選擇查詢關(guān)聯(lián)模型，可以優(yōu)化何種指標(biāo)并不完全明確，基于MAP選擇查詢關(guān)聯(lián)模型，其NDCG性能可能較好，而基于NDCG選擇查詢關(guān)聯(lián)模型，可能導(dǎo)致最終測試時MAP性能較好，與文獻(xiàn)[8]中直接優(yōu)化近似評價指標(biāo)的實驗結(jié)果與結(jié)論基本一致。該問題的解決尚需進(jìn)行進(jìn)一步的深入研究。

4 總結(jié)與展望

本文基于實驗發(fā)現(xiàn)查詢關(guān)聯(lián)模型可以反映查詢排序性能并有效地幫助提升排序性能，進(jìn)而提出了基于查詢關(guān)聯(lián)模型的排序支持向量機(jī)算法，針對傳統(tǒng)排序支持向量機(jī)的不足之處進(jìn)行改進(jìn)，加入反映排序性能評價指標(biāo)的查詢關(guān)聯(lián)模型對排序模型進(jìn)行正則化，并推導(dǎo)出高效的策略獲取排序模型。通過前期工作和本文的改進(jìn)，對排序支持向量機(jī)在偏序?qū)€數(shù)上的偏差進(jìn)行校正，并對于排序支持向量機(jī)對排序性能指標(biāo)欠缺考慮之處進(jìn)行補(bǔ)足。實驗結(jié)果表明，本文提出的算法在文本檢索，網(wǎng)頁搜索等多個數(shù)據(jù)集上均取得了良好的效果。本文的理論結(jié)果除排序問題外，還可應(yīng)用于分類等問題。

參考文獻(xiàn)：

1.Baeza-Yates，R.，Ribeiro-Neto B. Modern Information Retrieval [M]. Boston， MA： Addison-Wesley Longman Publishing Co： 1999

2.Jarvelin，K.and Kekalainen，J.Cumulated Gain-based Evaluation

of IR Techniques.[J]. ACM Transactions on Information Systems， 2002， 20（4）：422-446

3.Crammer，K.，and Singer， Y. PRanking with ranking[C]// Proc of the 14th Conference on Neural Information Processing Systems. British Columbia， Canada： ACM 2001： 641-647

4.Herbrich， R.，Graepel，T.，and Obermayer，K.Large margin rank boundaries for ordinal regression[M].Smola， A.， Bartlett， P.，Scholkopf，B.，and chuurmans， D.，eds.，Advances in Large Margin Classifiers. MIT Press， 2000： 115-132.

5.Joachims， T. Optimizing Search Engines Using Click-through Data[C]// Proc of the 8th ACM SIGKDD Conference. New York， USA： ACM 2002： 133-142

6.Cao， Y.， Xu， J.， Liu， T.-Y.， et al. Adapting ranking SVM to document retrieval[C]// Proc of the 29th ACM SIGIR Conference. Seattle， USA： ACM， 2006： 186-193

7.Liu， T.， Xu， J.Qin， T.，et al. LETOR： Benchmark Dataset for Research on Learning to Rank for Information Retrieval.[C]// Proc of the 30th ACM SIGIR Conference. Netherland： ACM， 2007

8.Qin， T.， Liu， T.-Y.， Li， H. A general approximation framework for direct optimization of information retrieval measures.[R] MSR-TR-2008-164， Microsoft Research， 2008