xgboost原理与推导

Love The Way You Lie 2022-05-17 02:09 319阅读 0赞

GBDT和xgboost在工业界被越来越多的使用，尤其是在一些数据比赛中经常能看到它的身影，虽然在使用起来不难，但是要能完整的理解还是有一点麻烦的。本文在分享xgboost之前，先一步一步梳理GB，GBDT，xgboost，它们之间有非常紧密的联系，GBDT是以决策树（CART）为基学习器的GB算法，xgboost扩展和改进了GDBT，xgboost算法更快，准确率也相对高一些。

## 1.梯度增强（GB） ##

机器学习中的学习算法的目标是为了优化或者说最小化损失功能，渐变助推的思想是迭代生成多个（M个）弱学习模型，然后将每个弱学习模型的预测结果相加，后面的模型FM + 1（x）的基于前面学习模型的FM（X）的效果生成的，关系如下：

![1 \\ le m \\ le M][1 _ le m _ le M]     ![F\_ \{m + 1\}（x）= F\_m（x）+ h（x）][F_ _m _ 1_x_ F_m_x_ h_x]

GB算法的思想很简单，关键是怎么生成h（x）？

如果目标函数是回归问题的均方误差，很容易想到最理想的H（X）应该是能够完全拟合 ，这就是常说基于残差的学习。残差学习在回归问题中可以很好的使用，但是为了一般性（分类，排序问题），实际中往往是基于Loss Function在函数空间的负梯度学习，对于回归问题残差和负梯度也是相同的。中的**f**，不要理解为传统意义上的函数，而是一个**函数向量 **，向量中元素的个数与训练样本的个数相同，因此基于Loss Function函数空间的负梯度的学习也称为“伪残差”。![y  -  F\_m（x）][y - F_m_x]![\\ frac \{1\} \{2\}（y  -  F（x））^ 2][frac _1_ _2_y - F_x_ 2]![L（y，f）][L_y_f]![\\！ f（x\_1），\\ ldots，f（x\_n）][f_x_1_ ldots_f_x_n]

**GB算法的步骤：**

1.初始化模型为常数值：

![F\_0（x）= \\ underset \{\\ gamma\} \{\\ arg \\ min\} \\ sum\_ \{i = 1\} ^ n L（y\_i，\\ gamma）。][F_0_x_ _ underset _ gamma_ _ arg _ min_ _ sum_ _i _ 1_ _ n L_y_i_ gamma]

2.迭代生成中号个基学习器

1.计算伪残差

![r\_ \{im\} =  -  \\ left \[\\ frac \{\\ partial L（y\_i，F（x\_i））\} \{\\ partial F（x\_i）\} \\ right\] \_ \{F（x）= F\_ \{m-1\}（x \}\} \\ quad \\ mbox \{for\} i = 1，\\ ldots，n。][r_ _im_ _ - _ left _ frac _ partial L_y_i_F_x_i_ _ partial F_x_i_ _ right_ _ _F_x_ F_ _m-1_x _ _ quad _ mbox _for_ i _ 1_ ldots_n]

2.基于     生成基学习器  ![\\ \{（x\_i，r\_ \{im\}）\\\} \_ \{i = 1\} ^ n][_x_i_r_ _im_ _ _i _ 1_ _ n]![\\！ h\_m（x）的][h_m_x]

3.计算最优的![\\！ \\ gamma\_m][_ gamma_m]

![\\ gamma\_m = \\ underset \{\\ gamma\} \{\\ operatorname \{arg \\，min\}\} \\ sum\_ \{i = 1\} ^ n L \\ left（y\_i，F\_ \{m-1\}（x\_i）+ \\ gamma h\_m（x\_i） \\对）。][gamma_m _ _ underset _ gamma_ _ operatorname _arg _min_ _ sum_ _i _ 1_ _ n L _ left_y_i_F_ _m-1_x_i_ _ gamma h_m_x_i_]

4.更新模型

![F\_m（x）= F\_ \{m-1\}（x）+ \\ gamma\_m h\_m（x）。][F_m_x_ F_ _m-1_x_ _ gamma_m h_m_x]

