Class Notes

Lab 05

Evaluating Information Retrieval Systems

Precision & Recall MRR & MAP nDCG Cranfield
Work in progress These notes are still being written and reviewed: content may change, and some parts may still contain mistakes.

Overview of the lab

Lab 04 answered "How do we rank documents?" Lab 05 answers "How do we know whether that ranking is good?" The aim is not only to calculate the standard metrics, but to understand what user behaviour each one approximates. The systems compared are TF-IDF and BM25 from Lab 04, on Cranfield.

queries + system rankings + relevance judgments → metrics
  1. Why evaluation? Relevance judgments and the offline setup.
  2. Accuracy, Precision and Recall: why accuracy is not enough, and precision and recall at a cutoff \(k\).
  3. Why rank position matters: RR and MRR, AP and MAP.
  4. Graded relevance: DCG and nDCG.
  5. Live evaluation on Cranfield with ir_measures.
  6. Different metrics can disagree: metric choice and per-query analysis.
  7. Summary, and an optional exercise.

Learning objectives

By the end you should be able to explain:

  • why retrieval evaluation requires relevance judgments;
  • why accuracy is not a useful measure for retrieval;
  • the difference between Precision and Recall, and why rank-aware metrics are needed;
  • the meaning of Reciprocal Rank and MRR, and of Average Precision and MAP;
  • how graded relevance leads to DCG and nDCG;
  • why different metrics can produce different conclusions;
Part I

Why evaluation?

Two systems return these rankings for the same query. Which system is better? Without knowing which documents are relevant: we do not know. We need relevance judgments.

Try it: be the assessor

Click documents to mark them relevant. The measures (explained below) update for both systems; the better value is highlighted.

Relevance judgments

For each query–document pair, a human assessor assigns a label: relevant or not relevant, or a grade such as 0 = not relevant, 1 = somewhat relevant, 2 = relevant, 3 = highly relevant. Once we have ranking + relevance, we can calculate metrics.

The offline evaluation setup

Query

from a fixed test set

Retrieval system

TF-IDF, BM25, …

Ranked documents

a run

Relevance judgments

qrels

Metric

one number per query, then the mean

The metric is a summary of ranking quality under a particular definition of relevance.

Part II

Accuracy, Precision and Recall

For one query, every document in the collection falls into one of four cells: the system retrieved it or not, and it is relevant or not.

relevantnot relevant
retrievedTP, true positive: a hitFP, false positive: noise the user reads
not retrievedFN, false negative: a missTN, true negative: correctly left out

Accuracy, and why it is not enough

📐 Accuracy
\[ \text{Accuracy} = \frac{TP + TN}{TP + FP + FN + TN} = \frac{\text{correct decisions}}{\text{all documents}} \]

The share of documents the system classified correctly, as retrieved-and-relevant or left-out-and-not-relevant. It is the natural measure for classification, where the classes are of similar size.

  • ❗ In retrieval, almost every document is not relevant. A Cranfield query has on average 7.2 relevant documents among 1,400 (1,612 relevant judgments for 225 queries). For a query with 7 relevant documents, a system that returns nothing leaves the other 1,393 correctly out and gets accuracy \(1393 / 1400 = 99.5\%\).
  • On the Web, with billions of pages and a handful of relevant ones, the useless empty system scores 99.9999…%. Accuracy is dominated by the true negatives, which the user never sees and does not care about.
  • So retrieval evaluation ignores TN and looks only at what the user sees (TP, FP) and what the user needs (TP, FN): precision and recall.

Try it: accuracy vs precision and recall

One query: set the collection size, how many documents are relevant, how many the system retrieves and how many of those are relevant.

A toy ranking

A toy ranking used throughout: D1 (relevant), D2 (not), D3 (relevant), D4 (not), D5 (relevant), written R N R N R. The collection contains exactly these three relevant documents: D1, D3, D5. For ranked retrieval both measures are computed at a cutoff \(k\): we look only at the top \(k\) results (P@1, P@5, P@10, …).

Precision

📐 Precision
\[ \text{Precision} = \frac{\text{relevant retrieved}}{\text{retrieved}} = \frac{TP}{TP + FP} \qquad P@k = \frac{\text{relevant in the top } k}{k} \]

Of the documents we retrieved, how many are relevant? Precision looks only at what the system returned: how clean is the result list?

  • Example: a search engine shows 10 results and 4 of them are relevant: \(P@10 = 4/10 = 0.4\). Six of the ten results the user reads are wasted.
  • Documents below the cutoff do not matter for P@k, and neither do relevant documents the system never returned.

