xgboost陈天奇_xgboost介绍

冷不防 2023-01-12 10:27 393阅读 0赞

xgboost是华盛顿大学博士陈天奇创造的一个梯度提升（Gradient Boosting）的开源框架。至今可以算是各种数据比赛中的大杀器，被大家广泛地运用。接下来，就简单介绍一下xgboost和普通的GBDT相比，有什么不同。(何为Gradient Boosting, GBDT请看我上篇文章)

## 1. 梯度下降 ##

在GBDT中，我们每次生成下一个弱学习器，都是把损失函数的梯度作为学习目标，相当于利用梯度下降法进行优化来逼近损失函数的最小值，也就是使得损失函数为0，最终学习器尽可能接近真实结果。

![equation?tex=F\_n%28x%29%3D%5Csum\_%7Bi%3D1%7D%5En+f\_i%28x%29][equation_tex_F_n_28x_29_3D_5Csum_7Bi_3D1_7D_5En_f_i_28x_29]

![equation?tex=F\_n%28x%29+%3D+F\_%7Bn-1%7D%28x%29+%2Bf\_n%28x%29+%3D+F\_%7Bn-1%7D%28x%29+-+%5Cnabla+L%28F\_%7Bn-1%7D%28x%29%29][equation_tex_F_n_28x_29_3D_F_7Bn-1_7D_28x_29_2Bf_n_28x_29_3D_F_7Bn-1_7D_28x_29_-_5Cnabla_L_28F_7Bn-1_7D_28x_29_29]

而xgboost中，我们则是把损失函数的二阶泰勒展开的差值作为学习目标，相当于利用牛顿法进行优化，来逼近损失函数的最小值，也就是使得损失函数为0。

![equation?tex=F\_n%28x%29%3D%5Csum\_%7Bi%3D1%7D%5En+f\_i%28x%29][equation_tex_F_n_28x_29_3D_5Csum_7Bi_3D1_7D_5En_f_i_28x_29]

![equation?tex=F\_n%28x%29+%3D+F\_%7Bn-1%7D%28x%29+%2Bf\_n%28x%29+%3D+F\_%7Bn-1%7D%28x%29+-%5Cfrac+%7BL%27%28F\_%7Bn-1%7D%28x%29%29%7D+%7BL%27%27%28F\_%7Bn-1%7D%28x%29%29%7D][equation_tex_F_n_28x_29_3D_F_7Bn-1_7D_28x_29_2Bf_n_28x_29_3D_F_7Bn-1_7D_28x_29_-_5Cfrac_7BL_27_28F_7Bn-1_7D_28x_29_29_7D_7BL_27_27_28F_7Bn-1_7D_28x_29_29_7D]

那为什么可以这么逼近呢？这就涉及到泰勒展开：

![equation?tex=L%28x%29%3DL%28x\_0%29%2BL%27%28x\_0%29%28x-x\_0%29%2BL%27%27%28x\_0%29%5Cfrac%7B%28x-x\_0%29%5E2%7D%7B2%7D%2BO%5B%28x-x\_0%29%5E2%5D][equation_tex_L_28x_29_3DL_28x_0_29_2BL_27_28x_0_29_28x-x_0_29_2BL_27_27_28x_0_29_5Cfrac_7B_28x-x_0_29_5E2_7D_7B2_7D_2BO_5B_28x-x_0_29_5E2_5D]

梯度下降法就是用一阶泰勒展开来近似函数：

![equation?tex=L%28x%29%5Capprox+L%28x\_0%29%2BL%27%28x\_0%29%28x-x\_0%29][equation_tex_L_28x_29_5Capprox_L_28x_0_29_2BL_27_28x_0_29_28x-x_0_29]

而牛顿法则是用二阶泰勒展开来近似函数：

![equation?tex=L%28x%29%5Capprox+L%28x\_0%29%2BL%27%28x\_0%29%28x-x\_0%29%2BL%27%27%28x\_0%29%5Cfrac%7B%28x-x\_0%29%5E2%7D%7B2%7D][equation_tex_L_28x_29_5Capprox_L_28x_0_29_2BL_27_28x_0_29_28x-x_0_29_2BL_27_27_28x_0_29_5Cfrac_7B_28x-x_0_29_5E2_7D_7B2_7D]

