官 蕊，丁家滿，賈連印，游進(jìn)國(guó)，姜 瑛

(1.昆明理工大學(xué)信息工程與自動(dòng)化學(xué)院,云南 昆明 650500;2.云南省人工智能重點(diǎn)實(shí)驗(yàn)室,云南 昆明 650500)

1 引言

在大數(shù)據(jù)時(shí)代，搜索引擎通常將用戶查詢檢索到的內(nèi)容以排序的方式反饋給用戶，因此排序模型在搜索中起著關(guān)鍵作用。排序?qū)W習(xí)(Learning to Rank)屬于機(jī)器學(xué)習(xí)與信息檢索交叉的新興研究領(lǐng)域，它利用機(jī)器學(xué)習(xí)方法解決排序問題，擁有機(jī)器學(xué)習(xí)的自動(dòng)調(diào)整參數(shù)和避免過擬合等優(yōu)點(diǎn)[1]。排序?qū)W習(xí)算法被廣泛應(yīng)用于信息檢索和推薦系統(tǒng)領(lǐng)域[2,3]。排序性能的優(yōu)劣直接影響用戶使用搜索引擎和推薦系統(tǒng)的體驗(yàn)。近幾年，國(guó)際頂級(jí)會(huì)議如SIGIR、WWW、WSDM、CIKM等都將排序?qū)W習(xí)作為一個(gè)主要的研究點(diǎn)[4]。

按照輸入數(shù)據(jù)樣例不同，排序?qū)W習(xí)方法分為3大類：?jiǎn)挝臋nPointwise、文檔對(duì)Pairwise、文檔列表Listwise。其中，文檔列表Listwise方法又可再細(xì)分為2類：直接優(yōu)化基于排序列表的損失的Listwise方法和直接優(yōu)化信息檢索評(píng)價(jià)指標(biāo)的Listwise方法[5]。前類Listwise方法通過定義Listwise損失函數(shù)并最優(yōu)化該損失函數(shù)而求得排序模型，其損失函數(shù)用于衡量預(yù)測(cè)的文檔序列與真實(shí)文檔序列之間的差異。后類Listwise方法將排序模型的構(gòu)建與信息檢索中的評(píng)價(jià)指標(biāo)建立起關(guān)聯(lián)，先定義信息檢索中某個(gè)具體的評(píng)價(jià)準(zhǔn)則(如歸一化折扣累積增益NDCG(Normalized Discounted Cumulative Gain)等)的優(yōu)化目標(biāo)，再選擇適當(dāng)?shù)臋C(jī)器學(xué)習(xí)方法和優(yōu)化算法去學(xué)習(xí)排序模型，以構(gòu)建能滿足用戶需求的最優(yōu)排序模型。直接優(yōu)化信息檢索評(píng)價(jià)指標(biāo)的Listwise方法在許多排序任務(wù)中表現(xiàn)良好。Yue等人[6]提出了SVMMAP(Support Vector Machine learning algorithm based on Mean Average Precision)算法，定義了評(píng)價(jià)指標(biāo)為平均精度均值MAP的目標(biāo)函數(shù)，并以此設(shè)計(jì)了一個(gè)基于Hinge的損失函數(shù)，利用結(jié)構(gòu)化SVM的框架來設(shè)計(jì)排序方法。Xu等人[7]提出一種基于Boosting框架的算法AdaRank，能直接最小化定義在信息檢索評(píng)價(jià)準(zhǔn)則上的指數(shù)損失函數(shù)，用以排序預(yù)測(cè)。Cao等人[8]提出基于神經(jīng)網(wǎng)絡(luò)和梯度下降的排序?qū)W習(xí)算法ListNet，采用K-L散度來定義排序損失函數(shù)進(jìn)行排序。然而，現(xiàn)有的大多數(shù)方法僅僅直接優(yōu)化預(yù)定義排名位置處的評(píng)價(jià)指標(biāo)，例如采用信息檢索評(píng)價(jià)指標(biāo)NDCG@k來配置AdaRank 的損失函數(shù)，AdaRank算法將集中于優(yōu)化前k個(gè)排序位置的NDCG值，排序在k之后的文檔所攜帶的信息則被忽略，因?yàn)樗鼈儗?duì)計(jì)算NDCG@k沒有貢獻(xiàn)[9]，這類方法未完全利用所有排序位置的評(píng)價(jià)指標(biāo)作為監(jiān)督信息。

