一種基于排序學習方法的查詢擴展技術

徐 博，林鴻飛，林 原，王 健

(大連理工大學，遼寧 大連 116024)

?

一種基于排序學習方法的查詢擴展技術

徐 博，林鴻飛，林 原，王 健

(大連理工大學，遼寧 大連 116024)

查詢擴展作為一門重要的信息檢索技術，是以用戶查詢為基礎，通過一定策略在原始查詢中加入一些相關的擴展詞，從而使得查詢能夠更加準確地描述用戶信息需求。排序學習方法利用機器學習的知識構造排序模型對數據進行排序，是當前機器學習與信息檢索交叉領域的研究熱點。該文嘗試利用偽相關反饋技術，在查詢擴展中引入排序學習算法，從文檔集合中提取與擴展詞相關的特征，訓練針對于擴展詞的排序模型，并利用排序模型對新查詢的擴展詞集合進行重新排序，將排序后的擴展詞根據排序得分賦予相應的權重，加入到原始查詢中進行二次檢索，從而提高信息檢索的準確率。在TREC數據集合上的實驗結果表明，引入排序學習算法有助于提高偽相關反饋的檢索性能。

信息檢索；查詢擴展；偽相關反饋；排序學習

1 引言

查詢擴展是一門重要的信息檢索技術，它能夠利用自然語言處理等多種方法對用戶提交的查詢進行分析和完善，進而提升信息檢索的性能。偽相關反饋技術是當前較為熱門的一種查詢擴展方法，它假設用戶提交查詢進行初次檢索后得到的前N篇文檔與原始查詢是相關的，而在這些文檔中出現頻率較高的詞與原始查詢也更為相關，因此可以從中提取一些高頻詞來對原始查詢進行補充，從而更加準確地理解用戶的信息需求。目前許多基于偽相關反饋的研究都關注于擴展詞的選擇，基于SVM的分類方法被用來對擴展詞的好與壞進行區分[1]，進而選擇更加有用的擴展詞來提升查詢擴展的性能；在冗長查詢中引入回歸方法對查詢詞進行加權[2]，從而提高查詢中關鍵詞的權重，更為清晰地描述查詢意圖；利用改進的馬爾科夫隨機域模型對查詢詞賦予權重[3]，結合詞與詞之間的語言和統計特征對查詢詞進行排序[4]等。這些研究表明，偽相關反饋作為一種局部上下文分析的查詢擴展技術相比于傳統的全局分析方法具有更好的檢索性能，但如何對查詢擴展詞賦予權重關系到檢索性能能否被進一步提升。排序學習[5]是機器學習與信息檢索相結合的研究領域。排序作為信息檢索中的核心問題一直以來備受研究者的關注，而排序學習是借鑒機器學習的方法，通過訓練集訓練排序模型，并將訓練好的模型應用于測試集的排序任務中，從而提高排序的準確率和召回率[6]。從廣義上講，很多問題實際上都可以歸結為排序問題，比如文本檢索、問答系統、文檔摘要、推薦系統等。近年來許多經典的排序學習算法被相繼提出，并被證明能夠很大程度上提升檢索性能，如RankBoost[7]，RankSVM[8-9]等。當前，一些研究致力于在查詢擴展中引入排序方法，比如在查詢日志中挖掘查詢推薦，并對推薦的查詢進行排序[10]；基于查詢會話發現替代查詢，并對替代查詢進行排序[11]等，但很少有研究關注于利用排序方法對偽相關反饋技術進行改進。

本文提出了一種基于排序學習方法的查詢擴展技術，該方法利用排序學習對擴展詞進行排序，從而為擴展詞賦予更加合適的權重，在選取擴展詞的過程中，排序學習方法綜合考慮了擴展詞的多種統計特征，更好地完成了查詢重構。與文獻[12]利用外部資源挖掘擴展詞不同，本文利用偽相關反饋文檔提取擴展詞，并關注于偽相關反饋方法性能的提升，而在實際應用中利用偽相關反饋技術雖然能夠得到理想的擴展詞，但是僅利用偽相關反饋方法的打分為擴展詞賦的權重并不能準確地描述擴展詞與查詢詞的相關程度，于是我們在擴展詞的選擇中引入排序學習方法，相比于只應用單一特征賦予擴展詞權重的傳統偽相關反饋技術，排序學習方法可以在查詢擴展中考慮到更多擴展詞的相關性信息，因而能夠更加充分的描述擴展詞與原始查詢的相關性，從而改善原始偽相關反饋擴展詞加權不夠精準的問題，更好地勝任查詢擴展任務，提高信息檢索的性能。

