比起XGBoost的那篇论文的层层递进，LightGBM讲得更为单刀直入，要是没有GBDT、XGBoost的理论作为基础，还真的挺难看懂的。在我的理解中，这篇论文的主要贡献还是在于对训练数据的处理上，新的方法使得算法能够更快、更准。

LightGBM作为GBDT的一种高效实现，直接针对已有方法“对于每一个特征的每一个分裂点，都需要遍历全部数据计算信息增益，这一过程非常耗时”的缺点进行改进，主要叙述了两种新方法：Gradient-based one-side sampling(GOSS,基于梯度的one-side采样)和Exclusive feature bundling(EFB,互斥的特征捆绑)

对于GOSS, 我们排除了一部分梯度值小的数据实例，仅仅使用剩下来评估信息增益。这样做可行性的原因，拥有梯度值大的数据集在信息增益计算时扮演更重要的角色。在小数据集上GOSS可以获得更加准确的信息增益的评估结果。

对于EFB，捆绑互斥的特征，来减少特征的数量。但是我们发现最优的互斥特征是一个NP难问题，贪心算法可以取得近似的分数（在不损害分割点方向准确率的情况下，有效减少特征值）。

前言

在GBDT的传统实现方案中，主要的时间花销在于建立决策树过程中找到最佳分割点。被广泛采用的方法是通过预排序再遍历找到分割点，算法简单精确，但是效率低下；其次便是直方图算法（xgb的近似算法），通过将连续特征映射到离散的桶中，统计这些值找到对应的分割点。

在这一过程中，如果可以减少数据量或者减少需要计算的特征，算法便可以得到加速。

为了减少数据量，传统的方法是下采样，比如过滤到权重小于阈值的数据（这里提到的随机梯度提升SGB, Adaboost)。GBDT没有初始权重，难以采用这种方法。

为了减少特征量，需要对特征进行过滤，常用的方法比如PCA和投影法。但这种方法的前提假设是特征中有冗余信息，在实际应用过程中往往不成立。

再者就是稀疏数据，现实应用中的大规模数据通常是稀疏的，使用预排序的GBDT算法可以通过忽略0值来降低训练开销，而使用直方图法的GBDT没有针对稀疏数据的优化方案，因为histogram-based algorithm无论特征值是否为0，都需要检索特征的bin值。如果基于直方图的算法能解决这一问题，将会更受欢迎。

为了解决上述问题，变提出了GOSS和EFB。

一、GOSS，基于梯度的One-side采样

GOSS是一种在减少数据量与保持算法进度上平衡的算法

算法描述

Adaboost中，样本权重是样本的重要属性，而在GBDT中却没有这一属性。但是GBDT中每个数据都有不同的梯度值，对采样十分有用，即实例的梯度小，实例训练误差也就较小，已经被学习得很好了，而梯度大的样本在计算信息增益的过程中起着更大的作用。直接想法就是丢掉这部分梯度小的数据，但是这样会改变数据分布，从而损害训练模型的精度，于是提出了GOSS:

1. 对所有样本按照梯度大小排序，选择top a * 100% 的样本
2. 在剩余样本中随机采样 b * 100% 的样本
3. 对于随机抽样的样本，计算信息增益时 * （1 - a）/ b

这样做既可以减少训练数据，还可以尽可能符合数据的原始分布。

理论分析暂且略过，markdown对公式和图片的支持还真是挺麻烦的。

二、EFB 互斥的特征捆绑

GOSS的作用是减少数据量，而EFB的主要作用在于有效减少特征的数量。

高维的数据往往是稀疏的，稀疏的数据提供给了我们减少特征数量而较小误差损失的可能。特别是在稀疏数据中，许多特征是互斥的，例如他们从不会同时为非零值。我们绑定互斥的特征为单一特征（排他特征绑定）。通过仔细设计特征扫描算法，我们从特征绑定中建立相同的特征直方图作为单一特征。通过这种方式，构建直方图的复杂度从O（data feature ） 到O（data bundle），bundle << feature。然后我们在无损精度的情况下加速GBDT的训练。

接下来的问题是：

1. 如何判断应该把哪些特征进行绑定）？
2. 怎么把特征绑定为一个（如何建立Bundle）？

如何选定互斥特征

The problem of partitioning features into a smallest number of exclusive bundles is
NP-hard.

具体算法为：

1. 建立权重图，边的权重和特征之前的冲突程度有关系。
2. 将特征按照图中的度数进行降序排序。
3. 检查排序后的每个特征，要么将其绑定到一个已经存在的冲突较小的Bundle中，要么新建一个Bundle.

这一算法的时间复杂度为（O(feature^2)）,在训练之前便可一次完成。当特征不是很多时，这一复杂度是可接受的。

为了进一步提高效率，文章又提出了一种更高效的无图算法，即：

1. 将特征按照非零值个数进行排序，因为非0值越多越容易导致冲突

Merging features 特征合并

特征合并的关键在于要保证原始特征的值可以从绑定后的特征中识别出来，因为基于直方图的算法需要存储离散的值，而不希望合并后的特征互相重叠。

解决这一问题的方法就是将偏移量添加到特征原始值中实现，例如，假设bundle中有两个特征，原始特征A取值[0, 10]，B取值[0, 20]。我们添加偏移量10到B中，因此B取值[10, 30]。通过这种做法，就可以安全地将A、B特征合并，使用一个取值[0, 30]的特征取代AB

EFB算法能够将许多互斥的特征变为低维稠密的特征，就能够有效的避免不必要0值特征的计算。

文中还提到可以对原始的直方图算法进行优化，通过用一张表来记录特征的非零值来忽略0值的计算，这样直方图算法的复杂度就可以从O(#data)降低到O(#noe_zero_data)。但是这一方法还是需要额外的存储空间和计算代价。但这一方法和EFB并不冲突，在LightGBM中也实现了这一方法。

其他

以上就是LightGBM这篇文章的主要内容，但是LightGBM还有许多其他的特征，总结如下：

1. level-wise的生长方式。这应该是问的比较多的知识点了，xgboost采用的是level-wise的分裂策略，而lightGBM采用了leaf-wise的策略，区别是xgboost对每一层所有节点做无差别分裂，可能有些节点的增益非常小，对结果影响不大，但是xgboost也进行了分裂，带来了务必要的开销。 leaft-wise的做法是在当前所有叶子节点中选择分裂收益最大的节点进行分裂，如此递归进行，很明显leaf-wise这种做法容易过拟合，因为容易陷入比较高的深度中，因此需要对最大深度做限制，从而避免过拟合。
2. 直方图做差加速。一个子节点的直方图可以通过父节点的直方图减去兄弟节点的直方图得到，从而加速计算。
3. XGBoost的近似直方图算法与LightGBM直方图算法的区别：xgboost在每一层都动态构建直方图， 因为xgboost的直方图算法不是针对某个特定的feature，而是所有feature共享一个直方图(每个样本的权重是二阶导),所以每一层都要重新构建直方图，而lightgbm中对每个特征都有一个直方图，所以构建一次直方图就够了。
4. lightGBM支持直接输入categorical的feature。在对离散特征分裂时，每个取值都当作一个桶，分裂时的增益算的是”是否属于某个category“的gain。类似于one-hot编码。
5. 并行优化。一是特征层面的并行，对特征进行分割，在汇总得到全局最优分割点；二是数据层面的并行，对数据进行分割，汇总合并全局的直方图。

参考：

1. lightgbm,xgboost,gbdt的区别与联系
2. LightGBM原理