信息檢索中的排序問題概述

勝紫菡

摘要：近年來，信息檢索中的排序學習受到越來越廣泛的關注.本文將在機器學習的框架下介紹排序學習，基于機器學習方法的排序算法稱為“學習排序法”.學習排序法的兩個主要特點是：一是基于特征的特點：訓練文本是用特征向量來表示的;二是判別訓練：“學習排序法”有自己的輸入空間，輸出空間，假設空間和損失函數.本文將針對不同的學習算法詳細闡述這四個主要成分。

關鍵詞：機器學習;排序問題;信息檢索

排序學習是典型的有監督學習，訓練集是由查詢，與查詢相關的文檔和相應的相關性判斷標準組成.排序模型可以通過一個排序算法來預測訓練集的真實標簽.當給定一個新的查詢時，就可以根據排序模型對文檔進行排序.不同的排序算法定義不同的輸入空間和輸出空間，并且使用不同的假設空間和不同的損失函數.因此在機器學習框架下，我們將“排序學習”分為以下兩類：

基于單個文檔的排序方法（Pointwise approach）

基于配對文檔的排序方法（Pairwise approach）

1.基于單個文檔的排序方法

基于單個文檔的排序方法是排序學習最早提出的算法，其基本思想是將訓練集中的每個查詢/文檔對作為訓練數據，再應用合適的算法來學習一個排序模型.因為每個查詢/文檔對都被看做一個單獨訓練樣本，所以稱這種方法為Pointwise方法.Pointwise方法的四個主要組成成分：

（1）輸入空間：包含單個查詢/文檔對的特征向量

（2）輸出空間：包含單個查詢/文檔對的相關度得分

（3）假設空間：包含映射函數，它將每個查詢/文檔對的特征向量作為輸入，通過一個函數來預測排序得分.我們稱這個映射函數為得分函數，基于得分函數可以對文檔進行排序。

（4）損失函數：衡量查詢/文檔對的預測得分與實值標簽之間的差異.在不同的Pointwise算法中，排序分別被看做是回歸、分類問題，相應的回歸、分類損失就是排序損失.根據機器學習的不同方法，Pointwise方法可以被分為三種類型：

1.1基于回歸的排序算法

基于回歸的排序算法，它的輸出空間是由實值相關度得分組成的.將排序問題轉化為回歸問題來考慮，他們把查詢/文檔對的相關度得分看作是一個連續變量，使用最小二乘損失來尋找最優排序函數.在此基礎上，他們還提出了重要性加權回歸模型來學習排序問題，并對最小二乘損失和排序誤差界進行了理論研究。

1.2基于分類的排序算法

對基于分類的算法排序而言，它的輸出空間是由類別標簽組成的.提出了基于二分類的排序問題，他將訓練集的類標簽分為“相關”和“不相關”兩類，通過SVM方法進行二分類學習來完成排序任務.在中提出了應用多類別分類問題來學習排序問題.他們提出了一個概率模型，以分類損失作為排序損失，并應用加權組合得分函數給出每個查詢/文檔對的得分，最終根據得分函數完成排序任務。

1.3基于順序回歸的排序算法

當把排序問題轉化為順序回歸時，我們考慮實值標簽的順序來學習排序模型.提出了基于感知器的排序算法，也稱為PRanking.其主要目的是通過迭代過程尋找一個參數向量和一些單調遞增的臨界值，根據每個查詢/文檔對的得分來判斷其屬于哪兩個臨界值之間，據此對查詢/文檔對進行排序。

2.基于配對文檔的排序方法

基于配對文檔的排序算法簡稱為Pairwise方法.Pairwise方法不同于Pointwise方法考慮每個查詢/文檔對的相關度，而是針對每個查詢考慮兩個文檔間的偏序關系，其目標是使得最終的排序列表中逆序的文檔對越少越好.基于Pairwise法的排序學習也稱為配對偏序關系學習.Pairwise方法的四個主要組成成分：

（1）輸入空間：包含每個查詢所對應的配對文檔的特征向量

（2）輸出空間：包含每個查詢所對應的配對文檔的偏序關系

（3）假設空間：一個二變量函數，它輸入一對文檔，輸出他們之間的偏序關系

（4）損失函數：衡量輸出的偏序關系與實際偏序關系之間的不一致程度.在許多Pairwise排序算法中，排序問題被看做是Pairwise分類問題，相應的分類損失就是排序損失.目前信息檢索中的排序算法有很大一部分都是基于Pairwise方法。

2.1Ranking SVM算法

Ranking SVM是由首次提出的.他是以SVM為工具，以每個查詢的配對文檔偏序關系為訓練數據，基于順序回歸的方法將排序問題轉化為分類問題來求解.在此基礎上，進一步使用了Ranking SVM算法，他從用戶的點擊量數據中獲取具有偏序關系的配對文檔作為訓練數據，同樣將排序問題轉換成一個二分類問題，并使用SVM來求解。

2.2RankBoost算法

RankBoost算法是在中提出的，其基本思想仍然是將排序問題轉化為配對文檔的二分類問題，但不同于Ranking SVM解決一個順序回歸問題，RankBoost直接求解偏序學習問題.他將AdaBoost應用到分類問題中，與所有的Boosting算法一樣，RankBoost通過結合多個弱排序結果構成唯一的排序結果.這是通過多次迭代實現的，每一次迭代過程都通過更新文檔對的分布得到一個弱排序，算法最終的排序結果是這些弱排序的加權線性組合。

3.小結

Pointwise 方法是排序學習最早提出的算法.他輸入單個查詢/文檔對，根據得分函數輸出其相關度得分，對得分按降序排列，據此來學習排序模型.Pointwise 方法分為三類：基于回歸的算法，基于分類的算法和基于順序回歸的算法。

Pairwise方法將排序問題轉化為二分類問題來處理，他輸入成對的文檔，根據一個排序函數輸出成對文檔的偏序關系，據此來學習排序模型.目前信息檢索中很多排序算法都基于Pairwise算法，其中最具代表性的是：基于SVM 的Ranking SVM算法，基于Boosting的RankBoost算法和基于神經網絡的RankNet算法。

參考文獻：

[1]Cossock， D.， Zhang， T.： Subset ranking using regression. In： Proceedings of the 19th Annual Conference on Learning Theory （COLT 2006），2006：605-619.

[2]Nallapati， R.：Discriminative models for information retrieval.In： Proceedings of the 27th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval （SIGIR 2004）， 2004： 64-71.

[3]Li， P.，Burges，C.，Wu， Q.：McRank： learning to rank using multiple classification and gradient boosting. In： Advances in Neural Information Processing Systems 20 （NIPS 2007）， 2008： 845-852.

[4]Crammer， K.， Singer， Y.： Pranking with ranking. In： Advances in Neural Information Processing Systems 14 （NIPS 2001）， 2002：641-647.

[5]Herbrich， R.， Obermayer， K.， Graepel， T.： Large margin rank boundaries for ordinal regression.In： Advances in Large Margin Classifiers， 2000： 115-132.

[6]Joachims， T.： Optimizing search engines using click through data.In： Proceedings of the 8th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining （KDD2002）， 2002： 133-142.