一種基于新型損失函數(shù)的Listwise排序?qū)W習(xí)方法

龔 安，孫 輝，喬 杰

(1．中國(guó)石油大學(xué)(華東) 計(jì)算機(jī)與通信工程學(xué)院，山東 青島 266580；2．中國(guó)石油大學(xué)(華東) 石油工程學(xué)院，山東 青島 266580)

0 引 言

近年來(lái)，排序?qū)W習(xí)方法以其優(yōu)異的性能成為信息檢索與機(jī)器學(xué)習(xí)交叉領(lǐng)域中的“驕子”[1]。排序?qū)W習(xí)方法按照訓(xùn)練樣本的不同分為點(diǎn)方式、對(duì)方式和列表方式[2-4]。研究表明，Listwise是排序?qū)W習(xí)中效果較好的一種算法，為了獲得整個(gè)序列的排序情況，在實(shí)現(xiàn)過(guò)程中將整個(gè)文檔序列看成一個(gè)訓(xùn)練樣本，不僅結(jié)果展示自然，并且實(shí)現(xiàn)了對(duì)不同查詢(xún)文檔進(jìn)行區(qū)分的功能[5-7]。在排序過(guò)程中，損失函數(shù)用來(lái)評(píng)價(jià)預(yù)測(cè)結(jié)果與真實(shí)結(jié)果之間擬合程度的高低，所以損失函數(shù)的構(gòu)建尤為重要。

針對(duì)損失函數(shù)，研究人員在優(yōu)化改進(jìn)、降低時(shí)間復(fù)雜度等方面取得了比較大的進(jìn)步。文獻(xiàn)[8]提出了一種SHF-SDCG(smoothed hinge function-smoothing discounted cumulative gain)損失函數(shù)融合方法，將Pairwise方法損失函數(shù)與Pointwise方法的損失函數(shù)相融合，效果顯著，但是時(shí)間復(fù)雜度高。文獻(xiàn)[9]提出用位置近似函數(shù)來(lái)平滑文檔位置損失函數(shù)，忽視了由單個(gè)文檔位置變化造成的損失。文獻(xiàn)[10]在降低訓(xùn)練過(guò)程時(shí)間復(fù)雜度的同時(shí)只考慮列表前端位置，缺乏對(duì)位置信息的利用。

基于此，文中提出了一種改進(jìn)的Listwise排序?qū)W習(xí)算法，以整排列表作為輸入，通過(guò)引入Pointwise損失函數(shù)及位置加權(quán)因子，對(duì)Listwise損失函數(shù)進(jìn)行融合，并采用效率更高的Top-k訓(xùn)練方法。最后，在LETOR4.0數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，對(duì)算法性能進(jìn)行驗(yàn)證。

1 改進(jìn)的Listwise排序?qū)W習(xí)算法

1.1 Listwise排序?qū)W習(xí)方法

Listwise將整個(gè)文檔序列看作一個(gè)樣本，通過(guò)優(yōu)化信息檢索和定義損失函數(shù)來(lái)得到排序函數(shù)。

Listwise采用概率模型計(jì)算列的損失函數(shù)，即通過(guò)概率模型把一列得分映射成概率分布，然后使用概率分布的度量作為損失函數(shù)[11-12]。度量分布通常有兩種方法：組合概率和Top-k概率。當(dāng)文檔數(shù)較多時(shí)，組合概率會(huì)增大計(jì)算量，故通常選擇Top-k概率來(lái)解決這個(gè)問(wèn)題。

1.2 損失函數(shù)的融合

排序?qū)W習(xí)的過(guò)程就是不斷優(yōu)化損失函數(shù)的過(guò)程，在確定損失函數(shù)后，對(duì)其不斷優(yōu)化，直到找到損失函數(shù)最小時(shí)的參數(shù)，最后得到排序函數(shù)模型。

1.2.1 損失函數(shù)分類(lèi)

(1)Pointwise損失函數(shù)。

(1)

其中，yj為訓(xùn)練集合中文檔位置為j的對(duì)象的相關(guān)性標(biāo)注分；f(xj)為學(xué)習(xí)排序函數(shù)對(duì)文檔xj的相關(guān)性預(yù)測(cè)值。

Pointwise方法的訓(xùn)練樣例是單個(gè)文檔，它關(guān)注每個(gè)文檔與查詢(xún)的相關(guān)性大小，但是忽略了不同文檔與查詢(xún)相關(guān)性的大小關(guān)系，同時(shí)它也是人工神經(jīng)網(wǎng)絡(luò)中經(jīng)常用于衡量訓(xùn)練樣例的預(yù)測(cè)值與真實(shí)值之間誤差的函數(shù)。

(2)Pairwise損失函數(shù)。

(2)

(3)

其中，oj=f(xj)，ojk=f(xj)-f(xk)。

