程序员学长

2023-12-27 23:34 北方工业大学大数据开发工程师

关注

Xgboost，史上最强面试总结

今天，来分享机器学习面试题之Xgboost 算法。

到目前为止，我们已经更新了九大算法，包含 74 个数据点。

常考面试题

什么是 XGBoost？

GBDT 和 XGBoost 的区别？

XGBoost 如何评价特征的重要性？

XGBoost 为什么可以并行训练？

XGBoost 为什么快

XGBoost 算法的优缺点？

面试题详解

什么是 XGBoost？

XGBoost（eXtreme Gradient Boosting）是一个高效的机器学习算法，常用于分类和回归任务。XGBoost 对 GBDT 进行了一系列优化，比如损失函数进行了二阶泰勒展开、目标函数加入正则项、支持并行和默认缺失值处理等，在可扩展性和训练速度上有了巨大的提升。

算法原理

XGBoost 遵从 Boosting 的加法模型架构，其在结构上可表示为

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

其中， k 是基模型的个数， $f_k$ 是基学习器（一般是CART）， $\hat{y}_i$ 是第 i 个样本的预测值。

带正则化项的目标函数

Xgboost 的损失函数如下所示：

$Obj = \sum_{i=1}^{n} l(\hat{y}_i, y_i) + \sum_{t=1}^{k} \Omega(f_t)$

其中， $\Omega(f_t)$ 是正则化项，由于 XGBoost 支持决策树也支持线性模型，所以这里再不展开描述。

我们知道 boosting 模型是加法模型架构，以第 t 步的模型为例，模型对第 i 个样本 $x_i$ 的预测为：

$\hat{y}_i^t = \hat{y}_i^{t-1} + f_t(x_i)$

其中 $\hat{y}_i^{t-1}$ 由第 t−1 步的模型给出的预测值，是已知常数， $f_t(x_i)$ 是我们这次需要加入的新模型的预测值，此时，目标函数就可以写成：

$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)) + \sum_{i=1}^{t} \Omega(f_i)$

求此时最优化目标函数，就相当于求解 $f_t(x_i)$

泰勒公式：若函数 $f(x)$ 在包含 $x_0$ 的某个闭区间 $[a,b]$ 上具有 n 阶导数，且在开区间 $(a,b)$ 上具有 n+1 阶导数，则对闭区间 $[a,b]$ 上任意一点 $x$ 有 $f(x) = \sum_{i=0}^{n} \frac{f^{(i)}(x_0)}{i!} (x - x_0)^i + R_n(x)$ ，其中 $R_n(x)$ 是泰勒公式的余项。

根据泰勒公式，我们把函数 $f(x+\Delta x)$ 在点 x 处进行泰勒的二阶展开，可得到如下等式：

$f(x + \Delta x) \approx f(x) + f'(x)\Delta x + \frac{1}{2}f''(x)\Delta x^2$

我们把 $\hat{y}_i^{t-1}$ 视为 $x$ ， $f_t(x_i)$ 视为 $\Delta x$ ，故可以将目标函数写为：

$Obj^{(t)} = \sum_{i=1}^{n} \left[ l(y_i, \hat{y}_i^{t-1}) + g_i f_t(x_i) + \frac{1}{2} h_i f_t^2(x_i) \right] + \sum_{i=1}^{t} \Omega(f_i)$

其中 $g_i$ 为损失函数的一阶导， $h_i$ 为损失函数的二阶导，注意这里的导是对 $\hat{y}_i^{t-1}$ 求导。

我们以平方损失函数为例

$\sum_{i=1}^{n} (\hat{y}_i^{t-1} + f_t(x_i) - y_i)^2$

则：

$g_i = \frac{\partial (\hat{y}_i^{t-1} - y_i)^2}{\partial \hat{y}_i^{t-1}} = 2(\hat{y}_i^{t-1} - y_i)$

$h_i = \frac{\partial^2 (\hat{y}_i^{t-1} - y_i)^2}{\partial (\hat{y}_i^{t-1})^2} = 2$

由于在第 t 步时， $\hat{y}_i^{t-1}$ 其实是一个已知的值，所以 $l(y_i, \hat{y}_i^{t-1})$ 是一个常数，其对函数的优化不会产生影响，因此目标函数可以写成：

