Logarithmic Time Online Multiclass prediction
This addresses computational efficiency for large-scale multiclass classification problems, representing an incremental improvement over existing logarithmic-time approaches.
The paper tackles multiclass classification with extremely large numbers of classes by developing tree-based approaches to achieve logarithmic time complexity in both training and testing, demonstrating that their online algorithm quickly improves test error compared to existing logarithmic-time methods.
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.