超级女王XGBoost到底“绝”在哪里?

读芯术 2019/05/15 23:18

全文共 3492 字,预计学习时长 15 分钟

前几天, Z 同学面试完一脸生无可恋地问我,“ 你知道XGBoost吗?

“当然知道啊,前几天不看你还在手推来着。”

“嗯,那你知道XGBoost的中英文全称是啥么?”

“ummmmm...X的话难道是罗马数字10? G的话Gradient梯度,Boost的Boosting tree?所以是第十代梯度提升树?”

“。。。换你答,你也凉。”

知识图谱,超级女王XGBoost到底“绝”在哪里?

图片来源:SOOGIF网站

知识图谱,超级女王XGBoost到底“绝”在哪里?

学习算法的最大误区

还记得那个吐槽清华某毕业生连手写红黑树都不会却张口就要一万八的HR吗?

知识图谱,超级女王XGBoost到底“绝”在哪里?

这事曾一度引起网友的广泛关注和热烈讨论,不过圈子不同,影响不同。

对于普通吃瓜群众,“HR说得对,太膨胀。”

对于某些资深程序猿,“我也不会,我月薪30k。”

对于求职小白,“好慌,手写红黑树?面试不会还要手推SVM、XGBoost吧?溜了溜了,去推泰勒二次展开了。

然后,就像我的同学小Z一样,只顾着埋头推导XGBoost的二阶泰勒展开,却连XGBoost的中英文全称都答不上来。

顾此失彼,乃是兵家大忌。 很多时候,我们在学习算法时,要么过于纠结弄懂原理而忽略了从宏观上对算法有一个总体的了解和把握,要么是囫囵吞枣一口气看个十来篇博客介绍却往往还是一知半解不求甚解,可能还会莫名自我感觉良好。

