Adaboost, GBDT 与 XGBoost 的区别

最近总结树模型，尝试将主流 Boosting 实现方式做一个分析汇总，文中部分内容借鉴了知乎答案，已于参考链接中标识。

1. Boosting算法

Boosting算法特征如下：通过将一些表现效果一般（可能仅仅优于随机猜测）的模型通过特定方法进行组合来获得一个表现效果较好的模型。从抽象的角度来看，Boosting算法是借助convex loss function在函数空间进行梯度下降的一类算法。Gradient Boost和Adaboost就是其中比较常见的两种。

2. AdaBoost（Adaptive Boosting)

由 Yoav Freund 和 Robert Schapire 提出，两人因此获得了哥德尔奖。

为了比较好地理解 AdaBoost，先来看下下面这些图。

二元分类问题，如何划分红球和篮球。显然这个问题用一个线性分类器的话很难取得最好的效果。有没有办法通过组合一系列和正方形平行的线（每条线都相当于一个线性分类器）来获得一个比较好的分类效果呢？

第一步：先矮子里拔将军，选择一条平行于四边且最不坏的线段。下图第一排中间的小图里，直线把图分为左边（红点）和右边（蓝点）两类，被错分的点只有3个，这似乎是能得到的最好的结果了。然后我们想去找第二条线（第二个线性分类器）。如果只是基于现有的这些点的话那么说不定得到的线段还是和之前那条差不多，那多个线段（线性分类器）就没有意义了。所以我们要稍微调整一下某些点在分类结果里的重要性，提升他们的权重。我们在这里提升了那三个被错分的点的权重。

第二步：我们找到了一条新的线段，因为之前提升了把蓝点和蓝点分在一起的重要性，所以这条线段没有选择平行于上下两边把上面4个点（1红3蓝）和下面7个点（5红2蓝）分开，而是选择尽可能多地把蓝点归在一起。然而这次不同的是我们分错的是右边那4个红点，于是我们放大那4个红点，提升他们的权重。

不断重复这一过程。

最终我们得到了多个线性分类器，把这些线性分类器的结果做一个线性组合，我们就得到了整个集成模型的结果。每个线性分类器的结果的系数（权重）取决于它的表现，表现越好，权重越高。比如第一条线段的分类错误就优于第二条线段，那么它获得的权重也就会更大。集成模型的效果非常好。

顺带一提，第一条线段的分类正确率是8/11，第二条线段的分类正确率是7/11，第三条线段的分类正确率是8/11，确实要好于随机猜测（以1/2为界）。

图片来源：Mehryar Mohris Foundations of Machine Learning的上课讲义cs.nyu.edu/~mohri/mls/m

把 AdaBoost 和一开始对 Boosting 算法的定义比较看看，我们确实通过组合一系列表现一般的模型获得了一个表现优秀的模型。另外值得注意的是在训练过程中，每个新的模型都会基于前一个模型的表现结果进行调整，这也就是为什么 AdaBoost 是自适应（adaptive）的原因。

算法如下：

图片来源：同上。

AdaBoost确实采用的是指数损失，基分类器最常见的是决策树（在很多情况下是决策树桩，深度为1的决策树）。在每一轮提升相应错分类点的权重可以被理解为调整错分类点的observation probability。

3. Gradient Boosting

在 AdaBoost 发表后不久，Breiman 等人发表了 Formulate AdaBoost as gradient descent with a special loss function。随后 Friedman 等人发表了 Generalize AdaBoost to Gradient Boosting in order to handle a variety of loss functions。可以说 AdaBoost 是 Gradient Boosting 的一个特例或者Gradient Boosting是对AdaBoost进行推广。

Gradient Boosting 和其它 Boosting 算法一样，通过将表现一般的数个模型（通常是深度固定的决策树）组合在一起来集成一个表现较好的模型。抽象地说，模型的训练过程是对一任意可导目标函数的优化过程。通过反复地选择一个指向负梯度方向的函数，该算法可被看做在函数空间里对目标函数进行优化。因此可以说 Gradient Boosting = Gradient Descent + Boosting。

和 AdaBoost 一样，Gradient Boosting 也是重复选择一个表现一般的模型并且每次基于先前模型的表现进行调整。不同的是，AdaBoost 是通过提升错分数据点的权重来定位模型的不足而 Gradient Boosting 是通过算梯度（gradient）来定位模型的不足。因此相比 AdaBoost, Gradient Boosting 可以使用更多种类的目标函数。

