基于檢索結果排序的偽相關反饋

閆蓉　高光來

摘要：針對傳統偽相關反饋（PRF）算法擴展源質量不高使得檢索效果不佳的問題，提出一種基于檢索結果的排序模型（REM）。首先，該模型從初檢結果中選擇排名靠前的文檔作為偽相關文檔集；然后，以用戶查詢意圖與偽相關文檔集中各文檔的相關度最大化、并且各文檔之間相似性最小化作為排序原則，將偽相關文檔集中各文檔進行重排序；最后，將排序后排名靠前的文檔作為擴展源進行二次反饋。實驗結果表明，與兩種傳統偽反饋方法相比，該排序模型能獲得與用戶查詢意圖相關的反饋文檔，可有效地提高檢索效果。

關鍵詞：偽相關反饋；潛在狄里克雷分配；主題模型；查詢擴展

中圖分類號：TP391.3

文獻標志碼：A

0引言

隨著Web的普及，越來越多的用戶希望從互聯網上獲取信息。對于目前主流的基于關鍵詞的搜索方式，用戶必須通過構造有限的查詢詞來表達信息需求（information need）。Carpineto等[1]在查詢擴展綜述中明確指出，大多數用戶喜歡構造短查詢交給搜索引擎，且構造的查詢詞多以1～3個詞居多；并且用戶的查詢構造本身就是一個抽象的過程，查詢構造結果具有模糊性、不確定性和描述的多樣性。在這種情況下，由于缺乏上下文語境，搜索引擎很難完全理解用戶的查詢意圖，返回的結果中經常會包含大量無關或相似的文檔。特別是當查詢詞出現歧義時，返回的文檔集會偏向于某一個主題，而該主題往往并不是用戶潛在查詢意圖[2]。如果搜索引擎能夠將與用戶初始查詢構造相關的信息全部返回給用戶，那么，用戶就可以在多個不同查詢結果中找到自己最想要的結果。文獻[3]的研究表明，提高用戶體驗較好的辦法就是給用戶提供盡可能多的不同信息，而這些信息中至少會有一個是與用戶需求相關的。

查詢擴展可以有效地解決用戶表達問題。其基本思想是利用與關鍵詞相關的詞語對用戶原始查詢進行修正，彌補用戶初始查詢信息的不足，提高查全率。偽相關反饋（Pseudo Relevance Feedback，PRF）作為一種有效的自動查詢擴展方法[4-6]，其假設初檢查詢結果集中排名靠前的k個文檔是與用戶查詢相關的，記為偽相關文檔集，并從中抽取擴展詞進行查詢擴展。該方法的查詢效果主要受制于選取的前k個文檔的數目及質量[7-8]，在其質量偏低的情況下，容易產生“查詢主題偏移”現象。提升前k個相關文檔的質量可以有效避免這種現象，形成真正與用戶查詢需求相關的偽相關文檔集合。通常，改善偽反饋文檔質量包括調整[9-11]和聚類[12]兩種方法。其中，調整的方法包括對查詢結果重排序和過濾兩種方式：重排序的方法通過給查詢結果集中各文檔賦予不同的值來進行排序，通過構造算子[9]或是加權[10]完成；過濾的方法[11]主要通過給查詢結果集中各文檔添加若干特征，突顯相關文檔，提高相關文檔的排名，從而達到過濾的目的。

以上這些偽相關反饋方法關注的重點仍是用戶查詢詞的表象形式，而不是用戶的內在實際信息需求，得到的偽相關文檔中往往有很多是非常相似的，造成查詢結果冗余的增加，不能很好地體現用戶不同層面的查詢需求[8]。本文研究認為，用戶的查詢需求并不是單一的，而是多層面和多角度的，要實現自動的查詢擴展，就要求偽相關文檔中的各文檔內容既保證與用戶原查詢相關，又要保證其與用戶多層面需求的一一映射關系，從而降低查詢主題偏移的風險，進而獲取與用戶查詢盡可能相關的信息來進行偽反饋。有鑒于此，本文提出一種提高偽反饋文檔質量的排序模型REM（REorder Model）。該模型從文檔隱含語義角度出發，通過對初檢查詢結果集中各文檔進行重調序的方式，提高與用戶查詢主題相關文檔的位序，確保二次反饋擴展源的質量，進而提高檢索效果。

