Relevance Feedback

Searchers often find it hard to write a query that describes what they want, but easy to recognize a good document when they see one. Relevance feedback exploits that asymmetry. The system shows initial results, the searcher marks some of them relevant or not, and the system uses those judgments to build a better query and search again. The judgments supply what the original query lacked: examples of the vocabulary that relevant documents actually use.

Relevance feedback dates from the SMART experiments of the 1960s, has been effective in experiment after experiment, and connects the course's two families of models. This article covers how feedback works in each, with a small geometric example for the vector space model and a real query for the probabilistic one, then how to evaluate feedback fairly, and reports experiments on the Cranfield collection.

Two ways to use judgments

Judgments can improve a query in two ways:

• Reweighting changes the weights of the terms already in the query. A query term found in most of the judged relevant documents should count for more, and one found mostly in nonrelevant documents for less.
• Expansion adds new terms drawn from the relevant documents. If the relevant documents keep using nozzle and thrust while the query said rocket engine, adding those words lets the query find relevant documents that never use the original ones. That addresses vocabulary mismatch directly.

In the vector space model: Rocchio

Rocchio's method (Rocchio, 1971) treats the query as a vector in the same space as the documents and moves it. The revised query is

$$\vec{q}_m = \alpha\, \vec{q}_0 + \beta\, \frac{1}{\lvert D_r \rvert} \sum_{\vec{d} \in D_r} \vec{d} \;-\; \gamma\, \frac{1}{\lvert D_{nr} \rvert} \sum_{\vec{d} \in D_{nr}} \vec{d},$$

where $\vec{q}_0$ is the original query, $D_r$ and $D_{nr}$ are the documents judged relevant and nonrelevant, and $\alpha$, $\beta$, $\gamma$ set how much each part counts. The two sums divided by the set sizes are centroids, the average vectors of the judged relevant and nonrelevant documents. Typical values are $\alpha = 1$, $\beta = 0.75$, $\gamma = 0.15$, and negative components of the result are set to zero (Manning, Raghavan, and Schütze, 2008, §9.1.1). The article on the limits of the vector space model works an example in four dimensions, with the query jaguar drifting toward cat. Because the centroids contain every term of the judged documents, Rocchio both reweights and expands. In practice the expansion is usually limited to the highest-weighted new terms.

Rocchio in two dimensions

With only two terms, the whole method can be drawn. Let the axes be the weights of rocket and nozzle. The searcher typed rocket, so $\vec{q}_0 = (1, 0)$. The system returned four documents, the searcher judged them, and two more documents have not been seen yet:

The relevant documents are about nozzles; the nonrelevant ones mention rockets and little else. Two unseen documents complete the example: U1, which resembles the relevant ones, and U2, which resembles the nonrelevant ones. The original query ranks U2 far above U1.

The computation, with $\alpha = 1$, $\beta = 0.75$, $\gamma = 0.15$:

1. Relevant centroid: $\frac{1}{2}\left((0.6, 0.8) + (0.2, 0.9)\right) = (0.40, 0.85)$.
2. Nonrelevant centroid: $\frac{1}{2}\left((0.9, 0.1) + (0.7, 0.0)\right) = (0.80, 0.05)$.
3. $\vec{q}_m = (1, 0) + 0.75\,(0.40, 0.85) - 0.15\,(0.80, 0.05) = (1 + 0.30 - 0.12,\; 0 + 0.6375 - 0.0075) = (1.18, 0.63)$.

The revised query points 28.1 degrees above the rocket axis. Its cosine with U1 rises from 0.141 to 0.591, while U2's changes from 0.936 to 0.991. In this example U2 stays ahead: one round with these weights turns the query part of the way. What has changed is that nozzle, a word the searcher never typed, now carries 0.63 of weight, so a document that uses only nozzle is no longer invisible.

Two properties of the formula are visible here:

• Only the ratios matter for ranking. Documents are ranked by cosine, which ignores the query vector's length. Multiplying $\alpha$, $\beta$, and $\gamma$ by the same number changes the length of $\vec{q}_m$ but not its direction, so only $\beta/\alpha$ and $\gamma/\alpha$ affect the results. With $\alpha = 1$, $\beta = 0.5$, $\gamma = 0.5$ the query is $(0.80, 0.40)$, at 26.6 degrees.
• Negative feedback is weak by design. The nonrelevant centroid lies almost on the original query, so subtracting it mostly shortens the query along the rocket axis, which tilts it only slightly. With $\gamma = 0$ the angle is 26.1 degrees instead of 28.1. Nonrelevant documents can be wrong in many different ways, so their centroid is a poor description of what to avoid. That is one reason $\gamma$ is usually set much smaller than $\beta$.

Ide's variants

Rocchio divides each sum by the number of documents in it. Ide (1971) proposed adding the document vectors without that division. The two forms below follow the descriptions and names in Salton and Buckley's later review (1990, p. 292 and Table 3):

