提升树简介

XGBoost 代表着“极限梯度提升”，其中“梯度提升”一词源自 Friedman 的论文 Greedy Function Approximation: A Gradient Boosting Machine。

梯度提升树一词已经存在了一段时间，关于这个主题有很多资料。本教程将使用监督学习的要素，以一种自包含且有原则的方式解释提升树。我们认为这种解释更清晰、更正式，并能激发 XGBoost 中使用的模型公式。

监督学习的要素

XGBoost 用于监督学习问题，其中我们使用训练数据（具有多个特征）\(x_i\) 来预测目标变量 \(y_i\)。在我们具体学习树之前，让我们先回顾一下监督学习中的基本要素。

模型与参数

监督学习中的模型通常指从输入 \(x_i\) 预测 \(y_i\) 的数学结构。一个常见的例子是线性模型，其中预测值由加权输入特征的线性组合 \(\hat{y}_i = \sum_j \theta_j x_{ij}\) 给出。预测值可以根据任务（即回归或分类）有不同的解释。例如，它可以进行逻辑变换以获得逻辑回归中正类的概率，当我们需要对输出进行排序时，它也可以用作排序得分。

参数是我们从数据中需要学习的未确定部分。在线性回归问题中，参数是系数 \({\theta}\)。通常我们将使用 \({\theta}\) 来表示参数（一个模型中有很多参数，这里的定义比较粗略）。

目标函数：训练损失 + 正则化

通过对 \(y_i\) 进行合理的选择，我们可以表达各种任务，例如回归、分类和排序。模型的训练任务在于找到最适合训练数据 \(x_i\) 和标签 \(y_i\) 的最佳参数 \({\theta}\)。为了训练模型，我们需要定义目标函数来衡量模型对训练数据的拟合程度。

目标函数的一个显著特征是它们由两部分组成：训练损失和正则化项

\[\text{obj}(\theta) = L(\theta) + \Omega(\theta)\]

其中 \(L\) 是训练损失函数，而 \(\Omega\) 是正则化项。训练损失衡量模型对训练数据的预测能力。常用的 \(L\) 选择是均方误差，其表达式为

\[L(\theta) = \sum_i (y_i-\hat{y}_i)^2\]

另一个常用的损失函数是逻辑损失，用于逻辑回归

\[L(\theta) = \sum_i[ y_i\ln (1+e^{-\hat{y}_i}) + (1-y_i)\ln (1+e^{\hat{y}_i})]\]

正则化项是人们经常忘记添加的部分。正则化项控制模型的复杂度，有助于我们避免过拟合。这听起来有点抽象，所以让我们考虑下图所示的问题。你被要求根据图片左上角的输入数据点，目测拟合一个阶梯函数。你认为这三种解决方案中哪种是最好的拟合？

正确答案已用红色标记。请考虑这在视觉上是否对你来说是一个合理的拟合。一般原则是，我们既希望模型简单又希望它具有预测性。两者之间的权衡在机器学习中也称为偏差-方差权衡。

为什么要介绍一般原则？

上面介绍的要素构成了监督学习的基本要素，它们是机器学习工具包的天然组成部分。例如，你应该能够描述梯度提升树和随机森林之间的差异和共同点。以形式化的方式理解这个过程也有助于我们理解正在学习的目标以及修剪和平滑等启发式方法的背后原因。

决策树集成

现在我们已经介绍了监督学习的要素，让我们开始学习真正的树。首先，让我们了解一下 XGBoost 的模型选择：决策树集成。树集成模型由一组分类回归树 (CART) 组成。这是一个简单的 CART 示例，它分类某人是否会喜欢一个假设的电脑游戏 X。

我们将家庭成员分类到不同的叶子节点，并为他们分配相应叶子节点上的得分。CART 与决策树略有不同，决策树的叶子节点只包含决策值。在 CART 中，每个叶子节点都关联着一个真实得分，这为我们提供了超越分类的更丰富的解释。这也为优化提供了一种有原则、统一的方法，我们将在本教程的后面部分看到。

通常，单个树不足以在实践中使用。实际使用的是集成模型，它将多棵树的预测结果相加。

这是一个包含两棵树的树集成示例。每棵单个树的预测得分被加起来得到最终得分。如果你看这个例子，一个重要的事实是这两棵树试图互相补充。在数学上，我们可以将模型写成以下形式

\[\hat{y}_i = \sum_{k=1}^K f_k(x_i), f_k \in \mathcal{F}\]

其中 \(K\) 是树的数量，\(f_k\) 是函数空间 \(\mathcal{F}\) 中的一个函数，而 \(\mathcal{F}\) 是所有可能的 CART 的集合。需要优化的目标函数由下式给出

\[\text{obj}(\theta) = \sum_i^n l(y_i, \hat{y}_i) + \sum_{k=1}^K \omega(f_k)\]

其中 \(\omega(f_k)\) 是树 \(f_k\) 的复杂度，后面会详细定义。

