当前位置:   article > 正文

xgboost多分类原理_xgboost从入门到放弃

多分类 xgboost
8f0fdf6a6208176b1b6e3ab825bcf568.gif

继曾经写过的关于树的通俗系列算法,从决策树,到分类树,随机森林,GBDT等,今天完善一些树系列中算是比较顶级的算法介绍:xgboost。看本篇之前对决策树分类树随机森林GBDT不熟悉的同学按不同程度建议先去看一看这几篇:

决策树:从特征的重要程度说起

决策树:属性的选择(续)

决策树与随机森林与GBDT

分类树与回归树的区别到底在哪

GBDT也就这些东西了

也许很多人已经或多或少学过xgboost的原理,能明显感受到xgboost的复杂程度是要高于随机森林与GBDT,xgboost的数学模型确实复杂,一大堆公式,对xgboost的学习只能慢慢啃,细节尽可能再去看看原始论文:XGBoost: A Scalable Tree Boosting System[1],本篇主要以作者Tianqi Chen的PPT为思路来进行介绍,看懂了他的PPT也就自然明白其原理了,ppt的下载链接[2]

监督学习模型

4c88e865b7ec1953c51d69c00b579ba7.png

做个简单回顾,通常来说机器学习模型分为两类,有监督的模型和无监督的模型,有监督模型的训练样本为(特征,标签),有特征也有真实标签;无监督的模型只有特征,没有样本的标签,这两类方法的训练过程是完全不一样的。

对于监督学习模型,我们需要定义一个模型,线性或者非线性的,logistic模型或者贝叶斯模型等,但是这些模型都有一个共性,就是有对应的参数需要学习,监督学习模型需要学习这样的模型参数w,有了模型参数就可以在给定一个新样本xi的情况下预测其结果了。

目标函数

aba5492c4d4fc838d43cfebe89919ccc.png

模型参数是需要学习的,如何学习?需要一个定量的学习指标吧,这就是目标函数。机器学习的目标函数通常由两个部分组成:

•训练样本的loss:也就是样本的预测值与真实标签之间的误差,本质上为了使得模型输出尽可能拟合真实标签;•正则化项loss:一般来说有了上面这个训练样本的loss就够了,但是通常会发现,如果这个训练样本的loss足够小,这样的模型就比较复杂,也就是通常所说的过拟合了,模型完全拟合了训练样本。这个时候就有了正则化项loss,这个loss主要从模型的学习参数上着手,和预测样本与真实样本没有关系,比如L1与L2范数,只与参数w有关,至于为什么只控制参数就能达到控制模型复杂度的问题,感兴趣可以查查,本文就不介绍了。

这样一切的一切都可以归结到这两类loss的设计上了,这两类loss根据问题不同也是可以千差万别。

回归树

0ffdd952db60abe8f0c5f9a2ab313dd8.png

基于此基础,再来看看树结构的分类器。

首先树包含两种:分类树与回归树。分类树自然是做分类任务的,输出值只能是某个label,而回归树既可以做分类也可以做回归,其输出值是连续的值,这两者虽然都是树结构,但是构造过程与输出的含义是不一样的,详细的区别可以参考前面给的链接。

xgboost模型底层是有回归树组成的,更准确的是CART树(分类回归树),就是回归树了。

单颗分类树的形成过程一定要清楚,主要包括:

•每个分裂的叶节点是如何选择出来的,以及分裂的阈值时如何确定的;•明白回归树的每个节点的输出是一个score值,而不是一个label;

集成回归树

7b1d58f916d7982183bbdfcd7cb7a219.png

一颗树结构的分类或者回归树一般很难达到较好的效果,这就出现了好多树组合起来当成一个模型的集成树模型。

一大堆分类树组合起来就形成了随机森林,详细见开始的参考;

一大堆回归树组合起来就形成了集成回归树,这里面最基础的模型就是GBDT了,同样前文也详细介绍了;

但是这两者的形成组合方式是完全不一样的,我们知道随机森林的一大堆树之间是相互独立的,而GBDT的树构造是有先后顺序的,一定要先理解这两者的不同以及GBDT的原理才能进一步研究xgboost。

其实xgboost属于集成回归树,其原理构造上可以说一大半都和GBDT完全一样,不同点在于xgboost针对GBDT存在的不足进行了改进,最核心的就是在速度与性能上进行了优化,这在后面再详细介绍。

集成树模型都有哪些参数

76ae3a338f07474441a9005ca9914166.png

前面说一个模型主要是由它的参数决定的,那么对于集成树模型什么才是它的参数呢?无外乎两点:

