Pseudo-Relevance Feedback and the Rocchio Drift Problem

A user’s first query is a guess. Relevance feedback closes the loop by having the user mark which results were right and re-running with the corrected query. Pseudo-relevance feedback removes the user: it assumes the top $k$ results of the first pass are relevant, extracts terms from them, and re-weights the query accordingly. The assumption is wrong often enough that the technique’s behaviour is dominated by what happens when it is wrong, which is the interesting part.

The mechanism is simple enough to implement in an afternoon. The reason it is not universally deployed is that the failure mode is severe and the conditions under which it helps are narrower than the conditions under which it is tried.

The vector-space form and its two weights

Rocchio’s formulation, from the SMART system, expresses the revised query as a weighted combination of the original query vector and the centroid of judged-relevant documents, minus a term for judged-irrelevant ones:

$$q’ = \alpha, q + \beta \sum_{d \in R} \frac{d}{|R|} - \gamma \sum_{d \in N} \frac{d}{|N|}$$

In pseudo-relevance mode there are no judged documents, so $R$ is the top $k$ retrieved results and $N$ is empty, which drops the negative term entirely. The two surviving weights do specific jobs. $\alpha$ controls how much of the original query survives, and $\beta$ controls how much mass the feedback documents contribute.

With $\alpha$ small, the rewritten query is essentially the centroid of the top $k$, and any bias in that set is inherited wholesale. With $\alpha$ large, the rewrite is a mild perturbation and cannot fix a query whose initial terms are wrong. Values in the published literature are typically in the range where $\alpha$ is a fraction and $\beta$ is comparable, and the exact numbers are dataset-dependent in a way that has never been resolved into a rule.

The negative term is what makes true relevance feedback more reliable than pseudo-relevance: the user’s explicit rejection of documents is the strongest available evidence against a term, and pseudo-relevance has no equivalent because it never identifies a document as bad.

The language-model form and why interpolation is the norm

The alternative formulation treats feedback as a distribution rather than a vector. Given the top $k$ documents, a feedback model is estimated from their terms, and the query model is interpolated with it:

$$P(w \mid q’) = (1-\lambda), P(w \mid q) + \lambda, P(w \mid F)$$

where $F$ is the feedback set and $\lambda$ is the interpolation weight. This is RM3, and the interpolation is the important structural difference from Rocchio. Because the query model remains a proper distribution and the feedback model is mixed in, every original query term retains non-zero probability. A term the feedback set never contains is not deleted; it is merely diluted. Rocchio’s vector form can in principle drop a term if $\alpha$ is small enough and the centroid has zero weight on it, though most implementations never fully remove original terms.

The feedback model itself needs smoothing. A maximum-likelihood estimate over the top $k$ documents assigns high probability to whatever those documents repeat, which includes the boilerplate of the collection: navigation text, copyright lines, and the template sentences that appear on every page. Smoothing against the collection model, or filtering terms by a document-frequency bound, is what keeps the rewrite from being dominated by template vocabulary.

A term-selection step is usually applied on top: take the top $m$ terms by the feedback model’s weight, discard the rest, and keep the query at a manageable size. The cutoff $m$ is another parameter, typically in the tens, and it trades the chance of including a useful new term against the cost of adding noise to the scorer’s input.

from collections import Counter

def rm3(query_terms, feedback_docs, collection, mu=2000.0, top_m=20, lam=0.5):
    """Dirichlet-smoothed feedback model, interpolated with the query model.
    feedback_docs: list of per-document term counts; collection: counts over the index."""
    n_coll = sum(collection.values())

    fb = Counter()
    for doc in feedback_docs:
        length = sum(doc.values())
        for w, c in doc.items():
            # Dirichlet prior: a term rare in the collection barely survives smoothing
            fb[w] += (c + mu * collection[w] / n_coll) / (length + mu)
    total_fb = sum(fb.values())          # sum of per-document estimates, renormalised

    q = Counter(query_terms)
    n_q = sum(q.values())

    mixed = {}
    for w in set(fb) | set(q):
        pq = q[w] / n_q
        pf = fb[w] / total_fb
        mixed[w] = (1 - lam) * pq + lam * pf
    return sorted(mixed.items(), key=lambda kv: -kv[1])[:top_m]

The Dirichlet prior is what prevents a term appearing once in one feedback document from being treated as more probable than a term appearing once in the query. With a large $\mu$, the feedback estimate is pulled toward the collection distribution and the rewrite becomes conservative.

Drift, and why the failure is not graceful

The central failure is that the top $k$ of a bad query are bad in a correlated way. If the query is ambiguous and the initial ranking picked the wrong sense, the feedback documents all belong to the wrong sense, the expanded terms all reinforce that sense, and the second-pass ranking is more confidently wrong than the first.

This is not a small effect. It is the reason pseudo-relevance feedback is applied selectively rather than universally. The published gains are real but they are averages over query sets that include queries where the technique hurts badly.

Several mitigations reduce the damage without eliminating it.

Small $k$. A feedback set of five to ten documents is less likely to contain a coherent wrong cluster than a set of fifty, and the centroid is correspondingly less biased. The cost is a noisier estimate of the feedback distribution.

Query-drift detection. The divergence between the original query model and the rewritten one can be computed directly, and a rewrite whose divergence exceeds a threshold can be rejected. This is a guard rather than a fix, and it needs a threshold, but it converts a silent failure into a no-op.

Term-level guards. A term is only added if its weight in the feedback model exceeds its weight in the collection by some margin, which is a document-frequency test. Terms that are merely common in the collection never qualify.

Prediction-gated application. Applying feedback only to queries predicted hard, using the pre-retrieval prediction signals, concentrates the risk where the initial ranking was weak anyway.

Feedback and diversity pull in opposite directions

A feedback rewrite moves the query toward the centroid of the top results, which makes it more specific. That is the intended effect on an under-specified query and the wrong effect on one that is already narrow, where the centroid adds terms that exclude the long tail of relevant documents.

The interaction with diversification is direct: a set of results that has been diversified to cover several senses produces a centroid that mixes those senses, and the rewrite becomes incoherent. Running feedback before diversification and diversification after is the ordering that keeps each step’s input well-defined.

The same tension appears with the phrase structure discussed under query segmentation. Feedback models are usually estimated over unigrams, so a rewrite adds individual terms without their adjacency relations, and a query that was correctly segmented loses that structure in the expansion. Restricting feedback terms to those that co-occur as phrases with the query’s existing segments is a way to preserve it, at the cost of a more expensive estimation.

What the parameters actually trade

Four parameters govern the behaviour, and each has a clear axis.

The feedback set size $k$ trades estimate variance against bias: small sets are noisy but less likely to be coherently wrong.

The interpolation weight $\lambda$ trades the influence of the rewrite against the preservation of the original query. Setting it to zero disables feedback; setting it near one discards the user’s words.

The term cutoff $m$ trades scorer cost and noise against the chance of including a useful expansion.

The smoothing strength trades the influence of collection frequency against the influence of the feedback documents’ raw counts.

There is no configuration that is right across query types, which is why the technique is best understood as a conditional rewrite rather than a fixed stage in the pipeline. The implementations that work reliably are the ones that decide per query whether to apply it at all, and that keep the original query available as a fallback when the rewrite reduces the result count or moves the ranking implausibly far.