Gradient Boosting for Regression

有一组数据

和一个基础模型 F 就像你说的我们想要最小化预测值

和真实值

之间的 square loss。对于任意 i，使得

，我们称

为关于

的残差。我们可以训练一个回归树 h 来拟合数据组

。这样我们就得到了一个更好的模型

，重复这一过程，我们最终得到了一个让人满意的模型。

用回归树去拟合残差其实就是用回归树去拟合目标方程关于$F(x_i)$ 的梯度。

对于任意 i，使得

，预测值和真实值之间的square loss为

，我们注意到

令

, 目标函数

, J 关于

的偏导数由链式法则可得正好是

，则

恰好是

。因此在这里用回归树拟合残差实际上就是用回归树拟合负梯度（当损失函数不为square loss时残差并不一定等于负梯度！）。我们实际上是在通过梯度下降法对模型参数进行更新。这样理解的好处在于我们可以把这一算法推广到其它的损失函数上。

图片来源：Li, Cheng. chengli.io/tutorials/gr

要注意regression并不一定会用square loss。square loss的优点是便于理解和实现，缺点在于对于异常值它的鲁棒性较差，如下图：

图片来源：同上。

一个异常值造成的损失由于二次幂而被过分放大，会影响到最后得到模型在测试集上的表现。

因此我们有时候会选择其它的损失函数，如absolute loss或Huber loss（标红色星号的数据为异常值）:

图片来源：同上。

梯度下降法的思想使得我们可以非常轻易地改用不同的损失函数设计Gradient Boosting算法。另外在使用某些其它损失函数时（如Huber loss），残差相比负梯度更容易受到异常值的影响。

Gradient Boosting for Classification

基于回归树的Gradient Boosting除了回归问题外还可以做分类问题、排序问题等。

对于分类问题，很多时候我们是要去获得一个概率分布去逼近真正的概率分布，因此很多时候就会基于log loss来构建目标函数，如KL-divergence或cross entropy。但有时候也可能使用其它损失函数，可以参考一下Loss functions for classification 。

除了损失函数的区别外，分类问题和回归问题的区别还在于当我有多个类的时候，我可能会训练多个分类器。比如如果要去识别手写字母的话，我可能会训26个分类器来分别去求该手写字母为A/.../Z的概率。

由于决策树是非线性的（并且随着深度的加深非线性越来越强），基于决策树的GBDT也是非线性的。

AdaBoost V.S. GBDT

最主要的区别在于两者如何识别模型的问题。AdaBoost用错分数据点来识别问题，通过调整错分数据点的权重来改进模型。Gradient Boosting通过负梯度来识别问题，通过计算负梯度来改进模型。

GBDT V.S. LR(Linear Regression? Logistic Regression?)

从决策边界来说，线性回归的决策边界是一条直线，逻辑回归的决策边界根据是否使用核函数可以是一条直线或者曲线，而GBDT的决策边界可能是很多条线。

逻辑回归算法在某一数据集上得到的决策边界。来源：Andrew Ng在Coursera上机器学习的讲义。

GBDT并不一定总是好于线性回归或逻辑回归。根据没有免费的午餐原则，没有一个算法是在所有问题上都能好于另一个算法的。根据奥卡姆剃刀原则，如果GBDT和线性回归或逻辑回归在某个问题上表现接近，那么我们应该选择相对比较简单的线性回归或逻辑回归。具体选择哪一个算法还是要根据实际问题来决定。

总结来说，GBDT算法基树采用CART回归树，树节点的划分指标是平方损失函数，叶子节点的值是落在该叶子节点所有样本的目标均值。树与树之间的Boosting逻辑是：新树拟合的目标是上一课树的损失函数的负梯度的值。GBDT最终的输出结果是将样本在所有树上的叶子值相加。

4. GBDT 与 XGBoost 区别