•树的结构(也就是每一层树节点选择哪个特征作为分裂属性)•叶节点的值(这个值就是每颗树输出,也是一个需要学习的参数)

想一想由这两点是不是可以确定一棵树的结构了,每一颗树都有一组参数包含这两部分,这样集成树模型结构也就知道了。

如何优化

现在的问题是如何进行公式化表示上面的这两类参数。也就是我们需要定义目标函数,然后进行优化。

前面我们说了,通用的监督学习目标函数一般都有两个部分组成:训练误差+正则化项;对应到集成树模型就是:训练误差+树的模型复杂度。

有人说为什么还要控制树的复杂度呢?看看下面这个图

e37843b925a02bbb6612bc2a9c20f4af.png

左下角的模型显示的就是训练误差的loss太高;

右上角的模型则是树的复杂度太高,本来一层分裂节点就可以解决的树模型,可以看到,该模型分裂了5次,相当于树的深度为5了,这样的树虽然训练误差的loss够低,但是模型太复杂,最好的模型就是平衡这两者的误差,使得训练误差的loss不高的同时树的复杂度也不高。

所以树模型的复杂度在哪?为什么要控制?其实主要就是在于树的分裂次数,或者说就是树的深度,或者节点的个数,也有权重的连续性。

a53af208a15dd28ee92ab8423c5c76bc.png

回归树是如何集成训练的

我们说xgboost属于集成回归树,和GBDT一样,那么GBDT的不同的树怎么构造的xgboost就是如何构造的,专业术语叫做加法训练

e13caf275e149d4dabe04694a25489f7.png

什么意思呢?这在GBDT那一节也有详细的介绍,简单来说,就是第n颗树的构造方式是由前面n-1颗树的结果来决定的。第n颗树构造的目的就是为了减少前n-1颗树预测完以后还可能存在的误差。基于这个加法训练的逻辑,在第t颗树构造的时候,其目标函数就如ppt中的Obj(t)所示:

cc0116eb0fefd48f79297dda8c6a1e85.png

仔细看一下ppt中的constant,constant代表的是前t-1颗树的复杂度。其实我们可以知道,在构造优化第t颗树的时候,其实前t-1颗树已经优化出来了,也就是前t-1颗树的复杂度不管是多少,都是一个定植了,所以用一个常数表示。

训练误差我们用l表示,可以看到截止到第t颗树,整个模型的输出就是前t-1颗树的输出加上第t颗树的输出,如果训练误差是均方误差,那么公式就可以进一步化简,也就是ppt中看到的那样。此时我们一定要明白一个东西,那就是对第t颗树的优化时,前t-1颗树结构是已经优化出来了的,凡是涉及到前t-1颗树的东西,都是一个常数。

90d9c371305c867ba462934d255d0fb2.png

在重新来看一下目标函数,根据泰勒展开,我们可以将原始的目标函数进行变换。泰勒展开很熟悉了,我想大家不明白的更多的是为什么可以这么展开。

其实泰勒公式里的f(x)在这里就是l(y_i,y*_i^(t-1)),而里面的△x在这里就是f_t(x_i)。所以才可以这么展开。为什么要约等于呢?因为一个函数泰勒展开可以有无穷项,这里取了前两项,所以近似约等于。至于为什么不取第三项第四项,因为后面方便计算。

再去看当误差函数为MSE均方误差的时候,我们可以看到,这个约等于其实就是等于了。为什么?因为均方误差只有二阶导,三阶导为0,所以就是等于。

而泰勒近似版的误差函数是适用于所有可以进行二阶导的误差函数的,不光是MSE均方误差。

重新定义目标函数

上面化简了半天,其实都是在着眼于训练误差这块的近似计算,我们知道还有一块的误差计算,这就是模型的复杂度。那么xgboost里面,模型的复杂度怎么表示的呢?两个部分:

•叶子结点的个数•叶子结点输出值(可以认为是w)的L2范数。

仔细去想一想,其实这么做也是合理的,这样可以控制树模型的复杂度,要不然还有什么可以控制模型复杂度呢。

f6c95c9d50c72118d297b27ec8dd6d3b.png

举个例子,看看上面这个ppt,可以看到,此时最末端的叶子结点个数为3,w1-w3分别是(2,0.1,-0.1),所以平方和就是图中的样本。

目标函数再变换

好了,睁大眼睛,目标函数到这里要进一步进行变换了:

7f3da8d16ff374fbd424a88d1f019404.png

注意Ij代表的范围什么?它代表一个集合,集合中每个值代表一个训练样本的序号,整个集合就是被第t棵CART树分到了第j个叶子节点上的训练样本。

再进行变换:

78c6fb1a634bebbf5bc569c83553e9cf.png

