大家好，又见面了，我是你们的朋友全栈君。

本篇博客是提升树模型博客的第二篇文章，第一篇介绍GBDT的博客可以参看这里。第三篇介绍Lightgbm博客可以参看这里。

本篇博客是基于kingsam_的博客整理而来，在此表示感谢。在这篇文章的基础上，我加入了一些自己的理解，使得介绍Xgboost的内容更加详实易读。

同介绍GBDT一样，我首先会介绍理论部分，然后举例说明模型训练过程，最后介绍一些细节问题。

一、Xgboost简介

在数据建模中，经常采用Boosting方法，该方法将成百上千个分类准确率较低的树模型组合起来，成为一个准确率很高的预测模型。这个模型会不断地迭代，每次迭代就生成一颗新的树。但在数据集较复杂的时候，可能需要几千次迭代运算，这将造成巨大的计算瓶颈。

针对这个问题。华盛顿大学的陈天奇博士开发的Xgboost（eXtreme Gradient Boosting）基于C++通过多线程实现了回归树的并行构建，并在原有Gradient Boosting算法基础上加以改进，从而极大地提升了模型训练速度和预测精度。

在Kaggle的比赛中，多次有队伍借助Xgboost在比赛中夺得第一。其次，因为它的效果好，计算复杂度不高，在工业界中也有大量的应用。

二、监督学习的三要素

因为Boosting Tree本身是一种有监督学习算法，要讲Boosting Tree，先从监督学习讲起。在监督学习中有几个逻辑上的重要组成部件，粗略地可以分为：模型、参数、目标函数和优化算法。

2.1 模型

模型指的是给定输入$x_i$如何去预测输出$y_i$。我们比较常见的模型如线性模型（包括线性回归和Logistic Regression）采用线性加和的方式进行预测
$${\hat{y}}_i=\sum _j{w}_j{x}_{ij}$$

这里的预测值$y$可以有不同的解释，比如我们可以把它作为回归目标的输出，或者进行sigmoid变换得到概率（即用$\frac{1}{1+e^{-{\hat{y}}_i}}$来预测正例的概率），或者作为排序的指标等。一个线性模型根据$y$的解释不同（以及设计对应的目标函数），分别用到回归、分类或者排序等场景。

2.2 参数

参数就是我们根据模型要从数据里头学习的东西，比如线性模型中的线性系数：
Θ = { w j ∣ j = 1 , 2 , ⋅ ⋅ ⋅ , d } \varTheta =\left\{w_j|j=1,2,···,d\right\} Θ={
wj​∣j=1,2,⋅⋅⋅,d}

2.3 目标函数：误差函数+正则化项

模型和参数本身指定了给定输入我们如何预测，但是没有告诉我们如何去寻找一个比较好的参数，这个时候就需要目标函数函数登场了。一般地目标函数包含两项：一项是损失函数，它说明了我们的模型有多拟合数据；另一项是正则化项，它惩罚了复杂模型。
$$Obj(\Theta )=L(\Theta )+\Omega (\Theta )$$

1. $L(\Theta )$:损失函数$L={\sum }_{i=1}^{n}l\left(y_i,{\hat{y}}_i\right)$，常见的损失函数有：

   平方损失：$l\left(y_i,{\hat{y}}_i\right)={\left(y_i-{\hat{y}}_i\right)}^2$
   Logistic损失：$l\left(y_i,{\hat{y}}_i\right)=y_i\ln \left(1+e^{-{\hat{y}}_i}\right)+\left(1-y_i\right)\ln \left(1+e^{{\hat{y}}_i}\right)$

2. $\Omega \left(\Theta \right)$:正则化项，之所以要引入它是因为我们的目标是希望生成的模型能准确地预测新的样本（即应用于测试数据集），而不是简单地拟合训练集的结果（这样会导致过拟合）。所以需要在保证模型“简单”的基础上最小化训练误差，这样得到的参数才具有好的泛化性能。而正则化项就是用于惩罚复杂模型，避免模型过分拟合训练数据。常用的正则有$L1$正则与$L2$正则:

   $L1$正则（lasso）：$\Omega \left(w\right)=\lambda ||w|{|}_1$
   $L2$正则: $\Omega \left(w\right)=\lambda ||w|{|}^2$

上述目标函数的设计来自于统计学习里面的一个重要概念叫做Bias-variance tradeoff（偏差-方差权衡），比较感性的理解，Bias可以理解为假设我们有无限多数据的时候，可以训练出最好的模型所拿到的误差。而Variance是因为我们只有有限数据，其中随机性带来的误差。目标中误差函数鼓励我们的模型尽量去拟合训练数据，这样相对来说最后的模型会有比较少的Bias。而正则化项则鼓励更加简单的模型。因为当模型简单之后，有限数据拟合出来结果的随机性比较小，不容易过拟合，使得最后模型的预测更加稳定。