除了有效利用排序位置的評(píng)價(jià)指標(biāo)作為監(jiān)督信息外，為了提高排序算法效果，突出排序結(jié)果多樣性也是十分關(guān)鍵的[10]。一方面，由于搜索引擎上的信息是高度冗余的，很容易造成用戶查詢返回的排序結(jié)果中頭部包含大量相似甚至重復(fù)的信息，導(dǎo)致用戶不得不耗費(fèi)更多的精力跳過這些冗余的信息，方可獲得更多所需的信息；另一方面，相同的查詢可能代表不同的用戶意圖或興趣。因此，如何盡可能多地覆蓋多用戶的查詢意圖，成為現(xiàn)代搜索引擎必須考慮的因素。

現(xiàn)有的多樣性排序方法將排序過程形式化為順序文檔選擇的過程，從而實(shí)現(xiàn)排序結(jié)果多樣性的目標(biāo)。一般可分為2類方法：第1類是啟發(fā)式方法，啟發(fā)式方法使用最大邊界相關(guān)性標(biāo)準(zhǔn)MMR(Maximal Marginal Relevance)[11]來指導(dǎo)不同排序模型的設(shè)計(jì)。Santos等人[12]提出一種xQuAD(the explicit Query Aspect Diversification)排序方法，明確地為查詢檢索出的文檔與可能的子查詢之間的關(guān)系進(jìn)行建模，以實(shí)現(xiàn)多樣性排序。第2類是機(jī)器學(xué)習(xí)方法[13]，結(jié)合機(jī)器學(xué)習(xí)方法實(shí)現(xiàn)搜索結(jié)果多樣性。近年來，強(qiáng)化學(xué)習(xí)被廣泛應(yīng)用于信息檢索、機(jī)器人控制等領(lǐng)域，應(yīng)用強(qiáng)化學(xué)習(xí)解決排序問題成為新的研究點(diǎn)。強(qiáng)化學(xué)習(xí)問題通常用馬爾可夫決策過程MDP(Markov Decision Process)來描述。Zeng等人[9]提出一種基于馬爾可夫決策過程的排序?qū)W習(xí)算法MDPRank，將獎(jiǎng)勵(lì)函數(shù)定義為信息檢索評(píng)價(jià)指標(biāo)NDCG，充分利用排序位置的信息排序，效果顯著。Luo等人[14]提出利用部分觀測(cè)馬爾可夫決策過程將會(huì)話搜索建模為一個(gè)雙智能體隨機(jī)博弈，以構(gòu)建雙贏搜索框架。Zhang等人[15]提出利用基于日志的文檔重排序，將其建模為POMDP(Partially Observable Markov Decision Process)，以提高排序性能。Xia等人[10]提出一種基于連續(xù)狀態(tài)的馬爾可夫決策過程的多樣性排序MDP-DIV(DIVerse ranking model based on Markov Decision Process)算法，利用排序位置的效用信息，實(shí)現(xiàn)多樣性排序。Wang等人[16]提出了一種極大極小博弈模型，統(tǒng)一迭代優(yōu)化生成檢索模型和判別檢索模型，其中生成檢索模型采用策略梯度算法中的REINFORCE算法[17]進(jìn)行優(yōu)化，解決了網(wǎng)頁搜索、項(xiàng)目推薦等問題。Hu等人[18]提出一種搜索會(huì)話馬爾可夫決策過程來建模多步排序問題，設(shè)計(jì)策略梯度算法學(xué)習(xí)最優(yōu)的排序策略，在電子商務(wù)搜索場(chǎng)景中取得了很好的排序效果。Oosterhuis等人[19]提出一種Double-Rank方法，利用深度強(qiáng)化學(xué)習(xí)技術(shù)同時(shí)為排序和網(wǎng)頁布局建模，解決復(fù)雜排序場(chǎng)景問題。Feng等人[20]提出利用蒙特卡洛樹搜索結(jié)合MDP的排序方法，解決了貪心選擇框架造成的局部最優(yōu)解問題。然而，現(xiàn)有的多樣性排序方法對(duì)每個(gè)排序位置的順序文檔選擇，需要評(píng)估所有查詢與候選文檔的相關(guān)性，如此導(dǎo)致形成了巨大的搜索空間。

