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

Ashish Sabharwal, Hanie Sedghi
Proceedings of the 33rd Conference on Uncertainty in Artificial Intelligence, PMLR R15:411-420, 2017.

Abstract

Large scale machine learning produces massive datasets whose items are often associated with a confidence level and can thus be ranked. However, computing the precision of these resources requires human annotation, which is often prohibitively expensive and is therefore skipped. We consider the problem of cost-effectively approximating precisionrecall (PR) or ROC curves for such systems. Our novel approach, called PAULA, provides theoretically guaranteed lower and upper bounds on the underlying precision function while relying on only O(log N) annotations for a resource with N items. This contrasts favorably with $\Theta$($\sqrt{}$N log N) annotations needed by commonly used sampling based methods. Our key insight is to capitalize on a natural monotonicity property of the underlying confidence-based ranking. PAULA provides tight bounds for PR curves using, e.g., only 17K annotations for resources with 200K items and 48K annotations for resources with 2B items. We use PAULA to evaluate a subset of the much utilized PPDB paraphrase database and a recent Science knowledge base.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR15-sabharwal17a, title = {How Good Are My Predictions? Efficiently Approximating Precision-Recall Curves for Massive Datasets}, author = {Sabharwal, Ashish and Sedghi, Hanie}, booktitle = {Proceedings of the 33rd Conference on Uncertainty in Artificial Intelligence}, pages = {411--420}, year = {2017}, editor = {Elidan, Gal and Kersting, Kristian}, volume = {R15}, series = {Proceedings of Machine Learning Research}, month = {11--15 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r15/main/assets/sabharwal17a/sabharwal17a.pdf}, url = {https://proceedings.mlr.press/r15/sabharwal17a.html}, abstract = {Large scale machine learning produces massive datasets whose items are often associated with a confidence level and can thus be ranked. However, computing the precision of these resources requires human annotation, which is often prohibitively expensive and is therefore skipped. We consider the problem of cost-effectively approximating precisionrecall (PR) or ROC curves for such systems. Our novel approach, called PAULA, provides theoretically guaranteed lower and upper bounds on the underlying precision function while relying on only O(log N) annotations for a resource with N items. This contrasts favorably with $\Theta$($\sqrt{}$N log N) annotations needed by commonly used sampling based methods. Our key insight is to capitalize on a natural monotonicity property of the underlying confidence-based ranking. PAULA provides tight bounds for PR curves using, e.g., only 17K annotations for resources with 200K items and 48K annotations for resources with 2B items. We use PAULA to evaluate a subset of the much utilized PPDB paraphrase database and a recent Science knowledge base.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T How Good Are My Predictions? Efficiently Approximating Precision-Recall Curves for Massive Datasets %A Ashish Sabharwal %A Hanie Sedghi %B Proceedings of the 33rd Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2017 %E Gal Elidan %E Kristian Kersting %F pmlr-vR15-sabharwal17a %I PMLR %P 411--420 %U https://proceedings.mlr.press/r15/sabharwal17a.html %V R15 %X Large scale machine learning produces massive datasets whose items are often associated with a confidence level and can thus be ranked. However, computing the precision of these resources requires human annotation, which is often prohibitively expensive and is therefore skipped. We consider the problem of cost-effectively approximating precisionrecall (PR) or ROC curves for such systems. Our novel approach, called PAULA, provides theoretically guaranteed lower and upper bounds on the underlying precision function while relying on only O(log N) annotations for a resource with N items. This contrasts favorably with $\Theta$($\sqrt{}$N log N) annotations needed by commonly used sampling based methods. Our key insight is to capitalize on a natural monotonicity property of the underlying confidence-based ranking. PAULA provides tight bounds for PR curves using, e.g., only 17K annotations for resources with 200K items and 48K annotations for resources with 2B items. We use PAULA to evaluate a subset of the much utilized PPDB paraphrase database and a recent Science knowledge base. %Z Reissued by PMLR on 04 October 2026.
APA
Sabharwal, A. & Sedghi, H.. (2017). How Good Are My Predictions? Efficiently Approximating Precision-Recall Curves for Massive Datasets. Proceedings of the 33rd Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R15:411-420 Available from https://proceedings.mlr.press/r15/sabharwal17a.html. Reissued by PMLR on 04 October 2026.

Related Material