特性

这是 LightGBM 工作原理的概念性概述[1]。我们假设您熟悉决策树 boosting 算法，以便将重点放在 LightGBM 与其他 boosting 包可能不同的方面。有关详细算法，请参阅引文或源代码。

速度和内存使用优化

许多 boosting 工具使用基于预排序的算法[2, 3]（例如 xgboost 中的默认算法）进行决策树学习。这是一个简单的解决方案，但不容易优化。

LightGBM 使用基于直方图的算法[4, 5, 6]，将连续特征（属性）值分桶到离散的 bin 中。这加快了训练速度并减少了内存使用。基于直方图的算法的优点包括以下几点

  • 减少计算每次分裂增益的成本

    • 基于预排序的算法的时间复杂度为 O(#data)

    • 计算直方图的时间复杂度为 O(#data)，但这只涉及快速求和操作。直方图构建完成后，基于直方图的算法的时间复杂度为 O(#bins)，而 #bins 远小于 #data。

  • 使用直方图相减进一步加速

    • 要在二叉树中获取一个叶子的直方图，可以使用其父节点与其兄弟节点的直方图相减

    • 因此，它只需要为其中一个叶子（其数据量 #data 小于其兄弟节点）构建直方图。然后，通过直方图相减可以以很小的成本（O(#bins)）获得其兄弟节点的直方图

  • 减少内存使用

    • 将连续值替换为离散的 bin。如果 #bins 较小，可以使用小数据类型，例如 uint8_t，来存储训练数据

    • 无需存储用于预排序特征值的额外信息

  • 减少分布式学习的通信成本

稀疏优化

  • 只需 O(2 * #non_zero_data) 即可构建稀疏特征的直方图

精度优化

逐叶（最优优先）树生长

大多数决策树学习算法按层（深度）生长树，如下图所示

A diagram depicting level wise tree growth in which the best possible node is split one level down. The strategy results in a symmetric tree, where every node in a level has child nodes resulting in an additional layer of depth.

LightGBM 按叶子（最优优先）生长树[7]。它会选择 delta loss 最大的叶子进行生长。在叶子数量 #leaf 固定时，逐叶算法通常比按层算法获得更低的损失。

当数据量 #data 较小时，逐叶生长可能导致过拟合，因此 LightGBM 包含 max_depth 参数来限制树的深度。但是，即使指定了 max_depth，树仍然会按叶子生长。

A diagram depicting leaf wise tree growth in which only the node with the highest loss change is split and not bother with the rest of the nodes in the same level. This results in an asymmetrical tree where subsequent splitting is happening only on one side of the tree.

类别特征的最优分裂

通常使用独热编码表示类别特征，但这种方法对于树学习器来说不是最优的。特别是对于高基数类别特征，基于独热特征构建的树往往不平衡，需要非常深才能达到良好的精度。

代替独热编码，最优的解决方案是将类别特征的类别划分成 2 个子集进行分裂。如果特征有 k 个类别，则有 2^(k-1) - 1 种可能的划分。但对于回归树，存在一种高效的解决方案[8]。它只需要大约 O(k * log(k)) 的时间来找到最优划分。

基本思想是在每次分裂时根据训练目标对类别进行排序。更具体地说，LightGBM 根据累积值（sum_gradient / sum_hessian）对直方图（针对类别特征）进行排序，然后在排序后的直方图上找到最优分裂点。

网络通信优化

在 LightGBM 的分布式学习中，只需要使用一些集合通信算法，例如“All reduce”、“All gather”和“Reduce scatter”。LightGBM 实现了最先进的算法[9]。这些集合通信算法可以提供比点对点通信更好的性能。

分布式学习优化

LightGBM 提供以下分布式学习算法。

特征并行

传统算法

特征并行旨在并行化决策树中的“寻找最优分裂”。传统特征并行的过程是

  1. 垂直划分数据（不同的机器拥有不同的特征集）。

  2. 工作节点在本地特征集上寻找本地最优分裂点 {特征，阈值}。

  3. 工作节点之间相互通信本地最优分裂点，并找到全局最优分裂点。

  4. 拥有全局最优分裂点的工作节点执行分裂，然后将数据的分裂结果发送给其他工作节点。

  5. 其他工作节点根据收到的数据进行分裂。

传统特征并行的缺点

  • 存在计算开销，因为它无法加速“分裂”，“分裂”的时间复杂度是 O(#data)。因此，当数据量 #data 较大时，特征并行无法很好地加速。

  • 需要通信分裂结果，这大约花费 O(#data / 8) 的开销（一个数据点需要一位）。

LightGBM 中的特征并行

由于当数据量 #data 较大时特征并行无法很好地加速，我们做了一个小改动：不是垂直划分数据，而是每个工作节点都持有完整的数据。因此，LightGBM 不需要通信数据的分裂结果，因为每个工作节点都知道如何分裂数据。而且 #data 不会更大，所以在每台机器中持有完整数据是合理的。

LightGBM 中的特征并行的过程

  1. 工作节点在本地特征集上寻找本地最优分裂点 {特征，阈值}。

  2. 工作节点之间相互通信本地最优分裂点，并找到全局最优分裂点。

  3. 执行最优分裂。

然而，当数据量 #data 较大时，这个特征并行算法在“分裂”时仍然存在计算开销。因此，当数据量 #data 较大时，最好使用数据并行。

数据并行

传统算法

数据并行旨在并行化整个决策树学习过程。数据并行的过程是

  1. 水平划分数据。

  2. 工作节点使用本地数据构建本地直方图。

  3. 合并所有本地直方图以得到全局直方图。

  4. 从合并的全局直方图找到最优分裂点，然后执行分裂。

传统数据并行的缺点

  • 高通信成本。如果使用点对点通信算法，一台机器的通信成本大约为 O(#machine * #feature * #bin)。如果使用集合通信算法（例如“All Reduce”），通信成本大约为 O(2 * #feature * #bin)（请查阅 [9] 中 4.5 章关于“All Reduce”的成本）。

LightGBM 中的数据并行

我们降低了 LightGBM 中数据并行的通信成本

  1. LightGBM 没有使用“合并所有本地直方图以得到全局直方图”，而是使用“Reduce Scatter”为不同的工作节点合并不同（不重叠）特征的直方图。然后工作节点在本地合并的直方图上找到本地最优分裂点，并同步全局最优分裂点。

  2. 如前所述，LightGBM 使用直方图相减来加速训练。基于此，我们只需通信一个叶子的直方图，并通过相减获得其兄弟节点的直方图。

综合来看，LightGBM 中数据并行的时间复杂度为 O(0.5 * #feature * #bin)。

投票并行

投票并行将 数据并行 中的通信成本进一步降低到常数成本。它使用两阶段投票来减少特征直方图的通信成本[10]。

GPU 支持

感谢 @huanzhang12 贡献此特性。请阅读 [11] 获取更多详细信息。

应用和评估指标

LightGBM 支持以下应用

  • 回归，目标函数是 L2 loss

  • 二分类，目标函数是 logloss

  • 多分类

  • 交叉熵，目标函数是 logloss 并支持在非二分类标签上进行训练

  • LambdaRank，目标函数是带有 NDCG 的 LambdaRank

LightGBM 支持以下评估指标

  • L1 loss

  • L2 loss

  • Log loss

  • 分类错误率

  • AUC

  • NDCG

  • MAP

  • 多分类 log loss

  • 多分类错误率

  • AUC-mu (v3.0.0 新增)

  • 平均精度 (v3.1.0 新增)

  • Fair

  • Huber

  • 泊松

  • 分位数

  • MAPE

  • Kullback-Leibler

  • Gamma

  • Tweedie

有关更多详细信息，请参阅参数。

其他特性

  • 逐叶生长树时限制树的 max_depth

  • DART

  • L1/L2 正则化

  • Bagging

  • 列（特征）子抽样

  • 使用输入的 GBDT 模型继续训练

  • 使用输入的 score 文件继续训练

  • 加权训练

  • 训练期间输出验证评估指标

  • 多个验证数据集

  • 多个评估指标

  • 提前停止（训练和预测均可）

  • 预测叶子索引

有关更多详细信息，请参阅参数。

参考文献

[1] Guolin Ke, Qi Meng, Thomas Finley, Taifeng Wang, Wei Chen, Weidong Ma, Qiwei Ye, Tie-Yan Liu. “LightGBM: A Highly Efficient Gradient Boosting Decision Tree.” Advances in Neural Information Processing Systems 30 (NIPS 2017), pp. 3149-3157.

[2] Mehta, Manish, Rakesh Agrawal, and Jorma Rissanen. “SLIQ: A fast scalable classifier for data mining.” International Conference on Extending Database Technology. Springer Berlin Heidelberg, 1996.

[3] Shafer, John, Rakesh Agrawal, and Manish Mehta. “SPRINT: A scalable parallel classifier for data mining.” Proc. 1996 Int. Conf. Very Large Data Bases. 1996.

[4] Ranka, Sanjay, and V. Singh. “CLOUDS: A decision tree classifier for large datasets.” Proceedings of the 4th Knowledge Discovery and Data Mining Conference. 1998.

[5] Machado, F. P. “Communication and memory efficient parallel decision tree construction.” (2003).

[6] Li, Ping, Qiang Wu, and Christopher J. Burges. “Mcrank: Learning to rank using multiple classification and gradient boosting.” Advances in Neural Information Processing Systems 20 (NIPS 2007).

[7] Shi, Haijian. “Best-first decision tree learning.” Diss. The University of Waikato, 2007.

[8] Walter D. Fisher. “On Grouping for Maximum Homogeneity.” Journal of the American Statistical Association. Vol. 53, No. 284 (Dec., 1958), pp. 789-798.

[9] Thakur, Rajeev, Rolf Rabenseifner, and William Gropp. “Optimization of collective communication operations in MPICH.” International Journal of High Performance Computing Applications 19.1 (2005), pp. 49-66.

[10] Qi Meng, Guolin Ke, Taifeng Wang, Wei Chen, Qiwei Ye, Zhi-Ming Ma, Tie-Yan Liu. “A Communication-Efficient Parallel Algorithm for Decision Tree.” Advances in Neural Information Processing Systems 29 (NIPS 2016), pp. 1279-1287.

[11] Huan Zhang, Si Si and Cho-Jui Hsieh. “GPU Acceleration for Large-scale Tree Boosting.” SysML Conference, 2018.