GBDT库原理和使用的比较-技术圈

GBDT拥有广泛的应用，然而GBDT在大数据集存在性能问题。为此很多GBDT方法都聚焦在模型加速和并行计算，在本文中对比了最近的GBDT系统的优缺点。

背景介绍

有许多GBDT的库，虽然这些库提供了类似的功能，但它们的算法设计和系统实现有很大的不同：

比如哪些部分分别在GPU和CPU上实现，以及树增长的策略。但树模型整体的构建过程是类似的：每个决策树的构建深度从0到最大深度。采用基于贪心的节点分割算法递归地生长树，直到达到终止条件。

求解每个节点的分裂点的方法包括精确方法和近似方法：

开发高效的GBDT训练并行算法具有挑战性

寻找一个节点的最佳分割点的传统方法是通过枚举所有分割点，这种方法对于取值空间较大的情况下是非常昂贵的。

当前并行GBDT系统常见解决方案是使用基于直方图的近似，而不是枚举所有可能的分裂点，或者说列举多个有代表性的分裂点。

直方图近似是效率和准确性之间的权衡，但这种解决方案不适用于高维和稀疏问题，因为每个维度都需要与一个直方图关联。 在并行算法中，需要维护的直方图总数等于：线程数乘以特征数量。

并行度的关键粒度包括三个级别：

在节点级并行：一个线程专门用于查找节点的最佳分割，因此它将计算节点中所有特性的所有值的增益。

在特征级并行中：一个线程专门用于仅为一个节点的一个特征查找最佳值。因此一个线程计算一个节点的一个特征的所有值的增益。

在值级并行性中：一个线程计算节点中一个特征的一个值的增益。基于多核CPU的训练算法经常会适应节点级和特征级的并行性。

当训练问题由多个GPU或多个CPU处理时，需要对训练数据集进行分区，数据有三种划分方法：

基于实例的分区：将许多训练实例分配给机器，其余的实例分配给其他机器。这种分区方式的好处是，每台机器都有存储在其中的实例的全部信息。因此当计算一个实例的训练错误时，存储该实例的机器可以很容易地计算出它。

相比之下，基于特性的分区会将多个特性的所有值分配给一台机器。因此，计算训练错误要困难得多，因为机器没有计算实例的所有信息。但是，基于特征的划分的优点是，机器可以很容易地找到特征的最佳分割值，因为训练数据的所有特征值都存储在一起。

混合划分分区将训练数据集视为一个矩阵，每个GPU/CPU处理一个块或瓷砖。主流GBDT可以使用基于实例的分区或基于特性的分区。由于实现和维护的复杂性，混合划分方法并没有得到广泛的采用。

在CPU的并行中，有许多挑战：

为了解决这些挑战，现有的GBDT库可以在CPU上并行运行，并在并行性、节点分割和训练数据分区方面采用不同的设计。

为了利用GPU 的能力，需要在优化GBDT训练的并行性、节点分割和训练数据分区方面做大量的工作。

GPU上的XGBoost使用属性级和节点级并行性，对于属性级并行性，GPU线程块用于计算属性的最佳分割点。LightGBM CatBoost还使用寻找最佳分割点来避免在枚举所有可能的分割点的同时消耗过多内存。

所有实验中不同库的预测精度相似，与XGBoost和ThudergGBM相比，LightGBM和CatBoost往往具有较低的预测精度。

所有的库都可以在GPU上运行来显著提高效率。其次LightGBM通常在CPU上比其他现有库工作得更好，CatBoost在GPU实现是非常好的，但也需要更多的显存。

网络通信主要从两个方面出发：构建一个特征的直方图和在所有特征中找到最佳特征。