受MDPRank算法的啟發(fā)，本文考慮將多樣性排序問題建模為馬爾可夫決策過程，該過程通過研究排序列表的狀態(tài)來決定文檔的排序，從中獲得獎(jiǎng)勵(lì)回報(bào)，并將文檔列表的狀態(tài)從當(dāng)前轉(zhuǎn)移到下一個(gè)，通過不斷選擇局部最優(yōu)解來得到最優(yōu)的排序策略。

綜上，針對(duì)現(xiàn)有的Listwise排序方法的損失函數(shù)在最大化利用所有排序位置的信息以及融合多樣性排序因素方面的不足，本文提出基于強(qiáng)化學(xué)習(xí)的多樣性文檔排序算法RLDDR(Diversity Document Ranking algorithm based on Reinforcement Learning)，將文檔排序問題建模為馬爾可夫決策過程。一方面，RLDDR算法通過計(jì)算所有排序位置的獎(jiǎng)勵(lì)回報(bào)，充分利用所有排序位置信息，在每一次迭代過程中進(jìn)行學(xué)習(xí)，不斷為每個(gè)排序位置選擇最優(yōu)的文檔；另一方面，采用多樣性策略，在排序過程中依據(jù)相似度閾值，將高度相似的文檔刪除，縮小搜索空間，增強(qiáng)排序結(jié)果的多樣性。

2 問題定義

在RLDDR算法中，假設(shè)有n個(gè)帶標(biāo)簽的訓(xùn)練查詢集合{qn,Xn,Yn}，設(shè)Xn={x1,x2,…，xM}為文檔的特征集合，Yn={y1,y2,…，yM}為查詢檢索出的文檔的相關(guān)性標(biāo)簽。M為由查詢qn檢索出的候選文檔{d1,…，dM}的數(shù)目。

應(yīng)用強(qiáng)化學(xué)習(xí)解決文檔排序問題，可以用一個(gè)連續(xù)狀態(tài)的馬爾可夫決策過程來描述。馬爾可夫決策過程由狀態(tài)集、動(dòng)作集、狀態(tài)轉(zhuǎn)移函數(shù)、獎(jiǎng)勵(lì)值函數(shù)和策略函數(shù)組成，可以用五元組〈S,A,T,R,π〉表示。下面將分別說明各元組的含義：

(1)狀態(tài)集S是描述系統(tǒng)環(huán)境的一組狀態(tài)集合。狀態(tài)集定義為一個(gè)二元組，包含排序位置信息和候選文檔集合。因此，在時(shí)間步t，狀態(tài)st定義為二元組[t,Xt]。其中，Xt是時(shí)間步t待排序的所有候選文檔集合。

(2)動(dòng)作集A是智能體Agent可選的所有離散動(dòng)作集合。所有可選的動(dòng)作集合取決于當(dāng)前的狀態(tài)st，表示為A(st)。在時(shí)間步t，選擇一個(gè)文檔xm(at)∈Xt放在排序位置t+1上。其中m(at)是在動(dòng)作at下可選文檔的索引。