三、Xgboost原理

3.1 目标函数及其二阶泰勒展开

在Xgboost中，选择树模型为基学习器，我们需要正则的对象，或者说需要控制复杂度的对象就是这$K$颗树,通常树的参数有树的深度，叶子节点的个数，叶子节点值的取值（Xgboost里称为权重weight)。

所以，我们的目标函数形式如下：
$$Obj\left(\Theta \right)=\sum _{i=1}^{n}L\left(y_i,{\hat{y}}_i\right)+\sum _{k=1}^K\Omega \left(f_k\right)$$

其中第一部分是训练损失，如上面所述的平方损失或者Logistic Loss等，第二部分是每棵树的复杂度的和。因为现在我们的参数可以认为是在一个函数空间里面，我们不能采用传统的如SGD之类的算法来学习我们的模型，因此我们会采用一种叫做additive training的方式。即每次迭代生成一棵新的回归树，从而使预测值不断逼近真实值（即进一步最小化目标函数）。每一次保留原来的模型不变，加入一个新的函数$f$到模型里面：
$${\hat{y}}_i^0=常数$$

$${\hat{y}}_i^1={\hat{y}}_i^0+f_1(x_i)$$

$${\hat{y}}_i^2={\hat{y}}_i^1+f_2(x_i)$$

$${\hat{y}}_i^K={\hat{y}}_i^{K-1}+f_K(x_i)\text{\hspace{1em}(0)}$$

所以，对于第$K$次的目标函数为：
$$Ob{j}^K=\sum _{i}L(y_i,{\hat{y}}_i^K)+\Omega (f_K)+constant$$

其中$constant$为前$K-1$颗树的正则化项和，是一个常数。

根据公式（0），进一步为：
$$Ob{j}^K=\sum _{i}L\left(y_i,{\hat{y}}_i^{K-1}+f_K(x_i)\right)+\Omega (f_K)+constant$$

上面的式子意义很明显，只需要寻找一颗合适的树$f_K$使得目标函数最小。然后不断的迭代$K$次就可以完成$K$个学习器的训练。

那么我们这颗树到底怎么找呢？

在GBDT里面（当然GBDT没有正则），我们的树是通过拟合上一颗树的负梯度值，建树的时候采用的启发式准则，如MSE等。

然而，在Xgboost里面，它是通过对损失函数进行二阶泰勒展开：
$$f(x+\Delta x)=f(x)+f^{\prime }(x)\Delta x+\frac{1}{2}{f}^{\prime \prime }(x){\Delta x}^2$$

对损失函数二阶泰勒展开：
$$\sum _{i}L\left(y_i,{\hat{y}}_i^{K-1}+f_K(x_i)\right)=\sum _i\left[L(y_i,{\hat{y}}_i^{K-1})+L^{\prime }(y_i,{\hat{y}}_i^{K-1})f_K(x_i)+\frac{1}{2}{L}^{\prime \prime }(y_i,{\hat{y}}_i^{K-1})f_K^2(x_i)\right]$$

注意的是，这里的$y_i$是标签值是个常数，而${\hat{y}}_i^{K-1}$是第$K-1$次学习到的结果，也是个常数。所以只要把变化量$\Delta x$看成我们需要学习的模型$f_K(x)$，把${\hat{y}}_i^{K-1}$看作$x$就可以展成上面的这个样子了。

这里，我们用$g_i$记为第$i$个样本损失函数的一阶导，$h_i$记为第$i$个样本损失函数的二阶导。

$$g_i=L^{\prime }(y_i,{\hat{y}}_i^{K-1})\text{\hspace{1em}(1)}$$

$$h_i=L^{\prime \prime }(y_i,{\hat{y}}_i^{K-1})\text{\hspace{1em}(2)}$$

(1)式和(2)式非常的重要，贯穿了整个树的构建（分裂，叶子节点值的计算）。同时(2)式是我们利用Xgboost做特征选择时的其中一个评价指标。

所以我们可以得到我们进化后的目标函数：
$$\sum _i\left[L(y_i,{\hat{y}}_i^{K-1})+g_i{f}_K(x_i)+\frac{1}{2}{h}_i{f}_K^2(x_i)\right]+\Omega (f_K)+constant$$

这里，我们先回忆一下，一颗树用数学模型来描述是什么样，很简单其实就是一个分段函数。比如有下面一颗树。

