LightGBM
LightGBM是一个实现GBDT算法的框架, 支持高效率的并行训练, 并且具有更快的训练速度, 更低的内存消耗, 更好的准确率, 支持分布式可以快速处理海量数据等优点.
它参考了Xgboost算法的优点, 以及不足之处, 对传统的GBDT算法进行了改造, 是一种高效准确的算法.
之前算法的不足之处
GBDT类算法的不足
之前的GBDT类算法都有一个问题, 在每一次迭代的时候, 都需要遍历整个训练数据多次. 当训练集不能完整的装入内存时, 反复的读写会消耗大量的时间. 即使可以装入内存, 高频地对大数据量进行扫描计算, 也是会消耗大量的算例, 导致算法的低效.
XGBoost的不足
在确定分割点时, 即使使用近似算法, 也要遍历整个训练集, 得到一阶梯度和二阶梯度的累加, 计算出每个分割点的收益. XGBoost使用了预排序算法, 对所有特征提前进行了预排序, 但这样导致每个特征的排序结果还要存储指向存储这个样本一阶和二阶梯度的指针, 导致消耗的内存变为原来的两倍, 对内存更加不友好.
另外XGBoost的多种cache机制经常出现miss cache的问题.
LightGBM就在传统的GBDT算法上, 对XGBoost进行了改进.
LightGBM基本原理
基于Histogram的决策树算法
直方图算法(Histogram algorithm)的基本思想是: 先把连续的浮点特征值离散化成k个整数, 同时构造一个宽度为k的直方图. 在遍历数据的时候, 根据离散化后的值作为索引在直方图中累积统计量, 然后根据直方图的离散值, 遍历寻找最优的分割点.
其实就是一种将连续特征离散化的技巧. 首先确定对于每一个特征需要多少个箱子(bin), 并为每一个箱子分配一个新的整数值作为这个特征的新值, 将浮点数的范围均分成若干区间, 将属于该箱子的样本数据更新为箱子的值.
使用直方图的方式处于以下考虑:
内存占用更小: 直方图算法不仅不需要额外存储预排序的结果, 而且可以只保存特征离散化后的值, 而这个值一般用int8位整型存储就足够了. 之前一般使用float32存储浮点数特征值, 使用int32存储指向样本梯度位置的指针, 相当于在这个特征上, 特征的内存消耗缩小为原来的1/8
计算代价更小: 使用预排序的特征值计算这个特征的最佳分裂点时, 还是需要遍历所有的样本. 但在LightGBM中只需要遍历k个bin即可, k的值一般很小, 这部分遍历的消耗基本可以忽略
而且, LightGBM树中的每个节点都会维护对应特征的分布直方图, 记录属于该节点的所有样本在本特征上的分布情况, 在分裂的过程中, 一个叶子的直方图可以由它的父亲节点的直方图与它兄弟的直方图做差得到, 不需要分别计算两个叶子节点, 因此得到了进一步的加速.
带深度限制的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是一个样本的采样算法, 目的是丢弃一些对计算信息增益没有帮助的样本留下有帮助的, 在采样的时候只保留了梯度较大的数据, 但是如果直接将所有梯度较小的数据都丢弃掉势必会影响数据的总体分布.
互斥特征捆绑算法
高维度的数据往往是稀疏的, 这种稀疏性启发我们设计一种无损的方法来减少特征的维度.
通常被捆绑的特征都是互斥的(如one-hot生成的特征), 这样两个特征捆绑起来才不会丢失信息. 如果两个特征并不是完全互斥, 可以用一个指标对特征不互斥程度进行衡量, 称之为冲突比率, 当这个值较小时, 我们可以选择把不完全互斥的两个特征捆绑, 在损失较小的信息下, 缩减特征维度, 提高训练速度.
EFB需要判断两个问题:
怎么判定哪些特征应该绑在一起
怎么把特征绑为一个
build bundled
LightGBM的EFB算法将判定哪些特征应该绑在一起转化为图着色的问题来求解. 将所有的特征视为图的各个顶点, 将不是相互独立的特征用一条边连接起来, 边的权重就是两个相连接的特征的总冲突值. 这样需要绑定的特征就是在图着色问题中要涂上同一种颜色的那些点. 过程如下:
构造一个加权无向图, 顶点是特征, 边有权重, 其权重与两个特征间冲突相关
根据节点的度进行降序排序, 度越大, 与其它特征的冲突越大
遍历每个特征, 将它分配给现有特征包, 如果发现该特征加入到特征包中的矛盾数不超过某一个阈值, 则将该特征加入到该包中, 如果该特征不能加入任何一个已有的特征包中, 则新建一个包, 使得总体冲突最小
将特征按照非零值个数排序
代替了度数量的计算, 将复杂度降低到线性级别.
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了. 例如:
LightGBM的工程优化
直接支持类别特征
LightGBM优化了对类别特征的支持, 可以直接输入类别特征, 不需要进行One-hot展开. LightGBM采用many-vs-many的切分方式将类别特征分为两个子集, 实现类别特征的最优切分.
这个方法很容易过拟合, 所以LightGBM里面还增加了很多对于这个方法的约束和正则化. 实验结果表明, 相对于将特征进行One-hot展开, 使用LightGBM支持的类别特征可以使训练速度加速8倍.
支持高效并行
数据并行
XGBoost是支持特征并行的, 它是将不同的特征分配到不同的核/机器上计算各自的最优的分割点, 然后在机器间同步最优的分割点. 这种方法把数据按特征进行划分, 每台机器所含数据不同, 增加了额外通信的复杂度.
LightGBM是在每台机器上保存全部训练数据, 但每台机器计算仍然是划分的, 只是在得到最佳划分方案后可在本地执行划分, 从而减少了不必要的通信.
投票并行
基于投票的数据并行则进一步优化数据并行中的通信代价, 使通信代价变成常数级别. 在数据量很大的时候, 使用投票并行的方式只合并部分特征的直方图从而达到降低通信量的目的, 可以得到非常好的加速效果. 具体过程如下:
本地找出Top K特征, 并基于投票筛选出可能是最优分割点的特征
合并时只合并每个机器选出来的特征
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之上增加了一个最大深度限制, 在保证高效率的同时防止过拟合
在寻找最优解时, 依据的是最优切分变量, 没有将最优解是全部特征的综合这一理念考虑进去
调参方法
参考资料
最后更新于