(3)狀態(tài)轉(zhuǎn)移函數(shù)T(S,A)是一個(gè)描述環(huán)境狀態(tài)轉(zhuǎn)移的函數(shù)，作為對(duì)時(shí)間t選擇執(zhí)行動(dòng)作at的結(jié)果，該函數(shù)將環(huán)境狀態(tài)st轉(zhuǎn)移到st+1。一旦選擇了一個(gè)動(dòng)作意味著選擇了一個(gè)文檔放置在排序位置，這時(shí)要將該動(dòng)作選擇的文檔在候選文檔集中刪除。避免選擇重復(fù)的文檔進(jìn)行排序。新狀態(tài)st+1如式(1)所示：

st+1=T([t,Xt],at)=[t+1,Xtxm(at)}]

(1)

(4)獎(jiǎng)勵(lì)函數(shù)R(S,A)也稱為強(qiáng)化函數(shù)，是一種即時(shí)獎(jiǎng)勵(lì)。在排序問題中，獎(jiǎng)勵(lì)視為對(duì)動(dòng)作選擇文檔的評(píng)價(jià)。因此，本文將獎(jiǎng)勵(lì)函數(shù)定義為信息檢索的評(píng)價(jià)指標(biāo)。本文將執(zhí)行動(dòng)作at后，環(huán)境給予的獎(jiǎng)勵(lì)定義為信息檢索的評(píng)價(jià)指標(biāo)歸一化折扣累積增益NDCG，使得RLDDR算法能夠利用所有排序位置的評(píng)價(jià)指標(biāo)，即所有排序位置的NDCG值。獎(jiǎng)勵(lì)函數(shù)R(S,A)如式(2)所示：

(2)

其中，ym(at)是動(dòng)作at選擇的文檔xm(at)的相關(guān)性標(biāo)簽。每一個(gè)排序位置的獎(jiǎng)勵(lì)對(duì)應(yīng)于每個(gè)排序位置的NDCG值。

(5)策略函數(shù)π(a|s)描述了Agent的行為。它是從環(huán)境狀態(tài)到動(dòng)作文檔的一種映射。RLDDR算法的策略函數(shù)定義為所有可選的候選動(dòng)作文檔的概率分布。策略函數(shù)π(a|s)如式(3)所示。

(3)

其中，θ是策略參數(shù)，θ的維度和文檔向量的特征維度相等。

3 RLDDR算法

3.1 融合多樣性

排序的最終目的是確定用戶查詢返回的文檔序列列表，除了傳統(tǒng)的相關(guān)性因素外，保證排序結(jié)果的多樣性能夠給用戶提供有關(guān)查詢的更豐富的查詢結(jié)果，避免了返回結(jié)果的冗余。在提高排序相關(guān)性的基礎(chǔ)上，綜合多樣性因素，不僅能夠幫助用戶了解查詢的相關(guān)信息，還能提高用戶的搜索興趣。

對(duì)于排序結(jié)果的多樣性，本文目標(biāo)是將最相關(guān)的文檔返回到查詢中，同時(shí)確保文檔的多樣性。由于RLDDR算法的空間復(fù)雜度與查詢返回的候選文檔集的個(gè)數(shù)即動(dòng)作集A的大小密切相關(guān)，因此若要降低算法的空間復(fù)雜度，一種方法是通過縮小動(dòng)作集A來縮小算法的多樣性搜索空間，同時(shí)必須保持排序準(zhǔn)確性不降低，這時(shí)就要求縮小動(dòng)作集的方法必須保證2點(diǎn)。第1，它能夠智能地刪除部分冗余即高度相似的動(dòng)作。第2，刪除后的候選動(dòng)作集幾乎可以替代原候選動(dòng)作集。例如，候選動(dòng)作集中動(dòng)作ai和動(dòng)作aj高度相似，且都和查詢q相關(guān)，則在動(dòng)作集中刪除動(dòng)作ai或動(dòng)作aj。因?yàn)閯?dòng)作ai和動(dòng)作aj高度相似，當(dāng)獲取了動(dòng)作ai所攜帶的信息，對(duì)動(dòng)作aj所攜帶的信息也就有了了解。此外，為了保證候選文檔的多樣性，將它們都刪除是不合理的。

