集成学习（5）LightGBM

发表于 2022-03-11 更新于 2023-04-21 分类于算法，机器学习，集成学习阅读次数：本文字数： 9.7k 阅读时长 ≈ 18 分钟

一、LightGBM

《Lightgbm: A highly efficient gradient boosting decision tree》

《A communication-efficient parallel algorithm for decision tree》

LightGBM 由微软提出，主要用于解决 GDBT 在海量数据中遇到的问题，以便其可以更好更快地用于工业实践中。从 LightGBM 名字我们可以看出其是轻量级（Light）的梯度提升机（GBM），其相对 XGBoost 具有训练速度快、内存占用低的特点。下图分别显示了 XGBoost、XGBoost_hist（利用梯度直方图的 XGBoost）和 LightGBM 三者之间针对不同数据集情况下的内存和训练时间的对比：

那么 LightGBM 到底如何做到更快的训练速度和更低的内存使用的呢？

LightGBM 为了解决这些问题提出了以下几点解决方案：

【减小内存、最优分类点】直方图算法；【特征离散化 + 内存占用 + 方差减少】
【样本维度】单边梯度抽样算法；
- 【根据样本梯度来对梯度小的这边样本进行采样，一部分大梯度和随机分布】
- 一方面算法将更多的注意力放在训练不足的样本上，另一方面通过乘上权重来防止采样对原始数据分布造成太大的影响。
【特征维度】互斥特征捆绑算法；【特征稀疏行优化 +分箱】
【分裂算法】基于最大深度的 Leaf-wise 的垂直生长算法；【深度限制的最大分裂收益的叶子】
类别特征最优分割；
特征并行和数据并行；
缓存优化。

1.1 数学原理

1.1.1 直方图算法

(1) 直方图算法

直方图算法的基本思想是将连续的特征离散化为 k （默认256, 1字节）个离散特征，同时构造一个宽度为 k 的直方图用于统计信息（含有 k 个 bin）。利用直方图算法我们无需遍历数据，只需要遍历 k 个 bin 即可找到最佳分裂点。

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

内存占用更小：XGBoost 需要用 32 位的浮点数去存储特征值，并用 32 位的整形去存储排序索引，而 LightGBM 只需要用 8 位去存储直方图，相当于减少了 1/8；
计算代价更小：计算特征分裂增益时，XGBoost 需要遍历一次数据找到最佳分裂点，而 LightGBM 只需要遍历一次 k 次，直接将时间复杂度从代价是O( feature * distinct_values_of_the_feature); 而 histogram 只需要计算 bins次, 代价是( feature * bins)。distinct_values_of_the_feature >> bins

（2）直方图优化算法流程:

直方图优化算法需要在训练前预先把特征值转化为bin value，也就是对每个特征的取值做个分段函数，将所有样本在该特征上的取值划分到某一段（bin）中。最终把特征取值从连续值转化成了离散值。需要注意得是：feature value对应的bin value在整个训练过程中是不会改变的。
最外面的 for 循环表示的意思是对当前模型下所有的叶子节点处理，需要遍历所有的特征，来找到增益最大的特征及其划分值，以此来分裂该叶子节点。
在某个叶子上，第二个 for 循环就开始遍历所有的特征了。对于每个特征，首先为其创建一个直方图 (new Histogram() )。这个直方图存储了两类信息，分别是 每个bin中样本的梯度之和 $H[ f.bins[i] ].g$ ，还有就是每个bin中样本数量$（H[f.bins[i]].n）$
第三个 for 循环遍历所有样本，累积上述的两类统计值到样本所属的bin中。即直方图的每个 bin 中包含了一定的样本，在此计算每个 bin 中的样本的梯度之和并对 bin 中的样本记数。
最后一个for循环, 遍历所有bin, 分别以当前bin作为分割点, 累加其左边的bin至当前bin的梯度和（ $\left.S_{L}\right)$ 以及样本数量 $\left(n_{L}\right)$, 并与父节点上的总梯度和 $\left(S_{p}\right)$ 以及总样本数量 $\left(n_{p}\right)$ 相减, 得到右边所有bin的梯度和 $\left(S_{R}\right)$ 以及样本数量 $\left(n_{R}\right)$, 带入公式, 计算出增益, 在遍历过程中取最大的增益, 以此时的特征和bin的特征值作为分裂节点的特征和分裂特征取值。