$$f(x)=\{\begin{array}{ll}0.444444& x1<10\\ -0.4& x1>=10\end{array}$$

也就是说，一棵树其实可以由一片区域以及若干个叶子节点来表达。 而同时，构建一颗树也是为了找到每个节点的区域以及叶子节点的值。

也就说可以有如下映射的关系$f_K(x)=w_{q(x)}$。其中$q(x)$叶子节点的编号（从左往右编)。$w$是叶子节点的取值。 即对于任意一个样本$x$,其最后会落在树的某个叶子节点上，其值为$w_{q(x)}$。

既然一棵树可以用叶子节点来表达，那么，我们上面的正则项就了其中一个思路。我们可以对叶子节点值进行惩罚(正则)，比如取$L2$正则，以及我们控制一下叶子节点的个数$T$，那么正则项有：

$$\Omega (f_K)=\frac{1}{2}\lambda \sum _j^T||w_j|{|}^2+\gamma T$$

---

正则为什么可以控制模型复杂度呢？有很多角度可以看这个问题，最直观就是，我们为了使得目标函数最小，自然正则项也要小，正则项要小，叶子节点个数T要小（叶子节点个数少，树就简单）。

而为什么要对叶子节点的值进行$L2$正则，这个可以参考一下LR里面进行正则的原因，简单的说就是LR没有加正则，整个$w$的参数空间是无限大的，只有加了正则之后，才会把$w$的解规范在一个范围内。（对此困惑的话可以跑一个不带正则的LR，每次出来的权重$w$都不一样，但是$loss$都是一样的，加了$L2$正则后，每次得到的$w$都是一样的）

---

这个时候，我们的目标函数（移除常数项后，注意：$L(y_i,{\hat{y}}_i^{K-1})$也是常数）就可以改写成这样（用叶子节点表达）：
$$\sum _i\left[g_i{w}_q(x_i)+\frac{1}{2}{h}_i{w}_{q(x_i)}^2\right]+\frac{1}{2}\lambda \sum _j^T||w_j|{|}^2+\gamma T\text{\hspace{1em}(3)}$$

其实我们可以进一步化简，也是最重要的一步化简。那么最后可以化简成：
$$\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\text{\hspace{1em}(4)}$$

（3)式子展开之后按照叶子节点编号进行合并后可以得到(4)。

下面，我们把${\sum }_{(i\in I_j)}{g}_i$记为$G_j$，把${\sum }_{(i\in I_j)}{h}_i$记为$H_j$。

$$G_j=\sum _{(i\in I_j)}{g}_i\text{\hspace{1em}(5)}$$

$$H_j=\sum _{(i\in I_j)}{h}_i\text{\hspace{1em}(6)}$$

那么目标函数可以进一步简化为：
$$\sum _{j=1}^T\left[G_j{w}_j+\frac{1}{2}(H_j+\lambda )w_j^2\right]+\gamma T\text{\hspace{1em}(7)}$$

我们做了这么多，其实一直都是在对二阶泰勒展开后的式子化简，其实刚展开的时候就已经是一个二次函数了，只不过化简到这里能够把问题看的更加清楚。所以对于这个目标函数，我们对$w_j$求导，然后代入极值点，可以得到一个极值：
$$w^{\ast }=-\frac{G_j}{H_j+\lambda }\text{\hspace{1em}(8)}$$

$$Obj=-\frac{1}{2}\sum _{j=1}^T\frac{G_j^2}{H_j+\lambda }+\gamma T\text{\hspace{1em}(9)}$$

(8)式即为叶子结点取值的表达式。(9)式为目标函数的值。

值得注意的是：在第一篇博客中我们提到，在GBDT中，不同的损失函数有不同的叶子节点的取值，而在Xgboost里，叶子节点取值的表达式很简洁，推导起来也比GBDT的要简便许多。

3.2 分裂准则

到这里，我们一直都是在围绕目标函数进行分析，这个到底是为什么呢？这个主要是为了后面我们寻找$f_k(x)$，也就是建树的过程。

具体来说，我们回忆一下建树的时候需要做什么，建树的时候最关键的一步就是选择一个分裂的准则，也就如何评价分裂的质量。比如在前面文章GBDT的介绍里，我们可以选择MSE，MAE来评价我们的分裂的质量，但是，我们所选择的分裂准则似乎不总是和我们的损失函数有关，因为这种选择是启发式的。 比如，在分类任务里面，损失函数可以选择logloss，分裂准确选择MSE，这样看来，似乎分裂的好坏和我们的损失并没有直接挂钩。

但是，在Xgboost里面，我们的分裂准则是直接与损失函数挂钩的准则，这个也是Xgboost和GBDT一个很不一样的地方。

