LightGBM

https://www.hrwhisper.me/machine-learning-lightgbm/
https://zhuanlan.zhihu.com/p/87885678
https://zhuanlan.zhihu.com/p/78293497

LightGBM 由微软提出，主要用于解决 GDBT 在海量数据中遇到的问题，以便其可以更好更快地用于工业实践中。

设计理念：

单个机器在不牺牲速度的情况下，尽可能多地用上更多的数据；
多机并行的时候，通信的代价尽可能地低，并且在计算上可以做到线性加速。

最后选择使用分布式 GBDT，选择了基于 histogram 的决策树算法。
XGBoost、XGBoost_hist（利用梯度直方图的 XGBoost）和 LightGBM 三者之间针对不同数据集情况下的内存和训练时间的对比：

image.png

XGBOOST的缺点：

空间消耗大。需要保存数据的特征值。XGBoost采用Block结构，存储指向样本的索引，需要消耗两倍的内存。
时间开销大。在寻找最优切分点时，要对每个特征都进行排序，还要对每个特征的每个值都进行了遍历，并计算增益。
对Cache不友好。使用Block块预排序后，特征对梯度的访问是按照索引来获取的，是一种随机访问，而不同特征访问顺序也不一样，容易照成命中率低的问题。同时，在每一层长树的时候，需要随机访问一个行索引到叶子索引的数组，并且不同特征访问的顺序也不一样，也会造成较大的Cachemiss。（虽然XG有Cache aware access优化但还是比不过）

使用直方图算法进行划分点的查找可以很好的克服这些缺点。

LightGBM的新解决方案：

单边梯度抽样算法；
直方图算法；（减少分割点的测试数）
互斥特征捆绑算法；（减少特征）
基于最大深度的 Leaf-wise 的垂直生长算法；
类别特征最优分割；
特征并行和数据并行；
缓存优化。

1）单边梯度抽样算法：（Gradient-based One-Side Sampling, GOSS）（压缩样本数量）

GBDT 算法的梯度大小可以反应样本的权重，梯度越小说明模型拟合的越好，单边梯度抽样算法利用这一信息对样本进行抽样，减少了大量梯度小的样本，在接下来的计算锅中只需关注梯度高的样本，极大的减少了计算量。但是抛弃那些梯度很小的样本，会导致训练集的分布会被改变，可能会使得模型准确率下降。

步骤：

根据梯度的绝对值将样本进行降序排序
选择前a×100%的样本，这些样本称为A
剩下的数据(1−a)×100% 的数据中，随机抽取b×100%的数据，这些样本称为B
在计算增益的时候，放大样本B中的梯度(1−a)/b 倍
关于g，在具体的实现中是一阶梯度和二阶梯度的乘积

GOSS 事先基于梯度的绝对值对样本进行排序（无需保存排序后结果），然后拿到前 a% 的梯度大的样本，和剩下样本的 b%，在计算增益时，通过乘上 $\frac{1-a}{b}$ 来放大梯度小的样本的权重。一方面算法将更多的注意力放在训练不足的样本上，另一方面通过乘上权重来防止采样量减少对原始数据分布造成太大的影响。

使用GOSS进行采样，使得训练算法更加的关注没有充分训练(under-trained)的样本，并且只会稍微的改变原有的数据分布。

2）直方图算法

<1> 直方图算法：

直方图算法的基本思想是将连续的特征值离散化为 k 个离散特征值，同时构造一个宽度为 k 的直方图用于统计信息（含有 k 个 bin）。同时，将特征根据其所在的bin进行梯度累加。这样，遍历一次数据后，直方图累积了需要的梯度信息，然后可以直接根据直方图，寻找最优的切分点。利用直方图算法我们无需遍历数据，只需要遍历 k 个 bin 即可找到最佳分裂点。

image.png

我们知道特征离散化的具有很多优点，如存储方便、运算更快、鲁棒性强、模型更加稳定等等。对于直方图算法来说最直接的有以下两个优点（以 k=256 为例）：