##  2.梯度提升决策树（GBDT） ##

GBDT（Gradient Boosted Decision Trees）在1999年由Jerome Friedman提出，将GBDT模型应用于CTR预估，最早见于  
          yahoo.GBDT是一个加性回归模型，通过boosting迭代的构造一组弱学习器，相对LR的优势如不需要做特征归一化，自动进行选择可解释性较低的模型，可以适应多种损失函数如Square Loss，Log Loss等。但作为非线性模型，其相对线性模型的缺点也是显然的：提升是个串行的过程，不能并化，计算复杂度较高，同时其不太适合高维稀疏特征，通常采用稠密的数值特征，如点击率预估中的COEC。

GB算法中最典型的基学习器是决策树，尤其是CART，正如名字的含义，GBDT是GB和DT的结合。要注意的是**GDBT中使用的决策树是回归树**，GBDT中的决策树是个弱模型，深度较小一般不会超过5，叶子节点的数量也不会超过10，对于生成的每棵决策树乘上比较小的缩减系数（学习率<0.1），有些GBDT的实现加入了随机抽样（子样0.5 <= f <= 0.8）提高模型的泛化能力。通过交叉验证的方法选择最优的参数。因此GBDT实际的核心问题变成怎么基于使用CART回归树生成？![\\ \{（x\_i，r\_ \{im\}）\\\} \_ \{i = 1\} ^ n][_x_i_r_ _im_ _ _i _ 1_ _ n]![\\！ h\_m（x）的][h_m_x]

作为对比，先说分类树，我们知道**CART是二叉树**，CART分类树在每次分枝时，是穷举每一个功能，每的一个**阈值**，根据**基尼系数**找到使不纯性降低最大的功能的以及其阀值，然后按照特征<=阈值，和特征>阈值分成的两个分枝，每个分支包含符合分支条件的样本。用同样方法继续分枝直到该分支下的所有样本都属于统一类别，或达到预设的终止条件，若最终叶子节点中的类别不唯一，则以多数人的类别作为该叶子节点的类别。

回归树总体流程也是类似，不过在每个节点（不一定是叶子节点）得都会一个**预测值**，时分枝**穷举**每一个特征的每个阈值找最好的分割点，但衡量最好的标准不再是GINI系数，而是**最小化：均方差。**

## 3. xgboost ##

xgboost算法的步骤和GB基本相同，都是首先初始化为一个常数，不同于传统的GBDT方式，只利用了一阶的导数信息**ri**，**xgboost是根据一阶导数gi和二阶导数hi**，**迭代**生成基学习器，相加更新学习器.xgboost对损失func做了二阶的**泰勒展开**，并在目标函数之外加入**正则项整体 **求最优解，用以权衡目标函数的下降和模型复杂程度，避免过拟合。

### 模型如何学习：添加剂训练 ###

其中第一部分是训练误差，也就是大家相对比较熟悉的如平方误差，logistic loss等。而第二部分是每棵树的复杂度的和。这个在后面会继续讲到。因为现在我们的参数可以认为是在一个函数空间里面，我们不能采用传统的如SGD之类的算法来学习我们的模型，因此我们会采用一种叫做**添加剂训练的方式也就是Boosting。每一次保留原来的模型不变，加入一个新的函数f到我们的模型中。**

![70][]

### xgboost推导过程 ###

我们会采用如下的泰勒展开近似来定义一个近似的目标函数，方便我们进行这一步的计算。

![70 1][]

其中，表示损失函数，     表示正则项，包括L1，L2，常数项。![70 2][]![70 3][]![70 4][]

GI为一阶导数，喜为二阶导数。

当我们把常数项移除之后，我们会发现如下一个比较统一的目标函数。这一个目标函数有一个非常明显的特点，它只依赖于每个数据点的在误差函数上的一阶导数和二阶导数。

![70 5][]

想一想当你被要求使用平方损失和logistic loss实现梯度树时，如何用代码分解模块？

