背景

在看Xgboost之前，先看看笔者写的AdaBoost 和GBDT。

AdaBoost 关注的是哪些错误分类的样本，每次加大误分类样本的权重，训练新的分类器。

GBDT关注的是分类器的残差，每一次训练分类器都是为了不断减小这个残差。

Xgboost可以说是GBDT算法在工程上的一种实现。如下图所示：

假定这是一家人中每个人想玩游戏的意愿。小男孩玩游戏的意愿是3，爷爷玩游戏的意愿是-3。xgboost 解决这个问题的思路是：先训练第一颗决策树，预测小男孩想玩的意愿是2；再训练第二棵决策树，预测小男孩想玩的意愿是0.9，此时的预测结果是二者之和2.9。这就是xgboost的预测过程：不断拟合残差。当迭代次数达到上限或者残差不断减小，算法停止。

二者的区别在于降低残差的方式不同。GBDT降低残差是通过不断加入新树实现。而XGBoost则可以人为定义损失函数，只需要知道该loss function对参数的一阶、二阶导数便可以进行boosting，其进一步增大了模型的泛化能力，其贪婪法寻找添加树的结构以及loss function中的损失函数与正则项等一系列策略也使得XGBoost预测更准确。

目标函数

XGBoost 算法采用分步向前加法模型，与其他boosting 算法不同的是不需要再计算弱学习器的系数，其加法模型如下：
$\hat y_i = \sum_{t=1}^k f_t(x_i)$y^​i​=t=1∑k​ft​(xi​)
其中，$f_k$fk​ 为第 k 个基模型，$\hat y_i$y^​i​ 为第 i 个样本的预测值，其损失函数如下：
$L = \sum_{i=1}^n l(y_i,\hat y_i)$L=i=1∑n​l(yi​,y^​i​)
损失函数代表了模型的偏差，而一个好的模型由方差和偏差共同决定。XGBoost同时还考虑了模型的方差，方差通过模型的复杂度来控制。所以最终的目标函数由损失函数L与抑制模型复杂度的正则项Ω组成
$Obj =\sum_{i=1}^n l(y_i,\hat y_i) + \sum_{t=1}^k \Omega(f_t)$Obj=i=1∑n​l(yi​,y^​i​)+t=1∑k​Ω(ft​)
其中$\Omega(f_t)$Ω(ft​)是正则化项：
$\Omega(f_t)=\gamma T_t+\frac{\lambda}{2}\sum_{j=1}^{J}\omega_{j}^2$Ω(ft​)=γTt​+2λ​j=1∑J​ωj2​
$T_t$Tt​：叶子节点数， $w_j$wj​：叶子上的节点权重，$\gamma,\lambda$γ,λ是超参数。

注：当正则化为零时，目标回归到传统的梯度提升树。正则化起到了抑制模型复杂度的作用，从而避免了过拟合。

为了进一步理解这个正则化项，请看下图：

由公式可知模型的复杂度是由决策树的叶子节点数量和权重所共同决定的。

接下来一步一步的对这个目标函数$Obj$Obj 进行化简。主要由以下四步组成：

（1）原始目标函数Obj

（2）原始目标函数Obj的泰勒展开

（3）具体化目标函数的泰勒展开细节

（4）求解目标函数中的$w_j $，并带入目标函数，得到最终版目标函数

（1）原始目标函数Obj

提升（boosting）模型是前向加法模型，设第$t-1$t−1步模型的输出为$\hat y_i^{t-1}$y^​it−1​，则第$t$t步模型的第$i$i个样本$x_i$xi​ 的预测为：
$\hat y_i ^t = \hat y_i^{t-1} + f_t(x_i)$y^​it​=y^​it−1​+ft​(xi​)
$f_t(x_i)$ft​(xi​)是需要新加入的模型。

将$\hat y_i ^t$y^​it​ 带入Obj，则有：
$\begin{aligned} Obj^{t} &=\sum_{i=1}^n l(y_i,\hat y_i^t) + \sum_{i=1}^t \Omega(f_t) \\ &=\sum_{i=1}^n l\left(y_i, \hat y_i^{t-1} + f_t(x_i)\right) + \sum_{i=1}^t \Omega(f_t) \end{aligned}$Objt​=i=1∑n​l(yi​,y^​it​)+i=1∑t​Ω(ft​)=i=1∑n​l(yi​,y^​it−1​+ft​(xi​))+i=1∑t​Ω(ft​)​
我们的目标是：求解当前的树$f_t(x_i)$ft​(xi​)，使得Obj 最小。 也就是：新生成的决策树要不断地拟合残差。