2 基于排序學習算法的查詢擴展技術

2.1 基于偽相關反饋的查詢擴展詞選擇

在介紹如何將排序學習方法引入查詢擴展之前，我們先簡要介紹一下利用偽相關反饋方法從反饋文檔中提取擴展詞的方法。這里的反饋文檔是指對查詢進行初次檢索后得到的前N篇文檔。我們采用語言模型進行初次檢索，利用查詢擴展中的相關模型[13]，來提取所需的擴展詞。相關模型(Relevance Model)是一種重要的基于語言模型的查詢擴展技術。在擴展詞權重的賦予中，相關模型分別建立了查詢語言模型和文檔語言模型，并通過二者的結合來對反饋文檔中的詞的重要性進行衡量，進而選出相關性得分最高的擴展詞，用于查詢擴展。

表1 擴展詞特征的定義

2.2 擴展詞的相關性標注

在利用相關模型得到擴展詞集合后，我們需要對擴展詞的相關性進行標注。標注的目的是為了利用排序學習方法訓練基于擴展詞的排序模型，進而對擴展詞進行重新排序。擴展詞的相關程度可以通過擴展詞對檢索性能的影響來衡量，本文在詞的相關性標注中，首先將擴展詞加入到原始查詢中進行檢索，然后將檢索結果與原始查詢結果進行比較，來確定擴展詞是否有助于提升檢索性能，進而標注擴展詞的相關性，具體如公式(1)所示。

(1)

本文選擇平均準確率(MAP)對檢索結果進行評價。從公式(1)可以看出，當把擴展詞加入到原始查詢中進行檢索時，若平均準確率相比于原始查詢的平均準確率有所提升，則認為該查詢詞為相關擴展詞并標注為1，否則將該擴展詞標注為0。

2.3 擴展詞特征選取

為了訓練針對于擴展詞的排序模型，我們還需要進一步將擴展詞表示成詞特征向量的形式，即通過不同的特征來建模擴展詞與原始查詢的相關性，進而表征不同的詞與原始查詢的相關程度，以及不同的擴展詞之間的差異程度。本文定義了若干不同的詞特征，它們不僅包含了信息檢索領域傳統的統計信息，比如擴展詞在數據集合中出現的詞頻，文檔頻率等，而且為了能夠更加充分地描述擴展詞的相關程度，我們也在特征選取中采用了擴展詞的共現信息作為詞排序的特征，比如考慮了諸如擴展詞與單一查詢詞的共現次數，擴展詞與多個查詢詞的共現次數等特征。在模型的訓練過程中，每一個擴展詞都被表示成了特征向量的形式。本文所定義的詞特征如表1所示。

在表1中，特征1和特征2分別利用了文檔中的詞頻和文檔頻率信息；特征3利用了擴展詞與單一查詢詞的共現信息；特征4利用了查詢詞對和擴展詞的共現信息，相比于特征3，這個特征包含了更強的語義信息，研究表明這種特征能夠體現擴展詞與整個查詢在語義層面的關系；特征5從另一個角度利用了共現信息，它的含義是若擴展詞與查詢詞在一篇文檔中出現的距離越近，則說明它們的相關程度越大，即把兩個詞在整個數據集中出現在同一篇文檔一定距離內的文檔的總數作為特征，在本文實驗中，分別取5和12作為distance的大小進行特征的提取。

本文所使用的特征都是從實驗數據集合中提取的。實驗數據集采用了TREC提供的Robust2004數據集。在計算特征1和特征2時，我們分別對提取的特征值進行了取對數和除以特征最大值兩種處理，得到了另外四種新的特征。而在數據集文檔中，每一篇文檔都包含了Text，Title，Dateline三個不同數據域，每個數據域對于詞特性的描述能力是不同的，因此我們不僅基于整篇文檔進行了詞特征的抽取，而且還基于每個不同的域也分別進行了詞特征的提取，并把從這四個部分提取的特征分別作為不同的特征應用于詞排序過程中，也就是說針對于每個擴展詞我們分別提取了與上述描述對應的總計36個不同特征。

2.4 排序學習方法

本節主要介紹三種本文使用的排序模型。它們分別是Regression， RankSVM和RankBoost。

