Background
Average precision is a popular and important performance metric widely used for, e.g., retrieval and detection tasks. It measures the area under the precision-recall curve, which plots the precision values for all possible detection thresholds against the respective recall values.
A typical precision-recall curve would look somewhat like this.
Confusion
Since there is only a limited number of thresholds to be evaluated on any given finite dataset, the precision-recall curve is a piece-wise linear function. Thus, I always thought the correct way of computing the area under that curve would be using the trapezoidal rule:
ap = sum( (recall[k+1] - recall[k]) * (precision[k+1] - precision[k]) / 2 )
Not only I thought so, apparently, since the official code for evaluating results on the Oxford Buildings dataset, which is a widely used benchmark in content-based image retrieval, computes AP in exactly this way, too.
However, the scikit-learn
package for Python computes average precision differently in the function sklearn.metrics.average_precision_score
, following the definition of AP from Wikipedia. They use the rectangle method:
ap = sum( (recall[k+1] - recall[k]) * precision[k+1] )
In the example given above, that would approximate the area under the precision-recall curve with the red function in the following figure:
The documentation of scikit-learn
says the following about this:
This implementation is different from computing the area under the precision-recall curve with the trapezoidal rule, which uses linear interpolation and can be too optimistic.
One of the curators of the Oxford Buildings dataset, on the other hand, explained in a related question on StackOverflow that the rectangle method would be a "commonly used worse approximation".
Question
Bad enough that different benchmarks and different packages use different variants of Average Precision to compare methods, but now I wonder:
- Which of the two versions is the "better" way of doing it? Trapezoidal rule or rectangle method?
- What are the pros and cons for each?
- What does the
scikit-learn
documentation mean with the claim the the trapezoidal rule is "too optimistic"?