（2）原始目标函数Obj的泰勒展开

回顾Taylor公式：
$f(x+\triangle x) \approx f(x) + f^{'}(x) \triangle x + \frac{1}{2}f^{''}(x) \triangle x^2$f(x+△x)≈f(x)+f′(x)△x+21​f′′(x)△x2
对于目标函数中的$l\left(y_i, \hat y_i^{t-1} + f_t(x_i)\right)$l(yi​,y^​it−1​+ft​(xi​))，将$\hat y_i^{t-1}$y^​it−1​ 视为$x$x，$ f_t(x_i)$视为$视为\triangle x$ ,那么目标函数可以写成：
$\begin{aligned} Obj^{(t)} &=\sum_{i=1}^n l\left(y_i, \hat y_i^{t-1} + f_t(x_i)\right) + \sum_{i=1}^t \Omega(f_t)\\ & \approx \sum_{i=1}^{N}\left(l(y_i,\hat y_i^{t-1})+g_if_t(x_i)+\frac{1}{2}h_if_t^2(x_i)\right)+\sum_{i=1}^t \Omega(f_t) \end{aligned}$Obj(t)​=i=1∑n​l(yi​,y^​it−1​+ft​(xi​))+i=1∑t​Ω(ft​)≈i=1∑N​(l(yi​,y^​it−1​)+gi​ft​(xi​)+21​hi​ft2​(xi​))+i=1∑t​Ω(ft​)​
其中：
$g_i =\frac{\partial l(y_i,\,\hat y_i^{t-1})}{\partial \hat y_i^{t-1}}$gi​=∂y^​it−1​∂l(yi​,y^​it−1​)​

$h_i =\frac{\partial^2 l(y_i,\,\hat y_i^{t-1})}{\partial \hat y_i^{t-1}}$hi​=∂y^​it−1​∂2l(yi​,y^​it−1​)​

由于$y_i,\hat y_i^{t-1}$yi​,y^​it−1​ 均为已知值，所以 $l(y_i,\hat y_i^{t-1})$l(yi​,y^​it−1​) 是常数。对优化目标函数的优化不会产生影响，所以舍去这一项：
KaTeX parse error: No such environment: align at position 8: \begin{̲a̲l̲i̲g̲n̲}̲ Obj^{(t)} …

举个例子：假设损失函数是平方损失函数：
$\sum_{i=1}^n \left(y_i-( \hat y_i^{t-1} + f_t(x_i))\right)^2$i=1∑n​(yi​−(y^​it−1​+ft​(xi​)))2
则对于每一个样本：
$g_i =\frac{\partial (y_i-\hat y_i^{t-1})^2}{\partial \hat y_i^{t-1}} = 2(\hat y_i^{t-1} -y_i)\\ h_i =\frac{\partial^2 (y_i-\hat y_i^{t-1})^2}{\partial \hat y_i^{t-1}}=2$gi​=∂y^​it−1​∂(yi​−y^​it−1​)2​=2(y^​it−1​−yi​)hi​=∂y^​it−1​∂2(yi​−y^​it−1​)2​=2
所以，每一步损失函数的一阶导和二阶导是均是已知数。然后最优化目标函数，就可以得到每一步的 f(x) ，最后根据加法模型得到一个整体模型。

（3）具体化目标函数的泰勒展开细节。

此时目标函数已经变为：
$\begin{aligned} Obj^{(t)} & \approx \sum_{i=1}^{N}\left(g_if_t(x_i)+\frac{1}{2}h_if_t^2(x_i)\right)+\sum_{i=1}^t \Omega(f_t) \end{aligned}$Obj(t)​≈i=1∑N​(gi​ft​(xi​)+21​hi​ft2​(xi​))+i=1∑t​Ω(ft​)​
这里的变量$f_t(x_i)$ft​(xi​) 表示训练样本$x_i$xi​ 经过决策树模型的预测值。把决策树模型定义成$f_t(x_i)=w_q(x)$ft​(xi​)=wq​(x)，其中$q(x)$q(x) 代表了该样本在哪个叶子节点上，$w$w 表示叶子结点的权重（也就是决策树的预测值：小男孩想玩游戏的意愿 2），所以$w_q(x)$wq​(x)代表每个样本的预测值。所以：
$\sum_{i=1}^{N}\left[g_if_t(x_i)+\frac{1}{2}h_if_t^2(x_i)\right]=\sum_{i=1}^{N}\left[g_iw_{q(x_i)}+\frac{1}{2}h_iw_{q(x_i)}^2\right] = \sum_{j=1}^{T}\left[(\sum _{i \in I_j}g_i)w_{j}+\frac{1}{2}(\sum _{i \in I_j}h_i)w_{j}^2\right]$i=1∑N​[gi​ft​(xi​)+21​hi​ft2​(xi​)]=i=1∑N​[gi​wq(xi​)​+21​hi​wq(xi​)2​]=j=1∑T​⎣⎡​(i∈Ij​∑​gi​)wj​+21​(i∈Ij​∑​hi​)wj2​⎦⎤​
**T : 叶子结点的总数。**由于一个叶子结点有多个样本，所以每一个叶子结点的一阶导数之和为$\sum _{i \in I_j}g_i$∑i∈Ij​​gi​，同理有二阶导之和$\sum _{i \in I_j}h_i$∑i∈Ij​​hi​ ，$I_j$Ij​ 表示某棵树第$j$j个叶子节点上的训练样本 , $w_j$wj​ 为第$j$j个叶子节点的输出值。

所以，目标函数变为：
$\begin{aligned} Obj^{(t)} & \approx \sum_{i=1}^{N}\left(g_if_t(x_i)+\frac{1}{2}h_if_t^2(x_i)\right)+ \Omega(f_t) \\ &=\sum_{j=1}^{T}\left[(\sum _{i \in I_j}g_i)w_{j}+\frac{1}{2}(\sum _{i \in I_j}h_i)w_{j}^2\right] + \gamma T+\frac{\lambda}{2}\sum_{j=1}^{J}\omega_{j}^2 \\ &= \sum_{j=1}^{T}\left[(\sum _{i \in I_j}g_i)w_{j}+\frac{1}{2}(\sum _{i \in I_j}h_i + \lambda)w_{j}^2\right] + \gamma T \end{aligned}$Obj(t)​≈i=1∑N​(gi​ft​(xi​)+21​hi​ft2​(xi​))+Ω(ft​)=j=1∑T​⎣⎡​(i∈Ij​∑​gi​)wj​+21​(i∈Ij​∑​hi​)wj2​⎦⎤​+γT+2λ​j=1∑J​ωj2​=j=1∑T​⎣⎡​(i∈Ij​∑​gi​)wj​+21​(i∈Ij​∑​hi​+λ)wj2​⎦⎤​+γT​

这里的$I_j = \{i|q(x_i)=j\}$Ij​={i∣q(xi​)=j}为第$j$j个叶子节点的样本集合。

设$G_{j}=\sum_{i \in I_{j}} g_{j},\,H_{j}=\sum_{i \in I_{j}} h_{j}$Gj​=∑i∈Ij​​gj​,Hj​=∑i∈Ij​​hj​，所以：
$Obj^{(t)}= \sum_{j=1}^{T}\left[G_jw_{j}+\frac{1}{2}(H_j + \lambda)w_{j}^2\right] + \gamma T$Obj(t)=j=1∑T​[Gj​wj​+21​(Hj​+λ)wj2​]+γT
（4）求解目标函数中的$w_j$wj​，并带入目标函数，得到最终版目标函数。

因为$G_{j}、H_{j}$Gj​、Hj​ 求解均为已知值。只有最后一颗树的叶子节点$w_j$wj​ 的值是不确定的。要求得$w_j$wj​ 使得目标函数$Obj$Obj 极小化。所以将目标函数对$w_j$wj​ 求一阶导，令其等于0，即：
$G_j+(H_j + \lambda)w_{j} = 0$Gj​+(Hj​+λ)wj​=0
解得：
$w_j^* = -\frac{G_j}{H_j+\lambda}$wj∗​=−Hj​+λGj​​
将这个结果带入目标函数Obj，得：
$Obj =-\frac{1}{2}\sum_{j=1}^{T}[\frac{G_{j}^2}{H_{j}+\lambda}]+\gamma T$Obj=−21​j=1∑T​[Hj​+λGj2​​]+γT
这就是XGboost模型得目标函数得最终版本。

解释：这个Obj又叫结构分数，类似于信息增益，可以对树的结构进行打分。当指定一个树的结构时，在目标函数上最多能减少多少。 下面就是一个计算例子：

首先，遍历树的叶子节点，得到所有样本的$h_i,g_i$hi​,gi​，进而计算出$G,H$G,H。然后带入Obj计算。

注意两个细节：

（1）每个样本的$h_i,g_i$hi​,gi​ 之间没有关系，可以并行计算。加快了训练速度。

（2） $h_i,g_i$hi​,gi​ 的计算要求损失函数二阶可导。

这个Obj 的作用是在树建立好以后，其值越小，所生成的树越好。那么在建立树的时候应该以什么样的准则去建立一棵树呢？用什么样的策略逐步学习出最佳的树的结构？

XGboost所生成的树是CART树 (采用的是二叉树)。开始时，全部样本都在一个叶子结点上，然后叶子节点不断二分裂，逐渐生成一棵树。问题是应该在哪个特征的哪个点上进行二分裂。也就是如何寻找最优的切分点。

最优切分点算法

我们知道基本的决策树算法：ID3、C4.5、CART的特征选择的准则分别是信息增益、信息增益比、基尼指数。特征选择的过程也就是最优切分的过程。而Xgboost也有类似于上述的信息选择的准则的东西来计算每个特征点上分裂之后的收益。

假设在某一节点未进行特征分裂前的目标函数为：
$Obj_1 =-\frac{1}{2}[\frac{(G_{L}+G_R)^2}{H_{L}+H_{R+}\lambda}]+\gamma$Obj1​=−21​[HL​+HR+​λ(GL​+GR​)2​]+γ
分裂后的目标函数为：
$Obj_2 =-\frac{1}{2}[\frac{G_{L}^2}{H_{L}+ \lambda} +\frac{G_{R}^2}{H_{R}+ \lambda} ] +2\gamma$Obj2​=−21​[HL​+λGL2​​+HR​+λGR2​​]+2γ
目标函数的收益为：
$Gain = \frac{1}{2}\left[\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}\right] - \gamma$Gain=21​[HL​+λGL2​​+HR​+λGR2​​−HL​+HR+​λ(GL​+GR​)2​]−γ
这个目标函数的收益也是特征重要性输出的依据。