当第t棵CART树的结构是确定的时候(可用q(x)表示),所有的Gj和Hj都是确定的。为什么?因为Gj是由一系列gi组成的,而gi是由当前前t-1颗树的输出与真实yi的输出决定的,所以当求第t颗树的结构时,Gj和Hj是确定的。

这样最优的w其实就在这个二次函数的极点取得,也是我们中学背的公式x=-b/2a,这就是w*。最优的obj也知道了。

那么obj代表了什么呢?它表示了这第t棵树的结构有多好,值越小,代表这样结构越好!也就是说,它是衡量第t棵CART树的结构好坏的标准。

看一个实例图:

80dc9f8aa41005dca9fd9fb5ad489d53.png

如何找到分裂属性与阈值

我们知道,xgboost的树训练都是由前面的t-1颗树的结果来训练第t颗树,这是一种贪婪算法,贪婪的起点就是第一颗树。

现在还有两个问题:

•如何找到最佳的分裂属性•如何找到这个最佳分裂属性对应的左右两边这个阈值

我们回想一下再GBDT哪里,这个过程是怎么做的,是不是有两层循环,外层循环是所有属性遍历,内存循环是把对应属性的范围进行分段遍历。当然遍历的方式是非常慢的。

那么xgboost里面对这一部分进行了优化,优化的公式如下:

438439723084fea25adc14829e306c6a.png

首先我们假设找到了一个分裂属性,这样我们就可以算出当按照这个属性进行分裂时的左右子树的obj,那么如果不按照这个属性分裂,也会有一个不分裂的obj,这样我们就可以算出这个属性的增量obj了。

以age分裂为例:

05f37e4373020ec3ead4b5225474784e.png

按照这个图从左至右扫描,我们就可以找出所有的切分点。对每一个确定的切分点,我们用增量的obj作为衡量切分好坏的标准。

这个Gain实际上就是单节点的obj减去切分后的两个节点的树obj,Gain如果是正的,并且值越大,表示切分后obj越小于单节点的obj,就越值得切分。同时,我们还可以观察到,Gain的左半部分如果小于右侧的γ,则Gain就是负的,表明切分后obj反而变大了。γ在这里实际上是一个临界值,它的值越大,表示我们对切分后obj下降幅度要求越严。这个值也是可以在xgboost中设定的。

扫描结束后,我们就可以确定是否切分,如果切分,对切分出来的两个节点,递归地调用这个切分过程,我们就能获得一个相对较好的树结构。

注意的是,xgboost的切分操作和普通的决策树切分过程是不一样的。普通的决策树在切分的时候并不考虑树的复杂度,而依赖后续的剪枝操作来控制。xgboost在切分的时候就已经考虑了树的复杂度,就是那个γ参数。所以,它不需要进行单独的剪枝操作。

至此,可以说xgboost的基本训练算是完成了,因为在找到了分裂节点以后,树结构也就确定了,那么最后一层的叶结点也是可以确定的。

总结

简单来总结一下xgboost相对与GBDT的区别,首先xgboost综合考虑了训练误差与模型复杂度统一到一个优化函数当中当成参数去优化了,其次结点的选择是自动优化选择的,还有一点,我们说xgboost再训练速度上是提升了的,看了这个过程可以发现,裂变结点的选择是通过一系列的G与H算出来的,而G和H主要由g和h组成的,对于第T颗树,单独的小g与h已经早早被算出来了,那么就可以将它们存在内存里面,而这,也是xgboost一定程度上能够实现分布式训练的核心所在,虽然不是完全式的分布式。

更多细节,可以再多读读原始论文[1], 另外附录两个学习参考:xgboost官方大全参考[3] ;xgboost的原理没你想像的那么难[4]

xgboost从入门到放弃就到这吧,你放弃了吗!_!

References

[1] 原始论文:XGBoost: A Scalable Tree Boosting System: https://arxiv.org/abs/1603.02754[2] ppt的下载链接: https://download.csdn.net/download/sinat_35512245/10133360

[3] xgboost官方大全参考https://xgboost.readthedocs.io/en/latest/tutorials/model.html[4] xgboost的原理没你想像的那么难: https://www.jianshu.com/p/7467e616f227

2d54f8ecd8b87fd0aa9aced03ad92c64.gif

更多阅读:

决策树:从特征的重要程度说起

决策树:属性的选择(续)

决策树与随机森林与GBDT

分类树与回归树的区别到底在哪

GBDT也就这些东西了

关注置顶,更多精彩

0b46f14fedc707f03b103ea3a7241ac7.png

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/Gausst松鼠会/article/detail/97475
推荐阅读
相关标签
  

闽ICP备14008679号