Query Term Weighting based on Query Performance Prediction
Haggai Roitman









Query Term Weighting based on Query Performance Prediction
    
  Haggai Roitman

  IBM Research

  Haifa University Campus

  Haifa, Israel 

   

  
    
===========================================================================================




This work presents a general query term weighting approach based on query performance prediction (QPP). To this end, a given term is weighed according to its predicted effect on query performance. Such an effect is assumed to be manifested in the responses made by the underlying retrieval method for the original query and its (simple) variants in the form of a single-term expanded query. Focusing on search re-ranking as the underlying application, the effectiveness of the proposed term weighting approach is demonstrated using several state-of-the-art QPP methods evaluated over TREC corpora. 





§ INTRODUCTION

This work presents a simple and general query term weighting approach based on query performance prediction (QPP) <cit.>. To this end, a given term is weighed according to its predicted effect on query performance. 
Such an effect is assumed to be manifested in the responses made  by the underlying retrieval method for the original query and its (simple) variants. Query variants are introduced in the form of a single-term expanded query, which artificially “re-focus" the intent of the original query. Hence, for a given term, the query is expanded with that single term and is resubmitted to obtain the corresponding response. By evaluating the quality of both result lists (i.e., the one originally retrieved for the query and the one retrieved for its single-term expanded version), the marginal effect of that term on the query's performance may be estimated. A post-retrieval QPP method <cit.>, assumed to be provided as an input, serves in this work as a proxy for estimating such “before"  and “after" effects on query performance.
The relative difference (positive, negative or none) in predicted query performance is, therefore, used for determining a given term's importance with respect to the original query.

Weighed terms may be extracted from any source, e.g., either considering the terms explicitly specified in the query or implicitly derived from it (e.g., using relevance models <cit.>). Specifically, in this work, terms are derived from the RM3 pseudo relevance model <cit.>.
Focusing on search re-ranking as the underlying application, the effectiveness of the proposed term weighting approach is demonstrated using several state-of-the-art QPP methods evaluated over TREC corpora. The proposed term weighting approach is further demonstrated to provide a more robust retrieval by improving the performance of the underlying relevance model that is used to derive the terms.



§ RELATED WORK

There exist numerous approaches for term weighting in IR, spanning from more “traditional" unsupervised term weighting schemes (e.g., TF-IDF, BM25 <cit.>, language models <cit.>, etc) and relevance models <cit.>, to supervised methods that exploit various term features (e.g., local and global term statistics <cit.>, term dependencies or proximity <cit.>, external corpora or sources <cit.>, etc).

In this work, term weights are derived using query performance prediction (QPP) methods. In the absence of any prior relevance knowledge, QPP methods may be utilized for predicting retrieval effectiveness <cit.>. Many QPP methods have been proposed, including various pre-retrieval methods, post-retrieval methods and their combinations <cit.>.

The proposed approach shares some relationship with previous works that utilized QPP methods for ranker selection <cit.>, selective query expansion <cit.> and query reduction <cit.>.
Yet, unlike such previous works, QPP methods are used in this work to directly weight terms for document scoring, rather than just for choosing over retrieved lists or selecting query terms for expansion/reduction.

Several previous works have also utilized various QPP methods for term weighting <cit.>. Yet, this work proposed term weighting approach is different from such previous works in several ways. First, similar to Song et al. <cit.> and unlike the works by Bendersky and Croft <cit.> and Ozdemiray and Altingovde <cit.>, term weighting is determined in the scope of the original query.  In <cit.> term weights are independently derived from the original query by estimating the performance of a query that contains only a single term. Second, unlike Song et al. <cit.>, the proposed weighting approach may be used to weight terms that were not explicitly specified in the query (e.g., those terms that are derived from a relevance model). Finally, this work proposed term weighting approach provides a more holistic solution, where various QPP methods may be applied, including methods similar to those that were proposed in <cit.>.



§ APPROACH




 §.§ Preliminaries

