ConceptDBISAI-written · not yet proofread

Average Precision

Also AP

Average precision (AP) is the average of the values P@R_i over the positions R_1 < … < R_R of all R relevant documents in a result list, where a relevant document missing from the list contributes 0.

Know these firstPrecision at k Ground Truth

Formula#

Equivalently, summing over the ranks $k$ of the result list:

\mathrm{AP} = \frac{1}{R} \sum_{\substack{k \ge 1 \\ r_k \text{ relevant}}} \mathrm{P@}k.

Properties#

$\mathrm{AP} \in [0, 1]$ .
The divisor is always the number $R$ of relevant documents, not the number of relevant documents found.
AP rewards ranking relevant documents high: a relevant document at rank 1 contributes $\mathrm{P@1} = 1$ ; the $i$ -th relevant document at rank $R_i$ contributes $i/R_i \le 1$ .
Averaged over all queries of a benchmark it gives MAP.

Proof

Since the $i$ -th relevant document can be at rank $R_i \ge i$ at the earliest, each term satisfies $\mathrm{P@}R_i = i/R_i \le 1$ (and $= 0$ if missing). So $\mathrm{AP} = \frac{1}{R}\sum_i \mathrm{P@}R_i = 1$ iff every term equals 1, iff $R_i = i$ for $i = 1, \dots, R$ , iff the relevant documents occupy ranks $1, \dots, R$ , i.e. all of them come before every non-relevant document. $\blacksquare$

Example#

ExampleAP from a bit array (exam WS 15/16, Task 1.2)

Assuming the bit array covers all relevant documents (so $R$ = number of ones):

def compute_ap(bits):
    num_rel, total = 0, 0.0
    for i, bit in enumerate(bits):
        if bit == 1:
            num_rel += 1
            total += num_rel / (i + 1)   # P@(i+1)
    return total / num_rel

Sources#

Slides 02, p. 23, Slides 13, p. 18
DBIS_VL02 > Average Precision, DBIS_VL13 > Example Task: Ranking and Precision (WS 22/23, Task 3.1, 8 points)
Exams: DBIS Exam WS1516 (not published) Task 1.1–1.3, DBIS Exam WS1617 (not published) Task 1.3, DBIS Exam WS1718 (not published) Task 1.1, DBIS Exam WS2122 (not published) Task 1.3, DBIS Exam WS2223 (not published) Task 3.1, DBIS Exam WS2324 (not published) Task 1.3, DBIS Exam WS2324-2 (not published) Task 1.3 (2)

Connections

Part of topics1

Evaluation

Mentioned in inline links8

BPref
Motivation: for very large collections, judging all documents is infeasible; competitions use pooling (judge only the top- $k$ results of each participant), see Ground Truth. Measures like AP need complete judgments; bpref uses only judged… §
Discounted Cumulative Gain
Discount: the factor $1/\log_2(i+1)$ makes a relevant document count less the lower it is ranked; rank 1 keeps its full relevance ( $\log_2 2 = 1$ ). So very relevant documents ranked above only somewhat relevant ones get a bonus, which bina… §
Ground Truth
Every evaluation measure compares a ranked result list with the ground truth: P@k, P@R, AP, MAP, nDCG and bpref. $R = |$ ground truth of $q|$ is the number of relevant documents. §
Mean Average Precision
Let $Q$ be the set of queries of a benchmark (ground truth for each query) and $\mathrm{AP}(q)$ the average precision of the system’s result list for $q \in Q$ . The mean average precision is §
Query matrix movies has $\mathrm{AP} = 0.55$ (see Average Precision); a second query with $\mathrm{AP} = 0.45$ (exam WS 22/23, Task 3.1). Then $\mathrm{MAP} = (0.55 + 0.45)/2 = 0.5$ . §
Precision at k
Average Precision averages $\mathrm{P@}k$ over the positions $k$ of the relevant documents. §
VL02 – Ranking and Evaluation
(Slide 23, Average Precision) §
Average Precision — mean of $\mathrm{P@}R_i$ over all relevant documents, 0 for missing ones §
VL13 – Evaluation, Exam, Work in our Group
Slide 18. This task combines dot-product ranking in the vector space model with P@k, P@R and average precision from the Evaluation topic. §
Average Precision — computed for the chosen relevant set in Task 3.1 §
Evaluation
Average Precision — mean of P@ $R_i$ over all relevant documents (0 for missing ones) §
| binary, complete | AP | all relevant documents, rewards early ranks | needs complete judgments; missing relevant documents count 0 | §

Search in these mentions →