有了这个衡量收益的标准，就可以来看看最优切分点的划分算法了:

注意两个个细节：

（1）针对每个特征，把属于该节点的训练样本根据该特征值进行升序排序，通过线性扫描的方式依次计算分裂收益，进而决定该特征的最佳分类点。不同特征的收益计算是并行的，这也决定了xgboost计算速度十分的快。

（2）选择收益最大的特征作为分裂特征，用该特征的最佳分裂点作为分裂位置，在该节点上分裂出左右两个新的叶节点，并为每个新节点关联对应的样本集。

举例说明：

回顾一家人中每个人想玩游戏的意愿为例的Xgboost过程，先把年龄进行一个排序，如下图：

从左到右扫描，对每一个切分点a，计算$G_L,G_R$GL​,GR​，然后计算得分，得分最大的年龄特征就是最优切分点。

这里还有一个细节：XGboost的切分操作和普通的决策树切分过程不一样，普通的决策树在切分的时候不考虑树的复杂度，所以才有了后续的剪枝操作。而xgboost在切分的时候就已经考虑了树的复杂度（$\gamma$γ 用于控制模型的复杂的）。所以，它不需要进行单独的剪枝操作。

这就是xgboost贪心建树的过程，遍历所有的特征以及其分割点，每次选最好的那个。当数据量太大时，这个过程计算量太大了。所以这里用一种近似分割的方式：选定一些候选分裂点，遍历这些点，从而决定最佳分裂点。如何选定这些候选分裂点呢？

