Logarithmic Time One-Against-Some
This addresses the computational bottleneck in multiclass classification for large-scale applications, offering exponential speed improvements while maintaining competitive accuracy.
The paper tackles multiclass classification by developing an online reduction method that scales logarithmically with the number of classes in training and prediction time, achieving substantially better statistical performance than previous approaches through a tighter boosting theorem and direct algorithmic translation.
We create a new online reduction of multiclass classification to binary classification for which training and prediction time scale logarithmically with the number of classes. Compared to previous approaches, we obtain substantially better statistical performance for two reasons: First, we prove a tighter and more complete boosting theorem, and second we translate the results more directly into an algorithm. We show that several simple techniques give rise to an algorithm that can compete with one-against-all in both space and predictive power while offering exponential improvements in speed when the number of classes is large.