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

作者：包大人

原文：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