勝紫菡

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

關(guān)鍵詞：機(jī)器學(xué)習(xí);排序問題;信息檢索

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

基于單個(gè)文檔的排序方法（Pointwise approach）

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

1.基于單個(gè)文檔的排序方法

基于單個(gè)文檔的排序方法是排序?qū)W習(xí)最早提出的算法，其基本思想是將訓(xùn)練集中的每個(gè)查詢/文檔對作為訓(xùn)練數(shù)據(jù)，再應(yīng)用合適的算法來學(xué)習(xí)一個(gè)排序模型.因?yàn)槊總€(gè)查詢/文檔對都被看做一個(gè)單獨(dú)訓(xùn)練樣本，所以稱這種方法為Pointwise方法.Pointwise方法的四個(gè)主要組成成分：

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

（2）輸出空間：包含單個(gè)查詢/文檔對的相關(guān)度得分

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

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

1.1基于回歸的排序算法

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

1.2基于分類的排序算法

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

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

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

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

基于配對文檔的排序算法簡稱為Pairwise方法.Pairwise方法不同于Pointwise方法考慮每個(gè)查詢/文檔對的相關(guān)度，而是針對每個(gè)查詢考慮兩個(gè)文檔間的偏序關(guān)系，其目標(biāo)是使得最終的排序列表中逆序的文檔對越少越好.基于Pairwise法的排序?qū)W習(xí)也稱為配對偏序關(guān)系學(xué)習(xí).Pairwise方法的四個(gè)主要組成成分：

（1）輸入空間：包含每個(gè)查詢所對應(yīng)的配對文檔的特征向量

（2）輸出空間：包含每個(gè)查詢所對應(yīng)的配對文檔的偏序關(guān)系

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

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

2.1Ranking SVM算法

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

2.2RankBoost算法

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

3.小結(jié)

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

Pairwise方法將排序問題轉(zhuǎn)化為二分類問題來處理，他輸入成對的文檔，根據(jù)一個(gè)排序函數(shù)輸出成對文檔的偏序關(guān)系，據(jù)此來學(xué)習(xí)排序模型.目前信息檢索中很多排序算法都基于Pairwise算法，其中最具代表性的是：基于SVM 的Ranking SVM算法，基于Boosting的RankBoost算法和基于神經(jīng)網(wǎng)絡(luò)的RankNet算法。

參考文獻(xiàn)：

[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.