这次终于彻底理解了 LightGBM 原理及代码( 三 ) _LightGBM

所以，GOSS首先将要进行分裂的特征的所有取值按照绝对值大小降序排序（XGBoost一样也进行了排序，但是LightGBM不用保存排序后的结果），选取绝对值最大的个数据。然后在剩下的较小梯度数据中随机选择个数据。
接着将这个数据乘以一个常数，这样算法就会更关注训练不足的样本，而不会过多改变原数据集的分布。最后使用这个数据来计算信息增益。下图是GOSS的具体算法。

文章插图
图：单边梯度采样算法
2.4 互斥特征捆绑算法
高维度的数据往往是稀疏的，这种稀疏性启发我们设计一种无损的方法来减少特征的维度。通常被捆绑的特征都是互斥的（即特征不会同时为非零值，像one-hot），这样两个特征捆绑起来才不会丢失信息。
如果两个特征并不是完全互斥（部分情况下两个特征都是非零值），可以用一个指标对特征不互斥程度进行衡量，称之为冲突比率，当这个值较小时，我们可以选择把不完全互斥的两个特征捆绑，而不影响最后的精度。
互斥特征捆绑算法（Exclusive Feature Bundling, EFB）指出如果将一些特征进行融合绑定，则可以降低特征数量。这样在构建直方图时的时间复杂度从变为，这里指特征融合绑定后特征包的个数，且远小于。
针对这种想法，我们会遇到两个问题：

怎么判定哪些特征应该绑在一起（build bundled）？
怎么把特征绑为一个（merge feature）？

（1）解决哪些特征应该绑在一起将相互独立的特征进行绑定是一个 NP-Hard 问题，LightGBM的EFB算法将这个问题转化为图着色的问题来求解，将所有的特征视为图的各个顶点，将不是相互独立的特征用一条边连接起来，边的权重就是两个相连接的特征的总冲突值，这样需要绑定的特征就是在图着色问题中要涂上同一种颜色的那些点（特征）。此外，我们注意到通常有很多特征，尽管不是％相互排斥，但也很少同时取非零值。
如果我们的算法可以允许一小部分的冲突，我们可以得到更少的特征包，进一步提高计算效率。经过简单的计算，随机污染小部分特征值将影响精度最多，是每个绑定中的最大冲突比率，当其相对较小时，能够完成精度和效率之间的平衡。具体步骤可以总结如下：

构造一个加权无向图，顶点是特征，边有权重，其权重与两个特征间冲突相关；
根据节点的度进行降序排序，度越大，与其它特征的冲突越大；
遍历每个特征，将它分配给现有特征包，或者新建一个特征包，使得总体冲突最小。

算法允许两两特征并不完全互斥来增加特征捆绑的数量，通过设置最大冲突比率来平衡算法的精度和效率。EFB 算法的伪代码如下所示：

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

（2）解决怎么把特征绑为一捆特征合并算法，其关键在于原始特征能从合并的特征中分离出来。绑定几个特征在同一个bundle里需要保证绑定前的原始特征的值可以在bundle中识别，考虑到histogram-based算法将连续的值保存为离散的bins，我们可以使得不同特征的值分到bundle中的不同bin（箱子）中，这可以通过在特征值中加一个偏置常量来解决。
比如，我们在bundle中绑定了两个特征A和B，A特征的原始取值为区间，B特征的原始取值为区间，我们可以在B特征的取值上加一个偏置常量，将其取值范围变为，绑定后的特征取值范围为，这样就可以放心的融合特征A和B了。具体的特征合并算法如下所示：

文章插图
图：特征合并算法
3. LightGBM的工程优化
我们将论文《Lightgbm: A highly efficient gradient boosting decision tree》中没有提到的优化方案，而在其相关论文《A communication-efficient parallel algorithm for decision tree》中提到的优化方案，放到本节作为LightGBM的工程优化来向大家介绍。