具体来说，Xgboost选择$Gain=Ob{j}_C-Ob{j}_L-Ob{j}_R$这个准则，计算增益$Gain$
$$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 \text{\hspace{1em}(10)}$$

其实选择这个作为准则的原因很简单也很直观。

我们这样考虑。由(9)式知道，对于一个结点，假设我们不分裂的话。

此时损失为：$-\frac{(G_L+G_R{)}^2}{(H_L+H_R)+\lambda }$

假设在这个节点分裂的话，分裂之后左右叶子节点的损失分别为：$-\frac{G_L^2}{H_L+\lambda }$、$-\frac{G_R^2}{H_R+\lambda }$

既然要分裂的时候，我们当然是选择分裂成左右子节点后，损失减少的最多。

也就是找到一种分裂有：$Max(\left[\frac{G_L^2}{H_L+\lambda }+\frac{G_R^2}{H_R+\lambda }-\frac{(GL+G_R{)}^2}{(H_L+H_R)+\lambda }\right])$。

那么$\gamma$的作用是什么呢？利用$\gamma$可以控制树的复杂度，进一步来说，利用$\gamma$来作为阈值，只有大于$\gamma$时候才选择分裂。这个其实起到预剪枝的作用。

最后就是如何得到左右子节点的样本集合？这个和普通的树一样，都是通过遍历特征所有取值，逐个尝试。

至此，我们把Xgboost的基本原理阐述了一遍。我们总结一下，其实就是做了以下几件事情。

1.在损失函数的基础上加入了正则项。
2.对目标函数进行二阶泰勒展开。
3.利用推导得到的表达式作为分裂准确，来构建每一颗树。

3.3 算法流程

Xgboost核心部分的算法流程图如下：

（这里的m貌似是d）

四、手动计算还原Xgboost的过程

在上一章，我阐述了整个流程，有一些细节的地方可能都说的不太清楚。在这里，我以一个简单的UCI数据集，一步一步地和大家演算整个Xgboost的过程。

4.1 数据集，参数设置以及损失函数

数据集的样本条数只有15条，2个特征。具体如下：

这里为了简单起见，树的深度设置为3(max_depth=3)，树的颗数设置为2(num_boost_round=2),学习率为0.1(eta=0.1)。

另外再设置两个正则的参数,λ=1,γ=0。 损失函数选择logloss。

由于后面需要用到logloss的一阶导数以及二阶导数，这里先简单推导一下。在介绍GBDT的博客里我已经推导过一遍。
$$L(y_i,{\hat{y}}_i)=y_{i}ln(1+e^{-{\hat{y}}_i})+(1-y_i)ln(1+e^{{\hat{y}}_i})$$

两边对${\hat{y}}_i$求一阶导数。
$$L^{\prime }(y_i,{\hat{y}}_i)=y_i\frac{-e^{-{\hat{y}}_i}}{1+e^{-{\hat{y}}_i}}+(1-y_i)\frac{e^{{\hat{y}}_i}}{1+e^{{\hat{y}}_i}}$$

$$==>L^{\prime }(y_i,{\hat{y}}_i)=y_i\frac{-1}{1+e^{{\hat{y}}_i}}+(1-y_i)\frac{1}{1+e^{-{\hat{y}}_i}}$$

$$==>L^{\prime }(y_i,{\hat{y}}_i)=y_i\ast (y_{i,pred}-1)+(1-y_i)\ast y_{i,pred}$$

$$==>L^{\prime }(y_i,{\hat{y}}_i)=y_{i,pred}-y_i$$

其中，$y_{i,pred}=\frac{1}{1+e^{-{\hat{y}}_i}}$

在一阶导的基础上再求一次有（其实就是sigmod函数求导)
$$L^{\prime \prime }(y_i,{\hat{y}}_i)=y_{i,pred}\ast (1-y_{i,pred})$$

所以样本的一阶导数值
$$g_i=y_{i,pred}-y_i\text{\hspace{1em}(11)}$$

样本的二阶导数值
$$h_i=y_{i,pred}\ast (1-y_{i,pred})\text{\hspace{1em}(12)}$$

4.2 建立第一颗树(k=1)

建树的时候从根节点开始(Top-down greedy)，在根节点上的样本有ID1～ID15。那么回顾Xgboost的算法流程，我们需要在根节点处进行分裂，分裂的时候需要计算式子(10)。
$$Gain=\frac{1}{2}\left[\frac{G_L^2}{H_L^2+\lambda }+\frac{G_R^2}{H_R^2+\lambda }-\frac{(G_L+G_R{)}^2}{(H_L+H_R{)}^2+\lambda }\right]-\gamma \text{\hspace{1em}(10)}$$

