Precision, Recall and Average Precision

A query has four relevant documents in the collection. System A returns them at ranks 1, 2, 9 and 10. System B returns them at ranks 3, 4, 5 and 6. Both have precision@10 of 0.4 and recall@10 of 1.0, so by the two oldest numbers in retrieval they are identical. Nobody who has used a search engine believes that. The metrics in this family turn that intuition into arithmetic, each by assuming something specific about the person reading the list.

This concept covers binary relevance; graded labels and nDCG have their own concept alongside it.

From sets to ranked lists

For a query with relevant set \(\mathcal{R}\) and retrieved set \(\mathcal{D}\), precision is \(P = |\mathcal{R} \cap \mathcal{D}| / |\mathcal{D}|\) and recall is \(R = |\mathcal{R} \cap \mathcal{D}| / |\mathcal{R}|\). These are set measures: they ignore order entirely. Ranked retrieval makes them functions of a cutoff \(k\). Writing \(\mathrm{rel}_i \in \{0,1\}\) for the relevance of the document at rank \(i\),

P@k has a ceiling that is easy to forget. A query with three relevant documents can never exceed \(P@10 = 0.3\), so averaging P@10 across queries mixes queries with ceilings of 0.1 and 1.0 and rewards collections of easy topics as much as good systems.

R-precision removes that ceiling by setting the cutoff to the number of relevant documents, \(k = |\mathcal{R}|\). At that rank precision and recall are equal by construction, which is why R-precision is also called the break-even point (Manning, Raghavan and Schütze, 2008, Introduction to Information Retrieval, ch. 8). For the example above, \(|\mathcal{R}| = 4\): System A has two relevant documents in its top four (R-precision 0.5), System B has one (0.25).

Curves and interpolation

Plotting precision against recall as you walk down the ranking gives a sawtooth: precision jumps up at every relevant document and decays through every non-relevant one. Interpolated precision smooths it by taking the best precision available at any recall level at least as high:

A user who wants recall \(r\) would happily read further if that raised precision. TREC historically summarised a run by the 11-point interpolated average precision, the mean of \(p_{\text{interp}}\) at recall \(0, 0.1, \dots, 1.0\). The cost is optimism. Interpolation can only raise the curve, and \(p_{\text{interp}}(0)\) is 1.0 for any system that ranks a relevant document first, however bad the rest of its ranking is.

Average precision

Average precision takes precision at the rank of each relevant document and averages over all relevant documents, including the ones never retrieved:

where \(n\) is the depth of the ranking. An unretrieved relevant document adds zero to the sum but still counts in the denominator, so AP punishes missed recall and late placement at once. MAP is the mean of AP over the query set, and it approximates the area under the uninterpolated precision-recall curve.

Back to the opening example. System A scores \(\tfrac14(1/1 + 2/2 + 3/9 + 4/10) = \tfrac14(2.733) = 0.683\). System B scores \(\tfrac14(1/3 + 2/4 + 3/5 + 4/6) = \tfrac14(2.100) = 0.525\). The intuition now has a number.

AP was long defended on empirical rather than behavioural grounds. Buckley and Voorhees found that P@30 had roughly twice the error rate of AP when judging which of two systems is better on a sample of topics, and that 25 topics is a working minimum with 50 being better (Buckley and Voorhees, 2000, Evaluating Evaluation Measure Stability, SIGIR). A user model came later: Robertson showed AP is the expected precision at the stopping point of a user who picks one relevant document uniformly at random and reads down to it (Robertson, 2008, A New Interpretation of Average Precision, SIGIR).

That model is where the field disagrees. Moffat and Zobel argued that a metric whose value depends on \(|\mathcal{R}|\), a quantity no searcher knows, is not a model of any real user, and proposed rank-biased precision, with a persistence parameter, in its place (Moffat and Zobel, 2008, Rank-Biased Precision for Measurement of Retrieval Effectiveness, ACM TOIS 27(1)). Fuhr later listed MAP's "unrealistic assumptions" among common mistakes in IR evaluation (Fuhr, 2018, Some Common Mistakes in IR Evaluation, and How They Can Be Avoided, SIGIR Forum 51(3)), and Moffat replied that metrics like AP are defensible whenever there is an external reason for the numbers they assign (Moffat, 2022, Batch Evaluation Metrics in Information Retrieval: Measures, Scales, and Meaning, arXiv:2207.03103). AP remains the TREC default; what it means is still argued.

When it breaks

\(|\mathcal{R}|\) is an estimate. In a pooled collection the denominator counts judged relevant documents, not all of them. A system that retrieves unjudged relevant documents gets no credit, and its AP and recall both drop. This is the pooling bias covered in the neighbouring concept on test collections.

On one-answer queries AP becomes reciprocal rank. With \(|\mathcal{R}| = 1\), AP reduces to \(1/\text{rank}\). MAP over a mixed query set therefore averages a precision-oriented metric on some queries with reciprocal rank on others, and a change that helps navigational queries can move MAP for reasons unrelated to ranking depth.

The arithmetic mean hides the worst queries. Raising AP from 0.80 to 0.85 on an easy query moves MAP as much as raising it from 0.01 to 0.06 on a failing one, though the second matters far more to the user. The TREC Robust track used the geometric mean of AP (GMAP) for this reason: it rewards gains on the hardest topics.

Recall-oriented tasks need different targets. E-discovery and systematic reviews care about the review depth needed to reach, say, 95% recall. Neither P@10 nor AP measures that.