RLDDR結(jié)合多樣性策略，降低算法搜索的空間復(fù)雜度。假設(shè)某一時(shí)間步t，選擇動(dòng)作at∈A(st)，此時(shí)，計(jì)算候選動(dòng)作集中動(dòng)作at的K個(gè)最近鄰動(dòng)作。由于文檔向量通常很長(zhǎng)，并且是稀疏的,于是本文采用余弦相似度(如式(4)所示)計(jì)算動(dòng)作at的K個(gè)最近鄰動(dòng)作。設(shè)置相似度閾值來評(píng)判候選動(dòng)作集中動(dòng)作at的近鄰動(dòng)作。

(4)

在訓(xùn)練階段，文檔多樣性排序的過程如下所示：給定查詢q、查詢q返回的M個(gè)文檔的特征集合X以及每個(gè)文檔相應(yīng)的相關(guān)性標(biāo)簽。系統(tǒng)環(huán)境的狀態(tài)初始化為s0=[0,X]。在每個(gè)時(shí)間步t=0,1,…，M-1，Agent根據(jù)環(huán)境狀態(tài)st=[t,Xt]，選擇一個(gè)動(dòng)作，即從候選文檔集中選擇文檔xm(at)并將其放置于排序列表中?；谒x擇文檔的相關(guān)性標(biāo)簽ym(at)，Agent接收環(huán)境給出的即時(shí)獎(jiǎng)勵(lì)rt+1=R(st,at)。然后，根據(jù)相似度閾值，判斷是否在候選集中刪除與所選文檔相似的K個(gè)最近鄰文檔。若所選文檔的相似度大于相似度閾值，表明該文檔與所選文檔高度相似，則在候選文檔集中刪除該文檔；若小于相似度閾值，則不刪除該文檔。算法隨之轉(zhuǎn)移到下一時(shí)間步t+1，系統(tǒng)環(huán)境狀態(tài)變化為st+1=[t+1,Xt+1]。同時(shí)，重復(fù)此過程直至M個(gè)文檔全部被選擇，完成排序。

在測(cè)試或在線文檔多樣性排序階段，因?yàn)椴]有相關(guān)性標(biāo)簽，也就無法得到每個(gè)排序位置相應(yīng)的獎(jiǎng)勵(lì)。此時(shí)RLDDR算法按照學(xué)習(xí)到的策略，選擇在每個(gè)時(shí)間步具有最大概率的文檔，因此在線文檔多樣性排序相當(dāng)于為所有檢索到的文檔分配排序分?jǐn)?shù)f(x;θ)=θTx，其中，x為文檔向量，依據(jù)相似度閾值裁剪高度相似文檔，按降序?qū)ξ臋n進(jìn)行排序。

3.2 策略參數(shù)學(xué)習(xí)

在本文中，通過強(qiáng)化學(xué)習(xí)中的策略梯度方法REINFORCE來學(xué)習(xí)策略參數(shù)θ。策略梯度方法是強(qiáng)化學(xué)習(xí)中的另一大分支。與基于值的方法(如Q-learning，Sarsa)類似，REINFORCE也需要同環(huán)境進(jìn)行交互，不同的是它輸出的不是動(dòng)作的價(jià)值，而是所有可選動(dòng)作的概率分布。RLDDR算法的目標(biāo)是最大化每一時(shí)間步的累積期望獎(jiǎng)勵(lì)J(θ),如式(5)所示：

J(θ)=ΕL～πw[G(L)]

(5)

