## Evaluation in information retrieval
- Efficiency
	- Aspects
		- Storage space
		- CPU time
		- I/O operations (number, load)
		- Response time
		- Scalability
	- Goal: Efficient *enough*
	- Easy to evaluate
- Effectiveness
	- Measure result quality
	- Key concept: Relevance
	- No precise definition

### Relevance
- Manifestations of relevance
	- System/algorithmic relevance
	- Topical/subject relevance
	- Cognitive relevance/pertinence
	- Situational relevance/utility
	- Affective relevance
- Notion of relevance in the lecture: **Topical/subject relevance**
- Current IR goal: Topical/subject relevance
- Future IR goal: Other manifestations of relevance
- *Relevant to query* means *relevant to typical information need for that query*

#### System/algorithmic relevance
- Static and objective concept
- *Fit between retrieved documents and user's query*
- Measurement: Effectiveness/rules for comparison

#### Topical/subject relevance
- Static and subjective concept
- *Semantic fit between query and topics of retrieved documents*
- Based on judgements
- Measurement: Aboutness 

#### Cognitive relevance/pertinence
- Dynamic and subjective concept
- *Relation between content of documents and cognitive state of knowledge/information need*
- *Judgement about the applicability of the documents*
- *Dynamic*: May change over time
- Measurement: Information quality/informativeness

![](images/pertinence.png)
#### Situational relevance/utility
- Dynamic and subjective concept
- *Relation between documents and situation/task/problem*
- *Can the user complete his task with the retrieved documents?*
- *Serendipity*: Information can be useful without expecting it
- Measurement: Reduction of uncertainty/Usefulness in decision making

#### Affective relevance
- Dynamic and subjective concept
- *Relation between documents and user's intents/goals/emotions/motivations*
- Represents the human drive for information
- Measurement: Success/satisfaction

### Evaluate relevance
- Benchmark approach
	- Document collection
	- Set of queries (information needs)
	- Gold standard: Assessment of relevance for each query-document pair
- Problem: Assessment for large document collections is very expensive
- Solution: **Pooling method**
	- Assumption: Un-assessed/un-marked documents are irrelevant (default)
	- Run query on set of IR systems
	- Union top-k results
	- Present union of documents to human assessors
- Test collections
	- Assumptions
		- Binary relevance
		- Independence of assessing documents
		- Collection resembles real retrieval (query logs?)
		- Intersubject reliability: Consistency between multiple users' opinion
	- Cranfield collection
		- 1960, Cranfield university
		- 1400 abstracts of aerodynaics
		- 225 queries
		- Judgement: Five steps
	- TREC
		- 1992, Text retrieval conference
		- 1.9 million documents (newswire)
		- 450 queries
		- Judgement: Binary
	- Reuters-RCV1 (800000 stories)

### Metrics
- Evaluate sets
	- Precision
	- Recall
	- Fallout
	- F-measure
- Evaluate lists
	- Precision at k
	- Recall at k
	- Interpolated precision (for precision-recall curve)
	- Mean average precision
- Errors
	- False positives
		- Irrelevant documents returned by the system
		- Unnecessary extension of result set
	- False negatives
		- Relevant documents not returned by the system
		- User is not aware of missing documents
		- *Often* worse than false positives

![](images/precisionrecall.png)
#### Precision
- Use for result sets
- Called *Positive predictive value PPV*
- Ratio of returned relevant documents to all returned documents
- `$ Precision = \frac{TP}{TP+FP} $`
- Important for Web search

#### Recall
- Use for result sets
- Called *True positive rate TPR*, *Sensitivity*, *Hit rate*
- Ratio of returned relevant documents to all relevant documents
- `$ Recall = \frac{TP}{TP+FN} $` 
- Important for professional searchers
- Important for desktop search
- Hard to measure (relevant documents often unknown)

#### Precision-recall curve
- Precision and recall tradeoff against each other
- Leads to system tuning
- Decide whether to optimize precision/recall
- Result lists
	- Sawtooth shape ((k+1)-th document is non-relevant, recall stays the same but precision drops)
	- *Interpolated precision*: Precision at recall `$ r $` is highest precision of any recall level `$ r'>r $`

![](images/sawtooth.png)
#### Fallout
- Use for result sets
- Called *False positive rate FPR*
- Ratio of returned non-relevant documents to all non-relevant documents
- `$ Fallout = \frac{FP}{FP+TN} $`
- Important for large result sets

#### F-measure
- Use for result sets
- Combine precision and recall
- Weighted harmonic mean (reciproke of the weighted average of the reciprokes)
- `$ F=\frac{1}{\alpha \frac{1}{precision}+(1-\alpha)\frac{1}{recall}} $`
- Parameter `$ \alpha\in [0,1] $`
- Motivation harmonic mean: `$ F=0.5 $` with arithmetic mean by returning all documents

#### Precision/recall at k
- Use for result lists
- Compute precision/recall for the first `$ k $` returned documents

#### Mean average precision
- Use for result lists
- Single aggregated value for a IR system
- Advantage: 
	- Good discrimination
	- Stability
- Computation
	- Compute precision at k for any k that there is a relevant document on position k
	- Compute arithmetic mean of these precision at k values
	- Repeat this computation for every query and compute the average precision