Gradient Boosted Decision Trees for High Dimensional Sparse Output
Gradient Boosted Decision Trees for High Dimensional Sparse Output
复制标题
DOI：
--
复制
发表时间：
2017-08
期刊：
影响因子：
--
通讯作者：
Si Si-Si;Huan Zhang;S. Keerthi;D. Mahajan;I. Dhillon;Cho-Jui Hsieh
中科院分区：
文献类型：
--
作者：
Si Si-Si;Huan Zhang;S. Keerthi;D. Mahajan;I. Dhillon;Cho-Jui Hsieh
在本文中，我们研究了输出空间高维且稀疏时的梯度提升决策树（GBDT）。例如，在多标签分类中，输出空间是 L 维 0/1 向量，其中 L 是标签数量，在许多现代应用中，标签数量可以增长到数百万甚至更多。我们表明，在这种情况下，普通 GBDT 很容易耗尽内存或遇到几乎永远的运行时间，并提出了一种新的 GBDT 变体 GBDT-SPARSE，通过采用 L0 正则化来解决这个问题。然后我们详细讨论如何利用这种稀疏性进行 GBDT 训练，包括分割节点、计算稀疏残差以及在亚线性时间内进行预测。最后，我们将我们的算法应用于极端的多标签分类问题，并表明所提出的 GBDT-SPARSE 与现有方法相比，在模型大小和预测时间方面实现了一个数量级的改进，同时产生了相似的性能。
In this paper, we study the gradient boosted decision trees (GBDT) when the output space is high dimensional and sparse. For example, in multilabel classification, the output space is a L-dimensional 0/1 vector, where L is number of labels that can grow to millions and beyond in many modern applications. We show that vanilla GBDT can easily run out of memory or encounter near-forever running time in this regime, and propose a new GBDT variant, GBDT-SPARSE, to resolve this problem by employing L0 regularization. We then discuss in detail how to utilize this sparsity to conduct GBDT training, including splitting the nodes, computing the sparse residual, and predicting in sub-linear time. Finally, we apply our algorithm to extreme multilabel classification problems, and show that the proposed GBDT-SPARSE achieves an order of magnitude improvements in model size and prediction time over existing methods, while yielding similar performance.