Evaluation

Concepts#

1. 1 Ground Truthrelevant documents per query; with the queries it forms a benchmark start here
2. 2 Precision at kP@k and P@R, fraction of relevant hits in the top $k$ / top $R$
3. 3 Average Precisionmean of P@$R_i$ over all relevant documents (0 for missing ones)
4. 4 Mean Average Precisionmean of AP (and P@k, P@R) over a benchmark
5. 5 Discounted Cumulative Gaingraded relevance with position discount, normalized by the ideal ranking
6. 6 BPrefrobust to incomplete judgments, uses only judged documents
7. 7 Overfitting (IR Evaluation)tuning on the evaluation benchmark inflates scores; use a training/test split

How it fits together#

Pick the measure by what the ground truth looks like:

Relations between them: AP is the average of P@k at the relevant positions; AP $= 1$ iff all relevant documents precede all non-relevant ones, which also gives P@R $= 1$ (but not conversely for AP with a short list, see the exam true/false question). nDCG generalizes the idea of AP to grades, bpref replaces “number of non-relevant documents above” by a capped count over judged ones.

Per query vs. per system. P@k, AP, nDCG, bpref rate one result list; averaging over all queries of the benchmark gives MP@k, MP@R, MAP (Mean Average Precision), which rate the system. The ground truth is a set but the results a ranked list; there is no natural cut-off or full order to compare directly, hence these measures (DBIS_VL02 > Set vs. Ranked List).

Honest evaluation. Parameters such as $k, b$ of BM25 are tuned on a training benchmark; the test benchmark is used once at the end (Overfitting (IR Evaluation)). Typical numbers (ES2): baseline MAP 42 %, best tuned 48 %.

Typical exam tasks. Compute the measures for a given result list, construct a relevance set that gives prescribed P@R and P@4 (Exam WS 22/23, see DBIS_VL13 > Example Task: Ranking and Precision (WS 22/23, Task 3.1, 8 points)), write ap/dcg/ndcg functions, and prove AP $= 1$ iff relevant documents come first. Pitfall: the divisor of AP is $R$, not the number of retrieved relevant documents. The rankings being evaluated come from Inverted Index and Ranking.

Key Formulas#

• $\mathrm{P@}k = \frac{|\text{relevant in top } k|}{k}$, $\ \mathrm{P@R} = \mathrm{P@}k|_{k=R}$ — Precision at k
• $\mathrm{AP} = \frac{1}{R}\sum_{k:\, r_k \text{ relevant}} \mathrm{P@}k$ — Average Precision
• $\mathrm{MAP} = \frac{1}{|Q|}\sum_{q} \mathrm{AP}(q)$ — Mean Average Precision
• $\mathrm{DCG@}k = \sum_{i=1}^k \frac{\mathrm{rel}_i}{\log_2(i+1)}$, $\ \mathrm{nDCG@}k = \frac{\mathrm{DCG@}k}{\mathrm{iDCG@}k}$ — Discounted Cumulative Gain
• $\mathrm{bpref} = \frac{1}{|R|}\sum_{d \in RR}\left(1 - \frac{|NR(d)|}{\min(|R|,|N|)}\right)$ — BPref

Exercises & Exam Questions#

Worked exam questions on these measures (WS 23/24 Task 1.3, WS 17/18 Task 1.1–1.2, WS 22/23 Task 3.1) are in Inverted Index and Ranking > Exercises & Exam Questions and DBIS_VL13; the concept notes contain the worked examples.

Lectures#

• DBIS_VL02 — ground truth, P@k, AP, MAP, nDCG, bpref, overfitting, set vs. ranked list
• DBIS_VL13 — example exam task combining dot-product ranking, P@R and AP

Related Topics#

• Inverted Index and Ranking — produces the rankings that are evaluated here