Let q denote a query submitted over a corpus of documents 𝒟.
Given query q, let Score_q(d) denote the score of document d∈𝒟 and let D_q^[k]⊆𝒟 further denote a ranked list that contains the k highest scored documents according to Score_q(d). In this work, the retrieval scores Score_q(d) are calculated according to the query-likelihood model <cit.> as follows.
Let w be a term in the vocabulary V and p_x^[μ](w) be text x's Dirichlet smoothed language model with smoothing parameter μ <cit.>, calculated as follows:

    p^[μ]_x(w)=tf(w,x)+μtf(w,𝒟)/|𝒟|/|x|+μ,

where tf(w,·) and |·| denote the term frequency of term w and the overall term frequency (either in text x or the entire collection 𝒟), respectively.
Let {q_i} be the bag of query terms, the query-likelihood  of a document d∈𝒟 is calculated as follows:

    Score_q(d)= p^[μ]_d(q)= log∏_q_i p^[μ]_d(q_i).




 §.§ Term Weighting using QPP


For a given query q and a term w∈V, let q∨w denote the expansion of query q with w as a single additional disjunctive term. Such an expansion basically “shifts" the original information need expressed in q towards a specific term w. Surely, for a given query q, not all terms w∈V may be related to q. Hence, an expansion of such terms may result in a query-drift <cit.>. To minimize query drift risk, terms w∈V considered for such an expansion should be carefully selected. For example, in this work we make use of the RM3 relevance model <cit.> to derive terms w that are (presumably) related to q. 

Terms w∈V are now weighted according to their predicted effect on the performance of query q. While a term w∈V may be relevant in some way to query q, it may still have a varying effect on its performance. For example, a term w that is explicitly expressed in query q may not be well covered in the collection 𝒟 <cit.>. As another example, a term w that was implicitly derived from query q (e.g., using a relevance model) may still incur a risk by including it as part of an expanded query due to possible query-drift <cit.>. Therefore, terms w∈V may be weighed according to their potential to improve (or decline) query q's performance.

For a given query q and retrieved list D_q^[k], let P(D_q^[k]) now denote the predicted quality[Such quality prediction is usually given in terms of correlation to Average Precision <cit.>.] of D_q^[k]. P(D_q^[k]) may be instantiated using various post-retrieval QPP methods <cit.>.
The relative influence of a term w∈V on the performance of query q (as manifested in the retrieved list D_q^[k]) is estimated by further retrieving the list D_q∨w^[k] (⊆𝒟). Let P(D_q∨w^[k]) be the corresponding predicted quality of D_q∨w^[k].
Let Δ P(w;q)= P(D_q∨w^[k]) - P(D_q^[k]) denote the difference between the quality predicted for the original query q and its single term expanded version q∨w.

Finally, let φ_q(w)∈[0,1] now denote the weight assigned to term w∈V, derived in this work using the following logistic (sigmoid) function[The logistic function transforms the absolute difference in predicted quality into a probabilistic [0,1] term weight representation.]:

    φ_q(w) =1/1+exp^-Δ P(w;q).


 Therefore, according to Eq. <ref>, the larger the predicted improvement Δ P(w;q) for a given term w∈V is, the higher will be the weight φ_q(w) assigned to that term.




§ EVALUATION





 §.§ Proof of concept application: search re-ranking

The proposed term weighting approach is evaluated in this work using search re-ranking as the underlying application.
Following Bendersky et al. <cit.>, a document d∈ D_q^[k] is re-scored based on the derived weights {φ_q(w)}_w∈V using the following log-linear score[TWQP stands for Term Weighting by Quality Prediction.]:

    Score^ TWQP_q(d)=∑_w∈Vφ_q(w)·log(p^[μ]_d(w)).


Documents initially retrieved in D_q^[k] are, therefore, re-ranked according to Score^ TWQP_q(·).



 §.§ Setup




  
*Datasets



