Is it better to compute Average Precision using the trapezoidal rule or the rectangle method?

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"?

UPDATE

This journal article explains why linear interpolation is both "too optimist" and is also "incorrect," due to the non-linear properties of the Precision-Recall curve: https://www.biostat.wisc.edu/~page/rocpr.pdf

Also,

The function sklearn.metrics.average_precision_score does not use the rectangle rule, or any Riemann sum, right or otherwise. It uses "average precision." The formulas are very different.

Note that f(x) is very, very different than Pi. Due to the formulas for precision and recall, the Average Precision is actually computing an average, with discrete values between 0 and 1. Regarding Riemann, f(x) = y. This gives you the height to multiply the delta with. There is no averaging there.

Average precision is most analogous to the midpoint rule, as they are both doing averages.

Note that R uses the same formula for Average Precision: https://www.rdocumentation.org/packages/yardstick/versions/0.0.4/topics/average_precision

• Thanks for your answer! I understand the argumentation for the midpoint rule. scikit-learn, however, uses the right Riemann sum instead of the midpoint rule. Why do you think this is not reflected in the figure? Please note that for computing AP, the intervals are not evenly spaced and there can are intervals with a delta of 0 (the vertical lines in the plot). Commented Jul 27, 2020 at 15:09
• The link says AP is calculated using AP=sum(Rn-Rn-1)Pn. I see other references that differentiate the rectangle rule from the midpoint rule, so I updated my answer.
– user255758
Commented Jul 28, 2020 at 22:50
• For examples of what right Reimann sums look like, see Example 6 here math24.net/riemann-sums-definite-integral ; or Figure 4.2.6 here math.libretexts.org/Bookshelves/Calculus/…
– user255758
Commented Jul 28, 2020 at 23:11
• @Callidior - I made significant updates to my answer. Average Precision is not a Reimann formula, but it is analogous to the midpoint rule.
– user255758
Commented Jul 29, 2020 at 2:06
• Thanks for the update and the extensive references. I understand from the provided literature, that linear interpolation is not a wise thing to do for precision-recall curves. It is worth noting that both papers referenced in the scikit-learn documentation propose other, more justified variants of AP, which are again different from the common implementation in scikit-learn and R. Commented Jul 29, 2020 at 9:25

For a piecewise linear function, using the trapezoidal rule with endpoints on each of the ends of the "pieces" will yield the exact area under the curve --- i.e., it is equivalent to integration under the curve. This occurs when the trapezoids correspond exactly with the lines in the piecewise linear function. (Of course, this does not hold if there are endpoints of the pieces in the function that are not endpoints of the trapezoids.) Contrarily, the rectangular method will not give an exact area under the curve, though it should be close if you use a large number of rectangles.

As to which method is better, the exact method (trapezoidal) is better if it is computationally feasible. I am not aware of any particular reason why it should not be computationally more expensive than the rectangular method, since the only difference is that it uses the average height of each endpoint instead of the maximum height. If we partition the recall values using the endpoints $$r_0 < r_1 < \cdots < r_n$$ then we have:

\begin{align} \text{Rectangular area} &= \sum_{k=1}^n (r_k - r_{k-1}) \times \max (P(r_k), P(r_{k-1})), \\[10pt] \text{Trapezoidal area} &= \sum_{k=1}^n (r_k - r_{k-1}) \times \frac{P(r_k) + P(r_{k-1})}{2}. \\[6pt] \end{align}

Assuming that these endpoints contain the endpoints of the piecewise linear function, it is simple to show that the trapezoidal area is the exact area under the curve.

• Thank you for your answer! It was also always my opinion that the trapezoidal rule computes the exact area under the precision-recall curve. However, do you have any insight why a massively popular machine learning library such as scikit-learn would opt to use the right-point rectangular method instead then? Commented Jul 27, 2020 at 15:11