集成学习（三）GBDT 梯度提升树

前面学习了：集成学习（二）Boosting-****博客

梯度提升树：GBDT-Gradient Boosting Decision Tree

一、介绍

作为当代众多经典算法的基础，GBDT的求解过程可谓十分精妙，它不仅开创性地舍弃了使用原始标签进行训练的方式，同时还极大地简化了Boosting算法的运算流程，让Boosting算法本该非常复杂的运算流程变得清晰简洁。GBDT的数学流程非常简明、美丽，同时这一美丽的流程也是我们未来所有Boosting高级算法的数学基础。与任意Boosting算法一致，对GBDT我们需要回答如下问题：

损失函数的表达式是什么？损失函数如何影响模型构建？
弱评估器是什么，当下boosting算法使用的具体建树过程是什么？
综合集成结果是什么？集成算法具体如何输出集成结果？

同时，还可能存在其他需要明确的问题，例如：

是加权求和吗？如果是，加权求和中的权重如何求解？
训练过程中，拟合的数据与分别是什么？

回顾Boosting算法的基本指导思想，我们来梳理梯度提升树回归算法的基本流程。虽然Boosting理论很早就被人提出，但1999年才是GBDT算法发展的高潮。1999年，有四篇论文横空出世：

《贪心函数估计：一种梯度提升机器》
Friedman, J. H. (February 1999). "Greedy Function Approximation: A Gradient Boosting Machine"

《随机梯度提升》
Friedman, J. H. (March 1999). "Stochastic Gradient Boosting"

《梯度下降式提升算法》
Mason, L.; Baxter, J.; Bartlett, P. L.; Frean, Marcus (1999). "Boosting Algorithms as Gradient Descent"

《函数空间中的梯度下降式提升算法》
Mason, L.; Baxter, J.; Bartlett, P. L.; Frean, Marcus (May 1999). "Boosting Algorithms as Gradient Descent in Function Space"

GBDT算法是融合了上述4篇论文思想的集大成之作，为了保持一致，使用与前文不同的数学符号。

二、数学过程

假设现有数据集，含有形如 $\left ( x_{i}, y_{i} \right )$ 的样本个，为任意样本的编号，单一样本的损失函数为 $l\left ( y_{i}, H\left ( x_{i} \right ) \right )$ ，其中 $H\left ( x_{i} \right )$ 是号样本在集成算法上的预测结果，整个算法的损失函数为 $L\left ( y, H( x ) \right )$ ，且总损失等于全部样本的损失之和： $L(y,H(x))=\sum_{i}^{}l\left ( y_{i}, H\left ( x_{i} \right ) \right )$ 。同时，弱评估器为回归树 ，总共学习轮。则GBDT回归的基本流程如下所示：

1、初始化数据迭代的起点 $H_{0}(x)$ 。sklearn当中，我们可以使用0、随机数或者任意算法的输出结果作为 $H_{0}(x)$ ，但在最初的论文中，Friedman定义了如下公式来计算 $H_{0}(x)$ ：

其中 $y_{i}$ 为真实标签， C 为任意常数。以上式子表示，找出令 $\sum_{i}^{M}l\left ( y_{i}, C \right )$ 最小的常数 C 值，并输出最小的 $\sum_{i}^{M}l\left ( y_{i}, C \right )$ 作为 $H_{0}(x)$ 的值。需要注意的是，由于 $H_{0}(x)$ 是由全部样本的计算出来的，因此所有样本的初始值都是 $H_{0}(x)$ ，不存在针对某一样本的单一初始值。

开始循环，for t in 1,2,3...T：

2、在现有数据集 N 中，抽样 M∗subsample 个样本，构成训练集 $N_{t}$
3、对任意一个样本，计算伪残差（pseudo-residuals） $r_{it}$ ，具体公式为：

不难发现，伪残差是一个样本的损失函数对该样本在集成算法上的预测值求导后取负的结果，并且在进行第次迭代、计算第个伪残差时，我们使用的前 t-1 次迭代后输出的集成算法结果。在 t=1 时，所有伪残差计算中的 $H_{t-1}(x_{i})$ 都等于初始 $H_{0}(x)$ ，在 t> 0 时，每个样本上的 $H_{t-1}(x_{i})$ 都是不同的取值。

4、求解出伪残差后，在数据集 $\left ( x_{i},r_{it} \right )$ 上按照CART树规则建立一棵回归树 $f_{t}$ ，训练时拟合的标签为样本的伪残差 $r_{it}$ 。

