XGBoost详解+问题思考

约定不等于承诺〃 2021-12-08 16:17 377阅读 0赞

### 前言 ###

2014年，陈天奇博士提出了XGBoost算法，它可认为是在GBDT算法基础上的进一步优化。XGBoost(eXtreme Gradient Boosting)算法是Gradient Boosting算法的高效实现版本，因其在应用实践中表现出优良的效果和效率，因而也被工业界广为推崇。算法上的优化有：

*  1、引入了正则项，控制减少训练过程当中的过拟合
 *  2、XGBoost算法不仅使用一阶导数计算伪残差，还计算二阶导数可近似快速剪枝的构建新的基学习器
 *  3、对比GBDT只支持决策树，XGBoost可以支持很多其他的弱学习器

工程上的优化有：

*  1、支持并行计算
 *  2、提高计算效率
 *  3、处理稀疏训练数据

### XGBoost损失函数 ###

这里首先要讲解的就是一个一直令人很诧异的问题：怎么切割样本点？怎么得到分裂后子树的预测值？这个问题大家可以先去谅解一下这两篇博客：[梯度提升树（GBDT）的问题思考][GBDT]、[全方面讲解提升树及问题思考 - 统计学习基础][-]。  
在GBDT算法中，它是分两步：求出最优的所有J个叶子节点区域，再求出每个叶子节点区域的最优解。对于XGBoost，它期望把这两步合并在一起做，即一次求解出决策树最优的所有J个叶子节点区域和每个叶子节点区域的最优解 c t j c\_\{tj\} ctj。我们来看下它是如何求解的，首先看下损失函数：  
 L t = ∑ i = 1 m L ( y i , f t − 1 ( x i ) + h t ( x i ) ) + Ω ( h t ) Ω ( h t ) = γ J + λ 2 ∑ j = 1 J w t j 2 L\_t=\\sum\_\{i=1\}^\{m\}L(y\_i,f\_\{t-1\}(x\_i)+h\_t(x\_i))+\\Omega(h\_t) \\\\ \\Omega(h\_t)=\\gamma J+\\frac\{\\lambda\}\{2\}\\sum\_\{j=1\}^\{J\}\{w\_\{tj\}\}^2 Lt=i=1∑mL(yi,ft−1(xi)\+ht(xi))\+Ω(ht)Ω(ht)=γJ\+2λj=1∑Jwtj2  
