写这篇博客的原因是，网上很多关于Lightgbm的讲解都是从Lightgbm的官方文档来的，官方文档只会告诉你怎么用，很多细节都没讲。所以自己翻过来Lightgbm的源论文：LightGBM: A Highly Efficient Gradient Boosting Decision Tree仔细看了几遍，现在整理一下源论文，加深自己对Lightgbm技术细节的认识和思考。

首先感谢网友立刻有的博客，省去了我很多翻译的工作。我更改了他博客的部分不当（翻译或者公式）的地方，又加入了自己的一些思考。

Abstract

Gradient Boosting Decision Tree (GBDT)非常流行却鲜有实现，只有像XGBoost和pGBRT实现。当特征维度较高和数据量巨大的时候，仍然存在效率和可扩展性的问题。一个主要原因就是对于每一个特征的每一个分裂点，都需要遍历全部数据计算信息增益，这一过程非常耗时。针对这一问题，本文提出两种新方法：Gradient-based One-Side Sampling (GOSS) 和Exclusive Feature Bundling (EFB)（基于梯度的one-side采样和互斥的特征捆绑）。在GOSS中，我们排除了重要的比例-具有小梯度的实例，只用剩下的来估计信息增益，我们证明，这些梯度大的实例在计算信息增益中扮演重要角色，GOSS可以用更小的数据量对信息增益进行相当准确的估计。对于EFB，我们捆绑互斥的特征（例如，特征间很少同时非零的特征），来降低特征的个数。我们完美地证明了捆绑互斥特征是NP难的，但贪心算法能够实现相当好的逼近率，因此我们能够在不损害分割点准确率许多的情况下，有效减少特征的数量。（牺牲一点分割准确率降低特征数量），这一算法命名为LightGBM。在多个公共数据集实验证明，LightGBM加速了传统GBDT训练过程20倍以上，同时达到了几乎相同的精度。

 

1. Introduction

GBDT因为其本身的有效性、准确性、可解释性，成为了广泛使用的机器学习算法。GBDT在许多机器学习任务上均取得了最好的效果，例如多分类，点击预测，排序。但最近几年随着大数据的爆发（特征量和数据量），GBDT面临平衡准确率和效率的调整。

GBDT缺点：对于每一个特征的每一个分裂点，都需要遍历全部数据来计算信息增益。因此，其计算复杂度将受到特征数量和数据量双重影响，造成处理大数据时十分耗时。

解决这个问题的直接方法就是减少特征量和数据量而且不影响精确度，有部分工作根据数据权重采样来加速boosting的过程，但由于gbdt没有样本权重而不能应用。而本文提出两种新方法实现此目标。

Gradient-based One-Side Sampling (GOSS)：GBDT虽然没有数据权重，但每个数据实例有不同的梯度，根据计算信息增益的定义，梯度大的实例对信息增益有更大的影响，因此在下采样时，我们应该尽量保留梯度大的样本（预先设定阈值，或者最高百分位间），随机去掉梯度小的样本。我们证明此措施在相同的采样率下比随机采样获得更准确的结果，尤其是在信息增益范围较大时。

Exclusive Feature Bundling (EFB)：通常在真实应用中，虽然特征量比较多，但是由于特征空间十分稀疏，是否可以设计一种无损的方法来减少有效特征呢？特别在稀疏特征空间上，许多特征几乎是互斥的（例如许多特征不会同时为非零值，像one-hot），我们可以捆绑互斥的特征。最后，我们将捆绑问题归约到图着色问题，通过贪心算法求得近似解。

 

2. Preliminaries

2.1 GBDT and Its Complexity Analysis

GBDT是一种集成模型的决策树，顺序训练决策树。每次迭代中，GBDT通过拟合负梯度（残差）来学到决策树。

学习决策树是GBDT主要的时间花销，而学习决策树中找到最优切分点最消耗时间。广泛采用的预排序算法来找到最优切分点，这种方法会列举预排序中所有可能的切分点。这种算法虽然能够找到最优的切分点，但对于训练速度和内存消耗上都效率低。另一种流行算法是直方图算法（histogram-based algorithm）。直方图算法并不通过特征排序找到最优的切分点，而是将连续的特征值抽象成离散的分箱，并使用这些分箱在训练过程中构建特征直方图，这种算法更加训练速度和内存消耗上都更加高效，lightGBM使用此种算法。

