LightGBM算法初探

本文共3700余字，包含极少数学公式，预计阅读时间20分钟

Light Gradient Boosting Machine (LightGBM)是一个由微软亚洲研究院分布式机器学习工具包（DMTK）团队开源的基于决策树算法的分布式梯度提升（Gradient Boosting Decision Tree，GBDT）框架。

在之前Argo的文章中，我们已经详细的介绍过GBDT算法及其重要的实现XGBoost算法的原理。GBDT是机器学习中的一个非常流行并且有效的算法模型，它是一个基于决策树的梯度提升算法。在Kaggle比赛中，XGBoost等基于GBDT思想的算法有着非常好的表现，据统计Kaggle比赛中，50%以上的冠军方案都是基于GBDT算法。但是大训练样本和高维度特征的数据环境下，GBDT算法的性能以及准确性却面临了极大的挑战。为了解决这些问题，LightGBM应运而生，引用LightGBM官网对该框架的介绍，LightGBM具有以下特点：

更快的训练速度和效率

更低的内存使用

更好的准确率

支持并行化学习

可以处理大规模数据

下图是LightGBM在GitHub主页上展示的在五个不同数据集上得到的性能实验数据，比起XGBoost算法，LightGBM算法在准确度上与之不相上下，但在速度和内存的消耗上有更明显的优势。

耗时比较

准确率比较

内存消耗

LightGBM是如何做到对GBDT算法的性能有如此大的提升呢？本文将会从以下几个方面介绍该算法：

GBDT算法的缺点

LightGBM算法原理

单边梯度采样算法(GOSS)

Exclusive Feature Bundling 算法

LightGBM的其他优化

总结

一. GBDT算法的缺点

Argo之前的文章讲解过

梯度提升决策树算法

的实现原理。它是基于决策树的提升算法，采用前向分布算法，在每次迭代中，通过负梯度拟合残差，从而学习到一颗决策树。在生成决策树的过程中，进行特征选择节点分裂时，需要对特征值进行排序，遍历所有可能的划分点，然后计算信息增益，从而选择出最优的分裂点。每轮迭代都会对整个训练集进行遍历，这样既耗费内存，也非常的耗时。

在这部分比较常用的优化算法有预排序，就是对所有特征值优先排序，计算每个划分点的增益值，并且保存在内存中。在迭代的过程中通过查表的方式进行选择最优分裂点。XGBoost算法已经提供了这种方式的优化，然而它在面对海量数据和特征维度很高的数据集时，算法的效率和扩展性很难让人满意。

如果要对GBDT进行优化，有两个方面：1. 降低训练集的规模，很显然，这样可以减少计算量，提高算法的计算效率。2. 降低特征维度，这样的话，可以在选择分裂点的时候减少计算量，提高算法的性能。但是直接减少训练集规模或者降低特征维度，很明显会牺牲模型的精确度。

然而，LightGBM算法正是通过对模型训练时样本点的采样优化和选择分裂点时的特征维度的优化，在不牺牲精度的条件下，提高了训练速度。LightGBM算法是如何做到这一点的，下一节，我们会详细的讲解。

二. LightGBM原理

2.1 单边梯度采样算法（Grandient-based One-Side Sampling，GOSS）

LightGBM使用GOSS算法进行训练样本采样的优化。在AdaBoost算法中，采用了增加被错误分类的样本的权重来优化下一次迭代时对哪些样本进行重点训练。然而GBDT算法中没有样本的权重，但是LightGBM采用了基于每个样本的梯度进行训练样本的优化，具有较大梯度的数据对计算信息增益的贡献比较大。当一个样本点的梯度很小，说明该样本的训练误差很小，即该样本已经被充分训练。然而在计算过程中，仅仅保留梯度较大的样本（例如：预设置一个阈值，或者保留最高若干百分位的梯度样本），抛弃梯度较小样本，会改变样本的分布并且降低学习的精度。GOSS算法的提出很好的解决了这个问题。

GOSS算法的基本思想是首先对训练集数据根据梯度排序，预设一个比例，保留在所有样本中梯度高于的数据样本；梯度低于该比例的数据样本不会直接丢弃，而是设置一个采样比例，从梯度较小的样本中按比例抽取样本。为了弥补对样本分布造成的影响，GOSS算法在计算信息增益时，会对较小梯度的数据集乘以一个系数，用来放大。这样，在计算信息增益时，算法可以更加关注“未被充分训练”的样本数据。

具体的算法如下：

图片来源:LightGBM: A Highly Efficient Gradient Boosting Decision Tree

回归树采用方差增益作为选取分裂特征的指标，通过GOSS算法对样本数据集进行采样后，生成梯度较大的数据样本子集A，梯度较小数据样本子集B，根据子集计算方差增益的公式如下：

此处GOSS通过对较小的样本数据集估算增益，大大的减少了计算量。而且通过证明，GOSS算法不会过多的降低训练的精度。

2.2 Exclusive Feature Bundling 算法(EFB)