内存占用更小：XGBoost 需要用 32 位的浮点数去存储特征值，并用 32 位的整形去存储索引，而 LightGBM 只需要用 8 位去存储直方图，相当于减少了 1/8；
计算代价更小：计算特征分裂增益时，XGBoost 需要遍历一次数据找到最佳分裂点，而 LightGBM 只需要遍历一次 k 次，直接将时间复杂度从 $Data*Future$ 降到 $k*Future$ ，而我们知道 $Data>>k$
如何分桶？

以离散特征为例：（连续的装箱处理就是特征工程中的离散化：如[0,0.3)—>0，[0.3,0.7)—->1等）

Step 1：先对A进行排序然后返回A的所有不重复取值和每一个取值对应出现的次数，比如[1,2,3,4,5,6,1,2,3,4...]处理完毕之后就得到了distinct_values=[1,2,3,4,5,6],counts=[4,2,4,4,3,1]，这个时候开始分桶。

Step2：假设max_bin=10（限制桶内元素最多个数）,此时distinct_values的值得比max_bin小，我们就开始从小到大开始进行分桶，首先1分为第一个桶，我们命名为“1桶”，这个时候分桶的切分点不是1，而是1和下一个数字2的平均数即(1+2)/2=1.5，接着到2，此时这里有一个小细节需要注意，lightgbm有一个不起眼的参数参数min_data_in_bin（限制桶内元素最小个数）默认值为3，也就是如果连续值中的某一个数的取值小于3是不能单独分桶的，这是一个可以调节的超参数，想象一下，当min_data_in_bin=1，而连续值没有一个重复的，那么最终分桶的结果和没分桶一样，从这个角度来看，这里实际上起到了一定正则化（避免分没分都一样）的作用，把取值差不多的但是出现次数少的数字合并到一块儿，避免了太过精细的切分。那么2无法合并，就要和后面的3合并成一个桶，则【2，2，3，3，3，3】合并成一个桶，我们称之为“2桶”，此时需要注意，因为在2的时候由于2的数量不够无法单独分桶，所以切分点不是（2+3）/2=2.5而应该与下一个连续值4相关联，切分点应该是（3+4）/2=3.5,下一个连续值是4，单独为1个桶，切分点为(4+5)/2=4.5,接着5和6合并为一个桶,切分点为(5+6)/2=5.5,注意到这个时候整个序列已经分桶完毕，6是最大值。

原始数据（从大到小排序）：【6，5，5，5，4，4，4，4，3，3，3，3，2，2，1，1，1，1】

映射为bin之后：【4，4，4，4，3，3，3，3，2，2，2，2，2，2，1，1，1，1】

之后如果需要针对这个特征进行切分，我们只需要在1.5,3.5,4.5进行切分就可以了，然后再去计算后续的各种增益。

计算分裂阈值的过程：

<2> 直方图加速：

在构建叶节点的直方图时，我们还可以通过父节点的直方图与相邻叶节点的直方图相减的方式构建，从而减少了一半的计算量。在实际操作过程中，我们还可以先计算直方图小的叶子节点，然后利用直方图作差来获得直方图大的叶子节点。

image.png

<3> 稀疏特征优化：

XGBoost 在进行预排序时只考虑非零值进行加速，而 LightGBM 也采用类似策略：只用非零特征构建直方图。

特征工程：

如何合并互斥特征到一块：

3）互斥特征捆绑算法：

一个有高维特征空间的数据往往是稀疏的，而稀疏的特征空间中，许多特征是互斥的。所谓互斥就是他们从来不会同时具有非0值（一个典型的例子是进行One-hot编码后的类别特征）。LightGBM利用这一点提出Exclusive Feature Bundling（EFB）算法来进行互斥特征的合并，从而减少特征的数目。做法是先确定哪些互斥的特征可以合并（可以合并的特征放在一起，称为bundle），然后将各个bundle合并为一个特征。

那么，问题来了：

如何判断哪里特征应该放在一个Bundle中？
如何将bundle中的特征合并为一个新的特征？