其中，L={xm(a0),xm(a1),…,xm(aM-1)}是根據(jù)RLDDR算法排序的文檔列表，G(L)定義為文檔列表的累積獎(jiǎng)勵(lì)，如式(6)所示：

(6)

其中，γ為折扣因子，rn為獎(jiǎng)勵(lì)回報(bào)。

若γ=1,則G(L)的定義與信息檢索的評(píng)價(jià)指標(biāo)NDCG一致。因此，RLDDR算法可以直接優(yōu)化信息檢索的評(píng)價(jià)指標(biāo)。

(7)

其中，πθ為策略參數(shù)θ下的策略表示。

利用該梯度調(diào)整策略參數(shù)，得到策略參數(shù)更新式為：

(8)

(9)

(10)

Gt的設(shè)置讓參數(shù)θ沿著有利于產(chǎn)生最高獎(jiǎng)勵(lì)回報(bào)的動(dòng)作的方向移動(dòng)，可以使好的動(dòng)作得到更高的獎(jiǎng)勵(lì)。本文提出的RLDDR算法的具體描述如算法1所示。算法2為多樣性序列算法，描述了算法1中獲取多樣性序列的詳細(xì)過程。

算法1RLDDR算法

輸入：帶標(biāo)簽的訓(xùn)練樣例集合D={q,X,Y},學(xué)習(xí)率η，折扣因子γ，獎(jiǎng)勵(lì)函數(shù)R。

輸出：策略參數(shù)θ。

步驟1隨機(jī)初始化策略參數(shù)θ；

步驟2初始化策略中間參數(shù)Δθ=0；

步驟3根據(jù)算法2獲取多樣性序列(θ,q,X,Y,R)；

步驟4根據(jù)式(9)計(jì)算多樣性序列(θ,q,X,Y,R)的累積期望獎(jiǎng)勵(lì)Gt；

步驟5根據(jù)式(10)更新策略中間參數(shù)Δθ；

步驟6根據(jù)式(8)更新策略參數(shù)θ。

算法2多樣性序列算法

輸入：帶標(biāo)簽的訓(xùn)練樣例集合D={q,X,Y},策略參數(shù)θ,獎(jiǎng)勵(lì)函數(shù)R，序列長(zhǎng)度L，相似度閾值ε。

輸出：多樣性序列E。

步驟1初始化s0= [0,X],M=|X|，多樣性序列E。

步驟2根據(jù)式(3)取樣動(dòng)作at∈A(st)～πθ(at|st;θ)。

步驟3根據(jù)式(2)計(jì)算獎(jiǎng)勵(lì)值rt+1=R(st,at)；

步驟4根據(jù)式(4)計(jì)算at的K個(gè)最近鄰動(dòng)作的相似度s=sim(at,a)。

步驟5若相似性s>ε，從X中刪除at的K個(gè)最近鄰動(dòng)作；若s≤ε，則不刪除。

步驟6根據(jù)式(1)轉(zhuǎn)換狀態(tài)st至st+1。

步驟7添加(st,,at,rt+1)至E的末端。

步驟8重復(fù)步驟2～步驟7，直至多樣性序列E長(zhǎng)度等于L。

4 實(shí)驗(yàn)結(jié)果與分析