一个树的定义可以分成两个部分：结构部分和叶子权重部分。    
假设q是结构映射函数把输入映射到叶子的索引号上面去，w表示叶子节点的权重。则树可以表示为：

![70 6][]

定义树的正则项（复杂度）：包含两个部分树的叶子节点的个数T和叶子节点的权重的平方（L2），即：

![70 7][]

目标函数的OBJ

![70 8][]

此时单棵决策树的学习过程如下：

> （1）枚举所有可能的树结构q    
> （2）计算对应的分数（损失值）obj，**obj越小越好 **  
> （3）找到最佳的树结构，为每个叶子节点计算权值w

然而，的可能树结构数量的英文**无穷的**，所以实际上我们不可能枚举所有可能的树结构。通常情况下，采用我们**贪心策略**来生成决策树的每个节点。

> 1.  从深度为0的树开始，每个对叶节点**枚举所有**的可用特征
> 2.  针对每个特征，属于把该节点的训练样本根据该特征值**升序个结果排列**，通过线性扫描的方式来决定该特征的最佳分裂点，并记录该特征的最大收益（**采用最佳分裂点时的收益**）
> 3.  选择收益最大的特征作为分裂特征，用该特征的最佳分裂点作为分裂位置，把该节点生长出左右两个新的叶节点，并为每个新节点关联对应的样本集
> 4.  回到第1步，**递归执行**到满足特定条件为止

## xgboost实现在做时还许多了**优化**： ##

*  在寻找最佳分割点时，考虑**传统的枚举每个特征的所有可能分割点的贪心法效率太低**，xgboost实现了一种近似的算法。的大致思想的英文**根据百分位行业释义法律列举几个可能成为分割点的候选者**，然后从候选者中根据上面求分割点的公式计算找出最佳的分割点。
 *  xgboost考虑了训练数据为稀疏值的情况，为可以缺失值或者指定的值**指定分支的默认方向**，这能大大提升算法的效率，造纸提到**50倍**。
 *  列特征排序后以**块**的形式存储在内存中，在迭代中可以重复使用;虽然提高算法迭代必须串行，但是处理在每个特征列时可以来到来到lái **parallel-** 。
 *  按照特征列方式存储能优化寻找最佳的分割点，但是当以行计算梯度数据时会导致内存的不连续访问，严重时会导致缓存未命中，降低算法效率。造纸中提到，先柯林斯**将数据收集到线程内部的缓冲区**，然后再计算，提高算法的效率。
 *  xgboost还考虑了当数据量比较大，内存不够时怎么有效的使用磁盘，主要是结合**多线程，数据压缩，分片**的方法，尽可能的提高算法的效率。

## 分布式xgboost发展过程 ##

![70 9][]

Xgboost分布式算法开始基本成熟后，分布式版本的变更主要是底层的AllReduce接口支持不同平台\[mpi，yarn ....\]的过程。

**第一版支持MPI**

Rabit开始兼容mpi的AllReduce，但是运行mpi的分布式程序需要读写hdfs，并分割数据。当时没有实现C ++读写hdfs功能，跑hdfs数据比较麻烦。

**第二版支持Hadoop Streaming**

通过Hadoop Streamingg把xgboost作为**地图**运行。在每个地图中进行allreduce的通信完xgboost每轮的迭代，减少只是负责输出模型。**通过在一个地图中完成xgboost所有的迭代**，避免了传统基于hadoop的机器学习程序每轮迭代间的资源重新分配，使得基于hadoop的xgboost的迭代速度能媲美基于mpi的xgboost，同时避免了，同时避免了mpi程序读写hdfs的麻烦。

**第三版原生支持Yarn**  
Yarn为了能自由的掌控各个节点资源分配并且使文件均衡割到各个节点，直接把rabit作为纱的一个APP运行。在这一版里，实现了c ++读写hdfs的功能，解决了流版本中xgboost中对文件操作自由不高的问题。

目前xgboost支持 Python, R, Java, Scala, C++ and more.