这个公式有一个累加误差的过程， m m m表示样本个数。公式 Ω ( h t ) \\Omega(h\_t) Ω(ht)是一个正则化因子， J J J表示叶子区域个数， w t j w\_\{tj\} wtj表示就是叶子区域预测值，跟GBDT中的 c t j c\_\{tj\} ctj是一个意思，只不过在XGBoost用 w t j w\_\{tj\} wtj表示。提出损失函数的目的就是求得使损失函数最小的叶子区域及预测值 w t j w\_\{tj\} wtj，这里XGBoost没有和GBDT一样去拟合泰勒展开式的一阶导数，而是期望直接基于损失函数的二阶泰勒展开式来求解。现在我们来看看这个损失函数的二阶泰勒展开式：  
 L t = ∑ i = 1 m L ( y i , f t − 1 ( x i ) + h t ( x i ) ) + γ J + λ 2 ∑ j = 1 J w t j 2 = ∑ i = 1 m \[ L ( y i , f t − 1 ( x i ) ) + L ′ ( y i , f t − 1 ( x i ) ) h t ( x i ) + 1 2 L ′ ′ ( y i , f t − 1 ( x i ) ) h t ( x i ) 2 \] + γ J + λ 2 ∑ j = 1 J w t j 2 \\begin\{aligned\} L\_t &=\\sum\_\{i=1\}^\{m\}L(y\_i,f\_\{t-1\}(x\_i)+h\_t(x\_i))+\\gamma J+\\frac\{\\lambda\}\{2\}\\sum\_\{j=1\}^\{J\}\{w\_\{tj\}\}^2 \\\\ &=\\sum\_\{i=1\}^\{m\} \\bigg \[L(y\_i,f\_\{t-1\}(x\_i))+L^\{&\#x27;\}(y\_i,f\_\{t-1\}(x\_i))h\_t(x\_i)+\\frac\{1\}\{2\}L^\{&\#x27;&\#x27;\}(y\_i,f\_\{t-1\}(x\_i))h\_t(x\_i)^2 \\bigg \]+\\gamma J+\\frac\{\\lambda\}\{2\}\\sum\_\{j=1\}^\{J\}\{w\_\{tj\}\}^2 \\end\{aligned\} Lt=i=1∑mL(yi,ft−1(xi)\+ht(xi))\+γJ\+2λj=1∑Jwtj2=i=1∑m\[L(yi,ft−1(xi))\+L′(yi,ft−1(xi))ht(xi)\+21L′′(yi,ft−1(xi))ht(xi)2\]\+γJ\+2λj=1∑Jwtj2  
其中 L ′ ( y i , f t − 1 ( x i ) ) L^\{&\#x27;\}(y\_i,f\_\{t-1\}(x\_i)) L′(yi,ft−1(xi))、 L ′ ′ ( y i , f t − 1 ( x i ) ) L^\{&\#x27;&\#x27;\}(y\_i,f\_\{t-1\}(x\_i)) L′′(yi,ft−1(xi))分别是损失函数对 f t − 1 ( x i ) f\_\{t-1\}(x\_i) ft−1(xi)的一阶导、二阶导，记做：  
 g t i = L ′ ( y i , f t − 1 ( x i ) ) h t i = L ′ ′ ( y i , f t − 1 ( x i ) ) g\_\{ti\} = L^\{&\#x27;\}(y\_i,f\_\{t-1\}(x\_i)) \\qquad h\_\{ti\}=L^\{&\#x27;&\#x27;\}(y\_i,f\_\{t-1\}(x\_i)) gti=L′(yi,ft−1(xi))hti=L′′(yi,ft−1(xi))  
简化公式为：  
 L t = ∑ i = 1 m \[ L ( y i , f t − 1 ( x i ) ) + g t i h t ( x i ) + 1 2 h t i h t ( x i ) 2 \] + γ J + λ 2 ∑ j = 1 J w t j 2 L\_t = \\sum\_\{i=1\}^\{m\} \\bigg \[L(y\_i,f\_\{t-1\}(x\_i))+g\_\{ti\}h\_t(x\_i)+\\frac\{1\}\{2\}h\_\{ti\}h\_t(x\_i)^2 \\bigg \]+\\gamma J+\\frac\{\\lambda\}\{2\}\\sum\_\{j=1\}^\{J\}\{w\_\{tj\}\}^2 Lt=i=1∑m\[L(yi,ft−1(xi))\+gtiht(xi)\+21htiht(xi)2\]\+γJ\+2λj=1∑Jwtj2  
我们再来思考，L(y\_i,f\_\{t-1\}(x\_i))是一个常数，表示上一课树的损失函数值， h t ( x i ) h\_t(x\_i) ht(xi)是一个子树区域的预测值，其实也就是 w t j w\_\{tj\} wtj，把 m m m个样本化成 J J J个样本子树区域，于是损失函数表示为：  
 L t = ∑ i = 1 m \[ g t i h t ( x i ) + 1 2 h t i h t ( x i ) 2 \] + γ J + λ 2 ∑ j = 1 J w t j 2 = ∑ j = 1 J \[ ∑ x i ∈ R t j g t i w t j + ∑ x i ∈ R t j 1 2 h t i w t j 2 \] + γ J + λ 2 ∑ j = 1 J w t j 2 = ∑ j = 1 J \[ ∑ x i ∈ R t j g t i w t j + w t j 2 2 ( ∑ x i ∈ R t j h t i + λ ) \] + γ J \\begin\{aligned\} L\_t &=\\sum\_\{i=1\}^\{m\} \\bigg \[g\_\{ti\}h\_t(x\_i)+\\frac\{1\}\{2\}h\_\{ti\}h\_t(x\_i)^2 \\bigg \]+\\gamma J+\\frac\{\\lambda\}\{2\}\\sum\_\{j=1\}^\{J\}\{w\_\{tj\}\}^2 \\\\ &=\\sum\_\{j=1\}^\{J\} \\bigg \[ \\sum\_\{x\_i \\in R\_\{tj\}\}g\_\{ti\}w\_\{tj\}+\\sum\_\{x\_i \\in R\_\{tj\}\}\\frac\{1\}\{2\}h\_\{ti\}w\_\{tj\}^2 \\bigg \]+\\gamma J+\\frac\{\\lambda\}\{2\}\\sum\_\{j=1\}^\{J\}\{w\_\{tj\}\}^2 \\\\ &=\\sum\_\{j=1\}^\{J\} \\bigg \[ \\sum\_\{x\_i \\in R\_\{tj\}\}g\_\{ti\}w\_\{tj\}+\\frac\{w\_\{tj\}^2\}\{2\}(\\sum\_\{x\_i \\in R\_\{tj\}\}h\_\{ti\}+\\lambda) \\bigg \]+\\gamma J \\end\{aligned\} Lt=i=1∑m\[gtiht(xi)\+21htiht(xi)2\]\+γJ\+2λj=1∑Jwtj2=j=1∑J\[xi∈Rtj∑gtiwtj\+xi∈Rtj∑21htiwtj2\]\+γJ\+2λj=1∑Jwtj2=j=1∑J\[xi∈Rtj∑gtiwtj\+2wtj2(xi∈Rtj∑hti\+λ)\]\+γJ  
把每个子树区域的样本的一阶和二阶导数的和单独表示如下：  
 G t j = ∑ x i ∈ R t j g t i H t j = ∑ x i ∈ R t j h t i G\_\{tj\}= \\sum\_\{x\_i \\in R\_\{tj\}\}g\_\{ti\} \\qquad H\_\{tj\}=\\sum\_\{x\_i \\in R\_\{tj\}\}h\_\{ti\} Gtj=xi∈Rtj∑gtiHtj=xi∈Rtj∑hti  
于是损失函数最终的形式为：  
 L t = ∑ j = 1 J \[ G t j w t j + w t j 2 2 ( H t j + λ ) \] + γ J L\_t = \\sum\_\{j=1\}^\{J\} \\bigg \[ G\_\{tj\}w\_\{tj\}+\\frac\{w\_\{tj\}^2\}\{2\}(H\_\{tj\}+\\lambda) \\bigg \]+\\gamma J Lt=j=1∑J\[Gtjwtj\+2wtj2(Htj\+λ)\]\+γJ  
得到了最终的损失函数，如何一次求解出决策树最优的所有J个叶子节点区域和每个叶子节点区域的最优解 w t j w\_\{tj\} wtj呢？

### XGBoost损失函数的优化求解 ###

我们得到了最终的损失函数，我们想通过求解损失函数最小值来得到决策树，从而得到样本被划分的子树区域及子树区域的预测值，所以我们的优化公式如下：  
 min ⁡ L t = ∑ j = 1 J \[ G t j w t j + w t j 2 2 ( H t j + λ ) \] + γ J G t j = ∑ x i ∈ R t j g t i H t j = ∑ x i ∈ R t j h t i \\min L\_t = \\sum\_\{j=1\}^\{J\} \\bigg \[ G\_\{tj\}w\_\{tj\}+\\frac\{w\_\{tj\}^2\}\{2\}(H\_\{tj\}+\\lambda) \\bigg \]+\\gamma J \\\\ G\_\{tj\}= \\sum\_\{x\_i \\in R\_\{tj\}\}g\_\{ti\} \\qquad H\_\{tj\}=\\sum\_\{x\_i \\in R\_\{tj\}\}h\_\{ti\} minLt=j=1∑J\[Gtjwtj\+2wtj2(Htj\+λ)\]\+γJGtj=xi∈Rtj∑gtiHtj=xi∈Rtj∑hti  
但对着这个损失函数求解最小值似乎一筹莫展，根本无从下手，其实还是回到了一开始说的那两个问题：

*  1、怎么划分子树，如何根据特征及特征值来划分子树，使得 L t L\_t Lt最小？
 *  2、划分子树后，如何计算每个子树区域的预测值，使得 L t L\_t Lt最小？

这个问题在GBDT算法中也涉及到了，它是通过穷举的方式通过均方误差来划分子树，我们来看下XGBoost如何来做，首先我们通过 L t L\_t Lt对 w t j w\_\{tj\} wtj求导，导数等于0求得极值，得到：  
 w t j = − G t j H t j + λ w\_\{tj\}=-\\frac\{G\_\{tj\}\}\{H\_\{tj\}+\\lambda\} wtj=−Htj\+λGtj  
带入到原损失函数中得到：  
 L t = − 1 2 ∑ j = 1 J G t j 2 H t j + λ + γ J L\_\{t\}=-\\frac\{1\}\{2\}\\sum\_\{j=1\}^\{J\}\\frac\{G\_\{tj\}^2\}\{H\_\{tj\}+\\lambda\}+\\gamma J Lt=−21j=1∑JHtj\+λGtj2\+γJ  
转换后的损失函数就变成了如何来分裂特征获得子树区域，XGBoost使用贪心算法来求解此问题，算法思想：如果我们每次做左右子树分裂时，可以最大程度的减少损失函数的损失就最好了。怎么衡量这个损失函数的损失？用如下公式：  
 − 1 2 ( G L + G R ) 2 H L + H R + λ − \[ − 1 2 G L 2 H L + λ − 1 2 G R 2 H R + λ + λ ( J + 1 ) \] + γ J -\\frac\{1\}\{2\}\\frac\{(G\_L+G\_R)^2\}\{H\_L+H\_R+\\lambda\}-\\bigg\[-\\frac\{1\}\{2\}\\frac\{G\_\{L\}^2\}\{H\_\{L\}+\\lambda\}-\\frac\{1\}\{2\}\\frac\{G\_\{R\}^2\}\{H\_\{R\}+\\lambda\}+\\lambda (J+1)\\bigg\]+\\gamma J −21HL\+HR\+λ(GL\+GR)2−\[−21HL\+λGL2−21HR\+λGR2\+λ(J\+1)\]\+γJ  
 G L 、 G R G\_L、G\_R GL、GR是左右子树的一阶导之和， H L 、 H R H\_L、H\_R HL、HR是左右子树的二阶导之和。这个公式怎么来的？为什么是这样的形式？目前还不清楚，后面再解析。整理上式，化简为：  
 max ⁡ 1 2 G L 2 H L + λ + 1 2 G R 2 H R + λ − 1 2 ( G L + G R ) 2 H L + H R + λ − γ \\max \\qquad \\frac\{1\}\{2\}\\frac\{G\_\{L\}^2\}\{H\_\{L\}+\\lambda\}+\\frac\{1\}\{2\}\\frac\{G\_\{R\}^2\}\{H\_\{R\}+\\lambda\}-\\frac\{1\}\{2\}\\frac\{(G\_L+G\_R)^2\}\{H\_L+H\_R+\\lambda\}-\\gamma max21HL\+λGL2\+21HR\+λGR2−21HL\+HR\+λ(GL\+GR)2−γ

### 总结XGBoost算法流程 ###

输入：训练集样本 I = \{ ( x 1 , y 1 ) , ( x 2 , y 2 ) , . . . , ( x m , y m ) \} I=\\\{(x\_1,y\_1),(x\_2,y\_2),...,(x\_m,y\_m)\\\} I=\{ (x1,y1),(x2,y2),...,(xm,ym)\}，最大迭代次数 T T T，损失函数 L L L，正则化系数 λ , γ \\lambda,\\gamma λ,γ  
输出：强学习器 f ( x ) f(x) f(x)  
算法流程：  
对迭代轮数 t = 1 , 2 , . . . T t=1,2,...T t=1,2,...T有：

*  1、计算第i个样本 ( i = 1 , 2 , . . m ) (i=1,2,..m) (i=1,2,..m)在当前轮损失函数L基于 f t − 1 ( x i ) f\_\{t-1\}(xi) ft−1(xi)的一阶导数 g t i g\_\{ti\} gti，二阶导数 h t i h\_\{ti\} hti,计算所有样本的一阶导数和 G t G\_t Gt和 H t H\_t Ht。
 *  2、基于当前节点尝试分裂决策树，默认分数score=0，对特征序号 k = 1 , 2... K k=1,2...K k=1,2...K：  
    a、 G L = 0 G\_L=0 GL=0和 H L = 0 H\_L=0 HL=0，将样本按特征k从小到大排列，依次取出第i个样本，依次计算当前样本放入左子树后，左右子树一阶和二阶导数和：  
     G L = G L + g t i , G R = G − G L H L = H L + h t i , H R = H − H L G\_L=G\_L+g\_\{ti\},G\_R=G-G\_L \\\\ H\_L=H\_L+h\_\{ti\},H\_R=H-H\_L GL=GL\+gti,GR=G−GLHL=HL\+hti,HR=H−HL  
    b、尝试更新最大的分数：  
     s c o r e = m a x ( s c o r e , 1 2 G L 2 H L + λ + 1 2 G R 2 H R + λ − 1 2 ( G L + G R ) 2 H L + H R + λ − γ ) score = max(score,\\frac\{1\}\{2\}\\frac\{G\_\{L\}^2\}\{H\_\{L\}+\\lambda\}+\\frac\{1\}\{2\}\\frac\{G\_\{R\}^2\}\{H\_\{R\}+\\lambda\}-\\frac\{1\}\{2\}\\frac\{(G\_L+G\_R)^2\}\{H\_L+H\_R+\\lambda\}-\\gamma) score=max(score,21HL\+λGL2\+21HR\+λGR2−21HL\+HR\+λ(GL\+GR)2−γ)
 *  3、 基于最大score对应的划分特征和特征值分裂子树。
 *  4)、如果最大score为0，则当前决策树建立完毕，计算所有叶子区域的 w t j w\_\{tj\} wtj, 得到弱学习器 h t ( x ) h\_t(x) ht(x)，更新强学习器 f t ( x ) f\_t(x) ft(x),进入下一轮弱学习器迭代.如果最大score不是0，则转到第2步继续尝试分裂决策树。

疑问：

*  迭代轮数是做什么的？
 *  步骤流程中2.a步有些看不太明白  
    尝试将样本加入到左子树，这样来计算一个优化公式，比较与score的值的大小，但是没有讲如果比score小，这个样本最终应该放在哪个子树中 ？我猜测是放到右子树中，毕竟整个流程中就涉及到左子树，计算也都是左子树，所以放不进去就放在右子树，最终一颗二叉树就成了，然后再继续分裂。
 *  score等于0？  
    最差的情况是不是就一个样本一个叶子节点，也不能继续分裂了，score=0。这样的决策树泛化能力太弱了，另一种情况就是子树的所有样本 g t i 、 h t i g\_\{ti\}、h\_\{ti\} gti、hti都是小于或等于0的。这样就分裂不了。
 *  正则项缺了一个 γ \\gamma γ

### 算法运行优化 ###

*  1、所有的特征，特征值都提前排序，并且计算一阶导、二阶导数值
 *  2、根据特征并行的计算分割点，这样可以提高效率，大部分的计算都在第一步里，直接拿结果用来相加就行

### 缺省值的算法健壮性 ###

看到有些博客里讲解了XGBoost关于缺省值的问题，我们假设有些样本特征值是缺省的，因为缺省的，所以这些样本的一阶导、二阶导都是没有的，那么这些样本是应该放在左子树还是右子树？原本是假定这些样本值是在右子树的。

### 疑问解答 ###

*  1）请问xgboost可以用来处理高维度的特征吗，最大能到什么级别呀？  
    XGboost肯定可以处理高维度的特征的，多大的维度取决于你有多少分布式的计算资源。如果你有一个比较大的spark集群，那么特征维度在百万级肯定没问题。
 *  2）还有就是xgboost做回归和分类的区别是什么呀？在原理这里没有关于分类和回归的区别呀。  
    xgboost做回归和分类的区别仅仅在于叶子节点的区域拟合值的意义。如果是回归，那么叶子节点区域拟合的就是普通的连续值。如果是分类，叶子节点区域拟合的是类别的概率偏差，这个概率偏差值你可以当做普通的连续值，那么分类和回归就可以从原理上同等对待了。
 *  3）它的gblinear具体是什么意思呢，是怎么使用线性模型进行提升计算的呀？  
    gblinear意味着弱学习器不使用决策树，而是使用线性模型，回归的话就是线性回归（Lasso，Ridge），分类就是逻辑回归
 *  4） g t i 、 h t i g\_\{ti\}、h\_\{ti\} gti、hti是如何计算的？  
    我们看公式知道， g t i = L ′ ( y i , f t − 1 ( x i ) ) g\_\{ti\} = L^\{&\#x27;\}(y\_i,f\_\{t-1\}(x\_i)) gti=L′(yi,ft−1(xi))其实对 f t − 1 ( x i ) f\_\{t-1\}(x\_i) ft−1(xi)求导，这样就存在一个问题，在上一个决策树中，子树叶子节点上的样本的预测值都是一样的，那么这些样本在生成下一棵树时，一阶导、二阶导都是一样的，最差的情况就是所有样本都是一样的，这样到后面算法就有问题了，所以初始值很重要。我们仔细分析，这里有两个问题要讨论：  
    第一个：我们是用上一个决策树还是利用之前所有的决策树来作为 f t − 1 f\_\{t-1\} ft−1计算当前导数的？实际上是全部的弱学习器来参与计算的，因为有 f n = f n − 1 + T f\_n=f\_\{n-1\}+T fn=fn−1\+T， T T T表示为当前弱学习器的某一个样本的预测值，所以是之前全部的学习器  
    第二个：一阶导和二阶导的计算也跟 y i y\_i yi是有关的，在 T = 0 T=0 T=0时，有一个默认的初始值，这个初始值对于所有样本都是一样的，由于 y i y\_i yi不一样会导致计算一阶导、二阶导时也会有结果会有差异，就尽可能的不会出现所有样本的一阶导、二阶导都是一样的情况。也就不会出现极端的情况。

这些问题，有些问题是咨询刘建平老师的，在他的博客里留言的，参考博客里就是他的一篇文章。

### 参考博客 ###

[XGBoost算法原理小结][XGBoost]

[GBDT]: https://blog.csdn.net/randompeople/article/details/95449409
[-]: https://blog.csdn.net/randompeople/article/details/93384524
[XGBoost]: https://www.cnblogs.com/pinard/p/10979808.html