现在来一个刁钻的问题：随机森林中使用的模型是什么？是树集成！所以随机森林和提升树本质上是相同的模型；区别在于我们如何训练它们。这意味着，如果你为树集成编写一个预测服务，你只需要编写一个，它应该同时适用于随机森林和梯度提升树。(请参阅 Treelite 了解实际示例。) 这是监督学习要素之所以强大的一个例子。

树提升

现在我们已经介绍了模型，接下来谈谈训练：我们应该如何学习这些树？答案是，就像所有监督学习模型一样：定义一个目标函数并对其进行优化！

设以下是目标函数（记住它总是需要包含训练损失和正则化）

\[\text{obj} = \sum_{i=1}^n l(y_i, \hat{y}_i^{(t)}) + \sum_{k=1}^t\omega(f_k)\]

其中 \(t\) 是我们集成中的树的数量。（每个训练步骤都会添加一棵新树，因此在第 \(t\) 步，集成包含 \(K=t\) 棵树）。

加法训练

我们想问的第一个问题是：树的参数是什么？你会发现我们需要学习的是那些函数 \(f_k\)，每个函数包含树的结构和叶子节点的得分。学习树结构比你可以简单地求梯度的传统优化问题要难得多。一次性学习所有树是不可行的。相反，我们采用加法策略：固定我们已经学到的，然后一次添加一棵新树。我们将第 \(t\) 步的预测值记为 \(\hat{y}_i^{(t)}\)。那么我们有

\[\begin{split}\hat{y}_i^{(0)} &= 0\\ \hat{y}_i^{(1)} &= f_1(x_i) = \hat{y}_i^{(0)} + f_1(x_i)\\ \hat{y}_i^{(2)} &= f_1(x_i) + f_2(x_i)= \hat{y}_i^{(1)} + f_2(x_i)\\ &\dots\\ \hat{y}_i^{(t)} &= \sum_{k=1}^t f_k(x_i)= \hat{y}_i^{(t-1)} + f_t(x_i)\end{split}\]

还有一个问题要问：在每一步我们想要哪棵树？自然而然的想法是添加一棵能够优化我们目标函数的树。

\[\begin{split}\text{obj}^{(t)} & = \sum_{i=1}^n l(y_i, \hat{y}_i^{(t)}) + \sum_{k=1}^t\omega(f_k) \\ & = \sum_{i=1}^n l(y_i, \hat{y}_i^{(t-1)} + f_t(x_i)) + \omega(f_t) + \mathrm{constant}\end{split}\]

如果我们考虑使用均方误差 (MSE) 作为损失函数，目标函数变为

\[\begin{split}\text{obj}^{(t)} & = \sum_{i=1}^n (y_i - (\hat{y}_i^{(t-1)} + f_t(x_i)))^2 + \sum_{k=1}^t\omega(f_k) \\ & = \sum_{i=1}^n [2(\hat{y}_i^{(t-1)} - y_i)f_t(x_i) + f_t(x_i)^2] + \omega(f_t) + \mathrm{constant}\end{split}\]

MSE 的形式很友好，包含一个一阶项（通常称为残差）和一个二次项。对于其他感兴趣的损失函数（例如，逻辑损失），就不那么容易得到如此好的形式了。因此在一般情况下，我们对损失函数进行泰勒展开，展开到二阶项

\[\text{obj}^{(t)} = \sum_{i=1}^n [l(y_i, \hat{y}_i^{(t-1)}) + g_i f_t(x_i) + \frac{1}{2} h_i f_t^2(x_i)] + \omega(f_t) + \mathrm{constant}\]

其中 \(g_i\) 和 \(h_i\) 定义为

\[\begin{split}g_i &= \partial_{\hat{y}_i^{(t-1)}} l(y_i, \hat{y}_i^{(t-1)})\\ h_i &= \partial_{\hat{y}_i^{(t-1)}}^2 l(y_i, \hat{y}_i^{(t-1)})\end{split}\]

在我们移除所有常数项后，第 \(t\) 步的具体目标函数变为

\[\sum_{i=1}^n [g_i f_t(x_i) + \frac{1}{2} h_i f_t^2(x_i)] + \omega(f_t)\]

这成为我们对新树的优化目标。这个定义的一个重要优势是目标函数的值只取决于 \(g_i\) 和 \(h_i\)。这就是 XGBoost 支持自定义损失函数的方式。我们可以使用完全相同的求解器来优化包括逻辑回归和成对排序在内的所有损失函数，该求解器以 \(g_i\) 和 \(h_i\) 作为输入！

模型复杂度

我们已经介绍了训练步骤，但是等等，还有一个重要的东西，那就是正则化项！我们需要定义树的复杂度 \(\omega(f)\)。为此，让我们首先将树 \(f(x)\) 的定义细化为

\[f_t(x) = w_{q(x)}, w \in R^T, q:R^d\rightarrow \{1,2,\cdots,T\} .\]

