GBDT和Xgboost：原理、推导、比较

网上有很多关于GBDT和Xgboost的文章，但是我在读的时候感觉对于提升树、GBDT和Xgboost之间的关系，以及他们和残差、梯度的关系，所以自己整理了一下，涉及的知识点比较多。Xgboost证明部分主要来源于论文，这里加入了自己的理解，以及对几者关系的说明。

在看本篇博文之前可以先看下提升树的相关内容，这样理解起来会思路更清晰。

提升树、GBDT和Xgboost的简单介绍如下：

①提升树基于残差，每一次迭代当前模型都在尽可能拟合残差； ②GBDT基于一阶导数（梯度下降法优化）； ③Xgboost基于GBDT的思想，使用了一阶和二阶导数信息（牛顿法优化，牛顿法：可参见[优化方法] 梯度下降法、最小二乘法、牛顿法、拟牛顿法、共轭梯度法）。

提升树、GBDT、Xgboost关系如下（最开始的时候总是搞不懂，网上很多资料把最原始的GBDT和Xgboost都混在一起讲了）：

①提升树的思想是基于加法模型，不断拟合残差。 ②GBDT和Xgboost都是基于提升树的思想。 ③GBDT的全称是Gradient Boosting Decision Tree，之所以有Gradient是因为GBDT中引入了梯度作为提升树中“残差”的近似值（提升树的每次迭代都是为了使当前模型拟合残差，就是使求得的增量模型尽可能等于残差）。 ④Xgboost可以说是GBDT的一种，因为其也是基于Gradient和Boosting思想，但是和原始GBDT的不同是：Xgboost中引入了二阶导数和正则化，除此之外，Xgboost的作者陈天奇博士在工程实现方面做了大量的优化策略。

提升树（Boosting Tree）主要采用加法模型，主要思想是不断拟合残差（《统计学习方法》有详述）。GBDT利用了提升树的思想，是提升树的一种，其是利用梯度下降法拟合残差。

