XGBoost原理详解

Dear 丶 2022-05-10 15:00 438阅读 0赞

**（作者：陈玓玏）**

## 1.XGBoost基础 ##

XGBoost是时下集成学习中最火的算法，效率非常之高，它的基础是集成学习中的GBDT，但是在GBDT的基础上做了很多改进。本文是我在阅读xgboost论文、源码以及其他大神的精解之后做的笔记，如果有不足之处，烦请留言讨论，如果有什么疑惑，可以查阅论文或尝试单步跟踪源码，会理解得更深刻些。

首先讲一下我所理解的集成学习，集成学习是通过构建多个基分类器来提高预测的准确性，这些基分类器单个的预测能力并不会很强，但是会更多样，如bagging算法中每次构建基分类器是采用的是不同的样本，而随机森林是每次会使用不同的特征，构建多样化的决策树。GBDT和其他的算法都不太一样，因为其他算法每次都是去优化真实值的拟合，而GBDT的每个基分类器是拟合残差。

那么XGBoost是基于GBDT的，也就是说XGBoost的每课树也都是在拟合残差，它的预测结果不是样本的预测值。这么来理解，如果我们要预测一个人的年龄，假设他的真实年龄是50岁，那么第一棵树的残差空间是最大的，预测结果可能是40岁，那么第二棵可拟合的残差最大是10岁，但它可能能预测个5，也就是第二棵树预测完之后，这个人的年龄预测值为45，后面的以此类推。

# **2. XGBoost原理推导** #

**1. 目标函数定义：**  
 L ( ϕ ) = ∑ i l ( y i , y ^ i ) + ∑ k Ω ( f k ) ， 其 中 Ω ( f k ) = γ T + 1 2 λ ∣ ∣ w ∣ ∣ 2 L(\\phi)=\\sum\_i l(y\_i, \\hat y\_i) +\\sum\_\{k\}\\Omega(f\_k)，其中\\Omega(f\_k)=\\gamma T + \\frac12\\lambda||w||^2 L(ϕ)=i∑l(yi,y^i)\+k∑Ω(fk)，其中Ω(fk)=γT\+21λ∣∣w∣∣2

目标函数共分两大项，前一项是每个样本的损失和，XGBoost的损失函数是可以自定义的，并且其自带的损失函数也有很多种。第二项是正则项，包含两个部分，一个是对树进行制约，一个是对叶子节点进行制约，都能够避免过拟合。公式中 y ^ i \\hat y\_i y^i为预测输出， y i y\_i yi为label值（真实值）， f k f\_k fk为第 k k k树个模型， T T T为第 k k k棵树的叶子节点数，  w w w为第 k k k棵树的叶子节点权重值， γ \\gamma γ为叶子树惩罚正则项，具有前剪枝的作用，抑制节点向下的分裂， λ \\lambda λ为叶子权重惩罚正则项，在计算分割点的过程中计算增益时可以起到平滑的作用，这两个惩罚项都能防止过拟合。

**2.根据boosting算法对公式做转换：**  
由于在Boosting算法中，最后的预测值是多棵树输出的结果和，所以我们可以对预测值进行一个转换，变为T棵树的预测结果之和，公式如下：  
![在这里插入图片描述][70]  
  在这里 L ( t ) L^\{(t)\} L(t)表示第 t t t棵树的目标函数， y ^ i ( t − 1 ) \\hat\{y\}\_i^\{(t-1)\} y^i(t−1)是前 t − 1 t-1 t−1棵树的输出值之和，构成前 t − 1 t-1 t−1棵树的预测值， f t ( x i ) f\_t(x\_i) ft(xi)为第 t t t棵树的输出结果，两项相加构成最新的预测值。正则项相应地变为当前树的对应项。

**3.泰勒展开：**  
我们知道任何函数都能够被展开成一个多项式，xgboost在这里采用的是损失函数在 l ( y i , y ^ i ( t − 1 ) ) l(y\_i, \\hat\{y\}\_i^\{(t-1)\}) l(yi,y^i(t−1))处的二阶泰勒展开，将用到损失函数的一阶导数和二阶导数，所以目标函数可以进一步约等于以下这个式子：  
![在这里插入图片描述][70 1]  
式子中 g i = ∂ y ^ i ( t − 1 ) &ThickSpace; l ( y i , y ^ i ( t − 1 ) ) g\_i=\\partial\_\{\\hat\{y\}\_i^\{(t-1)\}\}\\;l(y\_i, \\hat\{y\}\_i^\{(t-1)\}) gi=∂y^i(t−1)l(yi,y^i(t−1))，是前一棵树损失函数的一阶导数， h i = ∂ y ^ i ( t − 1 ) 2 &ThickSpace; l ( y i , y ^ i ( t − 1 ) ) h\_i=\\partial\_\{\\hat\{y\}\_i^\{(t-1)\}\}^2 \\; l(y\_i, \\hat\{y\}\_i^\{(t-1)\}) hi=∂y^i(t−1)2l(yi,y^i(t−1))，是前一棵树损失函数的二阶导数。