(3) 源码分析

https://blog.csdn.net/anshuai_aw1/article/details/83040541

『我爱机器学习』集成学习（四）LightGBM：https://www.hrwhisper.me/machine-learning-lightgbm/

问题一：如何将特征映射到bin呢？即如何分桶？对于连续特征和类别特征分别怎么样处理？

问题二：如何构建直方图？直方图算法累加的g是什么？难道没有二阶导数h吗？

特征分桶：

特征分桶的源码在bin.cpp文件和bin.h文件中。由于LGBM可以处理类别特征，因此对连续特征和类别特征的处理方式是不一样的。

连续特征:

在bin.cpp中，我们可以看到GreedyFindBin函数和FindBinWithZeroAsOneBin函数，这两个函数得到了数值型特征取值（负数，0，正数）的各个bin的切分点，即bin_upper_bound。

GreedyFindBin: 数值型根据特征不同取值的个数划分，类别型？？

特征取值计数的数组、特征的不同的取值的数组、特征有多少个不同的取值
bin_upper_bound就是记录桶分界的数组
特征取值数比max_bin数量少，直接取distinct_values的中点放置
特征取值数比max_bin来得大，说明几个特征值要共用一个bin
- 如果一个特征值的数目比mean_bin_size大，那么这些特征需要单独一个bin
- 剩下的特征取值的样本数平均每个剩下的bin：mean size for one bin

构建直方图：

给定一个特征的值，我们现在已经可以转化为对应的bin了。现在我们就可以构建直方图了。

ConstructHistogram：

累加了一阶、二阶梯度和还有个数
当然还有其它的版本，当is_constant_hessianis_constant_hessian为true的时候是不用二阶梯度的

寻找最优切分点 : 缺失值处理 + Gain和XGB一样

（4）直方图算法优点：

内存消耗降低。预排序算法需要的内存约是训练数据的两倍（2x样本数x维度x4Bytes），它需要用32位浮点来保存特征值，并且对每一列特征，都需要一个额外的排好序的索引，这也需要32位的存储空间。对于直方图算法，则只需要(1x样本数x维度x1Bytes)的内存消耗，仅为预排序算法的1/8。因为直方图算法仅需要存储特征的 bin 值(离散化后的数值)，不需要原始的特征值，也不用排序，而bin值用8位整型存储就足够了。
算法时间复杂度大大降低。决策树算法在节点分裂时有两个主要操作组成，一个是“寻找分割点”，另一个是“数据分割”。从算法时间复杂度来看，在“寻找分割点”时，预排序算法对于深度为$k$的树的时间复杂度：对特征所有取值的排序为$O(NlogN)$，$N$为样本点数目，若有$D$维特征，则$O(kDNlogN)$，而直方图算法需要$O(kD \times bin)$ (bin是histogram 的横轴的数量，一般远小于样本数量$N$)。
直方图算法还可以进一步加速【两个维度】。一个容易观察到的现象：一个叶子节点的直方图可以直接由父节点的直方图和兄弟节点的直方图做差得到（分裂时左右集合）。通常构造直方图，需要遍历该叶子上的所有数据，但直方图做差仅需遍历直方图的$k$个bin。利用这个方法，LightGBM可以在构造一个叶子的直方图后，可以用非常微小的代价得到它兄弟叶子的直方图，在速度上可以提升一倍。
缓存优化：上边说到 XGBoost 的预排序后的特征是通过索引给出的样本梯度的统计值，因其索引访问的结果并不连续，XGBoost 提出缓存访问优化算法进行改进。 LightGBM 所使用直方图算法对 Cache 天生友好所有的特征都采用相同的方法获得梯度，构建直方图时bins字典同步记录一阶导、二阶导和个数，大大提高了缓存命中；因为不需要存储特征到样本的索引，降低了存储消耗，而且也不存在 Cache Miss的问题。
数据并行优化，用 histgoram 可以大幅降低通信代价。用 pre-sorted 算法的话，通信代价是非常大的（几乎是没办法用的）。所以 xgoobst 在并行的时候也使用 histogram 进行通信。

