Pseudo-Relevance Feedback

Relevance feedback works, but searchers rarely provide the judgments it needs. Pseudo-relevance feedback, also called blind feedback, removes the searcher. Run the query, assume that the top $k$ results are relevant, apply a feedback method to them as if a searcher had judged them, and run the revised query. When the initial ranking is good, the top documents are mostly relevant, and the expansion terms drawn from them bring in relevant documents that share their vocabulary rather than the query's. When the initial ranking is poor, the method learns from the wrong documents and makes the results worse. That tension, a consistent average gain with a substantial minority of failures, defines the technique.

Methods

Probabilistic feedback. Croft and Harper (1979) proposed using the top-ranked documents to estimate the Binary Independence Model's probability $p_t$, which is unknown without judgments. The top $k$ documents stand in for the relevant set, and the Robertson–Spärck Jones weight is computed from them: $S = k$, and $s$ is the number of the top $k$ that contain the term. A query term found in all of the top documents gains weight and one found in few of them loses it, but no new terms are added.

Term-based expansion. More commonly, candidate terms from the top $k$ documents are scored by how frequent they are in those documents, often multiplied by their IDF. The highest-scoring terms are added to the query with a reduced weight. Rocchio's formula, with the top $k$ documents as the relevant set and no nonrelevant set, is one instance.

Local context analysis (Xu and Croft, 1996) chose expansion terms by how often they co-occurred with query terms in the top-ranked passages, which reduced the influence of off-topic parts of long documents.

Relevance models (Lavrenko and Croft, 2001) put pseudo-relevance feedback on a probabilistic footing within language modeling. They estimate a distribution over words for the relevant class, weighting each top document by how well it matches the query. The variant called RM3 (Abdul-Jaleel et al., 2004), which interpolates the estimated relevance model with the original query, became a standard strong baseline. Lin (2018) argued that neural ranking papers often reported gains over weak baselines, and showed that a well-tuned BM25 with RM3 matched or exceeded the neural results reported in two such papers.

The expansion used here, traced

The experiments below use a simple term-based expansion on top of BM25, defined in four steps:

1. Rank with BM25 ($k_1 = 1.2$, $b = 0.75$) and take the top $k$ documents.
2. Score every term in those documents by $\sum_{d \in \text{top } k} \frac{\mathit{tf}_{t,d}}{L_d} \times \mathrm{IDF}(t)$, its frequency in each top document divided by the document's length, summed, times its BM25 IDF. Dividing by length keeps one long document from dominating; multiplying by IDF demotes words that are frequent everywhere.
3. Take the $n$ highest-scoring terms that are not already in the query.
4. Score documents with BM25 over the original terms plus the expansion terms, the expansion terms' contributions multiplied by an expansion weight $w < 1$.

For Cranfield query 2, "what are the structural and aeroelastic problems associated with flight of high speed aircraft", with $k = 10$, $n = 10$, and $w = 0.5$, the top 10 documents contain 5 relevant ones. The highest-scoring terms in them are, rounded to three or four decimals:

The query's own terms dominate the top of the list, as they should, since BM25 retrieved the documents for containing them. Skipping those, the ten expansion terms are aerodynam, thermo, dure, model, research, plant, angular, airplan, wing, and control. Several are sensible. Others show the scoring's weak points: thermo, plant, and angular each occur in only one of the ten documents and qualify through a high IDF, and dure (from during) and research are generic words that happened to be frequent there. A rule that required a term to occur in at least two of the top documents would remove the first three. With the expansion, the query's average precision rises from 0.223 to 0.249.

An experiment on Cranfield

On the Cranfield collection, with the setup of comparing ranking models, the expansion above was run with four settings. Results across all 225 queries:

The $p$ values are from a paired randomization test against BM25 without feedback. Several patterns appear:

• The average gain is real but modest. The first setting, chosen in advance, raised MAP from 0.307 to 0.324, significant at the 0.05 level. The best of the four, 0.328, was selected on the same queries it is reported on, so it slightly overstates what a tuned setting would achieve on new queries.
• Many queries are harmed. In every setting, feedback hurt at least 90 of the 225 queries. The average conceals a large redistribution: many queries gain, many lose.
• Conservative settings work better. Fewer feedback documents, fewer expansion terms, and a lower weight for the added terms gave the best results. With expansion terms weighted equally with the original query, feedback harmed more queries than it helped, and the average gain was no longer significant.

When the assumption holds

The figure's right panel tests the premise of the method directly. Grouping queries by the number of relevant documents in their initial top 10:

The trend is there, but it is noisy. Queries with three or four relevant documents among the ten gain the most. Queries with none gain almost nothing on average (+0.004), yet 18 of the 32 improve: a document that is not judged relevant can still be about the right subject and supply useful terms. Queries with five or more gain less than those with four, perhaps because their initial rankings leave less room to improve. The connection between how good the initial ranking is and how much feedback helps is real but too weak to predict an individual query's fate, which is the difficulty that selective feedback, discussed below, runs into.

Tuning on held-out queries

