李偉寧，王 磊

(1.南京郵電大學(xué) 計算機(jī)學(xué)院，江蘇 南京 210003; 2.南京郵電大學(xué) 電子科學(xué)與工程學(xué)院，江蘇 南京 210003)

0 引 言

排序是信息檢索系統(tǒng)的一個重要組成部分，為了提高用戶檢索的準(zhǔn)確性，將更為相關(guān)有效的查詢頁面返回給用戶，如何提高搜索的排序質(zhì)量就顯得尤為重要。隨著搜索引擎的發(fā)展，對于某個網(wǎng)頁進(jìn)行排序需要考慮的因素越來越多，Google目前的網(wǎng)頁排序公式考慮200多種因子，如TFIDF、BM25、PageRank、HITS以及基于點擊數(shù)據(jù)的用戶行為的特征等，此時機(jī)器學(xué)習(xí)的作用即可發(fā)揮出來[1]。

特征以及特征的組合方式對于任何以機(jī)器學(xué)習(xí)算法為依托的任務(wù)來說都是至關(guān)重要的，并與機(jī)器學(xué)習(xí)算法結(jié)合形成了復(fù)雜的算法體系[2]。當(dāng)前對排序?qū)W習(xí)的特征處理的研究較少，文中的研究重點是對特征進(jìn)行有效的處理，從而在新的特征集合上構(gòu)建更加有效的排序函數(shù)。

1 相關(guān)研究

排序?qū)W習(xí)嘗試用機(jī)器學(xué)習(xí)的方法解決排序問題，已得到深入研究并廣泛應(yīng)用于不同的領(lǐng)域，如信息檢索、個性化推薦、文本挖掘、生物醫(yī)學(xué)等[3-5]。排序?qū)W習(xí)算法根據(jù)其數(shù)據(jù)形式的不同主要分為三類：Pointwise型，如基于感知器的Prank算法[6]，將問題轉(zhuǎn)換為單個文檔的分類和回歸問題；Pairwise型，如用神經(jīng)網(wǎng)絡(luò)模型結(jié)合梯度下降算法去優(yōu)化排序損失函數(shù)的RankNet算法[7]和使用支持向量機(jī)的RankingSVM算法[8-9]；Listwise型，如基于神經(jīng)網(wǎng)絡(luò)和梯度下降優(yōu)化方法，應(yīng)用概率模型來構(gòu)造損失函數(shù)的ListNet算法[10]和基于直接優(yōu)化信息檢索評價方法的LambdaMART算法[11]。研究表明[12]，Listwise方法的排序效果一般要優(yōu)于Pointwise及Pairwise方法。因此，文中采用Listwise型中經(jīng)典的ListNet算法進(jìn)行比較研究。

在排序?qū)W習(xí)領(lǐng)域，已經(jīng)提出了很多方法來提高排序的準(zhǔn)確率，例如提出一種新的排序?qū)W習(xí)算法[13]，構(gòu)建一種新的優(yōu)化函數(shù)，設(shè)計新的特征。然而，在排序技術(shù)較為成熟的基礎(chǔ)上，如果僅靠改進(jìn)排序?qū)W習(xí)算法來提高排序結(jié)果已經(jīng)變得越來越難。那么添加由原始特征生成的新特征是否會提升準(zhǔn)確率，一些學(xué)者進(jìn)行了研究。Amini等[14]假設(shè)若找到一個與已標(biāo)注文檔最為相似的未標(biāo)注的文檔，那么就認(rèn)為這個未標(biāo)注的文檔與已標(biāo)注的文檔的相關(guān)性條件也是相似的，使用這些文檔實例來擴(kuò)展訓(xùn)練數(shù)據(jù)集。Duh和Kirchhoff[15]應(yīng)用基于核的主成分分析方法對測試集合抽取新的特征集合，利用測試集合的特征來擴(kuò)展訓(xùn)練集合，獲得了好的效果。林等[16]將訓(xùn)練集與測試集進(jìn)行合并后的集合進(jìn)行奇異值分解，提取新的特征集合加入訓(xùn)練集，在RankBoost排序算法上提高了排序效果。

特征選擇是從一組特征集中挑選出一部分最有效的特征以降低特征空間維數(shù)的過程[17]。特征選擇對排序?qū)W習(xí)有兩大優(yōu)點：第一，可以提高排序?qū)W習(xí)的精確度；第二，可以提高訓(xùn)練的效率。文中綜合利用PCA方法擴(kuò)展數(shù)據(jù)集，并在擴(kuò)展后的數(shù)據(jù)集上進(jìn)行排序算法隱含的特征選擇。

2 基于排序?qū)W習(xí)的特征處理

2.1 基于PCA的數(shù)據(jù)集擴(kuò)展

