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

勝紫菡

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

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

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

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

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

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

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

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

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

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

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

1.1基于回歸的排序算法

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

1.2基于分類的排序算法

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

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

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

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

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

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

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

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

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

2.1Ranking SVM算法

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

2.2RankBoost算法

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

3.小結

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

Pairwise方法將排序問題轉化為二分類問題來處理，他輸入成對的文檔，根據(jù)一個排序函數(shù)輸出成對文檔的偏序關系，據(jù)此來學習排序模型.目前信息檢索中很多排序算法都基于Pairwise算法，其中最具代表性的是：基于SVM 的Ranking SVM算法，基于Boosting的RankBoost算法和基于神經(jīng)網(wǎng)絡的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.