基于查詢關聯模型的排序支持向量機方法

張瀟霄

摘要：排序學習是信息檢索、機器學習和數據挖掘等領域的重要研究課題，其核心任務是建立排序損失函數并進行優化而獲得排序模型。近年來，排序支持向量機RSVM（ranking support vector machine）以其理論性和有效性，被廣泛應用到如文本檢索、網頁搜索、自然語言處理等領域。然而，基于排序偏序對構建損失函數的排序支持向量機算法具有以下不足：1）在不同的查詢偏序對數目不同時，模型訓練過程將偏向偏序對多的查詢；2）其損失函數的優化過程并未考慮到排序性能評價指標。上述缺點導致排序支持向量機在實際應用中性能受到局限。因此，本文提出基于查詢關聯模型的排序支持向量機模型，在查詢的偏序對數目均一化的基礎上，加入反映排序性能評價指標的查詢關聯模型對排序模型進行正則化，并推導出高效的策略獲取排序模型。實驗結果表明，本文提出的方法在多個數據集上排序性能較好，優于傳統排序支持向量機、均一化偏序對數目的排序支持向量機等算法。

關鍵詞：信息檢索；排序學習；查詢關聯模型；排序支持向量機

排序在信息檢索和數據挖掘等領域中諸多應用中均占據重要地位[1]。近年來，使用機器學習技術來進行排序已發展為新的研究分支“排序學習”，是目前信息檢索、數據挖掘、機器學習和生物計算等領域研究的熱點問題。不失一般性，本文以信息檢索為例進行排序學習的研究。

在信息檢索中，排序學習的主要過程為：“查詢-文檔”對集合被標注后，分為訓練集、驗證集、測試集；排序模型由訓練集訓練生成，通過驗證集進行參數調節，最終由測試集進行測試并采用MAP[1]和NDCG[2]等指標進行評估。排序學習將傳統排序問題轉化為從排序特征到標注的學習問題，通過對不同任務或應用進行具體分析，建立不同的排序數學模型和損失函數并進行優化，可以獲得適用于不同任務或應用的排序模型。

現有的眾多排序算法如Prank[3]、Rank SVM等，排序支持向量機（RSVM）是主流的方法之一，其排序性能好而且理論性強。RSVM也具有不足之處：1）當不同的查詢偏序對數目不同時，模型訓練過程將偏向偏序對多的查詢；2）其損失函數的優化過程并未考慮到排序性能評價指標。上述缺點導致RSVM在實際應用中性能受到局限。

本文在IRSVM的工作基礎上，提出基于查詢關聯模型的排序支持向量機來彌補第二個不足之處。具體地，在查詢偏序對數目均一化的基礎上，加入反映排序性能評價指標的查詢關聯模型對排序模型進行正則化。實驗結果表明，本文提出的方法在多個數據集合上排序性能較好，優于傳統排序支持向量機（RSVM）、均一化偏序對數目的排序支持向量機（IRSVM）等算法。

1 排序支持向量機模型及分析

1.1 排序支持向量機模型

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

代表特征向量空間對應的標注值， 代表標注等級，用

表示一個“查詢-文檔”對的特征和標注。

給定訓練集合 ，每一個查詢 均對應自身的文檔集合，可表示為 ，整個訓練集合可表示為 。

排序學習模型通過訓練集上學習得到排序函數 ，滿足當標注

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

（1）

在排序支持向量機（RSVM）模型中 是特征 的線性函數 ，其中 表示點積?；谝延杏柧毤蟂，RSVM生成新的訓練數據集S'，對S中同一查詢下的具有不同標簽 ， 的特征 ，構建 ，滿足當 時 ，否則為 。為表示簡便，將 表示為 ，其中 代表所有生成偏序對個數。RSVM的模型如下[4][5]：

（2）

其中 為 范數的模型復雜度懲罰項， 為松弛變量， 為用于平衡模型復雜度和偏序對損失的參數，訓練優化后會得到排序模型w*，最終用于測試時 。

1.2 模型分析討論

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

1）當不同的查詢其偏序對數目不同時，模型訓練過程將偏向偏序對多的查詢。