查詢和文檔集的特征組成的特征向量X=(x1,x2,…,xn)，求取特征向量X的自相關(guān)矩陣Rx，根據(jù)PCA原理對Rx進(jìn)行特征分解，得到特征向量矩陣Λ和特征矩陣U，其中特征矩陣U為：

令Y=UX，Y即為X的K-L變換。其中，U的每一列向量均包含了X的相關(guān)信息，將其作為X的組合特征。選取最大特征值對應(yīng)的特征向量作為X的融合特征添加到原始數(shù)據(jù)集中，在擴(kuò)展訓(xùn)練數(shù)據(jù)集的同時達(dá)到特征融合的目的。算法思想如下：

輸入：訓(xùn)練集D，驗證集V，測試集T;

輸出：新的訓(xùn)練集D'，新的驗證集V'，新的測試集T'。

(1)對訓(xùn)練集所對應(yīng)的特征矩陣進(jìn)行主成分分析，選取前k個主元；

(2)用選取的前k個主元對原訓(xùn)練集、驗證集、測試集進(jìn)行主成分分析，分別得到它們的前k個特征向量集Dk，Vk，Tk；

(3)D∪Dk?D'，V∪Vk?V'，T∪Tk?T'，添加后的特征向量維度比原始維度大k。

文中綜合排序訓(xùn)練時間和排序效果選擇加入合適的特征向量數(shù)目。

2.2 基于排序?qū)W習(xí)的特征選擇

在基于PCA擴(kuò)展之后的數(shù)據(jù)集上進(jìn)行排序算法隱含的特征選擇，算法思想如下：

輸入：特征集合X=(x1,x2,…,xn+k)；

輸出：特征子集S=(s1,s2,…,sm)，m≤n+k。

(1)對基于PCA方法擴(kuò)展之后得到的訓(xùn)練集和驗證集使用排序?qū)W習(xí)算法得到排序函數(shù)；

(2)將上述得到的排序函數(shù)的特征系數(shù)的絕對值作為對應(yīng)特征的權(quán)重；

(3)做五組實驗，對五組實驗得到的特征權(quán)重求和取平均值，權(quán)重從大到小排序；

(4)取前m個特征構(gòu)建新的訓(xùn)練集、驗證集和測試集。

2.3 排序?qū)W習(xí)算法

Listwise型排序?qū)W習(xí)方法是將整個文檔序列看作一個樣本[18]。其中，ListNet方法是將排序問題建模為概率模型，然后選取交叉熵衡量由模型訓(xùn)練出的文檔排序和真正的文檔排序之間的差異，通過最小化這個差異值來完成排序。ListNet定義了一個置換概率：

(1)

其中，π為作用于n(qi)個文檔的置換；Φ()為一個遞增、恒正的函數(shù)；S為一個計算文檔與查詢相關(guān)度評分的函數(shù)；Sπ(j)為在置換π中第j個位置的文檔的評分值。

以交叉熵的形式定義損失，優(yōu)化目標(biāo)的公式如下：

(2)

3 實 驗

3.1 實驗數(shù)據(jù)

實驗采用的是微軟亞洲研究院(MSRA)提供的LETOR4.0[19]數(shù)據(jù)集中的MQ2007和MQ2008兩個數(shù)據(jù)集。LETOR4.0采用了Gov2的網(wǎng)頁集作為原始數(shù)據(jù)，使用從百萬查詢跟蹤TERC2007和TERC2008的兩個查詢集，每個查詢有許多相關(guān)聯(lián)的文檔。其中，每個查詢-文檔對的相關(guān)度標(biāo)注為三個等級(2，1，0)，分別對應(yīng)非常相關(guān)、部分相關(guān)和不相關(guān)。對數(shù)據(jù)集抽取了基于鏈接、內(nèi)容等的46個特征。

在實驗過程中，采用了交叉驗證的方法。數(shù)據(jù)被平分成五份，用S1、S2、S3、S4、S5表示。做五次訓(xùn)練，再取五次結(jié)果的平均數(shù)，這樣做可以避免數(shù)據(jù)過擬合的情況，保證結(jié)果的可信度。數(shù)據(jù)集劃分見表1。

表1 五折交叉驗證數(shù)據(jù)集劃分

3.2 評測函數(shù)

為了衡量排序函數(shù)性能的優(yōu)劣，應(yīng)用兩種常用的排序性能評測函數(shù)：MAP和NDCG@n。

MAP(mean average precision)的衡量標(biāo)準(zhǔn)單一，q與d的關(guān)系非0即1，核心是利用q對應(yīng)的相關(guān)的d出現(xiàn)的位置來進(jìn)行排序算法準(zhǔn)確性的評估。系統(tǒng)檢索出來的相關(guān)文檔越靠前，MAP值就可能越高。對于一個查詢qi，其平均查準(zhǔn)率的計算公式為：

(3)

