机器学习算法中GBDT与Adaboost的区别与联系是什么?

GBDT可用于classification与regression,我的理解是classification是Log Loss, regreesion是平方Loss,采用回归树去拟合残差或者Loss Fuction的导数,AdaBoost是向前加项模型,采用指数损失,是分类树做基分类器,调整错分类的点的observation probability,不知理解是否正确,求大神进一步从深层次分析一下两者的区别和联系 另外,GBDT做分类与逻辑回归的区别是什么?是否可以理解为寻找的是非线性分界面?为什么会比lr效果好?
关注者
126
被浏览
8,451

谢邀,试答一下。

Boosting算法

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

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。

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

有一组数据(x_1,y_1),...,(x_m,y_m)和一个基础模型F 就像你说的我们想要最小化预测值F(x_i) 和真实值y_i 之间的square loss。对于任意i ,使得1\le i \le m ,我们称h_i=y_i-F(x_i) 为关于x_i 的残差。我们可以训练一个回归树h来拟合数据组(x_1, y_1-F(x_1)),...,(x_m, y_m-F(x_m)) 。这样我们就得到了一个更好的模型F+h ,重复这一过程,我们最终得到了一个让人满意的模型。

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

对于任意i,使得1 \le i \le m,预测值和真实值之间的square loss为(y_i-F(x_i))^2 ,我们注意到\underset{F}{\mathrm{argmin}} (y-F(x))^2\\ = \underset{F}{\mathrm{argmin}} (y-F(x))^2/2\\ , 令L(y_i, F(x_i)) = (y_i-F(x_i))^2/2 , 目标函数J = \sum_i L(y_i, F(x_i)) , J 关于F(x_i) 的偏导数由链式法则可得正好是F(x_i)-y_i ,则y_i-F(x_i) 恰好是y_i-F(x_i) = -\frac{\partial J}{\partial F(x_i)} 。因此在这里用回归树拟合残差实际上就是用回归树拟合负梯度(当损失函数不为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和线性回归或逻辑回归在某个问题上表现接近,那么我们应该选择相对比较简单的线性回归或逻辑回归。具体选择哪一个算法还是要根据实际问题来决定。


参考:

  1. cs.nyu.edu/~mohri/mls/m
  2. chengli.io/tutorials/gr