To choose a setting fairly, the queries were split as in comparing ranking models into 112 development and 113 test queries. A grid of $k \in \{3, 5, 10, 20\}$, $n \in \{5, 10, 20, 30\}$, and $w \in \{0.25, 0.5, 1.0\}$ was evaluated on the development queries, and the best setting, $k = 3$, $n = 10$, $w = 0.5$, raised their MAP from 0.316 to 0.354. On the test queries, the same setting raised MAP from 0.297 to 0.317, with 59 queries improved and 49 harmed ($p = 0.060$). The first setting, chosen in advance, gave 0.306 on the same test queries. Tuning more than doubles the gain on unseen queries here, but the development gain (0.038) overstates the test gain (0.019) by a factor of two, and on 113 queries the test gain is not quite significant.

The grid shows the same conservatism as the table. Using 20 feedback documents lets in documents ranked 11 to 20, which on Cranfield are more often nonrelevant than relevant, and every extra expansion term drawn from them makes the query worse.

Probabilistic feedback without expansion

Croft and Harper's method, which reweights the query's own terms using the top $k$ as the relevant set and adds nothing, gives smaller gains. With BM25 (the RSJ weight replacing BM25's IDF), MAP rose from 0.307 to 0.318 with $k = 5$ ($p = 0.024$) and to 0.315 with $k = 10$ ($p = 0.12$). With the BIM, the setting it was designed for, MAP rose from 0.220 to 0.243 with $k = 10$ ($p < 0.001$), improving 137 queries and harming 75. As with explicit feedback, reweighting alone helps, but adding terms helps more.

Query drift

The failures have a common cause. If the top documents are not mostly relevant, the expansion terms come from whatever they are about, and the revised query moves toward that subject. This is query drift.

The worst case in the experiment was query 134, which asks "is it possible to correlate the results on the creep buckling of widely different structures within the framework of a single theory". It has two relevant documents. The initial BM25 ranking put one of them, document 1028 ("note on creep buckling of columns"), first, and the other at rank 42, for an average precision of $(1/1 + 2/42)/2 = 0.524$. The other nine documents of the top 10 were nonrelevant, among them four papers titled "principles of creep buckling weight-strength analysis" (one adding "of aircraft structures"), two other notes on the creep buckling of columns, and a unified theory of creep buckling under normal loads. Pseudo-relevance feedback treated all ten as relevant. The expansion terms, and how many of the top 10 contain each:

Eight of the ten terms come only from nonrelevant documents, and several of them, principl, weight, strength, and analysi, are the vocabulary of the weight-strength analysis papers. The revised query retrieved more of those: after feedback, the top 7 are all nonrelevant, document 1028 falls to rank 8, and the second relevant document moves only from 42 to 39. Average precision falls to $(1/8 + 2/39)/2 = 0.088$. The query has drifted from correlating creep buckling across structures toward the design of structures for weight and strength, a neighbouring subject that its top documents happened to share.

Even successful expansions carry noise, as the trace of query 2 above showed: about half of its expansion terms were generic or came from a single document. Feedback succeeds when the useful terms outweigh the noise, which is likelier when the top documents agree with one another and with the query.

The relevance feedback article's interactive plane shows the geometry: marking the nonrelevant documents as relevant there, as pseudo-relevance feedback in effect does when its assumption fails, turns the query toward them instead of away.

When to apply it

Since pseudo-relevance feedback helps queries whose initial results are good and hurts queries whose initial results are poor, the ideal system would apply it selectively. Query performance prediction estimates, without judgments, how good a query's initial results are. One example is the clarity score of Cronen-Townsend, Zhou, and Croft (2002), which measures how different the language of the top documents is from the collection as a whole. Such predictions can decide whether to apply feedback or how strongly to weight it. In practice, predictions are noisy enough that many systems apply feedback uniformly with conservative settings, accepting some losses for the average gain. The Cranfield grouping above illustrates why: even knowing the true number of relevant documents in the top 10, which no predictor does, separates the winners from the losers only weakly.

Pseudo-relevance feedback has a cost as well: a second retrieval with a query several times longer, which can take longer than the first retrieval did. In systems that rerank with neural models, its role has partly shifted. It may be used to expand queries before first-stage retrieval, where improving recall matters most. Or it may be replaced by learned query or document expansion.

References

• Abdul-Jaleel, N., Allan, J., Croft, W. B., Diaz, F., Larkey, L., Li, X., Smucker, M. D., and Wade, C. (2004). UMass at TREC 2004: Novelty and HARD. In Proceedings of TREC 2004.
• Croft, W. B., and Harper, D. J. (1979). Using probabilistic models of document retrieval without relevance information. Journal of Documentation, 35(4), 285–295.
• Cronen-Townsend, S., Zhou, Y., and Croft, W. B. (2002). Predicting query performance. In Proceedings of SIGIR 2002, 299–306.
• Lavrenko, V., and Croft, W. B. (2001). Relevance-based language models. In Proceedings of SIGIR 2001, 120–127.
• Lin, J. (2018). The neural hype and comparisons against weak baselines. SIGIR Forum, 52(2), 40–51.
• Xu, J., and Croft, W. B. (1996). Query expansion using local and global document analysis. In Proceedings of SIGIR 1996, 4–11.