張忠敏 吳勝利

摘? 要：對支持檢索結果多樣化任務的查詢性能預測進行了研究。分析了現(xiàn)有性能預測算法的不足，考慮利用不同方式衡量最終檢索結果列表的多樣性，并在此基礎上提出同時考察查詢結果的相關性性能與多樣性性能的三種方法。采用TREC ClueWeb09B數(shù)據(jù)集、Web Track任務的查詢集及開源的Indri搜索引擎構建實驗平臺并進行實驗?；赟pearman、Pearson和Kendall相關系數(shù)的評價結果表明，所提出的三種方法與傳統(tǒng)方法相比更適用于預測多樣化檢索結果，且在不同條件下性能穩(wěn)定。

關鍵詞：信息檢索;查詢性能預測;檢索結果多樣化

中圖分類號：TP391.3? ? ?文獻標識碼：A

Query Performance Prediction for Search Result?Diversification in Information Retrieval

ZHANG Zhongmin，WU Shengli

（Jiangsu University，Zhenjiang 212013，China）

Abstract：Query performance prediction in supporting of the task of retrieval results diversification is studied.This paper analyses the shortcomings of the existing performance prediction algorithms，considers using different ways to measure the diversity of the final search results list，and proposes three methods to simultaneously examine the relevance and diversity performance of the query results.TREC's ClueWeb09B dataset and query sets for the Web Track Task，and open sourced search engine Indri are used to build the experimental platform and carry out experiments.Measured by using Spearman，Pearson and Kendall correlation coefficients，the evaluation results show that the three proposed methods are more suitable for predicting diversified retrieval results than traditional methods，and have stable performance under different conditions.

Keywords：information retrieval;query performance prediction;search result diversification

1? ?引言（Introduction）

查詢性能預測，也稱為查詢困難度預測，是指在沒有相關性判斷信息的情況下，評估給定查詢對應檢索結果的性能[1-4]。查詢性能預測技術可以輔助搜索引擎向用戶提供更穩(wěn)定的服務。從搜索引擎的角度講，搜索引擎的管理員可以收集查詢性能預測技術產生的信息，識別出當下用戶檢索頻率高但性能較差的一類查詢，增加相應的文檔數(shù)量來提高該類查詢的檢索性能，從整體上提高搜索引擎的魯棒性（Robust）[1]。從用戶的角度講，當用戶把檢索信息需求轉化為查詢時，存在信息丟失或輸入的關鍵詞不夠具體等問題。此時查詢性能預測技術可以迅速識別這些問題，借由與用戶的交互輔助用戶構建意義更明確的查詢，提高檢索有效性。

傳統(tǒng)意義上查詢性能預測指的是查詢的相關性性能預測。目前依然是信息檢索和WEB搜索領域的一項重要任務，已有多篇論文[1，3，5-7]對其進行了深入研究。根據(jù)是否分析查詢的檢索結果，通常將查詢性能預測方法分為檢索前（pre-retrieval）預測方法[5，8]和檢索后（post-retrieval）預測方法[1，4，6，9]。

對于給定查詢，檢索前預測方法指在搜索引擎產生檢索結果前評估查詢的性能。此時可分析的信息主要有查詢詞項在文檔集中的統(tǒng)計特征（例如倒轉文檔頻率IDF）、查詢短語的語言特征[10]等。雖然可以在檢索開始前預測查詢的性能，計算代價小且速度快，但是由于沒有分析檢索模型方面的特性，因而預測的有效性不高。檢索后預測方法是指在搜索引擎產生檢索結果后評估查詢的性能。此時預測方法不僅能使用查詢詞項在文檔集中的統(tǒng)計信息和查詢自身的語言特征，還可以使用搜索引擎反饋的文檔列表信息[11，12]，例如查詢詞項在返回文檔集中的分布、返回文檔之間的關系等。由于查詢對應的返回文檔集包含與檢索模型算法相關的信息，檢索后預測方法可分析的數(shù)據(jù)因此更多且更可靠，從而預測更加準確有效。檢索后預測方法又可以大致分為三類：基于結果列表相對于整個數(shù)據(jù)集的清晰度（Clarity）[13]，基于檢索結果的穩(wěn)定性程度（Robustness）[14]，和分析結果列表中文檔的得分分布[6，15]。