實(shí)驗(yàn)數(shù)據(jù)集來自微軟亞洲研究院開發(fā)的LETOR數(shù)據(jù)集，本文從中選取了OHSUMED[21]和MQ2007[22]作為基準(zhǔn)數(shù)據(jù)集。每個(gè)數(shù)據(jù)集由查詢、相應(yīng)的檢索文檔和人工標(biāo)注的相關(guān)性標(biāo)簽組成。在多樣性排序領(lǐng)域，本文組合了4個(gè)TREC數(shù)據(jù)集(WT2009,WT2010,WT2011,WT2012)[23]進(jìn)行實(shí)驗(yàn)，共有200個(gè)查詢。每個(gè)查詢包括由TREC確定的若干個(gè)子主題。相關(guān)性標(biāo)簽根據(jù)子主題級(jí)別設(shè)定，0表示不相關(guān)，1表示相關(guān)。在所有實(shí)驗(yàn)中，根據(jù)訓(xùn)練經(jīng)驗(yàn)，K取動(dòng)作集A大小 的10%，序列長(zhǎng)度L取返回結(jié)果個(gè)數(shù)k，學(xué)習(xí)率設(shè)為0.001，相似度閾值設(shè)為0.65。使用LETOR標(biāo)準(zhǔn)特征并設(shè)置γ=1進(jìn)行實(shí)驗(yàn)，使RLDDR算法能夠直接優(yōu)化信息檢索的評(píng)價(jià)指標(biāo)NDCG。

對(duì)于實(shí)驗(yàn)結(jié)果，本文采用了信息檢索中廣泛使用的評(píng)價(jià)指標(biāo)進(jìn)行評(píng)價(jià)，包括NDCG@k，α-NDCG，S-recall。NDCG@k指標(biāo)通過評(píng)價(jià)查詢返回的文檔列表中，相關(guān)文檔與不相關(guān)文檔的相對(duì)位置來衡量排序文檔列表的優(yōu)劣。所有的查詢相關(guān)文檔均排在不相關(guān)文檔的前面時(shí)，評(píng)價(jià)指標(biāo)NDCG的值達(dá)到最大。本文采用在排序位置k為1,3,5和10的NDCG值進(jìn)行評(píng)估。TREC數(shù)據(jù)集的評(píng)價(jià)指標(biāo)α-NDCG被廣泛應(yīng)用于評(píng)估排序模型的多樣性，通過明確獎(jiǎng)勵(lì)多樣性文檔和懲罰冗余文檔來衡量排序列表的多樣性。根據(jù)經(jīng)驗(yàn)設(shè)置參數(shù)α為0.5。傳統(tǒng)的多樣性評(píng)價(jià)指標(biāo)S-recall衡量檢索文檔子主題的覆蓋率。所有的評(píng)估都是在top-k返回結(jié)果(k=5和k=10)上計(jì)算的。

將3個(gè)數(shù)據(jù)集的數(shù)據(jù)均分為訓(xùn)練集、驗(yàn)證集和測(cè)試集，大小比例為3∶1∶1。實(shí)驗(yàn)結(jié)果均采用五折交叉驗(yàn)證數(shù)據(jù)集上各評(píng)價(jià)指標(biāo)的平均值。將提出的RLDDR算法與經(jīng)典的排序?qū)W習(xí)算法進(jìn)行比較，包括基于Listwise的ListNet算法、直接優(yōu)化信息檢索評(píng)價(jià)指標(biāo)的MDPRank算法。在多樣性排序領(lǐng)域，選取代表性的多樣性排序算法MMR、xQuAD、MDP-DIV(S-recall)進(jìn)行對(duì)比。

表1和表2分別列出了RLDDR算法和對(duì)比算法在NDCG@k評(píng)價(jià)指標(biāo)上的對(duì)比結(jié)果。

Table 1 Comparison of NDCG@k value on OHSUMED表1 在OHSUMED 上NDCG@k值的比較

Table 2 Comparison of NDCG@k value on MQ2007表2 在MQ2007上NDCG@k值的比較

由表1可知，本文算法在k=1時(shí)具有較高NDCG@k值，說明其能夠?qū)⒆钕嚓P(guān)文檔排序在排序列表的前方位置。但是，隨著k的增大，由于RLDDR算法的融合多樣性因素原則，裁剪了高度相似文檔致使NDCG@k有所下降。MDPRank算法排序準(zhǔn)確性整體優(yōu)于RLDDR算法。但是，在k取1，3，5時(shí)，相較基于Listwise的ListNet算法，本文算法仍具有一定的準(zhǔn)確性。由表2可知，在MQ2007數(shù)據(jù)集上，RLDDR算法在k=1時(shí)也取得了較高的NDCG值。在k=3,5,10時(shí)，本文算法也獲得了不錯(cuò)的準(zhǔn)確性。在k=10時(shí)，基于神經(jīng)網(wǎng)絡(luò)和梯度下降的ListNet算法的排序準(zhǔn)確性最好。

