Log-time and Log-space Extreme Classification
This addresses efficiency bottlenecks in large-scale classification problems, though it appears incremental as it builds on structured prediction and dynamic programming.
The paper tackles the challenge of extreme classification by introducing LTLS, a technique that enables training and inference in logarithmic time and space, and shows it is often competitive with existing approaches on multiclass and multilabel datasets.
We present LTLS, a technique for multiclass and multilabel prediction that can perform training and inference in logarithmic time and space. LTLS embeds large classification problems into simple structured prediction problems and relies on efficient dynamic programming algorithms for inference. We train LTLS with stochastic gradient descent on a number of multiclass and multilabel datasets and show that despite its small memory footprint it is often competitive with existing approaches.