$Obj^{(t)} \approx \sum_{i=1}^{n} \left[ g_i f_t(x_i) + \frac{1}{2} h_i f_t^2(x_i) \right] + \sum_{i=1}^{t} \Omega(f_i)$

所以我们只需要求出每一步损失函数的一阶导和二阶导的值（由于前一步的 $\hat{y}_i^{t-1}$ 是已知的，所以这两个值就是常数），然后最优化目标函数，就可以得到每一步的 $f(x)$ ，最后根据加法模型得到一个整体模型。

基于决策树的目标函数

我们知道 Xgboost 的基模型不仅支持决策树，还支持线性模型，这里我们主要介绍基于决策树的目标函数。

我们可以将决策树定义为 $f_t(x)=w_{q(x)}$ ，其中 x 为某一样本，这里的 $q(x)$ 代表了该样本在哪个叶子结点上，而 $w_q$ 代表了叶子结点取值 $w$ ，所以 $w_{q(x)}$ 就代表了每个样本的取值 $w$ （即预测值）。

决策树的复杂度可由叶子数 $T$ 组成，叶子节点越少模型越简单，此外叶子节点也不应该含有过高的权重 $w$ （类比 LR 的每个变量的权重），所以目标函数的正则项可以定义为：

$\Omega(f_t) = \gamma T + \frac{1}{2} \lambda \sum_{j=1}^{T} w_j^2$

这张图给出了基于决策树的 XGBoost 的正则项的求解方式。

我们设 $I_j = \{i | q(x_i) = j\}$ 为第 j 个叶子节点的样本集合，故我们的目标函数可以写成：

$Obj^{(t)} \approx \sum_{i=1}^{n} \left[ g_i f_t (x_i) + \frac{1}{2} h_i f_t^2 (x_i) \right] + \Omega(f_t) \\ = \sum_{i=1}^{n} \left[ g_i w_{q(x_i)} + \frac{1}{2} h_i w_{q(x_i)}^2 \right] + \gamma T + \frac{1}{2} \lambda \sum_{j=1}^{T} w_j^2 \\ = \sum_{j=1}^{T} \left[ \left( \sum_{i \in I_j} g_i \right) w_j + \frac{1}{2} \left( \sum_{i \in I_j} h_i + \lambda \right) w_j^2 \right] + \gamma T$

第二步是遍历所有的样本后求每个样本的损失函数，但样本最终会落在叶子节点上，所以我们也可以遍历叶子节点，然后获取叶子节点上的样本集合，最后在求损失函数。即我们之前样本的集合，现在都改写成叶子结点的集合，由于一个叶子结点有多个样本存在，因此才有了 $\sum_{i \in I_j} g_i$ 和 $\sum_{i \in I_j} h_i$ ， $w_j$ 为第 $j$ 个叶子节点取值。

为简化表达式，我们定义 $G_j = \sum_{i \in I_j} g_i, \quad H_j = \sum_{i \in I_j} h_i$ ，则目标函数为：

$Obj^{(t)} = \sum_{j=1}^{T} \left[ G_j w_j + \frac{1}{2} (H_j + \lambda) w_j^2 \right] + \gamma T$

这里我们要注意 $G_i$ 和 $H_j$ 是前 t−1 步得到的结果，其值已知，可将其视为常数，只有最后一棵树的叶子节点 $w_j$ 不确定，那么将目标函数对 $w_j$ 求一阶导，并令其等于 0 ，则可以求得叶子结点 $w_j$ 对应的权值：

$w_j^* = - \frac{G_j}{H_j + \lambda}$

所以目标函数可以化简为：

$Obj = - \frac{1}{2} \sum_{j=1}^{T} \frac{G_j^2}{H_j + \lambda} + \gamma T$

上图给出目标函数计算的例子，求每个节点每个样本的一阶导数 $g_i$ 和二阶导数 $h_i$ ，然后针对每个节点对所含样本求和得到的 $G_i$ 和 $H_i$ ，最后遍历决策树的节点即可得到目标函数。

最优切分点划分算法

在决策树的生长过程中，一个非常关键的问题是如何找到节点的最优切分点，Xgboost 支持两种分裂节点的方法，贪心算法和近似算法。

贪心算法

