Result improvement (relevance feedback)¶

Users have rewritten queries by themselves to improve results
- Manual modification
- Browsing (find similar pages, requires clustering)
- Faceted search (use filters, incremental boolean query)
Query refinement approaches
- Global methods (independent from query/results)
  - Query expansion/reformulation
  - Spelling correction
- Local methods (depend on query/results)
  - Relevance feedback
  - Pseudo-relevance feedback / blind relevance feedback
  - Indirect relevance feedback
Focus: Local methods

Basics¶

Idea
- Involve user into the IR process
- Improve result set
Procedure
1. Issue query
2. System returns initial result set
3. User marks some documents as relevant/irrelevant
4. System re-computes result set
5. System shows the improved result set
When is RF useful
- User has basic knowledge (can pose initial query)
- Documents should cluster (Rocchio)
When isn’t RF useful
- Misspellings
- Cross-language IR (german and english documents about the same topic are unlikely close to each other)
- Synonyms / Searcher-document-vocabulary-mismatch

1971 by Salton (SMART system)
Idea: Move query vector into the direction of relevant documents
User feedback as classification for relevant/non-relevant
Assumption: Cluster hypothesis for documents
Advantages
- Intuitive approach
- Positive and negative feedback are exploited
- Can be combined with pseudo-relevance feedback
Disadvantages
- Initial query must have some quality
- Cluster hypothesis
- Hard to explain to user

Vector space model
Returned documents \( C \)
Relevant documents \( C_r \) (rated by user)
Non-relevant documents \( C_{nr} \) (rated by user)
Note: \( C_r \cup C_{nr} \subset C \)
Use normalized vectors (important)
Find optimal query that maximizes the similarity to the relevant documents und minimizes the similarity to the non-relevant documents \( q_{opt} = \arg\max_q(sim(q, C_r) - sim(q, C_{nr})) \)
Using the cosine similarity: \( q_{opt}=\arg\max_q(\frac{1}{|C_r|}\sum_{d\in C_r} \sum_{i=1}^m q_i d_i - \frac{1}{|C_{nr}|}\sum_{d\in C_{nr}} \sum_{i=1}^m q_i d_i) \)
Solve problem using Lagrange multipliers

Use Lagrange multipliers
Function to maximize:
- \( f(q_{opt,1},...,q_{opt,n}) = \frac{1}{|C_r|}\sum_{d\in C_r} \sum_{i=1}^m q_i d_i - \frac{1}{|C_{nr}|}\sum_{d\in C_{nr}} \sum_{i=1}^m q_i d_i \)
Condition \( |q_{opt}|=1 \):
- \( g(q_{opt,1},...,q_{opt,n})= \sum_{i=1}^m q_i^2 - 1 = 0 \)
Lagrangian function
- \( \mathcal{L}(q_{opt,1},...,q_{opt,n}, \lambda) = f(q_{opt,1},...,q_{opt,n}) - \lambda g(q_{opt,1},...,q_{opt,n}) \)
Solve \( \mathcal{L}'(q, \lambda) = 0 \)
- Use partial derivates w.r.t. \( q_1,...,q_n, \lambda \)
- \( q_{opt}(\lambda) = \frac{1}{2\lambda} (\frac{1}{|C_r|}\sum_{d\in C_r} d - \frac{1}{|C_{nr}|}\sum_{d\in C_{nr}} d) \)
- \( q_{opt}(\lambda) = \frac{q_{opt}(\lambda)}{||q_{opt}(\lambda)||} \)
Result: \( q_{opt} \) is scaled difference vector between centroids of \( C_r \) and \( C_{nr} \)

Problem: User rating depends on initial result set
Solution: Modify query vector
- \( q_m = \alpha q_0 + \beta \frac{1}{|D_r|} \sum_{d_j\in D_r} d_j - \gamma \frac{1}{|D_{nr}|} \sum_{d_j\in D_{nr}} d_j \)
\( D_r, D_{nr} \): relevant/non-relevant documents rated by user
\( \alpha,\beta,\gamma \): Weighting factors
Many user ratings: High \( \beta, \gamma>\alpha \)
Positive feedback more valuable: \( \beta>\gamma \)
Common values:
- \( \alpha = 1.0 \)
- \( \beta = 0.75 \)
- \( \gamma = 0.15 \)

Create Naive Bayes probabilistic classifier (?)
Model: Binary independence model
- Goal: Estimate \( P(D_i=1\mid D\in R_q) \)
Workflow
1. Compute result (using heuristics \( P=0.9 \))
2. User labels relevant documents
3. Recompute query using updated \( P \)
\( VR \): set of relevant documents
\( VR_{t_i} \): set of relevant documents containing term \( t_i \)
\( df(t_i) \): number of documents containing term \( t_i \)
Estimate probability that document \( d \) contains term \( t \)
- \( \hat{P}(D_i=1\mid D\in R_q) = \frac{|VR_{t_i}|}{|VR|} \)
- \( \hat{P}(D_i=0\mid D\in R_q) = \frac{df(t_i)-|VR_{t_i}|}{N-|VR|} \)

Also called blind relevance feedback
Automate the manual user interaction (relevance feedback without user interaction)
Assumption: Initial top-k documents are relevant
Problem: Topic drift
- Query: Copper mines (or Apple)
- If the top documents are about Chile, result will drift into the direction of documents in Chile