XGundam05 发表于 2022-5-9 17:58

XGBoost与LightGBM总结

问:XGBoost做了哪些优化?


[*]GBDT在优化时只用到一阶导;xgboost则对代价函数进行了二阶泰勒展开,同时用到了一阶和二阶导。
[*]Xgboost采用level-wise生成决策树,同时分裂同一层的叶子,从而进行多线程优化,不容易过拟合,但很多叶子节点的分裂增益较低,没必要进行跟进一步的分裂,带来了不必要的开销。



level-wise growth


[*]采用了以下三种降低过拟合的方法:

[*]在代价函数里显示的加入了正则项,用于控制模型的复杂度,降低过拟合,提高模型的泛化能力。正则项里包含了树的叶子节点个数、每个叶子节点上输出的score的L2模的平方和。
[*]Shrinkage(缩减),相当于学习速率(xgboost中的 https://www.zhihu.com/equation?tex=%5Ceta )。xgboost在进行完一次迭代后,会将叶子节点的权重乘上该系数,主要是为了削弱每棵树的影响,让后面有更大的学习空间,降低过拟合。
[*]列抽样(column/feature subsampling)。xgboost借鉴了随机森林的做法,支持列抽样(分裂只选取一部分特征),不仅能降低过拟合,还能减少计算。


[*]对缺失值的处理:对于特征的值有缺失的样本,xgboost可以自动学习出它的分裂方向。在按照特征分裂的时候,相当于增加了一个默认的分裂方向:如果该样本的特征缺失,则样本被分入默认的叶子节点。



default的分裂方向(红色)


[*]学习缺失值的方法:假如特征有两个值,那么缺失的一类会被通过 [(A, missing), B] 和 分别算损失,选取损失小的一侧作为default。预测时把missing的样本归入损失小的default方向里。
[*]xgboost工具支持并行。注意,并行不是tree粒度的并行,是在特征层面上的。决策树的学习最耗时的一个步骤就是对特征的值进行排序(因为要确定最佳分割点),xgboost在训练之前,预先对数据进行了排序,然后保存为block结构,后面的迭代中重复地使用这个结构,大大减小计算量。这个block结构也使得并行成为了可能,在进行节点的分裂时,需要计算每个特征的增益,最终选增益最大的那个特征去做分裂,那么各个特征的增益计算就可以开多线程进行。
[*]XGBoost使用的是预排序(pre-sort)算法,能够更精确的找到数据分隔点;LightGBM使用的是histogram算法,占用的内存更低,数据分隔的复杂度更低。
问:LightGBM做了哪些优化?


[*]LightGBM采用深度优化,leaf-wise生长策略,每次从当前叶子中选择增益最大的结点进行分裂,循环迭代,但会生长出更深的决策树,产生过拟合。因此引入了一个阈值进行限制,防止过拟合。



leaf-wise growth


[*]直方图算法的基本思想是先把连续的浮点特征值离散化成 k个整数,同时构造一个宽度为k的直方图。把连续的浮点特征值离散化为k个整数(分桶的思想,桶称为bin)比如[0,0.1)→0, [0.1,0.3)→1
[*]然后根据直方图的离散值,遍历寻找最优的分割点。在XGBoost中需要遍历所有离散化的值,而在这里只要遍历k个直方图的值。



直方图算法


[*]但是,基于直方图的算法对于稀疏的数据不如pre-sorted的算法。因此又提出了两个优化方法:

[*]GOSS(gradient-based one side sampling) 单边梯度抽样算法,对梯度小的样本随机抽样,用剩下的样本去估计信息增益,以此来选择特征。
[*]EFB(exclusive feature bundling) 互斥特征捆绑。互斥特征指的是不同时出现的特征(rarely take nonzero values simultaneously)。以此来减少特征的个数。
问:LightGBM是如何处理类别特征的?

我们知道,LightGBM可以直接处理类别特征,而不需要对类别特征做额外的one-hot encoding。那么LGB是如何实现的呢?
LGB采用了many-vs-many的方法,也就是说,把在分裂的时候把可以 https://www.zhihu.com/equation?tex=feature_k%3D1+%7C%7C+feature_k%3D2+ 分到二叉树的一侧,其余的类别值分到另一侧。对于一个 https://www.zhihu.com/equation?tex=k 个取值的离散变量,有 https://www.zhihu.com/equation?tex=2%5E%7Bk-1%7D+-+1 种分裂方法,朴素的分裂方法复杂度是 https://www.zhihu.com/equation?tex=O%282%5Ek%29 。LGB采用了优化的算法,得到了 https://www.zhihu.com/equation?tex=O%28k+%2A+log%28k%29%29 的复杂度:

具体来说,LGB在枚举分割点之前,先把直方图按每个类别的均值进行排序;然后按照均值的结果依次枚举最优分割点。



按照label均值进行排序

上图中,对某个离散特征的abc三个取值进行排序,排序的方法是取值的平均数。
问:XGBoost是如何计算特征重要性的?

有三个参数可以用于评估特征重要性:
1. 次数权重weight :该特征在所有树中被用作分割样本的总次数。
2. 增益gain :该特征在其出现过的所有树中产生的平均增益。
3. 覆盖cover :该特征在其出现过的所有树中的平均覆盖范围。覆盖范围这里指的是一个特征用作分割点后,其影响的样本数量,即有多少样本经过该特征分割到两个子节点。



Reference:
关于sklearn中的决策树是否应该用one-hot编码?
LightGBM 相关知识理解

算法面试系列文章:
页: [1]
查看完整版本: XGBoost与LightGBM总结