这里 \(w\) 是叶子节点的得分向量，\(q\) 是一个将每个数据点分配到相应叶子节点的函数，而 \(T\) 是叶子节点的数量。在 XGBoost 中，我们将复杂度定义为

\[\omega(f) = \gamma T + \frac{1}{2}\lambda \sum_{j=1}^T w_j^2\]

当然，定义复杂度的方法不止一种，但这种方法在实践中效果很好。正则化是大多数树模型包处理得不太仔细或干脆忽略的一部分。这是因为传统的树学习方法只强调改善不纯度，而复杂度控制则留给了启发式方法。通过形式化地定义它，我们可以更好地理解我们在学习什么，并获得在实际中表现良好的模型。

结构得分

这是推导的神奇之处。在重新形式化树模型后，我们可以将包含第 \(t\) 棵树的目标值写为

\[\begin{split}\text{obj}^{(t)} &\approx \sum_{i=1}^n [g_i w_{q(x_i)} + \frac{1}{2} h_i w_{q(x_i)}^2] + \gamma T + \frac{1}{2}\lambda \sum_{j=1}^T w_j^2\\ &= \sum^T_{j=1} [(\sum_{i\in I_j} g_i) w_j + \frac{1}{2} (\sum_{i\in I_j} h_i + \lambda) w_j^2 ] + \gamma T\end{split}\]

其中 \(I_j = \{i|q(x_i)=j\}\) 是分配给第 \(j\) 个叶子节点的数据点的索引集合。注意，在第二行我们改变了求和的索引，因为同一叶子节点上的所有数据点都得到相同的得分。我们可以通过定义 \(G_j = \sum_{i\in I_j} g_i\) 和 \(H_j = \sum_{i\in I_j} h_i\) 来进一步压缩表达式

\[\text{obj}^{(t)} = \sum^T_{j=1} [G_jw_j + \frac{1}{2} (H_j+\lambda) w_j^2] +\gamma T\]

在这个方程中，\(w_j\) 彼此独立，形式 \(G_jw_j+\frac{1}{2}(H_j+\lambda)w_j^2\) 是二次的，对于给定的结构 \(q(x)\)，最优的 \(w_j\) 以及我们可以获得的最优目标值降低量为

\[\begin{split}w_j^\ast &= -\frac{G_j}{H_j+\lambda}\\ \text{obj}^\ast &= -\frac{1}{2} \sum_{j=1}^T \frac{G_j^2}{H_j+\lambda} + \gamma T\end{split}\]

最后一个方程衡量了树结构 \(q(x)\) 的好坏程度。

如果这一切听起来有点复杂，让我们看看这张图，并了解如何计算得分。基本上，对于给定的树结构，我们将统计量 \(g_i\) 和 \(h_i\) 推送到它们所属的叶子节点，将统计量相加，然后使用公式计算树的好坏程度。这个得分就像决策树中的不纯度度量一样，不同之处在于它也考虑了模型的复杂度。

学习树结构

现在我们有了衡量一棵树好坏程度的方法，理想情况下我们会枚举所有可能的树并选择最好的那一棵。在实践中这是不可行的，所以我们将尝试一次优化树的一个级别。具体来说，我们尝试将一个叶子节点分裂成两个叶子节点，它获得的得分是

\[Gain = \frac{1}{2} \left[\frac{G_L^2}{H_L+\lambda}+\frac{G_R^2}{H_R+\lambda}-\frac{(G_L+G_R)^2}{H_L+H_R+\lambda}\right] - \gamma\]

这个公式可以分解为：1) 新左叶子节点的得分 2) 新右叶子节点的得分 3) 原始叶子节点的得分 4) 对新增叶子节点的正则化。我们在这里可以看到一个重要事实：如果增益小于 \(\gamma\)，我们最好不要添加该分支。这正是基于树模型的修剪技术！通过运用监督学习的原理，我们可以自然地想到这些技术有效的原因 :)

对于实值数据，我们通常希望寻找最优的分裂点。为了高效地做到这一点，我们将所有实例按排序顺序排列，如下图所示。

从左到右扫描足以计算所有可能分裂方案的结构得分，我们可以高效地找到最优分裂点。

注意

加法树学习的局限性

由于枚举所有可能的树结构是不可行的，我们一次添加一个分裂。这种方法在大多数情况下效果很好，但有些边缘情况会因为这种方法而失败。对于这些边缘情况，训练结果会导致退化模型，因为我们一次只考虑一个特征维度。请参阅 梯度提升能学会简单算术吗？ 以获取示例。

关于 XGBoost 的最后几句话

现在你已经了解了什么是提升树，你可能会问，XGBoost 的介绍在哪里？XGBoost 正是一个受本教程中介绍的形式化原理启发的工具！更重要的是，它是在深入考虑了系统优化和机器学习原理后开发的。该库的目标是突破机器计算能力的极限，提供一个可扩展、可移植且准确的库。务必试用一下，最重要的是，将你的智慧（代码、示例、教程）贡献给社区！