Pairwise方法的訓(xùn)練樣例是偏序文檔對(duì)，它將對(duì)文檔的排序轉(zhuǎn)化為對(duì)不同文檔與查詢(xún)相關(guān)性大小關(guān)系的預(yù)測(cè)。

(3)Listwise交叉熵?fù)p失函數(shù)。

(4)

其中，Gk為T(mén)op-k前k個(gè)對(duì)象。

Listwise方法將文檔序列作為整體考慮，認(rèn)為用戶(hù)關(guān)心的主要是位于文檔序列前列的文檔，從而忽略了每個(gè)文檔與查詢(xún)相關(guān)性的大小。

1.2.2 引入位置加權(quán)因子

排序的目的是將每個(gè)文檔按照查詢(xún)相關(guān)性進(jìn)行排序，從而獲取文檔在整個(gè)序列的位置。由于衡量排序預(yù)測(cè)效果最明顯的方法是和真實(shí)序列中的每篇文檔所處的位置作比較，因此引入位置加權(quán)因子，即當(dāng)文檔排列出現(xiàn)錯(cuò)位時(shí)，就將該文檔所在位置的倒數(shù)乘以位置損失的平方(位置損失就是預(yù)測(cè)得分與實(shí)際得分的差值)，就可以使相關(guān)文檔(根據(jù)相關(guān)性得分)的排列更靠前，不相關(guān)文檔更靠后，提高整體的排序質(zhì)量。

訓(xùn)練集中的數(shù)據(jù)包含許多查詢(xún)及查詢(xún)項(xiàng)對(duì)應(yīng)的文檔，每個(gè)文檔都有相關(guān)性得分，假設(shè)查詢(xún)之間服從獨(dú)立分布。例如，{q1,q2,…,qn}是查詢(xún)集，qj表示第j個(gè)查詢(xún)，Dj={dj,1,dj,2,…,dj,m}，其中Dj表示查詢(xún)qj所對(duì)應(yīng)的文檔集合，yj={yj,1,yj,2,…,yj,m}，yj表示每個(gè)文檔所對(duì)應(yīng)的得分。特征向量xj由特征函數(shù)φ(·)得到，訓(xùn)練特征集可以表示為x={x1,x2,…,xn}，排序函數(shù)為f(x)，則查詢(xún)每個(gè)qj所對(duì)應(yīng)的文檔集的位置加權(quán)因子為：

(5)

1.2.3 融合產(chǎn)生新型損失函數(shù)

綜合上述Pointwise、Listwise方法的優(yōu)缺點(diǎn)分析，引進(jìn)位置加權(quán)因子，依據(jù)SHF-SDCG損失函數(shù)的融合框架，進(jìn)行損失函數(shù)融合，得到新的損失函數(shù)：

L=Lpt×Tm+(1-Tm)×(Lls×Tm+(1-Tm)×Lp)

(6)

1.3 改進(jìn)的Listwise排序?qū)W習(xí)算法

文中采用雙層神經(jīng)網(wǎng)絡(luò)模型，借助誤差反向傳播算法以達(dá)到調(diào)節(jié)權(quán)值ω的目的，然后使用梯度下降優(yōu)化損失函數(shù)L得到排序模型。其算法具體描述如下：

輸入：訓(xùn)練集{(x(1),y(1)),(x(2),y(2)),…,(x(m),y(m))}

參數(shù)：設(shè)置迭代次數(shù)T，學(xué)習(xí)率η并初始化權(quán)重ω0。網(wǎng)絡(luò)輸入層單元數(shù)為nin，網(wǎng)絡(luò)隱藏層單元數(shù)為nhidden

輸出：改進(jìn)的Listwise排序模型

1.創(chuàng)建nin個(gè)網(wǎng)絡(luò)輸入單元，nhidden個(gè)網(wǎng)絡(luò)隱藏層單元，一個(gè)輸出單元的網(wǎng)絡(luò)，按照ω0初始化網(wǎng)絡(luò)初始權(quán)重值。

2.fort=1 tot=T

3.fori=1 toi=m

4.輸入查詢(xún)q(i)的對(duì)應(yīng)特征x(i)到神經(jīng)網(wǎng)絡(luò)，并且計(jì)算輸出得分f(xi)，同時(shí)計(jì)算Lpt、Lls以及Lp

6.更新網(wǎng)絡(luò)權(quán)重ωt+1=ωt-η×ωt

7.End for

8.End for

其中

f(x)=ω·x

(7)

對(duì)損失函數(shù)進(jìn)行梯度計(jì)算：

(8)

(9)

Tm×(1-Tm)2

(10)

(11)

2 實(shí) 驗(yàn)

2.1 數(shù)據(jù)集

