GBDT与XGBOOST串讲

最近,一直被GBDT和XGBOOST烦恼,产生了如下的问题,由此产生了这篇文章。

  • XGBOOST怎么生成一棵树?
  • GBDT算法是什么?
  • GBDT与BT(提升树)是一回事吗?

本篇文章结构:

Boosting Tree(提升树)

提升树是采用加法模型与前向分布算法进行提升的,是基于残差进行训练的。提升树分为回归树和二叉分类树,对于分类问题就是分类树(可以参考AdaBoost算法),对于回归问题就是回归树。至于为什么叫“提升”树?我的理解是因为是加法模型,相加进而为提升。

具体算法如下:

其中2.a步是计算残差,2.b步通过把2.a的残差当作标签,可以使用线性回归的方法进行拟合残差。通过M次循环一共得到M+1颗树,每个输入数据X的结果,是M+1棵树预测的结果之和。

GB算法

当提升树的损失函数是平方损失和指数损失时,每一步优化很简单;但是对于一般函数,优化不是非常简单,因此采用梯度下降法进行优化。至于为什么是“梯度提升”,我的理解是首先基于当前模型损失函数的负梯度信息进行拟合形成新的弱分类器,然后根据残差进行寻找该新分类器的权重!由此,即为梯度提升!

具体算法如下:

第4步,使用梯度作为标签进行拟合新的一棵树;第5步是基于残差进行得到新的一颗树的权重,其中残差来自于第i个数据的标签y与前m-1棵树的差得到的。其中F(x)表示前几棵树的总的函数。

GBDT算法

有了上面的GB算法介绍,那么使用决策树作为弱分类器的GB算法被称为GBDT(Gradient Boosting Decision Tree)。一般采用CART得到决策树,CART是采用基尼指数作为决策树的损失增益函数。基尼指数反应了数据集D中任意两个样本不一致的概率。其基尼指数越高则数据集D的纯度越高;纯度越高正是决策树每个叶子节点的类别越一致。信息熵和基尼指数都是《信息论》中的内容。

XGBOOST

XGBOOST是GBDT算法的工程实现,XGBOOST的公式推导采用二阶泰勒公式的展开形式进行推导,使得每棵树之间得变化更小,而且还使用了正则化项,控制了每棵树的复杂度,进而防止过拟合。

公式推导也可以参见论文XGBoost: A Scalable Tree Boosting System

XGBOOST在生成一颗树的时候,使用如下公式进行左右分支。

训练得到第M棵树的损失函数:

其实XGBOOST每一次分支采用的是贪心算法,对于决策说来说每次分支也是采用贪心算法,只不过每次进行分支使用的损失函数不一样。对于决策树有基尼指数、信息熵等loss函数。

参考文献:

[1]. 《统计学习方法》(提升树)

[2].《百面机器学习》(集成学习)

[3].XGBoost: A Scalable Tree Boosting System

[4].《机器学习》.西瓜书.周志华

本文分享自微信公众号 - 机器学习与推荐算法(ML_RSer),作者:Evan

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-09-14

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 美团机器学习算法岗实习四面面经(推荐系统方向)

    “ 本篇内容为师妹在美团面试时的相关记录,希望对目前学习推荐系统方向的朋友们一些方向指引,同时也希望对寻找推荐系统相关工作的朋友们一些借鉴意义。如有相关问题,请...

    张小磊
  • 知乎推荐算法工程师面经

    曾三次迈进知乎的大门,面试算法工程师岗位。特整理了一些相关问题供大家研究,并附上了一些大佬的建议供大家参考。更多关于算法工程师职位介绍以及面试准备等问题...

    张小磊
  • RecSys2020推荐系统论文集锦

    第14届推荐人自己的年会RecSys已在9月22日到26日在线上举行。大会围绕着推荐系统相关问题进行了3场KeyNotes,5场Tutorials,接收了41篇...

    张小磊
  • 【ML】一文详尽系列之K-means算法

    时间复杂度:,其中,t 为迭代次数,k 为簇的数目,n 为样本点数,m 为样本点维度。

    yuquanle
  • 一文详尽解释K-means算法

    K-means 是我们最常用的基于距离的聚类算法,其认为两个目标的距离越近,相似度越大。

    石晓文
  • GBDT算法(详细版)

    一、前言 通过之前的文章GBDT算法(简明版)对GBDT的过程做了大概的讲解,我们可以了解到GBDT是一种迭代的决策树算法,由多棵决策树组成,所有树的结论累加起...

    智能算法
  • 业界 | 从集成方法到神经网络:自动驾驶技术中的机器学习算法有哪些?

    选自kdnuggets 作者:Savaram Ravindra等 参与:Lj Linjing、蒋思源 机器学习算法可以融合来自车体内外不同传感器的数据,从而评估...

    机器之心
  • 《数据结构与算法》O(3N)=O(N)?

    相互之间存在一种或多种特定关系的数据元素的集合,我总结一下就是描述数据关系的一种载体。

    Java3y
  • 自动驾驶技术中的机器学习算法有哪些?

    如今,机器学习算法正大规模地用于解决自动驾驶汽车产业日益增多的问题。结合 ECU (电子控制单元)传感器数据,我们须加强对机器学习方法的利用以迎接新的挑战。潜在...

    机器人网
  • GBDT 算法:原理篇

    GBDT 是常用的机器学习算法之一,因其出色的特征自动组合能力和高效的运算大受欢迎。这里简单介绍一下 GBDT 算法的原理,后续再写一个实战篇。

    陈龙

扫码关注云+社区

领取腾讯云代金券