分析得分分布的預測算法在傳統(tǒng)預測任務上結果較優(yōu)。SD2[15]方法基于結果列表中文檔得分的標準方差，并且根據(jù)第一篇文檔的得分設定最低得分閾值來選擇截斷系數(shù)k，即截取的文檔列表長度。Zhou等[16]提出了一種預測方法WIG （Weighted Information Gain），該方法分析檢索結果中前k篇文檔的平均得分和整個文檔集的平均文檔得分的差值。若差值越大，說明前k篇文檔的整體得分越高，即檢索結果越有效。Shtok等[17]提出了另一種預測方法NQC（Normalized Query Commitment），該方法分析了檢索文檔列表中靠前和靠后文檔的查詢漂移程度。若檢索結果中文檔得分的梯度越明顯，則說明搜索引擎能更好地把握每篇文檔與查詢的相關度。也就是說漂移程度越小，檢索結果的質量越高。Tao和Wu[6]提出了一種SMV（Score Magnitude and Variance）預測方法，該方法同時考慮了檢索結果中文檔分數(shù)的大小和方差。

檢索結果多樣化是信息檢索領域中一項重要的任務，對于一些語義寬泛，解釋多樣的查詢尤為必要。一般它由兩個步驟實現(xiàn)。第一步采用傳統(tǒng)的搜索引擎進行搜索，得到一初始的結果列表。在這一步只考慮文檔的相關性。第二步對第一步的結果列表進行重排，這時既要考慮相關性，也要考慮多樣性。第二步重排的過程本質上是一個雙目標的優(yōu)化問題。一方面需要檢索與查詢相關的結果，另一方面也要盡可能地覆蓋查詢的多個方面。事實上，若將查詢q看成由一組子意圖A組成，并且初始結果列表R中每篇文檔d包含的子意圖是A的一個子集，那么問題變成對于給定的文檔數(shù)找到一個子集S滿足，子集S覆蓋查詢子意圖的程度取得最大值。該問題就成了一個最大化覆蓋問題，它是NP難解的。

相應的，支持檢索結果多樣化任務的查詢性能預測算法需要同時考慮查詢的相關性性能和多樣化性能。亦即不僅需要考慮返回結果列表中是否包含較多的相關文檔，而且需要考慮它們對查詢不同方面的覆蓋程度。因此不同于只考慮結果列表相關性的傳統(tǒng)性能預測方法，算法需要額外考慮結果列表文檔之間的內容冗余度和新穎性。通過實驗得知，現(xiàn)有傳統(tǒng)的性能預測方法預測檢索結果多樣化性能的有效性不高，有必要專門研究支持結果多樣化性能的預測算法。到目前為止，尚未見到有相關的研究。因此本文的工作有較高的創(chuàng)新性。

在綜合考慮檢索結果相關性和多樣性兩方面特征的基礎上，本文提出三種檢索后查詢結果多樣化性能預測算法。實驗結果表明所提的算法具有較高的可用性。

2? ?檢索結果多樣化（Search result diversification）

由于檢索結果多樣化問題的復雜性高，以往研究的多樣化算法大多基于貪心法。即對于一個模糊查詢，從初始檢索結果中迭代選擇局部最優(yōu)的文檔，產生重排后的結果。所選文檔應當最大化覆蓋與該查詢相關的各個方面，并且與已經(jīng)選擇的文檔間的相似度最小。

