Abstract
The difficulty of multi-class classification generally increases with the number of classes. Using data from a subset of the classes, can we predict how well a classifier will scale with an increased number of classes? Under the assumptions that the classes are sampled identically and independently from a population, and that the classifier is based on independently learned scoring functions, we show that the expected accuracy when the classifier is trained on k classes is the (k-1)st moment of a certain distribution that can be estimated from data. We present an unbiased estimation method based on the theory, and demonstrate its application on a facial recognition example.
Introduction
In modern machine learning, scaling is a primary concern. A facial recognition system that achieves 99% accuracy on a set of 10 individuals will inevitably see a performance degradation when expanded to distinguish between 10,000 people. However, collecting and labeling data for massive label sets—such as every person on earth or every species of insect—is often prohibitively expensive.
Researchers typically develop algorithms on small "source" datasets, but they lack a principled way to predict how these models will scale. This paper addresses the challenge of performance extrapolation, providing a formal theory to estimate how a multi-class classifier's accuracy drops as the number of classes increases.
Methodology
The proposed framework treats the set of classes as random samples from a larger population. The focus is on marginal classifiers, where the "score" for one class (e.g., a logit or distance metric) is calculated independently of other classes in the set.
The core mathematical breakthrough is the proof that the average generalization accuracy for $k$ classes ($AGA_k$) is exactly the $(k-1)$-th moment of a "discriminability function" $D(u)$. This realization transforms a complex scaling problem into a classic statistical estimation task. To implement this, the authors introduce ClassExReg (Classification Extrapolation using Regression):
- Subsampling: Calculate accuracies for small subsets of the existing dataset (e.g., subsets of 10, 20, and 50 classes from a 100-class set).
- Basis Fitting: Use these data points to fit a linear model of the discriminability function $D(u)$ using basis functions such as splines.
- Extrapolation: Use the fitted model to calculate the $(k-1)$-th moment for a much larger $k$, projecting the accuracy curve into unobserved territory.
As shown in the figure above, the classification rule $H(x)$ selects the label with the highest score $M_y(x)$. The theory assumes these score functions are learned independently, which allows for the elegant moment-based derivation.
Experimental Results
The theory was validated across three distinct domains:
- Synthetic Simulations: Using multivariate Gaussian distributions, ClassExReg consistently achieved lower Root Mean Squared Error (RMSE) than traditional Kernel Density Estimation (KDE) methods, particularly when extrapolating to 10x or 20x the original number of classes.
- Labeled Faces in the Wild (LFW): On this standard facial recognition dataset (1,672 individuals), the method successfully predicted scaling behavior using OpenFace embeddings.
- Telugu OCR: Testing on an optical character recognition dataset with over 400 glyphs, ClassExReg accurately predicted the performance of complex models, including Deep Convolutional Neural Networks (CNNs). Despite the CNNs technically violating the "marginality" assumption during training, the method remained robust.
Discussion and Conclusion
ClassExReg offers a significant improvement over previous methods that relied on exponentiating initial estimates, which often led to exploding biases. By estimating the "moment" directly, ClassExReg remains stable even when extrapolating to 100,000 classes.
Future work will address the current limitations of the I.I.D. assumption, as real-world classes often exhibit hierarchical or clustered structures. Additionally, extending the framework beyond top-1 accuracy to metrics like "Top-5" accuracy or cost-sensitive risks remains an open area for research. Nonetheless, this work provides a vital tool for researchers to evaluate the scalability of their algorithms before committing to massive data collection efforts.
Summary updated