XGBoost学习总结

  极端梯度提升算法XGBoost是2014年提出的基于CART回归树的一种boosting集成算法,是对梯度提升决策树(GBDT)算法的一种改进.它的目标是建立t棵回归树使得树群对样本的预测值尽可能接近样本的真实值,并且具有一定的泛化能力.本文是对XGBoost学习的总结与思考,通过总结CART回归树构建与剪枝的思想方法与工作原理,并讨论了集成学习中主要的两种集成方法,即bagging和boosting.然后再分析GBDT的算法工作流程,在此基础上详细的推导了XGBoost算法目标函数的构建与优化过程.最后对比GBDT与XGBoost的区别与联系,加深对XGBoost的理解与掌握.

概述

  Extreme Gradient Boosting (XGBoost)是在梯度提升决策树(GBDT)基础上的改进,GBDT全称为Gradient Boosting Decision Tree.顾名思义,它是一种基于决策树(decision tree)实现的分类回归算法,即GBDT由两部分组成:梯度提升和决策树.Boosting作为一种模型组合方式,与梯度提升有很深的渊源,所以理解集成学习方法对掌握XGBoost是有必要的.分类回归树(CART) 是一棵二叉决策树,构成了XGBoost的基础弱学习器.所以在学习XGBoost算法前,需要了解CART的基本工作原理.

1 分类与回归树(CART)

  分类与回归树(Classification And Regression Tree, CART)模型是在给定输入随机变量X条件下输出随机变量Y的条件概率分布的学习方法.CART是典型的二叉决策树,根据其内部节点特征的取值将样本递归的分为两部分,将判断为“是”的样本点划分到左边,右边则是判断为“否”的样本点.这样便将特征空间划分成了有限的单元,并在这些单元上确定预测的概率分布.CART可以用于分类也可用于回归.若样本输出结果是离散值,比如晴天/阴天/雾/雨、用户性别、网页是否是垃圾页面,此时CART用于分类;若样本输出结果是连续型数据,比如明天的温度、用户的年龄、网页的相关程度,此时CART则用于回归预测.CART的生成就是递归地构造二叉决策树的过程,对回归树用平方误差最小化准则,对分类树使用基尼指数最小化准则,进行特征的选择来生成二叉树.

1.1 CART回归树生成算法

  在XGBoost模型中,所使用的基学习器即为CART回归树,故此小节详细阐述一下回归树的生成算法.假设有样本集$S=(x_1,y_1),(x_2,y_2),\dots ,(x_N,y_N)$,一共有N个样本,X为输入变量,Y为取值连续的输出变量.特征集$F=f_1,f_2,\dots ,f_M$,每一个样本都对应一组特征,现在考虑生成一颗回归树.   (1) 现在有原始数据集S,树的深度depth=0.   (2) 特征选择,针对集合S,遍历每一个特征feature,逐个取出其对应的所有的value,每个value都可看作一个切分点.选择第f个特征和它的取值v,小于该值v的样本点划分到左边集合$R_1(f,v)=${ x| x^$(f)$≤v},将大于该值v的样本点划分到右边集合$R_2(f,v)=${x| x^$(f)$>v}.不同特征feature及其对应的不同取值value,就构成了许多切分方式.接着就需要知道该如何来选择最优的特征f以及对应的切分点v.最小化均方误差即可对固定的特征变量f找到最优切分点v.具体公式如下:   (3) 找到最佳分割feature以及最佳分割value之后,用该value将集合S分裂成2个集合:左集合$R_1$、右集合$R_2$,每一个集合也叫做一个节点.此时树的深度$depth+=1$.   (4) 针对集合$R_1$、$R_2$分别重复步骤2、3,直到达到终止条件. 终止条件:   a. 节点中的样本个数小于预定阈值;   b. 节点中的样本基本属于同一类.此时,样本已经被全部划分出来,节点停止分裂;   c. 节点中已经不存在样本了.   (5) 最后生成的、不再进行分裂的集合就叫做叶子节点.落在该叶子节点内的样本的预测值,就是该叶子节点的值.同一个叶子节点中的样本具有同一个预测值.

1.2 CART剪枝算法