![equation?tex=L%27%28x%29%5Capprox+L%27%28x\_0%29%2BL%27%27%28x\_0%29%28x-x\_0%29][equation_tex_L_27_28x_29_5Capprox_L_27_28x_0_29_2BL_27_27_28x_0_29_28x-x_0_29]

![equation?tex=x%3Dx\_0%2B%5Cfrac%7BL%27%28x\_0%29%7D%7BL%27%27%28x\_0%29%7D][equation_tex_x_3Dx_0_2B_5Cfrac_7BL_27_28x_0_29_7D_7BL_27_27_28x_0_29_7D]

之后具体的迭代收敛原理请看最优化方法。

## 2. 正则项 ##

正则项是为了防止模型过拟合。于是，一般的损失函数

![equation?tex=L%28x%29][equation_tex_L_28x_29] 就变成了目标函数

![equation?tex=L%28x%29%2B%5COmega%28x%29][equation_tex_L_28x_29_2B_5COmega_28x_29] 。这样，随着树的复杂度增大，对应的目标函数也就变大，这样就有效防止了过拟合。叶子节点个数(T)，叶节点分数(w)

![equation?tex=%5COmega%3D%5Cgamma+T%2B%5Cfrac%7B1%7D%7B2%7D%5Clambda%5Csum\_%7Bj%3D1%7D%5ET+w\_j%5E2][equation_tex_5COmega_3D_5Cgamma_T_2B_5Cfrac_7B1_7D_7B2_7D_5Clambda_5Csum_7Bj_3D1_7D_5ET_w_j_5E2]

对叶子节点个数进行惩罚，相当于在训练过程中做了剪枝。

将xgboost的目标函数进行化简，并把

![equation?tex=f%28x%29%3Dw\_q%28x%29][equation_tex_f_28x_29_3Dw_q_28x_29] 决策树和

![equation?tex=%5COmega%3D%5Cgamma+T%2B%5Cfrac%7B1%7D%7B2%7D%5Clambda%5Csum\_%7Bj%3D1%7D%5ET+w\_j%5E2][equation_tex_5COmega_3D_5Cgamma_T_2B_5Cfrac_7B1_7D_7B2_7D_5Clambda_5Csum_7Bj_3D1_7D_5ET_w_j_5E2] 代入：

![equation?tex=%5Cmathcal%7BL%7D%5E%7B%28t%29%7D%3D%5Csum\_%7Bi%3D1%7D%5En+l%5Cleft%28y\_%7Bi%7D%2C+%5Chat%7By%7D\_%7Bi%7D%5E%7B%28t-1%29%7D%2Bf\_%7Bt%7D%5Cleft%28%5Cmathbf%7Bx%7D\_%7Bi%7D%5Cright%29%5Cright%29%2B%5COmega%5Cleft%28f\_%7Bt%7D%5Cright%29][equation_tex_5Cmathcal_7BL_7D_5E_7B_28t_29_7D_3D_5Csum_7Bi_3D1_7D_5En_l_5Cleft_28y_7Bi_7D_2C_5Chat_7By_7D_7Bi_7D_5E_7B_28t-1_29_7D_2Bf_7Bt_7D_5Cleft_28_5Cmathbf_7Bx_7D_7Bi_7D_5Cright_29_5Cright_29_2B_5COmega_5Cleft_28f_7Bt_7D_5Cright_29]