其中，j表示排序序列的位置；M表示返回的文檔總數(shù)；Rj表示第j個查詢的相關(guān)文檔數(shù)目；precision(j)表示第j個檢索到的文檔的查準(zhǔn)率；pos(j)定義為：

(4)

用NQ表示查詢數(shù)量，平均查準(zhǔn)率的均值MAP為：

(5)

NDCG(normalized discount cumulative gain)是用來評估排序結(jié)果中頂部序列的準(zhǔn)確性的評價指標(biāo)，NDCG的值越高，表示排序結(jié)果中的頂部序列的貢獻(xiàn)越大，排序的結(jié)果也就越好，可以接受多種相關(guān)度的評分。給定查詢qi以及對應(yīng)的返回文檔序列，其折扣累積增益(DCG)定義為：

(6)

其中，r(j)是第j個文檔的等級，文中n=1,3,5,7,10。

為使不同等級上的搜索結(jié)果的得分值容易比較，需要對DCG做歸一化處理，歸一化的DCG值叫做NDCG。計算公式定義為：

(7)

其中，IDCG為理想的DCG，即通過人工對查詢的搜索結(jié)果進(jìn)行排序，排到最好的狀態(tài)后，計算得出的這個排列下本查詢的DCG。

3.3 實驗結(jié)果及分析

隨著向原始數(shù)據(jù)集添加PCA處理得到的主特征個數(shù)的增加，兩個數(shù)據(jù)集的MAP值的變化如圖1所示?？紤]到模型的訓(xùn)練時間，這里最多只添加15個主特征。從圖中可以看出，雖然隨著添加個數(shù)的增加，MAP值出現(xiàn)了下降的趨勢，但最終的排序效果仍要優(yōu)于原始的排序結(jié)果。

圖1 新加入的特征個數(shù)對排序結(jié)果的影響

加入較多的PCA主特征向量會增加排序模型的訓(xùn)練時間，引入較少的特征向量則會因數(shù)據(jù)特征信息丟失過多導(dǎo)致最終的排序結(jié)果改善不明顯。綜合考慮排序效果和模型訓(xùn)練時間，選擇添加前4位主特征向量。在擴(kuò)展后的數(shù)據(jù)集上進(jìn)行排序算法隱含的特征選擇，隨著新加入特征個數(shù)的逐漸增加，排序函數(shù)在兩個測試集上的MAP值的變化趨勢如圖2所示。

從圖中可以看出，隨著選擇的特征個數(shù)的逐漸增加，查詢集的排序精度并不是一直增高，甚至有所下降，這也驗證了進(jìn)行特征選擇的必要性。在MQ2007數(shù)據(jù)集，特征大小為25時，MAP值就達(dá)到了特征選擇之前的效果，并趨向于穩(wěn)定，選擇特征集合的大小為31。MQ2008數(shù)據(jù)集上的特征大小為7時就達(dá)到了特征選擇之前的效果，但波動較大，大小為29之后趨于穩(wěn)定，選擇特征集合的大小為33。

圖2 特征子集的大小對MAP值的影響

確定了要選擇的特征個數(shù)，在基于擴(kuò)展的數(shù)據(jù)集上進(jìn)行特征選擇的實驗結(jié)果如圖3所示，其中ListNet表示不進(jìn)行特征處理，ListNet_select表示只進(jìn)行特征選擇，ListNet_4pca表示只添加前4位主特征向量，ListNet_4pca_select表示在數(shù)據(jù)集擴(kuò)展的基礎(chǔ)上進(jìn)行特征選擇。

圖3 應(yīng)用特征選擇的排序結(jié)果對比

從圖3可以看出，三種特征處理的方法基本都使排序結(jié)果有所提高。在基于PCA特征重組方法擴(kuò)展后的數(shù)據(jù)集上進(jìn)行排序算法隱含的特征選擇之后得到的排序效果總體上是最優(yōu)的，雖然在MQ2007數(shù)據(jù)集上NDCG@3的值要略低于特征選擇之前的值，但是顯著優(yōu)于原始的排序函數(shù)得到的效果。

4 結(jié)束語

使用特征處理方法對構(gòu)建排序函數(shù)的特征進(jìn)行處理，并用排序?qū)W習(xí)算法ListNet進(jìn)行驗證，實驗結(jié)果表明，經(jīng)過特征處理后，對排序?qū)W習(xí)的排序結(jié)果的提高有積極意義。

在特征選擇算法中一個很難解決的問題是什么樣的特征子集是最優(yōu)的。希望用盡量少的特征，得到最好的輸出結(jié)果。文中沒有對選擇的特征子集的大小做分析，只是簡單地增加選擇的特征個數(shù)。在后面的工作中，將繼續(xù)研究如何在特征數(shù)和輸出精度中得到一個很好的平衡。