CART剪枝算法由两步组成:   (1) 由生成算法产生的决策树T_0底端开始不断剪枝,直到T_0的根节点,形成一个子树序列$T_0,T_1,\cdots ,T_n$;   (2) 通过交叉验证法在独立的验证数据集上对子树序列进行测试,从中选择最优子树.   那么对于第一步,这个子树序列是怎么剪出来的?已经存在的决策树$T_0$开始剪枝,对$T_0$的任意内部节点t,存在以t为根节点的子树Tt.因为建模的时候,目标就是让损失函数达到最优,那剪枝的时候也用损失函数来评判.我们希望减少树的大小来防止过拟化,但又担心去掉一些节点后预测的误差会增大,那么如何达到这两个变量之间的平衡则是问题的关键,因此我们用一个变量α来平衡,因此损失函数定义为如下:                 $C_{\alpha }(T)=C(T)+\alpha (T)$   T为任意子树,$C(T)$为预测误差,可以是平方误差也可以是基尼指数,$|T|$为子树T的叶子节点个数,注意是叶子节点, $\alpha$是参数,$C(T)$衡量训练数据的拟合程度,$|T|$衡量树的复杂度(即大小), $\alpha$权衡拟合程度与树的复杂度.   那么我们如何找到这个合适的$\alpha$来使拟合程度与复杂度之间达到最好的平衡呢,最好的办法就是,我们将$\alpha$从0取到正无穷,对于每一个固定的α,我们都可以找到使得$C_{\alpha }(T)$最小的最优子树$T(\alpha )$ .当$\alpha$ 很小的时候, $T_0$是这样的最优子树,当$\alpha$很大的时候,单独一个根节点是这样的最优的子树.   尽管$\alpha$取值无限多,但是$T_0$ 的子树是有限个,因此我们可以生成这样一个子树序列 :           $T_0>T_1>\cdots >T_n$ $Tn$是最后剩下的那个根节点.(这里的子树生成是根据前一个子树$T_i$,剪掉某一个内部节点,生成$T_{i+1}$ ),然后对这样的子树序列分别用测试集进行交叉验证,找到最优的那个子树作为我们的决策树.   我们每次剪枝剪的都是某个内部节点的子节点,也就是将某个内部节点的所有子节点回退到这个内部节点里,并将这个内部节点作为叶子节点.因此在计算整体的损失函数时,这个内部节点以外的值都没变,只有这个内部节点的局部损失函数改变了,因此我们本需要计算全局的损失函数,但现在只需要计算内部节点剪枝前和剪枝后的损失函数.对任意内部节点t,   剪枝前的状态:有$|T_t|$个叶子节点,预测误差是$C(T_t)$;   剪枝后的状态:只有本身一个叶子节点,预测误差是$C(t)$.因此剪枝前的以t节点为根节点的子树的损失函数是:       $C_{\alpha }(T_t)=C(T_t)+\alpha |T_t|$ 剪枝后的损失函数是:         $C_{\alpha }(t)=C(t)+\alpha$   已知剪枝后的损失函数≤剪枝前的损失函数,则有:C_α $(T_t)\le C_{\alpha }(t)$,这个值为:           $\alpha \ge (C(t)-C(T_t))/(|T_t|-1)$ 即当$\alpha \in [0,(C(t)-C(T_t))/(|T_t|-1))$时,不满足剪枝后的损失函数小于剪枝前的损失函数,不能进行剪枝;因此对于T_0,能够在t处剪枝的最小的α为：${\alpha }_{min}=(C(t)-C(T_t))/(|T_t|-1)$ .   自下而上地对内部每个内部节点t计算可以剪枝的最小α_min,取其中最小的${\alpha }_{min}$作为${\alpha }_1$($\alpha$序列逐渐增大,树序列T逐渐简单,最小的${\alpha }_{min}$保证没有遗漏可以剪枝的子树),对应的子树为$T_1$,剪切点为$t_1$;这样我们便得到了$\alpha$序列中的${\alpha }_1$以及对应的子树$T_1$.接着对子树$T_1$执行以上过程便可以得到${\alpha }_2$和$T_2$,不停地重复以上过程便可以得到最优子树序列$T_0,T_1,\cdots ,T_n$,且每一颗树都是上一颗树的子集(在上一颗的基础上进行剪枝).获得了可以剪枝的最优子树序列$T_0,T_1,\cdots ,T_n$之后,再将每棵树进行交叉验证,交叉验证结果最好的那颗子树便是最终的剪枝结果.

