Relevance modeling and data fusion are powerful yet simple approaches to improving the efectiveness of Information Retrieval Systems. For many of the classic TREC test collections, these approaches were used in many of the top performing retrieval systems. However, these approaches are often ineficient and are therefore rarely applied in production systems which must adhere to strict performance guarantees. Inspired by our recent work with humanderived query variations, we propose a new sampling-based system which provides significantly better eficiency-efectiveness tradeofs while leveraging both relevance modeling and data fusion. We show that our new end-to-end search system approaches the state-of-the-art in efectiveness while still being eficient in practice. Orthogonally, we also show how to leverage query expansion and data fusion to achieve significantly better risk-reward trade-ofs than plain relevance modeling approaches.
Query expansion is a classic technique used in search systems to
improve the efectiveness of a search engine. In general, it works by
taking a user’s query q and running it against the index to retrieve
a top-k set of documents assumed to be relevant, and then selecting
t terms to append to the user query to form a new query q′. One
drawback of query expansion is that several relevant documents
must be in the top-k list in order induce “useful” expansion terms [
However, the performance of any single query can vary widely
across diferent collections. Benham et al. [
Another line of research on the query expansion techniques is to
induce relevance models from external resources. One of the most
efective models was proposed by Diaz and Metzler [
Building on these two ideas, we present a new approach inspired
by the best performing system run in the TREC 2004 Robust Track –
pircRB04t3 [
A significant drawback to this approach — despite its efectiveness and risk-sensitivity properties — is that it is very expensive in practice. We show how to overcome this limitation by generating many short synthetic queries using a stochastic random process and fusing their result lists. We then explore how these synthetic queries compare with user-generated queries, and demonstrate how query expansion can also be optimized to reduce risk sensitivity.
We explore two related research questions in this paper: Research Question (RQ1): Can data fusion and query expansion be combined to produce state-of-the-art efectiveness in classically “hard” test collections? Research Question (RQ2): Can our new approaches be optimized to be eficient, efective, and minimize risk? 2
Relevance Modeling. The classic relevance model is induced from
the highest ranking top-k documents for a query in a first stage
search [
Data Fusion. Rank fusion algorithms can broadly be classified
into two categories – score-based fusion and rank-based fusion.
The earliest algorithms such as CombSUM and CombMNZ are
scorebased [
Users Information
Need
External Corpora Target Corpora
Fusion Function
Final Top-k
List
Top-! Documents
Relevance
Models
Top-k Documents
User Query Variations. The work of Belkin et al. [
Here we briefly describe our end-to-end approach to search,
using an approach we denote as RMQV. The key idea is to try and
induce query variations automatically using external corpora in
such a way as to mimic the performance achievable using query
variations created with human intervention. In order to achieve
this, we leverage prior work on relevance modeling with external
corpora [
p (w |RM3) = (1 − λ)p (w |q) + λp (w |RM1)
Note that we assume both models are clipped and renormalized appropriately. In this work, we use both RM1 and RM3.
In addition, we propose a new sampling-based version which attempts to capture the expressive power of RM3, without the computational costs. The key idea is to sample terms from both the expansion set T ′ and the original query q. We use a weighted probability sampling process over T ′, where each term t ∈ T ′ has a selection probability of: pˆ(t |Lc ) = Pd ∈Lc p (d |q) Pw ∈T ′ p (w |d )
Pd ∈Lc p (t |d )p (d |q)
in which p (d |q) is computed using p (q|d ) for each document d ∈ Lc .
We then perform a Bernoulli sampling over the original query in
order to randomly determine if the current query terms should be
included in the sampled query. This ensures that the induced queries
do not drift too far from the original, but also are not strictly new
terms concatenated to the original. The query length |qˆ| can also be
determined randomly, and in practice we found queries between the
length of 5 and 15 provide the best trade-of. Our overall goal is to
generate discriminative, unweighted queries of reasonable length.
In the next section, we will see that this is fundamentally important
to overall performance when using dynamic pruning. Also, note
that the classic RM1 and RM3 models rely on Query Likelihood.
However, these models are often significantly slower when using
dynamic pruning [
We now introduce further details of our sampling technique
for a single corpus, and then show how it can be parallelized over
multiple external corpora and combined with fusion to improve
eficiency-efectiveness trade-ofs. Figure 1 shows a sketch of the
entire retrieval process. To generate a query variant using our
sampling approach, the user first submits a query to the system. A first
stage top-k retrieval is performed on the external corpus (or the
target collection) to return the set of feedback documents Lc . This
(2)
(3)
retrieval process uses the Bmw dynamic pruning algorithm [
A key bottleneck in the retrieval process for term expansion is
relevance model construction. To reduce the computational
overhead of this stage, we extend the work of Asadi and Lin [
We now evaluate the merit of our RMQV approach by placing it into context with related baselines in the literature. 4
In this section, we discuss the datasets used, efectiveness baselines,
query expansion timings, risk-profiles and place all of these
considerations into context with our new query sampling approach.
All baseline runs used to demonstrate eficiency, efectiveness and
risk-reward profiles are generated using an extended version of
the VBmw [
Hardware Configuration . Our experiments are conducted on an idle Linux Server with 256 GiB of RAM and two Intel Xeon E52690 v3 CPUs. All algorithms were implemented with C++11 and compiled with GCC 6.3.1 using the highest optimization settings. Threading was implemented using the C++ STL threading libraries, and we use up to 48 threads at any one time.
Datasets. To evaluate our approach, we follow the methodology
from Diaz and Metzler [
Three external corpora are used: a variant of the BIGNEWS
collection [
We also use the TREC 2017 CORE user query variations from
Benham et al. [
All collections used are indexed using the Krovetz stemmer with stopwords removed.
System Configuration . We use 5-fold cross-validation for parameter tuning with the following sweeps performed: the number of feedback documents Lc ∈ {5, 10, 25, 50, 100}, the number of expansion terms |T ′| ∈ {5, 10, 25, 50, 100}, the number of query samples per collection |Q ′| ∈ {2, 4, 6, 8, 10}, and the RM3 anchoring parameter λ ∈ {0.0 . . . 1.0}. Note that in our sampling process, the query length of a sampled query is a random integer generated between 5 and 15.
Baseline Efectiveness . We now attempt to answer RQ1. Table 2
summarizes the efectiveness of every system compared in this
paper, representing diferent retrieval models. The BM25 method is
a bag-of-words run, providing a lower bound for efectiveness as a
simple, yet eficient retrieval technique. The L2p system was
proposed by Lu et al. [
Across all system comparisons, we see that RM3-ExtRRF outperforms all of the standard baselines. RMQV performs similarly to RM3, but as we shall see shortly has several other advantages that are not obvious when thinking in terms of only efectiveness. For upper bounds on efectiveness, the human-generated queries from UQV-RRF perform best in terms of NDCG@10 across all models. Although query fusion can be relatively fast and efective as the terms are unweighted allowing dynamic pruning to work efectively, it requires access to appropriately clustered queries generated by humans. Although, this is not the case for AP, where the entry TREC Best still outperforms all others.
So, in summary, automatic query expansion over multiple external corpora, when combined with fusion, is highly efective. While our current configuration is still unable to match the performance of fusion over human query variations (which is not an automatic process), it is clearly a step in the right direction. We believe further work on RQ1 using the techniques described in this paper will close this gap even more.
Query Processing Configuration . Our proposed system
implements a range of dynamic pruning algorithms for eficient top- k
retrieval. We ran several preliminary experiments to select which
algorithms should be deployed at each stage, which is not shown here
in the interest of succinctness. In all pipelines, we use Bmw [
Eficient Query Variation Expansion . A long-standing issue for retrieval processes that incorporate query expansion is that while efective, they fail to meet eficiency constraints in many real-world applications. This can be observed in Table 3 where the median response time for an RM3 query is several orders of magnitude slower than the bag-of-words retrieval. Note that the number of stage one posting evaluations is much higher for the bag-of-words runs as the top 1,000 documents are retrieved, whereas a RM3 run usually retrieves only the top 10 documents during the stage one. The stage two posting evaluations for RM3 are the result of the expanded query – more query terms equates an increase in posting evaluations, a stark contrast to the evaluations required by the bagof-words retrieval. Both RM3 and RM3-ExtRRF construct lengthy weighted queries commonly consisting of around 50 terms (empirically). The RM3-ExtRRF method has the highest eficiency cost due to the fact that three distinct relevance models are required to be induced from each external corpus (of varying size) in parallel; the newly formed expansion queries are executed on the target collection also in parallel; then RRF fusion is used to obtain the final ranked list. Although parallel processing is applied, this approach is still slower than RM3 as the (larger) external collections result in more processing for RM construction in the first stage.
Notably, the costs of inducing the relevance model(s) and the cost of long-weighted queries make the entire retrieval process impractical in even small collections. The number of postings which must be scored by the models, as shown in Table 3, suggests that significant performance improvements when using the full model are very unlikely.
Table 4 shows that the dominant cost in Query Expansion is correlated with the number of expansion terms. This indicates that limiting the number of terms selected might provide greater opportunities for eficiency improvements, but how can we find the best compromise between eficiency and efectiveness in this scenario? An interesting secondary aspect of Table 4 shows the eficiency cost of constructing the relevance model along with the choice of the number of feedback documents to use is negligible when compared to the second stage retrieval. The real performance bottleneck is processing long weighted queries.
Figure 2 shows the eficiency of the three query expansion pipelines implemented in our new system. RM3 and RM3-ExtRRF are the graphical interpretation of the timings reported in Table 3, System
RM3 RMQV RM3-ExtRRF 0 250
500 Time [ms] 750 and RMQV is our new sample-based modeling approach. It can be seen that RMQV is more eficient than the other methods which we largely attribute to the removal of the weighted query constraint in favour of running additional bag-of-words queries in parallel. Risk and Reward. We now focus our attention on risk and reward. We define risk as over-optimization of efectiveness in a way that improves the efectiveness of some queries at the expense of others. In order to measure risk, we employ the TRisk measure, and compare results for both AP and NDCG@10 with an α = 2. A simple visual aid in observing the risk-reward profiles of a run against a baseline can be achieved by ordering the baseline run in monotonically decreasing score by topic, which is then plotted against the efectiveness of the run to be compared.
Figure 3 shows the risk-reward profiles of four diferent highperforming retrieval models. Each system is compared against the BM25 baseline run. RM3 on the target collection, in general, performs better than the BM25 baseline, however, there are times where it drastically reduces efectiveness compared to the baseline. RM3ExtRRF appears to be operating with the most risk-sensitivity out of the four methods, as most of the data-points are above the baseline. The data-points that are below the baseline are only marginally worse. RMQV exhibits stronger potential gains than either of the RM approaches, with greater risk-sensitivity than a standard RM3 approach, but not quite as sensitive to risk as RM3-ExtRRF. Finally, while UQV-RRF demonstrates stronger improvements in efectiveness for many topics than the above approaches, again, it is not quite as risk-sensitive as RM3-ExtRRF.
Table 5 shows the risk exhibited by each system quantified using TRisk. A TRisk value greater than 2 indicates no significant risk of harming the baseline, while a value less than −2 indicates a statistically significant risk of harming the baseline, over a paired t-test for α = 2.
As shown in the discussion above for Figure 3, RM3-ExtRRF exhibits the least risk-sensitivity, followed by TREC Best and UQV-RRF. We see that while the retrieval efectiveness of RMQV is generally high, and comparable to other systems in Table 2, there is room for improving the risk dimension of our query sampling approach. It is, however, more efective and risk-sensitive than a traditional RM3 query expansion on the target corpus. We plan to explore the relationship between risk-sensitivity, fusion, and relevance modeling in future work.
AP TRisk α = 2 p-value TRisk α = 2 p-value 0.283 0.587 3.524 3.610 9.088 1.827 0.778 0.558 0.001 < 0.001
As observed by Benham and Culpepper [
Putting it all together. Figure 4 displays our query sampling approach RMQV in contrast with other retrieval models, with respect to their eficiency-efectiveness and eficiency-risk profiles. In both graphs, the closest data-point to the top-left is the best performing system across both dimensions. Although L2p is eficient, it exhibits high risk. The RMQV approach is only slightly less efective than RM3-ExtRRF, and is approximately three times faster. While the RM3-ExtRRF run exhibits strong risk-sensitivity, it is unclear how to deploy such an expensive process in a real search engine without significant improvements in scalability and eficiency. We, therefore, answer RQ2 in the afirmative, that our approach is fast enough RMQV 0 Topic to be usable in practice, produces efective runs, and reduces risk when compared to a strong baseline such as RM3. 5
In this work, we have shown how to combine relevance modeling with external corpora and rank fusion to build a prototype system which is eficient, and capable of achieving state-of-the-art efectiveness. Motivated by the premise that human curated query variations often cover the many aspects of a specific information need and provide efective results when combined with data fusion, we propose a fully automated surrogate to this manual process.
Our experiments show that weighted queries perform poorly when using dynamic pruning. To overcome this limitation, we construct multiple external relevance models, and automatically generate query variations using weighted random sampling process. Combining this idea with state-of-the-art indexing techniques, avoiding weighted queries, parallelization, and data fusion allow us to create an entirely new end-to-end search engine that is efective and eficient.
We place our prototype system in the context of strong baselines and show that the retrieval efectiveness is competitive with the state-of-the-art on a classically “hard” test collection — answering RQ1 in the afirmative. Finally, we show that when our approach RMQV is evaluated in the three contexts of efectiveness, eficiency and risk-sensitivity, it provides a competitive trade-of profile, answering RQ2 in the afirmative.
Acknowledgements. This work was supported by the Australian Research Council’s Discovery Projects Scheme (DP170102231), by an Australian Government Research Training Program Scholarship, and by a grant from the Mozilla Foundation.