专栏首页SAMshare【推荐收藏】带你读一遍 XGBoost论文(上)

【推荐收藏】带你读一遍 XGBoost论文(上)

XGBoost作为一个非常常用的算法,我觉得很有必要了解一下它的来龙去脉,于是抽空找了一些资料,主要包括陈天奇大佬的论文以及演讲PPT,以及网络上的一些博客文章,今天在这里对这些知识点进行整理归纳,论文中的一些专业术语尽可能保留不翻译,但会在下面写出自己的理解与解释。

? Index

  • XGBoost介绍
  • XGBoost亮点
  • 梯度增强树算法介绍
  • 分裂查找算法介绍
  • XGBoost的系统设计

? XGBoost介绍

在Paper中,作者定义XGBoost:

a scalable machine learning system for tree boosting.

XGBoost为“Extreme Gradient Boosting”的缩写,里面包含了关键字'Boosting',意味着它是一个boosting集成算法,所以它的主要思路是将成百上千个树模型组合起来成为一个准确率很高的模型,此模型通过不断迭代生成新的树。

XGBoost我们常用于监督学习,即建立一个数据模型,输入相关特征从而预测出目标,而这一过程,需要我们找到训练数据最好的参数,所以我们需要定义一个目标函数,通常由训练损失(traning loss)和正则项(regularization term)组成。

训练损失评估了预测模型的效果,例如常用的训练损失指标是均方误差或是逻辑回归的logistic loss。正则项则是控制着模型的复杂度,避免模型不被过度拟合。这两个互相博弈(tradeoff)的指标保证了模型的预测效果以及简洁程度。

? XGBoost亮点

  • We design and build a highly scalable end-to-end tree boosting system.
  • We propose a theoretically justified weighted quantile sketch for efficient proposal calculation.
  • We introduce a novel sparsity-aware algorithm for par- allel tree learning.
  • We propose an effective cache-aware block structure for out-of-core tree learning.

翻译来说,就是它设计并构建了适用于大规模的 end-to-end 的Boosting系统(end-to-end指的是端到端,就是只关心输入和输出,中间过程都不care),而且实现特征选择的并行处理,正则使用L2的稀疏感知算法,而且也提出了有效的缓存结构,加大训练效率

另外,其他博文也有一些总结:

  • 相对GBDT来说,XGB在增加二阶梯度有更高的精度;
  • XGB的节点划分策略带有进行预排序,利用样本在损失函数上面的二阶梯度作为权值;
  • XGB对稀疏的特征划分方式;
  • 在处理特征的粒度上进行多线程的优化;
  • 使用近似算法替代每个样本逐个判断最佳分裂点的Exact Greedy Algorithm算法。

? 梯度增强树算法介绍

XGBoost还是采用属于gradient tree boosting algorithms,推导过程和已有的算法理论类似,但这里有了一些创新,比如正则化学习目标、样本子采样、特征子采样、近似算法等等。

3.1 Regularized Learning Objective

给定一个n X m维的数据集D,通过训练D,得到K棵树,而这K棵树累加的值作为我们的预测值。

其中,

是CART的空间,q表示每个树的结构,其可以将每个样本映射到对应的叶节点中,T是树中叶子节点的个数。

有了上面的预测值,我们可以代入loss function,得到我们的损失函数:

可以看出损失函数由两部分组成,Training Loss和Regularization。

3.2 Gradient Tree Boosting

这一节是对损失函数的推导求解,这里不是采取传统的优化方法进行优化,而是采用了Additive Training训练,我们将Training Loss部分,展开成K棵树叠加的形式,开始于一个常数,每次增加一个新的函数学习当前的树,贪婪地利用误差函数改善当前模型,而这里创新的点在于对误差函数进行二阶泰勒近似展开。

具体公式推导就不展开了,建议查阅:

XGBoost原理介绍:https://blog.csdn.net/yinyu19950811/article/details/81079192

3.3 Shrinkage and Column Subsampling

这一节讲到了两种防止过拟合的tricks,Shrinkage和Column Subsampling。

  • Shrinkage:权值收缩,主要针对叶子节点,在每一次的Tree Boosting后,收缩叶子节点的权重,降低了每棵独立树的影响,为将来的优化留出一些空间。
  • Column Subsampling:这种技术出现在RF中,这种做法不仅可以防止过拟合,还能提升一部分训练效率。

? 分裂查找算法介绍

4.1 Basic Exact Greedy Algorithm

