机器学习算法中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=

声明: 除非注明,ixyzero.com文章均为原创,转载请以链接形式标明本文地址,谢谢!
https://ixyzero.com/blog/archives/4242.html

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

  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结构,后面的迭代中重复地使用这个结构,大大减小计算量。在进行节点的分裂时,需要计算每个特征的增益,最终选增益最大的那个特征去做分裂,那么各个特征的增益计算就可以开多线程进行,即在不同的特征属性上采用多线程并行方式寻找最佳分割点。

发表评论

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