（5）直方图算法缺点：

当然，直方图算法并不是完美的。由于特征被离散化后，找到的并不是很精确的分割点，所以会对结果产生影响。但在不同的数据集上的结果表明，离散化的分割点对最终的精度影响并不是很大，甚至有时候会更好一点。原因是决策树本来就是弱模型，分割点是不是精确并不是太重要；较粗的分割点也有正则化的效果，可以有效地防止过拟合；即使单棵树的训练误差比精确分割的算法稍大，但在梯度提升（GradientBoosting）的框架下没有太大的影响。

1.1.2 单边梯度抽样算法

直方图算法仍有优化的空间，建立直方图的复杂度为O(feature × data)，如果能降低特征数或者降低样本数，训练的时间会大大减少。

GBDT 算法的梯度大小可以反应样本的权重，梯度越小说明模型拟合的越好，单边梯度抽样算法（Gradient-based One-Side Sampling, GOSS）利用这一信息对样本进行抽样，减少了大量梯度小的样本，在接下来的计算锅中只需关注梯度高的样本，极大的减少了计算量。

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

a%（大梯度）+ (1-a)/ b * b % 的大梯度

使用GOSS进行采样, 使得训练算法更加的关注没有充分训练(under-trained)的样本, 并且只会稍微的改变原有的数据分布。原有的在特征值为 $\mathrm{d}$ 处分数据带来的增益可以定义为： \[ V_{j \mid O}(d)=\frac{1}{n_{O}}\left(\frac{\left(\sum_{x_{i} \in O: x_{i j} \leq d} g_{i}\right)^{2}}{n_{l \mid O}^{j}(d)}+\frac{\left(\sum_{x_{i} \in O: x_{i j}>d} g_{i}\right)^{2}}{n_{r \mid O}^{j}(d)}\right) \] 其中: - O为在决策树待分裂节点的训练集 - $n_{o}=\sum I\left(x_{i} \in O\right)$ - $n_{l \mid O}^{j}(d)=\sum I\left[x_{i} \in O: x_{i j} \leq d\right]$ and $n_{r \mid O}^{j}(d)=\sum I\left[x_{i} \in O: x_{i j}>d\right]$

而使用GOSS后, 增益定义为： \[ V_{j \mid O}(d)=\frac{1}{n_{O}}\left(\frac{\left(\sum_{x_{i} \in A_{l}} g_{i}+\frac{1-a}{b} \sum_{x_{i} \in B_{l}} g_{i}\right)^{2}}{n_{l}^{j}(d)}+\frac{\left(\sum_{x_{i} \in A_{r}} g_{i}+\frac{1-a}{b} \sum_{x_{i} \in B_{l}} g_{r}\right)^{2}}{n_{r}^{j}(d)}\right) \] 其中: - $A_{l}=\left\{x_{i} \in A: x_{i j} \leq d\right\}, A_{r}=\left\{x_{i} \in A: x_{i j}>d\right\}$ - $B_{l}=\left\{x_{i} \in B: x_{i j} \leq d\right\}, B_{r}=\left\{x_{i} \in B: x_{i j}>d\right\}$

实验表明，该做法并没有降低模型性能，反而还有一定提升。究其原因，应该是采样也会增加弱学习器的多样性，从而潜在地提升了模型的泛化能力，稍微有点像深度学习的dropout。