5、将数据集 $N_{t}$ 上所有的样本输入 $f_{t}$ 进行预测，对每一个样本，得出预测结果 $f_{t}\left ( x_{i} \right )$ 。在数学上我们可以证明，只要拟合对象是伪残差 $r_{it}$ ，则 $f_{t}\left ( x_{i} \right )$ 的值一定能让损失函数最快减小。

6、根据预测结果 $f_{t}\left ( x_{i} \right )$ 迭代模型，具体来说：

假设输入的步长为 $\eta$ ，则 $H_{t}(x)$ 应该为：

对整个算法则有：

7、循环结束，输出 $H_{T}(x)$ 的值作为集成模型的输出值。

三、初始化 $H_{0}$ 过程中的常数C是什么？

在最初的论文中，Friedman定义了如下公式来计算 $H_{0}$ :

其中 $y_{i}$ 为真实标签， C 为任意常数。以上式子表示，找出令 $\sum_{i}^{M}l\left ( y_{i}, C \right )$ 最小的常数 C 值，并输出最小的 $\sum_{i}^{M}l\left ( y_{i}, C \right )$ 作为 $H_{0}(x)$ 的值。在刚观察这个式子时，大家可能很难理解 C 这个常数的作用，但这个式子实际上很简单。

首先，是损失函数，损失函数衡量两个自变量之间的差异，因此 $l\left ( y_{i}, C \right )$ 衡量样本的真实标签 $y_{i}$ 与常数C之间的差异，因此 $l\left ( y_{i}, C \right )$ 是所有样本的真实标签与常数C之间的差异之和。现在我们要找到一个常数C，令所有样本的真实标签与常数C的差异之和最小，请问常数C是多少呢？这是一个典型的求极值问题，只需要对 $\sum_{i}^{M}l\left ( y_{i}, C \right )$ 求导，再令导数为0就可以解出令 $\sum_{i}^{M}l\left ( y_{i}, C \right )$ 最佳的C。假设是squared_error，每个样本的平方误差，则有：

对上述式子求导，并令一阶导数等于0：

所以：

可知，当L是平方误差squared error时，令 $l\left ( y_{i}, C \right )$ 最小的常数C就是真实标签的均值。因此，式子 $H_{0}=argmin_{C}\sum_{i}^{M}l\left ( y_{i}, C \right )$ 的本质其实是求解 $C=mean\left ( y_{i} \right )$ 时的损失函数，并以此损失函数作为 $H_{0}$ 的值。当然，如果我们选择了其他的损失函数，我们就需要以其他方式（甚至梯度下降）进行求解， C 的值可能也就不再是均值了。

四、为什么拟合伪残差可以令损失函数最快地减小

从直觉上来看，拟合伪残差可以降低 $H_{t}\left ( x_{i} \right )$ 与 $y_{i}$ 之间的差异，从而降低整体损失函数的值，但这个行为在数学上真的可行吗？毕竟，GBDT可以使用任意可微函数作为损失函数，不同损失函数求导后的结果即便与残差相似，也未必能代替真正的残差的效果。因此，不仅在直觉上需要理解拟合伪残差的作用，我们还需要从数学上证明：只要拟合对象是伪残差 $r_{it}$ ，则弱评估器的输出值 $f_{t}\left ( x_{i} \right )$ 一定是让损失函数减小最快的值。

我们可以对损失函数进行泰勒展开。对单一样本而言，我们有损失函数 $l(y_{i},H_{t-1}(x_{i})+f_{t}(x_{i}))$ ，其中 $y_{i}$ 是已知的常数，因此损失函数可以被看做是只有 $H_{t-1}(x_{i})+f_{t}(x_{i})$ 一个自变量的函数，从而简写为 $l(H_{t-1}(x_{i})+f_{t}(x_{i}))$ 。

根据一阶泰勒展开，已知：

该式子中 $H_{t-1}(x_{i})$ 是常数，因此第一部分 $l(H_{t-1}(x_{i}))$ 也是一个常数。同时，第二部分由导数和 $f_{t}$ 组成，其中导数就是梯度，可以写作 $g_{i}$ ，所以式子可以化简为：

现在，如果要令最小， $f_{t}(x_{i})$ 应该等于多少呢？回到我们最初的目标，找出令损失函数最小的 $f_{t}$ 值：

常数无法被最小化，因此继续化简：

