XGB-2: Boosted Trees（提升树）简介

用户3578099

发布于 2024-05-18 08:03:41

410

发布于 2024-05-18 08:03:41

XGBoost代表“Extreme Gradient Boosting”，其中术语“Gradient Boosting”来源于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}

。一个常见的例子是线性模型，其中预测值表

x_i

示为加权输入特征

x_i

的线性组合。预测值可以有不同的解释，取决于具体的任务，即回归或分类。例如，它可以经过逻辑变换以获得 logistic 回归中正类别的概率，并且想要对输出进行排序时，它还可以用作排名分数。

参数parameters是需要从数据中学习的未确定部分。**在线性回归问题中，参数是系数

\theta

**。通常，将

\theta

表示参数（模型中有许多参数，这里的定义有些粗略）。

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

通过对

y_i

的巧妙选择，可以表达多种任务，例如回归、分类和排名。训练模型的任务是找到最适合训练数据

x_i

和标签

y_i

的最佳参数

\theta

。为了训练模型，需要定义目标函数objective function来衡量模型对训练数据拟合的好坏。

目标函数的显著特征是由两部分组成: 训练损失和正则化项。

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

其中

是训练损失函数，

\Omega

是正则化项。训练损失度量了模型在训练数据方面的预测能力。常见的

选择是均方误差，表示为

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

另一个常用的损失函数是 logistic 损失，用于 logistic 回归：

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

正则化项是通常会忘记添加的部分，正则化项控制着模型的复杂性，有助于避免过拟合。这听起来有点抽象，因此考虑以下问题。在下面的图片中，被要求在图像的左上角给定输入数据点的情况下直观地拟合一个阶跃函数。在三个解决方案中，哪一个是最佳拟合？

在这里插入图片描述

正确答案标记为红色，总的原则是希望得到一个简单而又有预测能力的模型。在机器学习中，这两者之间的权衡也被称为偏差-方差权衡bias-variance tradeoff。

为什么介绍这个一般原则？

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

决策树集成Decision Tree Ensembles

现在已经介绍了监督学习的基本要素，下面介绍树模型。首先，首先了解XGBoost的模型选择：决策树集成decision tree ensembles。树集成模型由一组分类和回归树（CART）组成。

下面是一个简单的CART示例，用于分类某个虚构的电脑游戏 X 是否会被某人喜欢。

cart.png

将一个家庭的成员分类到不同的叶子上，并为它们分配相应叶子上的分数。CART与决策树有些不同，决策树中叶子只包含决策值。在CART中，每个叶子都关联有一个实际分数，使得能够进行超越分类的更丰富的解释。这也允许采用一个有原则的、统一的优化方法。

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

在这里插入图片描述

这是一个包含两棵树的树集成的示例。每棵树的预测分数相加以获得最终分数。这两棵树试图互补。从数学上讲，可以将模型写成以下形式：

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

其中，

是树的数量，

f_k

是特征空间

中的函数，

是所有可能的 CART 的集合。要优化的目标函数由以下公式给出：

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

其中，

\omega(f_k)

是树的复杂性。

现在有个问题：随机森林中使用的是什么模型？树集成！因此，随机森林和梯度提升树实际上是相同的模型；它们的区别在于训练的方式不同。这意味着，如果你为树集成编写一个预测服务，只需要编写一个，它应该同时适用于随机森林和梯度提升树。（有关实际示例，请参见 Treelite）这就是为什么监督学习元素如此强大的一个例子。

Tree Boosting

上述介绍了树集成模型，现在介绍训练：应该如何学习这些树呢？答案总是相同的，对于所有监督学习模型：定义一个目标函数并优化它！

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

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

加性训练Additive Training

第一个问题我们要问的是：树的参数是什么？你会发现我们需要学习的是那些包含树的结构和叶子得分的函数

f_i

。学习树的结构比传统的优化问题更难，传统优化问题中可以简单地取梯度。一次性学习所有的树是不可行的。相反，使用一种加法策略：固定已经学到的，一次添加一棵新树。将第

步的预测值写为

\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_{i=1}^t\omega(f_i) \\ & = \sum_{i=1}^n l(y_i, \hat{y}_i^{(t-1)} + f_t(x_i)) + \omega(f_t) + \mathrm{constant}\end{split}

MSE 的形式很友好，有一个一阶项（通常称为残差）和一个二次项。对于其他感兴趣的损失（例如 logistic 损失），要获得这样一个好看的形式就不那么容易。因此，在一般情况下，将损失函数进行泰勒展开，展开到二阶项：

\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}

在去除所有常数之后，第

步的具体目标函数变为：

\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 支持自定义损失函数的方式。可以使用完全相同的求解器来优化每个损失函数，包括 logistic 回归和成对排序，该求解器将

g_i

和

h_i

作为输入！

模型复杂度Model Complexity

上面已经介绍了训练步骤，下面介绍正则化项 regularization term！需要定义树的复杂性

\omega(f)

。为了做到这一点，首先细化对树

f(x)

的定义：

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

在这里，

是叶子上的分数向量，

是将每个数据点分配给相应叶子的函数，

是叶子的数量。在XGBoost中，将树的复杂性定义为：

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

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

结构分The Structure Score

在重新构建树模型后，可以将以第

个树为例的目标值写为：

\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\}

是分配给第

个叶子的数据点的索引集。请注意，在第二行中，更改了求和的索引，因为同一叶子上的所有数据点得分相同。可以通过定义

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. 新左叶子上的分数
1. 新右叶子上的分数
1. 原始叶子上的分数
1. 对额外叶子的正则化

可以看到这里一个重要的事实：如果增益小于

\gamma

，最好不要添加该分支。这正是树模型中剪枝技术的原理！通过使用监督学习的原理，可以自然地理解这些技术为什么有效。

对于实值数据，通常希望搜索最佳拆分。为了有效地进行此操作，按排序顺序放置所有实例，如下图所示。

split_find.png

从左到右的扫描足以计算所有可能的拆分解决方案的结构分数，可以有效地找到最佳拆分。

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2024-05-12，如有侵权请联系 cloudcommunity@tencent.com 删除

数据

本文分享自 AI科技时讯微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

登录后参与评论

0 条评论

热度