树模型的目标函数为何能涉及梯度？怎样参数化表示一棵树 ...

JoshWindsor

经典的算法永远值得被吃透。回顾 XGBoost 的推导过程，仍能感觉到实在是太巧妙了！特别是 XGBoost 能将树模型这种非参模型引入参数和导数，进而得到最优参数的闭式解，拍案叫绝。本文内容来自贪心学院录播整理。

一、集成模型回顾：Bagging 和 Boosting 的区别

说到这两者的区别，我们很容易联想许多参考资料里说的：Boosting 方法中的弱学习器要串行生成，而Bagging 的的弱学习器之间没有依赖关系，可以并行生成。
除了这个计算方面的特性，Bagging 和 Boosting 原理层面的本质区别到底是什么呢？
为了回答这个问题，我们先回顾一下集成学习的概念：

集成学习（Ensemble Learning）本身不是一个单独的机器学习算法，而是通过构建并结合多个机器学习器来完成学习任务。也就是我们常说的「博采众长」。集成学习的直觉是结合多个个体的能力，获得远超个体的集体能力优势。这种直觉在实际上对于“弱学习器”是非常符合的。故很多集成学习的研究也都是针对弱学习器，而基学习器（Base Learner）有时也被直接称为弱学习器。
什么是弱学习器呢（weak learner）？弱学习器指泛化性能略优于随机猜测的学习器：例如在二分类问题精度略高于50%的分类器。

实际上，模型「弱」有两个可能的原因：过拟合（Overfitting）或者欠拟合（Underfitting）。
而这两个可能则解释了 Bagging 和 Boosting 的最本质区别！
它们都利用了弱学习器，但是弱的原因不同：

• Bagging 是利用了一些因为过拟合而不稳定的弱学习器：类似于请了很多专家；
  
• Boosting 则是利用了虽然稳定但是因为欠拟合而精度表现差的弱学习器：类似于请了很多小学生。
  

二、Boosting 提升树的训练框架

给了一个预测模型，但是效果不怎么好，误差比较大。但是我们只能接受这个模型，不能对它做任何改变，那么在这个基础上我们还能做什么事情呢？
—— 那就是计算它的残差，然后训练别的模型接着做！



提升树的引子

所谓残差就是 真实值 - 预测值。



训练第一个模型，计算残差



利用残差训练第二个模型，残差降低了

继续迭代下去…… 如何获得最终预测呢？
加起来！



最终的预测结果是三个模型的总和

注意这个过程中，没有「投票」环节，每个模型的结果都以加总的方式用在了最终的结果中。
三、XGBoost 的核心算法推导

为什么 XGBoost 这几年这么流行呢？

原因一：比起其他的算法，实际效果好；
原因二：算法可以并行，训练效率高；
原因三：可控参数多，可以灵活调整。

接下来的学习流程：



XGBoost 的学习路径

1. 如何构造目标函数？

在 Gradient Boosting 的框架下，使用 k 棵树来预测的最终预测结果就为 k 棵树预测结果之和：


则 XGBoost 的目标函数由以下两部分组成：损失函数和正则项之和。
比如对于二分类问题，损失函数是交叉熵损失函数（Cross-Entropy Loss）。


叠加式训练：梯度提升树是一个叠加的过程，那么训练第 k 棵树的目标函数是什么呢？
首先我们必须清楚，第 k 棵树输出的预测结果是\hat{y_i}^{(k)} ，它是前 k-1 棵树的预测结果 \hat{y_i}^{(k-1)}  加上自己的预测结果 f_k(x_i) 计算得出。
那么训练第 k 棵树的目标函数即是预测结果 \hat{y_i}^{(k)} 和真实结果 y_i 的损失函数加上第 k 棵树 f_k(x_i) 的复杂度。
目标函数推导过程如下：



第 k 棵树目标函数的推导过程。重点理解它和 k-1 棵树的递推关系。

这样我们就表示了第 k 棵树的目标函数：



第 k 棵树目标函数，还是所有样本点的 loss 之和 + 第 k 棵树的正则项

那接下来我们要怎么优化呢？
很大的挑战在于，这个目标函数有可能并不是一个全局连续函数，例如 MSE。
2. 目标函数直接优化难，如何近似？

我们熟悉的 LR 逻辑回归可以用 GD 梯度下降法的方式优化。但是 XGBoost 的目标函数可能并不连续，所以很难直接优化。
XGBoost 算法把这个令人头疼的目标函数做了近似 —— 泰勒展开。
让我们先回顾一下泰勒展开的公式：

泰勒公式得名于英国数学家布鲁克·泰勒，他在1712年的一封信里首次叙述了这个公式。泰勒公式是为了研究复杂函数性质时经常使用的近似方法之一，也是函数微分学的一项重要应用内容。