Regression是一種傳統的機器學習方法也是最為直接的一種排序學習方法，它能夠直接將排序問題轉化為回歸問題進行處理。在本文的實驗中，回歸方法將每一個詞對應的特征向量作為輸入，輸出該詞的相關性得分。RankSVM是一種重要的排序學習方法。該算法將支持向量機(SVM)引入到了排序問題中，不僅集成了支持向量機的一些優良特性，而且很好地將其轉化到了排序問題中，取得了較好的排序效果。RankBoost是一種重要的排序學習算法，該算法采用機器學習領域的提升方法進行預測模型的訓練，與其他基于提升的方法類似，RankBoost是通過若干次的迭代過程完成模型訓練的，在每一次迭代中該算法選出一個最優的弱學習器作為本輪迭代的分類器對于所有對象進行分類，并根據排序中待排序對象的權重分布和本輪迭代的結果為該弱學習器計算權重，并更新下一輪迭代中待排序對象的權重分布，最終的預測模型為迭代過程中找到的所有弱學習器的線性加權和，最后將該模型用于新對象的排序。

近年來的研究表明，這三種算法在檢索中具有較好的排序性能和較高的效率，所以本文將它們引入偽相關反饋中，對查詢擴展過程進行改進，即對擴展詞集合中的擴展詞進行重新排序和重新加權。

2.5 基于排序學習算法的查詢擴展流程

本節主要介紹本文如何將排序學習算法用于查詢擴展的擴展詞排序。圖1給出了基于排序學習方法的查詢擴展架構的流程。如圖所示，首先我們利用語言模型進行初次檢索，選擇初次檢索的前N篇文檔作為擴展詞的來源，接下來采用相關模型選擇一組高頻詞作為擴展詞，然后對詞的相關性進行標注，并把擴展詞表示成特征向量的形式，然后利用排序學習方法對提取的擴展詞進行重新排序，并根據排序模型賦予的得分對每個擴展詞賦予不同的權重，將重新加權后的擴展詞加入到原始查詢中形成擴展后的新查詢，最后對擴展后的新查詢進行檢索。

圖1 查詢擴展流程

3 實驗

3.1 實驗數據集

本文實驗采用了TREC的英文語料集合Robust2004以及相對應的查詢文檔和相關性標準評估文檔，它是2003年TREC Robust檢索任務所使用的數據集。實驗中，我們將全部150個的查詢分成三部分，分別為訓練集、驗證集和測試集，用于對排序模型的訓練，對算法參數的選擇和對測試數據的預測。檢索時，我們只使用了查詢的Title部分作為初始查詢。在索引的創建過程中，我們使用Porter算法分別對語料和查詢進行詞干化處理，并且根據停用詞列表為數據集和查詢去停用詞，此外，分別為每一篇文檔的Title部分、Text部分、Dateline部分創建了不同域，用于針對于不同的域的統計特征的提取。

3.2 實驗設計

本文采用Robust2004作為實驗語料。用于比較的基準方法為基于語言模型[14]的初次檢索和基于相關模型的偽相關反饋檢索。實驗針對于三種排序學習方法Regression, RankSVM和 RankBoost進行了詞排序模型的訓練，并將訓練后的詞排序模型用于擴展詞的加權。

本文實驗采用了Indri檢索系統作為基礎的檢索環境，在實驗中，對原始語料建立索引，對于查詢集合中的每一個查詢，首先進行初次檢索，在檢索得到的前N篇文檔中，利用偽相關反饋技術提取出現頻率較高的前k個擴展詞作為擴展詞集合。針對于每一個擴展詞用前文中提到的特征提取方法，對擴展詞進行相關性標注，然后將所有擴展詞表示成特征向量的形式。之后按照8∶1∶1的比例將特征文件劃分為訓練集、驗證集和測試集，采用十折交叉驗證實驗進行模型的訓練，最后將訓練完的模型用于對測試集中與同一查詢相關的擴展詞的排序，并將重新加權后的擴展詞列表加入到原始查詢中進行二次檢索。其中，根據TREC比賽的最佳參數，我們設置相關參數：N=10，k=50。此外在將擴展詞加入到原始查詢中時，將擴展詞集合與原始查詢的比重分別設置為0.2和0.8。

3.3 實驗結果和分析

本文分別采用了信息檢索領域廣泛采用的MAP、P@k和NDCG@k 三種評價指標對于實驗結果進行評價。在后文的圖和表中，QL表示直接用原始查詢進行初次檢索時的結果，RM表示用基于相關模型的偽相關反饋進行檢索時的結果，RankBoost，RankSVM，Regression分別表示利用這三種算法對偽相關反饋得到的擴展詞進行重排序后檢索的結果。表2列出了上述幾種算法進行檢索結果評價時，當k=3,5,10時的P@k和NDCG@k評價結果以及MAP的評價結果。為了使結果對比更為清晰，我們用圖2和圖3分別對上述不同算法的實驗結果在P@k和NDCG@k上當k值變化時的評價指標進行了對比。圖中縱坐標為評價函數的分值，橫坐標為處于不同位置的評價指標函數。