1.1.3 互斥特征捆绑算法【冲突小的特征可能与多个特征包组合】[特征集合]

互斥指的是一些特征很少同时出现非0值【类似one-hot特征】

详解LightGBM两大利器：基于梯度的单边采样（GOSS）和互斥特征捆绑（EFB）

互斥特征捆绑算法（Exclusive Feature Bundling, EFB）指出如果将一些特征进行合并，则可以降低特征数量。高维特征往往是稀疏的，而且特征间可能是相互排斥的（如两个特征不同时取非零值），如果两个特征并不完全互斥（如只有一部分情况下是不同时取非零值），可以用互斥率表示互斥程度。

1）首先介绍如何判定哪些特征应该捆绑在一起？

EFB算法采用构图（build graph）的思想，将特征作为节点，不互斥的特征之间进行连边，然后从图中找出所有的捆绑特征集合。其实学过数据结构里的图算法就了解过，这个问题基本就是图着色问题。但是图着色问题是一个NP-hard问题，不可能在多项式时间里找到最优解。

因此EFB采用了一种近似的贪心策略解决办法。它允许特征之间存在少数的样本点并不互斥（比如某些对应的样本点之间并不同时为非 0 ）, 并设置一个最大冲突阈值 $K$ 。我们选择合适的 $K$ 值, 可以在准确度和训绩效率上获得很好的trade-off (均衡)。

下面给出EFB的特征捆绑的贪心策略流程：

（1）将特征作为图的顶点，对于不互斥的特征进行相连（存在同时不为0的样本），特征同时不为0的样本个数作为边的权重；（2）根据顶点的度对特征进行降序排序，度越大表明特征与其他特征的冲突越大（越不太可能与其他特征进行捆绑）；【入度排序，转化为非零值个数排序】（3）设置最大冲突阈值K，外层循环先对每一个上述排序好的特征，遍历已有的特征捆绑簇，如果发现该特征加入到该特征簇中的冲突数不会超过最大阈值K，则将该特征加入到该簇中。否则新建一个特征簇，将该特征加入到新建的簇中。

上面时间的复杂度为 $O(N^2)$，n为特征的数量，时间其实主要花费在建图上面，两两特征计算互斥程度的时间较长（2层for循环）。对于百万级别的特征数量来说，该复杂度仍是不可行的。为了提高效率，可以不再构建图，将特征直接按照非零值个数排序，将特征非零值个数类比为节点的度（即冲突程度)，因为更多的非零值更容易引起冲突。只是改进了排序策略，不再构建图，下面的for循环是一样的。

2）如何将特征捆绑簇里面的所有特征捆绑（合并）为一个特征？【直方图偏移】

如何进行合并，最关键的是如何能将原始特征从合并好的特征进行分离出来。EFB采用的是加入一个偏移常量（offset）来解决。

