Don't Label Twice: Quantity Beats Quality when Comparing Binary Classifiers on a Budget
Open accessAbstract
We study how to best spend a budget of noisy labels to compare the accuracy of two binary classifiers. It's common practice to collect and aggregate multiple noisy labels for a given data point into a less noisy label via a majority vote. We prove a theorem that runs counter to conventional wisdom. If the goal is to identify the better of two classifiers, we show it's best to spend the budget on collecting a single label for more samples. Our result follows from a non-trivial application of Cramér's theorem, a staple in the theory of large deviations. We discuss the implications of our work for the design of machine learning benchmarks, where they overturn some time-honored recommendations. In addition, our results provide sample size bounds superior to what follows from Hoeffding's bound.
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
For binary classification with judge errors independent of the performance of different models, a sufficiently large sample size guarantees correct rankings as long as the error rate is below 50%.
“For binary classification with judge errors that are independent of the performance of different models, a sufficiently large sample size guarantees correct rankings as long as the error rate is below 50% (Dorner & Hardt, 2024).”
From Limits to scalable evaluation at the frontier: LLM as Judge won't beat twice the data (2024) · cites this paper as Dorner & Hardt, 2024
Section 3 shows that when label accuracy exceeds 50% and the better classifier has a positive accuracy margin, noisy labels favor it in expectation. Section 3.3 bounds the probability of ranking the best classifier incorrectly as sample size grows, but guarantees a high probability of a correct ranking—not certainty for any finite sample. (LLM, conf=0.88)
Experimental — accuracy not yet measured
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Cites
No references could be resolved yet.
Research works printed but not linked: 26
- Aroyo, L. and Welty, C. Crowd truth: Harnessing disagreement in crowdsourcing a relation extraction gold standard. WebSci2013. ACM, 2013(2013), 2013.
- Aroyo, L. and Welty, C. Truth is a lie: Crowd truth and the seven myths of human annotation. AI Magazine, 36(1):15-24, 2015.
- Blum, A. and Hardt, M. The ladder: A reliable leaderboard for machine learning competitions. In Interna- tional Conference on Machine Learning, pp. 1006-1014. PMLR, 2015.
- Boland, P. J., Proschan, F., and Tong, Y. L. Modelling dependence in simple and indirect majority systems. Journal of Applied Probability, 26(1):81-88, 1989.
- Bowman, S. R., Angeli, G., Potts, C., and Manning, C. D. A large annotated corpus for learning natural language inference. arXiv preprint arXiv:1508.05326, 2015. · arXiv
- Chen, D., Yu, Z., and Bowman, S. R. Clean or annotate: How to spend a limited data collection budget. arXiv preprint arXiv:2110.08355, 2021. · arXiv
- Cheplygina, V. and Pluim, J. P. Crowd disagreement about medical images is informative. In Intravascular Imaging and Computer Assisted Stenting and Large-Scale Annotation of Biomedical Data and Expert Label Synthesis: 7th Joint International Workshop, CVII-STENT 2018 and Third International Workshop, LABELS 2018, Held in Conjunction with MICCAI 2018, Granada, Spain, September 16, 2018, Proceedings 3, pp. 105-111. Springer, 2018.
- Crammer, K., Kearns, M., and Wortman, J. Learning from data of variable quality. Advances in Neural Information Processing Systems, 18, 2005.
- Davani, A. M., Díaz, M., and Prabhakaran, V. Dealing with disagreements: Looking beyond the majority vote in subjective annotations. Transactions of the Association for Computational Linguistics, 10:92-110, 2022.
- Denton, E., Díaz, M., Kivlichan, I., Prabhakaran, V., and Rosen, R. Whose ground truth? accounting for individual and collective identities underlying dataset annotation. arXiv preprint arXiv:2112.04554, 2021. · arXiv
- Dolan, B. and Brockett, C. Automatically constructing a corpus of sentential paraphrases. In Third Inter- national Workshop on Paraphrasing (IWP2005), 2005.
- Dorner, F. E., Peychev, M., Konstantinov, N., Goel, N., Ash, E., and Vechev, M. Human-guided fair classification for natural language processing. arXiv preprint arXiv:2212.10154, 2022. · arXiv
- Fleisig, E., Amstutz, A., Atalla, C., Blodgett, S. L., Daumé III, H., Olteanu, A., Sheng, E., Vann, D., and Wallach, H. Fair-prism: Evaluating fairness-related harms in text generation. In Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics. Association for Computational Linguistics, 2023.
- Gordon, M. L., Lam, M. S., Park, J. S., Patel, K., Hancock, J., Hashimoto, T., and Bernstein, M. S. Jury learning: Integrating dissenting voices into machine learning models. In Proceedings of the 2022 CHI Conference on Human Factors in Computing Systems, pp. 1-19, 2022.
- Hardt, M. and Recht, B. Patterns, predictions, and actions: Foundations of machine learning. Princeton University Press, 2022.
- Klenke, A. Probability theory: a comprehensive course. Springer Science & Business Media, 2013.
- Köpf, A., Kilcher, Y., von Rütte, D., Anagnostidis, S., Tam, Z.-R., Stevens, K., Barhoum, A., Duc, N. M., Stanley, O., Nagyfi, R., et al. Openassistant conversations-democratizing large language model alignment. arXiv preprint arXiv:2304.07327, 2023. · arXiv
- Lin, C., Weld, D., et al. To re (label), or not to re (label). In Proceedings of the AAAI Conference on Human Computation and Crowdsourcing, volume 2, pp. 151-158, 2014.
- Mania, H. and Sra, S. Why do classifier accuracies show linear trends under distribution shift? arXiv preprint arXiv:2012.15483, 2020. · arXiv
- Marelli, M., Bentivogli, L., Baroni, M., Bernardi, R., Menini, S., and Zamparelli, R. Semeval-2014 task 1: Evaluation of compositional distributional semantic models on full sentences through semantic relatedness and textual entailment. In Proceedings of the 8th international workshop on semantic evaluation (SemEval 2014), pp. 1-8, 2014.
- Nguyen, H. Q., Lam, K., Le, L. T., Pham, H. H., Tran, D. Q., Nguyen, D. B., Le, D. D., Pham, C. M., Tong, H. T., Dinh, D. H., et al. Vindr-cxr: An open dataset of chest x-rays with radiologist's annotations. Scientific Data, 9(1):429, 2022.
- Ouyang, L., Wu, J., Jiang, X., Almeida, D., Wainwright, C., Mishkin, P., Zhang, C., Agarwal, S., Slama, K., Ray, A., et al. Training language models to follow instructions with human feedback. Advances in Neural Information Processing Systems, 35:27730-27744, 2022.
- Prabhakaran, V., Davani, A. M., and Diaz, M. On releasing annotator-level labels and information in datasets. arXiv preprint arXiv:2110.05699, 2021. · arXiv
- Ramponi, A. and Leonardelli, E. Dh-fbk at semeval-2022 task 4: leveraging annotators' disagreement and multiple data views for patronizing language detection. In Proceedings of the 16th International Workshop on Semantic Evaluation (SemEval-2022), pp. 324-334, 2022.
- Recht, B., Roelofs, R., Schmidt, L., and Shankar, V. Do imagenet classifiers generalize to imagenet? In International conference on machine learning, pp. 5389-5400. PMLR, 2019.
- Russakovsky, O., Deng, J., Su, H., Krause, J., Satheesh, S., Ma, S., Huang, Z., Karpathy, A., Khosla, A., Bernstein, M., et al. Imagenet large scale visual recognition challenge. International journal of computer vision, 115:211-252, 2015.
Cited by
Sorted by citations
Limits to scalable evaluation at the frontier: LLM as Judge won't beat twice the data
Dorner, F. E., Nastl, V. Y., & Hardt, M. (2024) · arXiv · doi:10.48550/arxiv.2410.13341
“…out that high agreement is also not necessary for stable rankings: For binary classification with judge errors that are independent of the performance of different models, a sufficiently large sample size guarantees correct rankings as long as the error rate is below 50% (Dorner & Hardt, 2024).”
Self-citation
- Authors
- Dorner, F. E., & Hardt, M.
- Affiliations
- Max Planck Society (DE)
- Venue
- arXiv
- Publisher
- arXiv
- Published
- 2024
- ISSN
- 2331-8422 (ISSN-L)
- arXiv
- 2402.02249
- OpenAlex
- W4391590869
- Cited by
- 1
- References
- 0
- Citations by year
- 2025: 1
- Type
- posted content
- Language
- en
- Open access
- green
- arxiv.org
- Licence
- Locations
- arXiv (Cornell University) (submittedVersion, cc-by-nc-nd)
- arXiv (Cornell University)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Machine Learning and Data Classification
- Physical Sciences › Computer Science › Artificial Intelligence › Machine Learning and Algorithms
- Physical Sciences › Computer Science › Artificial Intelligence › Stochastic Gradient Optimization Techniques
- Keywords
- label noise, majority voting, Cramér's theorem, large deviations, sample size bounds, Hoeffding inequality, machine learning benchmark
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