實(shí)驗(yàn)采用Letor4.0數(shù)據(jù)集中的TREC 2008，該數(shù)據(jù)集為46維數(shù)據(jù)，每一行表示一個(gè)樣本文檔，第一列是樣本相關(guān)度，第二列是查詢(xún)qid，其他列包含46維文檔特征索引以及相應(yīng)的特征值，例如：BM25、IF、語(yǔ)言模型等內(nèi)容特征，PageRank等基于網(wǎng)頁(yè)分析的特征。該數(shù)據(jù)集采用5折交叉驗(yàn)證策略，分為5組，每組有三個(gè)學(xué)習(xí)子集：訓(xùn)練集、驗(yàn)證集和測(cè)試集。規(guī)模較小的驗(yàn)證集被用來(lái)確定最佳迭代次數(shù)以及網(wǎng)絡(luò)權(quán)重。

2.2 評(píng)價(jià)標(biāo)準(zhǔn)

采用NDCG(normalized discounted cumulative gain)評(píng)價(jià)指標(biāo)，它是用來(lái)衡量排序質(zhì)量的指標(biāo)，當(dāng)所有相關(guān)文檔排在不相關(guān)文檔的前面時(shí)，NDCG值最大[13-15]。其定義如下：

(12)

其中，Zn為歸一化因子；r(j)為第j個(gè)位置文檔的標(biāo)簽，j為位置。

2.3 實(shí)驗(yàn)設(shè)計(jì)

文中算法實(shí)驗(yàn)設(shè)定隱藏層的權(quán)值為較小的隨機(jī)值[-0.2，0.2]，輸入層的權(quán)值設(shè)定為0或者較小的隨機(jī)值[-0.01，0.01]，初始學(xué)習(xí)率為0.003，在每次學(xué)習(xí)中，如果上次迭代的平均誤差小于所有樣例的平均誤差，則將學(xué)習(xí)率降為一半。最后將文中算法與Pointwise方法中的Regression算法、Pairwise方法中的RankSVM算法和基于SHF-SDCG改進(jìn)的RankNet算法及Listwise方法中的ListNet算法進(jìn)行實(shí)驗(yàn)對(duì)比。

2.4 實(shí)驗(yàn)結(jié)果對(duì)比與分析

采用NDCG@K，實(shí)驗(yàn)結(jié)果對(duì)比如表1所示。為了使結(jié)果對(duì)比更加直觀(guān)，將表1數(shù)據(jù)用直方圖表示出來(lái)，如圖1所示。

表1 NDCG@K值的比較

圖1 NDCG@K值的比較

從圖中可以看出，Listwise算法要優(yōu)于其他算法，主要原因是Listwise方法比Pointwise方法、Pairwise方法更加直接自然，可以區(qū)分不同查詢(xún)中的文檔。當(dāng)k=1,2,3時(shí)，基于SHF-SDCG改進(jìn)的RankNet要優(yōu)于其他算法，主要原因是在Pairwise方法中增加了對(duì)單個(gè)文檔相關(guān)性的考慮，不會(huì)出現(xiàn)因?yàn)槲臋n對(duì)內(nèi)兩個(gè)文檔的相關(guān)性預(yù)測(cè)錯(cuò)誤而導(dǎo)致連鎖反應(yīng)影響最終排序性能的現(xiàn)象，并且當(dāng)k比較小時(shí)，改進(jìn)Pairwise方法無(wú)限接近于Listwise方法，并且在排序性能上要優(yōu)于Listwise方法。而當(dāng)k=5,6,…,10時(shí)，改進(jìn)Listwise方法的NCDG@k值比較大且穩(wěn)定，主要原因是當(dāng)k較大時(shí)，改進(jìn)Listwise方法較其他方法不僅考慮了相關(guān)文檔位置，而且引入了Pointwise損失函數(shù)，更加全面地考慮了排序的各個(gè)方面。

綜上所述，改進(jìn)Listwise方法得到的排序列表中的相關(guān)文檔排在列表前面位置的情況要優(yōu)于Listwise、Pointwise、Pairwise等方法。

3 結(jié)束語(yǔ)

通過(guò)對(duì)排序效果最自然、效果較好的Listwise方法進(jìn)行研究，在現(xiàn)有SHF-SDCG損失函數(shù)融合框架的基礎(chǔ)上，引入位置加權(quán)因子以及Pointwise損失函數(shù)，分別采用梯度下降算法和多層神經(jīng)網(wǎng)絡(luò)算法訓(xùn)練網(wǎng)絡(luò)權(quán)重值，對(duì)Listwise算法進(jìn)行了綜合改進(jìn)與優(yōu)化，解決了原算法存在的時(shí)間復(fù)雜度高、排序位置信息利用度低等問(wèn)題。為了驗(yàn)證改進(jìn)之后Listwise算法的優(yōu)越性，選用Letor4.0數(shù)據(jù)集中的TREC 2008進(jìn)行實(shí)驗(yàn)，NDCG值的對(duì)比證實(shí)了改進(jìn)算法在排序過(guò)程中取得了較好的實(shí)驗(yàn)效果。