机器学习算法中GBDT与AdaBoost的区别与联系


=Start=

缘由:

最近在看《机器学习》这本书,想简单了解一下机器学习原理、算法相关的内容,避免被时代抛下。。。

但时间没那么充裕,意志也没那么坚定,看的断断续续的。不过趁着今天有些时间,学习、整理一下之前听的比较多的GBDT、XGBoost、AdaBoost等算法的概念(这里不涉及具体的公式和证明,一个是自己现在也看不明白,再一个就是网上的很多其他文章已经讲的很多了),从兴趣入手,一点一点的积累可能更适合我现在的状态。

正文:

参考解答:

在正式谈机器学习算法AdaBoost、GBDT与XGBoost的区别之前,有必要先了解一下集成学习(ensemble learning)

所谓集成学习,是指通过构建多个分类器(弱分类器)对数据集进行预测,然后用某种策略将多个分类器预测的结果集成起来,作为最终预测结果。通俗比喻就是“三个臭皮匠赛过诸葛亮”,或一个公司董事会上的各董事投票决策,它要求每个弱分类器具备一定的“准确性”,分类器之间具备“差异性”。有时集成学习也被称为多分类器系统(multi-classifier system)、基于委员会的学习(committee-based learning)等。

集成学习根据各个弱分类器之间有无依赖关系,分为Boosting和Bagging两大流派:

  • Boosting流派,各分类器之间有依赖关系,必须串行,比如AdaBoost、GBDT(Gradient Boosting Decision Tree)、XGBoost。
  • Bagging流派,各分类器之间没有依赖关系,可各自并行,比如随机森林(Random Forest)。

Boosting方法的思想

Boosting的思想其实相当的简单,大概是,对一份数据,建立M个模型(比如分类),一般这种模型比较简单,称为弱分类器(weak learner),每次分类都将上一次分错的数据权重提高一点再进行分类,这样最终得到的分类器在测试数据与训练数据上都可以得到比较好的成绩。可以想象得到,程序越往后执行,训练出的模型就越会在意那些容易分错(权重高)的点。当全部的程序执行完后,会得到M个模型,分别对应y1(x)…yM(x),通过加权的方式组合成一个最终的模型YM(x)。

我觉得Boosting更像是一个人学习的过程,开始学一样东西的时候,会去做一些习题,但是常常连一些简单的题目都会弄错,但是越到后面,简单的题目已经难不倒他了,就会去做更复杂的题目,等到他做了很多的题目后,不管是难题还是简单的题都可以解决掉了。

Gradient Boosting方法

Gradient Boosting是一种Boosting的方法,它主要的思想是,每一次建立模型是在之前建立模型损失函数的梯度下降方向。这句话有一点拗口,损失函数(loss function)描述的是模型的不靠谱程度,损失函数越大,则说明模型越容易出错(其实这里有一个方差、偏差均衡的问题,但是这里就假设损失函数越大,模型越容易出错)。如果我们的模型能够让损失函数持续的下降,则说明我们的模型在不停的改进,而最好的方式就是让损失函数在其梯度(Gradient)的方向上下降。


AdaBoost

AdaBoost,是英文”Adaptive Boosting”(自适应增强)的缩写,由Yoav Freund和Robert Schapire在1995年提出。它的自适应在于:前一个基本分类器分错的样本会得到加强,加权后的全体样本再次被用来训练下一个基本分类器。同时,在每一轮中加入一个新的弱分类器,直到达到某个预定的足够小的错误率或达到预先指定的最大迭代次数。

具体说来,整个Adaboost 迭代算法就3步:

  1. 初始化训练数据的权值分布。如果有N个样本,则每一个训练样本最开始时都被赋予相同的权值:1/N。
  2. 训练弱分类器。具体训练过程中,如果某个样本点已经被准确地分类,那么在构造下一个训练集中,它的权值就被降低;相反,如果某个样本点没有被准确地分类,那么它的权值就得到提高。然后,权值更新过的样本集被用于训练下一个分类器,整个训练过程如此迭代地进行下去。
  3. 将各个训练得到的弱分类器组合成强分类器。各个弱分类器的训练过程结束后,加大分类误差率小的弱分类器的权重,使其在最终的分类函数中起着较大的决定作用,而降低分类误差率大的弱分类器的权重,使其在最终的分类函数中起着较小的决定作用。换言之,误差率低的弱分类器在最终分类器中占的权重较大,否则较小。
GBDT(Gradient Boost Decision Tree, 梯度增强决策树)

另一种Boosting方法GBDT(Gradient Boost Decision Tree),则与AdaBoost不同,GBDT每一次的计算是都为了减少上一次的残差,进而在残差减少(负梯度)的方向上建立一个新的模型。

