开发者论坛 | 海睿思 轻量化数据中台生态引领者

 找回密码
 立即注册
搜索
热搜: 活动 交友 discuz
查看: 279|回复: 0

GBDT的原理和应用(下)

[复制链接]

6

主题

10

帖子

38

积分

新手上路

Rank: 1

积分
38
发表于 2022-3-15 15:50:07 | 显示全部楼层 |阅读模式
[color=rgba(0, 0, 0, 0.75)]

实践
XGBoost是GBDT最广为人知的一个实现。通过使用一定程度的近似,使得求解变得更高效。同时支持分布式和 GPU 优化,有着广泛的使用。在实践中,算法工程师使用 Spark 或者Python 的 XGBoost 库训练模型,并保存成文件,线上根据不同的语言采用相应的依赖包,将模型导入,执行决策。Java 中使用。
XGBoost算法原理
还记得前文提到的 GBDT 可以用如下公式表示:


[color=rgba(0, 0, 0, 0.75)]

优化目标如下:


[color=rgba(0, 0, 0, 0.75)]

年样本数量,yi表示样本真实 Label,y是模型输出,所以前半部分代表模型的损失函数。K表示树的个数,fk表示第K棵树. 那么如何找到一组树,使得 obj最小呢。
核心的思想是,已经训练好的树T1 - Tt-1不再调整。根据目标函数最小原则,新增树他Tt去拟合。
假设此时对第t棵树训练,则目标函数表示为:


[color=rgba(0, 0, 0, 0.75)]

回顾高等数学中的泰勒展开,它使用一个函数的高阶导数,用多项式的形式逼近原始函数。当展开到二阶导数的时候公式如下:


[color=rgba(0, 0, 0, 0.75)]

对obj二阶泰勒公式展开:


[color=rgba(0, 0, 0, 0.75)]

忽略常量得到:


[color=rgba(0, 0, 0, 0.75)]

如前述示T节点个数,w叶子节点的输出。
我们可以把这个视角换一下。既然每个样本都会落到一个叶子节点,最外层的累加维度可以为叶节点。定义
,含义是被映射到第j叶子节点的样本,该叶子节点的输出为
,那么


[color=rgba(0, 0, 0, 0.75)]


[color=rgba(0, 0, 0, 0.75)]

可以推导出:


[color=rgba(0, 0, 0, 0.75)]

看做一个二项式,可以得到:


[color=rgba(0, 0, 0, 0.75)]

所以根对于待训练的新树而言, 可以根据训练好的树预先计算好,枚举所有可能的新树的结构,选择目标函数最小的那棵树,同时使用
求得该树每个叶子节点的输出值,不断求解下去,就可以训练出一组最优树。
贪心法求解树
在XGBoost使用贪心法求解树结构,算法描述如下:
初始化树深度 0(即只有一个叶子节点,所有样本都落在该节点)
对于每个叶子节点,尝试分裂该节点,在分裂后得到的增益定义如下:


[color=rgba(0, 0, 0, 0.75)]

该公式定义了,分裂后左右子树的新增得分减去不分裂时候节点得分,再减去因为新增一个节点,增加的复杂度。
对于每个叶子节点,枚举所有的特征
对每个特征,把映射到该叶节点的样本按照该特征值排序
使用线性扫描来决定最佳分裂点
在所有枚举的特征中,选择最优的分裂
总结
从XGBoost原理部分可以看出,XGBoost的实现中,采用了二阶泰勒展开公式展开来近似损失函数,同时在求解树的过程中,使用了贪心算法,并使用枚举特征,样本按照特征排序后,采用线性扫描找到最优分裂点。这种实现方法,是对GDBT思想的逼近,但是在工程上确非常有效



回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

QQ|开发者论坛 | 海睿思 轻量化数据中台生态引领者 ( 苏ICP备13008384号-7 )

GMT+8, 2022-7-4 23:40 , Processed in 0.046345 second(s), 19 queries .

Powered by Discuz! X3.4

Copyright © 2001-2020, Tencent Cloud.

快速回复 返回顶部 返回列表