举个例子，我们绑定两个特征A和B，A取值范围为[0, 10)，B取值范围为[0, 20)。则我们可以加入一个偏移常量10，即将B的取值范围变为[10,30），然后合并后的特征范围就是[0, 30)，并且能很好的分离出原始特征~

因为lgb中直方图算法对特征值进行了分桶（bin）操作，导致合并互斥特征变得更为简单。从上面伪码看到偏移常量offset直接对每个特征桶的数量累加就行，然后放入偏移常数数组（binRanges）中。

1.1.4 带深度限制的 Leaf-wise 算法

Level-wise

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

Leaf-wise

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

1.1.5 LightGBM类别特征最优分割

LightGBM中只需要提前将类别映射到非负整数即可(integer-encoded categorical features)

我们知道，LightGBM可以直接处理类别特征，而不需要对类别特征做额外的one-hot encoding。那么LGB是如何实现的呢？

类别特征的使用在实践中是很常见的。且为了解决one-hot编码处理类别特征的不足, LightGBM优化了对类别特征的支持，可以直接输入类别特征，不需要额外的0/1展开。LightGBM 采用 many-vs-many 的切分方式将类别特征分为两个子集，实现类别特征的最优切分。假设某维特征有 k 个类别，则有$2^k - 1$种可能, 时间复杂度为$o(2^k)$ ,LightGBM 基于 Fisher的《On Grouping For Maximum Homogeneity》论文实现了 O(klogk) 的时间复杂度。

算法流程如下图所示，在枚举分割点之前，先把直方图按照每个类别对应的label均值进行排序; 然后按照排序的结果依次枚举最优分割点。从下图可以看到, $\frac{\operatorname{Sum}(y)}{\operatorname{Count}(y)}$为类别的均值。当然，这个方法很容易过拟合，所以LightGBM里面还增加了很多对于这个方法的约束和正则化。

在Expo数据集上的实验结果表明，相比0/1展开的方法，使用LightGBM支持的类别特征可以使训练速度加速8倍，并且精度一致。更重要的是，LightGBM是第一个直接支持类别特征的GBDT工具。

1.2 工程实现 - 并行计算

1.2.1 特征并行【优化最优划分点】

传统的特征并行算法在于对数据进行垂直划分，然后使用不同机器找到不同特征的最优分裂点，基于通信整合得到最佳划分点，然后基于通信告知其他机器划分结果。在本小节中，工作的节点称为worker

传统：

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

preview

传统的特征并行方法有个很大的缺点：

需要告知每台机器最终划分结果，增加了额外的复杂度（因为对数据进行垂直划分，每台机器所含数据不同，划分结果需要通过通信告知）；
无法加速split的过程，该过程复杂度为O(#data)O(#data)，当数据量大的时候效率不高；

LightGBM

LightGBM 则不进行数据垂直划分，每台机器都有训练集完整数据，在得到最佳划分方案后可在本地执行划分而减少了不必要的通信。

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

缺点：

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

1.2.2 数据并行

传统方法：

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

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

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

采用点对点方式(point-to-point communication algorithm)进行通讯，每个worker通讯量为$O(machine * feature * bin $)。
采用collective communication algorithm(如“All Reduce”)进行通讯（相当于有一个中心节点，通讯后在返回结果），每个worker的通讯量为$O(machine * feature * bin $)。

LightGBM中的数据并行

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

传统的数据并行策略主要为水平划分数据，然后本地构建直方图并整合成全局直方图，最后在全局直方图中找出最佳划分点。这种数据划分有一个很大的缺点：通讯开销过大。如果使用点对点通信，一台机器的通讯开销大约为 $O(machine * feature * bin $); 如果使用集成的通信, 则通讯开销为 $O(2 * feature * b i n)$.

LightGBM 采用分散规约（Reduce scatter）的方式将直方图整合的任务分摊到不同机器上，从而降低通信代价，并通过直方图做差进一步降低不同机器间的通信。

1.2.3 投票并行

LightGBM采用一种称为PV-Tree的算法进行投票并行(Voting Parallel)，其实这本质上也是一种数据并行。PV-Tree和普通的决策树差不多，只是在寻找最优切分点上有所不同。

其算法伪代码描述如下：

LightGBM-pv-tree

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

LightGBM-voting-parallelization

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

1.2.4 缓存优化

上边说到 XGBoost 的预排序后的特征是通过索引给出的样本梯度的统计值，因其索引访问的结果并不连续，XGBoost 提出缓存访问优化算法进行改进。

而 LightGBM 所使用直方图算法对 Cache 天生友好：

首先，所有的特征都采用相同的方法获得梯度（区别于不同特征通过不同的索引获得梯度），只需要对梯度进行排序并可实现连续访问，大大提高了缓存命中；
其次，因为不需要存储特征到样本的索引，降低了存储消耗，而且也不存在 Cache Miss的问题。