• 传统GBDT以CART作为基分类器，xgboost还支持线性分类器，这个时候xgboost相当于带L1和L2正则化项的逻辑斯蒂回归（分类问题）或者线性回归（回归问题）。
• 传统GBDT在优化时只用到一阶导数信息，xgboost则对代价函数进行了二阶泰勒展开，同时用到了一阶和二阶导数。顺便提一下，xgboost工具支持自定义代价函数，只要函数可一阶和二阶求导。
• xgboost在代价函数里加入了正则项，用于控制模型的复杂度。正则项里包含了树的叶子节点个数、每个叶子节点上输出的score的L2模的平方和。从Bias-variance tradeoff角度来讲，正则项降低了模型的variance，使学习出来的模型更加简单，防止过拟合，这也是xgboost优于传统GBDT的一个特性。
• Shrinkage（缩减），相当于学习速率（xgboost中的eta）。xgboost在进行完一次迭代后，会将叶子节点的权重乘上该系数，主要是为了削弱每棵树的影响，让后面有更大的学习空间。实际应用中，一般把eta设置得小一点，然后迭代次数设置得大一点。（补充：传统GBDT的实现也有学习速率）
• 列抽样（column subsampling）。xgboost借鉴了随机森林的做法，支持列抽样，不仅能降低过拟合，还能减少计算，这也是xgboost异于传统gbdt的一个特性。
• 对缺失值的处理。对于特征的值有缺失的样本，xgboost可以自动学习出它的分裂方向。
• xgboost工具支持并行。boosting不是一种串行的结构吗?怎么并行的？注意xgboost的并行不是tree粒度的并行，xgboost也是一次迭代完才能进行下一次迭代的（第t次迭代的代价函数里包含了前面t-1次迭代的预测值）。xgboost的并行是在特征粒度上的。我们知道，决策树的学习最耗时的一个步骤就是对特征的值进行排序（因为要确定最佳分割点），xgboost在训练之前，预先对数据进行了排序，然后保存为block结构，后面的迭代中重复地使用这个结构，大大减小计算量。这个block结构也使得并行成为了可能，在进行节点的分裂时，需要计算每个特征的增益，最终选增益最大的那个特征去做分裂，那么各个特征的增益计算就可以开多线程进行。
• 可并行的近似直方图算法。树节点在进行分裂时，我们需要计算每个特征的每个分割点对应的增益，即用贪心法枚举所有可能的分割点。当数据无法一次载入内存或者在分布式情况下，贪心算法效率就会变得很低，所以xgboost还提出了一种可并行的近似直方图算法，用于高效地生成候选的分割点。（就是 XGBoost 论文中介绍的加权直方图，这里权值是特征的二阶梯度，因为其目标函数可以化简为二次项系数为 H 的二次多项式）

此外，还有一点值得注意的是，对于 XGBoost 与 GBDT，其 Boosting 损失函数函数都是可自定义的，但 XGBoost 需要自定义损失函数二阶可导，而 GBDT 只需要一阶可导；其次，对于基模型拟合差异（对于 XGBoost 就是拟合

，对于 GBDT 就是拟合

），其内部的拟合函数不同，XGBoost 是自己定义的一套增益规则，而 GBDT 就是 CART 树的二阶平方损失拟合。

“xgboost代价函数里加入正则项，是否优于cart的剪枝”。其实陈天奇大神的slides里面也是有提到的，我当一下搬运工。

决策树的学习过程就是为了找出最优的决策树，然而从函数空间里所有的决策树中找出最优的决策树是NP-C问题，所以常采用启发式（Heuristic）的方法，如CART里面的优化GINI指数、剪枝、控制树的深度。这些启发式方法的背后往往隐含了一个目标函数，这也是大部分人经常忽视掉的。xgboost的目标函数如下：

其中正则项控制着模型的复杂度，包括了叶子节点数目T和leaf score的L2模的平方：

那这个跟剪枝有什么关系呢？？？跳过一系列推导，我们直接来看xgboost中树节点分裂时所采用的公式：

这个公式形式上跟ID3算法（采用entropy计算增益） 、CART算法（采用gini指数计算增益） 是一致的，都是用分裂后的某种值 减去 分裂前的某种值，从而得到增益。为了限制树的生长，我们可以加入阈值，当增益大于阈值时才让节点分裂，上式中的gamma即阈值，它是正则项里叶子节点数T的系数，所以xgboost在优化目标函数的同时相当于做了预剪枝。另外，上式中还有一个系数lambda，是正则项里leaf score的L2模平方的系数，对leaf score做了平滑，也起到了防止过拟合的作用，这个是传统GBDT里不具备的特性。

5. 总结：