LightGBM算法不仅通过GOSS算法对训练样本进行采样优化，也进行了特征抽取，以进一步优化模型的训练速度。但是这里的特征抽取与特征提取还不一样，并不减少训练时数据特征向量的维度，而是将互斥特征绑定在一起，从而减少特征维度。该算法的主要思想是：假设通常高维度的数据往往也是稀疏的，而且在稀疏的特征空间中，大量的特征是互斥的，也就是，它们不会同时取到非0值。这样，可以安全的将互斥特征绑定在一起形成一个单一的特征包（称为Exclusive Feature Bundling）。这样，基于特征包构建特征直方图的复杂度由O(#data*#feature)变为O(#data*#bundle)，由于#bundle

怎么判断哪些特征应该被绑定在一起呢？

LightGBM将这个问题转化成为了图着色问题：给定一个无向图，所有的特征视为图G的顶点集合V，如果两个特征之间不是互斥，使用一个边将它们连接，E代表所有不是互斥特征之间边的集合。使用贪心算法解决该着色问题，结果会将互斥的特征放入相同的集合内（相同的颜色），每个集合即为一个特征包。实际上，有很多特征，虽然不是100%的互斥，但是基本上不会同时取到非0值。所以在LightGBM的算法中，会允许特征有一部分的冲突，这样可以生成更小的特征包集合，进一步减少计算时的特征规模，提高效率。假设变量代表一个特征包内最大的冲突率。那么选用一个相对较小的值，算法可以在效率和精确度之间有更好的平衡。

基于以上的思路，LightGBM设计了一个这样的算法（Greedy Bundling）：首先，使用训练集的特征构建一个加权图，图的边的权重值为两个特征间的整体冲突。然后，根据图节点（特征）的度对特征进行降序排序。最后，检查每一个排列好的特征，将其在较小的冲突率下（值来控制）分配到一个已存在的特征包内，或者新创建一个特征包（这里判断是否新创建一个特征包，是由算法中的参数K来决定的，K代表了特征包内最大的冲突数）。这样生成特征包的复杂度为。这种处理只在训练前进行一次。因此，该复杂度在feature规模不是很大的情况下，是可以接受的。但是当训练集的特征规模达到百万级或者以上时，就无法忍受了。因此，为了进一步提高算法的效率，LightGBM采用了更加高效的不用构建图的排序策略：按非零值计数排序，因为更多的非零的特征值会导致更高的冲突概率。具体的算法流程如下图所示：

图片来源:LightGBM: A Highly Efficient Gradient Boosting Decision Tree

EFB算法如何绑定特征？

上面解决了如何判断哪些特征要被绑定在一起，那么EFB算法如何绑定特征呢？如何既减少了特征维度，又保证原始的特征值可以在特征包中被识别出来呢？由于LightGBM是采用直方图算法减少对于寻找最佳分裂点的算法复杂度，直方图算法将特征值离散到若干个bin中。这里EFB算法为了保留特征，将bundle内不同的特征加上一个偏移常量，使不同特征的值分布到bundle的不同bin内。例如：特征A的取值范围为[0,10)，特征B的原始取值范围为[0，20)，对特征B的取值上加一个偏置常量10，将其取值范围变为[10,30)，这样就可以将特征A和B绑定在一起了。具体的算法流程如下图所示：

图片来源:LightGBM: A Highly Efficient Gradient Boosting Decision Tree

EFB算法可以将数据集中互斥的特征绑定在一起，形成低维的特征集合，能够有效的避免对0值特征的计算。实际上，在算法中，可以对每个特征建立一个记录非零值特征的表格。通过对表中数据的扫描，可以有效的降低创建直方图的时间复杂度（从到)。在LightGBM的算法中也确实使用了这种优化方式，当Bundle稀疏时，这个优化与EFB并不冲突。

2.3 LightGBM的其他优化

2.3.1 直方图算法（Histogram算法）

LightGBM采用了基于直方图的算法将连续的特征值离散化成了K个整数，构造宽度为K的直方图，遍历训练数据，统计每个离散值在直方图中的累积统计量。在选取特征的分裂点的时候，只需要遍历排序直方图的离散值。使用直方图算法降低了算法的计算代价，XGBoost采用的预排序需要遍历每一个特征值，计算分裂增益，而直方图算法只需要计算K次，提高了寻找分裂点的效率；降低了算法的内存消耗，不需要存储预排序结果，只需要保存特征离散化后的值。

但是特征值被离散化后，找到的并不是精确的分割点，会不会对学习的精度上造成影响呢？在实际的数据集上表明，离散化的分裂点对最终学习的精度影响并不大，甚至会更好一些。因为这里的决策树本身就是弱学习器，采用直方图离散化特征值反而会起到正则化的效果，提高算法的泛化能力。

2.3.2. 按叶子生长（leaf-wise)的算法

大多数的决策树学习算法的树生成方式都是采用按层生长（level-wise)的策略。如下图所示：

图片来源:https://lightgbm.readthedocs.io/en/latest/Features.html

不同的是，LightGBM采用了一种更为高效的按叶子生长（leaf-wise）的策略。该策略每次从当前决策树所有的叶子节点中，找到分裂增益最大的一个叶子节点，然后分裂，如此循环往复。这样的机制，减少了对增益较低的叶子节点的分裂计算，减少了很多没必要的开销。与leve-wise的策略相比，在分裂次数相同的情况下，leaf-wise可以降低误差，得到更好的精度。Leaf-wise算法的缺点是可能会生成较深的决策树。因此，LightGBM在Leaf-wise上增加了限制最大深度的参数，在保证算法高效的同时，防止过拟合。

图片来源:https://lightgbm.readthedocs.io/en/latest/Features.html

三. 总结

本文通过对LightGBM与其他梯度提升决策树算法在相同数据集上的运算结果对比，让我们了解到，LightGBM是一个性能高度优化的GBTD算法。LightGBM采用了GOSS算法对训练样本集的采样进行了优化，减少了计算梯度时的样本点；同时采用EFB算法，绑定互斥特征，降低选择分裂点时的特征维度。采用了直方图算法和按叶子节点生长的树生成策略。在GOSS和EFB算法的帮助下，使LightGBM在处理大训练样本和高维特征的场景时，在计算速度和内存消耗上明显的优于XGBoost。

四. 参考文档

1. http://papers.nips.cc/paper/6907-lightgbm-a-highly-efficient-gradi

2. https://lightgbm.readthedocs.io/en/latest/Features.html