那么式子(10)表达是：在结点处把样本分成左子结点和右子结点两个集合。分别求两个集合的$G_L$、$H_L$、$G_R$、$H_R$，然后计算增益$Gain$。

而这里，我其实可以先计算每个样本的一阶导数值和二阶导数值，即按照式子(11)和(12)计算，但是这里你可能碰到了一个问题，那就是第一颗树的时候每个样本的预测的概率$y_{i,pred}$是多少？这里和GBDT一样，应该说和所有的Boosting算法一样，都需要一个初始值。而在Xgboost里面，对于分类任务只需要初始化为(0,1)中的任意一个数都可以。具体来说就是参数base_score。（其默认值是0.5）
(值得注意的是base_score是一个经过sigmod映射的值，可以理解为一个概率值，提这个原因是后面建第二颗树会用到，需要注意这个细节）

这里我们也设base_score=0.5。然后我们就可以计算每个样本的一阶导数值和二阶导数值了。具体如下表：

比如说对于ID=1样本,$g_1=y_{1,pred}-y_1=0.5-0=0.5$
$h_1=y_{1,pred}\ast (1-y_{1,pred})=0.5\ast (1-0.5)=0.25$

那么把样本如何分成两个集合呢？这里就是上面说到的选取一个最佳的特征以及分裂点使得$Gain$最大。

比如说对于特征$x1$，一共有[1,2,3,6,7,8,9,10]8种取值。可以得到以下这么多划分方式。

以1为划分时(x1<1)：

左子节点包含的样本$I_L=$[]
右子节点包含的样本$I_R=$[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]

那么左子节点为空，$G_L=0$和$H_L=0$

右子节点的一阶导数和：
$G_R={\sum }_{(i\in I_R)}{g}_i=(0.5+0.5+....-0.5)=-1.5$
右子节点的二阶导数和：
$H_R={\sum }_{(i\in I_R)}{h}_i=(0.25+0.25...0.25)=3.75$

最后我们在计算一下增益$Gain$，可以得到$Gain=0$。

计算出来发现$Gain=0$,不用惊讶,因为左子结点为空，也就是这次分裂把全部样本都归到右子结点，这个和没分裂有啥区别？所以，分裂的时候每个结点至少有一个样本。

---

下面，我再计算当以2划分时的增益Gain。
以2为划分时(x1<2)：

左子结点包含的样本$I_L=$[1,4]
右子节点包含的样本$I_R=$[2,3,5,6,7,8,9,10,11,12,13,14,15]

左子结点的一阶导数和：
$G_L={\sum }_{(i\in I_L)}{g}_i=(0.5-0.5)=0$
左子结点的二阶导数和：
$H_L={\sum }_{(i\in I_L)}{h}_i=(0.25+0.25)=0.5$

右子结点的一阶导数和：
$G_R={\sum }_{(i\in I_R)}{g}_i=-1.5$
右子结点的二阶导数和：
$H_R={\sum }_{(i\in I_R)}{h}_i=3.25$

最后计算一下增益$Gain$：
$Gain=\left[\frac{G_L^2}{H_L^2+\lambda }+\frac{G_L^2}{H_L^2+\lambda }-\frac{(GL+G_R{)}^2}{(H_L+H_R{)}^2+\lambda }\right]=0.0557275541796$

---

其他的值[3,6,7,8,9,10]类似，计算归总到下面表，供大家参考

从上表我们可以看到，如果特征x1以x1<10分裂时可以得到最大的增益0.615205。

按照算法的流程，这个时候需要遍历下一个特征x2，对于特征x2也是重复上面这些步骤，可以得到类似的表如下，供大家参考。

可以看到，以x2特征来分裂时，最大的增益是0.2186<0.615205。所以在根节点处，我们以x1<10来进行分裂。

由于我设置的最大深度是3，此时只有1层，所以还需要继续往下分裂。

左子节点的样本集合$I_L$=[1,2,3,4,5,6,7,8,9,10,11,12,14,15]
右子节点的样本集合$I_R$=[13]

右子节点此时只剩一个样本，不需要分裂了，也就是已经是叶子结点。可以计算其对应的叶子结点值了，按照公式(8)：
$$w^{\ast }=-\frac{G_j}{H_j+\lambda }\text{\hspace{1em}(8)}$$

$w_1=-\frac{G_R}{H_R+\lambda }=-\frac{g_{13}}{h_{13}+1}=-\frac{0.5}{1+0.25}=-0.4$。那么下面就是对左子结点$I_L$进行分裂。分裂的时候把此时的结点看成根节点，其实就是循环上面的过程，同样也是需要遍历所有特征(x1,x2)的所有取值作为分裂点，选取增益最大的点。

---

这里为了说的比较清晰，也重复一下上面的过程：
此时样本有$I=$[1,2,3,4,5,6,7,8,9,10,11,12,14,15]

先考虑特征x1，此时x1的取值有[1, 2, 3, 6, 7, 8, 9]

以1为分裂Gain=0。

以2为划分时(x1<2)：

左子结点包含的样本$I_L=$[1,4]
右子结点包含的样本$I_R=$[2,3,5,6,7,8,9,10,11,12,14,15]

左子结点的一阶导数和：
$G_L={\sum }_{(i\in I_L)}{g}_i=(0.5-0.5)=0$
左子结点的二阶导数和：
$H_L={\sum }_{(i\in I_L)}{h}_i=(0.25+0.25)=0.5$

右子结点的一阶导数和：
$G_R={\sum }_{(i\in I_R)}{g}_i=-2$
右子结点的二阶导数和：
$H_R={\sum }_{(i\in I_R)}{h}_i=3$

最后计算一下增益$Gain$：
$Gain=\left[\frac{G_L^2}{H_L^2+\lambda }+\frac{G_L^2}{H_L^2+\lambda }-\frac{(GL+G_R{)}^2}{(H_L+H_R{)}^2+\lambda }\right]=0.111111111111$

其他的同理，最后所有值都遍历完后可以得到下表：

可以看到，x1选择x<3时能够获得最大的增益0.2539。

同理，我们对x2再次遍历可以得到下表：

可以看到x2在x2<2时分裂可以获得最大的增益0.4444。

比较知道，应该选择x2<2作为分裂点。

分裂后左右叶子结点的集合如下：

左子节点的样本集合$I_L=$[1,3,5,6,8,10,11,15]
右子节点的样本集合$I_R=$[2,4,7,9,12,14]

然后继续对$I_L$和$I_R$进行分裂。这里就不在啰嗦了。这里直接给出第一个树的结构。

---

注意：

这里有的人可能对叶子结点取值感到困惑。为何我算出来的是-0.4，可图上却是-0.04？

这里以最左边的一个叶子结点为例，展示一下计算的过程。

落在最左边这个叶子结点上的样本有$I=$[1]

所以由公式：
$$w^{\ast }=-\frac{G_j}{H_j+\lambda }\text{\hspace{1em}(8)}$$

$w_2=-\frac{G_R}{H_R+\lambda }=-\frac{g_1}{h_1+1}=-\frac{0.5}{1+0.25}=-0.4$

落在从左边数起第二个叶子结点上的样本有$I=$[3,5,6,8,10,11,15]

$w_3=-\frac{G_R}{H_R+\lambda }=-\frac{g_3+g_5+g_6+g_8+g_{10}+g_{11}+g_{15}}{h_3+h_5+h_6+h_8+h_{10}+h_{11}+h_{15}+1}=-\frac{-2.5}{1+1.75}=0.909$

到这里完全没有问题，但是为什么和图上的不一样呢？这里其实和我们在GBDT中的处理一样，我们会以一个学习率来乘这个值，当完全取-0.4时说明学习率取1，这个时候很容易过拟合。所以每次得到叶子结点的值后需要乘上学习率eta，在前面我们已经设置了学习率是0.1。这里也是GBDT和Xgboost一个共同点，大家都是通过学习率来进行Shrinkage，以减少过拟合的风险。

至此，我们学习完了第一颗树。

4.3 建立第二颗树(k=2)

这里，我们开始拟合我们第二颗树。其实过程和第一颗树完全一样。只不过对$y_{i,pred}$需要进行更新，也就是拟合第二颗树是在第一颗树预测的结果基础上。这和GBDT一样，因为大家都是Boosting思想的算法。

在第一颗树里面由于前面没有树，所以初始$y_{i,pred}=0.5$

假设此时，模型只有这一颗树(K=1)，那么模型对样例$x_i$进行预测时，预测的结果表达是什么呢？
由加法模型

$$y_i^K=\sum _{k=0}^K{f}_k(x_i)\text{\hspace{1em}(13)}$$

$$y_i^1=f_0(x_i)+f_1(x_i)\text{\hspace{1em}(14)}$$

$f_1(x_i)$的值是样例$x_i$落在第一棵树上的叶子结点值。那$f_0(x_i)$是什么呢？这里就涉及前面提到一个问题base_score是一个经过sigmod映射后的值（因为选择使用Logloss做损失函数，概率$p=\frac{1}{1+e^{-x}}$）

所以需要将0.5逆运算$x=ln\frac{y}{1-y}$后可以得到$f_0(x_i)=0$。

所以第一颗树预测的结果就是$y_i^1=f_0(x_i)+f_1(x_i)=0+w_{q(x_i)}$
（其实当训练次数K足够多的时候，初始化这个值几乎不起作用的，这个在官网文档上有说明）

所以，我们可以得到第一棵树预测的结果为下表（预测后将其映射成概率）

比如对于ID=1的样本，其落在-0.04这个节点。那么经过sigmod映射后的值为
$p_{1,pred}=\frac{1}{1+e^{(0+0.04)}}=0.490001$

有了这个之后，根据公式（11）（12）我们就可以计算所有样本新的一阶导数和二阶导数的值了。具体如下表：

之后，我们和第一颗树建立的时候一样以公式(10)去建树。

拟合完后第二颗树如下图:

后面的所有过程都是重复这个过程，这里就不再啰嗦了。

至此，整个Xgboost的训练过程已经完了，但是其实里面还有一些细节的东西，下面已单独一个部分来说明这个部分。

五、细节Q&A

5.1 如何理解训练过程的参数min_child_weight ？

在选择分裂的时候，我们是选取分裂点为一个最大的增益Gain。但是其实在Xgboost里面有一个参数叫min_child_weight。

我先来看看官网对这个参数的解释：

可能看完大概知道这个权重指的应该是二阶导数，但是具体是怎么一回事呢。

其实是这样的：

在前面建立第一颗的根结点的时候，我们得到特征x1每个分裂点的这个表：

我们当时选取了x1<10作为分裂特征，但是！这个是有一个前提的，那就是参数min_child_weight $<min(H_L,H_R)$。如果我们设置min_child_weight=0.26的时候，分裂点就不是选择10，而是放弃这个最大增益，考虑次最大增益。如果次最大增益也不满足min_child_weight $<min(H_L,H_R)$，则继续往下找，如果没有找到一个满足的，则不进行分裂。（在上面中min_child_weight取的0，所以只要是最大的增益就选为分裂点）

5.2 如何理解训练过程的参数γ？

在前面例子里，我们把γ设成了0，如果我们设置成其他值比如1的话，在考虑最大增益的同时，也要考虑这个最大的增益是否比γ大，如果小于γ则不进行分裂（预剪枝）。由公式（10）得知这个结论：
$$Gain=\frac{1}{2}\left[\frac{G_L^2}{H_L^2+\lambda }+\frac{G_R^2}{H_R^2+\lambda }-\frac{(GL+G_R{)}^2}{(H_L+H_R{)}^2+\lambda }\right]-\gamma \text{\hspace{1em}(10)}$$

5.3 Xgboost如何处理缺失值？

我前面放了许多树的结构图，上面有一个方向是missing，其实这个是Xgboost自动学习的一个对缺失值处理的方向。可以看到，所有的missing方向都是指向右子结点，这是因为我们数据集中没有缺失值。

Xgboost对缺失值的处理思想很简单，具体看下面的算法流程：

首先需要注意到两个集合一个是$I$,其包含所有的样本（包括含空缺值的样本）。

$I_k$是不包含空缺值样本的集合。 在计算总的G和H时用的是$I$！！也就说空缺值的一阶导数和二阶导数已经包含进去了。

可以看到内层循环里面有两个$for$，这两个$for$针对的集合就是$I_k$。

第一个$for$是从把特征取值从小到大排序，然后从小到大进行扫描，这个时候在计算$G_R$的时候是用总的$G$减去$G_L$，$H_R$也是同样用总的$H$减去$H_L$,这意味着把空缺样本归到了右子结点。

第二个for相反过来，把空缺样本归到了左子结点。

只要比较这两次最大增益出现在第一个for中还是第二个for中就可以知道对于空缺值的分裂方向，这就是Xgboost如何学习空缺值的思想。

5.4 Xgboost如何用于特征选择？

相信很多做过数据挖掘比赛的人都利用Xgboost来做特征选择。

一般我们调用xgb库的get_fscore()。但其实Xgboost里面有三个指标用于对特征进行评价，而get_fscore()只是其中一个指标weight。

这个指标大部分玩家都很熟悉，其代表着某个特征被选作分裂的次数。

比如在前面举的例子里，我们得到这两颗树：

可以看到特征x1被选作分裂点的次数为6，x2被选做分裂点的次数为2。 get_fscore()就是返回这个指标。

而Xgboost还提供了另外两个指标，一个叫gain，一个叫cover。可以利用get_score()来选择。

那么gain是指什么呢？其代表着某个特征的平均增益。

比如，特征x1被选了6次作为分裂的特征，每次的增益假如为Gain1,Gain2,…Gain6，那么其平均增益为
$(Gain1+Gain2+...Gain3)/6$

最后一个cover指的是什么呢？其代表着每个特征在分裂时结点处的平均二阶导数。

这个为了加深理解，我举个例子，这个例子用的还是UCI数据集，不过此时只有max_depth=2,num_boost_round=1。

建树完之后，其结构如上。

在第一个结点分裂时，x1的特征增益表如下：

第二个结点分裂时，x2的特征增益表如下：

那么特征x1的cover是如下计算的：

x1在第一个结点处被选择为分裂特征，在特征值为10时进行分裂。此时结点处的总二阶导数$G=3.5+0.25=3.75$ 。故x1的cover值为3.75。 这里x1只是被分裂了一次，如果后续还有就是求平均。

同样地,x2的cover值为$G=2.25+1.25=3.5$ 。

举这个例子就是先给大家说一下何为平均二阶导数。

注意：
为什么需要选择二阶导数？这个二阶导数背后有什么意义吗？我们先看看官网对cover的定义：

‘cover’ – the average coverage of the feature when it is used in trees。大概的意义就是特征覆盖了多少个样本。
这里，我们不妨假设损失函数是mse，也就是$0.5\ast (y_i-y_{pred}{)}^2$，我们求其二阶导数，很容易得到为常数1。也就是每个样本对应的二阶导数都是1，那么这个cover指标不就是意味着，在某个特征在某个结点进行分裂时所覆盖的样本个数吗？

5.5 如何理解Xgboost+LR？

详见这里。

5.6 如何画出Xgboost中的决策树？

详见这里。

5.7 如何理解Xgboost的近似算法？

详见这里。

5.8 如何理解Xgboost的系统设计？

详见这里

六、Xgboost与传统GBDT的区别与联系

基于本篇博客和上一篇博客，我们来总结一下Xgboost与传统GBDT的区别与联系

6.1 区别

• Xgboost和GBDT的一个区别在于目标函数上。 在Xgboost中，损失函数+正则项。 GBDT中，只有损失函数。

• Xgboost中利用二阶导数的信息，而GBDT只利用了一阶导数。

• Xgboost在建树的时候利用的准则来源于目标函数推导，而GBDT建树利用的是启发式准则。

• Xgboost中可以自动处理空缺值，自动学习空缺值的分裂方向，GBDT(sklearn版本）不允许包含空缺值。

还有一些本文没有涉及到的区别：

• 列抽样（column subsampling）：Xgboost借鉴了随机森林的做法，支持列抽样，不仅能降低过拟合，还能减少计算，这也是Xgboost异于传统GBDT的一个特性。

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

• 线程缓冲区存储：按照特征列方式存储能优化寻找最佳的分割点，但是当以行计算梯度数据时会导致内存的不连续访问，严重时会导致cache miss，降低算法效率。paper中提到，可先将数据收集到线程内部的buffer（缓冲区），主要是结合多线程、数据压缩、分片的方法，然后再计算，提高算法的效率。

• 可并行的近似直方图算法：树节点在进行分裂时，我们需要计算每个特征的每个分割点对应的增益，即用贪心法枚举所有可能的分割点。当数据无法一次载入内存或者在分布式情况下，贪心算法效率就会变得很低，所以Xgboost还提出了一种可并行的近似直方图算法，用于高效地生成候选的分割点。大致的思想是根据百分位法列举几个可能成为分割点的候选者，然后从候选者中根据上面求分割点的公式计算找出最佳的分割点。

6.2 联系

• Xgboost和GBDT的学习过程都是一样的，都是基于Boosting的思想，先学习前$n-1$个学习器，然后基于前$n-1$个学习器学习第$n$个学习器。(Boosting)

• 建树过程都利用了损失函数的导数信息(Gradient),只是大家利用的方式不一样而已。

• 都使用了学习率来进行Shrinkage，从前面我们能看到不管是GBDT还是Xgboost，我们都会利用学习率对拟合结果做缩减以减少过拟合的风险。

6.3 Xgboost为什么比GBDT快？

当数据集大的时候使用近似算法
Block与并行
CPU cache 命中优化
Block压缩、Block拆分等

参考文献

【1】机器学习算法系列（8）：XgBoost

【2】Xgboost原理分析以及实践

【3】XGBoost Parameters

【4】XGBoost: A Scalable Tree Boosting System

【5】Introduction to Boosted Trees