XGBoost算法个人理解

小鱼儿 2022-10-31 00:58 339阅读 0赞

XGBoost算法仍然是一种使用加法模型和前向分布算法逐步逼近最优结果的Gradient boosting梯度提升方法。并且，XGBoost算法在目标函数中同时引入了正则化项（度量树模型的复杂度）用来降低模型过拟合的风险。

**损失函数**

![20210220192634740.png][]

其中，![20210220192634746.png][]表示模型对于样本的预测损失，也叫经验误差。![20210220192634744.png][]表示模型的复杂度，也叫结构误差，起到正则化的作用。这个损失函数的形式类似于加入L1或L2正则化的逻辑回归损失函数。

![20210220192735915.png][]

![20210220192735917.png][]

二阶泰勒展开公式：

![20210220192735913.png][]

对![20210220192841445.png][]应用二阶泰勒展开公式，其中![20210220192735926.png][]相当于![20210220192735927.png][]，![20210220192735930.png][]相当于 ![20210220192735934.png][]，![20210220192735937.png][]相当于![20210220192735936.png][]，![20210220192735938.png][]是一个函数模型，是一个自变量，作为最小的优化粒度，这也照应了Gradient Boosting梯度提升方法中所说的梯度提升方法是在函数空间中进行优化的说法。令![20210220192735944.png][]和![2021022019294356.png][]分别为经验损失函数![20210220192735941.png][]对![20210220193000976.png][]的一阶偏导和二阶偏导。

![20210220192735943.png][]

![20210220192735946.png][]

所以在进行第t轮迭代学习时，![20210220193049363.png][]和![20210220193049364.png][]只和前t-1个已经确定的模型参数有关，与当前第t轮正在学习的模型参数无关，所以可以认为![20210220193049369.png][]和![20210220193049372.png][]是确定的常数。所以优化的目标函数![20210220193049375.png][]可以改写为：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2N4eDY1NA_size_16_color_FFFFFF_t_70][]

其中![20210220193049376.png][]只和前t-1个已经确定的模型参数有关，与当前第t轮正在学习的模型参数无关，可以看做一个常数。此时可以看到目标函数![20210220193049397.png][]是一个关于![20210220193049399.png][]的一元二次函数，后面关于XGBoost为什么要使用二阶泰勒展开的讨论中再说一下。

**正则项（模型复杂度）**

![2021022019323134.png][]是正则化项，用于控制树的复杂度，![2021022019323137.png][]和叶子节点个数、叶子节点权重有关。首先将一棵树![2021022019323137.png][]定义如下：

![2021022019323138.png][]

这里* *![2021022019323142.png][] 表示树叶上的权重，![20210220193314316.png][]是一个将每个数据样本点![2021022019323147.png][]分配给叶子节点的函数，![2021022019323154.png][]是树叶的数量。 在 XGBoost算法中，将一棵树的复杂度定义为叶子结点的个数和树叶权重的L2范数的函数：

![2021022019323150.png][]

其中叶子节点的个数![20210220193231124.png][]表示树的规模大小，树叶权重的L2范数表示叶子节点权重的平滑程度。

**优化目标**

减小![20210220193409344.png][]，也就是说使![20210220193437268.png][]和![20210220193409347.png][]都减小，也就是得到的模型预测结果更准确的同时，模型更简单，也就是奥卡姆剃刀原理。

需要求解的优化目标就是得到每棵树的结构，以及对应叶子节点的权重。对上面的优化目标![20210220193409350.png][]做一下转换，由于![20210220193409352.png][]和![20210220193409356.png][]与当前第t轮学习的模型参数无关，且![20210220193409359.png][]表示的是样本![20210220193409357.png][]所在叶子节点的权重，所以可以将目标函数![20210220193409368.png][]转化为当前第t轮得到的决策树所有叶子节点目标函数的累加和：

![20210220193409369.png][]

将遍历所有样本求损失转换为遍历所有叶子节点上的样本求损失，因为样本终究会落在叶子节点上。其中，![20210220193409370.png][]表示落在第j个叶子节点上的样本集合，![20210220193409375.png][]表示i是落在第j个叶子节点上的样本集合中的样本。这样转换的好处就是，当树结构也就是![20210220193409378.png][]确定的情况下，由于一棵树叶子节点的权重计算与其他叶子节点无关，可以同时对![2021022019354810.png][]个叶子节点进行并行优化，提升优化速度，当每个叶子结点的子式都达到最值点时，整个目标函数![20210220193409379.png][]才达到最值点。同时，由于使用了二阶导数和L2正则化项，经过此转换后将每个叶子节点的优化函数转换成了一个关于![20210220193409380.png][]的一元二次函数，便于直接使用求根公式进行求解（解析解）。