針對上述問題，Cao[6]等人提出IRSVM算法，對不同查詢下的文檔偏序對個數進行均一化，從而使得所有查詢在優化時被同等對待，其模型描述如下[4]：

（3）

其中 表示樣本 所在查詢的偏序對個數。

2）RSVM損失函數的優化過程并未考慮到排序性能評價指標。由公式（2）的形式化描述可知，在損失函數中并未考慮到通用的評價指標，如MAP[1]，NDCG[2]等因素，模型的損失和懲罰都建立在偏序對的基礎上。另一方面，現有工作中并無在RSVM上加入性能評價指標優化項。本文基于實驗，提出利用查詢關聯模型替代排序評價指標，選擇出反映排序評價指標的關聯模型并直接融入RSVM 的優化目標，且推導出高效的優化策略得出最終模型。

2 查詢關聯模型評估及改進排序支持向量機模型

2.1 查詢關聯模型評估策略

對于訓練集中每一個查詢 ，利用RSVM等排序學習算法可學習得到模型 ，我們稱之為查詢關聯模型。在訓練集和測試集獨立同分布的前提下，訓練數據集上獲得較好排序性能查詢關聯模型 ，在測試數據集上的性能也較好，我們通過實驗發現，該結論在多個真實數據集上成立。

另一方面，在實驗中我們還發現，排序關聯模型之間的余弦相似性與排序性能之間具有相關性。

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

2.2 基于查詢關聯模型正則化的排序支持向量機

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

（4）

公式（4）中，在 范數的模型復雜度懲罰項基礎上加入了前 個查詢關聯模型進行正則化，保證最終訓練得到的模型與前 個查詢關聯模型相近，從而調節偏序對損失與反映性能評價指標的查詢關聯模型。其中 可以進行調節。對于公式（4）的求解，結合KKT條件，可以轉化為其對偶形式，利用二次規劃進行求解[5]：

（5）

其中， 是拉格朗日乘子， 代表數據集中所有偏序對個數， ，

。由于篇幅所限，從公式（4）推導至公式（5）的過程不詳細展開。

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

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

（6）

證明：展開公式（4）中優化目標的第一項

其中 ，在優化過程中是常數，可被約去，故整體優化目標（5）式可轉化成：

（10）

可進一步轉化為：

（11）

由于C為可調節參數，故第二項中分子k可被省略。

證畢。

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

簡化后的 ，結合均一化后偏序對損失的

和反映性能評價指標的 ，在大多數 不能達到最優排序性能的情況下利用 進行正則，通過調節參數 ，減少過擬合，增加模型泛化性，達到更好的排序效果。

3 實驗結果與分析

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

3.1 數據集介紹

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

3.2 評價指標

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

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

（12）

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

NDCG[2]（Normalized Discounted Cumulative Gain）在傳統評價標準的基礎上，考慮了相關性的等級和排序位置的影響，強調評價排序結果中頂部序列的準確性。對于給定一個查詢q，第k位的NDCG值NDCG@k的計算公式為：

（13）

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

3.3 實驗結果

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

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

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

3.4 實驗結果分析

為進一步探討Top-K中參數k和a的設定，以及參數變化導致實驗結果和性能變化的情況，本文進行了進一步實驗分析和討論。不失一般性，以部分數據集為例，且采用基于評價指標的查詢關聯模型評估策略。

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

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

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

4 總結與展望

本文基于實驗發現查詢關聯模型可以反映查詢排序性能并有效地幫助提升排序性能，進而提出了基于查詢關聯模型的排序支持向量機算法，針對傳統排序支持向量機的不足之處進行改進，加入反映排序性能評價指標的查詢關聯模型對排序模型進行正則化，并推導出高效的策略獲取排序模型。通過前期工作和本文的改進，對排序支持向量機在偏序對個數上的偏差進行校正，并對于排序支持向量機對排序性能指標欠缺考慮之處進行補足。實驗結果表明，本文提出的算法在文本檢索，網頁搜索等多個數據集上均取得了良好的效果。本文的理論結果除排序問題外，還可應用于分類等問題。

參考文獻：

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