现在， $g_{t}$ 是包含了所有样本梯度的向量， $f_{t}(x)$ 是包含了所有样本在 $f_{t}$ 上预测值的向量，两个向量对应位置元素相乘后求和，即表示为向量的内积，由尖括号 〈〉 表示。现在我们希望求解向量内积的最小值、并找出令向量内积最小的 $f_{t}(x)$ 的取值，那就必须先找出 $f_{t}(x)$ 的方向，再找出 $f_{t}(x)$ 的大小。

1、方向

$f_{t}(x)$ 的方向应该与 $g_{t}$ 完全相反。向量的内积 $\left \langle g_{t} f_{t}(x)\right \rangle=\left |g_{t} \right |\left | f_{t} (x) \right |cos(\alpha)$ ，其中前两项为两个向量的模长， α 是两个向量的夹角大小。模长默认为整数，因此当且仅当两个向量的方向完全相反，即夹角大小为180度时， cos(α) 的值为-1，才能保证两个向量的内积最小。假设向量 a = [1,2]，向量b是与a的方向完全相反的向量。假设a和b等长，那向量b就是[-1,-2]。因此，与 $g_{t}$ 方向完全相反且等长的向量就是， $-g_{t}$ ， $f_{t}(x)$ 的方向也正是 $-g_{t}$ 的方向。

2、大小

对于向量a，除了[-1,-2]之外，还存在众多与其呈180度夹角、但大小不一致的向量，比如[-2,-4], [-0.5,-1]，每一个都可以与向量a求得内积。并且我们会发现，当方向相反时，向量b中的元素绝对值越大，b的模长就越长，向量a与b的内积就越小。因此不难发现， $\left \langle g_{t} f_{t}(x)\right \rangle$ 是一个理论上可以取到无穷小的值，那我们的 ft(x) 应该取什么大小呢？答案非常出乎意料：任何大小都无所谓。

回到我们的迭代公式：

无论 $f_{t}(x)$ 的大小是多少，我们都可以通过步长 η 对其进行调整，只要能够影响 H(x) ，我们就可以影响损失迭代过程中的常数的大小。因此在数学上来说， $f_{t}(x)$ 的大小可以是 $-g_{t}$ 的任意倍数，这一点在梯度下降中其实也是一样的。为了方便起见，同时为了与传统梯度下降过程一致，我们通常让 $f_{t}(x)$ 就等于一倍的 $-g_{t}$ ，但也有不少论文令 $f_{t}(x)$ 等于其他值的。在GBDT当中：

这就是我们让GBDT当中的弱评估器拟合伪残差/负梯度的根本原因。拟合负梯度其实为GBDT带来了非常多的特点:

首先，通过直接拟合负梯度，GBDT避免了从损失函数找“最优”的过程，即避免了上述证明中求解 $f_{t}=argmin_{f}\sum_{i=1}^{M}l\left ( H_{t-1}(x_{i})+f_{t}(x_{i}) \right )$ 的过程，从而大大地简化了计算。

其次，通过拟合负梯度，GBDT模拟了梯度下降的过程，由于结合了传统提升法Boosting与梯度下降，因此才被命名为梯度提升法（Gradient Boosting）。这个过程后来被称为函数空间上的梯度下降（Gradient Descent in Function Space），这是视角为Boosting算法的发展奠定了重要的基础。

最后，最重要的一点是，通过让弱评估器拟合负梯度，弱评估器上的结果可以直接影响损失函数、保证损失函数的降低，从而指向Boosting算法的根本目标：降低偏差。这一过程避免了许多在其他算法中需要详细讨论的问题：例如，每个弱评估器的权重 ϕ 是多少，以及弱评估器的置信度如何。

在AdaBoost算法当中，损失函数是“间接”影响弱评估器的建立，因此有的弱评估器能够降低损失函数，而有的弱评估器不能降低损失函数，因此要在求和之前，需要先求解弱评估器的置信度，然后再给与置信度高的评估器更高的权重，权重 ϕ 存在的根本意义是为了调节单一弱评估器对 ϕ 的贡献程度。但在GBDT当中，由于所有的弱评估器都是能够降低损失函数的，只不过降低的程度不同，因此就不再需要置信度/贡献度的衡量，因此就不再需要权重 ϕ 。

五、遗留问题

有些细节性的东西本文还没有讲到，比如：

叶子结点如何取值？
其他损失函数下怎么推导？
...

详见下面《集成学习（四）DT、GBDT 公式推导》，注意：这两篇文章的符号不一样！！

接下来学习：

秒客网

集成学习（三）GBDT 梯度提升树