2 基于残差的训练方式

  已经知道Boosting是通过迭代多棵树来共同决策.这怎么实现呢?难道是每棵树独立训练一遍,当然不是。而是基于残差的训练方式.比如下图3所示6个样本,每个样本代表一个人,具有年龄、工作年限等特征,现在需要构造一个模型来预测每个样本的收入值.比如,对于第一个样本,使用已经训练好的学习器1,即一颗决策树.现在假如第一棵树对第一个样本的预测收入是9K,第二棵树预收入是0K,第三棵树预测收入是18K,我们就取平均值9K做最终结论?当然不是.且不说这是投票方法并不是GBDT,只要训练集不变,独立训练三次的三棵树必定完全相同,这样做完全没有意义.之前说过,GBDT是把所有树的结论累加起来做最终结论的,所以可以想到每棵树的结论并不是收入本身,而是收入的一个累加量.GBDT的核心就在于,每一棵树学的是之前所有树预测结果和的残差,这个残差就是一个加预测值后能得真实值的累加量.比如第一个样本的真实收入是10K,但第一棵树的预测收入是8K,差了2K,即残差为2K.那么在第二棵树里我们把第一个样本的收入设为2K去学习.如果第二棵树真的能把第一个样本分到2K的叶子节点,那累加两棵树的结论就是第一个样本的真实收入值;如果第二棵树的结论是1K,则第一个样本仍然存在1K的残差,第三棵树里的收入就变成1K,因此需要继续学习下去.

3 Extreme Gradient Boosting (XGBoost)

  XGBoost全名叫(Extreme Gradient Boosting)极端梯度提升,经常被用在一些比赛中,其效果显著. XGBoost 所应用的算法就是GBDT(gradient boosting decision tree)的改进,既可以用于分类也可以用于回归问题中.XGBoost是一种加法模型,将模型上次预测(由t-1棵树组合而成的模型)值与真实值的残差作为参考进行下一棵树(第t棵树)的建立.以此,每加入一棵树,将其损失函数不断降低.下面将XGBoost算法的目标函数构建过程与优化方法分为四步,第一步为目标函数的构建,后面三步为目标函数的具体优化方法.

3.1 目标函数构建

  假设给定数据集$D=${($x_i$,$y_i$)},XGBoost进行加法训练,学习t棵树,采用以下函数对样本进行预测:   这里F表示所有可能的CART树,𝑓(𝑥)是一棵回归树(CART),表示对样本进行的一次预测, $y$ ̂${}_i$则表示将1到t棵树预测值进行求和.这里运用了加法策略,即将上一棵回归树预测的结果与真实值的残差作为下一棵决策树的模型输入值,那么下一棵树的训练结果与上一棵树的结果累加,使得预测值更加接近真实值. 对于加法策略具体描述如下:   初始化(模型中没有树)时，其预测结果为0:   往模型中加入第一棵树:   往模型中加入第二棵树:   …   往模型中加入第t棵树:   加法策略经过t次迭代后,模型的预测等于前t-1次的模型预测加上第t棵树的预测,具体预测函数表达式如下:   那么，此时目标函数则可写作:   公式中都已知,即$y_i$为样本真实值,为前面t-1棵树预测得到的值,l则表示误差函数,误差函数可以是square loss,log loss等.$\Omega (f_t)$则表示正则项,用来缓解模型过拟合的风险,正则项可以使用L1正则或L2正则等.根据公式可知,模型当前的任务就是学习第t棵树$f_t(x)$来使得目标函数$L^{(t)}$的值最小.