对于第1个问题，将特征划分为最少数量的互斥的bundle是NP问题（可以根据图着色问题来证明）。

步骤：

1）构造一个加权无向图，顶点是特征，边是两个特征间互斥程度；
2）根据节点的度进行降序排序，度越大，与其他特征的冲突越大；
3）按顺序对排好序的特征进行遍历，对于当前特征i，查看是否能加入已有的bundle，若不行，则新建一个bundle（冲突小的圈先加入实在不行独立）

更进一步的，通常有少量的特征，它们之间并非完全的独立，但是绝大多数情况下，并不会同时取非0值。若构建Bundle的算法允许小的冲突，就能得到更少数的bundle，进一步提高效率。可以证明，随机的污染一部分特征则最多影响精度 $O([1-\gamma]n)^{-2/3}$ ，γ为最大的特征冲突率，也是在速度和精度之间达到平衡的有效手段。

上述的算法复杂度为 $O(\#feature^2)$ ，当特征数很大的时候，仍然效率不高。

还可以进一步优化：不建立图，直接按特征的非0值的个数进行排序。（这也是一种贪心，非0值越多，越可能冲突）

将放在一起的多个互斥特征再合并为一个特征

4）特征合并算法（Merge Exclusive Features）

通过对原始特征的值添加偏移来实现，从而将互斥的特征放在不同的bins中。例如，一个Bundle中有两个特征A和B $A \in [0,10),\ B \in [0,20)$ ，可以给特征B添加偏移量10，使得B的值域范围变为 $B \in [10,30)$ ，然后，A和B就可以合并成值域为 $[0,30]$ 新特征。

通过MEF算法，将许多互斥的稀疏特征转化为稠密的特征，降低了特征的数量，提高了建直方图的效率。

5）树的生长策略：

在XGBoost中，树是按层生长的，称为Level-wise tree growth，同一层的所有节点都做分裂，最后剪枝，如下图所示：

image.png

Level-wise过一次数据可以同时分裂同一层的叶子，容易进行多线程优化，也好控制模型复杂度，不容易过拟合。但实际上Level-wise是一种低效的算法，因为它不加区分的对待同一层的叶子，带来了很多没必要的开销，因为实际上很多叶子的分裂增益较低，没必要进行搜索和分裂。

LightGBM采用的是Leaf-wise tree growth：

Leaf-wise则是一种更为高效的策略，每次从当前所有叶子中，找到分裂增益最大的一个叶子，然后分裂，如此循环。因此同Level-wise相比，在分裂次数相同的情况下，Leaf-wise可以降低更多的误差，得到更好的精度。Leaf-wise的缺点是可能会长出比较深的决策树，产生过拟合。因此LightGBM在Leaf-wise之上增加了一个最大深度的限制，在保证高效率的同时防止过拟合。

image.png

并行计算

传统特征并行

特征并行主要是并行化决策树中寻找最优划分点(“Find Best Split”)的过程，因为这部分最为耗时。

传统算法的做法如下：

垂直划分数据（对特征划分），不同的worker有不同的特征集
每个workers找到局部最佳的切分点{feature, threshold}
workers使用点对点通信，找到全局最佳切分点
具有全局最佳切分点的worker进行节点分裂，然后广播切分后的结果（左右子树的instance indices）
其它worker根据收到的instance indices也进行划分

image.png

传统算法的缺点是：

1）无法加速split的过程，该过程复杂度为O(#data)，当数据量大的时候效率不高
2）需要广播划分的结果（左右子树的instance indices），1条数据1bit的话，大约需要花费O(#data/8)

LightGBM中的特征并行（CART选哪个特征）

每个worker保存所有的数据集，这样找到全局最佳切分点后各个worker都可以自行划分，就不用进行广播划分结果，减小了网络通信量。过程如下：

1）每个workers找到局部最佳的切分点{feature, threshold}
2）workers使用点对点通信，找到全局最佳切分点
3）每个worker根据全局全局最佳切分点进行节点分裂

但是这样仍然有缺点：

1）split过程的复杂度仍是O(#data)，当数据量大的时候效率不高
2）每个worker保存所有数据，存储代价高

image.png

传统数据并行

数据并行目标是并行化整个决策学习的过程：

1）水平切分数据，不同的worker拥有部分数据
2）每个worker根据本地数据构建局部直方图
3）合并所有的局部直方图得到全部直方图
4）根据全局直方图找到最优切分点并进行分裂

image.png

在第3步中，有两种合并的方式：

1）采用点对点方式进行通讯，每个worker通讯量为 O(#machine #feature #bin)
2）采用collective communication algorithm(如“All Reduce”)进行通讯（相当于有一个中心节点，通讯后在返回结果），每个worker的通讯量为 O(2∗#feature∗#bin) 可以看出通信的代价是很高的，这也是数据并行的缺点。

LightGBM中的数据并行

使用“Reduce Scatter”将不同worker的不同特征的直方图合并，然后workers在局部合并的直方图中找到局部最优划分，最后同步全局最优划分。(局部聚类如何再融合)
前面提到过，可以通过直方图作差法得到兄弟节点的直方图，因此只需要通信一个节点的直方图。

通过上述两点做法，通信开销降为 O(0.5 #feature #bin)

LightGBM中的投票并行（Voting Parallel）

LightGBM采用一种称为PV-Tree的算法进行投票并行(Voting Parallel)，其实这本质上也是一种数据并行。

PV-Tree和普通的决策树差不多，只是在寻找最优切分点上有所不同。

1）水平切分数据，不同的worker拥有部分数据。
2）Local voting: 每个worker构建直方图，找到top-k个最优的本地划分特征
3）Global voting: 中心节点聚合得到最优的top-2k个全局划分特征（top-2k是看对各个worker选择特征的个数进行计数，取最多的2k个）
4）Best Attribute Identification：中心节点向worker收集这top-2k个特征的直方图，并进行合并，然后计算得到全局的最优划分
5）中心节点将全局最优划分广播给所有的worker，worker进行本地划分。

image.png

可以看出，PV-tree将原本需要 #feature×#bin 变为了 2k×#bin，通信开销得到降低。此外，可以证明，当每个worker的数据足够多的时候，top-2k个中包含全局最佳切分点的概率非常高。

LightGBM的缓存优化：

LightGBM使用的直方图算法能很好的解决这类问题。首先。对梯度的访问，因为不用对特征进行排序，同时，所有的特征都用同样的方式来访问，所以只需要对梯度访问的顺序进行重新排序，所有的特征都能连续的访问梯度。并且直方图算法不需要把数据id到叶子节点号上（不需要这个索引表，没有这个缓存消失问题），大大提高cache的命中率，减少cache-miss出现的概率。

与XGBOOST的比较：

image.png

内存更小

1）XGBoost 使用预排序后需要记录特征值及其对应样本的统计值的索引，而 LightGBM 使用了直方图算法将特征值转变为 bin 值，且不需要记录特征到样本的索引，将空间复杂度从 $O(2*data)$ 降低为 $O(bin)$ ，极大的减少了内存消耗；
2）LightGBM 采用了直方图算法将存储特征值转变为存储 bin 值，降低了内存消耗；
3）LightGBM 在训练过程中采用互斥特征捆绑算法减少了特征数量，降低了内存消耗。

速度更快

1）LightGBM 采用了直方图算法将遍历样本转变为遍历直方图，极大的降低了时间复杂度；
2）LightGBM 在训练过程中采用单边梯度算法过滤掉梯度小的样本，减少了大量的计算；
3）LightGBM 采用了基于 Leaf-wise 算法的增长策略构建树，减少了很多不必要的计算量；
4）LightGBM 采用优化后的特征并行、数据并行方法加速计算，当数据量非常大的时候还可以采用投票并行的策略；
5）LightGBM 对缓存也进行了优化，增加了 Cache hit 的命中率。