histogram-based算法通过直方图寻找最优切分点，其建直方图消耗O(#data * #feature)，寻找最优切分点消耗O(#bin * # feature)，而#bin的数量远小于#data，所以建直方图为主要时间消耗。如果能够减少数据量或特征量，那么还能够够加速GBDT的训练。（寻找最优切分点已经进行了优化，那么我们现在应该对建直方图的时间进行优化）

2.2 Related Work

GBDT有许多实现，如XGBoost，PGBRT，Scikit-learn，gbm in R。Scikit-learn和gbm in R实现都用了预排序，pGBRT使用了直方图算法，XGBoost支持预排序和直方图算法，由于XGBoost胜过其他算法，我们用它作为baseline。

为了减小训练数据集，通常做法是下采样。例如过滤掉权重小于阈值的数据。SGB每次迭代中用随机子集训练弱学习器。或者采样率基于训练过程动态调整。基于AdaBoost的SGB不能直接应用于GBDT，因为GBDT中没有原始的权重。虽然SGB也能间接应用于GBDT，但往往会影响精度。

同样，可以考虑过滤掉弱特征（什么是弱特征）来减少特征量。通常用主成分分析或者投影法。当然，这些方法依赖于一个假设-特征有高冗余性，但实际中往往不是。（设计特征来自于其独特的贡献，移除任何一维度都可以某种程度上影响精度）。

实际中大规模的数据集通常都是非常稀疏的，使用预排序算法的GBDT能够通过无视为0的特征来降低训练时间消耗。然而直方图算法没有优化稀疏的方案。因为直方图算法无论特征值是否为0，都需要为每个数据检索特征区间值。如果基于直方图的GBDT能够有效解决稀疏特征中的0值，那么这样将会有很好的性能。

下图为直方图算法的流程：

3. Gradient-based One-Side Sampling

GOSS是一种在减少数据量和保证精度上平衡的算法。

3.1 Algorithm Description

AdaBoost中，样本权重是数据实例重要性的指标。然而在GBDT中没有原始样本权重，不能应用权重采样。幸运的事，我们观察到GBDT中每个数据都有不同的梯度值，对采样十分有用，即实例的梯度小，实例训练误差也就较小，已经被学习得很好了，直接想法就是丢掉这部分梯度小的数据。然而这样做会改变数据的分布，将会影响训练的模型的精确度，为了避免此问题，我们提出了GOSS。

GOSS保留所有的梯度较大的实例，在梯度小的实例上使用随机采样。为了抵消对数据分布的影响，计算信息增益的时候，GOSS对小梯度的数据引入常量乘数。GOSS首先根据数据的梯度绝对值排序，选取top a个实例。然后在剩余的数据中随机采样b个实例。接着计算信息增益时为采样出的小梯度数据乘以(1-a)/b（即，小梯度样本总数/随机采样出的小梯度样本数量），这样算法就会更关注训练不足的实例，而不会过多改变原数据集的分布。

GOSS的算法流程如下：

3.2 Theoretical Analysis

GBDT使用决策树，来学习获得一个将输入空间映射到梯度空间的函数。假设训练集有n个实例 ，特征维度为s。每次迭代时，模型数据变量的损失函数的负梯度方向表示为，决策树通过最优切分点（最大信息增益点）将数据分到各个节点。GBDT通过分割后的方差衡量信息增益

定义3.1：O表示某个固定叶子节点的训练集，分割特征j的分割点d定义为：

                                                   

其中，(某个固定叶子节点的训练集样本的个数)，(在第j个特征上值小于等于d的样本个数)，(在第j个特征上值大于d的样本个数)。

遍历每个特征的每个分裂点，找到 并计算最大的信息增益，然后，将数据根据特征的分裂点​将数据分到左右子节点。

在GOSS中，

1. 首先根据数据的梯度进行降序排序。

2. 保留top %a个数据实例，作为数据子集A。

3. 对于剩下的数据的实例集合，随机采样获得大小为的数据子集B。

4. 最后我们在集合上，通过以下方程估计信息增益:

                 

此处GOSS通过较小的数据集估计信息增益 ，将大大地减小计算量。更重要的是，我们接下来理论表明GOSS不会丢失许多训练精度，且胜过随机采样，理论的证明在附加材料(参考文献【2】)。

Theorem 3.2：我们定义GOSS近似误差为，，，概率至少是，有：

                                         

其中。

根据理论3.2，我们得出以下结论：

GOSS的渐近近似比率 。如果数据分割不是极不平衡（也就是 且），那么定理3.2中近似误差将由第二项主导，且在第二项中，当n趋于无穷（数据量很大）时将趋于0，即数据量越大，误差越小，精度越高。

随机采样是GOSS在a=0的一种情况。多数情况下，GOSS性能优于随机采样，即以下情况：(C代表误差，即随机抽比例的误差大于先抽top a%比例再抽比例的误差)，等价于，其中。

（其实这里，，代入，就可以得到等价的不等式）

下面分析GOSS的泛化性。考虑GOSS泛化误差，这是GOSS抽样的的实例计算出的方差增益与实际样本方差增益之间的差距。变换为，，因此，在GOSS准确的情况下，GOSS泛化误差近似于全量的真实数据。另一方面，采样将增加基学习器的多样性（因为每次采样获得的数据可能会不同），这将提高泛化性。

4 Exclusive Feature Bundling

这一章介绍如何有效减少特征的数量。

高维的数据通常是稀疏的，这种稀疏性启发我们可以设计一种无损地方法来减少特征的维度。特别地，在稀疏特征空间中，许多特征是互斥的，即它们从不同时为非零值。我们可以绑定互斥的特征为单一特征，通过仔细设计特征扫描算法，我们从特征捆绑中构建了与单个特征相同的特征直方图。这种方式的构建直方图时间复杂度从O(#data * #feature)降到O(#data * #bundle)，由于#bundle << # feature，我们能够极大地加速GBDT的训练过程而且不损失精度。(构造直方图的时候，遍历一个“大特征”可以得到一组exclusive feature的直方图。这样只需要遍历这些“大特征”就可以获取到所有特征的直方图，降低了需要遍历的特征量。)

有两个问题：

1. 怎么判定那些特征应该绑在一起（build bundled）？

2. 怎么把特征绑为一个（merge feature）？

4.1 bundle（什么样的特征被绑定）？

理论 4.1：将特征分割为较小量的互斥特征群是NP难的。

证明：将图着色问题归约为此问题，而图着色是NP难的，所以此问题就是NP难的。

给定图着色实例G=(V, E)。以G的关联矩阵的每一行为特征，得到我们问题的一个实例有|V|个特征。 很容易看到，在我们的问题中，一个独特的特征捆绑包与一组具有相同颜色的顶点相对应，反之亦然。

对于第1个问题，理论4.1说明在多项式时间中求解这个NP难问题是不可行的。为了寻找好的近似算法，我们将最优捆绑问题归结为图着色问题，如果两个特征之间不是相互排斥，那么我们用一个边将他们连接，然后用合理的贪婪算法（具有恒定的近似比）用于图着色来做特征捆绑。 此外，我们注意到通常有很多特征，尽管不是100％相互排斥的，也很少同时取非零值。 如果我们的算法可以允许一小部分的冲突，我们可以得到更少的特征包，进一步提高计算效率。经过简单的计算，随机污染小部分特征值将影响精度最多(参考文献【2】)， 是每个绑定中的最大冲突比率，当其相对较小时，能够完成精度和效率之间的平衡。

基于上面的讨论，我们设计了算法3，伪代码见下图，具体算法：

1. 建立一个图，每个点代表特征，每个边有权重，其权重和特征之间总体冲突相关。
2. 按照降序排列图中点的度来排序特征。
3. 检查排序之后的每个特征，对它进行特征绑定或者建立新的绑定使得操作之后的总体冲突最小（由控制）。

算法3的时间复杂度是，训练之前只处理一次，其时间复杂度在特征不是特别多的情况下是可以接受的，但难以应对百万维的特征。为了继续提高效率，我们提出了一个更加高效的不用构建图的排序策略：将特征按照非零值个数排序，这和使用图节点的度排序相似，因为更多的非零值通常会导致冲突。新算法在算法3基础上只是改变了排序策略。

4.2 merging features(特征合并)

对于第2个问题，如何合并同一个bundle的特征来降低训练时间复杂度。关键在于原始特征值可以从bundle中区分出来。鉴于直方图算法存储离散值而不是连续特征值，我们通过将互斥特征放在不同的箱中来构建bundle。这可以通过将偏移量添加到特征原始值中实现，例如，假设bundle中有两个特征，原始特征A取值[0, 10]，B取值[0, 20]。我们添加偏移量10到B中，因此B取值[10, 30]。通过这种做法，就可以安全地将A、B特征合并，使用一个取值[0, 30]的特征取代A和B。算法见算法4，算法流程如下：

EFB算法能够将许多互斥的特征变为低维稠密的特征，就能够有效的避免不必要0值特征的计算。实际，对每一个特征，建立一个记录数据中的非零值的表，通过用这个表，来忽略零值特征，达到优化基础的直方图算法的目的。通过扫描表中的数据，建直方图的时间复杂度将从O(#data)降到O(#non_zero_data)。当然，这种方法在构建树过程中需要而额外的内存和计算开销来维持这种表。我们在lightGBM中将此优化作为基本函数，因为当bundles是稀疏的时候，这个优化与EFB不冲突（可以用于EFB）

5 Experiments

实验部分，比较简单。主要用了五个公开数据集，且这些数据集都比较大，而且包含了稀疏和稠密的特征，涵盖了很多真实的业务，因此它们能够完全地测试lightGBM的性能。

经过与XGBoost，lightgbm without GOSS and EFB和SGB的对比，证明了LightGBM在计算速度和内存消耗上明显优于XGBoost和SGB，且不损失准确率。

这部分详细内容可以看参考文献1和2.

6 Conclusion

本文提出了新颖的GBDT算法–LightGBM，它包含了2个新颖的技术：Gradient-based One-Side Sampling (GOSS) 和Exclusive Feature Bundling (EFB)（基于梯度的one-side采样和互斥的特征捆绑）来处理大数据量和高维特征的场景。我们在理论分析和实验研究表明，GOSS和EFB使得LightGBM在计算速度和内存消耗上明显优于XGBoost和SGB。

未来，我们将研究优化如何在GOSS中选择a，b。继续提高EFB在高维特征上的性能，无论其是否是稀疏的。

 

参考文献

【1】https://papers.nips.cc/paper/6907-lightgbm-a-highly-efficient-gradient-boosting-decision-tree.pdf

【2】https://papers.nips.cc/paper/6907-lightgbm-a-highly-efficient-gradient-boosting-decision-tree

【3】https://blog.csdn.net/shine19930820/article/details/79123216