这个是常见的基础贪心算法,即对所有的特征进行遍历处理,这就要求对计算资源要求比较高,因为需要对每个特征计算其信息增益,选择增益最大的作为分裂点,当然是需要比较多的时间和算力。

4.2 Approximate Algorithm

顾名思义,近似算法就是可能效果或者原理和Exact Greedy Algorithm差不多的算法,它的原理是根据特征分布的百分位数进行采样,选择待分裂点,然后,该算法将连续特征映射到由这些候选点分割的桶中,汇总统计信息并根据汇总的信息找到最佳解决方案,这里选择分裂点的方式有global和local:

  • global:在树构建的初始状态阶段选出所有候选分裂点,后面每层都使用相同的策略选择分裂点。
  • local:每次分裂后重新选出候选分裂点,适合深度较大的树,因为不需要提前准备过多的候选分裂点。

这只是上半部分,后面继续写后半部分?

? References

  • 百度百科
  • 干货|XGBoost为什么能“横扫”机器学习竞赛(附论文)http://www.sohu.com/a/136316635_642762
  • XGBoost论文阅读及其原理 https://zhuanlan.zhihu.com/p/36794802
  • XGBoost原理介绍 https://blog.csdn.net/yinyu19950811/article/details/81079192
  • XGBoost论文阅毕 https://blog.csdn.net/mikasa3/article/details/82919755

本文分享自微信公众号 - SAMshare(gh_8528ce7b7e80),作者:Samshare

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

原始发表时间:2019-06-21

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【推荐收藏】带你撸一遍 XGBoost论文

    XGBoost作为一个非常常用的算法,我觉得很有必要了解一下它的来龙去脉,于是抽空找了一些资料,主要包括陈天奇大佬的论文以及演讲PPT,以及网络上的一些博客文章...

    Sam Gor
  • 推荐收藏 | 10道XGBoost面试题送给你

    XGBoost的威名想必大家都有所耳闻,它不仅是数据科学竞赛神器,在工业界中也被广泛地使用。本文给大家分享珍藏了多年的XGBoost高频面试题,希望能够加深大家...

    Sam Gor
  • Machine Learning-算法汇总介绍

    之前一个一个讲还是有些零散而且更新的速度也慢,所以我还是打算先整理一波全部的算法,再逐一展开介绍比较好,原文来自Jason Brownlee 的文章《A Tou...

    Sam Gor
  • 你听说过XGBoost吗

    这是个深度学习的时代,传统的机器学习算法仿佛已经失去了往日的光彩,你能随处听到卷积神经网络、循环神经网络以及其他各种net,偶尔听到的机器学习算法也是支持向量机...

    深度学习与Python
  • XGBoost资料汇总,以及它背后的故事

    近来,群中有几个小伙伴想要公号推送XGBoost的相关内容,去年我在学习XGBoost时写过几篇笔记(恕我当时理解的浅显):

    double
  • 【推荐收藏】带你撸一遍 XGBoost论文

    XGBoost作为一个非常常用的算法,我觉得很有必要了解一下它的来龙去脉,于是抽空找了一些资料,主要包括陈天奇大佬的论文以及演讲PPT,以及网络上的一些博客文章...

    石晓文
  • 【推荐收藏】带你撸一遍 XGBoost论文

    XGBoost作为一个非常常用的算法,我觉得很有必要了解一下它的来龙去脉,于是抽空找了一些资料,主要包括陈天奇大佬的论文以及演讲PPT,以及网络上的一些博客文章...

    Sam Gor
  • 周末漫谈|XGBoost与深度学习到底孰优孰劣?都说XGBoost好用,为什么名气总不如深度学习?

    来源|Quora 整理|AI100 AlphaGo大战柯洁、李世石后,所有人都能谈上几句深度学习。人工智能在围棋上的这场突破,最终还要归功于机器学习三巨头三十年...

    AI科技大本营
  • 陈天奇做的XGBoost为什么能横扫机器学习竞赛平台?

    在涉及非结构化数据(图像、文本等)的预测问题中,人工神经网络显著优于所有其他算法或框架。但当涉及到中小型结构/表格数据时,基于决策树的算法现在被认为是最佳方法。...

    新智元
  • 回归建模的时代已结束,算法XGBoost统治机器学习世界

    Vishal Morde讲了这样一个故事:十五年前我刚完成研究生课程,并以分析师的身份加入了一家全球投资银行。在我工作的第一天,我试着回忆我学过的一切。与此同时...

    用户2769421

扫码关注云+社区

领取腾讯云代金券