背景

讲XGBoost之前，先引入一个实际问题，即预测一家人每个人玩游戏的意愿值：

如果我们用XGBoost解决这个问题，步骤是：首先要训练出来第一棵决策树， 预测了一下小男孩想玩游戏的意愿是2， 然后发现离标准答案差一些，再训练出第二棵决策树， 预测了一下小男孩想玩游戏的意愿是0.9， 最后两个相加就是最终的答案2.9。也就是说，XGBoost是把训练出来的弱分类结果进行累加当作最终的结论。

XGBoost的思想和GBDT有相似之处，比较大的不同就是目标函数的定义，即XGBoost聚焦与标准答案的残差。准确来说它是一种GBDT的工业级实现。其主要原理是在GBDT的基础上，在损失函数加入正则化部分，并且每一轮迭代对损失函数做二阶泰勒展开，加快对损失函数的优化速度。

XGBoost算法也是采用分步前向加性模型，只不过与GBDT不同，在每次迭代中生成弱学习器后不再需要计算一个系数。XGBoost 是由 k 个基模型组成的一个加法运算式：
$\hat y_i = \sum^k_{t=1}f_t(x_i)$y^​i​=t=1∑k​ft​(xi​)
其中，$f_t$ft​是第t个模型，损失函数可以由真实值$y_i$yi​和预测值$\hat y_i$y^​i​表示：
$L = \sum^N_{t=1}l(y_i, \hat y_i)$L=t=1∑N​l(yi​,y^​i​)
其中N是样本个数。

定义损失函数

对于第m棵树而言，XGBoost的损失函数在GBDT损失函数$L(y,\,f_{m-1}(x)+h_m(x))$L(y,fm−1​(x)+hm​(x))的基础上，加入了如下的正则化：
$\Omega(h_m)=\gamma J+\frac{\lambda}{2}\sum_{j=1}^{J}\omega_{mj}^2$Ω(hm​)=γJ+2λ​j=1∑J​ωmj2​
这里的 $J$J 是叶子节点的个数，而 $\omega_{mj}$ωmj​ 是第 $j$j 个叶子节点的最优值。这里的 $\omega_{mj}$ωmj​ 和在GBDT里面使用的 $c_{mj}$cmj​ 其实是一个意思，只是XGBoost论文里面使用 $\omega$ω 符号表示叶子区域的值，这里为了和论文保持一致。最终，XGBoost的损失函数可以表示为：
$L_m=\sum_{i=1}^{N}L(y_i, f_{m-1}(x_i)+h_m(x_i))+\gamma J+\frac{\lambda}{2}\sum_{j=1}^{J}\omega_{mj}^2$Lm​=i=1∑N​L(yi​,fm−1​(xi​)+hm​(xi​))+γJ+2λ​j=1∑J​ωmj2​
我们要极小化上面这个损失函数，得到第$m$m个决策树最优的所有$J$J个叶子节点对应的区域和每个叶子节点区域的最优解$\omega_{mj}$ωmj​。