**XGBoost为什么要使用二阶导数？**

参照MSE损失函数的优化过程，关于二次方程的最优解可以直接计算一阶导数等于0计算得到，但是对于一般损失函数，没有MSE这种凸函数的性质，无法通过一阶导数为0计算最优结果。然而，在二阶泰勒展开中会自然的引入变量![20210220193612945.png][]的二次项，这样方便通过直接计算一阶导数为0得到优化结果。

![20210220193612942.png][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2N4eDY1NA_size_16_color_FFFFFF_t_70 1][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2N4eDY1NA_size_16_color_FFFFFF_t_70 2][]

最终优化目标转换为关于第 t 轮函数![20210220193612974.png][]的一元二次函数，可以使用求解公式求解最优解，这也是引入二阶导数的目的，便于使用求解公式求解。

**确定树结构**![2021022019370297.png][]

前面说过，当树结构![2021022019370296.png][]确定的情况下，可以使用求根公式求解每个叶子节点的权重。那么怎么才能快速的确定树的结构呢？

XGBoost的基模型可以是决策树和线型模型，当基模型是线性模型时，目标函数就相当于是同时使用了L1和L2正则化的线性回归模型。当基模型是决策树模型时，需要计算决策树的结构。

**贪心算法**

从树的深度0开始，计算所有特征的最佳分裂点，选择分裂收益最大的特征分裂点进行分裂左右分支，类似于ID3、C4.5和CART决策树算法的分裂规则。区别仅在于分裂原则不同，XGBoost的分裂原则是自己定义了一套计算收益的规则，而ID3则是信息增益。

1.  对每个叶节点枚举所有的可用特征；
2.  计算分裂收益：针对每个特征，把属于该节点的训练样本根据该特征值进行升序排列，通过线性扫描的方式来决定该特征的最佳分裂点，并记录该特征的分裂收益；
3.  选择分裂特征：选择收益最大的特征作为分裂特征，用该特征的最佳分裂点作为分裂位置，在该节点上分裂出左右两个新的叶节点，并为每个新节点关联对应的样本集；
4.  递归迭代：回到第1步，递归执行直到满足特定条件为止；

分裂规则：计算分裂前的目标函数值，计算分裂后的目标函数值（包含分裂后的左右子树），计算分裂后的目标函数收益

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2N4eDY1NA_size_16_color_FFFFFF_t_70 3][]

可以在这里看到一个重要的事实：如果增益小于gamma，最好不要添加那个分支，这样也可以起到防止过拟合的作用。

**近似算法**

贪心算法的计算量大，需要计算每个特征在每个可能的分裂位置的分裂收益，当训练数据量太大时，无法一次性全部加载入内存计算每个特征在每个可能的分裂位置的分裂收益。近似算法对于每个特征进行分位数离散化分桶，只考察分位点，计算在分位点位置的分裂收益，可以减少特征的分裂位置计算数量，降低计算复杂度。

两种特征离散化分桶策略：

1.  Global全局模式：学习每棵树前就提出候选切分点，并在每次分裂时都采用这种分割，计算的是全部样本每个特征的分位数，然后进行离散化分桶
2.  Local局部模式：每次分裂前将重新提出候选切分点，计算的是落在当前待分裂叶子节点上样本每个特征的分位数，然后进行离散化分桶。

特性：Local策略对于每个待分裂的叶子结点，分别计算当前叶子节点上样本特征的分位数，计算量小，分位数计算精细，但是需要更多的计算步骤。而Global策略因为节点已有划分，如果想得到与Local同样的分位数分桶粒度，需要划分更多的候选点，也就是分更多的桶。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2N4eDY1NA_size_16_color_FFFFFF_t_70 4][]

上图中![20210220193843433.png][]表示算法的精度，其倒数表示分位数分桶的数量，也就是分桶的粒度大小，粒度越大精度越低，粒度越小精度越高，过拟合的风险也越大。在上图中![202102201937528.png][]的情况下，Local的精度要远高于Global的精度，这也就是上文中说的，如果Global想得到与Local相同的计算精度，需要分更多的桶。当Global的![202102201937524.png][]时，分的桶更多，同时Global也达到了了与Local ![2021022019375240.png][]相当的精度。同时近似算法也可以得到与贪心算法相当的精度。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2N4eDY1NA_size_16_color_FFFFFF_t_70 5][]

分别以每个分位点作为切分点，计算切分前后的目标函数收益，选择目标函数收益最大的切分点。

**预测结果**