它是一个用函数在某点的信息描述其附近取值的公式。如果函数满足一定的条件，泰勒公式可以用函数在某一点的各阶导数值做系数构建一个多项式来近似表达这个函数 。
泰勒公式完整定义如下：



泰勒公式的定义

换句话一言以蔽之：对于复杂函数，想要知道某个点附近的取值，除了直接代入原函数求，可以利用泰勒级数通过原函数在这个点的一/二阶导数构建多项式，从而近似这个点的取值。

那么如何将泰勒级数用在训练 XGBoost 第 k 棵树的目标函数中呢？
精彩的推理过程如下：



泰勒级数如何让 XGBoost 的目标函数引入梯度（更准确来说是偏导数）

其中 gi 和 hi 是损失函数的一阶导数和二阶导数，而又因为在训练第 k 棵树的时候，已经知道它们的取值是多少了，因而可以被看作是常数项！
从而得到的改写后目标函数如下：



引入泰勒二阶展开公式后的 XGBoost 目标函数

3. 如何把树的结构引入目标函数？

分辨了已知信息和未知信息之后，接下来我们就要想方设法把树的结构参数化，这样才能优化：

• 用数学语言参数化第 k 棵树的输出结果 f_t(x_i) ？
  
• 以及如何参数化树的复杂度 \Omega f(t) ？
  

首先考虑如何定义一棵树：
这里需要定义3个变量：

• 表示叶节点取值的 w ；
  
• 表示样本 x 位置的 q(x)
  
• 表示第 j  个叶子结点包含哪些 x 索引 i 的集合 I_j 。
  

然后考虑如何表示树的复杂度：
假设已经知道了一棵树的形状，那么我们如何衡量树的复杂度呢？
用叶节点个数？
用树的深度？
还是用叶节点值？
在 XGBoost 中，用两个指标之和来表示树的复杂度：叶节点的个数 + 叶节点的值的平方和。



树的复杂度度量公式：叶节点的个数 + 叶节点的值的平方和，各自有系数

新的目标函数，最优解和推导过程：
这个过程实在是太精彩啦！
假设：我们已经知道了树的形状。
先用 w_{q(x)} 来表示树模型的预测结果 f_t(x_i) ；
而由于下标各不相同，不方便合并同类项表示（因为同一个叶子结点的取值是一样的），我们使用 I_j 来表示第 j 个叶子结点包含哪些 x  的索引  i 。这样对于每一个叶子结点 j ，我们只需要将其包含的样本的 g_i  加总，然后再一起乘该叶子结点的取值 w_j就可以了。
而得到系数 \sum_{i \in I_j}g_i 和 \sum_{i \in I_j}h_i 都是与待优化的 w_j 无关的常数！
是不是非常妙！
此时我们还能将树的复杂度的其中一部分合并进来。
这样我们的新目标函数就可以表示为和待优化参数 w_j 有关的一元二次函数，可以使用高中学的最优解公式 w_j^* = -\frac{b}{2a} 来求解，得到：
w_j^* = -\frac{G_i}{H_j + \lambda}
Obj^* = -\frac{1}{2}\sum_{j=1}^T\frac{G_j^2}{H_j+\lambda}+\gamma T
也就是说，在树的形状已知的情况下，是可以得到最优参数 w_j ，即最优的叶子结点取值的。从而也就求得了情况的目标函数最优取值。




新的目标函数，最优解和推导过程，非常精彩

在树的形状已知时，我们很容易就能得到目标函数的最优解。我们可以创建各种形状的树来重复这个过程，但是要如何才能找到使得目标函数最小的那棵树呢？



可以生成 k 种不同形状的树，每一棵树我们都可以算出这个形状下最优的目标函数值

4. 如何获得最优结构的树？贪心算法

如何找到形状最好的树呢？这是一个 NP-hard 问题，与特征数量是指数级的关系。
因此先回顾一下决策树的生成方式 —— 因为优化目标是最小化熵（不确定性），因此利用分裂前后树的熵值之差来表示信息增益来选择分裂点。这个过冲是用贪心算法来迭代的，每次分裂使用当前最好的方式分割。
在 XGBoost 的树形状选取过程中，唯一的区别就是，用之前定义的目标函数 Obj  来取代决策树的熵，从而最小化目标函数。妙！


这里举一个具体的例子来展示这个过程：
每一层叶子结点的生成，是为了最大化新树的 Obj  和老树的 Obj  之差。


分裂原则依据的公式，我们要找使得这个 L_{split}  最大的特征分裂点：


至此 XGBoost 的核心原理总结完毕。