开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 人工智能 -> XGBoost学习笔记 -> 正文阅读

[人工智能]XGBoost学习笔记

概念

XGBoost即Extreme Gredient Boosting，是一种基于CART决策树的boosting算法

相比GBDT来说优化迭代的方式不同。GBDT使用损失函数的负梯度近似残差来训练下一棵树；

原理

优化方式

设XGBoost模型为 $\hat y_i=\sum_{k=1}^Kf_k(x_i)$

则第 $t$ 次优化的损失函数为

$L=\sum_{i=1}^nL(y_i,F_{t-1}(x_i)+f_t(x_i))+\sum_{k=1}^K(\gamma T_k+\frac{1}{2}\lambda||w_k||^2)$

第二项为正则项， $T_k$ 表示第 $k$ 棵树的叶节点个数， $w_k$ 表示该树各个叶节点的输出值的向量。

根据前向加法算法，此时需找到 $f_t(x)$ ，使 $L$ 最小。此时正则项也只表示第 $t$ 棵树的复杂度。

采用二项泰勒展开式可得

$L(y_i,F_{t-1}(x_i)+f_t(x_i))=L(y_i,F_{t-1}(x_i))+g_if_t(x_i)+\frac{1}{2}h_if_t^2(x_i)$

$g_i=\frac{\partial L(y_i, F_{t-1}(x))}{\partial F_{t-1}(x)}|_{F_{t-1}(x_i)}$ 为一阶偏导

$h_i=\frac{\partial^2 L(y_i, F_{t-1}(x))}{(\partial F_{t-1}(x))^2}|_{F_{t-1}(x_i)}$ 为二阶偏导

代入得

$L=\sum_{i=1}^n[L(y_i,F_{t-1}(x_i))+g_if_t(x_i)+\frac{1}{2}h_if_t^2(x_i)]+\gamma T+\frac{1}{2}\lambda\sum_{j=1}^Tw_j^2$

$L(y_i,F_{t-1}(x_i))$ 是定值，所以只需最小化

$L'=\sum_{i=1}^n[g_if_t(x_i)+\frac{1}{2}h_if_t^2(x_i)]+\gamma T+\frac{1}{2}\lambda\sum_{j=1}^Tw_j^2$

关于样本 $n$ 的连加可以转化为叶节点的输出值的连加，即同一结点下样本的输出值都一样

$f_t(x_i)=w_j$ $x_i属于j结点)$

即

$L'=\sum_{j=1}^T[w_j\sum g_i+\frac{1}{2}w_j^2\sum h_i]+\gamma T+\frac{1}{2}\lambda\sum_{j=1}^Tw_j^2$

$=\sum_{j=1}^T[w_j(\sum g_i)+\frac{1}{2}(\sum h_i+\lambda)w_j^2]+\gamma T$

其中 $\sum g_i$ 表示该结点下所有样本的一阶梯度值， $\sum h_i$ 同理

令 $G_j=\sum g_i$ ， $H_j=\sum h_i$ 则

$L'=\sum_{j=1}^T[w_jG_j+\frac{1}{2}(H_j+\lambda)w_j^2]+\gamma T$

假设树的结构已经固定，即那些样本属于哪个叶节点已固定，则求叶节点的输出 $w_j$ 使损失函数 $L$ 最小

关于 $w_j$ 求导得到 $w_j=-\frac{G_j}{H_j+\lambda}$

代入得， $L'=-\sum_{j=1}^T\frac{1}{2} \frac{G_j^2}{H_j+\lambda}+\gamma T$