XGBoost在损失函数优化方面做了一些优化，基于损失函数的二阶泰勒展开式来求解。具体的，将$f_{m-1}(x_i)$fm−1​(xi​)视为参数，将$h_m(x_i)$hm​(xi​)视为参数的增量，现在来看看这个损失函数的二阶泰勒展开式：
$\begin{aligned} L_m &=\sum_{i=1}^{N}L(y_i, f_{m-1}(x_i)+h_m(x_i))+\gamma J+\frac{\lambda}{2}\sum_{j=1}^{J}\omega_{mj}^2 \\\\ & \approx \sum_{i=1}^{N}\left(L(y_i, f_{m-1}(x_i))+\frac{\partial L(y_i,\,f_{m-1}(x_i))}{\partial f_{m-1}(x_i)}h_m(x_i)+\frac{1}{2}\frac{\partial^2 L(y_i,\,f_{m-1}(x_i))}{\partial^2 f_{m-1}(x_i)}h_m^2(x_i)\right)+\gamma J+\frac{\lambda}{2}\sum_{j=1}^{J}\omega_{mj}^2 \end{aligned}$Lm​​=i=1∑N​L(yi​,fm−1​(xi​)+hm​(xi​))+γJ+2λ​j=1∑J​ωmj2​≈i=1∑N​(L(yi​,fm−1​(xi​))+∂fm−1​(xi​)∂L(yi​,fm−1​(xi​))​hm​(xi​)+21​∂2fm−1​(xi​)∂2L(yi​,fm−1​(xi​))​hm2​(xi​))+γJ+2λ​j=1∑J​ωmj2​​
为方便公式表达，记：
$g_{mi}=\frac{\partial L(y_i,\,f_{m-1}(x_i))}{\partial f_{m-1}(x_i)}\\ \,h_{mi}=\frac{\partial^2 L(y_i,\,f_{m-1}(x_i))}{\partial^2 f_{m-1}(x_i)}$gmi​=∂fm−1​(xi​)∂L(yi​,fm−1​(xi​))​hmi​=∂2fm−1​(xi​)∂2L(yi​,fm−1​(xi​))​
于是损失函数简化为：
$L_m\approx \sum_{i=1}^{N}\left(L(y_i, f_{m-1}(x_i))+g_{mi}h_m(x_i)+h_{mi}h_m^2(x_i)\right)+\gamma J+\frac{\lambda}{2}\sum_{j=1}^{J}\omega_{mj}^2$Lm​≈i=1∑N​(L(yi​,fm−1​(xi​))+gmi​hm​(xi​)+hmi​hm2​(xi​))+γJ+2λ​j=1∑J​ωmj2​
对于第$m$m轮的迭代，损失函数里面$L(y_i,f_{m-1}(x_i))$L(yi​,fm−1​(xi​))为常数项，对最小化无影响，可以直接去掉。