根據(jù)是否分析查詢意圖，現(xiàn)有的多樣化方法可分為隱式和顯式兩類。隱式多樣化方法假設相似的文檔會覆蓋相同的子意圖，因此盡可能使結果中文檔之間存有較大的差異度。這類方法的特性是，不直接分析查詢意圖，而分析文檔的相似程度。

MMR（Maximal Marginal Relevance）[18]是最早的一種隱式多樣化方法。該方法分析候選文檔與查詢之間的相關度，并計算候選文檔與已排文檔之間的相似度，降低最終文檔列表的冗余度。

區(qū)別于隱式多樣化方法，顯式多樣化方法的特性是直接獲取查詢的子意圖集合。在此基礎上建立目標函數(shù)，使選擇的文檔最大化覆蓋查詢的多個子意圖。Santos和Macdonald等人[19]提出了概率框架xQuAD（Explicit Query Aspect Diversification），該框架把查詢的多個方面表示為一組子查詢集合。一方面評估文檔與查詢的相關性，另一方面考慮候選文檔覆蓋的子查詢數(shù)目，以及這些子查詢是否已被排在前面的文檔覆蓋。并用參數(shù)控制兩者之間的平衡，使得重排后的結果兼顧相關性與內容的新穎性。

Dang和Croft等人[20]提出了PM-2顯式多樣化方法，該方法將子查詢視作參與選舉的不同黨派，主要思想類似于政黨選舉中的Sainte-Lagu?方法。該方法首先計算每個席位應被分配的子查詢，然后選擇出一篇針對該子查詢得分最高的文檔獲得該席位。重復這一過程直至獲得重排后的結果。

本文采用三種典型的顯式多樣化方法對初始結果列表進行重排，分別是xQuAD[19]、PM-2[20]和CombSUM。有效的多樣化方法是我們構建實驗平臺和測試預測算法性能必不可少的。

3? 多樣化性能預測算法（Diversified performance?prediction algorithm）

本節(jié)提出的三種多樣化預測算法，均屬于檢索后預測算法。在預測查詢多樣化性能時，分別考慮影響多樣性的不同因素，分析中間檢索結果列表蘊涵的信息。

3.1? ?IASUM

IASUM主要從檢索結果的多樣性和新穎性兩個方面考察。多樣性衡量結果列表是否覆蓋到查詢的不同子意圖，新穎性則考慮結果列表是否過度偏向于某些特定子意圖。對特定檢索模型M與查詢q，假設不同子查詢的權重一致，IASUM算法如公式（1）所示。

本節(jié)提出的IASUM預測方法，在文檔的相關性性能方面，利用文檔排名信息度量與子查詢的相關程度。而在多樣化性能方面，考慮到每一個子查詢結果列表均對最終結果有所貢獻，IASUM利用懲罰因子α對隸屬同一子查詢的文檔的貢獻值進行懲罰。由此可見，IASUM是一種綜合考量了相關性和多樣性的預測方法。

3.2? ?IASUM2

IASUM算法本質上是從檢索結果列表排名信息的角度對檢索結果的多樣化性能進行分析。考慮到檢索結果中文檔的分數(shù)分布也提供了有價值的信息，因此可將IASUM算法和傳統(tǒng)的預測算法（SD2[15]和WIG[16]）進行整合，得出一種組合的多樣化性能預測算法IASUM2，如公式（2）所示。

3.3? ?IASUM3

不同于僅考慮文檔在不同列表中排名情況的IASUM方法和組合的IASUM2方法，IASUM3更加直接地分析利用了文檔的真實得分信息（經(jīng)過分數(shù)規(guī)范化，但保留了文檔原始得分的特征）。如公式（5）所示。

公式（5）中各變量的含義與前文基本一致，不同之處在于Sun（di）的計算方式。score（di，qj）表示文檔di在子查詢qj對應的結果列表中所得分數(shù)，采用0-1規(guī)范化方法處理，進而保留分數(shù)的原始分布特征。同樣地，若文檔未出現(xiàn)則設其值為0。