本文算法在考慮多樣性因素之外，仍能保證排序準(zhǔn)確性的主要原因是在訓(xùn)練階段，能夠利用獎(jiǎng)勵(lì)回報(bào)作為監(jiān)督信息，更新策略參數(shù)，學(xué)習(xí)最優(yōu)的排序策略。RLDDR算法在OHSUMED和MQ2007數(shù)據(jù)集上均有一定改進(jìn)，是直接優(yōu)化信息檢索評(píng)價(jià)指標(biāo)的有效算法。

圖1更加直觀地顯示了本文算法和對(duì)比算法在NDCG@k上的效果及趨勢(shì)。

Figure 1 Comparison of NDCG@k value on OHSUMED圖1 在OHSUMED 上NDCG@k值的比較

表3和表4列出了在多樣性排序領(lǐng)域中本文算法和對(duì)比算法的多樣性排序評(píng)價(jià)指標(biāo)α-NDCG和S-recall的實(shí)驗(yàn)對(duì)比結(jié)果。

Table 3 Comparison of α-NDCG value on TREC表3 在TREC上α-NDCG值的比較

Table 4 Comparison of S-recall value on TREC表4 在TREC上S-recall值的比較

由表3可知，在提高文檔多樣性方面，本文算法有不錯(cuò)的表現(xiàn)。本文算法在k=5和k=10時(shí)評(píng)價(jià)指標(biāo)α-NDCG均高于對(duì)比算法。通過裁剪高度相似的文檔，縮小了文檔搜索空間，增強(qiáng)了排序文檔的多樣性。由表4可知，在傳統(tǒng)的多樣性指標(biāo)S-recall方面,本文算法較對(duì)比算法能夠使排序文檔涵蓋更多的子主題，說明文檔的多樣性高于對(duì)比算法的，體現(xiàn)了RLDDR算法融合多樣性排序的有效性。

綜上，在排序?qū)W習(xí)方法中加入多樣性排序因素，排序準(zhǔn)確性會(huì)有所下降。但是，保證一定程度的搜索結(jié)果多樣性也是未來搜索引擎算法調(diào)整的趨勢(shì)。多樣性排序的優(yōu)點(diǎn)將彌補(bǔ)準(zhǔn)確性稍有下降的缺點(diǎn)，幫助用戶過濾高度相似的文檔，不僅能夠避免返回結(jié)果的冗余，還能提高用戶的搜索興趣。

5 結(jié)束語

針對(duì)現(xiàn)有排序?qū)W習(xí)算法中損失函數(shù)未能充分利用所有排序位置信息，以及確保排序結(jié)果多樣性方面能力不足的問題，本文引入強(qiáng)化學(xué)習(xí)思想，通過計(jì)算所有排序位置的獎(jiǎng)勵(lì)回報(bào)，并將其作為評(píng)價(jià)監(jiān)督，在每一次迭代過程中進(jìn)行學(xué)習(xí)，保證了每個(gè)排序位置選擇最優(yōu)的文檔，提高排序準(zhǔn)確性；結(jié)合多樣性策略，通過將高度相似的文檔刪除的方式確保排序結(jié)果的多樣性。實(shí)驗(yàn)結(jié)果表明，RLDDR算法較相關(guān)對(duì)比算法能獲得更顯著的排序結(jié)果。在以后的工作中，將繼續(xù)挖掘影響排序性能的因素，得到性能更優(yōu)的排序模型。