基于此,本文就从宏观上来帮大家梳理梳理XGBoost,力求通俗易懂,精准得当。至于算法原理和 资源链接嘛,请直接拜读陈天奇博士的论文 XGBoost: A Scalable Tree Boosting System,同时请参考Github上的开源资源进行源码的学习和实战( https://github.com/dmlc/xgboost

知识图谱,超级女王XGBoost到底“绝”在哪里?

什么是 XGBoost?

知识图谱,超级女王XGBoost到底“绝”在哪里?

原图来自 Unsplash (by Jared Subia

十几年前,回归建模是预测分析中毫无争议的女王。但如今 回归建模的时代已经结束,XGBoost已被成功加冕!

XGBoost的英文全称为Extreme Gradient Boosting, 中文可以解释为极端梯度提升(Extreme,一听就很牛X),它是一种基于决策树的集成机器学习算法,采用了梯度 提升(Gradient Boosting)框架。 在预测有关非结构化数据(如图像、文本等)的问题时,人工神经网络往往表现得比其他算法或框架更出色。但在有关中小型结构/表格数据方面,基于决策树的算法则是目前为止的最佳方式。

请参阅以下图表,了解几年来基于决策树的算法演变。

知识图谱,超级女王XGBoost到底“绝”在哪里?

基于决策树的算法演变

XGBoost算法最初由华盛顿大学的一个研究项目发展而来。2016年,陈天奇和卡洛斯·格斯特林在知识发现和数据挖掘(SIGKDD)会议上共同发表了一篇论文,一时间这轰动了整个机器学习领域。

自算法提出以来,它不仅帮助竞赛者赢得了多场Kaggle竞赛的胜利,还被几款尖端行业的应用所采纳。在GitHub上,有一群强大的数据科学家们为XGBoost开源项目提供帮助,约有350名科学家,总提交次数约为3,600次。总体而言, XGBoost 具有以下特征:

1. 应用广泛: 可用于解决回归、分类、排名和用户定义的预测问题。

2. 移植性强:可在Windows、Linux和OS X上流畅运行。

3. 语言支持:支持目前主要的全部编程语言,包括C ++、Python、R、Java、Scala和Julia。

4. 云集成:支持AWS、GCE、Azure和 Yarn集群,可以与 Flink、Spark和其他云数 据流系统集成。

知识图谱,超级女王XGBoost到底“绝”在哪里?

通俗理解基于决策树的算法演变

知识图谱,超级女王XGBoost到底“绝”在哪里?

照片来自Unsplash( by rawpixel

假设你是一名面试官,正在面试几位资历优秀的候选人。基于决策树的算法演变中的每一环,都可看作面试过程的一部分。

1. 决策树:每名面试官都有一套面试评价标准,如教育水平、工作经验以及面试表现,通过决策树来预测分析,就类似于面试官根据他自己的标准面试候选人。

2. Bagging:假设现在面试官不止一名,而是一个面试小组,每名面试官都有一票,Bagging( 也称作bootstrap aggregating 意味着通过民主投票方式,将所有面试官的投票结果进行输入,从而做出最终决定。

3. 随机森林:这是一种基于bagging的算法,与bagging的不同在于仅随机选择特征的子集。换句话说,每名面试官只会根据某些随机的资质测试方式(例如,测试编程技能的技术面试和非技术技能评估的行为面试)来考查面试者。

4. Boosting:这是一种动态评估方法,每位面试官根据前一位面试官的反馈,改变评估标准。通过部署更加动态的评估流程,“提高”面试流程的效率。

5. Gradient Boosting:这是Boosting的一种特殊情况,通过梯度下降算法 将误差最小化 ,打个比方说,就好比战略咨询公司利用面试案例,剔除不合格的候选人。

6. XGBoost:将XGBoost视为强化版的的gradient boosting,毕竟extreme不是随随便便就能“ ”名的。它是软件和硬件优化技术的完美结合,可在最短的时间内,使用较少的计算资源,得 到较为出色的结果。

知识图谱,超级女王XGBoost到底“绝”在哪里?

XGBoost为什么这么“绝”?

XGBoost之所以能叫 XGBoost ,因为她够“绝”(够Extreme)。

XGBoost 和Gradient Boosting Machines(GBMs)都是基于决策树的集合方法,通过梯度下降架构来提升较弱学习者(通常是CARTs)。通过系统优化和算法增强,XGBoost进一步改进了基础GBM框架。

知识图谱,超级女王XGBoost到底“绝”在哪里?

XGBoost 如何优化GBM 标准算法

系统优化:

1. 并行化:XGBoost通过多线程实现了回归树的并行构建。由于用于构建基础学习者的循环具有可互换性,因此设计并行是可能的。外部循环枚举树的节点,内部循环则计算特征。这种循环嵌套在一定程度上限制了并行化,当没有完成内部循环,外部循环就无法启动。

因此,为改善运行时间,可通过对所有实例的全局扫描实现初始化,使用并行线程分类来交换循环顺序。这一交换通过抵消计算中的并行化开销,提高算法性能。

2. 决策树剪枝:当剪枝分裂遇到一个负损失时,GBM会停止分裂。因此GBM实际上是一个贪心算法(只求 达到 局部最优解就ok)。但XGBoost会一直分裂到指定的最大深度(max_depth),然后回过头来剪枝。这种“深度优先”方法显著提高了计算性能。

3.硬件优化:该算法旨在有效利用硬件资源。通过在每个线程中分配内部缓冲区,存储梯度统计信息,获取缓存感知。诸如“核外”计算等进一步增强功能可优化可用磁盘空间,同时处理不适合保存的大数据帧。

算法增强:

1. 正则化:通过LASSO(L1)和Ridge(L2)正则化来对更为复杂的模型进行惩罚,防止过度拟合。

2. 稀疏性感知:XGBoost具有稀疏性的离散特征,根据训练缺失自动“学习”最佳缺失值,并且可以更有效率地处理数据中不同类型的稀疏模式。

3. 加权分位数草图:XGBoost采用分布式加权分位数草图算法,有效地找到加权数据集中的最佳分裂点。

4. 交叉验证:在每次迭代时,该算法都有内置的交叉验证方法,无需显式地对搜索进行编程或明确在指定单次运行中所需的增强迭代数量。

有何证据?

我们使用Scikit-learn的“Make_Classification”数据包创建了一个包含20类特征(2类信息型和2类冗余型)的100万个数据点的随机样本。我们测试了几种算法,如逻辑回归、随机森林、标准Gradient Boosting和XGBoost。

知识图谱,超级女王XGBoost到底“绝”在哪里?

使用SKLearn的Make_Classification数据集比较XGBoos与其他机器学习算法

如上图所示,与其他算法相比,XGBoost模型是兼顾预测性能和处理时间的最佳预测方式。其他严格的基准研究也产生相同结果。正因如此,XGBoost在最近的数据科学竞赛中被广泛使用。

如有疑问,请使用XGBoost。

——Kaggle网站上Avito Context Ad Click Prediction竞赛的获奖者OwenZhang

知识图谱,超级女王XGBoost到底“绝”在哪里?

XGBoost的未来

尽管就目前而言,XGBoost的王座还难以撼动。但机器学习这一领域的学者大都比较活跃,而且不畏权贵,一心恋战。

目前已有几种据说可以匹敌XGBoost的新算法框架被提出,比如 微软研究中心新发布的LightGBM框架和Yandex Technology开发的CatBoost框架。

知识图谱,超级女王XGBoost到底“绝”在哪里?

图片来源:RSG Media网站

每当NIPS/ICML/KDD等顶级会议上一有新的算法被提出,最忙活的可能就是数据科学家了。数据科学家们必须测试所有可能的数据算法,以保证最终选择的算法是最佳的。此外, 选择正确的算法还远远不够,还 必须通过不断调整超参数,正确对算法数据集进行配置。

此外,如何选择最佳的算法还有其他几个值得考虑的因素,例如算法的计算复杂度、可解释性以及实现的难易程度。而这正是机器学习开始从科学走向艺术的时刻。

历史的车轮总是在不断向前滚动。XGBoost的铁王座早就被许多人觊觎垂涎,开发 一个优于XGBoost的更强大的模型框架只是时间上的早晚问题。

然而,在强大的挑战者出现之前,XGBoost将继续统治机器学习的世界!

编译组: 梁晶晶、狄思云

相关链接:

https://towardsdatascience.com/https-medium-com-vishalmorde-xgboost-algorithm-long-she-may-rein-edd9f99be63d

如需转载,请后台留言,遵守转载规范

知识图谱,超级女王XGBoost到底“绝”在哪里?

读芯术
收藏 | 微信分享 微博分享 QQ分享 | 返回顶部