4? ?實驗（Experiment）

4.1? ?數(shù)據(jù)集

本文實驗數(shù)據(jù)來自TREC信息檢索會議（Text Retrieval Conference）在Web Track任務中提供的Clueweb09-CategoryB英文數(shù)據(jù)集。Clueweb09數(shù)據(jù)集包含超過10億個網(wǎng)頁，規(guī)模較大。為幫助更多不同組織參與活動，TREC為其設置了規(guī)模較小的Category B集。該數(shù)據(jù)集是Clueweb09的子集，由5000萬個網(wǎng)頁構成。

實驗選取來自TREC Web Track 2009—2012年采用的查詢，每年50個。由于第95和第100號查詢沒有相關文檔，于是在實驗中去除了這兩個查詢，共計198個查詢參與實驗。使用查詢集合中的query域作為主查詢，去除停用詞和敘述詞后的subtopic域作為子查詢。每個主查詢包含3到8個子查詢，以2009年的第25號查詢?yōu)槔?，它的主查詢?yōu)椤癊uclid”，相應的四個子查詢如圖1所示。

對于所有的查詢結果，TREC的主辦者聘請專家進行人工檢查。判斷哪些文檔和查詢相關，哪些和查詢不相關。在多樣化任務中，也判斷一個文檔和哪些子查詢相關。

4.2? ?評價方法

對于一組查詢，采用如前所述實驗平臺進行檢索。為每一個查詢生成相應的文檔序列。采用特定的性能預測算法可以預測每一個查詢的困難度，然后按照預測的困難度對所有查詢排序。同時對所有查詢的結果按照特定的性能指標（常用的檢索結果多樣化性能指標有ERR-IA@20、αNDCG@20等）進行評價，并按照評價的性能值對該組查詢進行排序。通過計算這兩組序列的相似程度，可以評價性能預測算法的優(yōu)劣。

比較兩組排序序列的相似程度，可用的指標有Pearson積差相關系數(shù)、Kendall秩相關系數(shù)、Spearman秩相關系數(shù)等。這些相關系數(shù)的取值范圍為[-1，1]。如兩組排序完全相同，值為1。如兩組排序完全相反，值為-1。如兩組排序無相關性，值接近0。值越接近1，說明兩組排序越相似，預測算法的性能越好。

4.3? ?實驗設置及預處理

實驗采用Indri開源搜索引擎中的查詢項似然檢索模型對所有查詢及子查詢進行初始檢索，其中狄利克雷平滑系數(shù)，結果列表文檔數(shù)N設置為1000。并使用公開的垃圾文檔排名算法Waterloo spam scorer對初始檢索結果進行垃圾文檔過濾。Waterloo spam scorer為ClueWeb09數(shù)據(jù)集中的每篇文檔賦予了一個垃圾百分數(shù)分值，分值越低，越有可能為垃圾文檔。本實驗中閾值設置為70%。

下一步是對初始檢索結果進行多樣化重排，使用xQuAD[19]、PM-2[20]和CombSUM三種多樣化算法。對于四組查詢，共產生12個結果（run）。最后使用Ndeval程序對這些檢索結果進行評價，并根據(jù)ERR-IA@20指標選擇性能最好的檢索結果和對應的平衡系數(shù)λ，產生的多樣化檢索結果如表1所示。

為評估本文所提預測方法的有效性，實驗選取SD2、WIG、NQC及SMV四種傳統(tǒng)性能預測算法作為基準。各種算法中的參數(shù)根據(jù)文獻[6，16，17]的推薦而設置，WIG的截斷系數(shù)k設置為5，NQC的截斷系數(shù)k設置為100，SMV的截斷系數(shù)k設置為100。

4.4? ?多樣化性能預測方法的評估分析

