图:直⽅图做差
注意: 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在进⾏数据采样的时候只保留了梯度较⼤的数据,但是如果直接将所