前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >从一道数学题到GBDT原理的部分推导

从一道数学题到GBDT原理的部分推导

作者头像
统计学家
发布2019-08-23 17:49:20
9440
发布2019-08-23 17:49:20
举报
文章被收录于专栏:机器学习与统计学

作者:包大人

原文:https://zhuanlan.zhihu.com/p/76002032

首先要从一道我在字节跳动遇到的一道面试题讲起,可以说是十分精妙的一道题。

在任意序列

中,划分两个子集

定义函数

其中

,

求解

,要求编程实现做到的时间复杂度最优。(其实就是Square Error下的回归树切分点计算,如何优化的问题)

这个题简单粗暴的办法就是从0到n遍历所有的切分点。我们观察一下,每次遍历一次切分点,都要重新计算一次均值,然后再算n次减法的平方和。

这必然不是最优解,怎么优化呢?我们往下看。想看结论的可以直接翻到最后。

为什么说这道题比较精妙呢,他其实跟GBDT有着千丝万缕的联系,可以推导出LightGBM论文里面一个非常隐晦以及关键的定义。

那么我们看看下面的一个问题。从GBDT的建树过程讲起。

参考文献[3]最早的GBDT其实有个两步优化,但是研究了下类似sklearn的实现都把line search这一步省略了,用定学习率的函数空间梯度下降来代替,所以这里也忽略了那个line search.

在GBDT里面,我们使用回归树拟合负梯度的时候(注意不是残差,千万不要一大票博客被带跑偏了),整体的loss为如下。遍历一棵树的所有叶子节点,对预测值求一个偏差的平方和。

每个叶子节点的值为落到当前叶子节点上的预测值的均值,这是使用平方和误差作为建回归树损失的推导结果,(注意建树损失函数和优化目标损失函数的一定要区分开)。

即当前叶子结点的预测值为

(这个推导可以见参考文献3,其实在不同的建树loss下这个是不一样的,甚至有种神奇的中位数的情况)

我们建树的时候,就看每一次划分,是让loss变小了吗,那么考虑对叶子节点j划分成两部分,一部分是左节点

,一部分是右节点

,那么划分后loss的变为。

一个简单粗暴的办法就是在每次遍历切分点的时候,把这个式子计算一遍,这样没问题,好多demo级别的代码也是这么实现的,那么有没有办法优化呢?

我们继续看两次的loss变化为。

我们只需要找出

最大的值就可以了。就是我们的目标切分点。

由于前面是一个定量,我们 可以直接忽略。只需要研究后半部分

是不是很熟悉,这不就是那道面试题吗!

其实这个推导也就比较简单了,我们考虑一个引理

好了原来的公式可以变成

前面是跟切分位置无关的项。所以剩下找

的最小值。所以GBDT在回归树建立的时候,分裂指标是variance gain(LightGBM 论文的定义)

LightGBM 定义3.1

注意这里面的

对一次分裂来说是常量不影响结果,作者写在这里是为了论文里GOSS优化技巧的算法bound推导。所以对我们来说可以去掉。

可以简单的写成

,其中G是一阶梯度和,Xgboost的是

是不是很像呢。这个式子非常简洁漂亮。

Xgboost通过对LOSS二阶泰勒展开求得的结果和我们通过对LOSS化简推导得的结果是相似的。只不过它考虑了二阶导数和模型复杂度的正则参数。

Introduction to Boosted Trees -Tianqi Chen

这样的好处,我遍历切分点的时候,只需要一次加(减)法运算,一次乘方运算就可以了。避免了之前的n次加(减)法运算和n次乘方运算。

这是GBDT在实现的时候一个非常关键的trick. 在这里给头条的面试官点个赞,不知道透露了大佬的祖传面试题会不会打死我~

关于GBDT网上写的好的文章不多,大多数是用李航老师统计机器学习方法上的“拟合残差”为例子讲的,那个例子会让人混淆了优化LOSS和建树的LOSS,然后还让大家过拟合到残差上了,XGBoost天奇大佬的ppt写的很清楚了,这里拾人牙慧把GBDT的建树Gain推导也写一下,可以看出来,回归树没有问题,支持任意损失函数也没有问题。一定一定要记住,那个"拟合残差"是目标损失是MSE的情况,建树损失是square error的情况这个的特例。其实就两点,一个是拟合负梯度,一个是回归树做一切。

参考文献

[1]. LightGBM: A Highly Efficient Gradient Boosting Decision Tree. Guolin Ke

[2].Introduction to Boosted Trees. Tianqi Chen

[3].Greedy function approximation: a gradient boosting machine. JH Friedman

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2019-08-22,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 机器学习与统计学 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档