使用Pearson、Kendall和Spearman相關系數(shù)評價預測算法的有效性時發(fā)現(xiàn)，三種系數(shù)下的實驗結果整體上相似。所以這里僅列出Spearman系數(shù)對應的實驗結果。表2列出了傳統(tǒng)預測算法的預測值與ERR-IA@20指標值的Spearman相關系數(shù)，表3列出了本文所提算法的預測值與ERR-IA@20指標值的Spearman相關系數(shù)。其中黑體數(shù)字表示在所有七種預測算法中的最優(yōu)值。

從表2可以發(fā)現(xiàn)，每一種方法的預測性都有負相關的情況出現(xiàn)。所以傳統(tǒng)的基于得分分布的預測算法在查詢多樣化性能預測上的適用性不強。而根據(jù)表3，可以得知本文提出的三種考慮多樣性的性能預測算法優(yōu)于四種基準預測算法。具體來說，與作為基準的四種預測算法相比，本文提出的三種預測算法共在11個運行結果上取得了最大的Spearman系數(shù)，而前者共在一個運行結果上取得最大值。對四種基準預測算法中進行兩兩比較，WIG算法的有效性最高，但與本文提出的三種預測算法相比也略輸一籌。在三種新方法中，IASUM3方法的有效性最高，它優(yōu)于IASUM和IASUM2的主要原因是，在綜合考慮相關性和多樣性的基礎上，它充分地利用了結果列表中文檔的得分分布信息，故在實驗中共有六次取得了最好成績。

除了ERR-IA@20外，還分別使用αNDCG@20和NRBP指標值評估所得結果列表的性能和預測的排序進行比較。圖2和圖3分別顯示了采用αNDCG@20和NRBP時的Spearman相關系數(shù)，圖中列出了三種較好的預測方法（WIG、SD2和IASUM3）的性能。

總體說來，采用αNDCG@20或NRBP和采用ERR-IA@20指標效果相仿。對比圖2和圖3中使用不同指標測度時預測算法的有效性，可以得知在改變度量指標（αNDCG@20和NRBP）時，預測算法的Spearman系數(shù)趨勢是相似的。當指標為αNDCG@20時，12個運行結果中IASUM3算法在10個運行結果上優(yōu)于WIG和SD2算法，其在12個運行結果上的平均Spearman系數(shù)為0.408。當指標為NRBP時，IASUM3算法在10個運行結果上優(yōu)于WIG和SD2算法，其在12個運行結果上的平均Spearman系數(shù)為0.422。另一方面，對三種指標計算所有結果的平均方差值，得到WIG和SD2的方差分別為0.226和0.199，而IASUM3的方差為0.181。這表明IASUM3算法在檢索結果多樣化性能的預測上，是有效且穩(wěn)定的。

5? ?結論（Conclusion）

針對近些年來備受研究人員關注的查詢性能預測技術，本文明確了從查詢的相關性性能和多樣化性能這兩個方向入手研究查詢性能預測，并提出了三種查詢多樣化性能的預測算法。為了檢驗提出的預測算法的有效性，在經(jīng)過多樣化處理的Indri運行結果上進行了查詢多樣化性能的預測實驗。實驗結果表明，和傳統(tǒng)的預測算法相比，本文提出的預測算法IASUM和IASUM3優(yōu)勢明顯，能有效提高多樣化性能預測精度，且性能較為穩(wěn)定。同時，分析文檔原始得分的IASUM3算法的預測效果整體上優(yōu)于分析排名得分的IASUM算法。這說明與檢索結果的排名得分相比，文檔得分包含了更多的文檔查詢相似度信息，對于預測算法而言，文檔得分比排名得分具有更高的使用價值。

本文提出的查詢多樣化性能預測算法采用了結果列表中文檔的排名與得分信息，但未考慮文檔的內容，這是下一步的工作方向。我們將嘗試一些基于自然語言處理的算法，以期獲得更為有效的多樣化查詢性能預測方法。另一方面，搜索引擎在檢索過程中產生了大量的搜索日志信息，并且這些日志包含了大量用戶和搜索引擎的交互信息。如何有效地挖掘和分析這些數(shù)據(jù)，并用于查詢性能預測，也是一項值得研究的工作。

