基于強化學習的多樣性文檔排序算法*

官 蕊，丁家滿，賈連印，游進國，姜 瑛

(1.昆明理工大學信息工程與自動化學院,云南 昆明 650500;2.云南省人工智能重點實驗室,云南 昆明 650500)

1 引言

在大數據時代，搜索引擎通常將用戶查詢檢索到的內容以排序的方式反饋給用戶，因此排序模型在搜索中起著關鍵作用。排序學習(Learning to Rank)屬于機器學習與信息檢索交叉的新興研究領域，它利用機器學習方法解決排序問題，擁有機器學習的自動調整參數和避免過擬合等優點[1]。排序學習算法被廣泛應用于信息檢索和推薦系統領域[2,3]。排序性能的優劣直接影響用戶使用搜索引擎和推薦系統的體驗。近幾年，國際頂級會議如SIGIR、WWW、WSDM、CIKM等都將排序學習作為一個主要的研究點[4]。

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

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

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

受MDPRank算法的啟發，本文考慮將多樣性排序問題建模為馬爾可夫決策過程，該過程通過研究排序列表的狀態來決定文檔的排序，從中獲得獎勵回報，并將文檔列表的狀態從當前轉移到下一個，通過不斷選擇局部最優解來得到最優的排序策略。

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

2 問題定義

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

應用強化學習解決文檔排序問題，可以用一個連續狀態的馬爾可夫決策過程來描述。馬爾可夫決策過程由狀態集、動作集、狀態轉移函數、獎勵值函數和策略函數組成，可以用五元組〈S,A,T,R,π〉表示。下面將分別說明各元組的含義：

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

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

(3)狀態轉移函數T(S,A)是一個描述環境狀態轉移的函數，作為對時間t選擇執行動作at的結果，該函數將環境狀態st轉移到st+1。一旦選擇了一個動作意味著選擇了一個文檔放置在排序位置，這時要將該動作選擇的文檔在候選文檔集中刪除。避免選擇重復的文檔進行排序。新狀態st+1如式(1)所示：

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

(1)

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

(2)

其中，ym(at)是動作at選擇的文檔xm(at)的相關性標簽。每一個排序位置的獎勵對應于每個排序位置的NDCG值。

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

(3)

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

3 RLDDR算法

3.1 融合多樣性

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

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

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

(4)

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

在測試或在線文檔多樣性排序階段，因為并沒有相關性標簽，也就無法得到每個排序位置相應的獎勵。此時RLDDR算法按照學習到的策略，選擇在每個時間步具有最大概率的文檔，因此在線文檔多樣性排序相當于為所有檢索到的文檔分配排序分數f(x;θ)=θTx，其中，x為文檔向量，依據相似度閾值裁剪高度相似文檔，按降序對文檔進行排序。

3.2 策略參數學習

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

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

(5)

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

(6)

其中，γ為折扣因子，rn為獎勵回報。

若γ=1,則G(L)的定義與信息檢索的評價指標NDCG一致。因此，RLDDR算法可以直接優化信息檢索的評價指標。

(7)

其中，πθ為策略參數θ下的策略表示。

利用該梯度調整策略參數，得到策略參數更新式為：

(8)

(9)

(10)

Gt的設置讓參數θ沿著有利于產生最高獎勵回報的動作的方向移動，可以使好的動作得到更高的獎勵。本文提出的RLDDR算法的具體描述如算法1所示。算法2為多樣性序列算法，描述了算法1中獲取多樣性序列的詳細過程。

算法1RLDDR算法

輸入：帶標簽的訓練樣例集合D={q,X,Y},學習率η，折扣因子γ，獎勵函數R。

輸出：策略參數θ。

步驟1隨機初始化策略參數θ；

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

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

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

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

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

算法2多樣性序列算法

輸入：帶標簽的訓練樣例集合D={q,X,Y},策略參數θ,獎勵函數R，序列長度L，相似度閾值ε。

輸出：多樣性序列E。

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

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

步驟3根據式(2)計算獎勵值rt+1=R(st,at)；

步驟4根據式(4)計算at的K個最近鄰動作的相似度s=sim(at,a)。

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

步驟6根據式(1)轉換狀態st至st+1。

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

步驟8重復步驟2～步驟7，直至多樣性序列E長度等于L。

4 實驗結果與分析

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

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

將3個數據集的數據均分為訓練集、驗證集和測試集，大小比例為3∶1∶1。實驗結果均采用五折交叉驗證數據集上各評價指標的平均值。將提出的RLDDR算法與經典的排序學習算法進行比較，包括基于Listwise的ListNet算法、直接優化信息檢索評價指標的MDPRank算法。在多樣性排序領域，選取代表性的多樣性排序算法MMR、xQuAD、MDP-DIV(S-recall)進行對比。

表1和表2分別列出了RLDDR算法和對比算法在NDCG@k評價指標上的對比結果。

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時具有較高NDCG@k值，說明其能夠將最相關文檔排序在排序列表的前方位置。但是，隨著k的增大，由于RLDDR算法的融合多樣性因素原則，裁剪了高度相似文檔致使NDCG@k有所下降。MDPRank算法排序準確性整體優于RLDDR算法。但是，在k取1，3，5時，相較基于Listwise的ListNet算法，本文算法仍具有一定的準確性。由表2可知，在MQ2007數據集上，RLDDR算法在k=1時也取得了較高的NDCG值。在k=3,5,10時，本文算法也獲得了不錯的準確性。在k=10時，基于神經網絡和梯度下降的ListNet算法的排序準確性最好。

本文算法在考慮多樣性因素之外，仍能保證排序準確性的主要原因是在訓練階段，能夠利用獎勵回報作為監督信息，更新策略參數，學習最優的排序策略。RLDDR算法在OHSUMED和MQ2007數據集上均有一定改進，是直接優化信息檢索評價指標的有效算法。

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

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

表3和表4列出了在多樣性排序領域中本文算法和對比算法的多樣性排序評價指標α-NDCG和S-recall的實驗對比結果。

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可知，在提高文檔多樣性方面，本文算法有不錯的表現。本文算法在k=5和k=10時評價指標α-NDCG均高于對比算法。通過裁剪高度相似的文檔，縮小了文檔搜索空間，增強了排序文檔的多樣性。由表4可知，在傳統的多樣性指標S-recall方面,本文算法較對比算法能夠使排序文檔涵蓋更多的子主題，說明文檔的多樣性高于對比算法的，體現了RLDDR算法融合多樣性排序的有效性。

綜上，在排序學習方法中加入多樣性排序因素，排序準確性會有所下降。但是，保證一定程度的搜索結果多樣性也是未來搜索引擎算法調整的趨勢。多樣性排序的優點將彌補準確性稍有下降的缺點，幫助用戶過濾高度相似的文檔，不僅能夠避免返回結果的冗余，還能提高用戶的搜索興趣。

5 結束語

針對現有排序學習算法中損失函數未能充分利用所有排序位置信息，以及確保排序結果多樣性方面能力不足的問題，本文引入強化學習思想，通過計算所有排序位置的獎勵回報，并將其作為評價監督，在每一次迭代過程中進行學習，保證了每個排序位置選擇最優的文檔，提高排序準確性；結合多樣性策略，通過將高度相似的文檔刪除的方式確保排序結果的多樣性。實驗結果表明，RLDDR算法較相關對比算法能獲得更顯著的排序結果。在以后的工作中，將繼續挖掘影響排序性能的因素，得到性能更優的排序模型。