通過對比多種方法的實驗結果可以看出，相比于基于語言模型的初次檢索，原始偽相關反饋在各種評價指標上都有所提升；而基于排序學習的方法通過對擴展詞的權重進行重新計算，使得檢索性能進一步提升。從表2可以看出，將回歸算法引入到詞排序中后的檢索性能與原始偽相關反饋的性能相似，只在P@k評價指標上略好于后者，而在其他指標上不如后者，也就是說將回歸算法用于擴展詞的重新排序并不能對檢索性能產生較大提升；而將RankSVM算法引入到詞排序中相比于回歸方法的檢索性能有了較大提升，僅在個別評價指標上略差于偽相關反饋，并且平均準確率也獲得了一定的提升；基于RankBoost的查詢擴展相比于原始偽相關反饋在多種評價指標上都有了較大幅度的提升。因此我們認為基于排序學習的查詢擴展技術對于擴展詞的重新排序更為準確，相比于原始偽相關反饋在整體上具有更好的檢索性能，而RankBoost算法對檢索性能的提升更為顯著。

表2 檢索結果的評價比較

從圖2和圖3中我們可以看到類似的趨勢。基于原始偽相關反饋和基于回歸方法的詞排序算法，二者有較為相似的檢索性能；而將RankSVM和Regression兩種算法引入到詞排序過程的查詢擴展在P@k和NDCG@k評價時的趨勢較為相近，而基于RankBoost的查詢擴展在多組評價指標上體現出了更大的優勢。這一定程度上是由于Regression在排序過程中只考慮了每個擴展詞的絕對分數，而忽略了擴展詞之間的相關性，因此對于擴展詞重排序的結果不太理想；而RankSVM和RankBoost二者相比，前者是基于分類的SVM算法，后者是基于提升算法，通過實驗結果的評價指標可以看出，基于

圖2 NDCG@k評價結果的比較

圖3 P@k評價結果的比較

提升算法的RankBoost算法在查詢擴展的詞排序選擇階段具有更大的優勢，所以我們認為選用了RankBoost算法對擴展詞進行重排序對檢索性能產生了更大的幫助。

我們之所以將排序算法引入偽相關反饋進行查詢擴展，是由于原始偽相關反饋對于擴展詞權重的分配只考慮了偽相關反饋方法賦予擴展詞的分數，而偽相關反饋在給擴展詞加權的過程中僅僅考慮了擴展詞的詞頻、文檔頻率等較少的特征，因而擴展詞的權重并不是最合適的，而在引入了排序學習算法后，在對于擴展詞的權重計算時，考慮到了更多關于擴展詞的統計特征，因而更好地完成了查詢的重構，取得了更高的檢索性能；而RankBoost排序學習算法采用了機器學習中的提升方法，提升方法可以在模型的訓練過程中，根據模型對于訓練數據的訓練結果，不斷地構造弱學習器對于訓練結果進行提升，最終得到的模型是多輪迭代后的弱學習器的集合，因此能夠更好地勝任擴展詞排序的任務。

4 結論與展望

本文提出了一種基于排序學習方法的查詢擴展技術。相比于傳統的偽相關反饋技術，本文提出的方法獲得了更好的檢索性能，它首先對偽相關文檔中提取的擴展詞進行了相關性標注，把擴展詞表示成了特征向量的形式，然后利用排序學習算法對所有的擴展詞進行排序，并在此基礎上根據擴展詞的排序得分賦予不同擴展詞不同的權重，權重表明了擴展詞與原始查詢的相關程度，在此基礎上完成了查詢的重構，既提升了偽相關反饋方法對于擴展詞加權的精準度，又進一步提升了檢索的性能。在TREC數據集上的實驗結果表明將排序學習方法引入到查詢擴展中確實有助于擴展詞相關性的判斷，改善偽相關反饋過程中擴展詞權重不夠準確的問題，而RankBoost算法在詞排序中更為有效，對檢索性能產生了較大的提升。本文提出的利用排序學習方法對于查詢擴展進行改進的思路具有較好的推廣性。未來的工作可以從以下幾個方面繼續進行，一方面可以嘗試使用其他的排序學習方法對擴展詞排序進行改進，另一方面可以在排序過程中，引入更為適合的統計特征，來表征不同查詢詞的重要程度，從而進一步提升檢索性能。

