We study the problem of multiclass classification with an extremely large number of classes, 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 small error rates relative to more common O(k) approaches and simultaneously achieves significant improvement in test error compared to other logarithmic training time approaches.

本文研究多类别分类问题，提出了一种新的基于树的方法，通过动态分区构造深度对数的树，能够在类别数较大的情况下在训练和测试时间上实现对数复杂度；同时采用在线决策树构建程序解决了节点目标函数优化的挑战，实验证明该算法显著提高了分类准确率，适用于大规模应用中的场景。

对数时间在线多分类预测