1基于檢索結果排序的PRF模型

偽反饋文檔質量不高實質上是由于搜索引擎對于用戶查詢理解不充分造成的，而要讓搜索引擎完成這種充分理解是不大可能的。那么，如果能夠將用戶查詢本身所有相關內容都盡可能地覆蓋到，這樣就可以在偽相關文檔中減少不相關文檔的數量，從而提高查詢準確率。為了確保偽相關文檔中各文檔滿足用戶查詢覆蓋度的要求，本文提出一個排序模型REM。該模型將初檢查詢結果文檔集中的各文檔依據滿足用戶查詢意圖相關度程度進行重新排序，選擇排名靠前的top-k個文檔來構造二次反饋的擴展源集合。

1.1排序原則

Carbonell等[13]提出的最大邊緣相關算法（Maximal Marginal Relevance， MMR）是用來解決查詢結果多樣化問題的一種方法。該算法分別對各文檔與用戶查詢間的相關度和文本之間的相關度進行度量，所謂的邊緣相關即為二者的線性組合。按照各文檔的邊緣相關最大化作為排序依據，提升在已有查詢結果中與查詢相關性盡量大、且與先前被選擇的文檔間相似性盡量小的文檔的排名次序，完成對各文檔的重定序。

本文的排序策略與MMR很類似，區別在于：本文認為初檢查詢結果集中的各文檔還應當依據其與用戶查詢意圖相關度高低來進行排序，并從排序結果中構造偽相關文檔集。這就要求構造的REM排序模型，一方面要保證偽相關文檔集中各文檔與用戶各層次查詢需求的一一映射關系，另一方面要保證其中的文檔間的相似度最小。本文假定初檢查詢結果各文檔相關主題的語義集合涵蓋了用戶的查詢需求。由此，構造REM模型的排序準則如下：排序結果集中的各文檔要滿足用戶各層次查詢需求，即需求覆蓋度的最大化；同時還應保證各文檔之間盡可能的不相似，即冗余度的最小化。

2文本相似度計算

式（2）中列出了兩個相似度計算，它們是構造本文排序模型的關鍵。對于文本間相似度的計算方法大部分以基于向量空間模型[14]為主。該方法通過構造詞典空間，將文本在詞典空間表示為詞向量的方式進行建模。但在真實數據集中構造的詞典空間存在維度過高和數據稀疏的問題，而且在建模過程中未考慮文本中各詞項的語義特征。在本文的排序模型中，目的是讓偽相關反饋集中的各文檔盡量滿足用戶各層面的信息需求，那么，在相似度計算中，應該選取一種更合適的，能考慮文本中各詞項語義特征的文本表示方法。近年來，主題模型——潛在狄利克雷分配（Latent Dirichlet Allocation， LDA）[15]被研究應用在文本相似度計算[16]中。LDA通過引入隱含主題（latent topic）概念，在主題空間（topic space）中用有限主題數目將文檔表示成低維的文檔主題向量，并且考慮了文本的語義特征，通過構造“詞匯主題文檔”模式來提取大規模數據集中潛在的主題（語義）信息。基于此，本文選用LDA主題模型抽象表示文本，用于計算文本間語義相似度。

信息檢索本身對于詞匯的精確度要求高。但是，LDA在建模過程中抽象的主要對象是整個數據集，對應用LDA模型生成的文本來說，文本被表示成所有主題的特定比例的混合。如果依此方式對用短文本構造的用戶查詢直接進行LDA建模，會由于數據稀疏的原因，使得這種文本表示結果不合適[17]，勢必會造成檢索性能較差。所以本文在實驗過程中，僅對進行Sim2（di， dj）計算的兩個文本進行LDA建模，而對Sim1（di， Q）相似度計算，本文將直接利用經典的BM25[18]檢索結果。對于LDA建模后的兩個文本，本文使用JS（Jensen-Shannon）距離[19]計算文本相似度，如式（4）所示：

