一文入门：XGBoost与手推二阶导

参考链接： 机器学习: XGBoost简介

作者前言 

在2020年还在整理XGB的算法，其实已经有点过时了。。不过，主要是为了学习算法嘛。现在的大数据竞赛，XGB基本上已经全面被LGB模型取代了，这里主要是学习一下Boost算法。之前已经在其他博文中介绍了Adaboost算法和Gradient-boost算法，这篇文章讲解一下XGBoost。 

Adaboost和XGBoost无关，但是Gradient-boost与XGBoost有一定关系。 一文搞懂：Adaboost及手推算法案例 一文读懂：GBDT梯度提升 

树模型概述 

XGB就是Extreme Gradient Boosting极限梯度提升模型。XGB简单的说是**一组分类和回归树（CART）**的组合。跟GBDT和Adaboost都有异曲同工之处。 【CART=classification adn regression trees】 

这里对于一个决策树，如何分裂，如何选择最优的分割点，其实就是一个搜索的过程。搜索怎么分裂，才能让目标函数最小。目标函数如下： 

        O

        b

        j

        =

        L

        o

        s

        s

        +

        Ω

       Obj = Loss + \Omega

    Obj=Loss+Ω 

        O

        b

        j

       Obj

    Obj就是我们要最小化的优化函数，

        L

        o

        s

        s

       Loss

    Loss就是这个CART模型的预测结果和真实值得损失。

        Ω

       \Omega

    Ω就是这个CART模型的复杂度,类似神经网络中的正则项。 【上面的公式就是一个抽象的概念。我们要知道的是：CART树模型即要求预测尽可能准确，又要求树模型不能过于复杂。】 

对于回归问题，我们可以用均方差来作为Loss： 

        L

        o

        s

        s

        =

         ∑

         i

         (

          y

          i

         −

           y

           i

          ^

          )

          2

       Loss=\sum_i{(y_i-\hat{y_i})^2}

    Loss=∑i​(yi​−yi​^​)2 

对于分类问题，用交叉熵是非常常见的,这里用二值交叉熵作为例子： 

        L

        o

        s

        s

        =

         ∑

         i

         (

          y

          i

         l

         o

         g

         (

           y

           i

          ^

         )

         +

         (

         1

         −

          y

          i

         )

         l

         o

         g

         (

           y

           i

          ^

         )

         )

       Loss = \sum_i{(y_ilog(\hat{y_i})+(1-y_i)log(\hat{y_i}))}

    Loss=∑i​(yi​log(yi​^​)+(1−yi​)log(yi​^​)) 

总之，这个Loss就是衡量模型预测准确度的损失。 

下面看一下如何计算这个模型复杂度

        Ω

       \Omega

    Ω吧。 

        Ω

        =

        γ

        T

        +

         1

         2

        λ

         ∑

         j

         T

          w

          j

         2

       \Omega = \gamma T+\frac{1}{2} \lambda \sum^T_j{w_j}^2

    Ω=γT+21​λ∑jT​wj​2 

        T

       T

    T表示叶子节点的数量，

         w

         j

       w_j

    wj​表示每个叶子节点上的权重（与叶子节点的样本数量成正比）。 

【这里有点麻烦的在于，

         w

         j

       w_j

    wj​是与每个叶子节点的样本数量成正比，但是并非是样本数量。这个

         w

         j

       w_j

    wj​的求取，要依靠与对整个目标函数求导数，然后找到每个叶子节点的权重值

         w

         j

       w_j

    wj​。】 

XGB vs GBDT 

其实说了这么多，感觉XGB和GDBT好像区别不大啊？下面整理一下网上有的说法，再加上自己的理解。有错误请指出评论，谢谢！ 

区别1：自带正则项 

GDBT中，只是让新的弱分类器来拟合负梯度，那拟合多少棵树才算好呢？不知道。XGB的优化函数中，有一个

        Ω

       \Omega

    Ω复杂度。这个复杂度不是某一课CART的复杂度，而是XGB中所有CART的总复杂度。可想而知，每多一颗CART，这个复杂度就会增加他的惩罚力度，当损失下降小于复杂度上升的时候，XGB就停止了。 

