Model comparison needs many labels to certify the best choice
How Many Labels Does Model Choice Need? Certificates and Budgets for Selective Prediction
Machine Learning
Summary
Choosing the best machine learning model often requires comparing their performance using labeled data. The authors study how many labels are actually needed to confidently decide which model is better when models have similar predictions but differ in confidence. They find that certifying the top model usually demands a large part of the labeled data, much more than simply agreeing on accuracy. Their findings also show that even with some tolerance for error, a significant number of labels must be checked. This work links the way model confidence rankings affect the amount of labeled data needed for reliable model selection.
What this means in practice
- •For machine learning engineers: Plan data labeling efforts to certify the best model choice with confidence rankings and label budgets.
- •For data labeling teams: Use stopping tests based on confidence scores to reduce labeling while ensuring model selection accuracy.
Authors
Tetsuji Kuboyama
Abstract
Classifiers can make identical predictions yet require labels to compare their selective performance: confidence ranks weight the same errors differently. We quantify this requirement for the area under the generalized risk-coverage curve (AUGRC). A prelabel lower bound rules out insufficient budgets. With all labels known, a covering linear program bounds the minimum number of labels sufficient to fix the winner (the certificate size) within $K-1$ labels for $K$ candidates. For fixed $K$, independent uniform orders and identical predictions, the prelabel bound approaches one quarter of the pool. With iid Bernoulli errors independent of the orders, every exact acquisition policy reads almost all labels asymptotically, although a two-candidate certificate needs only half. Across 108 feature-panel comparisons on nine datasets, disagreement labels settle every accuracy choice but no AUGRC choice. A 20% budget is ruled out in 96 conditions; certificates need 56-57% on average. On ten conditions with pretrained image classifiers, confidence-score choice reads 68-91% of 10,000 labels for exact selection and 50-67% with AUGRC tolerance $5\times10^{-4}$. An exact stopping test works with any acquisition order. Together, these results link confidence ranks to label budgets and certified model comparison.