![equation?tex=%5Cbegin%7Baligned%7D+%5Ctilde%7B%5Cmathcal%7BL%7D%7D%5E%7B%28t%29%7D%26%3D%5Csum\_%7Bi%3D1%7D%5E%7Bn%7D%5Cleft%5Bg\_%7Bi%7D+f\_%7Bt%7D%5Cleft%28%5Cmathbf%7Bx%7D\_%7Bi%7D%5Cright%29%2B%5Cfrac%7B1%7D%7B2%7D+h\_%7Bi%7D+f\_%7Bt%7D%5E%7B2%7D%5Cleft%28%5Cmathbf%7Bx%7D\_%7Bi%7D%5Cright%29%5Cright%5D%2B%5COmega%5Cleft%28f\_%7Bt%7D%5Cright%29%5C%5C+%26%3D%5Csum\_%7Bj%3D1%7D%5E%7BT%7D%5Cleft%5B%5Cleft%28%5Csum\_%7Bi+%5Cin+I\_%7Bj%7D%7D+g\_%7Bi%7D%5Cright%29+w\_%7Bj%7D%2B%5Cfrac%7B1%7D%7B2%7D%5Cleft%28%5Csum\_%7Bi+%5Cin+I\_%7Bj%7D%7D+h\_%7Bi%7D%2B%5Clambda%5Cright%29+w\_%7Bj%7D%5E%7B2%7D%5Cright%5D%2B%5Cgamma+T+%5C%5C+%26%3D%5Csum\_%7Bj%3D1%7D%5E%7BT%7D%5Cleft%5BG\_%7Bj%7D+w\_%7Bj%7D%2B%5Cfrac%7B1%7D%7B2%7D%5Cleft%28H\_%7Bj%7D%2B%5Clambda%5Cright%29+w\_%7Bj%7D%5E%7B2%7D%5Cright%5D%2B%5Cgamma+T+%5Cend%7Baligned%7D][equation_tex_5Cbegin_7Baligned_7D_5Ctilde_7B_5Cmathcal_7BL_7D_7D_5E_7B_28t_29_7D_26_3D_5Csum_7Bi_3D1_7D_5E_7Bn_7D_5Cleft_5Bg_7Bi_7D_f_7Bt_7D_5Cleft_28_5Cmathbf_7Bx_7D_7Bi_7D_5Cright_29_2B_5Cfrac_7B1_7D_7B2_7D_h_7Bi_7D_f_7Bt_7D_5E_7B2_7D_5Cleft_28_5Cmathbf_7Bx_7D_7Bi_7D_5Cright_29_5Cright_5D_2B_5COmega_5Cleft_28f_7Bt_7D_5Cright_29_5C_5C_26_3D_5Csum_7Bj_3D1_7D_5E_7BT_7D_5Cleft_5B_5Cleft_28_5Csum_7Bi_5Cin_I_7Bj_7D_7D_g_7Bi_7D_5Cright_29_w_7Bj_7D_2B_5Cfrac_7B1_7D_7B2_7D_5Cleft_28_5Csum_7Bi_5Cin_I_7Bj_7D_7D_h_7Bi_7D_2B_5Clambda_5Cright_29_w_7Bj_7D_5E_7B2_7D_5Cright_5D_2B_5Cgamma_T_5C_5C_26_3D_5Csum_7Bj_3D1_7D_5E_7BT_7D_5Cleft_5BG_7Bj_7D_w_7Bj_7D_2B_5Cfrac_7B1_7D_7B2_7D_5Cleft_28H_7Bj_7D_2B_5Clambda_5Cright_29_w_7Bj_7D_5E_7B2_7D_5Cright_5D_2B_5Cgamma_T_5Cend_7Baligned_7D]

令 其导数为0，解得每个叶节点的最优预测分数为：

![equation?tex=w\_%7Bj%7D%5E%7B%2A%7D%3D-%5Cfrac%7BG\_%7Bj%7D%7D%7BH\_%7Bj%7D%2B%5Clambda%7D][equation_tex_w_7Bj_7D_5E_7B_2A_7D_3D-_5Cfrac_7BG_7Bj_7D_7D_7BH_7Bj_7D_2B_5Clambda_7D]

代入目标函数，得到最小损失为：

