前篇参考：学习笔记——集成学习（Ensemble Learning）
相关论文：LightGBM A Highly Efficient Gradient Boosting
Github：LightGBM
论文总结
LightGBM 是 GBDT 的一个实现
论文里主要提出了两个技术，用于解决计算分裂点的时候要遍历所有样本计算信息增益所带来的时间开销过大的问题：
- 单边梯度采样，Gradient-based One-Side Sampling（GOSS）
- 互斥特征绑定，Exclusive Feature Bundling（EFB）
结合使用 GOSS 和 EFB 的 GBDT 算法就是 LightGBM。
Histogram-based Algorithm
GBDT 中最耗时的部分是进行决策树学习的时候寻找最佳分裂点的过程。现在有两个很流行的最佳分裂点查找算法：
- pre-sorted algorithm（预排序算法）
这种算法根据预排序特征值枚举所有可能的分裂点。XGBoost 中的精确贪婪算法就是这种。这种算法简单且能保证获得最优解，但是时间和空间效率都很低 - histogram-based algorithm（直方图算法）
这种算法先将连续的特征值离散化，构建成一个直方图。这种算法时间和空间效率都更高。LightGBM 就是使用的这种算法
histogram-based algorithm 通过特征直方图寻找最佳分裂点。这个算法花费 \(O(\#data \times \#feature)\) 构建直方图，花费 \(O(\#bin \times \#feature)\) 寻找最佳分裂点。
histogram-based algorithm 不是 LightGBM 提出的，只使用而已。
Gradient-based One-Side Sampling（GOSS）
在训练过程里，每个样本具有不同的梯度，具有较大梯度（绝对值）的样本能贡献更大的信息增益。因此在对样本进行采样的时候，对梯度较大的样本（根据阈值或者样本占比）直接保留，只在梯度较小的样本里进行随机丢弃，这样可以使得每次丢弃的都是一些对信息增益没有帮助的样本。 
Exclusive Feature Bundling（EFB）
在实际应用中，可能会有很多特征，然后特征空间是稀疏的，这为设计无损降维方案提供了便利。稀疏的特征空间里往往有很多特征是互斥的（它们不同时取到非零值），而互斥特征可以绑定为一个单一特征，这就叫互斥特征绑定。进行这种操作后，可以将生成直方图的复杂度由 \(O(\#data \times \#feature)\) 降为 \(O(\#data \times \#bundle)\) 其中 \(\#bundle << \# feature\)。这可以在不降低精度的前提下大大提高 GBDT 的效率。
这里有两个问题：
- 怎么决定将哪些特征绑定到一起
- 怎么实现绑定
将独立特征绑定到一起是一个 NP-hard 问题，这里是转换为图着色问题来解决的。将特征视为图的顶点，将不互斥的特征之间添上边，然后使用贪婪算法解决图着色问题，也就解决了第一个问题。具体算法如下： 
下面这个融合互斥特征算法用于解决第二个问题。因为 histogram-based 算法是用离散的 bins 来存储特征值的，所以实现绑定的时候将互斥的特征绑定到不同的 bins 里就可以了。这个可以通过给特征原始值添加一个偏移量来实现。具体算法如下： 
Leaf-wise
LightGBM 还使用了 leaf-wise 生长策略（XGBoost 是 lever-wise），这种策略每次从当前所有叶子中，找到分裂增益最大的一个叶子，然后分裂，如此循环，因此不会像 layer-wise 一样为了达到深度而去分裂增益不大的节点，因此在分裂次数相同的情况下，leaf-wise 的精度一般比 lever-wise 要高。在设置参数的时候不进行最大深度限制的话有可能会生成较深的决策树，造成过拟合。
Lever-wise 
Leaf-wise 
这一项论文只在第五节提了一下。