我们知道特征离散化具有很多优点,如存储方便、运算更快、鲁棒性强、模型更加稳定等 。对于直方图算法来说最直接的有以下两个优点:
- 内存占用更小:直方图算法不仅不需要额外存储预排序的结果,而且可以只保存特征离散化后的值,而这个值一般用 位整型存储就足够了,内存消耗可以降低为原来的。也就是说XGBoost需要用 位的浮点数去存储特征值,并用 位的整形去存储索引,而 LightGBM只需要用 位去存储直方图,内存相当于减少为 ;
文章插图
图:内存占用优化为预排序算法的1/8
- 计算代价更小:预排序算法XGBoost每遍历一个特征值就需要计算一次分裂的增益,而直方图算法LightGBM只需要计算 次( 可以认为是常数),直接将时间复杂度从 降低到 ,而我们知道 。
原因是决策树本来就是弱模型,分割点是不是精确并不是太重要;较粗的分割点也有正则化的效果,可以有效地防止过拟合;即使单棵树的训练误差比精确分割的算法稍大,但在梯度提升(Gradient Boosting)的框架下没有太大的影响 。
(2)直方图做差加速LightGBM另一个优化是Histogram(直方图)做差加速 。一个叶子的直方图可以由它的父亲节点的直方图与它兄弟的直方图做差得到,在速度上可以提升一倍 。通常构造直方图时,需要遍历该叶子上的所有数据,但直方图做差仅需遍历直方图的k个桶 。
在实际构建树的过程中,LightGBM还可以先计算直方图小的叶子节点,然后利用直方图做差来获得直方图大的叶子节点,这样就可以用非常微小的代价得到它兄弟叶子的直方图 。
文章插图
图:直方图做差
注意:XGBoost 在进行预排序时只考虑非零值进行加速,而 LightGBM 也采用类似策略:只用非零特征构建直方图 。
2.2 带深度限制的 Leaf-wise 算法
在Histogram算法之上,LightGBM进行进一步的优化 。首先它抛弃了大多数GBDT工具使用的按层生长 (level-wise) 的决策树生长策略,而使用了带有深度限制的按叶子生长 (leaf-wise) 算法 。
XGBoost 采用 Level-wise 的增长策略,该策略遍历一次数据可以同时分裂同一层的叶子,容易进行多线程优化,也好控制模型复杂度,不容易过拟合 。但实际上Level-wise是一种低效的算法,因为它不加区分的对待同一层的叶子,实际上很多叶子的分裂增益较低,没必要进行搜索和分裂,因此带来了很多没必要的计算开销 。
文章插图
图:按层生长的决策树
LightGBM采用Leaf-wise的增长策略,该策略每次从当前所有叶子中,找到分裂增益最大的一个叶子,然后分裂,如此循环 。
因此同Level-wise相比,Leaf-wise的优点是:在分裂次数相同的情况下,Leaf-wise可以降低更多的误差,得到更好的精度;Leaf-wise的缺点是:可能会长出比较深的决策树,产生过拟合 。因此LightGBM会在Leaf-wise之上增加了一个最大深度的限制,在保证高效率的同时防止过拟合 。
文章插图
图:按叶子生长的决策树
2.3 单边梯度采样算法
Gradient-based One-Side Sampling 应该被翻译为单边梯度采样(GOSS) 。GOSS算法从减少样本的角度出发,排除大部分小梯度的样本,仅用剩下的样本计算信息增益,它是一种在减少数据量和保证精度上平衡的算法 。
AdaBoost中,样本权重是数据重要性的指标 。然而在GBDT中没有原始样本权重,不能应用权重采样 。幸运的是,我们观察到GBDT中每个数据都有不同的梯度值,对采样十分有用 。即梯度小的样本,训练误差也比较小,说明数据已经被模型学习得很好了,直接想法就是丢掉这部分梯度小的数据 。然而这样做会改变数据的分布,将会影响训练模型的精确度,为了避免此问题,提出了GOSS算法 。
GOSS是一个样本的采样算法,目的是丢弃一些对计算信息增益没有帮助的样本留下有帮助的 。根据计算信息增益的定义,梯度大的样本对信息增益有更大的影响 。因此,GOSS在进行数据采样的时候只保留了梯度较大的数据,但是如果直接将所有梯度较小的数据都丢弃掉势必会影响数据的总体分布 。
推荐阅读
- AMD|AMD Zen4锐龙“龙凤胎”来了:55W功耗、游戏本终于满血
- 家长的鼓励和希望寄语有哪些?
- 如何彻底禁用手机内置浏览器?
- 亚马逊|发布15年后 亚马逊Kindle终于支持ePub电子书格式了
- 一文让你彻底搞清楚,Linux零拷贝技术的那些事儿
- 个人网站站长的时代要彻底落幕了,挥手不带云彩
- 财报|结束三年连亏 长安汽车终于靠卖车赚钱了
- Win11彻底解决系统蓝屏问题简单粗暴!只是背景换成了黑屏
- 坚持苦学 TCP,终于把 TCP 协议给学明白了,坚持看完你会收获很大
- 便秘怎么调理 12食疗方帮你彻底远离便秘