$L^{'}$ 代表这棵树的整体损失，越小越好

树的生成

接下来需要确定树的结构，即在树的结点处确定特征和对应的划分点。采用 $L^{'}$ 作为衡量标准。则当一个结点被划分为两个叶节点后，切分前后的损失变化为

切分前 $obj=-\frac{1}{2}\frac{G_0^2}{H_0+\lambda}+\gamma=-\frac{1}{2}\frac{(G_L+G_R)^2}{H_L+H_R+\lambda}+\gamma$

切分后左+右为 $obj=-\frac{1}{2}\frac{G_L^2}{H_L+\lambda}+\gamma-\frac{1}{2}\frac{G_R^2}{H_R+\lambda}+\gamma$

前后损失变化为

$L_{split}=\frac{1}{2}(\frac{G_L^2}{H_L+\lambda}+\frac{G_R^2}{H_R+\lambda}-\frac{(G_L+G_R)^2}{H_L+H_R+\lambda})-\gamma$

要找到特征以及对应的划分点，使上式值最大。

这个公式形式上跟ID3算法（采用entropy计算增益）、CART算法（采用gini指数计算增益）是一致的，都是用分裂后的某种值减去分裂前的某种值，从而得到增益。为了限制树的生长，我们可以加入阈值，当增益大于阈值时才让节点分裂，上式中的gamma即阈值，它是正则项里叶子节点数T的系数，所以xgboost在优化目标函数的同时相当于做了预剪枝。另外，上式中还有一个系数lambda，是正则项里leaf score的L2模平方的系数，对leaf score做了平滑，也起到了防止过拟合的作用，这个是传统GBDT里不具备的特性。

特征查找方式

基本精确的贪心算法（Basic Exact Greedy Algorithm）

为了找到节点最好的划分，该算法的原理是在所有特征上枚举所有的可能的划分，我们称这个算法为Basic Exact Greedy Algorithm。大多数已存在的单台机器上的树提升算法库都是用这种方法实现的，例如scikit-learn，R’s gbm 以及 XGBoost的单机版本都支持这种算法。该算法要求为连续特征枚举所有可能的切分，这对计算机的要求很高，所以该算法为了有效的做到这一点，首先根据特征值排序数据并且按照顺序访问数据，以累积方程（6）中结构分数的梯度统计量。该算法如下：

在这里插入图片描述

近似算法

Basic Exact Greedy Algorithm是一个非常精确的算法，因为它枚举的所有可能的切分点。但是，当数据不能完全的加载到内存时，它可能不是特别有效地。同样的问题也出现在分布式的设置中。为了有效的支持在这两种设置中的有效的梯度提升，一个近似算法需要被使用。该算法首先根据特征分布的百分位数提出n个候选切分节点，然后，算法将位于相邻分位点之间的样本分在一个桶中，在遍历该特征的时候，只需要遍历各个分位点，从而计算最优划分。注意到上面算法流程中表明有全局的近似(global)和局部(local)的近似，所谓全局就是在新生成一棵树之前就对各个特征计算分位点并划分样本，之后在每次分裂过程中都采用近似划分，而局部就是在具体的某一次分裂节点的过程中采用近似算法。该算法如下所示：
在这里插入图片描述

特点

与GBDT相比：

算法上：

GBDT以传统CART作为基分类器，而XGBoost支持线性分类器，相当于引入L1和L2正则化项的逻辑回归（分类问题）和线性回归（回归问题）；
GBDT在优化时只用到一阶导数，XGBoost对代价函数做了二阶Talor展开，引入了一阶导数和二阶导数。XGBoost支持自定义的损失函数，只要是能满足二阶连续可导的函数均可以作为损失函数；
XGBoost在损失函数中引入正则化项，用于控制模型的复杂度。正则化项包含全部叶子节点的个数，每个叶子节点输出的score的L2模的平方和。从Bias-variance tradeoff角度考虑，正则项降低了模型的方差，防止模型过拟合，这也是xgboost优于传统GBDT的一个特性。
当样本存在缺失值是，xgBoosting能自动学习分裂方向，即XGBoost对样本缺失值不敏感；
XGBoost借鉴RF的做法，支持列抽样，这样不仅能防止过拟合，还能降低计算，这也是xgboost异于传统gbdt的一个特性。
XGBoost在每次迭代之后，会将叶子节点的权重乘上一个学习率，主要是为了削弱每棵树的影响，让后面有更大的学习空间。实际应用中，一般把eta设置得小一点，然后迭代次数设置得大一点。GBDT也有学习率这一参数。

运行效率上：

xgboost工具支持并行。boosting不是一种串行的结构吗?怎么并行的？注意xgboost的并行不是tree粒度的并行，xgboost也是一次迭代完才能进行下一次迭代的（第t次迭代的代价函数里包含了前面t-1次迭代的预测值）。xgboost的并行是在特征粒度上的。我们知道，决策树的学习最耗时的一个步骤就是对特征的值进行排序（因为要确定最佳分割点），xgboost在训练之前，预先对数据进行了排序，然后保存为block结构，后面的迭代中重复地使用这个结构，大大减小计算量。这个block结构也使得并行成为了可能，在进行节点的分裂时，需要计算每个特征的增益，最终选增益最大的那个特征去做分裂，那么各个特征的增益计算就可以开多线程进行。

Xgboost在并行处理之前，会提前把样本按照特征大小排好序，默认都放在右子树，然后递归的从小到大拿出一个个的样本放到左子树，然后计算对基于此时的分割点的增益的大小，然后记录并更新最大的增益分割点。

可并行的近似直方图算法，树结点在进行分裂时，需要计算每个节点的增益，若数据量较大，对所有节点的特征进行排序，遍历的得到最优分割点，这种贪心法异常耗时，这时引进近似直方图算法，用于生成高效的分割点，即用分裂后的某种值减去分裂前的某种值，获得增益，为了限制树的增长，引入阈值，当增益大于阈值时，进行分裂；
XGBoost的原生语言为C/C++，这是也是它训练速度快的一个原因。
对于 XGBoost 与 GBDT，其 Boosting 损失函数函数都是可自定义的，但 XGBoost 需要自定义损失函数二阶可导，而 GBDT 只需要一阶可导；其次，对于基模型的拟合（对于 XGBoost 就是拟合 $-\frac{G_j}{H_j+\lambda}$ ，对于 GBDT 就是拟合 $? g$ ），其内部的拟合方式不同，XGBoost 是自己定义的一套增益规则，而 GBDT 就是 CART 树的二阶平方损失拟合。

与LightGBM相比:

XGBoost采用预排序，在迭代之前，对结点的特征做预排序，遍历选择最优分割点，数据量大时，贪心法耗时，LightGBM方法采用histogram算法，占用的内存低，数据分割的复杂度更低，但是不能找到最精确的数据分割点；
XGBoost采用level-wise生成决策树策略，同时分裂同一层的叶子，从而进行多线程优化，不容易过拟合，但很多叶子节点的分裂增益较低，没必要进行更进一步的分裂，这就带来了不必要的开销；LightGBM采用leaf-wise生长策略，每次从当前叶子中选择增益最大的叶子进行分裂，如此循环，但会生长出更深的决策树，产生过拟合，因此 LightGBM 在leaf-wise之上增加了一个最大深度的限制，在保证高效率的同时防止过拟合）。另一个比较巧妙的优化是 histogram 做差加速。一个容易观察到的现象：一个叶子的直方图可以由它的父亲节点的直方图与它兄弟的直方图做差得到。

XGBoost的巧妙之处

机器学习就是模型对数据的拟合。对于一组数据，使用过于复杂的模型去拟合，往往会发生过拟合，这时就需要引入正则化项来限制模型复杂度，然而正则化项的选取、正则化系数的设定都是比较随意的，也比较难做到最佳。而如果使用过于简单的模型，由于模型能力有限，很难把握数据中蕴含的规律，导致效果不佳。

Boosting算法比较巧妙，首先使用简单的模型去拟合数据，得到一个比较一般的结果，然后不断向模型中添加简单模型（多数情况下为层数较浅决策树），随着树的增多，整个boosting模型的复杂度逐渐变高，直到接近数据本身的复杂度，此时训练达到最佳水平。

因此，**boosting算法要取得良好效果，要求每棵树都足够“弱”，**使得每次增加的复杂度都不大，同时树的总数目要足够多。XGBoost中，对每棵树的叶子节点数做了惩罚，从而限制了叶子节点的增长，使得每棵树都是“弱”的，同时还引入了学习速率，进一步降低了每棵树的影响。这样做的代价是，数的总数目会多一些，但从其取得的效果上看，这样做是值得的。

为什么XGBoost运行这么快

连续型特征的处理

决策树在训练时需要进行分叉，对于连续型特征，枚举所有可能分叉点将会十分耗时。一种近似方法是只枚举若干个分位点，例如将所有样本根据此特征进行排序，然后均分10份，两份之间断开的数值即为分位点，枚举所有9个分位点后，使用降低损失最多的那个作为分叉点。

利用数据稀疏性

数据稀疏有三个原因：缺失数据；某些特征本身就含有大量的0；对离散特征做了one-hot处理。无论是哪种，都会导致样本中出现大量的0。通常，利用稀疏性可以提高运算效率。**XGBoost的方法是，每次分叉时，都指定一条默认分支，如果样本的这个特征为0，就走这个默认分支。这样，训练时不必考虑这些0元素，大大提高了运算速度。**陈天奇的实验表明，此方法在稀疏数据上可以提高50倍。

数据的预排序和分块存储

分叉的时候为了判断分叉点，需要对每个特征进行排序。这个步骤是要重复多次的，因此XGBoost在训练之前预先对数据进行每一列做了排序，并按列存储到内存中。在分布式环境下，可以进行分块存储。

减少读写相关，提高Cache命中率

由于预排序的数据是按列存储的，但训练时并不总是按列读取和写回，在需要按行读写的时候，将需要的行预先收集到一块连续内存上，再进行计算。这样由于是连续内存地址，可以提高Cache命中率，从而提高了运算速度。

数据量大时，提高硬盘吞吐率

当数据量很大，不能装入内存时，需要将一部分数据放在硬盘里。然而硬盘读写速度慢，会严重影响计算效率。XGBoost使用了两种方法提高吞吐率，一个是对存储的内容进行压缩，读取时再进行解压，这相当于在读取代价和解压代价之间做了一个权衡。另一个方法是做数据分片，即在多块硬盘上存储数据，然后同时读写，从而提高读写速度。