Query Refinement and Relevance Feedback

Search engines have to deal with synonymy.

If we do not take into account synonyms of a query, we miss matches with many relevant documents; a mismatch between query and document terms.

Refining a query is a common user strategy. Search engines nowadays try to help you with finding a good query in a different ways.

Query Refinement

Global approaches:

  • Reformulate query terms independent of a specific query and its relevant documents

Local approaches:

  • Adjust the query relative to the documents that initially match the query.

Global approaches

Take a thesaurus such as MeSH or WordNet, and then automatically expand the query with synonyms.

Imagine someone having neck pain. There's medical terms for that, which the user may not know. Expanding the query with synonyms may then help the user find what she is looking for.

Performance:

  • Good results in specific domains, e.g. medical or legal
  • Increases recall
  • But may significantly decrease precision
    • Ambiguity in terms will lead to many synonyms being created that are not necessarily relevant

Issues:

  • Context is not taken into account (so also not used for resolving ambiguity)
    • See above; this is another reason why ambiguity is such a problem
  • There are plenty of out of vocabulary meanings, e.g. product names
  • Expensive to create and maintain a manual thesaurus

Q: Can you distinguish global and local query refinement?

Q: What does global query refinement usually do to precision and recall?

Q: Is query expansion a global or a local approach to query refinement?

Local approaches: Relevance Feedback

  • Relevance feedback
    • Rocchio Algorithm
  • Pseudo relevance feedback

Involves user feedback in the retrieval process.

Users do not know the whole collection, so it may be hard for them to formulate a good query. So the idea is to instead just start somewhere and improve on the query through iterations.

Procedure:

  • User starts with short, simple query
  • User marks some results as relevant or non-relevant
  • The system computes a better representation of the information need based on feedback
  • System displays a revised set of retrieval results.

Roccio algorithm

Uses a vector space model, and the concept of centroids. Similarity between two vectors is then their dot product.

The centroid is in this case the center of mass of all vector representations in a collection of documents.

$\vec{\mu}(C)=\frac{1}{|C|}\sum_{\vec{d}\in C}d$ where $\mu$ and $d$ are both vectors.

I.e. the centroid $\mu$ is just the average of all vectors. We can compute a centroid of all relevant documents and a centroid of the non-relevant documents.

Roccio algorithm:

  • Find a query vector $q_m$ that maximizes similarity with relevant doc while minimizing similarity with non-relevant doc
    • We refine the query by moving closer to the centroid of the relevant documents
    • And by moving away from the centroid of the irrelevant documents.
  • Starting with initial query $q_0$, the user marks relevant and irrelevant documents.

$$\alpha\vec{q_0} + \beta\frac{1}{|D_r}\sum_{\vec{d_j} \in D_r}\vec{d_j} - \gamma \frac{1}{|D_{nr}} \sum_{\vec{d_j} \in D_{nr}} \vec{d_j}$$

Recall: why are we "finding" a query vector? Because we start with the original user query and we want to refine it such that it finds documents that the user deems to be relevant.

$\alpha$ weighs our previous query vector, $\beta$ weights the relevant centroid, $\gamma$ weighs the irrelevant centroid.

Setting parameters:

  • Usually you prefer to reward good moves more than punishing the bad moves, so $\beta > \gamma$
  • If you have a lot of relevant judgments for the next iteration, then you also want these to be weighed relatively strongly so that they can appropriately overrule the previous estimate, i.e. we want $\frac{\beta}{\gamma} > \alpha$.
  • Note that negative term weights are ignored and just set to zero.

Pseudo relevance feedback

In the previous procedure, we require explicit manual feedback of the user.

In pseudo relevance feedback, we do not require explicit feedback but simulate it.

  • Retrieve a ranked list of hits
  • Assume top-k documents are relevant
  • Do the relevance feedback loop
    • But note that we now only have positive feedback, i.e. judgments on relative feedback
    • I.e. if we run Rocchio we need $\gamma=0$.

This works well on average. But why can we just assume the top-k documents are relevant?

Relevant documents to the query often talk about the same thing; they are mutually more coherent; they have a coherent set of terms. Irrelevant documents instead can be expected to discuss different things. Faegheh suggests that we can see the noise of irrelevant documents returned in the top-k ranking as a form of regularization. Would this then also help combat query drift?

Issue:

If we iterate this process we may have query drift; at some point the created query may not be related anymore to the original query.

Q: What is query drift and for what is it a problem?

Q: What is a downside of pseudo-relevance feedback?

Kullback-Leibner Divergence Retrieval Model

Interesting observation: the query likelihood model discussed in lecture 2 can be seen as a special case of a KL Divergence model, namely one that drops parts related to the query language model.

The parts that relate to documents are the same and they are thus rank equivalent.

KL Divergence Measures the difference between two probability distributions. Note that this is not symmetric!

We can use KL divergence for ranking. When we take the negative of the KL Divergence we get a ranking; we want the least different to score higher.

If you write out the negative KL-divergence between the query language model $M_q$ and a document language model $M_d$ you can derive the query likelihood formula (when we ignore and drop the parts that do not depend on documents).

I.e. start with

$$D( M_q || M_d) = - \sum_{w \in V}P(w|M_q)log(\frac{P(w|M_q)}{Q(w|M_d)})$$

Split the log and then drop the part that depends on the query model.

Language based relevance model

We have thus seen that query likelihood and KL between $M_q$ and $M_d$ are very similar. Based on that we can build the following procedure for pseudo-relevance, but now not using Roccio but using language models:

  1. Rank documents using the query likelihood for the query
    • Document language model probabilities $P(w|M_d)$ use Dirichlet smoothing
  2. Select some number of top-ranked documents for C
    • C can be the whole collection, but top 10-50 are most influential for estimating $P(W_q)$ anyways
    • Also results in substantial speed up
  3. Calculate relevance model probabilities P(w|Mq) using smoothed estimate for P(w,q1,..,qn).
    • Recall, I think we just need to compute this part because this was missing from the query likelihood
  4. Rank documents again using the KL-divergence score (using 10-25 of highest-probability words from step 3)
    • Again, the highest-probability words matter most; so using just those really speeds things up.

the query likelihood score for the document D. This means that the estimate for P(w, q1. . . qn) is simply a weighted average of the language model probabilities for w in a set of documents, where the weights are the query likelihood scores for those documents.Ranking based on relevance models actually requires two passes. The first pass ranks documents using query likelihood to obtain the weights that are needed for relevance model estimation. In the second pass, we use KL-divergence to rank documents by comparing the relevance model and the document model. Note also that we are in effect adding words to the query by smoothing the relevance model using documents that are similar to the query. Many words that had zero probabilities in the relevance model based on query frequency estimates will now have non-zero values. What we are describing here is exactly the pseudo-relevance feedback process described in section 6.2.4. In other words, relevance models pro-vide a formal retrieval model for pseudo-relevance feedback and query expansion. (SEIRiP, 264)

Q: How can relevance models be seen as a process of query expansion and smoothing?

In summary, ranking by comparing a model of the query to a model of the document using KL-divergence is a generalization of query likelihood scoring. (265)