一、模型介绍
上一篇文章介绍了一个梯度提升决策树模型 XGBoost，这篇文章我们继续学习一下 GBDT 模型的另一个进化版本：LightGBM。LigthGBM 是 boosting 集合模型中的新成员，由微软提供，它和 XGBoost 一样是对 GBDT 的高效实现，原理上它和 GBDT 及 XGBoost 类似。不过GBDT 在每一次迭代的时候，都需要遍历整个训练数据多次。如果把整个训练数据装进内存则会限制训练数据的大小；如果不装进内存，反复地读写训练数据又会消耗非常大的时间。尤其面对工业级海量的数据，普通的 GBDT 算法是不能满足其需求的。
LightGBM 提出的主要原因就是为了解决 GBDT 在海量数据遇到的问题，让 GBDT 可以更好更快地用于工业实践。LightGBM 在很多方面会比 XGBoost 表现的更为优秀。这也是我们这篇文章要介绍的重点内容。
二、模型原理
LightGBM 的模型原理和 XGBoost 的模型原理基本一致，具体可参考 XGBoost。不过值得一提的是其中使用的两个算法: GOSS 和 EFB 。
LightGBM 中的 GOSS 和 EFB 算法
提升树是利用加模型与前向分布算法实现学习的优化过程，它有一些高效实现，如 XGBoost，GBDT(Gradient Boosting Decision Tree) 等。其中 GBDT 采用负梯度作为划分的指标（信息增益），XGBoost 则利用到二阶导数。他们共同的不足是，计算信息增益需要扫描所有样本，从而找到最优划分点。在面对大量数据或者特征维度很高时，它们的效率和扩展性很难使人满意。解决这个问题的直接方法就是减少特征量和数据量而且不影响精确度，有部分工作根据数据权重采样来加速 booisting 的过程，但由于 GBDT 没有样本权重不能应用。
LightGBM（基于GBDT的）则很好的解决这些问题，它主要包含两个算法：
(1) 单边梯度采样，Gradient-based One-Side Sampling（GOSS）
GOSS（从减少样本角度）：排除大部分小梯度的样本，仅用剩下的样本计算信息增益，它是一种在减少数据量和保证精度上平衡的算法。
AdaBoost 中，样本权重是数据重要性的指标。然而在 GBDT 中没有原始样本权重，不能应用权重采样。幸运的是，我们观察到 GBDT 中每个数据都有不同的梯度值，对采样十分有用。即梯度小的样本，训练误差也比较小，说明数据已经被模型学习得很好了，直接想法就是丢掉这部分梯度小的数据。然而这样做会改变数据的分布，将会影响训练模型的精确度，为了避免此问题，提出了 GOSS 算法。
GOSS 是一个样本的采样算法，目的是丢弃一些对计算信息增益没有帮助的样本留下有帮助的。根据计算信息增益的定义，梯度大的样本对信息增益有更大的影响。因此，GOSS 在进行数据采样的时候只保留了梯度较大的数据，但是如果直接将所有梯度较小的数据都丢弃掉势必会影响数据的总体分布。所以，GOSS 首先将要进行分裂的特征的所有取值按照绝对值大小降序排序（XGBoost一样也进行了排序，但是 LightGBM 不用保存排序后的结果），选取 top a 个实例。然后在剩余的数据中随机采样 b 个实例。接着计算信息增益时为采样出的小梯度数据乘以 (1-a)/b，这样算法就会更关注训练不足的实例，而不会过多改变原数据集的分布。我们证明此措施在相同的采样率下比随机采样获得更准确的结果，尤其是在信息增益范围较大时。
(2) 互斥特征绑定，Exclusive Feature Bundling（EFB）
EFB（从减少特征角度）：EFB是通过特征捆绑的方式减少特征维度（其实是降维技术）的方式，来提升计算效率。
通常真是应用中，虽然特征量比较多，但是由于特征空间十分稀疏，是否可以设计一种无损的方法来减少有效特征呢？特别在稀疏特征空间上，许多特征几乎是互斥的（例如许多特征不会同时为非零值，像 one-hot），我们可以捆绑互斥的特征。通常被捆绑的特征都是互斥的（一个特征值为零,一个特征值不为零），这样两个特征捆绑起来才不会丢失信息。如果两个特征并不是完全互斥（部分情况下两个特征都是非零值），可以用一个指标对特征不互斥程度进行衡量，称之为冲突比率，当这个值较小时，我们可以选择把不完全互斥的两个特征捆绑，而不影响最后的精度。最后，我们将捆绑问题归约到图着色问题，通过贪心算法求得近似解。
EBF的算法步骤如下：
- 将特征按照非零值的个数进行排序。
- 计算不同特征之间的冲突比率。
- 遍历每个特征并尝试合并特征，使冲突比率最小化。
当然，这里面有两个非常重要的问题：
- 怎么判定那些特征应该绑在一起（build bundled）?
- 怎么把特征绑为一个（merge feature）?
由于这两个问题过于复杂，这里只作简单的思路描述。
bundle（什么样的特征被绑定）算法流程：
- 建立一个图，每个点代表特征，每个边有权重，其权重和特征之间总体冲突相关。
- 按照降序排列图中的度数来排序特征。
- 检查排序之后的每个特征，对他进行特征绑定或者建立新的绑定使得操作之后的总体冲突最小。
merging features(特征合并)：
如何合并同一个 bundle 的特征来降低训练时间复杂度。关键在于原始特征值可以从 bundle 中区分出来。鉴于直方图算法存储离散值而不是连续特征值，我们通过将互斥特征放在不同的箱中来构建 bundle。这可以通过将偏移量添加到特征原始值中实现，例如，假设 bundle 中有两个特征，原始特征 A 取值 [0, 10]， B 取值 [0, 20]。我们添加偏移量 10 到 B 中，因此 B 取值 [10, 30]。通过这种做法，就可以安全地将 A、B 特征合并，使用一个取值 [0, 30] 的特征取代 AB。
EFB 算法能够将许多互斥的特征变为低维稠密的特征，就能够有效的避免不必要 0 值特征的计算。实际，通过用表记录数据中的非零值，来忽略零值特征，达到优化基础的直方图算法。通过扫描表中的数据，建直方图的时间复杂度将从 O(#data) 降到 O(#non_zero_data)。当然，这种方法在构建树过程中需要而额外的内存和计算开销来维持预特征表。我们在 LightGBM 中将此优化作为基本函数，因为当 bundles 是稀疏的时候，这个优化与 EFB 不冲突（可以用于 EFB）。
三、模型细节
1. XGBoost 的缺点
(1) 精确贪心算法
每轮迭代时，都需要遍历整个训练数据多次。如果把整个训练数据装进内存则会限制训练数据的大小；如果不装进内存，反复地读写训练数据又会消耗非常大的时间。
- 优点：可以找到精确的划分条件。
- 缺点：计算量巨大，内存占用巨大，易产生过拟合。
(2) 预排序方法（pre-sorted）
首先，空间消耗大。这样的算法需要保存数据的特征值，还保存了特征排序的结果（例如排序后的索引，为了后续快速的计算分割点），这里需要消耗训练数据两倍的内存。其次时间上也有较大的开销，在遍历每一个分割点的时候，都需要进行分裂增益的计算，消耗的代价大。
- 优点：可以使用多线程，可以加速精确贪心算法
- 缺点：效率低下，可能产生不必要的叶结点
(3) level-wise
生成决策树是 level-wise 级别的，也就是预先设置好树的深度之后，每一颗树都需要生长到设置的那个深度，这样有些树在某一次分裂之后效果甚至没有提升但仍然会继续划分树枝，然后再次划分....之后就是无用功了，耗时。
(4) 对 cache 优化不友好
在预排序后，特征对梯度的访问是一种随机访问，并且不同的特征访问的顺序不一样，无法对 cache 进行优化。同时，在每一层长树的时候，需要随机访问一个行索引到叶子索引的数组，并且不同特征访问的顺序也不一样，也会造成较大的 cache miss。
2. LightGBM对Xgboost的优化
- 基于Histogram的决策树算法
- 直方图做差加速
- 直接支持类别特征 (Categorical Feature)
- 基于直方图的稀疏特征优化
- 带深度限制的Leaf-wise的叶子生长策略
- Cache命中率优化
- 多线程优化
(1) Histogram算法
Histogram algorithm 应该翻译为直方图算法，直方图算法的思想也很简单，首先将连续的浮点数据转换为 bin 数据，具体过程是首先确定对于每一个特征需要多少的桶 bin，然后均分，将属于该桶的样本数据更新为 bin 的值，最后用直方图表示。将连续的浮点特征离散成 k 个离散值，并构造宽度为 k 的 Histogram。然后遍历训练数据，统计每个离散值在直方图中的累计统计量。在进行特征选择时，只需要根据直方图的离散值，遍历寻找最优的分割点。
使用直方图算法有很多优点。首先最明显就是内存消耗的降低，直方图算法不仅不需要额外存储预排序的结果，而且可以只保存特征离散化后的值，而这个值一般用 8 位整型存储就足够了，内存消耗可以降低为原来的 1/8。
然后在计算上的代价也大幅降低，预排序算法每遍历一个特征值就需要计算一次分裂的增益，而直方图算法只需要计算 k 次（k可以认为是常数），时间复杂度从 O(#data#feature) 优化到 O(k#features)。
Histogram 算法并不是完美的。由于特征被离散化后，找到的并不是很精确的分割点，所以会对结果产生影响。但在实际的数据集上表明，离散化的分裂点对最终的精度影响并不大，甚至会好一些。原因在于 decision tree 本身就是一个弱学习器，采用 Histogram 算法会起到正则化的效果，有效地防止模型的过拟合。时间上的开销由原来的 O(#data * #features) 降到 O(k * #features)。由于离散化，#bin 远小于 #data，因此时间上有很大的提升。
Histogram 算法有几个需要注意的地方：
- 使用 bin 替代原始数据相当于增加了正则化。
- 使用 bin 意味着很多数据的细节特征被放弃了，相似的数据可能被划分到相同的桶中，这样的数据之间的差异就消失了。
- bin 数量选择决定了正则化的程度，bin 越少惩罚越严重，欠拟合风险越高。
- 构建直方图时不需要对数据进行排序（比XGBoost快），因为预先设定了bin的范围。
- 直方图除了保存划分阈值和当前 bin 内样本数以外还保存了当前 bin 内所有样本的一阶梯度和（一阶梯度和的平方的均值等价于均方损失）。
- 阈值的选取是按照直方图从小到大遍历，使用了上面的一阶梯度和，目的是得到划分之后 △loss 最大的特征及阈值。
Histogram 算法的优缺点：
Histogram 算法并不是完美的。由于特征被离散化后，找到的并不是很精确的分割点，所以会对结果产生影响。但在实际的数据集上表明，离散化的分裂点对最终的精度影响并不大，甚至会好一些。原因在于 decision tree 本身就是一个弱学习器，采用 Histogram 算法会起到正则化的效果，有效地防止模型的过拟合。时间上的开销由原来的 O(#data * #features) 降到 O(k * #features) 。由于离散化，#bin 远小于 #data，因此时间上有很大的提升。
(2) 直方图差加速:
LightGBM 另一个优化是 Histogram（直方图）做差加速。一个容易观察到的现象：一个叶子的直方图可以由它的父亲节点的直方图与它兄弟的直方图做差得到。通常构造直方图，需要遍历该叶子上的所有数据，但直方图做差仅需遍历直方图的k个桶。利用这个方法，LightGBM 可以在构造一个叶子的直方图后，可以用非常微小的代价得到它兄弟叶子的直方图，在速度上可以提升一倍。
(3) 直接支持类别特征:
实际上大多数机器学习工具都无法直接支持类别特征，一般需要把类别特征，转化 one-hot 特征，降低了空间和时间的效率。而类别特征的使用是在实践中很常用的。基于这个考虑，LightGBM 优化了对类别特征的支持，可以直接输入类别特征，不需要额外的 0/1 展开。并在决策树算法上增加了类别特征的决策规则。
one-hot 编码是处理类别特征的一个通用方法，然而在树模型中，这可能并不一定是一个好的方法，尤其当类别特征中类别个数很多的情况下。主要的问题是：
- 可能无法在这个类别特征上进行切分（即浪费了这个特征）。使用 one-hot 编码，意味着在每一个决策节点上只能使用 one vs other 的切分方式。当类别值很多时，每个类别上的数据可能会比较少，这时候切分会产生不平衡，这意味着切分增益也会很小（比较直观的理解是，不平衡的切分和不切分没有区别）。
-
会影响决策树的学习。因为就算可以在这个类别特征进行切分，也会把数据切分到很多零碎的小空间上。如下图左边所示，而决策树学习时利用的是统计信息，在这些数据量小的空间上，统计信息不准确，学习会变差。但如果使用下图右边的分裂方式，数据会被切分到两个比较大的空间，进一步的学习也会更好。
image.png
为了解决 one-hot 编码处理类别特征的不足。LightGBM 采用了 many vs many 的切分方式，实现了类别特征的最优切分。用 LightGBM 可以直接输入类别特征，并产生上图右边的效果。在 1 个 k 维的类别特征中寻找最优切分，朴素的枚举算法的复杂度是 O(2^k)，而LightGBM采用了如 On Grouping For Maximum Homogeneity 的方法实现了 O(k log k) 的算法。
算法流程下图所示：在枚举分割点之前，先把直方图按每个类别的均值进行排序；然后按照均值的结果依次枚举最优分割点。从下图可以看到，Sum(y)/Count(y) 为类别的均值。当然，这个方法很容易过拟合，所以在 LightGBM 中加入了很多对这个方法的约束和正则化。
(4) 基于直方图的稀疏特征优化
(5) 带深度限制的 Leaf-wise 的叶子生长策略
在 Histogram 算法之上，LightGBM 进行进一步的优化。首先它抛弃了大多数 GBDT 工具使用的按层生长 (level-wise) 的决策树生长策略，而使用了带有深度限制的按叶子生长 (leaf-wise) 算法。
XGBoost 采用的是按层生长 level-wise 生长策略，能够同时分裂同一层的叶子，从而进行多线程优化，不容易过拟合；但不加区分的对待同一层的叶子，带来了很多没必要的开销。因为实际上很多叶子的分裂增益较低，没必要进行搜索和分裂。
LightGBM 采用 leaf-wise 生长策略，每次从当前所有叶子中找到分裂增益最大（一般也是数据量最大）的一个叶子，然后分裂，如此循环。因此同 Level-wise相比，在分裂次数相同的情况下，Leaf-wise 可以降低更多的误差，得到更好的精度。Leaf-wise 的缺点是可能会长出比较深的决策树，产生过拟合。因此 LightGBM 在 Leaf-wise 之上增加了一个最大深度的限制，在保证高效率的同时防止过拟合。
(6) Cache 命中率优化
(7) 线程优化
直接支持高效并行。LightGBM 原生支持并行学习，目前支持特征并行和数据并行的两种。特征并行的主要思想是在不同机器在不同的特征集合上分别寻找最优的分割点，然后在机器间同步最优的分割点。数据并行则是让不同的机器先在本地构造直方图，然后进行全局的合并，最后在合并的直方图上面寻找最优分割点。
LightGBM 针对这两种并行方法都做了优化，在特征并行算法中，通过在本地保存全部数据避免对数据切分结果的通信；在数据并行中使用分散规约 (Reduce scatter) 把直方图合并的任务分摊到不同的机器，降低通信和计算，并利用直方图做差，进一步减少了一半的通信量。
基于投票的数据并行则进一步优化数据并行中的通信代价，使通信代价变成常数级别。在数据量很大的时候，使用投票并行可以得到非常好的加速效果。
更具体的内容可以看NIPS2016的文章：A Communication-Efficient Parallel Algorithm for Decision Tree
四、模型优缺点
五、模型使用
import lightgbm as lgb
model = lgb.LGBMClassifier(boosting_type='gbdt', num_leaves=31, max_depth=-1,
learning_rate=0.1, n_estimators=100,
subsample_for_bin=200000, objective=None, class_weight=None,
min_split_gain=0., min_child_weight=1e-3, min_child_samples=20,
subsample=1., subsample_freq=0, colsample_bytree=1.,
reg_alpha=0., reg_lambda=0., random_state=None,
n_jobs=-1, silent=True, importance_type='split')
model.fit(X_train, y_train, eval_metric='l2',
eval_set=[(X_train, y_train), (X_eval, y_eval)],
eval_names=['train', 'evals'],
early_stopping_rounds=50,
verbose=500,
categorical_feature=categorical_feature)
model.predict(test_x)
model.predict_proba(test_x)