[1] G Cao, J Y Nie, S Robertson. Selecting good expansion terms for pseudo-relevance feedback[C]//Proceedings of the 31st Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, Singapore, 2008: 243-250.

[2] L Matthew, A James, C Bruce. Regression Rank: Learning to Meet the Opportunity of Descriptive Queries[C]//Proceedings of the 32th European Conference on IR Research, Toulouse, France, 2009: 90-101.

[3] L Matthew. An Improved Markov Random Field Model for Supporting Verbose Queries[C]//Proceedings of SIGIR2009, American, 2009: 476-483.

[4] C J Lee, R C Chen, S H Kao and P J Cheng. A Term Dependency-Based Approach for Query Terms Ranking[C]//Proceedings of the 18th ACM Conference on Information and Knowledge Management, Hong Kong, China, 2009: 1267-1276.

[5] T Y Liu. Learning to Rank for Information Retrieval [J]. Foundations and Trends in Information Retrieval, 2009, 3(3): 225-331.

[6] T Qin, T Y Liu, J Xu, et al. LETOR: Benchmark Collection for Research on Learning to Rank for Information Retrieval[C]//Proceedings of SIGIR 2007 Workshop on Learning to Rank for Information Retrieval (LR4IR 2007), Amsterdam, The Netherlands, 2007: 3-10.

[7] Y Freund, R D Iyer, R E Schapire, et al. An Efficient Boosting Algorithm for Combining Preferences[J]. Journal of Machine Learning Research, 2003, 4:933-969.

[8] Y Cao, J Xu, T Liu, et al. Adapting ranking SVM to document retrieval[C]//Proceedings of SIGIR2006, Seattle, WA, USA, 2006:186-193.

[9] T Joachims. Optimizing search engines using clickthrough data[C]//Proceedings of the 8th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Edmonton, Alberta, Canada, 2002: 133-142.

[10] U Ozertem, O Chapelle, P Donmez, et al. Learning to suggest: a machine learning framework for ranking query suggestions[C]//Proceedings of SIGIR2012, Portland, OR, USA, 2012: 25-34.

[11] R Jones, B Rey, O Madani, et al. Generating query substitutions[C]//Proceedings of WWW2006, Edinburgh, Scotland, UK, 2006: 387-396.

[12] Y Lin, H Lin, S Jin, et al. Social Annotation in Query Expansion: a Machine Learning Approach[C]//Proceedings of SIGIR2011, Beijing, China, 2011: 405-414.

[13] V Lavrenko, W B Croft. Relevance based language models[C]//Proceedings of SIGIR2001. New Orleans, Louisiana, 2001: 186-193

[14] J Ponte, W Croft. A language modeling approach to information retrieval[C]//Proceedings of SIGIR1998, Melbourne, Australia, 1998: 275-281.

A Query Expansion Method Based on Learning to Rank

XU Bo, LIN Hongfei, LIN Yuan, WANG Jian

(Dalian University of Technology, Dalian， Liaoning 116024, China)

Query Expansion is an important technique for improving retrieval performance. It uses some strategies to add some relevant terms to the original query submitted by the user, which could express the user’s information need more exactly and completely. Learning to rank is a hot machine learning issue addressed in in information retrieval, seeking to automatically construct ranking models determining the relevance degrees between objects. This paper attempts to improve pseudo-relevance feedback by introducing learning to rank algorithm to re-rank expansion terms. Some term features are obtained from the original query terms and the expansion terms, learning from which we can get a new ranking list of expansion terms. Adding the expansion terms list to the original query, we can acquire more relevant documents and improve the rate of accuracy. Experimental results on the TREC dataset shows that incorporating ranking algorithms in query expansion can lead to better retrieval performance.

information retrieval; query expansion; pseudo-relevance feedback; learning to rank

徐博(1988—)，博士研究生，主要研究領域為搜索引擎、機器學習、排序學習。E?mail：xubo2011@mail．dlut．edu．cn林鴻飛(1962—)，博士，教授，博士生導師，主要研究領域為搜索引擎、文本挖掘、情感計算和自然語言理解。E?mail：hflin@dlut．edu．cn林原(1983—)，博士，講師，主要研究領域為搜索引擎、機器學習，排序學習。E?mail：zhlin@dlut．edu．cn

1003-0077(2015)03-0155-07

2013-04-08 定稿日期： 2013-07-31

國家自然科學基金(61277370、61402075)；國家863高科技計劃(2006AA01Z151)；遼寧省自然科學基金(201202031、2014020003)、教育部留學回國人員科研啟動基金和高等學校博士學科點專項科研基金(20090041110002)；中央高校基本科研業務費專項資金。

TP391

A