回归问题：

![20210220193930462.png][]

二分类问题：

![20210220193930461.png][]

![20210220193930463.png][]

多分类问题：

![20210220193930471.png][]

![20210220193930472.png][]

![20210220194149894.png][]

![20210220194050199.png][]

![20210220193930479.png][]

![20210220193930473.png][]

![20210220193930482.png][]

![20210220193930483.png][]

**XGBoost每一轮拟合的目标是什么？**

我们都知道提升树算法拟合的是残差，梯度提升算法拟合的是损失函数负梯度在当前模型的值，其实拟合的也是残差。而通过上面描述的XGBoost算法可知，XGBoost算法与提升树和梯度提升算法的优化方向不同，提升树和梯度提升算法的优化方向是逐步降低模型预测的残差，损失函数是![20210220193930490.png][]，而XGBoost算法的优化方向是逐步降低模型预测的误差，预测误差通过损失函数来定义，损失函数是![20210220193930498.png][]。所以XGBoost算法在每一轮拟合的都是样本的真实标签label，那么XGBoost每一轮拟合的数据岂不是都一样吗？我的个人理解是，表面上看上去每一轮的拟合数据都是一样的，但是XGBoost采用的是前向分布加法，每一轮的迭代是在前面t-1轮的基础上进行的，所以第t轮迭代的优化会受到前面t-1轮结果的约束，从这个角度来理解，那么每一轮的拟合数据又都是不一样的。GBDT每一步的损失函数是![20210220193930497.png][]，而XGBoost每一步的损失函数是![20210220193930504.png][]，![20210220193930505.png][]一直在变，而每一步![20210220193930503.png][]不变。如果一定要说XGBoost分类问题每轮拟合一个什么东西，那就是输入样本对应某类的真实概率–前面k-1棵树组合计算的对应该类的概率值。

--------------------

就说到这吧，头发要紧。

**以下是来自于知乎大神wepon对于XGBoost的总结：**

*  传统GBDT以CART作为基分类器，xgboost还支持线性分类器，这个时候xgboost相当于带L1和L2正则化项的逻辑斯蒂回归（分类问题）或者线性回归（回归问题）。
 *  传统GBDT在优化时只用到一阶导数信息，xgboost则对代价函数进行了二阶泰勒展开，同时用到了一阶和二阶导数。顺便提一下，xgboost工具支持自定义代价函数，只要函数可一阶和二阶求导。
 *  xgboost在代价函数里加入了正则项，用于控制模型的复杂度。正则项里包含了树的叶子节点个数、每个叶子节点上输出的score的L2模的平方和。从Bias-variance tradeoff角度来讲，正则项降低了模型的variance，使学习出来的模型更加简单，防止过拟合，这也是xgboost优于传统GBDT的一个特性。
 *  Shrinkage（缩减），相当于学习速率（xgboost中的eta）。xgboost在进行完一次迭代后，会将叶子节点的权重乘上该系数，主要是为了削弱每棵树的影响，让后面有更大的学习空间。实际应用中，一般把eta设置得小一点，然后迭代次数设置得大一点。（补充：传统GBDT的实现也有学习速率）
 *  列抽样（column subsampling）。xgboost借鉴了随机森林的做法，支持列抽样，不仅能降低过拟合，还能减少计算，这也是xgboost异于传统gbdt的一个特性。

*  对缺失值的处理。对于特征的值有缺失的样本，xgboost可以自动学习出它的分裂方向。
 *  xgboost工具支持并行。boosting不是一种串行的结构吗?怎么并行的？注意xgboost的并行不是tree粒度的并行，xgboost也是一次迭代完才能进行下一次迭代的（第t次迭代的代价函数里包含了前面t-1次迭代的预测值）。xgboost的并行是在特征粒度上的。我们知道，决策树的学习最耗时的一个步骤就是对特征的值进行排序（因为要确定最佳分割点），xgboost在训练之前，预先对数据进行了排序，然后保存为block结构，后面的迭代中重复地使用这个结构，大大减小计算量。这个block结构也使得并行成为了可能，在进行节点的分裂时，需要计算每个特征的增益，最终选增益最大的那个特征去做分裂，那么各个特征的增益计算就可以开多线程进行。

*  可并行的近似直方图算法。树节点在进行分裂时，我们需要计算每个特征的每个分割点对应的增益，即用贪心法枚举所有可能的分割点。当数据无法一次载入内存或者在分布式情况下，贪心算法效率就会变得很低，所以xgboost还提出了一种可并行的近似直方图算法，用于高效地生成候选的分割点。

**参考文献**

