Logarithmic Time One-Against-Some

Abstract

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.

Cited by in corpus (14)

• Joint Optimization of Tree-based Index and Deep Model for Recommender Systems
• Fast Multi-Resolution Transformer Fine-tuning for Extreme Multi-label Text Classification
• Adversarial Extreme Multi-label Classification
• Unbiased scalable softmax optimization
• Quizbowl: The Case for Incremental Question Answering
• Efficient Loss-Based Decoding on Graphs For Extreme Classification
• Aggressive Sampling for Multi-class to Binary Reduction with Applications to Text Classification
• Extreme Classification in Log Memory
• Efficient Hierarchical Clustering for Classification and Anomaly Detection
• Contextual Memory Trees
• On the Calibration of Nested Dichotomies for Large Multiclass Tasks
• MEMOIR: Multi-class Extreme Classification with Inexact Margin
• Candidates vs. Noises Estimation for Large Multi-Class Classification Problem
• Context-aware Tree-based Deep Model for Recommender Systems