Runs on **single machine**, **Hadoop**, **Spark**, **Flink** and **DataFlow** , [https://xgboost.ai/][https_xgboost.ai]

参考

陈天奇博士幻灯片：[https][]：//homes.cs.washington.edu/~tqchen/pdf/BoostedTree.pdf

xgboost导读和实战：https：//pan.baidu.com/s/1BWdIOUYaxA2PuN\_TPcLEBg密码：m7py

对于如何安装xgboost可参考我的博文：[Windows环境下安装xgboost][Windows_xgboost]

[1 _ le m _ le M]: https://upload.wikimedia.org/math/e/4/7/e4746d8b9e912c1875cd9e5f612ab2ae.png
[F_ _m _ 1_x_ F_m_x_ h_x]: https://upload.wikimedia.org/math/7/5/7/7579bdfb140e56a86da109ec96b87421.png
[y - F_m_x]: https://upload.wikimedia.org/math/9/7/d/97dfe316cb29bf7289a75ade5be7de1c.png
[frac _1_ _2_y - F_x_ 2]: https://upload.wikimedia.org/math/d/6/9/d69638d1c777cf19b3b3b04bc81d101e.png
[L_y_f]: https://upload.wikimedia.org/math/6/1/3/613b882386356b2a890c03969c349759.png
[f_x_1_ ldots_f_x_n]: https://upload.wikimedia.org/math/a/9/6/a9631135ced6265452825a49f4c7badb.png
[F_0_x_ _ underset _ gamma_ _ arg _ min_ _ sum_ _i _ 1_ _ n L_y_i_ gamma]: https://upload.wikimedia.org/math/7/f/7/7f7ee5504c0d54de6d2510bdae7f723a.png
[r_ _im_ _ - _ left _ frac _ partial L_y_i_F_x_i_ _ partial F_x_i_ _ right_ _ _F_x_ F_ _m-1_x _ _ quad _ mbox _for_ i _ 1_ ldots_n]: https://upload.wikimedia.org/math/0/b/e/0bebe45631e9a1c4ed693590d60829c0.png
[_x_i_r_ _im_ _ _i _ 1_ _ n]: https://upload.wikimedia.org/math/2/b/b/2bbe4b0725baed85eae8dbbb20360ea6.png
[h_m_x]: https://upload.wikimedia.org/math/7/f/d/7fd32efb7a21cc484be23d1015ee074e.png
[_ gamma_m]: https://upload.wikimedia.org/math/8/7/2/8721621535a98cea1b0e38459f594057.png
[gamma_m _ _ underset _ gamma_ _ operatorname _arg _min_ _ sum_ _i _ 1_ _ n L _ left_y_i_F_ _m-1_x_i_ _ gamma h_m_x_i_]: https://upload.wikimedia.org/math/9/2/e/92e9576607b45540b71e23c14c737d0a.png
[F_m_x_ F_ _m-1_x_ _ gamma_m h_m_x]: https://upload.wikimedia.org/math/3/b/0/3b047653ac126f19f09112f47ddb9f9c.png
[70]: /images/20220517/667ac0b522274ffebdba59e84f447e3b.png
[70 1]: /images/20220517/587683daabd745b993fa3f519cc7555a.png
[70 2]: https://img-blog.csdn.net/20180805110436524?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTA4OTk5ODU=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70
[70 3]: https://img-blog.csdn.net/20180805110450437?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTA4OTk5ODU=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70
[70 4]: /images/20220517/b9a0abc18ae24402a29844f083a80a1c.png
[70 5]: /images/20220517/209aa379c685414f8f3eda51f1bfee70.png
[70 6]: /images/20220517/b7aa0fe5ae0a4040a8446580ca0c10ae.png
[70 7]: /images/20220517/e50e6ba8afc24522b418c8dfc33c050f.png
[70 8]: /images/20220517/e354c8b0b22241d1a1d925b812090cd7.png
[70 9]: /images/20220517/fb591eebaa754fa59851635e79565631.png
[https_xgboost.ai]: https://xgboost.ai/
[https]: https://homes.cs.washington.edu/~tqchen/pdf/BoostedTree.pdf
[Windows_xgboost]: https://blog.csdn.net/u010899985/article/details/80461885