作者这里采用了一种对loss的影响权重的等值percentiles（百分比分位数）划分算法（Weight Quantile Sketch）

作者进行候选点选取的时，考虑的是想让loss在左右子树上分布的均匀一些，而不是样本数量的均匀，因为每个样本对降低loss的贡献可能不一样，按样本均分会导致分开之后左子树和右子树loss分布不均匀，取到的分位点会有偏差。如下图所示：

这里有两个细节：

（1）$h_i$hi​是损失函数在样本$i$i处的二阶导数，为啥它就能代表第个$i$i样本的权值啊？

目标函数经过一系列的化简，得到下面这个结果：
$Obj \approx \sum_{i=1}^{N} \frac{1}{2}h_{i} \left( f_t(x_i)-(-\frac{g_{i}}{h_{i}}) \right)^2 +\Omega(f_t)+Constant$Obj≈i=1∑N​21​hi​(ft​(xi​)−(−hi​gi​​))2+Ω(ft​)+Constant
后面的每一个分类器都是在拟合每个样本的一个残差 $-\frac{g_i}{h_i}$−hi​gi​​, 很明显，前面的系数$h_i$hi​ 可以看做计算残差时某个样本的重要性,即每个样本对降低loss的贡献程度。

ps: Xgboost引入了二阶导之后，相当于在模型降低残差的时候给各个样本根据贡献度不同加入了一个权重，这样就能更好的加速拟合和收敛，GBDT只用到了一阶导数，这样只知道梯度大的样本降低残差效果好，梯度小的样本降低残差不好，但是好与不好的这个程度，在GBDT中无法展现。而xgboost这里就通过二阶导可以展示出来，这样模型训练的时候就有数了。

