Unachievable Region in Precision-Recall Space and Its Effect on Empirical Evaluation

1. Introduction

• PR analysis is preferred to ROC analysis under large class skew, where even a low false positive rate can yield many false positives and low precision.Precision measures the proportion of positively labeled examples that are truly positive, while recall measures correctly classified positives.Source: §1 · p. 1
• PR curves and AUCPR are often treated as substitutes for ROC curves and AUCROC, although PR curves vary with class skew.AUCPR is used to compare algorithms in information retrieval, statistical relational learning, and information extraction; some algorithms explicitly optimize it.Source: §1 · p. 1
• Unlike ROC space, PR space contains points that cannot be achieved by any confusion matrix for a given data set.The paper characterizes the unachievable region's size as a function only of class skew and identifies a minimum PR curve whose area every algorithm obtains for free.Source: §1 · p. 2
• Unachievable-region effects can distort task or fold aggregation, change with downsampling, and alter the behavior of algorithms optimizing AUCPR or MAP.The paper describes straightforward modifications to AUCPR that can at least partially offset these undesirable effects.Source: §1 · p. 2

2.1. Unachievable Points in PR Space

• With 100 positives and 200 negatives, precision 0.2 is possible at recall 0.5 but impossible above it because false positives cannot exceed the negatives.At recall 0.6, the attempted confusion matrix would require more false positives than available negatives.Source: §2.1 · pp. 2–3, Table 1 · p. 3
• Theorem 1 requires achievable precision and recall to satisfy p ≥ rπ/(rπ + 1 − π), so the feasible boundary depends on skew, not data-set size.Here π is the proportion of positive examples.Source: §2.1 · p. 3

2.2. Unachievable Region in PR Space

• The minimum PR curve is a tight lower bound: for a given skew, all achievable points lie on or above it.The bound is attained by ranking every negative ahead of every positive.Source: §2.2 · p. 3
• The unachievable region lies below the minimum PR curve, and its area—and thus minimum AUCPR—has a closed-form value determined by skew.Every algorithm's AUCPR includes this minimum area “for free.”Source: §2.2 · p. 3
• The minimum average precision follows the worst ranking, with all negatives ranked before positives, and unlike AUCPR depends on the number of positive examples.AP is a discrete sum over positives, whereas AUCPR is calculated from interpolated curves.Source: §2.2 · p. 4
• Changing skew from 0.01 to 0.5 raises minimum AUCPR by approximately 0.3, even with no change to the learning algorithm.This is an automatic score increase from changing the data set.Source: §2.2 · p. 4
• Because most of the unachievable region is at higher recall, its effect on AUCPR is more pronounced when the area is restricted to high recall.The paper gives a formula for the minimum AUCPR over a restricted recall interval.Source: §2.2 · p. 4, Figure 3 · p. 4

3. PR Space Metrics that Account for Unachievable Region

• A replacement metric should preserve AUCPR ordering on a single test set and have the same range across data sets, though preserving ordering may not suit cross-validation with differing skews.Source: §3 · p. 4
• AUCNPR subtracts minimum AUCPR so the worst ranking scores 0, then normalizes by the maximum, which is 1 for full recall or b−a over recall range a≤r≤b.Source: §3 · p. 5
• Across skews, AUCNPR gives the best ranking 1 and the worst 0, preserves same-test-set ordering, and makes cross-dataset comparisons more meaningful than AUCPR.Source: §3 · p. 5
• Normalizing by random-guessing AUCPR π leaves the score range skew-dependent and can produce negative scores for algorithms below random guessing.Source: §3 · p. 5
• When π=0 or π=1, AUCPRMIN and AUCNPR are undefined; the paper refers readers to its technical report for these degenerate data sets.Source: §3 · p. 5

4. Discussion and Recommendations

• When π=0.1, AUCPRMIN is approximately 0.05 and grows as π approaches 0.5; PR plots should show the minimum PR curve.The paper urges practitioners to account for the unachievable region when inspecting PR curves and AUCPR scores.Source: §4 · p. 5

4.1. Aggregation for Cross-Validation

• Fold-skew differences can make straightforward AUCPR or vertical-curve averaging overly optimistic; averaging AUCNPR reduces, but does not eliminate, skew’s effect.The folds can have different unachievable regions, and AUCNPR has the same range regardless of skew.Source: §4.1 · pp. 5–6

4.2. Aggregation among Different Tasks

• AUCPR 0.4 is worse than random for gender but reasonably high for genre; Table 2’s AUCNPR is more conservative, though it remains skew-sensitive.The cited predicates have different AUCPR ranges, so the same AUCPR value need not have the same interpretation.Source: §4.2 · p. 6, Table 2 · p. 6

4.3. Downsampling

• AUCNPR varied less than AUCPR across downsampling settings, yet at a 1:1 ratio its downsampled-test score was more than twice its original-test score.The original test set had a 1:24 positive-to-negative ratio (π=0.04).Source: §4.3 · p. 7, Table 3 · p. 7

4.4. F1 Score

• At π=0.33, A, B, and C all score F1=0.45, yet are respectively unachievable, near the minimum PR curve, and good precision at modest recall.F1 treats precision and recall as interchangeable despite their different constraints in PR space.Source: §4.4 · p. 7, Figure 4 · p. 8

• Theorems 1 and 2 precisely characterize the unachievable region of precision-recall space for a given positive-to-negative example ratio.Source: §5 · p. 8
• The characterization further informs the effects of downsampling on precision-recall evaluation.Source: §5 · p. 8
• The paper examines how the minimum PR curve affects F measure and score aggregation.Source: §5 · p. 8