3實驗設置及評價

3.1實驗設置

3.1.1索引建立

本文使用lemur（http：//www.lemurproject.org）工具建立文檔索引和查詢。實驗數據集包括文檔集和查詢集，其中：文檔集包括簡體中文Xinhua（2002—2005）四年的新聞文檔，共308845個文檔；查詢集包括簡體中文ACLIA2-CS（0001 ～0100），共100個查詢。由于數據集為中文數據，所以在進行檢索和查詢前，首先對文檔集和查詢集都進行了預處理，包括分詞（采用的是中國科學院計算技術研究所的ICTCLAS）和去除停用詞。

3.1.2LDA建模

在進行LDA建模前，為了降低少數低頻詞對文本建模結果的影響，對實驗文檔集作了進一步的預處理：去除部分虛詞、形容詞、副詞等意義不大的詞；刪除文檔集中出現頻度小于5的詞匯。最后對剩余的65082429個詞項進行LDA主題建模。LDA建模的參數估計利用MCMC（Markov Chain Monte Carlo）方法中的Gibbs抽樣[20]算法。初始設置主題個數M=10， α=50/M， β=0.01，Gibbs抽樣的迭代次數為100。

LDA建模過程中主題數目M的設置非常關鍵，主要是因為主題數目與數據集密切相關。用LDA對數據建模后，數據會通過主題進行高度抽象和壓縮，主題數目的設置應當以數據為根本，因為不同的主題數目會導致每個主題詞項分布結果的不一樣，直接影響文本的語義表達。所以對于不同的數據集，主題數目M的取值是不固定的。困惑度（Perplexity）[21]可以用來評價主題模型的生成性能，本文采用該方法作為評價指標來確定最佳主題數目M。一般地，困惑度取值越低，就表示模型更能發現數據中深層次的語義結構，模型的推廣性就越好。困惑度的計算如式（6）所示：

本文實驗中，依次取主題個數M=10，20，…，100，分別對LDA建模，分析困惑度的變化。實驗結果如圖2所示。從圖2可以看出，當M=60，模型困惑度達到最小峰值，此時模型的生成性能最佳。因此，實驗中選取主題數目M=60。

3.2實驗評測標準和結果分析

初檢的相關度排序方法選用的是典型的一元語言模型（Language Model， LM）方法，采用Dirichlet平滑方法，設置值為1000。LM是基于詞項空間的統計結果來對用戶查詢和文檔的相關度進行計算的，并沒有考慮詞語所表達的語義信息。選取其結果作為初檢結果的目的，是為了驗證引入表達語義信息的文本表示方法后，從淺層語義的角度是否可以通過文檔位序的調整來達到提升擴展源質量的目的。因為大多數用戶在檢索過程中主要關注排名靠前的結果，實驗結果應該考察其是否符合大多數檢索用戶的習慣，所以實驗中主要從查詢準確率方面進行評價，分別采用前n個結果的查準率Precision@n（簡記為P@n）和平均查準率 （Mean Average Precision， MAP）來衡量。

實驗中初檢查詢結果文檔個數設定為K=50，并設置統一從排名前10個文檔（即k=10）中抽取擴展詞。文獻[22]研究表明，擴展詞個數的數目設定為10～20時，檢索效果最好，所以實驗中設置feedbackTermCount=20進行偽反饋。Baseline選取標準的BM25[18]偽反饋。REM算法中關于參數λ取值，本文采用貪心策略，當λ取0.7時，檢索效果最好。為了有效驗證REM方法，本文還和TF-IDF（Term Frequency-Inverse Document Frequency）偽反饋方法進行了比較。實驗結果如表1所示。