XGBoost

事实上,如果不考虑工程实现、解决问题上的一些差异,XGBoost与GBDT比较大的不同就是目标函数的定义。它们的策略类似,区别在于GBDT旨在通过不断加入新的树最快速度降低残差,而XGBoost则可以人为定义损失函数(可以是最小平方差、logistic loss function、hinge loss function或者人为定义的loss function),只需要知道该loss function对参数的一阶、二阶导数便可以进行boosting,其进一步增大了模型的泛化能力,其贪婪法寻找添加树的结构以及loss function中的损失函数与正则项等一系列策略也使得XGBoost预测更准确


## 随机森林

随机森林顾名思义,是用随机的方式建立一个森林,森林里面有很多的决策树组成,随机森林的每一棵决策树之间是没有关联的。在得到森林之后,当有一个新的输入样本进入的时候,就让森林中的每一棵决策树分别进行一下判断,看看这个样本应该属于哪一类(对于分类算法),然后看看哪一类被选择最多,就预测这个样本为那一类。

在建立每一棵决策树的过程中,有两点需要注意 – 采样完全分裂首先是两个随机采样的过程,random forest对输入的数据要进行行、列的采样。对于行采样,采用有放回的方式,也就是在采样得到的样本集合中,可能有重复的样本。假设输入样本为N个,那么采样的样本也为N个。这样使得在训练的时候,每一棵树的输入样本都不是全部的样本,使得相对不容易出现over-fitting。然后进行列采样,从M个feature中,选择m个(m << M)。之后就是对采样之后的数据使用完全分裂的方式建立出决策树,这样决策树的某一个叶子节点要么是无法继续分裂的,要么里面的所有样本的都是指向的同一个分类。一般很多的决策树算法都一个重要的步骤 – 剪枝,但是这里不这样干,由于之前的两个随机采样的过程保证了随机性,所以就算不剪枝,也不会出现over-fitting。

按这种算法得到的随机森林中的每一棵都是很弱的,但是大家组合起来就很厉害了。我觉得可以这样比喻随机森林算法:每一棵决策树就是一个精通于某一个窄领域的专家(因为我们从M个feature中选择m让每一棵决策树进行学习),这样在随机森林中就有了很多个精通不同领域的专家,对一个新的问题(新的输入数据),可以用不同的角度去看待它,最终由各个专家,投票得到结果。

## GBDT(Gradient Boosting Decision Tree)

GBDT是一个应用很广泛的算法,可以用来做分类、回归。在很多的数据上都有不错的效果。GBDT这个算法还有一些其他的名字,比如说MART(Multiple Additive Regression Tree),GBRT(Gradient Boost Regression Tree),Tree Net等,其实它们都是一个东西(参考自wikipedia – Gradient Boosting),发明者是Friedman。

Gradient Boost其实是一个框架,里面可以套入很多不同的算法,可以参考一下机器学习与数学(3)中的讲解。Boost是”提升”的意思,一般Boosting算法都是一个迭代的过程,每一次新的训练都是为了改进上一次的结果。

原始的Boost算法是在算法开始的时候,为每一个样本赋上一个权重值,初始的时候,大家都是一样重要的。在每一步训练中得到的模型,会使得数据点的估计有对有错,我们就在每一步结束后,增加分错的点的权重,减少分对的点的权重,这样使得某些点如果老是被分错,那么就会被“严重关注”,也就被赋上一个很高的权重。然后等进行了N次迭代(由用户指定),将会得到N个简单的分类器(basic learner),然后我们将它们组合起来(比如说可以对它们进行加权、或者让它们进行投票等),得到一个最终的模型。

而Gradient Boost与传统的Boost的区别是,每一次的计算是为了减少上一次的残差(residual),而为了消除残差,我们可以在残差减少的梯度(Gradient)方向上建立一个新的模型。所以说,在Gradient Boost中,每个新的模型的建立是为了使得之前模型的残差往梯度方向减少,与传统Boost对正确、错误的样本进行加权有着很大的区别。

 

参考链接:

=END=