从深度为 0 的树开始，对每个叶节点枚举所有的可用特征
针对每个特征，把属于该节点的训练样本根据该特征值进行升序排列，通过线性扫描的方式来决定该特征的最佳分裂点，并记录该特征的分裂收益
选择收益最大的特征作为分裂特征，用该特征的最佳分裂点作为分裂位置，在该节点上分裂出左右两个新的叶节点，并为每个新节点关联对应的样本集
回到第 1 步，递归执行到满足特定条件为止

那么如何计算每个特征的分裂收益呢？

假设我们在某一节点完成特征分裂，则分列前的目标函数可以写为：

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

分裂后的目标函数为：

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

则对于目标函数来说，分裂后的收益为：

$\text{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$

注意该特征收益也可作为特征重要性输出的重要依据。

对于每次分裂，我们都需要枚举所有特征可能的分割方案，如何高效地枚举所有的分割呢？

我假设我们要枚举所有 x<a 这样的条件，对于某个特定的分割点 a 我们要计算 a 左边和右边的导数和。

可以发现对于所有的分裂点 a ，只要做一遍从左到右的扫描就可以枚举出所有分割的梯度和 $G_L$ 和 $G_R$ 。

观察分裂后的收益，我们会发现节点划分不一定会使得结果变好，因为我们有一个引入新叶子的惩罚项，也就是说引入的分割带来的增益如果小于一个阀值的时候，我们可以剪掉这个分割。

近似算法

贪婪算法可以得到最优解，但当数据量太大时则无法读入内存进行计算，近似算法主要针对贪婪算法这一缺点给出了近似最优解。

对于每个特征，只考察分位点就可以减少计算复杂度。

该算法首先根据特征分布的分位数提出候选划分点，然后将连续型特征映射到由这些候选点划分的桶中，然后聚合统计信息找到所有区间的最佳分裂点。

在提出候选切分点时有两种策略：

Global，学习每棵树前就提出候选切分点，并在每次分裂时都采用这种分割。
Local，每次分裂前将重新提出候选切分点。

直观上来看，Local 策略需要更多的计算步骤，而 Global 策略因为节点没有划分所以需要更多的候选点。

下图给出不同种分裂策略的 AUC 变换曲线，横坐标为迭代次数，纵坐标为测试集 AUC，eps 为近似算法的精度，其倒数为桶的数量。

我们可以看到 Global 策略在候选点数多时（eps 小）可以和 Local 策略在候选点少时（eps 大）具有相似的精度。此外我们还发现，在 eps 取值合理的情况下，分位数策略可以获得与贪婪算法相同的精度。

下图给出近似算法的具体例子，以三分位为例：

找到其中最大的信息增量的划分方法。

$\text{Gain} = \max \left\{ \text{Gain}, \frac{G_1^2}{H_1 + \lambda} + \frac{G_{23}^2}{H_{23} + \lambda} - \frac{G_{123}^2}{H_{123} + \lambda} - \gamma, \frac{G_{12}^2}{H_{12} + \lambda} + \frac{G_3^2}{H_3 + \lambda} - \frac{G_{123}^2}{H_{123} + \lambda} - \gamma \right\}$

根据样本特征进行排序，然后基于分位数进行划分，并统计三个桶内的 $G,H$ 值，最终求解节点划分的增益。

加权分位数

事实上， XGBoost 不是简单地按照样本个数进行分位，而是以二阶导数值 $h$ 作为样本的权重进行划分，如下：

假设

$D_k = \{ (x_{1k}, h_1), (x_{2k}, h_2), \ldots, (x_{nk}, h_n) \}$

表示所有样本的第 k 个特征值及二阶导数。

则可以定义一个排序函数如下，该排序函数的输入为某个特征值 z，计算的是该特征所有可取值中小于 z 的特征值的总权重占总的所有可取值的总权重和的比例，输出为一个比例值，变化范围由0到1。

$r_k(z) = \frac{1}{\sum_{(x,h) \in D_k} h} \sum_{\substack{(x,h) \in D_k \\ x < z}} h$

该函数表示特征值 k 小于 z 的实例比例。目标就是寻找候选分裂点集 $\{s_{k1}, s_{k2}, ..., s_{kl}\}$ 。希望得到的分位点满足如下条件：

$\| r_k(s_{k,j}) - r_k(s_{k,j+1}) \| < \epsilon, s_{k1} = \min_i x_{ik}, s_{kl} = \max_i x_{ik}$

$s_{k1}$ 是特征 k 的取值中最小的值 $x_{ik}$ ， $s_{kl}$ 是特征 k 的取值中最大的值 $x_{nk}$ ，这是分位数缩略图要求需要保留原序列中的最小值和最大值。这里 $\epsilon$ 是近似因子或者说是扫描步幅，按照步幅 $\epsilon$ 挑选出特征 k 的取值候选点，组成候选点集。这意味着大概有 $1/\epsilon$ 个分位点。

那么问题来了，为什么要用 $ℎ_i$ 进行样本加权？

我们知道模型的目标函数为：

$Obj^{(t)} \approx \sum_{i=1}^{n} \left[ g_i f_t (x_i) + \frac{1}{2} h_i f_t^2 (x_i) \right] + \sum_{i=1}^{t} \Omega(f_i)$

我们稍作整理，便可以看出 $h_i$ 有对 loss 加权的作用。

$Obj^{(t)} \approx \sum_{i=1}^{n} \left[ g_i f_t (x_i) + \frac{1}{2} h_i f_t^2 (x_i) \right] + \sum_{i=1}^{t} \Omega(f_i)$

$= \sum_{i=1}^{n} \left[ g_i f_t (x_i) + \frac{1}{2} h_i f_t^2 (x_i) + \frac{1}{2} \frac{g_i^2}{h_i} \right] + \Omega(f_t) + C$

$= \sum_{i=1}^{n} \frac{1}{2} h_i \left[ f_t (x_i) - \left( - \frac{g_i}{h_i} \right) \right]^2 + \Omega(f_t) + C$

其中 $\frac{1}{2} \frac{g_i^2}{h_i}$ 与 $C$ 皆为常数。我们可以看到 $ℎ_i$ 就是平方损失函数中样本的权重。

稀疏感知算法

XGBoost 在构建树的节点过程中只考虑非缺失值的数据遍历，而为每个节点增加了一个缺省方向，当样本相应的特征值缺失时，可以被归类到缺省方向上，最优的缺省方向可以从数据中学到。至于如何学到缺省值的分支，其实很简单，分别枚举特征缺省的样本归为左右分支后的增益，选择增益最大的枚举项即为最优缺省方向。

在构建树的过程中需要枚举特征缺失的样本，乍一看该算法的计算量增加了一倍，但其实该算法在构建树的过程中只考虑了特征未缺失的样本遍历，而特征值缺失的样本无需遍历只需直接分配到左右节点，故算法所需遍历的样本量减少，下图可以看到稀疏感知算法比 basic 算法速度快了超过 50 倍。

一个案例

from sklearn.datasets import fetch_california_housing
from sklearn.model_selection import train_test_split
from sklearn.metrics import mean_squared_error
import xgboost as xgb

# 1. 加载加州房屋数据集
california_housing = fetch_california_housing()
X, y = california_housing.data, california_housing.target

# 2. 划分数据集为训练集和测试集
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42)

