All About GBDT (1)

GBDT(Gradient Boosting Decision Tree) 从名字上理解包含三个部分：提升、梯度和树。它最早由 Freidman 在 greedy function approximation ：a gradient boosting machine 中提出。很多公司线上模型是基于 GBDT+FM 开发的，我们 Leader 甚至认为 GBDT 是传统的机器学习集大成者。断断续续使用 GBDT 一年多后，大胆写一篇有关的文章和大家分享。

朴素的想法

假设有一个游戏：给定数据集 ，寻找一个模型，使得平方损失函数 最小。

如果你的朋友提供一个可以使用但是不完美的模型，比如 在如何不修改这个模型的参数情况下，提高模型效果？

一个简单的思路是：重新训练一个模型实现

换一个角度是用模型学习数据 。得到新的模型 。

其中 的部分被我们称之为残差，即之前的模型没有学习到的部分。重新训练模型 正是学习残差。如果多次执行上面的步骤，可以将流程描述成：

即 ，这也就是 GBDT 。

如何理解 Gradient Boosting Decision Tree ?

Gradient Boosting Decision Tree 简称 GBDT，最早由 Friedman 在论文《Greedy function approximation: a gradient boosting machine》中提出。简单从题目中理解包含三个部分内容：Gradient Descent、Boosting、Decision Tree。

Decision Tree 即决策树，利用超平面对特征空间划分来预测和分类，根据处理的任务不同分成两种：分类树和回归树。在 GBDT 算法中，用到的是 CART 即分类回归树。用数学语言来描述为 ，完成样本 到决策树叶子节点 的映射，并将该叶子节点的权重 赋给样本。CART 中每次通过计算 gain 值贪心来进行二分裂。

Boosting 是一种常用的集成学习方法（另外一种是 Bagging）。利用弱学习算法，反复学习，得到一系列弱分类器（留一个问题，为什么不用线性回归做为弱分类器）。然后组合这些弱分类器，构成一个强分类器。上面提到的模型 即是一种 boosting 思路，依次训练多个 CART 树 ，并通过累加这些树得到一个强分类器 。

为什么 GBDT 可行？

在 2 中我提到 GBDT 包括三个部分并且讲述了 Boosting 和 Decison Tree。唯独没有提到 Gradient Descent，GBDT 的理论依据却恰恰和它相关。

回忆一下，Gradient Descent 是一种常用的最小化损失函数 的迭代方法。

• 给定初始值
• 迭代公式：
• 将 在 处进行一阶泰勒展开：
• 其中 是步长，可以通过 line search 确定，但一般直接赋一个很小的数。

在 1 中提到的问题中，损失函数是 MSE 。

我们的任务是通过调整 最小化 。

如果将 当成是参数，并对损失函数求导得到 。

可以发现，在 1 中提到的模型 学习的残差 正好等于负梯度，即 。

所以，参数的梯度下降和函数的梯度下降原理上是一致的：

GBDT 算法流程

模型 F 定义为加法模型：

其中，x 为输入样本，h 为分类回归树，w 是分类回归树的参数， 是每棵树的权重。

通过最小化损失函数求解最优模型：

1. 对于 ：
   1. 计算负梯度（伪残差）：
   2. 根据 学习第 m 棵树：
   3. line searcher 找步长：
   4. 令 ，更新模型：

1. 初始化 方法
   1. 求解损失函数最小
   2. 随机初始化
   3. 训练样本的充分统计量
2. 每一轮拟合负梯度，而不是拟合残差，是为方便之后扩展到其他损失函数。
3. 最小化问题中，如果有解析解，直接带入。否则，利用泰勒二阶展开，Newton Step 得到近似解。

这一篇就先到这里，之后还会分享 GBDT 常用损失函数推导以及 XGboost 相关内容。如果有任何想法，都可以在留言区和我交流。

Reference