The toy ranking R N R N R, precision at every cutoff:

rank \(k\)12345
documentD1 RD2 ND3 RD4 ND5 R
relevant in top \(k\)11223
\(P@k\)1/1 = 1.001/2 = 0.502/3 = 0.672/4 = 0.503/5 = 0.60

Try it: precision at k

Move the cutoff \(k\): the bracket marks the retrieved set, the documents the user sees. Click a document to switch it between relevant and not relevant.

3

Recall

📐 Recall
\[ \text{Recall} = \frac{\text{relevant retrieved}}{\text{all relevant}} = \frac{TP}{TP + FN} \qquad Recall@k = \frac{\text{relevant in the top } k}{\text{all relevant}} \]

Of all relevant documents that exist, how many did we retrieve? Recall looks at the whole collection: how much of what the user needs did we find? Its denominator counts relevant documents the system never showed, which is why it needs relevance judgments beyond the returned list.

  • Example: a lawyer needs every court decision on a topic. The archive holds 50 relevant decisions and the search finds 40 of them: \(Recall = 40/50 = 0.8\), however many irrelevant ones came along.
  • If the collection held 2 more relevant documents that the ranking never reaches, the same ranking would only get \(Recall@5 = 3/5\): nothing about the list changed, only the denominator.

The toy ranking R N R N R, with 3 relevant documents in the collection:

rank \(k\)12345
documentD1 RD2 ND3 RD4 ND5 R
relevant in top \(k\)11223
\(Recall@k\)1/3 = 0.331/3 = 0.332/3 = 0.672/3 = 0.673/3 = 1.00

Try it: recall at k

The whole collection of 30 documents; the toy ranking returns D1–D5 in order. Move \(k\) to retrieve more of the ranking, and add relevant documents that the ranking never reaches.

3
0

retrieved (top \(k\))   relevant, found   relevant, missed

Precision vs recall

  • They answer different questions. With 10 relevant documents: system A retrieves 2, both relevant: Precision 1.0, Recall 0.2. System B retrieves 100, 10 of them relevant: Precision 0.1, Recall 1.0. Neither measure is universally more important.
  • Retrieval depth: as we retrieve more and more documents, recall tends to increase and precision often decreases. This is a tendency, not a guarantee for every single step: a relevant document at rank \(k\) raises P@k.

Try it: both on one ranking

Click a rank to switch it between relevant (R) and not relevant (N); use + and − to change the length, and set how many relevant documents exist in total. The plot shows P@k and Recall@k; the shaded columns are relevant ranks. The same playground computes RR and AP, used in Part III.

P@k   Recall@k

Part III

Why rank position matters

Ranking A is R R R N N N N N N N, ranking B is N N N N N N N R R R. Both have \(P@10 = 0.3\), yet ranking A is clearly preferable for most users (load both in the playground above). We need rank-aware metrics.

Reciprocal Rank and MRR

📐 Reciprocal Rank
\[ RR = \frac{1}{r} \qquad MRR = \frac{1}{|Q|} \sum_{q \in Q} RR(q) \]

\(r\) is the rank of the first relevant result: at rank 1, RR = 1; at rank 2, 0.5; at rank 5, 0.2. With no relevant result, RR = 0. RR is for one query, MRR is the mean across queries.

  • Useful when the user mainly wants one good result: navigational search, entity lookup, question answering, some FAQ tasks.
  • But MRR ignores everything after the first relevant document.

Average Precision and MAP

📐 Average Precision
\[ AP = \frac{1}{R} \sum_{k=1}^{N} P@k \cdot rel(k) \qquad MAP = \frac{1}{|Q|} \sum_{q \in Q} AP(q) \]

\(R\) is the number of relevant documents for the query and \(rel(k)\) is 1 if the document at rank \(k\) is relevant. In words: every time we meet a relevant document, record the precision at that point; then average those values over all \(R\) relevant documents. AP is for one query, MAP the mean across queries.

Worked example, R N R N R: \(P@1 = 1\), \(P@3 = 2/3\), \(P@5 = 3/5\), so \(AP = \frac{1 + 2/3 + 3/5}{3} \approx 0.756\). For rankings A and B above, AP is 1.0 and about 0.216, and RR is 1 and 0.125: the rank-aware metrics separate what P@10 could not.

Recap