（2）如何进行分箱

定义数据集$D_k=\{(x_{1k}, h_1), (x_{2k}, h_2),...,(x_{nk}, h_n)\}$Dk​={(x1k​,h1​),(x2k​,h2​),...,(xnk​,hn​)}代表每个训练样本第k个特征的取值和二阶梯度值，定义一个排名函数
$r_k(z) = \frac{1}{\sum_{(x,h)\in D_k} h}\; \sum_{(x,h)\in D_k, x<z}h$rk​(z)=∑(x,h)∈Dk​​h1​(x,h)∈Dk​,x<z∑​h
上面的式子中，z表示特征值小于z的样本的贡献度占比。

对于上图的第一个划分点，$r_k(z)=\frac{1}{3}$rk​(z)=31​。设有$l$l个划分点：$\{s_{k1}, s_{k2},..,s_{kl}\}${sk1​,sk2​,..,skl​}，目标是让相邻的划分点的贡献度都差不多，即指定ε 控制每个桶中样本贡献度比例的大小，使得：
$|r_k(s_{kj})-r_k(s_{kj+1})|<ε$∣rk​(skj​)−rk​(skj+1​)∣<ε
例如，设定$ε=\frac{1}{3}$ε=31​，那么划分点就是1/3分位点。上面样本贡献度总和是1.8， 那么每个箱贡献度就是 1.8 * 1/3 = 0.6，分为3（$\frac{1}{ε}$ε1​）个箱。

上面的过程，就是先计算一下总的贡献度， 然后指定ε，两者相乘得到每个桶的贡献度进行分桶即可。这样我们就可以确定合理的候选切分点，然后进行分箱了。

Shrinkage(收缩过程)

核心思想：每次走一小步逐渐逼近结果的效果，要比每次迈一大步很快逼近结果的方式更容易避免过拟合。即它不完全信任每一个棵残差树，它认为每棵树只学到了真理的一小部分，累加的时候只累加一小部分，通过多学几棵树弥补不足。用方程来看更清晰，即给每棵数的输出结果乘上一个步长$\eta$η（收缩率）

缺失值处理

xgboost是如何处理缺失值呢？看下面这个算法过程：

即XGBoost没有假设缺失值一定进入左子树还是右子树，第一次假设特征k所有有缺失值的样本都走右子树，第二次假设特征k所有缺失值的样本都走左子树。分别计算最终的收益$\frac{1}{2}\left[\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}\right] - \gamma$21​[HL​+λGL2​​+HR​+λGR2​​−HL​+HR+​λ(GL​+GR​)2​]−γ ，哪个大就把它放到哪棵子树上。

优缺点

xgboost相比于GBDT有以下的优点：

• 精度更高：GBDT只用到一阶泰勒， 而xgboost对损失函数进行了二阶泰勒展开， 一方面为了增加精度， 另一方面也为了能够自定义损失函数，二阶泰勒展开可以近似大量损失函数
• 灵活性更强：GBDT以CART作为基分类器，而Xgboost不仅支持CART，还支持线性分类器，另外，Xgboost支持自定义损失函数，只要损失函数有一二阶导数。
• 正则化：xgboost在目标函数中加入了正则，用于控制模型的复杂度。有助于降低模型方差，防止过拟合。正则项里包含了树的叶子节点个数，叶子节点权重的L2范式。
• Shrinkage（缩减）：相当于学习速率。这个主要是为了削弱每棵树的影响，让后面有更大的学习空间，学习过程更加的平缓
• 列抽样：这个就是在建树的时候，不用遍历所有的特征了，可以进行抽样，一方面简化了计算，另一方面也有助于降低过拟合
• 缺失值处理：这个是xgboost的稀疏感知算法，加快了节点分裂的速度
• 并行化操作：块结构可以很好的支持并行计算

缺点：

• 时间复杂度高：虽然利用了预排序和近似算法可以降低寻找最优分裂点的计算量，但在节点分裂过程中仍需要遍历整个数据集。
• 空间复杂度高：预排序过程的空间复杂度过高，不仅需要存储特征值，还需要存储特征对应样本梯度统计值的索引，相当于消耗了两倍的内存。

参考文献：

xgboost论文原文

XGBoost算法梳理

算法理论+实战之Xgboost算法