The TREC corpora and queries used for the evaluation are specified in
Table <ref>. 
Titles of TREC topics were used as queries. The Apache
Lucene[<http://lucene.apache.org>] open source search library (version 4.9) was used for indexing and searching documents.  Documents and queries were processed
using Lucene's English text analysis (i.e., tokenization, stemming, stopwords, etc). Lucene's implementation of the query-likelihood (QL) model with Dirichlet smoothing <cit.> was used for scoring documents. Various values of the Dirichlet-smoothing free parameter were explored μ∈{100,200,…,5000} <cit.> so as to optimize MAP (@1000) (denoted QLOpt hereinafter).



  
*Terms extraction
For efficiency considerations, in this work, for a given query q, terms in V considered for weighting were induced using the RM3 pseudo relevance feedback model <cit.>. Usage of this relevance model allows to induce terms that are presumably relevant to the queried topic <cit.>.
Let D_q^[m] denote the top-m scored documents in D_q^[k]. The likelihood of a given term w∈V according to the RM3 relevance model is calculated as follows:


    p_RM3(w;D_q^[m],μ,λ)= λ· p_q^[0](w)    
    
     + (1-λ)·∑_d∈ D_q^[m]p_d^[0](w)   p_d^[μ](q)/∑_d'∈ D_q^[m]p_d'^[μ](q),


where λ∈[0,1] is a smoothing parameter, used for smoothing the query language model p_q^[0](·) with the (RM1) relevance model <cit.>.
Finally, V consists of the top-n terms with the highest p_RM3(w;D_q^[m],μ,λ) likelihood. Following previous recommendations, the following parameters were fixed: μ=1000, λ=0.9 and n=100 <cit.>. The number of top documents m in D_q^[k] used for inducing the RM3 terms was further chosen as follows m∈{5,10,…,100} so as to optimize MAP (@1000). Let RM3Opt denote the induced “optimal" RM3 model[It is worth noting that, while such simple parameter tuning was done in order to obtain the “optimal" initial retrieval (QLOpt) and the “optimal" relevance model (RM3Opt) that is used later on (see Section <ref>) for deriving a reasonable re-ranking baseline, the proposed term weighting method is completely unsupervised and requires no further tuning.].



  
*Baseline term weighting methods
The proposed term weighting approach, denoted TWQP(·) hereinafter, was compared against three other previous approaches that also utilized QPP methods for the same task <cit.>. The details of these methods are now shortly introduced.

  
  * nWIG: The normalized Weighted Information Gain (WIG) QPP method <cit.> was used in <cit.>, together with many other term features, for inducing term weights. For a given term w∈ V its nWIG weight is calculated as follows:
      
    nWIG(w)=1/m∑_d∈ D_q^[m]log p_d^[μ](w) - log p_𝒟^[0](w)/- log p_𝒟^[0](w),

       with m=50, following <cit.>.
  
  * ScoreRatio: For a given term w∈V, let sr(w)=Score_w(d_1)/Score_w(d_k) denote the ratio between the score of the first and last ranked documents in D_q^[k], using q=w (i.e., a query with term w as its single term) <cit.>.
  The (sum-)normalized sr(w) value is then used as the weight of term w. The ScoreRatio approach was used in <cit.> for weighing query aspects for search diversification and was shown to be superior to several other state-of-the-art QPP alternatives <cit.>.
  
  * SROR: The Search Result Overlap Ratio (SROR) method proposed in <cit.> scores each term w∈{q_i} according to the relative overlap between the initial query result and that obtained by removing term w from q.
  The lower such overlap is, the higher the predicted query drift due to the exclusion of term w from q (denoted: q-w), and thus, the more important term w is <cit.>. The SROR weight of a given term w∈{q_i} is calculated as follows: SROR(w)= 1-|D_q^[k]∩ D_q-w^[k]|/|D_q^[k]|. Please note that, only terms that are explicitly specified in query q may be weighed according to this method <cit.>.




  
*TWQP method instantiations
To illustrate the effectiveness of the proposed TWQP(·) term weighting approach, three different QPP method instantiations of P(·) were evaluated.
Each QPP method was applied twice, once over the result of query q (i.e., D_q^[k]) and once over the result of its expansion q∨w (i.e., D_q∨w^[k]), so as to derive Δ P(w;q).
The first, denoted TWQP(WIG), is based on the WIG predictor <cit.>, and is calculated as follows:

    WIG(D_q^[k])=1/m√(|q|)·∑_d∈ D_q^[m]∑_q_i∈qlogp_d^[μ](q_i)/p_𝒟^[0](q_i),


with m=5, following previous recommendations <cit.>.

The second, denoted TWQP(ScoreRatio), is based on the ScoreRatio method <cit.> that was described above.
The third, denoted TWQP(NQC), is based on the Normalized Query Commitment (NQC) method <cit.>, and is further calculated as follows:

    NQC(D_q^[k])=σ(D_q^[m])/p^[0]_𝒟(q),


where σ(D_q^[m]) denotes the standard deviation (spread) of the score of the m highest scored documents in D_q^[k] (setting m=150, following previous recommendations <cit.>). p^[0]_𝒟(q) further denotes the collection query likelihood <cit.>.
The higher the spread of the document scores within D_q^[m], the better the performance predicted for query q <cit.>.





  
*Evaluation measures
For each corpus 𝒟 and query q, an initial list D_q^[k] was retrieved. Each list included the top k=1000 ranked documents according to QLOpt. The RM3 terms V were further used for term weighting (except for the SROR method, where only the initial query's terms were considered).  The top-100 documents were then re-ranked according to Score^ TWQP_q(·). To further compare against RM3Opt, documents in the initial list D_q^[k] were re-ranked according to RM3Opt using the cross entropy between the (RM3) relevance
model (i.e, p_RM3(·,D_q^[m],μ,λ)) and their (smoothed) unigram language models (i.e., p^[μ]_d(·), further using the same Dirichlet smoothing parameter μ derived for QLOpt) <cit.>.

The effectiveness of the various term weighting approaches was evaluated using the following measures:  p@10, MAP, and MRR[The Mean Reciprocal Rank (MRR) measure captures the ability of a re-ranking method to improve the position of the first relevant document and is given by the inverse ratio of that document's position.].
Statistically significant differences in performance were measured using the paired two-tailed t-test with a 95% confidence level.



 §.§ Results




The results of the evaluation are depicted in Table <ref>. Overall, regardless of the actual QPP method that was used, TWQP(·) provided the most effective term weights for search re-ranking. Re-ranking according to TWQP(·) has provided a notable boost to the performance of the initial retrieved list. The boost in P@10 was up to +4.8%, +6.7% and +10.5% more for the ROBUST, WT10g and GOV2 collections, respectively. The boost in MAP was up to +4.7%, +2.5% and +6.1% more for the ROBUST, WT10g and GOV2 collections, respectively. A slight decrease, yet reasonable and insignificant, in MRR was observed.

Among the other term weighting alternatives that were evaluated, nWIG has exhibited a negative effect on query quality[This actually comes with no surprise, as in <cit.> nWIG served only as a single feature among many others used for concept weights learning.]  while ScoreRatio has been the most competitive to TWQP(·). Comparing ScoreRatio to the best TWQP(·) alternative on each setting, depending on the QPP method instantiation,  TWQP(·) has provided a better performance. Specifically, TWQP(NQC), which utilizes the NQC measure as its underlying QPP method, has provided the best alternative with a significant improvement in MAP over ScoreRatio for the ROBUST and GOV2 datasets.

Finally, comparing  TWQP(·) with RM3Opt, it is apparent that, re-ranking according to the weights derived by TWQP(·) provides a more robust retrieval (in general) compared to that based on RM3Opt directly. By further measuring the Robustness Index[Let %N_+ or %N_- be the percentage of queries in which a given method has a better or worse p@10 performance than the baseline method, respectively; then, RI=%N_+-%N_-∈[-1,1].] <cit.> (RI) at top-10 documents cutoff, TWQP(·) has provided +12.5% (0.08 → 0.09), 0% (no change) and +47% (0.17 → 0.25) improvement in RI on top of RM3Opt for the ROBUST, WT10g and GOV2 collections, respectively.




plain
10

amati2004
G. Amati, C. Carpineto, and G. Romano.
Query difficulty, robustness, and selective application of query
  expansion.
Advances in information retrieval, pages 127–137, 2004.

Balasubramanian:2010a
Niranjan Balasubramanian and James Allan.
Learning to select rankers.
In Proceedings of SIGIR '10, pages 855–856, 2010.

Balasubramanian:2010b
Niranjan Balasubramanian, Giridhar Kumaran, and Vitor R. Carvalho.
Exploring reductions for long web queries.
In Proceedings of SIGIR '10, pages 571–578, 2010.

Bendersky:2008
Michael Bendersky and W. Bruce Croft.
Discovering key concepts in verbose queries.
In Proceedings of SIGIR '08, pages 491–498, 2008.

Bendersky:2012a
Michael Bendersky and W. Bruce Croft.
Modeling higher-order term dependencies in information retrieval
  using query hypergraphs.
In Proceedings of SIGIR '12, pages 941–950, 2012.

Bendersky:2010
Michael Bendersky, Donald Metzler, and W. Bruce Croft.
Learning concept importance using a weighted dependence model.
In Proceedings of WSDM '10, pages 31–40, 2010.

Bendersky:2011
Michael Bendersky, Donald Metzler, and W. Bruce Croft.
Parameterized concept weighting in verbose queries.
In Proceedings of SIGIR '11, pages 605–614, 2011.

Bendersky:2012
Michael Bendersky, Donald Metzler, and W. Bruce Croft.
Effective query formulation with multiple information sources.
pages 443–452, 2012.

Buckley:2004
C. Buckley.
Why current ir engines fail.
In Proceedings of SIGIR '04, pages 584–585, 2004.

Cao:2008
Guihong Cao, Jian-Yun Nie, Jianfeng Gao, and Stephen Robertson.
Selecting good expansion terms for pseudo-relevance feedback.
In Proceedings of SIGIR '08, pages 243–250, 2008.

CarmelBook
D. Carmel and E. Yom-Tov.
Estimating the query difficulty for information retrieval.
In Synthesis Lectures on Information Concepts, Retrieval, and
  Services, 2(1):1–89, 2010.

Collins-Thompson:2007b
K. Collins-Thompson and J. Callan.
Estimation and use of uncertainty in pseudo-relevance feedback.
In Proceedings of SIGIR '07, pages 303–310, 2007.

cronen2004language
Steve Cronen-Townsend, Yun Zhou, and W Bruce Croft.
A language modeling framework for selective query expansion.
Technical report, DTIC Document, 2004.

diaz2016pseudo
Fernando Diaz.
Pseudo-query reformulation.
In European Conference on Information Retrieval, pages
  521–532. Springer, 2016.

Lavrenko:2001
V. Lavrenko and W. B. Croft.
Relevance based language models.
In Proceedings of SIGIR '01, pages 120–127, 2001.

liu2006experiments
Xiaoyong Liu and W Bruce Croft.
Experiments on retrieval of optimal clusters.
Technical report, Technical Report IR-478, Center for Intelligent
  Information Retrieval (CIIR), University of Massachusetts, 2006.

Ozdemiray:2014
A. M. Ozdemiray and Ismail S. Altingovde.
Query performance prediction for aspect weighting in search result
  diversification.
In Proceedings of CIKM '14, pages 1871–1874, 2014.

Ponte:1998
J. M. Ponte and W. B. Croft.
A language modeling approach to information retrieval.
In Proceedings of SIGIR '98, pages 275–281, 1998.

Robertson:2009
S. Robertson and H. Zaragoza.
The probabilistic relevance framework: Bm25 and beyond.
Found. Trends Inf. Retr., 3(4):333–389, April 2009.

Roitman:2014
H. Roitman, S. Hummel, and O. Kurland.
Using the cross-entropy method to re-rank search results.
In Proceedings of SIGIR '14, pages 839–842, 2014.

Roitman:2018:SYR
Haggai Roitman, Ella Rabinovich, and Oren Sar Shalom.
As stable as you are: Re-ranking search results using query-drift
  analysis.
In Proceedings of the 29th on Hypertext and Social Media, HT
  '18, pages 33–37, New York, NY, USA, 2018. ACM.

Shtok:2012
A. Shtok, D. Kurland, O.and Carmel, F. Raiber, and G. Markovits.
Predicting query performance by query-drift estimation.
ACM Trans. Inf. Syst., 30(2), May 2012.

Song:2011
Wei Song, Yu Zhang, Yubin Xie, Ting Liu, and Sheng Li.
Query term ranking based on search results overlap.
In Proceedings of SIGIR '11, pages 1253–1254, 2011.

Svore:2010
Krysta M. Svore, Pallika H. Kanani, and Nazan Khan.
How good is a span of terms?: Exploiting proximity to improve web
  retrieval.
In Proceedings of SIGIR '10, pages 154–161, 2010.

Zhou:2007
Y. Zhou and W. B. Croft.
Query performance prediction in web search environments.
In Proceedings of SIGIR '07, pages 543–550, 2007.



