XGBoost算法的原理总结

最近在网上查询阅读了关于XGBoost的文章和博客，便对自己的理解做了总结。XGBoost(eXtreme Gradient Boosting)全名叫极端梯度提升，是集成学习方法中的王牌，在绝大数的回归和分类问题上表现的强悍，在这里梳理下XGBoost的算法原理。

1.最优模型的构建方法

构建最优模型的一般方法是最小化训练数据的损失函数，我们用字母 L表示，如下式： 式（1）称为经验风险最小化，训练得到的模型复杂度较高。当训练数据较小时，模型很容易出现过拟合问题。 因此，我们可以利用添加正则项的结构风险最小化模型： 结构风险最小化模型在考虑了损失函数最小化的基础上，控制了模型复杂度，用来避免过拟合的情况，往往对训练数据以及测试数据都有较好的预测效果。

2.Boosting方法的回归思想

Boosting法是结合多个弱学习器给出最终的学习结果，不管任务是分类或回归，我们都用回归任务的思想来构建最优Boosting模型 。 回归思想：把每个弱学习器的输出结果当成连续值，这样做的目的是可以对每个弱学习器的结果进行累加处理，且能更好的利用损失函数来优化模型。 假设$f^t(x_i)$是第 $t$ 轮弱学习器的输出结果,${\hat{y}}_i^t$是模型的输出结果，而$y_i$是实际输出结果，表达式如下： 上面两式就是加法模型，都默认弱学习器的输出结果是连续值。

3.分类任务的回归思想

根据2.1式的结果，得到最终的分类器： 分类的损失函数一般选择指数函数或对数函数，这里假设损失函数为对数函数，学习器的损失函数是 若实际输出结果yi=1，则： 对${\hat{y}}_i^t$求梯度，得： 负梯度方向是损失函数下降最快的方向，（2.6）式取反的值大于0，因此弱学习器是往增大${\hat{y}}_i^t$的方向迭代的，当样本的实际标记 $yi=1$ 时，模型输出结果${\hat{y}}_i^t$随着迭代次数的增加而增加，模型的损失函数相应的减小；当样本的实际标记 $yi=-1$时，模型输出结果${\hat{y}}_i^t$随着迭代次数的增加而减小，模型的损失函数相应的减小 。这就是加法模型的原理所在，通过多次的迭代达到减小损失函数的目的。

4.XGBoost算法的目标函数推导

XGBoost对应的模型包含了多个CART树，因此，模型的目标函数为： （3.1）式是正则化的损失函数，等式右边第一部分是模型的训练误差，第二部分是正则化项，这里的正则化项是K棵树的正则化项相加而来的。 第K棵CART树,将输入样本映射到一个确定的叶子节点上，记为$f_k(x)$,$q(x)$表示输出的叶子节点序号，$w_{q(x)}$表示对应叶子节点序号的值。即： 树的复杂度定义： XGBoost法对应的模型包含了多棵CART树，定义每棵树的复杂度： 其中$T$为叶子节点的个数，$||w||$为叶子节点向量的模 。$\gamma$表示节点切分的难度，$\lambda$表示$L2$正则化系数。 如下例树的复杂度表示： 目标函数推导: 根据（3.1）式，共进行t次迭代的学习模型的目标函数为： 泰勒公式的二阶导近似表示： 令$f_t(x_i)$为Δx，则（3.5）式的二阶近似展开： 其中： $l(y_i,{\hat{y}}^{(t-1)})$表示前$t-1$棵树组成的学习模型的预测误差，$gi$和$hi$分别表示预测误差对当前模型的一阶导和二阶导 ，当前模型往预测误差减小的方向进行迭代。 忽略（3.8）式常数项，并结合（3.4）式，得： 通过（3.2）式简化（3.9）式： （3.10）式第一部分是对所有训练样本集进行累加，因为所有样本都是映射为树的叶子节点，我们换种思维，从叶子节点出发，对所有的叶子节点进行累加，得： 令 $Gj$ 表示映射为叶子节点$j$ 的所有输入样本的一阶导之和，同理，$Hj$表示二阶导之和。 得： 对于第$t$ 棵CART树的某一个确定结构（可用$q(x)$表示），其叶子节点是相互独立的，$Gj$和$Hj$是确定量，因此，（3.12）可以看成是关于叶子节点的一元二次函数 。最小化（3.12）式，得： 得到最终的目标函数： （3.14）也称为打分函数(scoring function)，它是衡量树结构好坏的标准，值越小，代表这样的结构越好 。我们用打分函数选择最佳切分点，从而构建CART树。 CART回归树的构建方法

5.CART回归树的构建方法

上节推导得到的打分函数是衡量树结构好坏的标准，因此，可用打分函数来选择最佳切分点。首先确定样本特征的所有切分点，对每一个确定的切分点进行切分，切分好坏的标准如下：

$Gain$表示单节点$obj\ast$与切分后的两个节点的树$obj\ast$之差，遍历所有特征的切分点，找到最大$Gain$的切分点即是最佳分裂点，根据这种方法继续切分节点，得到CART树。若 $\gamma$ 值设置的过大，则$Gain$为负，表示不切分该节点，因为切分后的树结构变差了。$\gamma$值越大，表示对切分后$obj$下降幅度要求越严，这个值可以在XGBoost中设定。

6.XGBoost与GDBT的区别

XGBoost生成CART树考虑了树的复杂度，GDBT未考虑，GDBT在树的剪枝步骤中考虑了树的复杂度。传统GBDT以CART作为基分类器，xgboost还支持线性分类器，这个时候xgboost相当于带L1和L2正则化项的逻辑斯蒂回归（分类问题）或者线性回归（回归问题）。XGBoost是拟合上一轮损失函数的二阶导展开，GDBT是拟合上一轮损失函数的一阶导展开，因此，XGBoost的准确性更高，且满足相同的训练效果，需要的迭代次数更少。顺便提一下，xgboost工具支持自定义代价函数，只要函数可一阶和二阶求导列抽样（column subsampling）。xgboost借鉴了随机森林的做法，支持列抽样，不仅能降低过拟合，还能减少计算，这也是xgboost异于传统gbdt的一个特性。对缺失值的处理。对于特征的值有缺失的样本，xgboost可以自动学习出它的分裂方向。XGBoost与GDBT都是逐次迭代来提高模型性能，但是XGBoost在选取最佳切分点时可以开启多线程进行，大大提高了运行速度。xgboost工具支持并行。boosting不是一种串行的结构吗?怎么并行的？注意xgboost的并行不是tree粒度的并行，xgboost也是一次迭代完才能进行下一次迭代的（第t次迭代的代价函数里包含了前面t-1次迭代的预测值）。xgboost的并行是在特征粒度上的。我们知道，决策树的学习最耗时的一个步骤就是对特征的值进行排序（因为要确定最佳分割点），xgboost在训练之前，预先对数据进行了排序，然后保存为block结构，后面的迭代中重复地使用这个结构，大大减小计算量。这个block结构也使得并行成为了可能，在进行节点的分裂时，需要计算每个特征的增益，最终选增益最大的那个特征去做分裂，那么各个特征的增益计算就可以开多线程进行。可并行的近似直方图算法。树节点在进行分裂时，我们需要计算每个特征的每个分割点对应的增益，即用贪心法枚举所有可能的分割点。当数据无法一次载入内存或者在分布式情况下，贪心算法效率就会变得很低，所以xgboost还提出了一种可并行的近似直方图算法，用于高效地生成候选的分割点。

参考 [1]:XGBoost:A Scalable Tree Boosting System [2]:XGBoost浅入浅出 [3]:XGBoost算法原理小结