来源：机器之心

参与：李亚洲
原文链接：微软开源GB框架LightGBM，表现超越已有boosting工具
本文经机器之心（微信公众号：almosthuman2014）授权转载，禁止二次转载

LightGBM（Light Gradient Boosting Machine）是一个基于决策树算法的快速的、分布式的、高性能 gradient boosting（GBDT、GBRT、GBM 或 MART）框架，可被用于排行、分类以及其他许多机器学习任务中。

开源项目地址：https://github.com/Microsoft/LightGBM

LightGBM 是一个梯度 boosting 框架，使用基于学习算法的决策树。它可以说是分布式的，高效的，它有以下优势：

• 更快的训练效率
• 低内存使用
• 更好的准确率
• 支持并行学习
• 可处理大规模数据

在公开数据上的实验表明 LightGBM 能在学习效率和准确率上都表现出比其他已有 boosting 工具更好的表现，而且有着更低的内存消耗。此外，实验也表明 LightGBM 通过使用多台机器进行特定设定的训练，它能取得线性加速。

优化速度和内存使用

很多 boosting 工具使用 pre-sorted based 算法进行决策树学习。这是一种简单的解决方案，但不易于优化。

LightGBM 使用 histogram based 算法，将连续特征（属性）值装进离散的容器中，从而加速训练流程并减少内存使用。

稀疏优化

只需要 O(#non_zero_data) 来构建进行稀疏特征的 histogram。

准确率优化

大部分决策树学习算法通过 level（depth）-wise 成长决策树，如下图所示：

通过 leaf-wise 成长决策树，它将选择带有 max delta loss 的 leaf 进行成长。在长到同样的 #leaf 时，Leaf-wise 算法要比 level-wise 算法能减少更多的损失。

网络通信优化

在 LightGBM 并行学习中，只需要使用一些 collective 通信算法，像是「All reduce」、 「All gather」和「Reduce scatter」。这些 collective 通信算法要比点到点通信能提供更好的表现。

并行学习中的优化

LightGBM 能提供以下并行学习算法。

特征并行

传统算法的特征并行意图在决策树种并行「Find Best Split」，有着以下两个缺点：

• 因为不能加速「split」，所以有着计算费用，其时间复杂性是 O(#data)，因此在 #data 很大时，特征并行不能加速。
• 需要 split 结果的通信，这大约花费 O(#data/8) (one bit for one data)。

在数据很大时，因为特征并行不能加速，因此在 LightGBM 中进行了小的改变：不再是垂直的分割数据，每个 worker 持有全部数据。因此由于每个 worker 都知道如何 split 数据，LightGBM 就不需要通信数据的 split 结果。而且由于 #data 不会更大，所以在每个机器中持有全部数据也是合理的。

然而，在 #data 较大时，该特征并行算法仍遭受进行”split”的计算费用，所以当 #data 较大时使用数据并行更好。

数据并行

传统算法的数据并行意在并行全部决策学习，其缺点是高通信成本。而在 LightGBM 数据并行中减少了通信成本。

LightGBM 还有其他的许多特征，想了解更多可查看该网址：https://github.com/Microsoft/LightGBM/wiki/Features。