![equation?tex=%5Ctilde+L%5E%2A%3D-%5Cfrac%7B1%7D%7B2%7D%5Csum\_%7Bj%3D1%7D%5ET%5Cfrac%7BG\_j%5E2%7D%7BH\_j%2B%5Clambda%7D%2B%5Cgamma+T][equation_tex_5Ctilde_L_5E_2A_3D-_5Cfrac_7B1_7D_7B2_7D_5Csum_7Bj_3D1_7D_5ET_5Cfrac_7BG_j_5E2_7D_7BH_j_2B_5Clambda_7D_2B_5Cgamma_T]

## 3. 树节点分裂方法 ##

精确算法：遍历所有特征的所有可能分割点，来寻找使目标函数最小的分割点。

近似算法：对于每个特征，只考察分位点，减少计算复杂度。

而XGBoost不是简单地按照样本个数进行分位，而是以二阶导数值作为权重(Weighted Quantile Sketch)，比如:

![c4e8a901473aff3b042fe4edee6504b3.png][]

## 4. 其他特征 ##

1.  shrinkage（收缩）方法：相当于学习系数eta。对每颗子树都要乘上该系数，防止过拟合。
2.  列采样：对特征进行降采样，灵感来源于随机森林，除了能降低计算量外，还能防止过拟合。
3.  行采样：
4.  缺失值处理：通过枚举所有缺失值在当前节点是进入左子树，还是进入右子树更优来决定一个处理缺失值默认的方向。
5.  xgboost工具支持并行。一般决策树中，我们需要每次都对特征的值进行排序，来寻找分割点，极其费时。xgboost中，我们先对每个特征进行分块（block）并排序，使得在寻找最佳分裂点的时候能够并行化计算。这个结构加速了split finding的过程，只需要在建树前排序一次，后面节点分裂时直接根据索引得到梯度信息。这是xgboost比一般GBDT更快的一个重要原因。
6.  out-of-core, cache-aware优化内存等方法来加速计算。

**参考资料：**

知乎上有关问题的回答 https://www.zhihu.com/question/41354392

一个很详细的PPT http://wepon.me/files/gbdt.pdf

陈天奇原版论文 https://arxiv.org/pdf/1603.02754.pdf

