Logarithmic Time Online Multiclass prediction

Abstract

We study the problem of multiclass classification with an extremely large number of classes (k), with the goal of obtaining train and test time complexity logarithmic in the number of classes. We develop top-down tree construction approaches for constructing logarithmic depth trees. On the theoretical front, we formulate a new objective function, which is optimized at each node of the tree and creates dynamic partitions of the data which are both pure (in terms of class labels) and balanced. We demonstrate that under favorable conditions, we can construct logarithmic depth trees that have leaves with low label entropy. However, the objective function at the nodes is challenging to optimize computationally. We address the empirical problem with a new online decision tree construction procedure. Experiments demonstrate that this online algorithm quickly achieves improvement in test error compared to more common logarithmic training time approaches, which makes it a plausible method in computationally constrained large-k applications.

References in corpus (2)

• Multi-Label Prediction via Compressed Sensing
• Conditional Probability Tree Estimation Analysis and Algorithms

Cited by in corpus (18)

• Learning Tree-based Deep Model for Recommender Systems
• Joint Optimization of Tree-based Index and Deep Model for Recommender Systems
• Fast Multi-Resolution Transformer Fine-tuning for Extreme Multi-label Text Classification
• Extreme Classification in Log Memory using Count-Min Sketch: A Case Study of Amazon Search with 50M Products
• Distributed Optimization of Multi-Class SVMs
• LdSM: Logarithm-depth Streaming Multi-label Decision Trees
• Log-time and Log-space Extreme Classification
• Scalable Multilabel Prediction via Randomized Methods
• Efficient Loss-Based Decoding on Graphs For Extreme Classification
• Extreme Classification in Log Memory
• Efficient Hierarchical Clustering for Classification and Anomaly Detection
• A Hierarchical Spectral Method for Extreme Classification
• LightMC: A Dynamic and Efficient Multiclass Decomposition Algorithm
• Online probabilistic label trees
• Contextual Memory Trees
• Reinforced Decision Trees
• Candidates vs. Noises Estimation for Large Multi-Class Classification Problem
• On the Calibration of Nested Dichotomies for Large Multiclass Tasks