《“机器学习算法中GBDT与AdaBoost的区别与联系”》 有 12 条评论

  1. 深度学习500问,以问答形式对常用的概率知识、线性代数、机器学习、深度学习、计算机视觉等热点问题进行阐述,以帮助自己及有需要的读者。 全书分为18个章节,近30万字。由于水平有限,书中不妥之处恳请广大读者批评指正。 未完待续…
    https://github.com/scutan90/DeepLearning-500-questions

  2. 算法学习思路
    http://jartto.wang/2019/04/07/learn-algorithm/
    `
    一、为什么学习算法?
    二、如何入门?
    三、后面的路怎么走?
    1.入门系列:
    《算法图解》《大话数据结构》
    2.教科书之类:
    《数据结构与算法分析》
    3.进阶之旅:
    《算法导论》
    4.针对面试准备:
    《剑指 Offer》《编程珠玑》
    5.扩展阅读:
    《算法之美》《算法帝国》
    6.实践操作:
    《算法竞赛入门经典》《力扣题库》
    四、配合实践
    五、推荐学习

    六、总结
    文章陆陆续续说了这么多,大体总结如下:
    1.算法很重要,尤其是对于前端童鞋;
    2.算法学习最好由浅入深,先了解算法思维,再去理解实际应用;
    3.从一本小而薄的书开启,逐步全面的掌握相关知识体系;
    4.推荐速成路线:《算法图解》-《剑指 Offer》- LeetCode 刷题 -《算法之美》-《算法导论》;
    5.去努力实践,刷刷题库,参加参加竞赛;
    `

  3. 理解AdaBoost算法
    https://mp.weixin.qq.com/s/CL1w5OxTLFD5pRStY6RiyA
    `
    AdaBoost算法的全称是自适应Boosting(Adaptive Boosting),是一种二分类器,它用弱分类器的线性组合构造强分类器。弱分类器的性能不用太好,只需要比随机猜测强,依靠它们可以构造出一个非常准确的强分类器。

    训练时,依次训练每一个弱分类器,并得到它们的权重值。训练样本同样带有权重,初始时所有样本的权重相等,被前面的弱分类器错分的样本会加大权重,反之会减小权重,因此接下来的弱分类器会更加关注这些难分的样本。弱分类器的权重值根据它的准确率构造,精度越高的弱分类器权重越大。

    AdaBoost算法最成功的应用之一是机器视觉里的目标检测问题,如人脸检测和行人检测。车辆检测。在深度卷积神经网络用于此问题之前,AdaBoost算法在视觉目标检测领域的实际应用上一直处于主导地位。

    在2001年Viola和Jones设计了一种人脸检测算法。它使用简单的Haar特征和级联AdaBoost分类器构造检测器,检测速度较之前的方法有2个数量级的提高,并且有很高的精度,我们称这种方法为VJ框架。VJ框架是人脸检测历史上有里程碑意义的一个成果,奠定了AdaBoost目标检测框架的基础。
    `

  4. 决策树、随机森林、bagging、boosting、Adaboost、GBDT、XGBoost总结
    https://zhuanlan.zhihu.com/p/75468124
    `
    综合以上所述,我们可以得到xgboost相比于GBDT的创新之处:

    传统GBDT以CART作为基分类器,xgboost还支持线性分类器,这个时候xgboost相当于带L1和L2正则化项的逻辑斯蒂回归(分类问题)或者线性回归(回归问题)。

    传统GBDT在优化时只用到一阶导数信息,xgboost则对代价函数进行了二阶泰勒展开,同时用到了一阶和二阶导数。顺便提一下,xgboost工具支持自定义代价函数,只要函数可一阶和二阶求导。

    xgboost在代价函数里加入了正则项,用于控制模型的复杂度。正则项里包含了树的叶子节点个数、每个叶子节点上输出的score的L2模的平方和。从Bias-variance tradeoff角度来讲,正则项降低了模型的variance,使学习出来的模型更加简单,防止过拟合,这也是xgboost优于传统GBDT的一个特性。

    Shrinkage(缩减),相当于学习速率(xgboost中的eta)。每次迭代,增加新的模型,在前面成上一个小于1的系数,降低优化的速度,每次走一小步逐步逼近最优模型比每次走一大步逼近更加容易避免过拟合现象;

    列抽样(column subsampling)。xgboost借鉴了随机森林的做法,支持列抽样(即每次的输入特征不是全部特征),不仅能降低过拟合,还能减少计算,这也是xgboost异于传统gbdt的一个特性。

    忽略缺失值:在寻找splitpoint的时候,不会对该特征为missing的样本进行遍历统计,只对该列特征值为non-missing的样本上对应的特征值进行遍历,通过这个工程技巧来减少了为稀疏离散特征寻找splitpoint的时间开销

    指定缺失值的分隔方向:可以为缺失值或者指定的值指定分支的默认方向,为了保证完备性,会分别处理将missing该特征值的样本分配到左叶子结点和右叶子结点的两种情形,分到那个子节点带来的增益大,默认的方向就是哪个子节点,这能大大提升算法的效率。

    并行化处理:在训练之前,预先对每个特征内部进行了排序找出候选切割点,然后保存为block结构,后面的迭代中重复地使用这个结构,大大减小计算量。在进行节点的分裂时,需要计算每个特征的增益,最终选增益最大的那个特征去做分裂,那么各个特征的增益计算就可以开多线程进行,即在不同的特征属性上采用多线程并行方式寻找最佳分割点。
    `

  5. 科普分享:带你认识集成学习
    https://mp.weixin.qq.com/s/SKWcgJgaDRUOrVDc1Erzuw
    `
    # 为什么集成

    “三个臭皮匠,顶个诸葛亮”、“众人拾柴火焰高”、“兄弟齐心,其利断金”——种种耳熟能详的谚语指向一个古老而深刻的道理:**良好的合作关系总能带来更好的结果**。对于机器学习亦然——如果一种机器学习模型在问题的某一方面展现出良好的性能,另一种机器学习模型在问题的另一方面也展现出良好的性能,**那么用一种良好的方法把这些模型结合起来**,就能够得到在问题所有方面都表现优异的预测模型。

    **集成学习,是一种集成多个机器学习模型的预测结果并给出最终预测的算法。集成学习的根本思想就是集成各基学习器的优势减少预测误差——这里的误差既可以是Bias(即模型预测能力差),也可以是Variance(即模型泛化能力差)。通常来说,选择一种好的集成方法至少可以降低一种误差,如Bagging算法擅长提高模型的泛化能力,而Boosting算法擅长提高模型的预测能力。**当然,作为一名优秀的机器学习(炼丹)工程师,妙手偶得一种既能提高泛化能力,又能提高预测能力的算法也不无可能。

    ## Bagging
    Bagging看上去是一个词,实际上是Bootstrap Aggregating的缩写。Bagging算法的基本思想是对训练数据进行n次抽样,每次抽样得到的数据用来训练一个基模型学习器,最后再将基模型的结果集成得到最终预测结果。

    Bagging算法的设计主要为了提升模型的泛化能力(即降低Variance)。

    Bagging算法采用的基学习器通常来自同一类——如**随机森林算法**实际上就是对决策树算法的Bagging。

    ## Boosting

    Boosting算法的基本思想是不断提高错误预测样本的权重,以收获更加精确的预测效果。因此和Bagging并行式的基模型训练不同,Boosting对于模型的训练是串行的。

    Boosting的提出是为了提高模型的预测能力(即降低Bias)。在训练基学习器时,Boosting首先在一个基学习器上训练一次数据,然后根据弱学习器的预测对数据集进行权重更新,增加错误预测数据的权重同时减小正确预测数据的权重,然后在权重更新后的数据集上训练下一个基学习器。上述过程在Boosting的训练过程中会重复数次,直到得到n个排列好的基学习器。最后,Boosting可以通过加权平均或投票、提升树两种算法中的任意一种将各基学习器的结果组合起来,得到最终的预测结果。

    Boosting和Bagging一样,采用的基学习器通常都来自同一类。常用的Boosting算法包括AdaBoost (Adaptive Boosting)和基于GBDT (Gradient Boosting Decision Tree)的算法如XGBoost, LightGBM, CatBoost等等。

    ## Stacking

    Stacking与Boosting和Bagging相比,恐怕是最简单粗暴的集成算法了。所谓Stacking(堆叠),即将多个机器学习模型堆起来,一层模型的输入是上层所有模型的输出(这种结构与神经网络具有高度的相似性)。每一层模型的训练与Bagging相同,都是并行开展的。只不过对于每一层的各个基学习器来说,其训练数据都是总体数据,没有经过随机抽样。
    `

  6. 3种常见的集成学习决策树算法及原理
    https://mp.weixin.qq.com/s/dvM-W6zxiNXVLF8xE8UqIA
    `
    # 集成学习
    常见的集成学习框架有三种:Bagging,Boosting 和 Stacking。三种集成学习框架在基学习器的产生和综合结果的方式上会有些区别,我们先做些简单的介绍。

    # 偏差与方差
    偏差(Bias)描述的是预测值和真实值之差;方差(Variance)描述的是预测值作为随机变量的离散程度。

    偏差:描述样本拟合出的模型的预测结果的期望与样本真实结果的差距,要想偏差表现的好,就需要复杂化模型,增加模型的参数,但这样容易过拟合,过拟合对应上图的 High Variance,点会很分散。低偏差对应的点都打在靶心附近,所以喵的很准,但不一定很稳;

    方差:描述样本上训练出来的模型在测试集上的表现,要想方差表现的好,需要简化模型,减少模型的复杂度,但这样容易欠拟合,欠拟合对应上图 High Bias,点偏离中心。低方差对应就是点都打的很集中,但不一定是靶心附近,手很稳,但不一定瞄的准。
    `

回复 hi 取消回复

您的电子邮箱地址不会被公开。 必填项已用*标注