LightGBM
摘要
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数据实例没有直接的权重，我们注意到带有不同梯度的数据样本在信息增益的计算中发挥着不同的作用。根据信息增益的定义，拥有更大梯度的样例将对信息增益贡献更大。因此在下采样时，为了维持信息增益精度，我们应该尽量保留具有较大梯度的样本（大于预设置的阈值，或者在top百分位中），同时随机去除梯度小的样本。我们证明，在相同的采样率下，该采样机制将比均匀随机采样有更高的精度。尤其当信息增益有较大的范围时。
Exclusive Feature Bundling (EFB)：通常在真实应用中，尽管特征数量非常多，但对应的特征空间是格外稀疏的。这为我们设计一种近乎无损的方法来减少有效特征的数量提供了可能性。尤其在稀疏特征空间中，许多特征是互斥的：他们几乎不会同时为非零。我们可以捆绑这些互斥特征。为此，我们设计了一个有效的算法，将最优的捆绑问题简化为图的着色问题(将特征作为顶点，在不是互斥的两个特征间添加边)，使用贪婪算法求解。
论文内容组织：第二章回顾GBDT算法和相关工作；第三章介绍GOSS和EFB；第四章展示实验结果；第五章总结
2. Preliminaries
2.1 GBDT及其复杂度分析
GBDT是决策树的一种集成模型。在每轮迭代中，GBDT学习决策树来拟合损失函数的负梯度（近似残差）。
GBDT的主要时间花费在学习决策树，而学习决策树大部分时间消耗在于寻找最优划分点。广泛采用的寻找划分点方法使用预排序算法，在预排序的特征值上列举所有可能的划分点。该算法比较简单可以找到最有划分点，但是其训练时间和内存消耗是较高的。另一种流行的算法是基于直方图的算法。该算法不通过预排序特征值来寻找划分点，它将连续特征值分桶到不同离散bin中，使用这些bin在训练过程中来构造特征直方图。由于基于直方图的算法在时间和内存上的效率更高，我们将采用这种方法。
histogram-based算法通过特征直方图寻找最优切分点，其建直方图消耗
image.png
决策树模型在最大影响的特征上划分结点（最大信息增益）。对于GBDT，信息增益通常用划分后的方差来衡量。
image.png
在我们提出的GOSS方法中，我们首先根据样例梯度的绝对值进行降序排列；其次，我们保留top
image.png
因此，在GOSS中，我们对一个较小的样例子集评估
image.png
4.2 merge feature
对于第二个问题，我们需要好的方式来合并在同一个Bundle中的特征，同时降低对应的训练复杂度。关键是确保原始特征值可以在特征bundle中区分。由于基于直方图的算法存储离散值而不是连续特征值，我们通过将互斥特征放在不同的箱中来构建bundle。这可以通过将偏移量添加到特征原始值中实现。例如，假设我们在bundle中有两个特征，特征A取值[0,10)，特征B取值[0,20)。我们添加偏移量10 到特征B中，使特征取值为[10,30)。之后我们可以合并特征A、B，使用取值为[0,30)的新特征代替A和B。
EFB可以捆绑许多互斥特征，将其转化为稠密特征，来有效的避免对0特征值不必要的计算。事实上，我们可以对每一个特征构建对应表记录非零值来忽略0特征值，这样也可以优化基础的直方图算法。通过在表中扫描数据，对一个特征建立直方图的复杂度从
image.png
5. Experiments
主要是LightGBM在各大数据集上的表现，及GOSS和EFB的有效性
6.优缺点
6.1 内存更小
XGBoost 使用预排序后需要记录特征值及其对应样本的统计值的索引，而 LightGBM 使用了直方图算法将特征值转变为 bin 值，且不需要记录特征到样本的索引，将空间复杂度从 O(2*#data) 降低为 O(#bin) ，极大的减少了内存消耗；
LightGBM 采用了直方图算法将存储特征值转变为存储 bin 值，降低了内存消耗；
LightGBM 在训练过程中采用互斥特征捆绑算法减少了特征数量，降低了内存消耗。
6.2 速度更快
LightGBM 采用了直方图算法将遍历样本转变为遍历直方图，极大的降低了时间复杂度；
LightGBM 在训练过程中采用单边梯度算法过滤掉梯度小的样本，减少了大量的计算；
LightGBM 采用了基于 Leaf-wise 算法的增长策略构建树，减少了很多不必要的计算量；
LightGBM 采用优化后的特征并行、数据并行方法加速计算，当数据量非常大的时候还可以采用投票并行的策略；
LightGBM 对缓存也进行了优化，增加了 Cache hit 的命中率。
直方图算法
这里额外补充下直方图算法， 可以参照下面链接的讲解，很详细：
Lightgbm 直方图优化算法深入理解
网友评论