從表1的結果可以看到，REM方法比Baseline（BM25）和TF-IDF偽反饋方法在MAP和P@5指標上有了明顯的提高，說明REM方法對于提高檢索效果是有效的；但在指標P@10上的結果略有下降，該結果其實正體現了本文的核心思想，即實際應用中對于搜索引擎提供的查詢結果，應該做到查詢的多樣性與查詢內容的相關性及有用性的折中。

為了進一步驗證本文提出方法的有效性，將REM方法結果與直接對初檢結果利用MMR算法進行調序的結果（VSM_PRF）進行了比較。在VSM_PRF方法中，文檔采用向量空間模型文本表示方法，并基于Cosine系數計算文檔間相似度。這樣做，還可以比較兩種不同文本表示方法對于檢索效果的影響。另外，本文同時還與初始結果直接進行偽反饋的結果（LM_PRF）進行了比較。結果如表2所示。

從表2結果可以看出，在各項評測指標上，VSM_PRF和REM均明顯高于LM_PRF檢索結果，說明從文本語義角度出發對初檢結果進行重排序的方法是切實可行的。另外，對MMR結果進一步改進，可以達到更好的檢索效果，REM方法在MAP指標上比VSM_PRF高出6.4%，表明引入主題空間的統計信息，可以更有效地改善詞項空間的統計結果；但二者在P@5和P@10指標上相差無幾，主要是由于本文提出的算法對于文本的主題建模精度要求高所造成的。

4結語

主流的關鍵詞查詢表達多樣性使得傳統的查詢擴展會發生“查詢主題偏移”問題，為此提出一種新的偽相關反饋方法，通過引入排序模型REM對初檢結果文檔集中各文檔進行重排序，從而獲取高質量偽相關文檔，減小查詢主題偏移的風險。實驗結果驗證了本文提出方法的有效性。與傳統的偽反饋方法比較而言，本文提出的REM模型更有助于提高查詢效果；而且實驗結果還表明，在重排序過程中，與基于詞匯級別上的文本建模方式相比，基于主題級別上的文本建模方式能夠獲取更多的語義信息，有助于提升偽相關文檔的質量，改善檢索效果。

本文將淺層語義應用于文本相似度計算中，并對將其用于解決實際的檢索問題進行了初步嘗試。但在實際的檢索實現中，需要用戶的參與或分析和挖掘用戶檢索行為來獲取與用戶查詢真相關的RR集合，這是一件很困難的事情。所以進一步的工作重點在于，在對大規模文本數據集進行主題建模基礎上，有效利用隱藏在偽反饋文檔中的主題信息，進而提取與用戶查詢相關的語義信息，以達到用淺層語義指導檢索過程的目的。

參考文獻：

[1]CARPINETO C， ROMANO G. A survey of automatic query expansion in information retrieval [J]. ACM Computing Surveys， 2012， 44（1）： Article No. 1.

[2]VARGAS S， SANTOS R L T， MACDONALD C， et al. Selecting effective expansion terms for diversity [C]// OAIR2013： Proceedings of the 10th Conference on Open Research Areas in Information Retrieval. Paris： Le Centre de Hautes Etudes Internationales DInformatique Documentaire， 2013： 69-76.

【只有法文名稱LE CENTRE DE HAUTES ETUDES INTERNATIONALES DINFORMATIQUE DOCUMENTAIRE】

http：//dblp.uni-trier.de/rec/bibtex/conf/riao/EmbarekF10，該頁面上縮寫用的是