若定义$I_j=\{i|q(x_i)=j\}$Ij​={i∣q(xi​)=j}为第$j$j个叶子节点的样本集合，经过$M$M轮迭代完毕以后每个决策树（弱学习器）的第$j$j个叶子节点的取值(也就是该叶子节点对应的预测值)最终会是同一个值$\omega_{mj}$ωmj​，因此，可以对损失函数继续化简：
$\begin{aligned} L_m &\approx \sum_{i=1}^{N}\left(g_{mi}h_m(x_i)+h_{mi}h_m^2(x_i)\right)+\gamma J+\frac{\lambda}{2}\sum_{j=1}^{J}\omega_{mj}^2 \\\\ & =\sum_{j=1}^{J}\left(\sum_{x_i \in R_{mj}}g_{mj}\omega_{mj}+\frac{1}{2}\sum_{x_i \in R_{mj}}h_{mj}\omega_{mj}^2\right)+\gamma J+\frac{\lambda}{2}\sum_{j=1}^{J}\omega_{mj}^2 \\\\ & = \sum_{j=1}^{J}[(\sum_{x_i \in R_{mj}}g_{mj})\omega_{mj}+\frac{1}{2}(\sum_{x_i \in R_{mj}}h_{mj}+\lambda)\omega_{mj}^2]+\gamma J \end{aligned}$Lm​​≈i=1∑N​(gmi​hm​(xi​)+hmi​hm2​(xi​))+γJ+2λ​j=1∑J​ωmj2​=j=1∑J​⎝⎛​xi​∈Rmj​∑​gmj​ωmj​+21​xi​∈Rmj​∑​hmj​ωmj2​⎠⎞​+γJ+2λ​j=1∑J​ωmj2​=j=1∑J​[(xi​∈Rmj​∑​gmj​)ωmj​+21​(xi​∈Rmj​∑​hmj​+λ)ωmj2​]+γJ​
同样为了方便表示，记：
$G_{mj}=\sum_{x_i \in R_{mj}} g_{mj}\\ H_{mj}=\sum_{x_i \in R_{mj}} h_{mj}$Gmj​=xi​∈Rmj​∑​gmj​Hmj​=xi​∈Rmj​∑​hmj​
于是有：
$L_m=\sum_{j=1}^{J}[(G_{mj}\omega_{mj}+\frac{1}{2}(H_{mj}+\lambda)\omega_{mj}^2]+\gamma J$Lm​=j=1∑J​[(Gmj​ωmj​+21​(Hmj​+λ)ωmj2​]+γJ
好，现在简化的损失函数有了，现在又多了两个问题。

确定叶节点的输出

第一个问题，前面我们假设第m棵树的第 j 个叶子节点的输出值为$\omega_{mj}$ωmj​，这个数值具体是多少，怎么求？

可以这么求，将损失函数对$\omega_{mj}$ωmj​求偏导，令其为0即可得到最佳的$\omega_{mj}$ωmj​：
$\omega_{mj}= - \frac{G_{mj}}{H_{mj}+\lambda}$ωmj​=−Hmj​+λGmj​​
将上面的式子代入目标函数，又能进一步化简得到：
$L_m=-\frac{1}{2}\sum_{j=1}^{J}[\frac{G_{mj}^2}{H_{mj}+\lambda}]+\gamma J$Lm​=−21​j=1∑J​[Hmj​+λGmj2​​]+γJ
式子中的G和H，就需要明确的给出损失函数才能求得。给定不同的树，$L_m$Lm​的值也会不同，也就是说，我们可以用$L_m$Lm​ 来给一颗树打分，作用类似于CART算法中的Gini值。

有了这个，我们就知道这棵树建的好不好了。回到预测每个人玩游戏意愿预测的例子：

假设建了右边的那棵树，那么每个样本都对应到了叶子节点上去，每一个样本都会对应一个g和h， 那么我们遍历叶子节点，就会得到每个叶节点的G和H，然后累加就可以得到这棵树的结构分数。（这里有个小细节，假设有N个训练样本， 那么就会有N次计算g和h，不同样本的计算过程没有联系，所以可以并行计算，加速训练了。另外，计算g和h是不依赖于特定的损失函数的，任何有意义的二次可微的函数都行。）

树的分裂

第二个问题，如何建立一颗树呢？XGBoost采用二叉树， 用了贪心策略。在开始的时候， 全部样本在一个叶子节点上， 然后叶子节点不断通过二分裂，逐渐生成一棵树。

叶节点分裂成树的过程中最关键的是应该在哪个特征的哪个点上进行分裂，也就是寻找最优切分点的过程。对XGBoost算法而言，分列前的目标函数可以写为：
$L_1=-\frac{1}{2}\sum_{j=1}^{J}[\frac{G_{mj}^2}{H_{mj}+\lambda}]+\gamma \times1$L1​=−21​j=1∑J​[Hmj​+λGmj2​​]+γ×1
令$I_L,\,I_R$IL​,IR​分别表示分裂点之后加入左右叶子节点的样本集合，且有$G_L=\sum_{i\in I_L}g_{mi}，G_R=\sum_{i\in I_R}g_{mi}，H_L=\sum_{i\in I_L}h_{mi}，H_R=\sum_{i\in I_R}h_{mi}$GL​=i∈IL​∑​gmi​，GR​=i∈IR​∑​gmi​，HL​=i∈IL​∑​hmi​，HR​=i∈IR​∑​hmi​，则分裂后的目标函数可以写为：
$L_2=-\frac{1}{2}\frac{G_L^2}{H_L+\lambda}-\frac{1}{2}\frac{G_R^2}{H_R+\lambda}+2\gamma$L2​=−21​HL​+λGL2​​−21​HR​+λGR2​​+2γ
则分裂后的收益(分裂前后损失的差)表示为$L_1- L_2$L1​−L2​：
$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$Lsplit​=21​[HL​+λGL2​​+HR​+λGR2​​−HL​+HR​+λ(GL​+GR​)2​]−γ
基于上面的描述，得到最优切分点的划分算法：

• 从深度为 0 的树开始，对每个叶节点枚举所有的可用特征；
• 针对每个特征，把属于该节点的训练样本根据该特征值进行升序排列，通过线性扫描的方式来决定该特征的最佳分裂点，并记录该特征的分裂收益；（这个过程每个特征的收益计算是可以并行计算的）
• 选择收益最大的特征作为分裂特征，用该特征的最佳分裂点作为分裂位置，在该节点上分裂出左右两个新的叶节点，并为每个新节点关联对应的样本集（这里稍微提一下，XGBoost是可以处理空值的，也就是假如某个样本在这个最优分裂点上值为空的时候， 那么XGBoost先把它放到左子树上计算一下收益，再放到右子树上计算收益，哪个大就把它放到哪棵树上。）
• 回到第 1 步，递归执行到满足特定条件为止

回到玩游戏的那个例子，假设我有每个人有性别，年龄，兴趣等几个特征，我想用XGBoost建立一棵树预测玩游戏的意愿值。首先，五个人都聚集在根节点上，现在就考虑根节点分叉，我们就遍历每个特征，对于当前的特征，我们要去寻找最优切分点以及带来的最大收益。比如当前特征是年龄，我们需要知道两点：

1. 按照年龄分是否有效，即，是否减少了损失值 ？
2. 如果真的可以分，特征收益比较大， 那么我们从哪个年龄点分开呢？

对于这两个问题，首先是要对年龄排序，5个人可以找到4个切分点。对于每个切分点，计算$H_L，H_R，G_L，G_R$HL​，HR​，GL​，GR​，取出使得$L_{split}$Lsplit​最大的划分点a：

然后哪个最大，就是年龄特征的最优切分点，而最大值就是年龄这个特征的最大信息收益。

遍历完所有特征后，我们就可以确定应该在哪个特征的哪个点进行切分。对切分出来的两个节点，递归地调用这个过程，我们就能获得一个相对较好的树结构， 有了树结构就比较容易找最优的叶子节点，这样就能对上面的样本进行预测了。当然，特征与特征之间的收益计算是互不影响的，所以这个遍历特征的过程其实可以并行运行。

要注意的是XGBoost在切分的时候就已经考虑了树的复杂度 λ ，所以，它不需要进行单独的剪枝操作。

基于分桶的划分策略

当数据量大，特征又多的时候，数据划分的计算量太大了。于是作者采用近似分割的方式（可以理解为分割点分桶的思路），选出一些候选的分裂点，然后再遍历这些较少的分裂点来找到最佳分裂点。

具体而言，作者这里采用了一种对loss的影响权重的等值percentiles（百分比分位数）划分算法（Weight Quantile Sketch）。也就是说，进行候选点选取的时候，考虑的是想让loss在左右子树上分布的均匀一些，而不是样本数量的均匀。

我们知道每个样本对于降低loss的贡献可能不-样，所以我们可以根据这个贡献程度给每个样本加上权值，这里用 hi 表示(即 hi 表示每个样本对降低 Ioss 的贡献程度) 。这样我们就可以画出下面这个图来，第一行表示每个样本在某个特征上取值情况，第二行代表每个样本对于降低loss的贡献程度：

划分的时候，我们是根据这个 hi 的取值进行分箱的，就是尽量的每个桶里面的 hi 分布相对均匀些，不让某些节点重要的样本多而且还大。比如最右边的子树，只要一 个权重特别大的样本就够了，而左边的子树，样本权值偏低，所以咱可以多给些样本，这样loss在树结构中才比较均匀，这样每个bin的贡献度都是0.6了，比较均匀。

现在又用了两个问题：

1. hi 是啥，它为啥就能代表样本对降低loss的贡献程度？
2. 这个bin是怎么分的，为啥是0.6一个箱？

对于第一个问题，hi 其实就是前面说到的二阶导，也就是下面损失函数中的 $h_{mi}$hmi​：
$L_m\approx \sum_{i=1}^{N}\left(L(y_i, f_{m-1}(x_i))+g_{mi}h_m(x_i)+h_{mi}h_m^2(x_i)\right)+\gamma J+\frac{\lambda}{2}\sum_{j=1}^{J}\omega_{mj}^2$Lm​≈i=1∑N​(L(yi​,fm−1​(xi​))+gmi​hm​(xi​)+hmi​hm2​(xi​))+γJ+2λ​j=1∑J​ωmj2​
对于上面的式子，可以凑完全平方项，并化简为如下的形式（这里不展开讲，有兴趣看看参考文章1）：
$L_m\approx \sum_{i=1}^{N} \frac{1}{2}h_{mi} \left( h_m(x_i)-(-\frac{g_{mi}}{h_{mi}}) \right)^2 +\gamma J+\frac{\lambda}{2}\sum_{j=1}^{J}\omega_{mj}^2+Constant$Lm​≈i=1∑N​21​hmi​(hm​(xi​)−(−hmi​gmi​​))2+γJ+2λ​j=1∑J​ωmj2​+Constant
也就是$h_{mi}$hmi​是表示残差$-\frac{g_{mi}}{h_{mi}}$−hmi​gmi​​的重要程度，即每个样本对loss减少的贡献程度。

对于第二个如何分箱的问题，定义数据集$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分位点，2/3分位点。上面样本贡献度总和是1.8， 那么每个箱贡献度就是 1.8 * 1/3 = 0.6。

上面这些公式看起来挺复杂，可计算起来很简单，就是计算一下总的贡献度， 然后指定ε，两者相乘得到每个桶的贡献度进行分桶即可。这样我们就可以确定合理的候选切分点，然后进行分箱了。

总结下，前面那一部分是围绕着如何建立一棵树进行的，即采用贪心的方式从根节点开始一层层的建立树结构（每一层争取最优），然后就是建树过程中一个关键的问题：如何寻找最优切分点，给出了最优切分点算法，基于这个算法就可以建立树了。

后面这一部分是一个优化的过程，提出了一种Weight Quantile Sketch的算法，这个算法可以将原来的分割点进行分桶，然后找到合适的候选分裂点，这样可以减少遍历时尝试的分裂点的数量，是XGBoost相比于GBDT做出的切分点优化策略，现在知道为啥XGBoost要快了吧，因为XGBoost寻找切分点的时候不用遍历所有的，而是只看候选点就可以了。而且在特征上，XGBoost是可以并行处理的。这样XGBoost的建树过程及优化策略基本上就是这些了。

正则化

总体上讲，XGBoost抵抗过拟合的方法与GBDT类似，主要也是从以下几方面考虑：

模型复杂度

正则化项的表达式：
$\Omega(h_m)=\gamma J+\frac{\lambda}{2}\sum_{j=1}^{J}\omega_{mj}^2$Ω(hm​)=γJ+2λ​j=1∑J​ωmj2​
其中，$J$J 是叶节点个数，$\omega_{mj}$ωmj​是第m棵树第j个叶节点的最优值。第一项是用于对过多的叶节点个数进行惩罚，第二项对过于大的最优值(预测值)进行惩罚。

Shrinkage

Shrinkage的思想是，每次走一小步逼近最优值，比每次迈一大步很快逼近结果的方式更容易避免过拟合。因为这个过程不完全信任每一个棵残差树，它认为每棵树只学到了真理的一小部分，累加的时候只累加一小部分，通过多学几棵树弥补不足。用方程来看更清晰，即给每棵数的输出结果乘上一个步长$\alpha$α（learning rate），于是原来的弱学习器迭代：
$f_m(x)=f_{m-1}(x)+T(x;\gamma_m)$fm​(x)=fm−1​(x)+T(x;γm​)
由于Shrinkage思想的加入，变成了：
$f_m(x)=f_{m-1}(x)+\alpha\, T(x;\gamma_m)$fm​(x)=fm−1​(x)+αT(x;γm​)
其中，$\alpha$α的取值范围为(0,1]。对于同样的训练集学习效果，较小$\alpha$α的意味着需要更多的弱学习器的迭代次数。通常我们用步长$\alpha$α和迭代最大次数一起决定算法的拟合效果。

特征采样和样本采样

XGBoost借鉴RF的思想，对特征和特征进行采样以达到降低过拟合的目的，根据用户反馈，特征采样比起样本采样效果更优(特征采样率：[0.5,0.8])。当然，XGBoost同时支持以上两种降低过拟合的采样方式。

Early Stopping

对于每一次分离后的增益，即前面的：
$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$Lsplit​=21​[HL​+λGL2​​+HR​+λGR2​​−HL​+HR​+λ(GL​+GR​)2​]−γ
在sklearn接口当中，如果$L_{split}$Lsplit​出现负值，则提前停止；但是，被提前终止掉的分裂可能其后续的分裂会带来好处。在XBGoost原生接口当中是采用过后剪枝策略：将树分裂到最大深度，然后再基于上述增益计算剪枝。在具体实现时，还有learning rate等其它参数一起控制，给$L_{split}$Lsplit​出现负值的后续轮留机会。

缺失值处理

XGBoost支持缺失值的处理，没有简单的假设缺失值一定进入左子树还是右子树，而是尝试通过枚举所有缺失值在当前节点是进入左子树，还是进入右子树更优，来决定一个处理缺失值默认的方向，这样处理起来更加的灵活和合理。

优缺点

优点

• 支持线性分类器（相当于引入$L_1,\,L_2$L1​,L2​正则惩罚项的LR和线性回归，损失函数公式=误差平方和+正则项，似LR）
• 损失函数用了二阶泰勒展开，引入一阶导和二阶导，提高模型拟和的速度
• 可以给缺失值自动划分方向
• 同RF，支持样本(行)随机抽取，也支持特征(列)随机抽取，降低运算，防过拟合
• 损失函数引入正则化项，包含全部叶子节点个数，每个叶子节点得分的$L_2$L2​模的平方和（代表叶子节点权重的影响），控制模型（树）复杂度
• 每次迭代后为叶子分配结合学习速率，减低每棵树权重，减少每棵树影响，灵活调整后面的学习空间
• 支持并行，不是树并行，是把特征值先预排序，存起来，可以重复用于并行计算分裂点
• 分裂时把分开后与未分前的损失差值视为增益，不用每个节点排序算增益，减少计算量，可以并行计算
• 可以引入阈值限制树分裂，控制树的规模

缺点

• 往往会选择具有更高数量的不同值的预测器
• 当预测器具有很多类别时，容易过拟合
• 参数过多，调参困难
• 如果采用精确搜索算法对内存消耗过大，且不支持分布式

总结

简单的回顾一下本文内容:

XGBoost是好多弱分类器的集成，训练弱分类器的策略就是尽量的减小残差，使得答案越来越接近正确答案。XGBoost的精髓部分是目标函数的Taylor化简，这样就引入了损失函数的一阶和二阶导数。然后又把样本的遍历转成了对叶子节点的遍历，得到了最终的目标函数。这个函数就是衡量一棵树好坏的标准。在建树过程中，XGBoost采用了贪心策略，并且对寻找分割点也进行了优化。基于这个，才有了后面的最优点切分建立一棵树的过程。XGBoost训练的时候，是通过加法进行训练，也就是每一次只训练一棵树出来， 最后的预测结果是所有树的加和表示。

参考文章：

【白话机器学习】算法理论+实战之XGBoost算法

XGBoost算法梳理