3.2 目标函数近似化处理

  XGBoost目标函数的优化使用了一阶和二阶偏导数,二阶导数有利于梯度下降的更快更准.使用泰勒展开取得函数做自变量的二阶导数形式,可以在没有选定损失函数具体形式的情况下,仅仅依靠输入数据的值就可以进行叶子节点分裂优化计算,本质上也就把损失函数的选取和模型算法优化/参数选择分开了.这种去耦合增加了XGBoost的适用性,使得它按需选取损失函数.   二阶偏导信息本身就能让梯度收敛更快更准确.这一点在优化算法里的牛顿法里已经证实.可以简单认为一阶导指引梯度方向,二阶导指引梯度方向如何变化.这是从二阶导本身的性质,也就是为什么要用泰勒二阶展开的角度来说的.   下面引入泰勒级数的具体展开公式:   根据泰勒公式展开式,可以将目标函数中看作 𝑓(𝑥),那么则可看作𝑓(𝑥+Δ𝑥),即那么目标函数即可用泰勒级数进行近似化处理.将目标函数在处进行二阶泰勒展开得到如下式子: 公式中,我们使用$g_i$来表示误差函数在处的一阶导数,$h_i$来表示误差函数在处的二阶导数,即 由于公式表示的是前t-1棵树的预测值与真实值的残差,具体残差函数也已经明确,那么这一项即可看作常数项,因为参数项对具体目标函数的优化不起作用,故将公式中的常数项去掉,得到:

3.3 目标函数引入树的结构

目标函数经过近似化处理后,得到从式中可以把看作一个一元二次方程,对其求偏导就可以很容易的取到最值,但是一个函数,而我们的目标是寻找一个参数来最小化目标函数.目标函数在函数空间中的表示方法: 参数空间中的目标函数表示如下: 故需要将目标函数从函数空间转到参数空间,因此引入了函数$q(x)$,把写成树结构的形式,即把树的结构引入到目标函数中: 上式中$q(x)$是一个映射,用来将样本映射成1到T的某个值,也就是把它分到某个叶子节点,$q(x)$其实就代表了CART树的结构,w是叶子节点的分数(leaf score),所以$w_q(x)$表示回归树对样本的预测值.   对于正则项$\Omega (f_k)$,同样需要引入树的结构,对每棵回归树的复杂度进行惩罚,那么有哪些指标可以衡量树的复杂度?包括树的深度,内部节点个数,叶子节点个数(T),叶节点分数(w)等等.在XGBoost算法中采用的是叶子节点分数和叶节点个数,分别表示为w和T,正则项的具体表示如下:   拥有了$f_t$, $\Omega (f_t)$的树结构的表示形式,将其代入目标函数中得到:   但是又出现了一个问题,现在的表示形式前半部分是对样本个数进行累加,而后半部分是对叶子节点数进行累加,怎样对后续的优化造成了阻碍,那么需要将其统一起来.   这里定义每个叶节点j上的样本集合为,集合中每个值代表一个训练样本的序号,整个集合就是被第t棵CART树分到了第j个叶子节点上的所有样本.   如果确定了树的结构(即$q(x)$确定),为了使目标函数最小,可以令其导数为0,解得每个叶节点的最优预测分数为:   代入目标函数,得到最小损失为:

3.4 贪心算法构建回归树

  当回归树的结构确定时,我们前面已经推导出其最优的叶节点分数以及对应的最小损失值,问题是怎么确定树的结构?贪心法,每次尝试分裂一个叶节点,计算分裂前后的增益,选择增益最大的.   一个回归树形成的关键点:分裂点怎么选,分裂后的节点预测值是多少,分裂何时停止以及分裂前后的增益怎么计算. 式中的衡量了每个叶子节点对总体损失的贡献,我们希望损失越小越好,则该部分的值越大越好.因此,对一个叶子节点进行分裂,分裂前后的增益定义为:   此处引入了γ,表示加入新叶子节点时增加的复杂度. Gain的值越大,分裂后 L 减小越多.所以当对一个叶节点分割时,计算所有候选(feature, value)对应的Gain,选取gain最大的(feature, value)进行分裂.

本文参考了许多博客，如有引用漏缺，请联系我！！！

参考文献

https://www.bilibili.com/video/BV1mZ4y1j7UJ?from=search&seid=14951923256840818281

https://www.cnblogs.com/zongfa/p/9324684.html

https://blog.csdn.net/huibeng7187/article/details/77588001

https://www.cnblogs.com/bnuvincent/p/9693190.html

https://www.cnblogs.com/ModifyRong/p/7744987.html

https://blog.csdn.net/lanyuelvyun/article/details/88697386

cart树怎么进行剪枝？ - 椒盐砒霜叶小沐的回答 - 知乎 https://www.zhihu.com/question/22697086/answer/821565832