publisher = {{CID} - Le Centre de Hautes Etudes Internationales D'Informatique Documentaire}，

[3]TEEVAN J， DUMAIS S T， HORVITZ E. Characterizing the value of personalizing search [C]// SIGIR2007： Proceedings of the 30th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. New York： ACM， 2007： 757-758.

[4]COLLINS-THOMPSOM K. Reducing the risk of query expansion via robust constrained optimization [C]// CIKM2009： Proceedings of the 18th ACM Conference on Information and Knowledge Management. New York： ACM， 2009： 837-846.

[5]RAMAN K， UDUPA R， BHATTACHARYA P， et al. On improving pseudo-relevance feedback using pseudo-irrelevant documents [C]// ECIR 2010： Proceedings of the 32nd European Conference on IR Research， LNCS 5993. Berlin： Springer-Verlag， 2010： 573-576.

[6]ZHAI C， LAFFERTY J. Model-based feedback in the language modeling approach to information retrieval [C]// CIKM2001： Proceedings of the 10th International Conference on Information and Knowledge Management. New York： ACM， 2001： 403-410.

[7]HUANG Q， SONG D， RüGER S. Robust query-specific pseudo feedback document selection for query expansion [C]// ECIR 2008： Proceedings of the 30th European Conference on IR Research， LNCS 4956. Berlin： Springer-Verlag， 2008： 547-554.

[8]HE B， OUNIS I. Studying query expansion effectiveness [C]// ECIR 2009： Proceedings of the 31th European Conference on IR Research， LNCS 5478. Berlin： Springer-Verlag， 2009： 611-619.

[9]MITRA M， SINGHAL A， BUCKLEY C. Improving automatic query expansion [C]// SIGIR1998： Proceedings of the 21st Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. New York： ACM， 1998： 206-214.

[10]AMO P， FERRERAS F L， CRUZ F， et al. Smoothing functions for automatic relevance feedback in information retrieval [C]// DEXA 2000： Proceedings of the 11th International Workshop on Database and Expert Systems Applications. Washington， DC： IEEE Computer Society， 2000： 115-119.

[11]葉正.基于網絡挖掘與機器學習技術的相關反饋研究[D].大連：大連理工大學， 2011： 51-55. （YE Z. The research of machine learning techniques and external Web resources for relevance feedback [D]. Dalian： Dalian University of Technology， 2011： 51-55.

[12]PU Q， HE D. Pseudo relevance feedback using semantic clustering in retrieval language model [C]// CIKM2009： Proceedings of the 18th ACM Conference on Information and Knowledge Management. New York： ACM， 2009： 1931-1934.

[13]CARBONELL J， GOLDSTEIN J. The use of MMR， diversity-based reranking for reordering documents and producing summaries [C]// SIGIR 1998： Proceedings of the 21st Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. New York： ACM， 1998： 335-336.

[14]SALTON G， WONG A， YANG C S. A vector space model for automatic indexing [J]. Communications of the ACM， 1975， 18（11）： 613-620.

[15]BLEI D M， NG A Y， JORDAN M I. Latent Dirichlet allocation[J]. Journal of Machine Learning Research， 2003， 3： 993-1022.

[16]ZHOU D， DING Y， YOU Q， et al. Learning to rank documents using similarity information between objects [C]// ICONIP 2011： Proceedings of the 18th International Conference on Neural Information Processing， LNCS 7063. Berlin： Springer-Verlag， 2011： 374-381.

[17]HONG L， DAVISON B D. Empirical study of topic modeling in twitter [C]// SOMA 10： Proceedings of the First Workshop on Social Media Analytics. New York： ACM， 2010： 80-88.

[18]JONES K S， WALKER S， ROBERTSON S E. A probabilistic model of information retrieval： development and comparative experiments： Part 1 [J]. Information Processing & Management， 2000， 36（6）： 779-808.

[19]LIN J. Divergence measures based on Shannon entropy[J]. IEEE Transactions on Information Theory， 1991， 37（14）：145-151.

[20]GRIFFITHS T L， STEYVERS M. Finding scientific topics [J]. Proceedings of the National Academy of Sciences of the United States of America， 2004， 101（Supp 1）： 5228-5235.

[21]BLEI D B， LAFFERTY J D. Correlated topic models [C]// NIPS 2005： Advances in Neural Information Processing Systems 18. Cambridge， MA： MIT Press， 2005， 18： 147-155.

[22]OGILVIE P， VOORHEES E， CALLAN J. On the number of terms used in automatic query expansion [J]. Information Retrieval， 2009， 12（6）： 666-679.