**4.忽略常数项：**  
从上面泰勒展开后的例子我们可以看出，函数的第一部分 ∑ i = 1 n \[ l ( y i , y ^ i ( t − 1 ) ) \\sum\\limits\_\{i=1\}^n \[l(y\_i, \\hat\{y\}\_i^\{(t-1)\}) i=1∑n\[l(yi,y^i(t−1))是上一轮建树的损失函数，在本轮建树的过程中，它是一个已知的常量，并不会对我们本轮的建树过程有任何影响，因此我们可以把它忽略掉，从而将目标函数简化为以下形式：  
![!\[在这里插入图片描述\](https://img-blog.csdn.net/20181020114440584?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc1MDA4NA==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70][https_img-blog.csdn.net_20181020114440584_watermark_2_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc1MDA4NA_font_5a6L5L2T_fontsize_400_fill_I0JBQkFCMA_dissolve_70]

**5.根据样本所属的叶子节点进行合并：**  
对于每一棵树而言，最终的每一个样本都会落入某个叶子节点，而这个叶子节点的权重将作为其拟合的残差值，因此对于以上的式子，我们可以将对每个样本求和转换为对叶子节点的结果求和，从而更好地理解建树的过程。首先假设树有 T T T个叶子节点，落入叶子节点j的样本集合表示为 I j = \{ i ∣ q ( x i ) = j \} I\_j=\\\{i |q(x\_i)=j\\\} Ij=\{ i∣q(xi)=j\}，意思是对于树结构 q q q，落入其叶子节点 j j j的样本序号集合为 I j I\_j Ij。有了这个结果，我们可以将 ∑ i = 1 n g i f t ( x i ) \\sum\\limits\_\{i=1\}^n g\_if\_t(x\_i) i=1∑ngift(xi)转化为 ∑ j = 1 T ( ∑ i ∈ I j g i ) w j \\sum\\limits\_\{j=1\}^\{T\} (\\sum\\limits\_\{i\\in I\_j\}g\_i)w\_j j=1∑T(i∈Ij∑gi)wj， ∑ i ∈ I j g i \\sum\\limits\_\{i\\in I\_j\}g\_i i∈Ij∑gi为落入叶子节点 j j j的所有样本对应的一阶导数之和。相应地， ∑ i = 1 n 1 2 h t f t 2 ( x i ) \\sum\\limits\_\{i=1\}^n \\frac12h\_tf\_t^2(x\_i) i=1∑n21htft2(xi)也可以转换为 ∑ j = 1 T 1 2 ∑ i ∈ I j h i w j 2 \\sum\\limits\_\{j=1\}^\{T\}\\frac\{1\}\{2\}\\sum\\limits\_\{i\\in I\_j\}h\_iw\_j^2 j=1∑T21i∈Ij∑hiwj2。因此，经过转换以及合并正则项后，式子转换成以下形式：  
![在这里插入图片描述][70 2]

**6.求解叶子节点权重：**  
既然我们已经得到了一个解释性很强的目标函数，并且我们知道要取其极值，在树的结构确定的情况下，我们可以通过令其一阶导数为0来求解权重，求解结果如下：  
![在这里插入图片描述][70 3]  
**7.代入权重，更新目标函数：**  
将求得的权重菜如目标函数，我们得到以下结果：  
![在这里插入图片描述][70 4]  
这个结果可以作为树结构的打分函数。

**8.计算分割点：**  
前七个步骤都是建立在树结构已知的基础上所做的推导，那么xgboost具体的建树过程和决策树是类似的，只不过它在计算增益时，使用的不是熵，而是以上求得的目标函数，选中分割点之后，将所有需要进行分簇的样本分别划入左子树和右子树，并求左子树和右子树的目标函数之和，减去分裂前的目标函数之和，即为分割点的增益，选择增益最高的点作为分割点，计算公式如下：  
![在这里插入图片描述][70 5]  
更简单地说，当分割后损失函数减小的值大于 γ \\gamma γ时，我们就可以进行分裂，这就是xgboost调参时的gamma参数，而 λ \\lambda λ参数在计算增益时加在分母上，可以起到平滑的作用，但是因为xgboost有了gamma参数和min\_child\_weight参数做前剪枝，所以调整lambda参数来防止过拟合就变为可选项，而不是必选项。

**9.分位数算法高效搜索分割点：**  
这部分内容较多，在论文中的附录部分有说明，也可以看这篇文章：[https://blog.csdn.net/weixin\_39750084/article/details/83216127][https_blog.csdn.net_weixin_39750084_article_details_83216127]

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

# **参考资料** #

1.  陈天奇XGBoost论文：[https://arxiv.org/pdf/1603.02754.pdf][https_arxiv.org_pdf_1603.02754.pdf]
2.  [https://blog.csdn.net/matrix\_zzl/article/details/78635221][https_blog.csdn.net_matrix_zzl_article_details_78635221]
3.  [https://blog.csdn.net/a358463121/article/details/68617389][https_blog.csdn.net_a358463121_article_details_68617389]

[70]: /images/20220505/ec401d8b7f974cc790a78f7f921b6cb7.png
[70 1]: /images/20220505/e033910295384cdf9f5aabe009a48c27.png
[https_img-blog.csdn.net_20181020114440584_watermark_2_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc1MDA4NA_font_5a6L5L2T_fontsize_400_fill_I0JBQkFCMA_dissolve_70]: /images/20220505/f2f7a69cd1c948f0bf554df5ebd70ae2.png
[70 2]: /images/20220505/2a507d5f39614d8099b151c093a87ae5.png
[70 3]: /images/20220505/3b0b04e083124b7b801bbb868d43acfb.png
[70 4]: /images/20220505/0cc177122e65436793e508284dcbb5a9.png
[70 5]: /images/20220505/05eb552ba1a34f8aa8089aab306d4f65.png
[https_blog.csdn.net_weixin_39750084_article_details_83216127]: https://blog.csdn.net/weixin_39750084/article/details/83216127
[https_arxiv.org_pdf_1603.02754.pdf]: https://arxiv.org/pdf/1603.02754.pdf
[https_blog.csdn.net_matrix_zzl_article_details_78635221]: https://blog.csdn.net/matrix_zzl/article/details/78635221
[https_blog.csdn.net_a358463121_article_details_68617389]: https://blog.csdn.net/a358463121/article/details/68617389