GBDT（Gradient Boosting Decision Tree）是梯度提升树，Gradient主要体现在：使用损失函数的负梯度在当前模型的值作为回归问题提升树算法的残差近似值。负梯度为： − [ ∂ L ( y i , F m − 1 ( x i ) ∂ F m − 1 ( x i ) ] \begin{aligned} -[\frac{\partial L(y_i, F_{m-1}(x_i)}{\partial F_{m-1}(x_i)}] \end{aligned} −[∂Fm−1​(xi​)∂L(yi​,Fm−1​(xi​)​]​ 注意：GBDT中目标函数仅仅使用了损失函数，没有加入正则化等。

为什么已经有了基于残差的回归树，还提出基于负梯度来替代残差的替代提升树？ 《统计学习方法》中给出的解释是：当损失函数是平方损失和对数损失时，每一步的优化是很简单的，但是对于一般的损失函数而言，往往每一步的优化不是那么容易，使用负梯度代替残差。kaggle blog给出的解释是：Although we can minimize this function directly, gradient descent will let us minimize more complicated loss functions that we can’t minimize directly.

当损失函数是平方函数时， L ( y , F ( x ) ) = 1 2 ∑ i = 0 N ( y − F ( x i ) ) 2 L(y, F(x)) = \frac{1}{2} \sum_{i=0}^N(y-F(x_i))^2 L(y,F(x))=21​∑i=0N​(y−F(xi​))2，此时对损失函数求梯度： ∂ J ∂ F ( x i ) = − ( y − F ( x i ) ) \begin{aligned} \frac{\partial J }{\partial F(x_i)} = -(y-F(x_i)) \end{aligned} ∂F(xi​)∂J​=−(y−F(xi​))​ 此时残差 y − F ( x i ) y-F(x_i) y−F(xi​)等于负梯度，也就是说，当损失函数是平方函数时，负梯度就是残差。 但是当损失函数非平方函数时，负梯度只是残差的近似值，并不等于残差。

GBDT借助了梯度下降的优化方法，梯度下降的参数更新方程如下（假设 θ ( t ) \theta^{(t)} θ(t)表示第 t t t轮迭代的参数值）： θ ( t ) = θ ( t − 1 ) − η ∂ J ∂ θ ( t − 1 ) \begin{aligned} \theta^{(t)} = \theta^{(t-1)} - \eta \frac{\partial J}{\partial \theta^{(t-1)}} \end{aligned} θ(t)=θ(t−1)−η∂θ(t−1)∂J​​ 为了最优化 θ ( t ) \theta^{(t)} θ(t)，参数沿着梯度下降的方法不断迭代。 θ t = − η ∂ J ∂ θ ( t − 1 ) \theta_t = - \eta \frac{\partial J}{\partial \theta^{(t-1)}} θt​=−η∂θ(t−1)∂J​我们可以将其看作第 t t t次迭代的增量，则 θ = ∑ t = 0 T θ t \theta = \sum_{t=0}^T{\theta_t} θ=∑t=0T​θt​，即最终参数等于每次迭代的增量累加和。

推广到梯度提升树的函数空间： F ( t ) ( x ) = F ( t − 1 ) ( x ) + f t ( x ) \begin{aligned} F^{(t)}(x)=F^{(t-1)}(x) + f_t(x) \end{aligned} F(t)(x)=F(t−1)(x)+ft​(x)​ 其中第 t t t次迭代的增量为 f t ( x ) = − η ∂ L ∂ F ( t − 1 ) ( x ) f_t(x)=-\eta\frac{\partial L}{\partial F^{(t-1)}(x)} ft​(x)=−η∂F(t−1)(x)∂L​，最终函数 F ( x ) = ∑ t = 0 T f t ( x ) F(x)=\sum_{t=0}^Tf_t(x) F(x)=∑t=0T​ft​(x)。因为梯度下降对应目标函数下降最快的位置，所以最好的优化情况便是每次的增量等于负梯度乘以学习率。所以在下面GBDT算法中我们可以看到，算法每次迭代的目的都是为了拟合梯度。

注意： 这里要讲明白一点：我们优化的当前模型（增量模型），其目标值是负梯度，也就是说，我们不是使用负梯度去拟合残差。而是在GBDT中，我们用负梯度的值近似充当残差的值，然后使用当前模型去拟合负梯度的值（在这个模型优化的过程中，负梯度的值就是真实的y，从下面的算法流程中也可以看到这一点）。

定义GBDT的加法模型： F ( x ; w ) = ∑ t = 0 T f t ( x ; w t ) = ∑ 0 T α t h ( t ) ( x ; w t ) \begin{aligned} F(x;w)=\sum_{t=0}^Tf_t(x;w_t) = \sum_0^{T}\alpha_th^{(t)}(x;w_t) \end{aligned} F(x;w)=t=0∑T​ft​(x;wt​)=0∑T​αt​h(t)(x;wt​)​ 由上面的公式我们可以知道，最优的情况， h ( t ) ( x ) h^{(t)}(x) h(t)(x)是应该拟合梯度的，所以GBDT的思想就是拟合梯度（替代提升树中的残差）来求 h ( t ) ( x ) h^{(t)}(x) h(t)(x)。

GBDT的算法流程和提升树雷同，只是将提升树的残差部分换成了梯度部分（注意：为什么 h ( t ) ( x ; w t ) h^{(t)}(x;w_t) h(t)(x;wt​)前面有个 ρ \rho ρ，这是因为 h ( t ) ( x ; w t ) h^{(t)}(x;w_t) h(t)(x;wt​)拟合的是负梯度，但是满足最优化，负梯度前面还有一个类似学习率的值），其算法流程如下：

输入： 训练数据集 T = ( x 1 , y 1 ) , ( x 2 , y 2 ) , . . . , ( x N , y N ) T={(x_1, y_1), (x_2, y_2), ..., (x_N, y_N)} T=(x1​,y1​),(x2​,y2​),...,(xN​,yN​)，损失函数L(y, F(x)) 输出： 回归树 F ( x ) F(x) F(x) Step1： 初始化 f ( 0 ) ( x ) f^{(0)}(x) f(0)(x) Step2： for t = 1 t=1 t=1 to T T T do                 2.1 计算梯度： h ^ ( t ) ( x i ) = − [ ∂ L ( y i , F ( t − 1 ) ( x i ) ) ∂ F ( t − 1 ) ( x i ) ] , i = 1 , 2 , . . , N \hat{h}^{(t)}(x_i) =-[ \frac{\partial L(y_i, F^{(t-1)}(x_i))}{\partial F^{(t-1)}(x_i)}],i=1,2,..,N h^(t)(xi​)=−[∂F(t−1)(xi​)∂L(yi​,F(t−1)(xi​))​],i=1,2,..,N                 2.2 拟合第 t t t棵树： w ∗ = arg ⁡ min ⁡ w ∑ i = 1 N ( h ^ ( t ) ( x i ) − h ( t ) ( x i ) ) 2 w^*=\mathop{\arg\min}_{w} \sum_{i=1}^N(\hat{h}^{(t)}(x_i) - h^{(t)}(x_i) )^2 w∗=argminw​i=1∑N​(h^(t)(xi​)−h(t)(xi​))2                 2.3 搜索找步长(类似于学习率)： ρ ∗ = arg ⁡ min ⁡ ρ ∑ i = 1 N L ( h ( t ) ( x i ) , F ( t − 1 ) ( x i ) + ρ h ( t ) ( x i , w ∗ ) \rho^*=\mathop{\arg\min}_{\rho}\sum_{i=1}^NL(h^{(t)}(x_i),F^{(t-1)}(x_i) + \rho h^{(t)}(x_i, w^*) ρ∗=argminρ​i=1∑N​L(h(t)(xi​),F(t−1)(xi​)+ρh(t)(xi​,w∗)                 2.4 令 f t ( x ) = ρ ∗ h ( t ) ( x , w ∗ ) f_t(x) =\rho^*h^{(t)}(x,w^*) ft​(x)=ρ∗h(t)(x,w∗)                       更新模型： F ( t ) ( x ) = F ( t − 1 ) ( x ) + f t ( x ) F^{(t)}(x)=F^{(t-1)}(x)+f_t(x) F(t)(x)=F(t−1)(x)+ft​(x) Step3： 输出 F ( t ) ( x ) F^{(t)}(x) F(t)(x)

其实从上面的流程可以看出， h ^ ( t ) ( x i ) \hat{h}^{(t)}(x_i) h^(t)(xi​)在这里充当的角色就是普通线性回归中的真实值 y i y_i yi​。

Xgboost基于二阶泰勒公式，除此之外，在GBDT的基础上，Xgboost引入了正则化。

对于一般的模型，其目标函数定义如下： O b j = ∑ i = 1 n L ( y i , F ( x i ) ) + Ω ( F ( x i ) ) \begin{aligned} Obj = \sum_{i=1}^{n}L(y_i, F(x_i) )+ \Omega (F(x_i)) \end{aligned} Obj=i=1∑n​L(yi​,F(xi​))+Ω(F(xi​))​ 其中， Ω ( F ( x i ) ) \Omega (F(x_i)) Ω(F(xi​))是正则项部分。

对于提升树而言， F t ( x i ) = F t − 1 ( x i ) + f t ( x i ) F_{t}(x_i) = F_{t-1}(x_i) +f_{t}(x_i) Ft​(xi​)=Ft−1​(xi​)+ft​(xi​)，其中 f t ( x i ) f_{t}(x_i) ft​(xi​)是当前加入的新模型，此时，目标函数可以写成： O b j ( t ) = ∑ i = 1 n L ( y i , F t − 1 ( x i ) + f t ( x i ) ) + Ω ( f t ( x i ) ) + 常 数 \begin{aligned} Obj^{(t)} = \sum_{i=1}^{n}L(y_i, F_{t-1}(x_i) +f_{t}(x_i) )+ \Omega (f_t(x_i)) + 常数 \end{aligned} Obj(t)=i=1∑n​L(yi​,Ft−1​(xi​)+ft​(xi​))+Ω(ft​(xi​))+常数​ 此时最优化目标函数 O b j ( t ) Obj^{(t)} Obj(t)，即最优化当前的新模型 f t ( x i ) f_t(x_i) ft​(xi​)，这也说明了Boosting的思想是重点关注那些学习器错误分类的样本。

将 O b j ( t ) Obj^{(t)} Obj(t)在 F t − 1 ( x i ) F_{t-1}(x_i) Ft−1​(xi​)处的泰勒公式展开： O b j ( t ) = ∑ i = 1 n [ L ( y i , F t − 1 ( x i ) ) + L ′ ( y i , F t − 1 ( x i ) ) f t ( x i ) + 1 2 L ′ ′ ( y i , F t − 1 ( x i ) ) f t ( x i ) 2 ] + Ω ( f t ( x i ) ) + 常 数 \begin{aligned} Obj^{(t)} = \sum_{i=1}^{n}[L(y_i, F_{t-1}(x_i)) +L'(y_i, F_{t-1}(x_i)) f_{t}(x_i) +\frac{1}{2}L''(y_i, F_{t-1}(x_i))f_t(x_i)^2]+ \Omega (f_t(x_i)) + 常数 \end{aligned} Obj(t)=i=1∑n​[L(yi​,Ft−1​(xi​))+L′(yi​,Ft−1​(xi​))ft​(xi​)+21​L′′(yi​,Ft−1​(xi​))ft​(xi​)2]+Ω(ft​(xi​))+常数​ 我们记 g i = L ′ ( y i , F t − 1 ( x i ) ) g_i=L'(y_i, F_{t-1}(x_i)) gi​=L′(yi​,Ft−1​(xi​)), h i = 1 2 L ′ ′ ( y i , F t − 1 ( x i ) ) h_i=\frac{1}{2}L''(y_i, F_{t-1}(x_i)) hi​=21​L′′(yi​,Ft−1​(xi​))，因为常数不影响最优化结果，所以为了简单，我们将常数项去掉； L ( y i , F t − 1 ( x i ) ) L(y_i, F_{t-1}(x_i)) L(yi​,Ft−1​(xi​))也是一个常数，所以我们可以直接去掉，则： O b j ( t ) = ∑ i = 1 n [ g i f t ( x i ) + h i f t ( x i ) 2 ] + Ω ( f t ( x i ) ) \begin{aligned} Obj^{(t)} = \sum_{i=1}^{n}[g_i f_{t}(x_i) +h_if_t(x_i)^2]+ \Omega (f_t(x_i)) \end{aligned} Obj(t)=i=1∑n​[gi​ft​(xi​)+hi​ft​(xi​)2]+Ω(ft​(xi​))​ 由于 F t − 1 ( x i ) F_{t-1}(x_i) Ft−1​(xi​)是前一次迭代的整体结果， y i y_i yi​已知，所以最优化 O b j ( t ) Obj^{(t)} Obj(t)就等价于最优化 f t ( x i ) f_{t}(x_i) ft​(xi​)。

假设决策树有 T T T片叶子，每片叶子对应的值 w ∈ R T w \in R^T w∈RT。在决策树中，每一个结点的预测值都是一样的，那么一定存在一个函数 q : R T → { 1 , 2 , . . . , T } q:R^T \rightarrow \{1,2,...,T\} q:RT→{1,2,...,T}，其可以将 f t ( x ) f_t(x) ft​(x)中的每个样本映射到每一个叶子结点上。那么 f t ( x ) f_t(x) ft​(x)就可以转成 w q ( x ) w_{q(x)} wq(x)​，其中 q ( x ) q(x) q(x)代表了每个样本在哪个叶子结点上，而 w q w_q wq​则代表了哪个叶子结点取什么 w w w值，所以 w q ( x ) w_{q(x)} wq(x)​就代表了每个样本的取值 w w w（即预测值）。

模型复杂度可以定义为： Ω ( f t ( x i ) ) = γ T + 1 2 λ ∑ j = 1 T w j 2 \begin{aligned} \Omega (f_t(x_i)) = \gamma T + \frac{1}{2} \lambda \sum_{j=1}^Tw_j^2 \end{aligned} Ω(ft​(xi​))=γT+21​λj=1∑T​wj2​​ 即决策树模型的复杂度由生成的树的叶子节点数量和叶子结点对应的值的向量的L2范数组成。

我们假设 I j = { i ∣ q ( x i ) = j } I_j= \{i|q(x_i)=j \} Ij​={i∣q(xi​)=j}为第 j j j个叶子的样本集合，则带入 O b j ( t ) Obj^{(t)} Obj(t)等式： O b j ( t ) ≈ ∑ i = 1 n [ g i f t ( x i ) + h i f t ( x i ) 2 ] + Ω ( f t ( x i ) ) = ∑ i = 1 n [ g i f t ( x i ) + h i f t ( x i ) 2 ] + γ T + 1 2 λ ∑ j = 1 T w j 2 = ∑ j = 1 T ∑ i ∈ I j g i w j + ∑ j = 1 T ∑ i ∈ I j 1 2 h i w j 2 + γ T + 1 2 λ ∑ j = 1 T w j 2 = ∑ j = 1 T [ ( ∑ i ∈ I j g i ) w j + 1 2 ( ∑ i ∈ I j h i + λ ) w j 2 ] + γ T \begin{aligned} Obj^{(t)} ;\approx \sum_{i=1}^{n}[g_i f_{t}(x_i) +h_if_t(x_i)^2]+ \Omega (f_t(x_i)) \\ ;= \sum_{i=1}^{n}[g_i f_{t}(x_i) +h_if_t(x_i)^2]+\gamma T + \frac{1}{2} \lambda \sum_{j=1}^Tw_j^2 \\ ;= \sum_{j=1}^{T}\sum_{i \in I_j} g_i w_j + \sum_{j=1}^{T}\sum_{i \in I_j} \frac{1}{2}h_iw_j^2 + \gamma T + \frac{1}{2} \lambda \sum_{j=1}^Tw_j^2 \\ ; = \sum_{j=1}^{T} [(\sum_{i \in I_j} g_i) w_j + \frac{1}{2}(\sum_{i \in I_j}h_i + \lambda)w_j^2] + \gamma T \end{aligned} Obj(t)​≈i=1∑n​[gi​ft​(xi​)+hi​ft​(xi​)2]+Ω(ft​(xi​))=i=1∑n​[gi​ft​(xi​)+hi​ft​(xi​)2]+γT+21​λj=1∑T​wj2​=j=1∑T​i∈Ij​∑​gi​wj​+j=1∑T​i∈Ij​∑​21​hi​wj2​+γT+21​λj=1∑T​wj2​=j=1∑T​[(i∈Ij​∑​gi​)wj​+21​(i∈Ij​∑​hi​+λ)wj2​]+γT​ 令 G j = ∑ i ∈ I j g i G_j=\sum_{i \in I_j} g_i Gj​=∑i∈Ij​​gi​， H j = ∑ i ∈ I j h i H_j=\sum_{i \in I_j} h_i Hj​=∑i∈Ij​​hi​，则上式可以写成： O b j ( t ) = ∑ j = 1 T [ G j w j + 1 2 ( H i + λ ) w j 2 ] + γ T \begin{aligned} Obj^{(t)} = \sum_{j=1}^{T} [G_jw_j + \frac{1}{2}(H_i + \lambda)w_j^2] + \gamma T \end{aligned} Obj(t)=j=1∑T​[Gj​wj​+21​(Hi​+λ)wj2​]+γT​ 如果我们已经确定树的结构，即 q q q是确定的，或者说我们已经知道了每个叶子结点有哪些样本，则 G j G_j Gj​和 H j H_j Hj​是确定的，但是 w w w不确定，那么对 w j w_j wj​求导并令其等于 0 0 0： G j + ( H j + λ ) w j = 0 = ; w j ∗ = − G j H j + λ \begin{aligned} ;G_j + (H_j + \lambda)w_j = 0 \\ ;=;w_j^*=-\frac{G_j}{H_j + \lambda} \end{aligned} ​Gj​+(Hj​+λ)wj​=0=>wj∗​=−Hj​+λGj​​​ 将此 w j ∗ w_j^* wj∗​代入 O b j ( t ) Obj^{(t)} Obj(t)，则： O b j ( t ) = ∑ j = 1 T [ G j ( − G j H j + λ ) + 1 2 ( H i + λ ) ( − G j H j + λ ) 2 ] + γ T = − 1 2 ∑ j = 1 T G j 2 H j + λ + γ T \begin{aligned} Obj^{(t)} ;= \sum_{j=1}^{T} [G_j(-\frac{G_j}{H_j + \lambda})+ \frac{1}{2}(H_i + \lambda)(-\frac{G_j}{H_j + \lambda})^2] + \gamma T \\ ;= -\frac{1}{2}\sum_{j=1}^T \frac{G_j^2}{H_j + \lambda} + \gamma T \end{aligned} Obj(t)​=j=1∑T​[Gj​(−Hj​+λGj​​)+21​(Hi​+λ)(−Hj​+λGj​​)2]+γT=−21​j=1∑T​Hj​+λGj2​​+γT​ 计算求得的 O b j ( t ) Obj^{(t)} Obj(t)代表了当指定一个树的结构的时候，目标函数的值最多可以减少多少，也就是增量的含义，一般称其为结构函数。

对于单棵决策树，一种理想的优化状态就是枚举所有可能的树结构，然后找到一棵最优树，过程如下：

Step1: 枚举所有可能的树结构，即 q q q Step2: 计算每种树结构下的目标函数值，即 O b j ( t ) Obj^{(t)} Obj(t)的值。 Step3: 取目标值最佳的树结构，使用 w j ∗ w_j^* wj∗​求解每个叶子节点的 w w w取值，即样本的预测值

但是因为树的结构比较多，枚举法来枚举所有的树结构是实际不可行的，所以一般使用贪心策略来求解：每次尝试分类一个叶节点，计算分裂前后的增益，选择增益最大的，其具体过程如下：

Step1: 从深度为0的树开始，对每个叶子节点枚举所有可用特征。 Step2: 针对每个特征，把属于该节点的训练样本根据该特征值升序排列，通过线性扫描的方式来决定该特征的最佳分裂点，并记录该特征的最大收益（采用最佳分裂点时的收益） Step3: 选择收益最大的特征作为分裂特征，用该特征的最佳分裂点作为分裂位置，把该节点生长出左右两个新的叶节点，并为每个新节点关联对应的样本集 Step4: 回到Step1，递归执行到满足特定条件为止

计算收益的方法如下：假设我们在某一节点上二分裂成两个节点，分别是左（ L L L）右（ R R R），则分裂前的目标函数是 − 1 2 [ G L 2 + G R 2 H L + H R + λ ] + γ -\frac{1}{2}[ \frac{G_L^2+G_R^2}{H_L+H_R+ \lambda} ]+ \gamma −21​[HL​+HR​+λGL2​+GR2​​]+γ，分裂后的目标函数是 − 1 2 [ G L 2 H L + λ + G R 2 H R + λ ] + 2 γ -\frac{1}{2}[\frac{G_L^2}{H_L + \lambda} +\frac{G_R^2}{H_R+ \lambda}]+ 2\gamma −21​[HL​+λGL2​​+HR​+λGR2​​]+2γ，则对于目标函数来说，分裂后的收益是（这里假设是最小化目标函数，所以用分裂前-分裂后，即loss降低了多少）： G a i n = 1 2 [ G L 2 H L + λ + G R 2 H R + λ − G L 2 + G R 2 H L + H R + λ ] − γ \begin{aligned} Gain=\frac{1}{2}[\frac{G_L^2}{H_L + \lambda} +\frac{G_R^2}{H_R+ \lambda} - \frac{G_L^2+G_R^2}{H_L+H_R+ \lambda}]- \gamma \end{aligned} Gain=21​[HL​+λGL2​​+HR​+λGR2​​−HL​+HR​+λGL2​+GR2​​]−γ​ G a i n Gain Gain是计算出来的收益，这个公式跟ID3算法采用信息熵计算增益、C4.5算法使用信息增益率计算增益和CART算法采用基尼指数计算增益是一致的，都是用分裂后的某种值减去分裂前的某种值，从而得到增益。关于分割点的详细算法请参见论文：Xgboost: A scalable tree boosting system。

为了限制树的生长，我们可以加入阈值，当增益大于阈值时才让节点分裂，上式中的 γ \gamma γ即阈值，它是正则项里叶子节点数 T T T的系数，所以Xgboost在优化目标函数的同时相当于做了预剪枝。另外，上式中还有一个系数 λ \lambda λ，是正则项里关于叶子节点的L2模平方的系数，对叶子节点的复杂度做了平滑，也起到了防止过拟合的作用，这个是传统GBDT里不具备的特性。

所以Xgboost的算法可以总结为：

Step1： 算法在拟合的每一步都新生成一颗回归树； Step2： 在拟合这棵树之前，需要计算损失函数在每个样本上的一阶导数和二阶导数，即 g i g_{i} gi​和 h i h_{i} hi​； Step3： 通过上面的贪心策略生成一颗树，计算每个叶子结点的的 G j G_{j} Gj​和 H j H_{j} Hj​，利用 w ∗ w^* w∗的公式预测值 w w w； Step4： 把新生成的回归树 f t ( x ) f_t(x) ft​(x)加入 y ^ i t = y ^ i t − 1 + ϵ f t ( x i ) \hat{y}_i^t = \hat{y}_i^{t-1} + \epsilon f_t(x_i) y^​it​=y^​it−1​+ϵft​(xi​)，其中 ϵ \epsilon ϵ为学习率，主要为了抑制模型的过拟合。

Random Forest和GBDT区别如下：

①RF的基分类器可以是分类树也可以是回归树，GBDT只能是回归树。 ②RF不同基分类器可以并行，GBDT只能串行。 ③RF最终结果采用的策略是多数投票、一票否则、加权投票等，而GBDT是将所有结果（加权）累加起来。 ④RF对异常值不敏感，GBDT对异常值敏感 ⑤RF对训练集一视同仁，GBDT基于Boosting思想，基于权值，分类器越弱，权值越小 ⑥RF主要减少模型方差，所以在噪声较大的数据上容易过拟合，而GBDT主要较少模型偏差。 ⑦RF随机选择样本，GBDT使用所有样本。

Xgboost就是GBDT的一种，所以Xgboost和RF的区别和GBDT一样。

GBDT和Xgboost的区别如下：

①基分类器的选择： 传统GBDT以CART作为基分类器，XGBoost还支持线性分类器，这个时候XGBoost相当于带L1和L2正则化项的逻辑斯蒂回归（分类问题）或者线性回归（回归问题）。 ②梯度信息： 传统GBDT只引入了一阶导数信息，Xgboost引入了一阶导数和二阶导数信息，其对目标函数引入了二阶近似，求得解析解, 用解析解作为Gain来建立决策树, 使得目标函数最优（Gain求到的是解析解）。另外，XGBoost工具支持自定义损失函数，只要函数可一阶和二阶求导。 ③正则项： Xgboost引入了正则项部分，这是传统GBDT中没有的。加入正则项可以控制模型的复杂度，防止过拟合。 ④特征采样： Xgboost引入了特征子采样，像随机森林那样，既可以降低过拟合，也可以减少计算。 ⑤节点分裂方式：GBDT是用的基尼系数，XGBoost是经过优化推导后的。 ⑥并行化： 传统GBDT由于树之间的强依赖关系是无法实现并行处理的，但是Xgboost支持并行处理，XGBoost的并行不是在模型上的并行，而是在特征上的并行，将特征列排序后以block的形式存储在内存中，在后面的迭代中重复使用这个结构。这个block也使得并行化成为了可能，其次在进行节点分裂时，计算每个特征的增益，最终选择增益最大的那个特征去做分割，那么各个特征的增益计算就可以开多线程进行。 ⑦除此之外，Xgboost实现了分裂点寻找近似算法、缺失值处理、列抽样（降低过拟合，还能减少计算）等包括一些工程上的优化，LightGBM是Xgboost的更高效实现。

参考文章： [1] A Kaggle Master Explains Gradient Boosting [2] GBDT (Gradient Boosting Decision Tree) [3] 机器学习-一文理解GBDT的原理-20171001 [4] GBDT算法原理深入解析 [5] GBDT算法原理与系统设计简介 [6] 机器学习算法系列（8）：XgBoost [7] gbdt的残差为什么用负梯度代替？ [8] Friedman J H. Greedy function approximation: a gradient boosting machine[J]. Annals of statistics, 2001: 1189-1232. [9] Chen T, Guestrin C. Xgboost: A scalable tree boosting system[C]//Proceedings of the 22nd acm sigkdd international conference on knowledge discovery and data mining. ACM, 2016: 785-794.