Adaptive Stratified Sampling for Precision-Recall Estimation

Ashish Sabharwal, Yexiang Xue
Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence, PMLR R16:824-833, 2018.

Abstract

We propose a new algorithm for computing a constant-factor approximation of precision- recall (PR) curves for massive noisy datasets produced by generative models. Assessing va- lidity of items in such datasets requires human annotation, which is costly and must be mini- mized. Our algorithm, ADASTRAT, is the first data-aware method for this task. It chooses the next point to query on the PR curve adaptively, based on previous observations. It then selects specific items to annotate using stratified sam- pling. Under a mild monotonicity assumption, ADASTRAT outputs a guaranteed approxima- tion of the underlying precision function, while using a number of annotations that scales very slowly with N, the dataset size. For exam- ple, when the minimum precision is bounded by a constant, it issues only log log N preci- sion queries. In general, it has a regret of no more than log log N w.r.t. an oracle that is- sues queries at data-dependent (unknown) op- timal points. On a scaled-up NLP dataset of 3.5M items, ADASTRAT achieves a remark- ably close approximation of the true precision function using only 18 precision queries, 13x fewer than best previous approaches.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR16-sabharwal18a, title = {Adaptive Stratified Sampling for Precision-Recall Estimation}, author = {Sabharwal, Ashish and Xue, Yexiang}, booktitle = {Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence}, pages = {824--833}, year = {2018}, editor = {Globerson, Amir and Silva, Ricardo}, volume = {R16}, series = {Proceedings of Machine Learning Research}, month = {06--10 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r16/main/assets/sabharwal18a/sabharwal18a.pdf}, url = {https://proceedings.mlr.press/r16/sabharwal18a.html}, abstract = {We propose a new algorithm for computing a constant-factor approximation of precision- recall (PR) curves for massive noisy datasets produced by generative models. Assessing va- lidity of items in such datasets requires human annotation, which is costly and must be mini- mized. Our algorithm, ADASTRAT, is the first data-aware method for this task. It chooses the next point to query on the PR curve adaptively, based on previous observations. It then selects specific items to annotate using stratified sam- pling. Under a mild monotonicity assumption, ADASTRAT outputs a guaranteed approxima- tion of the underlying precision function, while using a number of annotations that scales very slowly with N, the dataset size. For exam- ple, when the minimum precision is bounded by a constant, it issues only log log N preci- sion queries. In general, it has a regret of no more than log log N w.r.t. an oracle that is- sues queries at data-dependent (unknown) op- timal points. On a scaled-up NLP dataset of 3.5M items, ADASTRAT achieves a remark- ably close approximation of the true precision function using only 18 precision queries, 13x fewer than best previous approaches.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Adaptive Stratified Sampling for Precision-Recall Estimation %A Ashish Sabharwal %A Yexiang Xue %B Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2018 %E Amir Globerson %E Ricardo Silva %F pmlr-vR16-sabharwal18a %I PMLR %P 824--833 %U https://proceedings.mlr.press/r16/sabharwal18a.html %V R16 %X We propose a new algorithm for computing a constant-factor approximation of precision- recall (PR) curves for massive noisy datasets produced by generative models. Assessing va- lidity of items in such datasets requires human annotation, which is costly and must be mini- mized. Our algorithm, ADASTRAT, is the first data-aware method for this task. It chooses the next point to query on the PR curve adaptively, based on previous observations. It then selects specific items to annotate using stratified sam- pling. Under a mild monotonicity assumption, ADASTRAT outputs a guaranteed approxima- tion of the underlying precision function, while using a number of annotations that scales very slowly with N, the dataset size. For exam- ple, when the minimum precision is bounded by a constant, it issues only log log N preci- sion queries. In general, it has a regret of no more than log log N w.r.t. an oracle that is- sues queries at data-dependent (unknown) op- timal points. On a scaled-up NLP dataset of 3.5M items, ADASTRAT achieves a remark- ably close approximation of the true precision function using only 18 precision queries, 13x fewer than best previous approaches. %Z Reissued by PMLR on 04 October 2026.
APA
Sabharwal, A. & Xue, Y.. (2018). Adaptive Stratified Sampling for Precision-Recall Estimation. Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R16:824-833 Available from https://proceedings.mlr.press/r16/sabharwal18a.html. Reissued by PMLR on 04 October 2026.

Related Material