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