区别2：有二阶导数信息 

GBDT中新的CART拟合的是负梯度，也就是一阶导数。而在XGB会考虑二阶导数的信息。 

这里简单推导一下XGB如何用上二阶导数的信息的： 

 之前我们得到了XGB的优化函数： 

          O

          b

          j

          =

          L

          o

          s

          s

          +

          Ω

         Obj = Loss + \Omega

      Obj=Loss+Ω  然后我们把Loss和Omega写的更具体一点： 

          O

          b

          j

          =

           ∑

           i

           n

           L

           o

           s

           s

           (

            y

            i

           ,

             y

             ^

            i

            t

           )

          +

           ∑

           j

           t

           Ω

           (

           c

           a

           r

            t

            j

           )

         Obj = \sum_i^n{Loss(y_i,\hat{y}_i^t)}+\sum_j^t{\Omega(cart_j)}

      Obj=∑in​Loss(yi​,y^​it​)+∑jt​Ω(cartj​) 

             y

             i

             t

            ^

          \hat{y_i^t}

       yit​^​表示总共有t个CART弱分类器，然后t个弱分类器给出样本i的估计值就。

            y

            i

          y_i

       yi​第i个样本的真实值；

           Ω

           (

           c

           a

           r

            t

            j

           )

          \Omega(cart_j)

       Ω(cartj​)第j个CART模型的复杂度。  我们现在要求取第t个CART模型的优化函数，所以目前我们只是知道前面t-1的模型。所以我们得到： 

            y

            ^

           i

           t

          =

            y

            ^

           i

            t

            −

            1

          +

           f

           t

          (

           x

           i

          )

         \hat{y}_i^t = \hat{y}_i^{t-1}+f_t(x_i)

      y^​it​=y^​it−1​+ft​(xi​) t个CART模型的预测，等于前面t-1个CART模型的预测加上第t个模型的预测。  所以可以得到： 

           ∑

           i

           n

           L

           o

           s

           s

           (

            y

            i

           ,

             y

             ^

            i

            t

           )

          =

           ∑

           i

           n

           L

           o

           s

           s

           (

            y

            i

           ,

             y

             ^

            i

             t

             −

             1

           +

            f

            t

           (

            x

            i

           )

           )

         \sum_i^n{Loss(y_i,\hat{y}_i^t)}=\sum_i^n{Loss(y_i,\hat{y}_i^{t-1}+f_t(x_i))}

      ∑in​Loss(yi​,y^​it​)=∑in​Loss(yi​,y^​it−1​+ft​(xi​)) 这里考虑一下特勒展开： 

          f

          (

          x

          +

          Δ

          x

          )

          ≈

          f

          (

          x

          )

          +

           f

           ′

          (

          x

          )

          Δ

          x

          +

           1

           2

           f

            ′

            ′

          (

          x

          )

          Δ

           x

           2

         f(x+\Delta x)\approx f(x)+f'(x)\Delta x + \frac{1}{2} f''(x)\Delta x^2

      f(x+Δx)≈f(x)+f′(x)Δx+21​f′′(x)Δx2  如何把泰勒公式带入呢？ 

          L

          o

          s

          s

          (

           y

           i

          ,

            y

            ^

           i

           t

          )

         {Loss(y_i,\hat{y}_i^t)}

      Loss(yi​,y^​it​)中的

           y

           i

         y_i

      yi​其实就是常数，不是变量 所以其实这个是可以看成

          L

          o

          s

          s

          (

            y

            ^

           i

           t

          )

         Loss(\hat{y}_i^t)

      Loss(y^​it​),也就是: 

          L

          o

          s

          s

          (

            y

            ^

           i

            t

            −

            1

          +

           f

           t

          (

           x

           i

          )

          )

         Loss(\hat{y}_i^{t-1}+f_t(x_i))

      Loss(y^​it−1​+ft​(xi​))  带入泰勒公式，把

           f

           t

          (

           x

           i

          )

         f_t(x_i)

      ft​(xi​)看成

          Δ

          x

         \Delta x

      Δx： 

          L

          o

          s

          s

          (

            y

            ^

           i

            t

            −

            1

          +

           f

           t

          (

           x

           i

          )

          )

          =

          L

          o

          s

          s

          (

            y

            ^

           i

            t

            −

            1

          )

          +

          L

          o

          s

           s

           ′

          (

            y

            ^

           i

            t

            −

            1

          )

           f

           t

          (

           x

           i

          )

          +

           1

           2

          L

          o

          s

           s

            ′

            ′

          (

            y

            ^

           i

            t

            −

            1

          )

          (

           f

           t

          (

           x

           i

          )

           )

           2

         Loss(\hat{y}_i^{t-1}+f_t(x_i))=Loss(\hat{y}_i^{t-1})+Loss'(\hat{y}_i^{t-1})f_t(x_i)+\frac{1}{2}Loss''(\hat{y}_i^{t-1})(f_t(x_i))^2

      Loss(y^​it−1​+ft​(xi​))=Loss(y^​it−1​)+Loss′(y^​it−1​)ft​(xi​)+21​Loss′′(y^​it−1​)(ft​(xi​))2 

  在很多的文章中，会用

            g

            i

           =

           L

           o

           s

            s

            ′

           (

             y

             ^

            i

             t

             −

             1

           )

          g_i=Loss'(\hat{y}_i^{t-1})

       gi​=Loss′(y^​it−1​),以及

            h

            i

           =

           L

           o

           s

            s

             ′

             ′

           (

             y

             ^

            i

             t

             −

             1

           )

          h_i=Loss''(\hat{y}_i^{t-1})

       hi​=Loss′′(y^​it−1​)来表示函数的一阶导数和二阶导数。  把泰勒展开的东西带回到最开始的优化函数中，删除掉常数项

          L

          o

          s

          s

          (

            y

            ^

           i

            t

            −

            1

          )

         Loss(\hat{y}_i^{t-1})

      Loss(y^​it−1​)(这个与第t个CART模型无关呀)以及前面t-1个模型的复杂度，可以得到第t个CART的优化函数： 

          O

          b

           j

           t

          ≈

           ∑

           i

           n

           [

            g

            i

            f

            t

           (

            x

            i

           )

           +

            1

            2

            h

            i

           (

            f

            t

           (

            x

            i

           )

            )

            2

          ]

          +

           Ω

           (

           c

           a

           r

            t

            t

           )

         Obj^t \approx \sum_i^n{[g_i f_t(x_i)+\frac{1}{2}h_i(f_t(x_i))^2}]+{\Omega(cart_t)}

      Objt≈∑in​[gi​ft​(xi​)+21​hi​(ft​(xi​))2]+Ω(cartt​)  

【所以XGB用到了二阶导数的信息，而GBDT只用了一阶的梯度】 

区别3：列抽样 

XGB借鉴了随机森林的做法，不仅仅支持样本抽样，还支持特征抽样（列抽样），不仅可以降低过拟合，还可以减少计算。 

区别4：缺失值 

XGB可以自适应的处理样本中的缺失值。如何处理的这里就不再讲述。 

喜欢的话，可以微信扫码关注微信公众号【机器学习炼丹术】,成为炫酷的炼丹师吧~ 

公众号回复【下载】有精选的免费机器学习学习资料。 公众号每天会更新一个机器学习、深度学习的小知识，都是面试官会问的知识点哦~ 

【机器学习的基础数学(PDF)】【竞赛中的大数据处理流程(PDF)】【如何做大数据的基础特征工程(PDF)】【自然语言处理NLP的应用实践大合集(PDF)】【python入门级教材(400页PDF)】 

公众号每天会更新一个机器学习、深度学习的小知识，都是面试官会问的知识点哦~