信息檢索中的排序問(wèn)題概述

勝紫菡

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

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

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

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

基于配對(duì)文檔的排序方法（Pairwise approach）

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

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

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

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

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

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

1.1基于回歸的排序算法

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

1.2基于分類(lèi)的排序算法

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

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

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

2.基于配對(duì)文檔的排序方法

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

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

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

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

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

2.1Ranking SVM算法

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

2.2RankBoost算法

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

3.小結(jié)

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

Pairwise方法將排序問(wèn)題轉(zhuǎn)化為二分類(lèi)問(wèn)題來(lái)處理，他輸入成對(duì)的文檔，根據(jù)一個(gè)排序函數(shù)輸出成對(duì)文檔的偏序關(guān)系，據(jù)此來(lái)學(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.