• Ide regular: $\vec{q}_m = \vec{q}_0 + \sum_{\vec{d} \in D_r} \vec{d} - \sum_{\vec{d} \in D_{nr}} \vec{d}$.
• Ide dec-hi: $\vec{q}_m = \vec{q}_0 + \sum_{\vec{d} \in D_r} \vec{d} - \vec{d}_{\mathrm{top}}$, where $\vec{d}_{\mathrm{top}}$ is the highest-ranked nonrelevant document. All relevant documents are used, but only one nonrelevant one, which gives "a definite point in the vector space from which the new feedback query is removed" (Salton and Buckley, 1990, p. 292).

In the plane, Ide regular gives $(1, 0) + (0.8, 1.7) - (1.6, 0.1) = (0.2, 1.6)$, at 82.9 degrees: two relevant documents added at full strength overwhelm a query of length 1. Ide dec-hi subtracts only N2, the nonrelevant document the original query ranked first, giving $(1.1, 1.7)$ at 57.1 degrees. Both put U1 above U2. Without the division, the more documents are judged, the less the original query counts, so Ide's methods trust the judgments more than Rocchio's defaults do.

Salton and Buckley (1990) compared twelve feedback methods on six collections, one of them Cranfield, evaluating each on the residual collection described below. Ide dec-hi was the best overall method; on Cranfield it raised average precision at three recall levels from 0.116 for the initial search to 0.301 (their Table 4). They noted that the method is also cheap, since only one nonrelevant document must be processed.

In the probabilistic model: the RSJ weight

The Binary Independence Model was designed for feedback. Its Robertson–Spärck Jones term weight, derived in that article, is

$$c_t = \ln \frac{(s + \tfrac12) \,/\, (S - s + \tfrac12)}{(\mathrm{df}_t - s + \tfrac12) \,/\, (N - \mathrm{df}_t - S + s + \tfrac12)},$$

where $S$ is the number of documents judged relevant and $s$ the number of those that contain the term. Without judgments, $S = s = 0$ and the weight reduces to $\ln \frac{N - \mathrm{df}_t + 0.5}{\mathrm{df}_t + 0.5}$, an IDF. With judgments, terms that occur in many relevant documents gain weight and terms that occur in none lose it. The BIM article works the weight with full knowledge of a query's relevant documents. In feedback the judgments are partial: only what the searcher saw. In BM25, the same weight replaces the IDF component.

A worked example: Cranfield query 180

Query 180 of the Cranfield collection asks "how does scale height vary with altitude in an atmosphere". It analyzes to seven terms, how, doe, scale, height, vari, altitud, and atmospher. The collection has $N = 1{,}400$ documents, and 7 are relevant to this query. The BIM without judgments ranks them; the searcher judges the top 10 and finds three relevant (documents 617, 616, and 622), so $S = 3$. For each query term, natural logarithms, rounded to three decimals:

Take height as a check: $\frac{3.5/0.5}{31.5/1{,}366.5} = 7 \times 43.38 = 303.7$, and $\ln 303.7 = 5.716$. Before feedback, how and doe (the stem of does) had the two highest weights of all, because they are rare in a collection of technical abstracts: an IDF has no way to tell a rare function word from a rare content word. The judgments tell them apart. A term in every judged relevant document gains about 2.0, and a term in none loses about 1.9, whatever its document frequency, because the change is driven by the first half of the log odds ratio, $\ln \frac{s + 0.5}{S - s + 0.5}$, which goes from $\ln 1 = 0$ to $\ln 7 = 1.95$ or $\ln(1/7) = -1.95$. Altitud drops a little, since only one of the three relevant documents uses it.

The effect shows on the documents the searcher has not seen. Of the four remaining relevant documents, document 621 moves from rank 10 to rank 1 of the residual ranking; average precision over the unseen documents rises from 0.086 to 0.306.

Choosing expansion terms

Reweighting cannot find a relevant document that shares no words with the query. For expansion, candidate terms from the relevant documents must be ranked. Robertson (1990) analyzed term selection and proposed ranking candidates by $c_t (p_t - u_t)$, a term's weight times the difference between its probabilities in relevant and nonrelevant documents. The Okapi experiments used an approximation, the offer weight $s \times c_t$, which balances how strongly a term indicates relevance against how many relevant documents it would help find. The top 10 to 30 candidates are typically added.

For query 180, the ten best candidates from the three judged relevant documents are:

The judged documents are about measuring the density of the upper atmosphere from satellite orbits, and the candidates say so: perigee, orbit, satellite, density. None of these appear in the query. The offer weight favors terms found in all three documents: nine of the ten have $s = 3$, and a term in only two needs a much higher weight to compete, as 200 (presumably an altitude in kilometres, and in only 7 documents) does. The list also shows the method's weakness: generic words such as chang and determin qualify simply by being in every judged document.

Evaluating feedback fairly

Measuring feedback naively overstates it. After feedback, the documents the searcher judged relevant will rank at the top of the new results, so measures computed over the whole ranking improve even if the new query finds nothing new. The searcher has already seen those documents, so their reappearance is worth nothing.

