How is average precision related to the precision-recall curve?

Question

As background, in Information Retrieval, there are many metrics to assess how well search results are retrieving information.

A simple one is precision, where we calculate the fraction of documents returned that are relevant to our query. There is a second (or more general?) metric, precision@K: For a ranked result set, we calculate the fraction of documents at rank $k$ or higher which are relevant. So if the first document is relevant, the second is not, and the third is, then precision@3 is 1/3.

On to average precision. As I understand it (thanks in part to this), for this we get the rank of every relevant document in the result set, and then average the precision@k values at each of those ranks. It's even clearer if you look at my link.

Ok, my question: Both Wikipedia (here) and my IR book give the same explanation I gave, but then they start talking about precision-recall curves. My understanding of precision-recall curves is from machine learning, but I assume the concept is similar: You plot precision and recall against each other (on the x and y axis), showing how a decrease in one leads to an increase in the other.

I don't see how that relates to average precision, which is only a metric of precision and not of recall.

Wikipedia says: Precision and recall are single-value metrics based on the whole list of documents returned by the system. For systems that return a ranked sequence of documents, it is desirable to also consider the order in which the returned documents are presented. By computing a precision and recall at every position in the ranked sequence of documents, one can plot a precision-recall curve, plotting precision p(r) as a function of recall r. Average precision computes the average value of p(r) over the interval from r=0 to r=1.

If I had to guess, it seems like they're describing calculating both average precision and average recall for every rank, or something. But if so it's confusing that they'd put it under Average Precision, and I'm very unsure of my interpretation.

So, how is average precision related to precision-recall graphs? It probably goes without saying that any other tips on understanding that Wikipedia section are also humbly appreciated.

Answer 1

Let $p(r)$ be the best precision which can be achieved at recall $r$. The average precision is $$ p_{avg} = \int_0^1 p(r) \, dr. $$ Let $r(p)$ be the best recall which can be achieved at precision $p$. The average recall is $$ r_{avg} = \int_0^1 r(p) \, dp. $$ Notice that the functions $p(r)$ and $r(p)$ are inverses of one another.

We can express these quantities using the function $\chi(p,r)$, which is 1 if precision $p$ and recall $r$ are achievable at the same time, and 0 otherwise. We have $p(r) = \int_0^1 \chi(p,r) \, dp$, and so $$ p_{avg} = \int_0^1 \int_0^1 \chi(p,r) \, dp dr. $$ Similarly, $r(p) = \int_0^1 \chi(p,r) \, dr$, and so $$ r_{avg} = \int_0^1 \int_0^1 \chi(p,r) \, dr dp. $$ As a consequence, $p_{avg} = r_{avg}$.

Yet another interpretation of this common quantity is the area below the precision–recall curve. It is also the area below the ROC curve.