MetricMain question
Precision@kHow many of the top \(k\) are relevant?
Recall@kHow much of the relevant material did we find?
RRWhere is the first relevant result?
MRRHow early is the first relevant result, on average?
APAre relevant documents consistently ranked high?
MAPMean AP across queries

So far relevance has been binary. What if some relevant documents are much better than others?

Part IV

Graded relevance: DCG and nDCG

Cranfield has graded relevance: a document may be of minimum interest, useful, highly relevant, or a complete answer. Binary metrics collapse all of these into "relevant", which loses information: a ranking that puts a complete answer first and one that puts a document of minimum interest first get the same P@1. DCG (Järvelin & Kekäläinen, 2002) measures a graded ranking by imagining a user who reads the list from the top.

Three ideas in one formula

  1. Gain: each document is worth something to the user, and more if its grade is higher. With the gain \(2^{rel} - 1\): grade 0 → 0, 1 → 1, 2 → 3, 3 → 7, 4 → 15. The exponent makes one highly relevant document worth more than several marginal ones: a grade-3 document (7) is worth more than two grade-2 documents (3 + 3).
  2. Discount: the user reads from the top, and every rank further down is less likely to be read. So the gain at rank \(i\) is divided by \(\log_2(i + 1)\): rank 1 by 1 (full value), rank 2 by 1.58, rank 3 by 2, rank 4 by 2.32, rank 10 by 3.46. The logarithm makes the penalty grow slowly: a document at rank 10 still keeps 29% of its value.
  3. Cumulative: add up the discounted gains of the top \(k\) documents. The total is the value the user collects by reading the top \(k\).
📐 Discounted Cumulative Gain
\[ DCG@k = \sum_{i=1}^{k} \frac{2^{rel_i} - 1}{\log_2(i + 1)} \qquad nDCG@k = \frac{DCG@k}{IDCG@k} \]

\(rel_i\) is the grade of the document at rank \(i\); \(IDCG@k\) is the DCG@k of the ideal ranking, all judged documents sorted by grade, highest first.

A worked example

The system ranks four documents with grades [3, 0, 2, 1].

rank \(i\)gradegain \(2^{rel} - 1\)discount \(\log_2(i+1)\)gain / discount
1371.0007.000
2001.5850.000
3232.0001.500
4112.3220.431
DCG@48.931
  • Is 8.931 good? A raw DCG cannot tell: it depends on how much relevant material the query has. Ten grade-3 documents give \(DCG@10 = 31.8\); a query with a single grade-1 document can never exceed 1.
  • So normalize: the best possible order of the same documents is [3, 2, 1, 0], with \(IDCG@4 = 7 + 3/1.585 + 1/2 + 0 = 9.393\). Then \(nDCG@4 = 8.931 / 9.393 = 0.951\): 95% of the best achievable. The system lost a little because the grade-2 and grade-1 documents came one rank too late.
  • The same documents in the worst order, [0, 1, 2, 3]: \(DCG@4 = 0 + 1/1.585 + 3/2 + 7/2.322 = 5.146\), \(nDCG@4 = 0.548\). Same documents, same precision, very different nDCG: the order of the grades is what it measures.
  • \(nDCG@k\) is always between 0 and 1, and 1 exactly for an ideal ranking; after normalization it can be averaged over queries.

Try it: compute nDCG

Type the grades of a ranking, top first. The tables show every term of the sum; "Sort to ideal" turns the ranking into the ideal one.

💡 Not every nDCG uses \(2^{rel} - 1\). ir_measures' default nDCG@10 (the trec_eval definition) uses the grade itself as the gain; the formula above is nDCG(dcg='exp-log2')@10. With [3, 0, 2, 1] the two give 0.951 and 0.930. Always report which one you used.

Part V

Live evaluation on Cranfield

Cranfield (ir_datasets) has graded judgments. For binary metrics we treat relevance ≥ 1 as relevant; for nDCG we keep the grades (a grade of −1 counts as 0).

qrels.py Python 
import ir_datasets
from collections import Counter

dataset = ir_datasets.load("cranfield")
queries = list(dataset.queries_iter())
qrels = list(dataset.qrels_iter())

Counter(q.relevance for q in qrels)
# Counter({3: 734, 2: 387, 4: 363, -1: 225, 1: 128})

Using ir_measures

Use an established evaluation library (ir_measures) rather than implementing every metric yourself. It reads TREC-style run files, query_id Q0 doc_id rank score system, with the top 100 results of each system for every query, made with the two search functions from Lab 04:

write_runs.py Python 
# search_tfidf and search_bm25 from Lab 04, return (doc_id, title, score)
def write_run(path, system_name, search_fn, k=100):
    with open(path, "w", encoding="utf-8") as f:
        for q in queries:
            for rank, (doc_id, title, score) in enumerate(search_fn(q.text, k=k), start=1):
                f.write(f"{q.query_id} Q0 {doc_id} {rank} {score:.8f} {system_name}\n")

write_run("lab04_tfidf.run", "tfidf", search_tfidf)
write_run("lab04_bm25.run", "bm25", search_bm25)
evaluate.py Python 
# pip install ir_measures
import ir_measures
from ir_measures import P, Recall, RR, AP, nDCG

tfidf_run = ir_measures.read_trec_run("lab04_tfidf.run")
bm25_run = ir_measures.read_trec_run("lab04_bm25.run")

metrics = [
    P(rel=1) @ 10,
    Recall(rel=1) @ 100,
    RR(rel=1),
    AP(rel=1),
    nDCG @ 10,
]

tfidf_scores = ir_measures.calc_aggregate(metrics, qrels, tfidf_run)
bm25_scores = ir_measures.calc_aggregate(metrics, qrels, bm25_run)
print(tfidf_scores)
# {AP: 0.2737..., nDCG@10: 0.3170..., RR: 0.5100..., P@10: 0.2284..., R@100: 0.7006...}
print(bm25_scores)
# {AP: 0.2405..., nDCG@10: 0.2822..., RR: 0.5044..., P@10: 0.1991..., R@100: 0.6512...}

See it: TF-IDF vs BM25 on all 225 queries

Computed in the page from the same runs; the values are identical to ir_measures' output above (checked query by query). The last row is nDCG with the \(2^{rel} - 1\) gain from Part IV.

💡 Do not focus only on which row has the larger number. Ask instead: which metric changed? What user behaviour does that metric represent? Is the difference at rank 10, at rank 100, or across the whole ranking? And here: BM25 is lower than TF-IDF on every metric. "More sophisticated" is not automatically better; the setup matters. text.lower().split() keeps punctuation attached: 5,486 of the 12,246 distinct tokens contain it, like thickness,, which then does not match thickness. With a word tokenizer (\b\w+\b) the same BM25 reaches MAP 0.262 and P@10 0.219, closer to TF-IDF but still below it on Cranfield.

Part VI

Different metrics can disagree

  • System A has a higher P@10, system B a higher Recall@100: no contradiction, they are strong in different ways.
  • System A has a higher MRR, system B a higher MAP: this can happen, because MRR cares about the first relevant result and MAP about all of them.

Metric choice follows the task

TaskWhat mattersTypical metrics
Web searchthe early ranksP@5, P@10, nDCG@10
Legal or medical literature searchfinding as much relevant material as possibleRecall@100, Recall@1000
Navigational searchone correct result, quicklyMRR
General ad-hoc retrievalthe whole rankingMAP, nDCG

Per-query analysis

Averages can hide failures. A higher MAP for one system does not mean it wins on every query: some queries may strongly prefer one system, others the other. Serious IR evaluation combines aggregate metrics + per-query analysis + error analysis.

Try it: every Cranfield query

Each dot is one query: TF-IDF's score on the x-axis, BM25's on the y-axis. Dots above the diagonal are queries where BM25 is better. Click a dot (or choose a query) to compare the two top-10 lists with their relevance grades; the default is the query where the systems differ most in AP.

Summary: key takeaways

MetricBest interpretation
P@kHow clean are the top results?
Recall@kHow much relevant material did we retrieve?
MRRHow quickly did we find the first relevant result?
MAPAre relevant documents ranked high throughout the ranking?
nDCG@kAre the most relevant documents ranked highest?
Lab 04: build a ranking → Lab 05: evaluate the ranking → later labs: replace the retriever, keep the evaluation framework
  1. A retrieval score is meaningless without an evaluation setup.
  2. Accuracy is useless for retrieval: almost every document is not relevant. Precision and Recall measure different retrieval goals.
  3. Rank position matters.
  4. Different metrics encode different assumptions about user needs.

Optional exercise

Evaluate TF-IDF and BM25 on Cranfield with P@10, Recall@100, MRR, MAP and nDCG@10. Then choose two queries where the systems differ strongly and inspect the rankings manually (the per-query plot above helps). The purpose is not a large report, but to connect a metric difference to actual ranking behaviour.