The standard remedy is residual collection evaluation (Manning, Raghavan, and Schütze, 2008, §9.1.5). Remove the documents the searcher judged from the collection, and evaluate both the original ranking and the feedback ranking on what remains. The question becomes whether feedback helps find relevant documents the searcher has not yet seen. Residual scores are lower than full-collection scores, because the easiest relevant documents have been removed, so only before-and-after comparisons on the same residual collection are meaningful. In query 180, the residual collection is the 1,390 documents outside the top 10, and the four relevant documents among them.

Experiments on Cranfield

The Cranfield collection has 1,400 documents and 225 queries with relevance judgments. Each query was run with three models, using the setup of comparing ranking models. The judgments for the top 10 documents were then treated as the searcher's feedback, and feedback queries were evaluated on the residual collection:

All three improvements are statistically significant by a paired randomization test (see significance testing).

A second set of runs varies the method within each family, starting from the same initial rankings:

The expansion terms are added with their RSJ weights as BM25 term weights. MAP values are rounded to three decimals, and all the changes are significant at the 0.01 level. Several observations follow:

• Feedback works. Even reweighting alone, without adding any terms, raises the BIM's residual effectiveness by nearly half, and BM25's by more than a third.
• Expansion matters more than reweighting. Within BM25, adding the ten best offer-weight terms to the reweighted query raises residual MAP from 0.157 to 0.204 ($p = 0.001$), and twenty terms reach 0.216. Rocchio, which expands with every term of the relevant documents, more than doubles residual MAP. On technical abstracts, where relevant documents use vocabulary the query may not, new terms are the larger gain.
• Negative feedback adds little. Rocchio with $\gamma = 0$ reaches the same residual MAP as with $\gamma = 0.15$. The difference is in the counts. With $\gamma = 0$, a query whose top 10 contains no relevant document (34 of the 225 under TF-IDF) is left unchanged, and 59 queries in all are neither improved nor harmed. With $\gamma = 0.15$, those queries are pushed away from their nonrelevant documents, and the counts become 151 improved and 45 harmed: 7 more improved, 23 more harmed. Moving away from what is known to be wrong, without knowing what is right, is more often harmful than helpful.
• How much to trust the judgments depends on how many are negative. Ide dec-hi, using one nonrelevant document, comes close to Rocchio, as Salton and Buckley found. Ide regular gains far less (0.158) and harms more queries than it helps, unlike in their experiments. Cranfield's top 10 contains on average 2.3 relevant documents and 7.7 nonrelevant ones (TF-IDF's precision at 10 is 0.228), and Ide regular subtracts all of the nonrelevant ones at full strength, which cancels much of the relevant evidence. Their weighting of documents and queries also differed from the lnc.ltc weighting used here.
• Feedback needs something to learn from. For 56 of the 225 queries, the BIM's top 10 contained no relevant document. The RSJ reweighting then has no positive examples, falls back to the IDF weights, and leaves the ranking unchanged.

Why searchers rarely use it

Despite its effectiveness, explicit relevance feedback is rarely used in practice. A study of the Excite search engine's logs found that few searchers used its "more like this" feedback option even though it was offered with every result (Spink, Jansen, and Ozmultu, 2000). Judging documents takes effort, and searchers prefer to reformulate the query themselves. Feedback queries are also long, which makes them slower to evaluate. And searchers may not understand why the new results differ, which reduces trust.

The idea survived in less demanding forms:

• Implicit feedback infers judgments from behavior, such as clicks and dwell time, rather than asking for them (see online evaluation).
• Interactive query expansion suggests expansion terms, or related queries, and lets the searcher choose.
• Pseudo-relevance feedback assumes the top results are relevant and applies feedback with no searcher involvement at all.
• Professional search still uses explicit feedback heavily. Technology-assisted review in legal discovery is relevance feedback run until a recall target is met (see search in professional domains).

References

• Ide, E. (1971). New experiments in relevance feedback. In G. Salton (Ed.), The SMART Retrieval System: Experiments in Automatic Document Processing, 337–354. Prentice-Hall.
• Manning, C. D., Raghavan, P., and Schütze, H. (2008). Introduction to Information Retrieval, chapter 9. Cambridge University Press.
• Robertson, S. E. (1990). On term selection for query expansion. Journal of Documentation, 46(4), 359–364.
• Robertson, S. E., and Spärck Jones, K. (1976). Relevance weighting of search terms. Journal of the American Society for Information Science, 27(3), 129–146.
• Rocchio, J. J. (1971). Relevance feedback in information retrieval. In G. Salton (Ed.), The SMART Retrieval System: Experiments in Automatic Document Processing, 313–323. Prentice-Hall.
• Salton, G., and Buckley, C. (1990). Improving retrieval performance by relevance feedback. Journal of the American Society for Information Science, 41(4), 288–297.
• Spink, A., Jansen, B. J., and Ozmultu, H. C. (2000). Use of query reformulation and relevance feedback by Excite users. Internet Research, 10(4), 317–328.