**[XGBoost做分类问题时每一轮迭代拟合的是什么？][XGBoost]**

[深入理解XGBoost][XGBoost 1]

[机器学习算法中 GBDT 和 XGBOOST 的区别有哪些？][GBDT _ XGBOOST]

[XGB做分类时每一轮都在干啥？][XGB]

[20210220192634740.png]: /images/20221024/80196429d9614778a9524c299711d4c7.png
[20210220192634746.png]: https://img-blog.csdnimg.cn/20210220192634746.png
[20210220192634744.png]: /images/20221024/3d8205992f184a0999607098079f15f3.png
[20210220192735915.png]: /images/20221024/73aa70f645b64093b18af29dfa0ef661.png
[20210220192735917.png]: /images/20221024/1783f7aaf4c545e787fb5e4cf47199e0.png
[20210220192735913.png]: /images/20221024/7f84b083582f4f25953504ce5e90cffd.png
[20210220192841445.png]: https://img-blog.csdnimg.cn/20210220192841445.png
[20210220192735926.png]: https://img-blog.csdnimg.cn/20210220192735926.png
[20210220192735927.png]: https://img-blog.csdnimg.cn/20210220192735927.png
[20210220192735930.png]: https://img-blog.csdnimg.cn/20210220192735930.png
[20210220192735934.png]: https://img-blog.csdnimg.cn/20210220192735934.png
[20210220192735937.png]: https://img-blog.csdnimg.cn/20210220192735937.png
[20210220192735936.png]: https://img-blog.csdnimg.cn/20210220192735936.png
[20210220192735938.png]: https://img-blog.csdnimg.cn/20210220192735938.png
[20210220192735944.png]: https://img-blog.csdnimg.cn/20210220192735944.png
[2021022019294356.png]: https://img-blog.csdnimg.cn/2021022019294356.png
[20210220192735941.png]: https://img-blog.csdnimg.cn/20210220192735941.png
[20210220193000976.png]: /images/20221024/815143e9b8e74776b6fdc13233f0bd9c.png
[20210220192735943.png]: /images/20221024/40af5e6f43734f0ebb43fbece13fb447.png
[20210220192735946.png]: /images/20221024/34ec1d1bfbf54b50bac20c32fd2f25cf.png
[20210220193049363.png]: https://img-blog.csdnimg.cn/20210220193049363.png
[20210220193049364.png]: https://img-blog.csdnimg.cn/20210220193049364.png
[20210220193049369.png]: https://img-blog.csdnimg.cn/20210220193049369.png
[20210220193049372.png]: https://img-blog.csdnimg.cn/20210220193049372.png
[20210220193049375.png]: /images/20221024/af55b69d1a2b4ca2bc6c7e8ea2205391.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2N4eDY1NA_size_16_color_FFFFFF_t_70]: /images/20221024/8034b76f10c84c06974f99c405ac0104.png
[20210220193049376.png]: https://img-blog.csdnimg.cn/20210220193049376.png
[20210220193049397.png]: https://img-blog.csdnimg.cn/20210220193049397.png
[20210220193049399.png]: /images/20221024/aa99bab3400e42348d4f804ae818780e.png
[2021022019323134.png]: https://img-blog.csdnimg.cn/2021022019323134.png
[2021022019323137.png]: /images/20221024/91add18d29e44a8db09a4878eec30728.png
[2021022019323138.png]: /images/20221024/4fa5c772bd404946a5a085068a1c403f.png
[2021022019323142.png]: https://img-blog.csdnimg.cn/2021022019323142.png
[20210220193314316.png]: https://img-blog.csdnimg.cn/20210220193314316.png
[2021022019323147.png]: https://img-blog.csdnimg.cn/2021022019323147.png
[2021022019323154.png]: /images/20221024/df436163be314b81b0e71868f7978064.png
[2021022019323150.png]: /images/20221024/9d393ebb518c4a81825a409b2f87dc7a.png
[20210220193231124.png]: /images/20221024/c08eac7b60ad423caa255ae79c6b9113.png
[20210220193409344.png]: https://img-blog.csdnimg.cn/20210220193409344.png
[20210220193437268.png]: https://img-blog.csdnimg.cn/20210220193437268.png
[20210220193409347.png]: /images/20221024/3eb305989c764d1db503ad6b3bbae1e1.png
[20210220193409350.png]: https://img-blog.csdnimg.cn/20210220193409350.png
[20210220193409352.png]: https://img-blog.csdnimg.cn/20210220193409352.png
[20210220193409356.png]: https://img-blog.csdnimg.cn/20210220193409356.png
[20210220193409359.png]: https://img-blog.csdnimg.cn/20210220193409359.png
[20210220193409357.png]: https://img-blog.csdnimg.cn/20210220193409357.png
[20210220193409368.png]: /images/20221024/3098c8eab5e347bca897e68b648244ac.png
[20210220193409369.png]: /images/20221024/158610e3ccb04e7399468da42397742c.png
[20210220193409370.png]: https://img-blog.csdnimg.cn/20210220193409370.png
[20210220193409375.png]: https://img-blog.csdnimg.cn/20210220193409375.png
[20210220193409378.png]: https://img-blog.csdnimg.cn/20210220193409378.png
[2021022019354810.png]: https://img-blog.csdnimg.cn/2021022019354810.png
[20210220193409379.png]: https://img-blog.csdnimg.cn/20210220193409379.png
[20210220193409380.png]: /images/20221024/6afde57e9f0c4d008372c3664c9a27de.png
[20210220193612945.png]: /images/20221024/51e9e931c0d44416b1ea2b16f14e6e57.png
[20210220193612942.png]: /images/20221024/c2ccc02f9bf340b786cc4906844cddbb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2N4eDY1NA_size_16_color_FFFFFF_t_70 1]: /images/20221024/02618e52240d4dd39714cea2cd1c89bc.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2N4eDY1NA_size_16_color_FFFFFF_t_70 2]: /images/20221024/74fbbe83bf404b29b657a54429e55ba4.png
[20210220193612974.png]: /images/20221024/198af9159f0a46269498f228461a7d5f.png
[2021022019370297.png]: /images/20221024/e9efd1cd7dad4a1985a262e509b243e2.png
[2021022019370296.png]: /images/20221024/211765330fe740988ecc9a5d0324efbf.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2N4eDY1NA_size_16_color_FFFFFF_t_70 3]: /images/20221024/e7fdbefe7e324f24b02469453e817887.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2N4eDY1NA_size_16_color_FFFFFF_t_70 4]: /images/20221024/f35f06dc34d2480a83ccaeeba570f1c9.png
[20210220193843433.png]: https://img-blog.csdnimg.cn/20210220193843433.png
[202102201937528.png]: https://img-blog.csdnimg.cn/202102201937528.png
[202102201937524.png]: https://img-blog.csdnimg.cn/202102201937524.png
[2021022019375240.png]: /images/20221024/dad30ecb6f374bd18365fe356164f657.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2N4eDY1NA_size_16_color_FFFFFF_t_70 5]: /images/20221024/12dece91034547cea4d68ccfaec76d9f.png
[20210220193930462.png]: /images/20221024/6cd32160bbd44e64b9f1d401974322b8.png
[20210220193930461.png]: /images/20221024/c1c08f294b1e489b903bd374180357e9.png
[20210220193930463.png]: /images/20221024/dedc456e86024508abbf4d22262efe44.png
[20210220193930471.png]: /images/20221024/cf6a02b9476b477487f728a9db7f47e6.png
[20210220193930472.png]: /images/20221024/0a7340b19e624332bb1084da096f3112.png
[20210220194149894.png]: /images/20221024/ee60ba3d266a4950a98ea583502dbefb.png
[20210220194050199.png]: /images/20221024/68f50f6865564d8d9dd500b62fe5ab4d.png
[20210220193930479.png]: /images/20221024/8c9d2ca8fd394d629d035384aeec6d17.png
[20210220193930473.png]: /images/20221024/e29b5a63327b4abba51b7d064bed8b9d.png
[20210220193930482.png]: /images/20221024/fdacbc0635ff494f870bb76ead8e8ae0.png
[20210220193930483.png]: /images/20221024/244d22db3ae4466cb0b104f54bcbf447.png
[20210220193930490.png]: https://img-blog.csdnimg.cn/20210220193930490.png
[20210220193930498.png]: https://img-blog.csdnimg.cn/20210220193930498.png
[20210220193930497.png]: https://img-blog.csdnimg.cn/20210220193930497.png
[20210220193930504.png]: https://img-blog.csdnimg.cn/20210220193930504.png
[20210220193930505.png]: https://img-blog.csdnimg.cn/20210220193930505.png
[20210220193930503.png]: /images/20221024/1afdeefc37f3453fa363f0bf926b3c19.png
[XGBoost]: https://www.zhihu.com/question/269929168
[XGBoost 1]: https://mp.weixin.qq.com/s/HDEKnIufbW8xQcOgHaXlZw
[GBDT _ XGBOOST]: https://www.zhihu.com/question/41354392/answer/98658997
[XGB]: https://zhuanlan.zhihu.com/p/139039073