我们在 Boosting Trees 中介绍了 Gradient Boosting Decision Tree (GBDT) 的原理。Light GBM 是 GBDT 的一个衍生方法。相比其他的衍生方法（如 XGBoost），它最明显的优势就是训练速度快，这也是它被命名为 "light" 的原因。它在保持训练精度的前提下，将传统 GBDT 的训练速度提高了 20 倍。

1. 论文要点

LightGBM 的目的是缩短训练时间，而训练时间主要取决于样本数量和特征维度。

它使用了三种重要的优化：

1. （非原创）在训练树的时候，使用直方图算法来寻找最佳划分节点
2. （原创）使用基于梯度的单边采样(GOSS)降低样本数量
3. （原创）使用互斥特征捆绑 (EFB)降低特征维度

1.1 直方图算法

在 GBDT 的训练中，每次迭代，我们都会拟合负梯度来生成一个决策树，这也是 GBDT 训练中最耗时的部分。其中，计算量最大的部分就是寻找最佳划分节点。

最简单直接的方法就是预排序法。即，先将所有样本以某个特征为比较对象排序，再依次遍历寻找最优划分点。这种虽然能找到最优点， 但是缺点很明显：

1. 效率低下，时间复杂度是
2. 对噪声敏感

LightGBM 选择了直方图法。即，先将数据划分到多个 bin 中，用 bin 的值覆盖原始值进行训练。它的优势是：

1. 将时间复杂度降低到了 。由于 bin 的数量肯定远小于样本的数量，因此优化很明显
2. 不需要对样本数据进行排序
3. 增强了对数据噪声的鲁棒性

当然，它也有缺点，但是都可以接受：

1. 找到的划分点不一定是最优的
2. 由于相似的数据被划分到了一个 bin 中，忽略了一些细节特征
3. bin 的数量选择过少可能导致欠拟合

直方图算法并不是 LightGBM 的原创：

Scikit-learn和gbm in R演变算法使用了pre-sorted algorithm算法，pGBRT算法是使用了histogram-based algorithm，而XGBoost两者都支持

直方图算法

1.2 基于梯度的单边采样

基于梯度的单边采样(Gradient-based One Side Sample, GOSS)是 LightGBM 论文中提出的一大创新点，用于减少训练样本，从而提高效率。

在 AdaBoost 中（见我之前的文章 ESL 10.1 Boosting Methods），每个样本都被赋予了权重，因此可以简单地丢弃掉权重小的样本。然而，GBDT 中的样本并没有权重这一概念。因此，文中提出了利用梯度来筛选样本的思路。如果一个样本的梯度较小，说明它已经是充分训练过的了，可以丢弃。

但是，这个方法的问题在于丢弃样本会改变数据的分布，影响模型精度。为了避免这个问题，LightGBM 保留所有梯度较大的样本，同时，对梯度较小的样本进行随机采样，因此称为“单边采样”。

GOSS 算法

其中输入：

• 是“较大梯度样本”的比例，top 的样本都被全部选取
• 是“较小梯度样本”采样后的比例（相对于所有样本）

因此必然有 ，且 。

核心思想是：

1. 将样本梯度（残差）由高到低排序
2. 选取前 的样本为集合 A
3. 从后 的样本中选取 的样本为集合 B
4. 将被选取的样本（A + B）用于训练
5. 在更新模型时，需要对集合 B 进行补偿，乘以

1.3 互斥特征捆绑

实际应用中的特征之间有时是存在互斥关系的，即，他们不会同时有值。我们可以将这一类特征“捆绑”成一个特征。这样我们可以把时间复杂度由 降低到 。为了能捆绑更多的特征，LightGBM 还引入了一个”冲突率“，即两个特征同时不为 0 的比例。我们通过调节 来使部分几乎互斥的特征也可以捆绑成一个。

那么我们就需要处理两个问题：

1. 如何找到互斥特征
2. 如何捆绑

1.3.1 选取互斥特征

寻找互斥特征的问题本质上是一个图着色问题。假设把每个特征看作图的一个顶点，若两个特征互斥，那他们之间没有路径。这样就可以构造一个无向图。图着色问题就是使图的相邻顶点颜色不同，即非互斥的特征不在同一个 bundle 里。

具体来说，算法为：

1. 构造一个有权重的无向图，以特征为顶点，每条边的权重是特征之间的冲突率 。
2. 将特征按他们的度（degree，即边的数量）降序排列
3. 检查每个特征，若 小于阈值，则将其加入现有的 bundle，否则创建一个新的 bundle。

时间复杂度为 ，而且只用运行一次，完全可以接受。

图着色贪婪算法

1.3.2 捆绑互斥特征

我们在 1.3.1 中已经将特征组合成了多个 bundle，现在需要考虑如何将同一个 bundle 内的特征在不丢失信息的情况下转为一个特征。

一个简单直接的方法就是附加一个偏移量。例如，我们已知 A 特征取值范围是 [0, 10)，B 特征取值范围是 [0, 20)。那么我们可以构建一个合并的特征，取值范围是 [0, 30)，对于所有的 B 特征附加一个偏移量 10。这样就将 B 特征从 [0,20) 映射到了 [10, 30)。这个合并的特征将替代 A 和 B 两个特征进行训练。

特征捆绑算法

假设互斥特征空间 F 中有 n 个特征 f。由于我们采用的是 bin，不同特征 f 可能有不同数量的 bin。他们捆绑过后的合并特征 bin 的个数应该等于所有特征 bin 的个数之和。

对于每个样本，假设它原先属于第 j 个特征的第 i 个 bin，则融合后它应该属于第 个 bin。即附加前 j-1 个特征的 bin 数量之和的偏移。

2. 实例说明

计划用这个比赛的数据 Optiver Realized Volatility Prediction，在另一篇更新。

（已更新，见 LightGBM 实战：波动率预测(1) ）

Reference

1. LightGBM 论文
2. 深入理解LightGBM
3. LightGBM 源码阅读