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 mas- sive datasets whose items are often associ- ated 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 precision- recall (PR) or ROC curves for such sys- tems. Our novel approach, called PAULA, pro- vides theoretically guaranteed lower and up- per bounds on the underlying precision func- tion while relying on only O(log N) anno- tations for a resource with N items. This contrasts favorably with $\Theta$($\sqrt{}$N log N) anno- tations needed by commonly used sampling based methods. Our key insight is to capital- ize 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 mas- sive datasets whose items are often associ- ated 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 precision- recall (PR) or ROC curves for such sys- tems. Our novel approach, called PAULA, pro- vides theoretically guaranteed lower and up- per bounds on the underlying precision func- tion while relying on only O(log N) anno- tations for a resource with N items. This contrasts favorably with $\Theta$($\sqrt{}$N log N) anno- tations needed by commonly used sampling based methods. Our key insight is to capital- ize 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 mas- sive datasets whose items are often associ- ated 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 precision- recall (PR) or ROC curves for such sys- tems. Our novel approach, called PAULA, pro- vides theoretically guaranteed lower and up- per bounds on the underlying precision func- tion while relying on only O(log N) anno- tations for a resource with N items. This contrasts favorably with $\Theta$($\sqrt{}$N log N) anno- tations needed by commonly used sampling based methods. Our key insight is to capital- ize 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