參考文獻（References）

[1] Zamani H，Croft W B，Culpepper J S，et al.Neural Query Performance Prediction using Weak Supervision from Multiple Signals[C].international acm sigir conference on research and development in information retrieval，2018：105-114.

[2] Mizzaro S，Mothe J，Roitero K，et al.Query Performance Prediction and Effectiveness Evaluation Without Relevance Judgments：Two Sides of the Same Coin[C].international acm sigir conference on research and development in information retrieval，2018：1233-1236.

[3] Roitman H.An Extended Query Performance Prediction Framework Utilizing Passage-Level Information[C].international conference on the theory of information retrieval，2018：35-42.

[4] Roitman H，Erera S，Sarshalom O，et al.Enhanced Mean Retrieval Score Estimation for Query Performance Prediction[C].international conference on the theory of information retrieval，2017：35-42.

[5] Katz G，Shtock A，Kurland O，et al.Wikipedia-based query performance prediction[C].international acm sigir conference on research and development in information retrieval，2014：1235-1238.

[6] Tao Y，Wu S.Query performance prediction by considering score magnitude and variance together[C].Acm International Conference on Conference on Information & Knowledge Management.ACM，2014：1891-1894.

[7] Raiber F，Kurland O.Query-performance prediction：setting the expectations straight[C].international acm sigir conference on research and development in information retrieval，2014：13-22.

[8] Hauff C，De Jong F M，Kelly D，et al.Query quality：user ratings and system predictions[C].international acm sigir conference on research and development in information retrieval，2010：743-744.

[9] Sondak M，Shtok A，Kurland O，et al.Estimating query representativeness for query-performance prediction[C].international acm sigir conference on research and development in information retrieval，2013：853-856.

[10] Mothe J，Tanguy L.Linguistic features to predict query difficulty-a case study on previous TREC campaigns[C].ACM SIGIR Workshop on Predicting Query Difficulty-Methods & Applications，2005.

[11] Butman O，Shtok A，Kurland O，et al.Query-Performance Prediction Using Minimal Relevance Feedback[C].Conference on the Theory of Information Retrieval.ACM，2013.

[12] Julie A，Adrian G，Sebastien D，et al.Statistical Analysis to Establish the Importance of Information Retrieval Parameters[J].Journal of Universal Computer Science，2015，21（13）：1767-1787.

[13] Cronen-Townsend S，Zhou Y，Croft W B，et al.Predicting query performance[C].international acm sigir conference on research and development in information retrieval，2002：299-306.

[14] Zhou Y，Croft W B.Ranking robustness：a novel framework to predict query performance[C].conference on information and knowledge management，2006：567-574.

[15] Cummins R，Jose J M，Oriordan C，et al.Improved query performance prediction using standard deviation[C].international acm sigir conference on research and development in information retrieval，2011：1089-1090.

[16] Zhou Y，Croft W B.Query performance prediction in web search environments[C].international acm sigir conference on research and development in information retrieval，2007：543-550.

[17] Shtok A，Kurland O，Carmel D，et al.Predicting Query Performance by Query-Drift Estimation[J].ACM Transactions on Information Systems，2012，30（2）：305-312.

[18] Carbinell J，Goldstein J.The use of MMR，diversity-based reranking for reordering documents and producing summaries[J].international acm sigir conference on research and development in information retrieval，1998，51（2）：335-336.

[19] Santos R L，Macdonald C，Ounis I，et al.Exploiting query reformulations for web search result diversification[J].the web conference，2010：881-890.

[20] Dang V，Croft W B.Diversity by proportionality：an election-based approach to search result diversification[C].international acm sigir conference on research and development in information retrieval，2012：65-74.