# 3. 初始化 XGBoost 回归模型
xg_reg = xgb.XGBRegressor(objective='reg:squarederror', colsample_bytree=0.3, learning_rate=0.1,
                          max_depth=5, alpha=10, n_estimators=100)

# 4. 训练模型
xg_reg.fit(X_train, y_train)

# 5. 对测试集进行预测
y_pred = xg_reg.predict(X_test)

# 6. 评估模型性能
rmse = mean_squared_error(y_test, y_pred, squared=False)
rmse

GBDT和XGBoost的区别？

基分类器：传统的 GBDT 采用 CART 作为基分类器，XGBoost 支持多种类型的基分类器，比如线性分类器。
二阶导数：GBDT 在模型训练时只使用了代价函数的一阶导数信息，XGBoost 对代价函数进行二阶泰勒展开，可以同时使用一阶和二阶导数。
正则项：在使用 CART 作为基分类器时，XGBoost 显式地加入了正则项来控制模型的复杂度，有利于防止过拟合，从而提高模型的泛化能力。
列采样：传统的 GBDT 在每轮迭代时使用全部的数据，XGBoost 则采用了与随机森林相似的策略，支持对数据进行采样，支持列抽样，不仅能降低过拟合，还能减少计算，这也是xgboost异于传统gbdt的一个特性。
缺失值处理：传统的GBDT没有设计对缺失值进行处理，XGBoost可以为缺失值或者特定值指定分支的默认方向，对特征值有缺失的样本可以自动学习出他的分裂方向。
并行化：XGBoost 支持并行，可以在特征粒度上并行，在训练前对特征进行分块排序，在寻找最佳分裂点的时候可以并行化计算，大大提升速度。
Shrinkage（缩减）：相当于学习速率（xgboost 中的 eta）。xgboost 在进行完一次迭代后，会将叶子节点的权重乘上该系数，主要是为了削弱每棵树的影响，让后面有更大的学习空间。实际应用中，一般把 eta 设置得小一点，然后迭代次数设置得大一点（注意，传统 GBDT 的实现也有学习速率）。

