Relevance Feedback Through Query Expansion and Term Reweighting

The interface that looks simplest on a search page, a button or a tap that says “this result was relevant”, hides the oldest feedback mechanism in information retrieval. The user’s judgement is turned into a new query, and the new query is run again. The name for the family of techniques is relevance feedback, and it is distinct from personalization: it does not learn a user model, it rewrites the current query using documents judged in the current session.

The vector-space form: Rocchio

Rocchio’s method, first described in the context of the SMART retrieval system, treats the query and every document as points in a vector space where each dimension is a term and each coordinate is a weight. Relevance feedback moves the query point. The new query vector is a weighted sum of three terms: the original query, the centroid of the documents the user judged relevant, and the centroid of the documents judged non-relevant, the last with a negative coefficient.

The usual statement is written as a sum with three coefficients, conventionally labelled alpha, beta, and gamma. Alpha keeps the original query from being drowned out; beta pulls the query toward the relevant documents; gamma pushes it away from the non-relevant ones. In the formulation Salton and Buckley described, the negative component uses the non-relevant centroid scaled by gamma, and the three coefficients are free parameters tuned on a corpus. The effect is a query that scores higher against documents resembling the judged-relevant set and lower against documents resembling the judged-non-relevant set.

The appeal of the vector form is that it requires nothing beyond what a vector-space ranking engine already stores. The relevant and non-relevant centroids are sums of the document vectors, and the new query is a linear combination, computable in time proportional to the number of judged documents times the vector dimension. No index rebuild and no model training is involved.

The probabilistic form: term reweighting

The probabilistic tradition, associated with the Robertson and Sparck Jones weighting behind BM25, does something more conservative. Instead of moving the query through space, it reweights the query’s terms using the distribution of those terms in the judged-relevant documents. A term that appears frequently in relevant documents and rarely in the collection gains weight; a term that is uniformly distributed gains nothing. The mechanism re-estimates the probability that a term indicates relevance, and feeds those revised probabilities back into the ranking function as modified term weights.

The two families differ in what they trust. Rocchio trusts the geometric position of the judged documents and can therefore pull in terms that never appeared in the original query, because the relevant centroid introduces them. Term reweighting trusts only the existing query terms and modulates their strength, so it cannot introduce new vocabulary. The difference matters when a query is under-specified: a two-word query like “memory allocator” judged against documents about slab allocation can only become richer under Rocchio, which can add “slab” and “arena” from the relevant centroid.

The Rocchio update can be written compactly. Given the original query vector q, the set R of documents judged relevant, and the set N judged non-relevant, the revised query is a weighted sum of the three centroids:

q' = alpha * q + (beta / |R|) * sum(d in R) d - (gamma / |N|) * sum(d in N) d

The division by the set sizes normalizes the centroids so that the number of judged documents does not inflate the update, and the three coefficients are the free parameters. In the values Salton and Buckley reported from their experiments, alpha and beta were both on the order of one, and gamma was smaller, reflecting the weaker evidential weight of a non-relevant judgement: a document the user rejects tells the system less than one the user accepts, because there are many reasons to pass over a document that have nothing to do with the query.

A small worked example fixes the behaviour. Take a vocabulary of three terms and a query vector q = (1, 1, 0) for the query “memory allocator”. One document is judged relevant, with vector d1 = (2, 1, 3), where the third coordinate is “slab”, and one is judged non-relevant, with vector d2 = (0, 3, 1). With alpha = 1, beta = 0.75, and gamma = 0.25, the revised query is (1, 1, 0) + 0.75·(2, 1, 3) − 0.25·(0, 3, 1) = (2.5, 1.0, 2.0). The new term “slab” has gone from absent to a weight of 2.0, on par with the original query terms; the term shared mostly with the non-relevant document has been damped from 1 toward 0.25, and the original two terms survive with their relative order roughly intact. Every effect claimed for the method is visible in this one update: vocabulary growth from the relevant centroid, damping from the non-relevant centroid, and preservation of the original query through alpha.

A further property of the formula is that negative weights are possible. When the non-relevant centroid dominates a coordinate, the revised weight can fall below zero, and a negative query weight actively penalizes documents containing that term. Implementations commonly truncate negative weights to zero, both because the underlying term-weighting schemes are defined for non-negative weights and because a term the user rejected as part of one bad document may still be a legitimate part of other relevant documents; the negative evidence is weaker than the positive, which is the same asymmetry the small gamma encodes.

Expansion without any user at all

The same machinery runs with a stand-in for the user’s judgement. Pseudo-relevance feedback, or blind relevance feedback, assumes that the top k documents returned for the initial query are relevant, then runs the expansion step on those. It costs a second retrieval pass and introduces a real hazard: when the initial ranking is poor, the expansion amplifies the error rather than correcting it. A query that retrieves off-topic documents at the top will have those off-topic terms injected into the expanded query, a failure called query drift. The classic mitigation is to cap the number of expansion terms, commonly on the order of ten to twenty, and to require each to occur in several of the pseudo-relevant documents rather than one.

The parameter k is a real tension. A small k gives the expansion few documents to learn from and risks a noisy centroid dominated by one bad result. A large k dilutes the relevance assumption, because the assumption that top results are relevant weakens with rank, and the bottom of a large k is less reliably relevant than its top. The practical range is usually between ten and fifty documents, chosen to balance a stable centroid against the weakening assumption, and the choice is revisited per collection because a collection with poorer baseline ranking tolerates a smaller k.

Query drift is the clearest failure mode in the whole family. Because expansion is run unattended in the pseudo-relevant case, a single bad top-10 set can poison the second pass, and the user sees a result list that is worse than the first, with no signal in the interface that a rewrite happened. Interactive relevance feedback is safer precisely because the judgement is human, but it is also scarce: users mark documents relevant far less often than they click, so the fully interactive form is rare outside retrieval tooling such as legal and research search.

The interaction layer and the retrieval layer meet here in one specific way. Relevance feedback is the mechanism by which the interface’s most explicit signal, the judgement, is converted into something the ranking engine can consume, a rewritten query. What the user experiences as a single refinement is, on the retrieval side, a second query whose term weights have been moved by a geometric or probabilistic rule. The choice between the two rules determines whether the system can only strengthen what the user already said, or can bring in vocabulary the user never typed.

There is a further interaction concern that the retrieval description does not surface: the interface must decide how the revised query relates to the original one. If the expanded query replaces the typed query outright, the user loses sight of what they originally asked, and a poor expansion cannot be audited. If the interface shows the expansion terms separately, the mechanism becomes legible and reversible, at the cost of surface area. This is the same tension that appears in zero-result relaxation, where a reformulation must be annotated rather than silently applied, and it is the reason feedback systems in retrieval tooling tend to expose the expanded terms while consumer search folds them invisibly into the rerun.