机器学习算法中GBDT和XGBOOST的区别有哪些? 举报 理由 举报 取消 在昨天阿里的面试中被问到了,我只简单的说了下xgboost能自动利用cpu的多线程,而且适当改进了gradient boosting,加了剪枝,控制了模型的复杂程度 2018年2月5日 10 条回复 1092 次浏览 学习,数据挖掘,机器
回复 ( 10 )
xgboost相比传统gbdt有何不同?xgboost为什么快?xgboost如何支持并行?
看了陈天奇大神的文章和slides,略抒己见,没有面面俱到,不恰当的地方欢迎讨论:
=============
回复 @肖岩在评论里的问题,因为有些公式放正文比较好。评论里讨论的问题的大意是 “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里不具备的特性。
1.引言
最近,因为一些原因,自己需要做一个小范围的XGBoost的实现层面的分享,于是干脆就整理了一下相关的资料,串接出了这份report,也算跟这里的问题相关,算是从一个更偏算法实现的角度,提供一份参考资料吧。
这份report从建模原理、单机实现、分布式实现这几个角度展开。
在切入到细节之前,特别提一下,对于有过GBDT算法实现经验的同学(与我有过直接connection的同学,至少有将四位同学都有过直接实现GBDT算法的经验)来说,这份report可能不会有太多新意,这更多是一个技术细节的梳理,一来用作技术分享的素材,二来也是顺便整理一下自己对这个问题的理解,因为自己实际上并没有亲自动手实现过分布式的GBDT算法,所以希望借这个机会也来梳理一下相关的知识体系。
本文基于XGBoost官网代码[12],commit是b3c9e6a0db0a7eb755949ac6b26e3ef805738350。
2.建模原理
我个人的理解,从算法实现的角度,把握一个机器学习算法的关键点有两个,一个是loss function的理解(包括对特征X/标签Y配对的建模,以及基于X/Y配对建模的loss function的设计,前者应用于inference,后者应用于training,而前者又是后者的组成部分),另一个是对求解过程的把握。这两个点串接在一起构成了算法实现的主框架。具体到XGBoost,也不出其外。
XGBoost的loss function可以拆解为两个部分,第一部分是X/Y配对的建模,第二部分是基于X/Y建模的loss function的设计。
2.1. X/Y建模
作为GBDT算法的具体实现,XGBoost代表了Tree Model的一个特例(boosting tree v.s. bagging tree),基本的思想用下图描述起来会更为直观:
如果从形式化的角度来观察,则可以描述如下:
其中F代表一个泛函,表征决策树的函数空间,K表示构成GBDT模型的Tree的个数,T表示一个决策树的叶子结点的数目, w是一个向量。
看到上面X/Y的建模方式,也许我们会有一个疑问:上面的建模方式输出的会是一个浮点标量,这种建模方式,对于Regression Problem拟合得很自然,但是对于classification问题,怎样将浮点标量与离散分类问题联系起来呢?
理解这个问题,实际上,可以通过Logistic Regression分类模型来获得启发。
我们知道,LR模型的建模形式,输出的也会是一个浮点数,这个浮点数又是怎样跟离散分类问题(分类面)联系起来的呢?实际上,从广义线性模型[13]的角度,待学习的分类面建模的实际上是Logit[3],Logit本身是是由LR预测的浮点数结合建模目标满足Bernoulli分布来表征的,数学形式如下:
对上面这个式子做一下数学变换,能够得出下面的形式:
这样一来,我们实际上将模型的浮点预测值与离散分类问题建立起了联系。
相同的建模技巧套用到GBDT里,也就找到了树模型的浮点预测值与离散分类问题的联系:
考虑到GBDT应用于分类问题的建模更为tricky一些,所以后续关于loss function以及实现的讨论都会基于GBDT在分类问题上的展开,后续不再赘述。
2.2. Loss Function设计
分类问题的典型Loss建模方式是基于极大似然估计,具体到每个样本上,实际上就是典型的二项分布概率建模式[1]:
经典的极大似然估计是基于每个样本的概率连乘,这种形式不利于求解,所以,通常会通过取对数来将连乘变为连加,将指数变为乘法,所以会有下面的形式:
再考虑到loss function的数值含义是最优点对应于最小值点,所以,对似然估计取一下负数,即得到最终的loss形式,这也是经典的logistic loss[2]:
有了每个样本的Loss,样本全集上的Loss形式也就不难构造出来:
2.3. 求解算法
GBDT的求解算法,具体到每颗树来说,其实就是不断地寻找分割点(split point),将样本集进行分割,初始情况下,所有样本都处于一个结点(即根结点),随着树的分裂过程的展开,样本会
分配到分裂开的子结点上。分割点的选择通过枚举训练样本集上的特征值来完成,分割点的选择依据则是减少Loss。
给定一组样本,实际上存在指数规模的分割方式,所以这是一个NP-Hard的问题,实际的求解算法也没有办法在多项式时间内完成求解,而是采用一种基于贪心原则的启发式方法来完成求解。 也就是说,在选取分割点的时候,只考虑当前树结构到下一步树结构的loss变化的最优值,不考虑树分裂的多个步骤之间的最优值,这是典型的greedy的策略。
在XGBoost的实现, 为了便于求解,对loss function基于Taylor Expansion进行了变换:
在变换完之后的形式里,
就是为了优化loss function,待更新优化的变量(这里的变量是一个广义的描述)。
上面的loss function是针对一个样本而言的,所以,对于样本全集来说,loss function的形式是:
对这个loss function进行优化的过程,实际上就是对第k个树结构进行分裂,找到启发式的最优树结构的过程。而每次分裂,对应于将属于一个叶结点(初始情况下只有一个叶结点,即根结点)下的训练样本分配到分裂出的两个新叶结点上,每个叶结点上的训练样本都会对应一个模型学出的概率值,而loss function本身满足样本之间的累加特性,所以,可以通过将分裂前的叶结点上样本的loss function和与分裂之后的两个新叶结点上的样本的loss function之和进行对比,从而找到可用的分裂特征以及特征分裂点。
而每个叶结点上都会附著一个weight,这个weight会用于对落在这个叶结点上的样本打分使用,所以叶结点weight的赋值,也会影响到loss function的变化。基于这种考虑,也许将loss function从样本维度转移到叶结点维度也许更为自然,于是就有了下面的形式:
上面的loss function,本质上是一个包含T(T对应于Tree当前的叶子结点的个数)个自变量的二次函数,这也是一个convex function,所以,可以通过求函数极值点的方式获得最优解析解(偏导数为0的点对应于极值点),其形如下:
现在,我们可以把求解过程串接梳理一下:
I. 对loss function进行二阶Taylor Expansion,展开以后的形式里,当前待学习的Tree是变量,需要进行优化求解。
II. Tree的优化过程,包括两个环节:
I). 枚举每个叶结点上的特征潜在的分裂点
II). 对每个潜在的分裂点,计算如果以这个分裂点对叶结点进行分割以后,分割前和分割后的loss function的变化情况。
因为Loss Function满足累积性(对MLE取log的好处),并且每个叶结点对应的weight的求取是独立于其他叶结点的(只跟落在这个叶结点上的样本有关),所以,不同叶结点上的loss function满足单调累加性,只要保证每个叶结点上的样本累积loss function最小化,整体样本集的loss function也就最小化了。
而给定一个叶结点,可以通过求取解析解计算出这个叶结点上样本集的loss function最小值。
有了上面的两个环节,就可以找出基于当前树结构,最优的分裂点,完成Tree结构的优化。
这就是完整的求解思路。有了这个求解思路的介绍,我们就可以切入到具体实现细节了。
注意,实际的求解过程中,为了避免过拟合,会在Loss Function加入对叶结点weight以及叶结点个数的正则项,所以具体的优化细节会有微调,不过这已经不再影响问题的本质,所以此处不再展开介绍。
3.单机实现
有了2里对XGBoost算法原理的介绍,不难推敲出单机的实现细节。实际上,对XGBoost的源码进行走读分析之后,能够看到下面的主流程:
尝试回答一下
首先xgboost是Gradient Boosting的一种高效系统实现,并不是一种单一算法。xgboost里面的基学习器除了用tree(gbtree),也可用线性分类器(gblinear)。而GBDT则特指梯度提升决策树算法。
xgboost相对于普通gbm的实现,可能具有以下的一些优势:
4.实现了一种分裂节点寻找的近似算法,用于加速和减小内存消耗。
5.节点分裂算法能自动利用特征的稀疏性。
6.data事先排好序并以block的形式存储,利于并行计算
7.cache-aware, out-of-core computation,这个我不太懂。。
8.支持分布式计算可以运行在MPI,YARN上,得益于底层支持容错的分布式通信框架rabit。
参考资料:
chentq的slides
chentq的paper
chentq在52cs上的中文博文
微博上分享的xgboost导读和实战.pdf
P.S. GBM还有好多名字,AnyBoost,MART,TreeNet,GBRT等等。。
xgboost号称scalable tree boosting system,其中非常重要的scalability有下面几个层面的含义,也算是与gbdt的核心差异所在:
(按李航的机器学习=模型+策略+算法的思路,不一定完全对应~)
1、模型的scalability,弱分类器除cart外也支持lr和linear
2、策略的scalability,可以支持不同的loss functions,来优化效果,只要一、二阶可导即可
3、算法的scalability,做了很多细节工作,来优化参数学习和迭代速度,特征压缩技术,bagging学习中的特征抽样,特征选择与阈值分裂的分位方法和并行方法等
4、数据的scalability,因为3中的优化,支持B级别的快速训练和建模;同时也因为加上了正则项和随机特征抽样,减少了过拟合问题
工作中用得比较多,区别在于:
1. 在Loss function中做approximate,把泰勒展开限制为1阶和2阶偏导,gbdt是1阶;
2. penalty function Omega主要是对树的叶子数和叶子分数做惩罚,这点确保了树的简单性;
3. 快,非常快,最新版本支持spark,4000多万样本,70个dimension,200棵树的训练也就1小时不到;
没有答到关键点啊,xgboost建树的时候和一般的gbdt不一样,正则的加法也比较独特。可以看这个:
几个回答都写的很好,xgboost和大部分gbdt的实现的主要区别是在于loss function是1阶还是2阶近似。
不过速度上仍有提升空间。有幸见过某大神的单机gbdt速度比xgboost快一倍。效果略优或至少持平。
1. xgboost在目标函数中加入了正则化项,当正则化项为0时与传统的GDBT的目标函数相同
2. xgboost在迭代优化的时候使用了目标函数的泰勒展开的二阶近似,paper中说能加快优化的过程!!xgboost可自定义目标函数,但是目标函数必须二阶可导也是因为这个。GDBT中只用了一阶导数。
3. xgboost寻找最佳分割点时,考虑到传统贪心法效率比较低,实现了一种近似贪心法,除此之外还考虑了稀疏数据集、缺失值的处理,这能大大提升算法的效率。paper中提到在一个稀疏数据集中测试,发现速度提升了50倍。
4. xgboost在算法实现时做了很多优化,大大提升了算法的效率,感叹陈天奇大牛深厚计算机基础!
XGBoost除去正则和并行的优化,我觉得和传统GBDT最核心的区别是:
1. 传统GBDT的每颗树学习的是梯度,是损失函数在上一轮预测值的梯度,所以喂给下一轮决策树的样本是,g_i 是损失函数L对上一轮预测值y_{i,t-1}处的梯度,然后y_{i,t} = y_{i,t-1} – lambda * g_i;
2. 而XGBoost是直接学习的残差,看论文里的分裂方法,就是在找每个叶子节点上最优的权重w_j,而这个值对应的是y – y_t;
想过好自己的人生,就应该像XGBoost学习
1. 目标明确
XGBoost的代价函数就是人生的奋斗目标,所有努力都是为了降低XGBoost。有时候我们的目的不一样,所以我们需要自己定义自己的目标函数。有时候为了查全率,有时候是为了查准率,有时候为了F1,F0.5或者F2值。
2. 高瞻远瞩
有时候我们不仅仅看到,下一步怎么走,还有看到下一步的下一步。
3. 学会多任务能力
同一时间,要学会处理多件事情。
4. 学会快人一步,积累经验
需要预学习,利用既往的经验,达到快速处理任务的能力。
有人赞,我再虾扯蛋。