XGBoost 如何评价特征的重要性？

采用三种方法来评判 XGBoost 模型中特征的重要程度。

weight ：该特征在所有树中被用作分割样本的特征的总次数。
gain：该特征在其出现过的所有树中产生的平均增益。
cover ：该特征在其出现过的所有树中的平均覆盖范围。

注意：覆盖范围这里指的是一个特征用作分割点后，其影响的样本数量，即有多少样本经过该特征分割到两个子节点。

XGBoost 为什么可以并行训练？

XGBoost 的并行，并不是说每棵树可以并行训练，XGB 本质上仍然采用 boosting 思想，每棵树训练前需要等前面的树训练完成才能开始训练。
XGBoost 的并行，指的是特征维度的并行，在训练之前，每个特征按特征值对样本进行预排序，并存储为 Block 结构，在后面查找特征分割点时可以重复使用，而且特征已经被存储为一个个 block 结构，那么在寻找每个特征的最佳分割点时，可以利用多线程对每个block并行计算。

XGBoost 为什么快？

分块并行在建树的过程中，最耗时的一个步骤就是在每次寻找最佳分裂点是都需要对特征的值进行排序。而 XGBoost 在训练之前，根据特征对数据进行了排序，然后保存到块结构中，并在每个块结构中都采用了稀疏矩阵存储格式（Compressed Sparse Columns Format，CSC）进行存储，后面的训练过程中会重复地使用块结构，可以大大减小计算量。每一个块结构包括一个或多个已经排序好的特征；缺失特征值将不进行排序；每个特征会存储指向样本梯度统计值的索引，方便计算一阶导和二阶导数值；这种块结构存储的特征之间相互独立，方便计算机进行并行计算。在对节点进行分裂时需要选择增益最大的特征作为分裂，这时各个特征的增益计算可以同时进行，这也是 Xgboost 能够实现分布式或者多线程计算的原因。
候选分位点：每个特征采用常数个分位点作为候选分割点
CPU 缓存命中优化块结构的设计可以减少节点分裂时的计算量，但特征值通过索引访问样本梯度统计值的设计会导致访问操作的内存空间不连续，这样会造成缓存命中率低，从而影响到算法的效率。为了解决缓存命中率低的问题，XGBoost 提出了缓存访问优化算法，为每个线程分配一个连续的缓存区，将需要的梯度信息存放在缓冲区中，这样就是实现了非连续空间到连续空间的转换，提高了算法效率。此外适当调整块大小，也可以有助于缓存优化。
Block 处理优化：Block预先放入内存；Block按列进行解压缩；将 Block 划分到不同硬盘来提高吞吐

XGBoost 的优缺点有哪些？

优点

精度更高：GBDT 只用到一阶泰勒展开，而 XGBoost 对损失函数进行了二阶泰勒展开。XGBoost 引入二阶导一方面是为了增加精度，另一方面也是为了能够自定义损失函数；
灵活性更强：GBDT 以 CART 作为基分类器，XGBoost 不仅支持 CART 还支持线性分类器。
正则化：XGBoost 在目标函数中加入了正则项，用于控制模型的复杂度。正则项里包含了树的叶子节点个数、叶子节点权重的 L2 范式。正则项降低了模型的方差，使学习出来的模型更加简单，有助于防止过拟合；
Shrinkage（缩减）：相当于学习速率。XGBoost 在进行完一次迭代后，会将叶子节点的权重乘上该系数，主要是为了削弱每棵树的影响，让后面有更大的学习空间；
列抽样：XGBoost 借鉴了随机森林的做法，支持列抽样，不仅能降低过拟合，还能减少计算；
缺失值处理：XGBoost 采用的稀疏感知算法极大的加快了节点分裂的速度；
可以并行化操作：块结构可以很好的支持并行计算。

缺点