> For the complete documentation index, see [llms.txt](https://kerasnoone.gitbook.io/garnet/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://kerasnoone.gitbook.io/garnet/ji-qi-xue-xi/ensemble-model/boosting-ji-ben-gai-nian/lightgbm.md). # LightGBM ## LightGBM LightGBM是一个实现GBDT算法的框架, 支持高效率的并行训练, 并且具有更快的训练速度, 更低的内存消耗, 更好的准确率, 支持分布式可以快速处理海量数据等优点. 它参考了Xgboost算法的优点, 以及不足之处, 对传统的GBDT算法进行了改造, 是一种高效准确的算法. ### 之前算法的不足之处 #### GBDT类算法的不足 之前的GBDT类算法都有一个问题, **在每一次迭代的时候, 都需要遍历整个训练数据多次**. 当训练集不能完整的装入内存时, 反复的读写会消耗大量的时间. 即使可以装入内存, 高频地对大数据量进行扫描计算, 也是会消耗大量的算例, 导致算法的低效. #### XGBoost的不足 在确定分割点时, 即使使用近似算法, 也要遍历整个训练集, 得到一阶梯度和二阶梯度的累加, 计算出每个分割点的收益. XGBoost使用了预排序算法, 对所有特征提前进行了预排序, 但这样导致每个特征的排序结果还要存储指向存储这个样本一阶和二阶梯度的指针, 导致消耗的内存变为原来的两倍, 对内存更加不友好. 另外XGBoost的多种cache机制经常出现miss cache的问题. LightGBM就在传统的GBDT算法上, 对XGBoost进行了改进. ### LightGBM基本原理 #### 基于Histogram的决策树算法 **直方图算法**(Histogram algorithm)的基本思想是: 先把连续的浮点特征值离散化成k个整数, 同时构造一个宽度为k的直方图. 在遍历数据的时候, 根据离散化后的值作为索引在直方图中累积统计量, 然后根据直方图的离散值, 遍历寻找最优的分割点. 其实就是一种将**连续特征离散化**的技巧. 首先确定对于每一个特征需要多少个箱子(bin), 并为每一个箱子分配一个新的整数值作为这个特征的新值, 将浮点数的范围均分成若干区间, 将属于该箱子的样本数据更新为箱子的值. ![](/files/-MTiIfzotBp9B_usJEAl) ![](/files/-MTiIfzqF0tFVHx66X1M) 使用直方图的方式处于以下考虑: * **内存占用更小**: 直方图算法不仅不需要额外存储预排序的结果, 而且可以只保存特征离散化后的值, 而这个值一般用int8位整型存储就足够了. 之前一般使用float32存储浮点数特征值, 使用int32存储指向样本梯度位置的指针, 相当于在这个特征上, 特征的内存消耗缩小为原来的1/8 * **计算代价更小**: 使用预排序的特征值计算这个特征的最佳分裂点时, 还是需要遍历所有的样本. 但在LightGBM中只需要遍历k个bin即可, k的值一般很小, 这部分遍历的消耗基本可以忽略 而且, LightGBM树中的每个节点都会维护对应特征的分布直方图, 记录属于该节点的所有样本在本特征上的分布情况, 在分裂的过程中, **一个叶子的直方图可以由它的父亲节点的直方图与它兄弟的直方图做差得到**, 不需要分别计算两个叶子节点, 因此得到了进一步的加速. ![](/files/-MTiIfzrdGm_Rz6PuLKW) #### 带深度限制的Leaf-wise算法 GBDT, XGBoost算法等都使用了传统决策树**按层生长**(level-wise)的策略, 但LightGBM中的决策树使用**按叶子生长**(leaf-wise)的方法. 按层生长策略, 遍历一次数据(即所有当前的叶子节点)可以分裂得到一层新的叶子节点, 容易进行多线程优化, 也好控制模型复杂度, 不容易过拟合. 但它不加区分的对待同一层的叶子, 实际上很多叶子的分裂增益较低, 没必要进行搜索和分裂, 带来了很多没必要的计算开销, 实际上是一种比较低效的算法. LightGBM采用Leaf-wise的增长策略: 从当前所有叶子中, 找到分裂增益最大的一个叶子节点, 然后分裂, 如此循环. 同Level-wise策略相比, Leaf-wise的优点是: * 在分裂次数相同的情况下, Leaf-wise可以降低更多的误差, 得到更好的精度 * 避免了分裂增益低的节点计算, 效率高 缺点是: * 可能会长出比较深的决策树, 产生过拟合 因此LightGBM会在Leaf-wise之上增加了一个**最大深度的限制**, 在保证高效率的同时防止过拟合. #### 单边梯度采样算法 单边梯度采样算法(Gradient-based One-Side Sampling, GOSS), 从减少样本的角度出发, **排除大部分小梯度的样本**, 仅用剩下的样本计算信息增益, **是一种在减少数据量和保证精度上平衡的算法**. GBDT与XGBoost不同, 样本没有权重, 不能应用权重采样. 但在每次迭代时, 每个样本都有自己的梯度值, 梯度值小说明这个样本产生的误差很小, 可以认为被学习的很好了, 对训练的进一步提升作用不大, 可以尝试在**尽量少改变数据分布**的情况下, 丢弃这部分小梯度样本. 因此可以使用梯度作为样本的权重, 进行抽样. GOSS是一个样本的采样算法, 目的是丢弃一些对计算信息增益没有帮助的样本留下有帮助的, 在采样的时候只保留了梯度较大的数据, 但是如果直接将所有梯度较小的数据都丢弃掉势必会影响数据的总体分布. GOSS首先将要进行分裂的特征的所有取值按照梯度绝对值大小降序排序(与XGBoost不同的是不保存排序结果), 选取绝对值最大的$$a \times 100 %$$个样本, 然后再在剩余的样本中选择$$b \times 100 %$$个样本(这里的$$b%$$指的是全部样本中的比例), 再将被选择的这些样本的梯度放大$$\frac{1-a}{b}$$倍, 再使用这$$(a+b)%$$被选择的样本按新的梯度计算分裂增益. #### 互斥特征捆绑算法 高维度的数据往往是稀疏的, 这种稀疏性启发我们设计一种无损的方法来减少特征的维度. 通常被捆绑的特征都是互斥的(如one-hot生成的特征), 这样两个特征捆绑起来才不会丢失信息. 如果两个特征并不是完全互斥, 可以用一个指标对特征不互斥程度进行衡量, 称之为**冲突比率**, 当这个值较小时, 我们可以选择把不完全互斥的两个特征捆绑, 在损失较小的信息下, 缩减特征维度, 提高训练速度. 互斥特征捆绑算法(Exclusive Feature Bundling, EFB)将一些特征进行融合绑定, 降低特征数量, 这样在构建直方图时的时间复杂度从$$O(\text{#data} \* \text{#feature})$$变为$$O(\text{#data} \* \text{#bundle})$$, 其中的$$\text{#bundle}$$指的是特征融合绑定后特征包的个数, 通常是远小于原始特征数量的. EFB需要判断两个问题: * 怎么判定哪些特征应该绑在一起 * 怎么把特征绑为一个 **build bundled** LightGBM的EFB算法将判定哪些特征应该绑在一起转化为图着色的问题来求解. **将所有的特征视为图的各个顶点, 将不是相互独立的特征用一条边连接起来, 边的权重就是两个相连接的特征的总冲突值**. 这样需要绑定的特征就是在图着色问题中要涂上同一种颜色的那些点. 过程如下: * 构造一个加权无向图, 顶点是特征, 边有权重, 其权重与两个特征间冲突相关 * 根据**节点的度**进行降序排序, 度越大, 与其它特征的冲突越大 * 遍历每个特征, 将它分配给现有特征包, 如果发现该特征加入到特征包中的矛盾数不超过某一个阈值, 则将该特征加入到该包中, 如果该特征不能加入任何一个已有的特征包中, 则新建一个包, 使得总体冲突最小 上面这个算法的时间复杂度为$$O(\text{#feature}^2)$$. 在训练之前处理一次, 在特征数量不多的时可接受. 但对于上百万的特征, LightGBM进一步提出了种更加高效的无图的排序策略: * 将特征按照非零值个数排序 代替了度数量的计算, 将复杂度降低到线性级别. **merge feature** 特征合并算法, 其关键在于原始特征能从合并的特征中分离出来, 绑定几个特征在同一个bundle里需要保证绑定前的原始特征的值可以在bundle中识别. 考虑到histogram-based算法将连续的值保存为离散的bins, 我们可以使得不同特征的值分到bundle中的不同bin中, 这可以通过在特征值中加一个偏置常量来解决. 比如, 我们在bundle中绑定了两个特征A和B, A特征的原始取值为区间\[0,10), B特征的原始取值为区间\[0,20), 我们可以在B特征的取值上加一个偏置常量10, 将其取值范围变为\[10,30), 绑定后的特征取值范围为\[0, 30), 这样就可以放心的融合特征A和B了. 例如: ![](/files/-MTiIfzvo8NJS25VIVTs) ### LightGBM的工程优化 #### 直接支持类别特征 LightGBM优化了对类别特征的支持, 可以直接输入类别特征, 不需要进行One-hot展开. LightGBM采用**many-vs-many**的切分方式将类别特征分为两个子集, 实现类别特征的最优切分. 假设某维特征有$$k$$个类别, 有$$2^{(k-1)}-1$$种划分的可能. LightGBM基于Fisher的\论文实现了$$O(k \log k)$$的时间复杂度下计算这些中可能中的最优划分. 在枚举分割点之前, 先按照直方图对这个特征的所有类别(bins)对应的label均值进行排序, 然后按照排序的结果依次枚举最优分割点. 所以这里是做了一个简化, 将$$2^{(k-1)}-1$$种划分可能简化为$$k$$种划分可能. 排序的依据是标签值均值, 即$$\frac{\text{Sum}(y)}{\text{Count}(y)}$$, 如下图: ![](/files/-MTiIfzwhPTGPq5Kdv62) 这个方法很容易过拟合, 所以LightGBM里面还增加了很多对于这个方法的约束和正则化. 实验结果表明, 相对于将特征进行One-hot展开, 使用LightGBM支持的类别特征可以使训练速度加速8倍. #### 支持高效并行 **数据并行** XGBoost是支持特征并行的, 它是将不同的特征分配到不同的核/机器上计算各自的最优的分割点, 然后在机器间同步最优的分割点. 这种方法把数据按特征进行划分, 每台机器所含数据不同, 增加了额外通信的复杂度. LightGBM是在每台机器上保存全部训练数据, 但每台机器计算仍然是划分的, 只是在得到最佳划分方案后可在本地执行划分, 从而减少了不必要的通信. **投票并行** 基于投票的数据并行则进一步优化数据并行中的通信代价, 使通信代价变成常数级别. 在数据量很大的时候, 使用投票并行的方式只合并部分特征的直方图从而达到降低通信量的目的, 可以得到非常好的加速效果. 具体过程如下: * 本地找出Top K特征, 并基于投票筛选出可能是最优分割点的特征 * 合并时只合并每个机器选出来的特征 ![](/files/-MTiIfzxEq8aLqNtDJGV) #### Cache命中率优化 XGBoost对cache优化不友好, 在预排序后, 特征对梯度的访问是一种随机访问, 并且不同的特征访问的顺序不一样, 无法对cache进行优化. 而LightGBM所使用直方图算法对Cache天生友好: * 区别于XGBoost的不同特征通过不同的索引获得梯度, 所有的特征都采用相同的方式获得梯度, 只需要对梯度进行排序并可实现连续访问, 大大提高了缓存命中率 * 因为不需要存储样本索引到叶子索引的数组, 降低了存储消耗, 而且也不存在Cache Miss的问题 ### LightGBM的优缺点 #### 优点 * LightGBM采用了直方图算法将遍历样本转变为遍历直方图, 极大的降低了时间复杂度 * LightGBM在训练过程中采用单边梯度算法过滤掉梯度小的样本, 减少了大量的计算 * LightGBM采用了基于Leaf-wise算法的增长策略构建树, 减少了很多不必要的计算量 * LightGBM采用优化后的特征并行, 数据并行方法加速计算, 当数据量非常大的时候还可以采用投票并行的策略 * LightGBM对缓存也进行了优化, 增加了缓存命中率 * LightGBM使用了直方图算法将特征值转变为bin值, 且不需要记录特征到样本的索引, 极大的减少了内存消耗 * LightGBM在训练过程中采用互斥特征捆绑算法减少了特征数量, 降低了内存消耗 * LightGBM采用了直方图算法将存储特征值转变为存储bin值, 降低了数据的精度, 从而降低了内存消耗 #### 缺点 * 可能会长出比较深的决策树, 产生过拟合. 因此LightGBM在Leaf-wise之上增加了一个最大深度限制, 在保证高效率的同时防止过拟合 * 在寻找最优解时, 依据的是最优切分变量, 没有将最优解是全部特征的综合这一理念考虑进去 ## 调参方法 参考[机器学习算法之LightGBM](https://www.biaodianfu.com/lightgbm.html)中**如何使用LightGBM**一节. ## 参考资料 * [机器学习算法之LightGBM](https://www.biaodianfu.com/lightgbm.html) * [深入理解LightGBM](https://zhuanlan.zhihu.com/p/99069186) * [【白话机器学习】算法理论+实战之LightGBM算法](https://zhuanlan.zhihu.com/p/149522630)