1. Adaboost 与 GBDT 两者 boosting 的不同策略是两者的本质区别。
2. Adaboost强调Adaptive（自适应），通过不断修改样本权重（增大分错样本权重，降低分对样本权重），不断加入弱分类器进行boosting，有文章指出，可以将 Adaboost 看作是 GBDT 的一种特例，个人认为，是否非要这样看见仁见智，无需强求。
3. GBDT 则是在确定损失函数后，本轮 cart 树的拟合目标就是沿着损失函数相对于前一轮组合树模型的负梯度方向进行拟合，也就是希望最快速度地最小化预测值与真实值之间的差异；当损失函数选择为 square loss 时候，其沿着负梯度方向拟合表现为拟合残差（选择其他损失函数不一定表现出拟合残差的性质）

总结来说，GBDT算法基树采用CART回归树，树节点的划分指标是平方损失函数，叶子节点的值是落在该叶子节点所有样本的目标均值。树与树之间的Boosting逻辑是：新树拟合的目标是上一轮目标函数负梯度的值，而这个损失函数也可以自定义，只需满足具备一阶可导即可。GBDT最终的输出结果是将样本在所有树上的叶子值相加。 当选定损失函数为 square loss 时，用回归树去拟合残差其实就是用回归树去拟合目标方程关于

的梯度。对于任意 i，使得

，预测值和真实值之间的square loss为

，我们注意到

令

, 目标函数

, J 关于

的偏导数由链式法则可得正好是

，则

恰好是

。因此在这里用回归树拟合残差实际上就是用回归树拟合负梯度（当损失函数不为square loss时残差并不一定等于负梯度！）。我们实际上是在通过梯度下降法对模型参数进行更新。这样理解的好处在于我们可以把这一算法推广到其它的损失函数上。

1. 而 XGBoost 的 boosting 策略则与 GBDT 类似，均是旨在新加入的基分类器进一步拟合预测值与真实值之间的差异（不一定是残差），只不过 GBDT 是沿着负梯度的方向进行拟合(

)，只用到了一阶梯度信息，而 XGBoost 则是直接进行 loss function 进行二阶泰勒展开，得到

，

是正则叶子分数约束系数，相比于 GBDT，其拟合方向更准、速度更快；

1. XGBoost, GBDT 均支持自定义损失函数，但 XGBoost 进行基分类器拟合的时候需要一阶、二阶梯度信息，故而需要自定义损失函数提供一阶、二阶梯度信息，而 GBDT 因为只用到一阶梯度信息，故而只需提供自定义损失函数的一阶梯度信息；
2. XGBoost 可以看做是 GBDT 的一种升级版实现，其中需要明确的一个概念是，XGBoost 是 Boosting 框架的一种实现结构， lightgbm 也是一种框架实现结构，而 GBDT 则是一种算法实现，其基分类器为 CART 树，可以处理分类、回归任务，处理分类任务则是将分类任务利用 softmax 转换为回归任务进行求解，具体过程可参考博客 CTR 预测理论（五）：集成学习之Boosting家族(AdaBoost+GBDT)；
3. XGBoost 相比于 GBDT 的差别主要就是 XGBoost 做的优化，其主要内容可参考本博客第 4 小节

一个十分值得注意的点是：虽然 GBDT 是采用的 CART 树作为基分类器，但要主要两个损失函数：一是 Boosting 过程中前一轮模型与实际值之间的损失函数，另一个是当前轮 CART 树本身进行拟合前一轮预测值与真实值差异相对于前一轮组合模型的 CART 自身的损失函数，CART 自身的损失函数是确定的，对回归是平方损失函数，但 Boosting 求前轮预测与实际值之前的损失函数则是可以自由选定的，前提是可以一阶可导！ XGBoost 对目标函数直接进行泰勒展开，其泛化形式支持自定义损失函数，当前轮基分类器拟合的目标是

；GBDT 是否也是支持自定义损失函数？首先说下我个人看法，GBDT 也同样支持自定义损失函数，其拟合目标是

，即负梯度，但 GBDT 的基分类器已经确定是 CART 树，故而对回归问题，当确定好 Boosting 的损失函数后，计算出前一轮的

，利用 CART 树的平方损失进行建树拟合

，而对于分类问题，CART 树对分类问题是采用 softmax + 回归解决的。

参考文献：

1. cs.nyu.edu/~mohri/mls/m
2. chengli.io/tutorials/gr
3. 机器学习算法中GBDT与Adaboost的区别与联系是什么？
4. 梯度提升树中为什么说目标函数关于当前模型的负梯度是残差的近似值？
5. 机器学习算法中 GBDT 和 XGBOOST 的区别有哪些？