XGBoost与LightGBM总结

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

问：XGBoost做了哪些优化？

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

level-wise growth

采用了以下三种降低过拟合的方法：

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

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

default的分裂方向(红色)

学习缺失值的方法：假如特征有两个值，那么缺失的一类会被通过 [(A, missing), B] 和 [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的方法，也就是说，把在分裂的时候把可以 $feature_k=1 || feature_k=2$ 分到二叉树的一侧，其余的类别值分到另一侧。对于一个 $k$ 个取值的离散变量，有 $2^{k-1} - 1$ 种分裂方法，朴素的分裂方法复杂度是 $O(2^k)$ 。LGB采用了优化的算法，得到了 $O(k * log(k))$ 的复杂度：

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

按照label均值进行排序

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

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

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

算法面试系列文章：

		自动登录	找回密码
密码			立即注册

XGBoost与LightGBM总结

本帖子中包含更多资源