## 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

### Vector space relevance feedback (Rocchio's algorithm)
- 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

#### Theory
- 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*
  
#### Calculation of the optimal query
- 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} $`
  
#### Algorithm
- 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 $`


### Probabilistic relevance feedback
- 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|} $`
  
  
### Pseudo-relevance feedback
- 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


### Indirect relevance feedback
- Also called *implicit relevance feedback*
- Collect information with monitoring user's behavior
- Example
	- Eye tracking
	- Mouse movement
	- Reading time
	- Clicking on results
		- Assumption: Document description is representative
		- *Click in result 3 implies that 1 and 2 are irrelevent*
- Clickstream mining
	- Gather relevance data from all users of a system