[equation_tex_F_n_28x_29_3D_5Csum_7Bi_3D1_7D_5En_f_i_28x_29]: https://www.zhihu.com/equation?tex=F_n%28x%29%3D%5Csum_%7Bi%3D1%7D%5En+f_i%28x%29
[equation_tex_F_n_28x_29_3D_F_7Bn-1_7D_28x_29_2Bf_n_28x_29_3D_F_7Bn-1_7D_28x_29_-_5Cnabla_L_28F_7Bn-1_7D_28x_29_29]: https://www.zhihu.com/equation?tex=F_n%28x%29+%3D+F_%7Bn-1%7D%28x%29+%2Bf_n%28x%29+%3D+F_%7Bn-1%7D%28x%29+-+%5Cnabla+L%28F_%7Bn-1%7D%28x%29%29
[equation_tex_F_n_28x_29_3D_F_7Bn-1_7D_28x_29_2Bf_n_28x_29_3D_F_7Bn-1_7D_28x_29_-_5Cfrac_7BL_27_28F_7Bn-1_7D_28x_29_29_7D_7BL_27_27_28F_7Bn-1_7D_28x_29_29_7D]: https://www.zhihu.com/equation?tex=F_n%28x%29+%3D+F_%7Bn-1%7D%28x%29+%2Bf_n%28x%29+%3D+F_%7Bn-1%7D%28x%29+-%5Cfrac+%7BL%27%28F_%7Bn-1%7D%28x%29%29%7D+%7BL%27%27%28F_%7Bn-1%7D%28x%29%29%7D
[equation_tex_L_28x_29_3DL_28x_0_29_2BL_27_28x_0_29_28x-x_0_29_2BL_27_27_28x_0_29_5Cfrac_7B_28x-x_0_29_5E2_7D_7B2_7D_2BO_5B_28x-x_0_29_5E2_5D]: /images/20221119/812bb16e20854809831628813232471a.png
[equation_tex_L_28x_29_5Capprox_L_28x_0_29_2BL_27_28x_0_29_28x-x_0_29]: /images/20221119/17bae331c95145d388cc44a968dcf7eb.png%5Capprox+L%28x_0%29%2BL%27%28x_0%29%28x-x_0%29
[equation_tex_L_28x_29_5Capprox_L_28x_0_29_2BL_27_28x_0_29_28x-x_0_29_2BL_27_27_28x_0_29_5Cfrac_7B_28x-x_0_29_5E2_7D_7B2_7D]: /images/20221119/17bae331c95145d388cc44a968dcf7eb.png%5Capprox+L%28x_0%29%2BL%27%28x_0%29%28x-x_0%29%2BL%27%27%28x_0%29%5Cfrac%7B%28x-x_0%29%5E2%7D%7B2%7D
[equation_tex_L_27_28x_29_5Capprox_L_27_28x_0_29_2BL_27_27_28x_0_29_28x-x_0_29]: https://www.zhihu.com/equation?tex=L%27%28x%29%5Capprox+L%27%28x_0%29%2BL%27%27%28x_0%29%28x-x_0%29
[equation_tex_x_3Dx_0_2B_5Cfrac_7BL_27_28x_0_29_7D_7BL_27_27_28x_0_29_7D]: /images/20221119/be8ecf8d10dc4ca9ad1d07e23fe7323a.png
[equation_tex_L_28x_29]: /images/20221119/17bae331c95145d388cc44a968dcf7eb.png
[equation_tex_L_28x_29_2B_5COmega_28x_29]: /images/20221119/17bae331c95145d388cc44a968dcf7eb.png%2B%5COmega%28x%29
[equation_tex_5COmega_3D_5Cgamma_T_2B_5Cfrac_7B1_7D_7B2_7D_5Clambda_5Csum_7Bj_3D1_7D_5ET_w_j_5E2]: https://www.zhihu.com/equation?tex=%5COmega%3D%5Cgamma+T%2B%5Cfrac%7B1%7D%7B2%7D%5Clambda%5Csum_%7Bj%3D1%7D%5ET+w_j%5E2
[equation_tex_f_28x_29_3Dw_q_28x_29]: /images/20221119/b1c2af563554419eb2d3f2a307e34f2e.png
[equation_tex_5Cmathcal_7BL_7D_5E_7B_28t_29_7D_3D_5Csum_7Bi_3D1_7D_5En_l_5Cleft_28y_7Bi_7D_2C_5Chat_7By_7D_7Bi_7D_5E_7B_28t-1_29_7D_2Bf_7Bt_7D_5Cleft_28_5Cmathbf_7Bx_7D_7Bi_7D_5Cright_29_5Cright_29_2B_5COmega_5Cleft_28f_7Bt_7D_5Cright_29]: https://www.zhihu.com/equation?tex=%5Cmathcal%7BL%7D%5E%7B%28t%29%7D%3D%5Csum_%7Bi%3D1%7D%5En+l%5Cleft%28y_%7Bi%7D%2C+%5Chat%7By%7D_%7Bi%7D%5E%7B%28t-1%29%7D%2Bf_%7Bt%7D%5Cleft%28%5Cmathbf%7Bx%7D_%7Bi%7D%5Cright%29%5Cright%29%2B%5COmega%5Cleft%28f_%7Bt%7D%5Cright%29
[equation_tex_5Cbegin_7Baligned_7D_5Ctilde_7B_5Cmathcal_7BL_7D_7D_5E_7B_28t_29_7D_26_3D_5Csum_7Bi_3D1_7D_5E_7Bn_7D_5Cleft_5Bg_7Bi_7D_f_7Bt_7D_5Cleft_28_5Cmathbf_7Bx_7D_7Bi_7D_5Cright_29_2B_5Cfrac_7B1_7D_7B2_7D_h_7Bi_7D_f_7Bt_7D_5E_7B2_7D_5Cleft_28_5Cmathbf_7Bx_7D_7Bi_7D_5Cright_29_5Cright_5D_2B_5COmega_5Cleft_28f_7Bt_7D_5Cright_29_5C_5C_26_3D_5Csum_7Bj_3D1_7D_5E_7BT_7D_5Cleft_5B_5Cleft_28_5Csum_7Bi_5Cin_I_7Bj_7D_7D_g_7Bi_7D_5Cright_29_w_7Bj_7D_2B_5Cfrac_7B1_7D_7B2_7D_5Cleft_28_5Csum_7Bi_5Cin_I_7Bj_7D_7D_h_7Bi_7D_2B_5Clambda_5Cright_29_w_7Bj_7D_5E_7B2_7D_5Cright_5D_2B_5Cgamma_T_5C_5C_26_3D_5Csum_7Bj_3D1_7D_5E_7BT_7D_5Cleft_5BG_7Bj_7D_w_7Bj_7D_2B_5Cfrac_7B1_7D_7B2_7D_5Cleft_28H_7Bj_7D_2B_5Clambda_5Cright_29_w_7Bj_7D_5E_7B2_7D_5Cright_5D_2B_5Cgamma_T_5Cend_7Baligned_7D]: https://www.zhihu.com/equation?tex=%5Cbegin%7Baligned%7D+%5Ctilde%7B%5Cmathcal%7BL%7D%7D%5E%7B%28t%29%7D%26%3D%5Csum_%7Bi%3D1%7D%5E%7Bn%7D%5Cleft%5Bg_%7Bi%7D+f_%7Bt%7D%5Cleft%28%5Cmathbf%7Bx%7D_%7Bi%7D%5Cright%29%2B%5Cfrac%7B1%7D%7B2%7D+h_%7Bi%7D+f_%7Bt%7D%5E%7B2%7D%5Cleft%28%5Cmathbf%7Bx%7D_%7Bi%7D%5Cright%29%5Cright%5D%2B%5COmega%5Cleft%28f_%7Bt%7D%5Cright%29%5C%5C+%26%3D%5Csum_%7Bj%3D1%7D%5E%7BT%7D%5Cleft%5B%5Cleft%28%5Csum_%7Bi+%5Cin+I_%7Bj%7D%7D+g_%7Bi%7D%5Cright%29+w_%7Bj%7D%2B%5Cfrac%7B1%7D%7B2%7D%5Cleft%28%5Csum_%7Bi+%5Cin+I_%7Bj%7D%7D+h_%7Bi%7D%2B%5Clambda%5Cright%29+w_%7Bj%7D%5E%7B2%7D%5Cright%5D%2B%5Cgamma+T+%5C%5C+%26%3D%5Csum_%7Bj%3D1%7D%5E%7BT%7D%5Cleft%5BG_%7Bj%7D+w_%7Bj%7D%2B%5Cfrac%7B1%7D%7B2%7D%5Cleft%28H_%7Bj%7D%2B%5Clambda%5Cright%29+w_%7Bj%7D%5E%7B2%7D%5Cright%5D%2B%5Cgamma+T+%5Cend%7Baligned%7D
[equation_tex_w_7Bj_7D_5E_7B_2A_7D_3D-_5Cfrac_7BG_7Bj_7D_7D_7BH_7Bj_7D_2B_5Clambda_7D]: /images/20221119/ad38cb8517124ecab2b61549d085e3b8.png
[equation_tex_5Ctilde_L_5E_2A_3D-_5Cfrac_7B1_7D_7B2_7D_5Csum_7Bj_3D1_7D_5ET_5Cfrac_7BG_j_5E2_7D_7BH_j_2B_5Clambda_7D_2B_5Cgamma_T]: https://www.zhihu.com/equation?tex=%5Ctilde+L%5E%2A%3D-%5Cfrac%7B1%7D%7B2%7D%5Csum_%7Bj%3D1%7D%5ET%5Cfrac%7BG_j%5E2%7D%7BH_j%2B%5Clambda%7D%2B%5Cgamma+T
[c4e8a901473aff3b042fe4edee6504b3.png]: /images/20221119/f3362a998fce442682a9bac3d2ac35c6.png