How Good Are My Predictions? Efficiently Approximating Precision-Recall Curves for Massive Datasets

Ashish Sabharwal, Hanie SedghiUAI 2017

Abstract

Evaluating the quality of massive datasets containing millions or billions of items is often prohibitively expensive due to the need for manual human labeling. This paper presents PAULA (Precision Approximation Using Logarithmic Annotations), an algorithm designed to approximate Precision-Recall (PR) curves with theoretical guarantees. By leveraging the monotonicity of ranked lists, PAULA reduces the required number of annotations from a square-root to a logarithmic scale relative to dataset size. Experimental results on large-scale resources like the Paraphrase Database (PPDB) demonstrate that PAULA provides tight, deterministic bounds at a fraction of the cost of traditional random sampling.

Introduction

Modern machine learning systems frequently produce massive resources, such as the 169-million-item Paraphrase Database (PPDB). While these items are typically ranked by confidence scores, understanding system performance requires a Precision-Recall (PR) curve. However, human annotation remains a major bottleneck; labeling enough data for a reliable curve using standard random sampling is often too costly for datasets of this scale. Consequently, many large resources are released without rigorous quality evaluation.

Methodology

PAULA introduces a deterministic approach to evaluation by exploiting the "strong monotonicity" property of ranked lists. In well-calibrated systems, items with higher confidence scores are generally more likely to be correct than those with lower scores.

  • Logarithmic Spacing: Instead of sampling uniformly, PAULA selects annotation points spaced geometrically (e.g., at ranks 100, 110, 121...).
  • Guaranteed Bounds: By calculating local precision at these intervals, PAULA constructs upper and lower step-function bounds. If the monotonicity assumption holds, the true precision curve is guaranteed to lie within these bounds.
  • Efficiency: Unlike standard sampling which requires $O(\sqrt{N \log N})$ annotations to reach a target accuracy, PAULA achieves comparable results with only $O(\log N)$ annotations. For a dataset of 2 billion items, PAULA might require only ~47,000 annotations, whereas traditional sampling would require millions.

Experimental Evaluation

The authors evaluated PAULA on two large-scale resources:

  1. PPDB (Paraphrase Database): A 169M item paraphrase database. A subset of 36,000 labeled items served as ground truth for validation.
  2. Science KB: A knowledge base with ~217,000 scientific triples. Since no ground truth existed for the full set, PAULA was used to estimate quality, with results validated by independent random point estimates.

Results

PAULA demonstrates significant efficiency gains over conventional methods. As shown in Figure 1, it requires an order of magnitude fewer annotations than conventional random sampling to achieve the same level of guaranteed accuracy.

Comparison of annotation requirements between PAULA and traditional sampling methods.

Furthermore, the bounds produced are remarkably tight. On the PPDB dataset, with only 11,000 annotations for a 36,000-item set, the upper and lower bounds successfully "sandwiched" the ground truth curve, becoming nearly indistinguishable from it as shown in Figure 2.

PAULA's upper and lower bounds tightly bounding the true precision curve.

In real-world scaling tests on the Science KB, PAULA provided a reliable PR curve using only 17,000 annotations, a task that would have required nearly 50,000 labels using standard sampling methods to reach the same confidence level.

Conclusion and Limitations

PAULA makes the evaluation of massive datasets feasible by shifting complexity from square-root to logarithmic scaling. The primary limitation is the dependency on monotonicity; if a system is poorly calibrated (where low-confidence items are more likely to be correct), the bounds may not hold. However, for most well-designed systems, PAULA provides a powerful tool for providing deterministic quality guarantees for large-scale machine learning outputs.

Summary updated

BibTeX
@inproceedings{sabharwal2017how,
  author = {Ashish Sabharwal and Hanie Sedghi},
  title = {{How Good Are My Predictions? Efficiently Approximating Precision-Recall Curves for Massive Datasets}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2017},
}
Figure