介绍一下XGBoost
XGBoost是一款卓越的机器学习算法，它属于梯度提升树（Gradient Boosting Tree）的范畴，以其高效的运算性能、灵活的模型结构及优异的预测精度而广受推崇。它通过优化损失函数的梯度，以迭代的方式构建一系列决策树，每一步都旨在修正前序模型的残差。XGBoost不仅支持并行处理和分布式计算，还能有效处理大规模数据集和稀疏数据，适用于回归、分类及排序等多种机器学习任务。其内置的防止过拟合机制，如正则化项、自动处理缺失值等，进一步增强了模型的泛化能力，使其成为数据科学竞赛和工业应用中的常胜将军。
XGBoost的目标函数推导
XGBoost的目标函数由损失函数和正则化项两部分组成，分别解决偏差问题和方差问题。损失函数用于衡量模型的预测值与真实值之间的偏差，而正则化项则用于控制模型的复杂度，防止过拟合。
目标函数的定义
XGBoost的目标函数可以表示为：
$$ \text{Obj}(\Theta) = \sum_{i=1}^n L(y_i, \hat{y}_i) + \sum_{k=1}^{K} \Omega(f_k) $$
其中：
- $n$ 是样本的数量。
- $L(y_i, \hat{y}_i)$ 是损失函数，表示第 $i$ 个样本的预测值 $\hat{y}_i$ 与真实值 $y_i$ 之间的偏差。
- $K$ 是树的总数。
- $\Omega(f_k)$ 是第 $k$ 棵树的正则化项，用于控制模型的复杂度。
前向分步加法
XGBoost采用前向分步加法（Forward Stagewise Additive Modeling），即每次迭代只训练一棵树，并将其添加到模型中。因此，在第 $t$ 次迭代时，模型的预测值可以表示为： $$ \hat{y}_i^{(t)} = \hat{y}_i^{(t-1)} + f_t(x_i) $$ 其中：
- $\hat{y}_i^{(t-1)}$ 是前 $t-1$ 棵树的预测值，是已知的常数。
- $f_t(x_i)$ 是当前第 $t$ 棵树的预测值。
目标函数的展开
在第 $t$ 次迭代时，目标函数可以写成： $$ \text{Obj}^{(t)} = \sum_{i=1}^n L\left(y_i, \hat{y}_i^{(t)}\right) + \sum_{k=1}^t \Omega(f_k) $$
将 $\hat{y}_i^{(t)} = \hat{y}_i^{(t-1)} + f_t(x_i)$ 代入后，目标函数变为：
$$ \text{Obj}^{(t)} = \sum_{i=1}^n L\left(y_i, \hat{y}_i^{(t-1)} + f_t(x_i)\right) + \sum_{k=1}^t \Omega(f_k) $$
正则化项的拆分
由于前 $t-1$ 棵树的结构已经确定，其正则化项之和 $\sum_{k=1}^{t-1} \Omega(f_k)$ 是一个常数，可以记为 $\text{const}$。因此，目标函数可以进一步简化为： $$ \text{Obj}^{(t)} = \sum_{i=1}^n L\left(y_i, \hat{y}_i^{(t-1)} + f_t(x_i)\right) + \Omega(f_t) + \text{const} $$
泰勒展开
为了简化优化问题，XGBoost对损失函数进行二阶泰勒展开。设： $$ g_i = \frac{\partial L(y_i, \hat{y}_i^{(t-1)})}{\partial \hat{y}_i^{(t-1)}} $$ $$ h_i = \frac{\partial^2 L(y_i, \hat{y}_i^{(t-1)})}{\partial (\hat{y}_i^{(t-1)})^2} $$
- $g_i$ 是损失函数对当前预测值的一阶导数，表示样本 $i$ 的梯度
- $h_i$ 是损失函数对当前预测值的二阶导数，表示样本 $i$ 的Hessian矩阵元素，衡量梯度的变化率。
则损失函数的二阶泰勒展开为： $$ L(y_i, \hat{y}_i^{(t-1)} + f_t(x_i)) \approx L(y_i, \hat{y}_i^{(t-1)}) + g_i f_t(x_i) + \frac{1}{2} h_i f_t^2(x_i) $$ 因此，目标函数可以近似为： $$ \text{Obj}^{(t)} \approx \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] + \Omega(f_t) + \text{const} $$
最终目标函数
移除常数项 $L(y_i, \hat{y}_i^{(t-1)})$ 和 $\text{const}$，最终目标函数可以表示为： $$ \text{Obj}^{(t)} = \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) $$
采用决策树作为基模型
决策树的定义
XGBoost的基模型不仅支持决策树，还支持线性模型。本文主要介绍基于决策树的目标函数。一棵决策树可以重新定义为两部分：
- 叶子结点的权重向量 $w$：表示每个叶子结点的预测值。
- 实例（样本）到叶子结点的映射关系 $q$（树的分支结构）：将样本分配到特定的叶子结点。
定义树的复杂度
决策树的复杂度 $\Omega(f)$ 由叶子数 $T$ 和叶子结点权重的 $L2$ 范式共同决定： $$ \Omega(f) = \gamma T + \frac{1}{2} \lambda \sum_{j=1}^T w_j^2 $$ 其中：
- $T$ 是叶子结点的数量，叶子结点越少，模型越简单。
- $w_j$ 是第 $j$ 个叶子结点的权重。
- $\gamma$ 和 $\lambda$ 是超参数，用于控制正则化强度。
求叶子节点权重向量$w$
这一步的核心是，在使用决策树作为基模型，且认为树结构确定的情况下，如何找到使得目标函数$Obj$最小的叶子结点权重向量$w$
叶子结点归组
将属于第 $j$ 个叶子结点的所有样本 $x_i$ 划入到一个叶子结点的样本集合中： $$ I_j = { i \mid q(x_i) = j } $$ 然后，XGBoost的目标函数可以改写为： $$ \text{Obj}^{(t)} = \sum_{i=1}^n \left[ g_i f_t(x_i) + \frac{1}{2} h_i f_t^2(x_i) \right] + \gamma T + \frac{1}{2} \lambda \sum_{j=1}^T w_j^2 $$ 由于样本会落在叶子结点上，我们可以按照叶子结点对目标函数进行归组： $$ \text{Obj}^{(t)} = \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 $$ 为了简化表达式，定义： $$ G_j = \sum_{i \in I_j} g_i $$ $$ H_j = \sum_{i \in I_j} h_i $$ 其中：
- $G_j$ 是第 $j$ 个叶子结点所包含样本的一阶偏导数累加之和，是一个常量。
- $H_j$ 是第 $j$ 个叶子结点所包含样本的二阶偏导数累加之和，是一个常量。
将 $G_j$ 和 $H_j$ 代入目标函数，最终目标函数为： $$ \text{Obj}^{(t)} = \sum_{j=1}^T \left[ G_j w_j + \frac{1}{2} (H_j + \lambda) w_j^2 \right] + \gamma T $$
树结构打分
回忆一下一元二次函数的最值公式，对于目标函数中的每个叶子结点 $j$： $$ G_j w_j + \frac{1}{2} (H_j + \lambda) w_j^2 $$ 这是一个关于 $w_j$ 的一元二次函数，其最值点可以通过求导得到： $$ w_j = -\frac{G_j}{H_j + \lambda} $$ 将 $w_j$ 代入目标函数，目标函数的最值为： $$ \text{Obj}^{(t)} = -\frac{1}{2} \sum_{j=1}^T \frac{G_j^2}{H_j + \lambda} + \gamma T $$
求决策树的结构$q$
这一步的核心是，在使用决策树作为基模型，找到最好的那个树结构
好的！我们将 加权分位数缩略图 的知识整合到 近似算法 部分，并完整地写出 穷举法、精确贪心算法 和 近似算法 这三种方法的详细描述。
求决策树的结构 $q$
在构建决策树时，核心问题是如何找到最优的分裂点，从而确定树的结构 $q$。 最直观的方法就是穷举法，把所有的树结构枚举出来，但是这个完全不可接受。因此XGBoost把它变成分步贪婪，即每次按照增益来确定一个结点的最优划分。XGBoost 提供了两种主要方法：精确贪心算法 和 近似算法。这些方法逐步从精确但计算复杂的策略过渡到高效但近似的策略，以平衡计算效率与模型性能。
精确贪心算法（Exact Greedy Algorithm）
基本思想
精确贪心算法通过贪心策略来高效地寻找最优分裂点，而不是枚举所有可能的分裂点。它通过排序特征值，依次尝试可能的分裂点，并选择使目标函数下降最大的点。
具体步骤
- 对于每个特征 $j$，将样本按特征值排序。
- 遍历所有可能的分裂点，计算分裂后的目标函数下降量 $\text{Gain}$ $$ \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 $$ 其中： $G_L$ 和 $H_L$ 是左子节点的一阶和二阶导数之和。 $G_R$ 和 $H_R$ 是右子节点的一阶和二阶导数之和。
- 选择 $\text{Gain}$ 最大的分裂点。
- 如$max(Gain) \leq eps$时候
- 叶子结点包含样本个数小于等于1
- 可以对层级、叶子结点数做正则
近似算法（Approximate Algorithm）
基本思想
为了进一步降低计算复杂度，XGBoost 提供了近似算法。近似算法简单来说，就是根据特征 $k$ 的分布来确定 $l$ 个候选切分点 $Sk={s_{k1},s_{k2},…,s_{kl}}$ ，然后根据这些候选切分点把相应的样本放入对应的桶中，对每个桶的 $G,H$ 进行累加。最后在候选切分点集合上贪心查找。
加权分位数缩略图（Weighted Quantile Sketch）
在近似算法中，XGBoost 引入了加权分位数缩略图，将样本的二阶导数 $h_i$ 作为权重，更精确地计算特征值的分位点。
- 加权分位数的定义 给定特征 $j$ 的 $n$ 个样本及其对应的二阶导数 $h_i$，定义累积权重函数： $$ r(z) = \frac{\sum_{{i \mid x_{ij} \leq z}} h_i}{\sum_{i=1}^n h_i} $$ 其中，$x_{ij}$ 是样本 $i$ 在特征 $j$ 上的值。
- 分桶策略 根据累积权重函数 $r(z)$，将特征值划分为若干个桶（bucket）。每个桶代表一个分裂点。
- 分桶方式
- 全局分桶（Global）：在整个数据集上计算分位点。
- 局部分桶（Local）：在每个节点上重新计算分位点。
具体步骤
- 对于每个特征 $j$，使用加权分位数缩略图将特征值划分为若干个桶（bucket）。
- 对每个桶，计算一阶导数 $G$ 和二阶导数 $H$ 的累计值。
- 遍历所有可能的桶间分裂点，计算目标函数下降量 $\text{Gain}$，并选择最优的分裂点。
为什么选二阶导数做权重
以下是目标函数推导过程的重写，以更清晰地展示每一步的逻辑和数学变形：
原始目标函数如下： $$ Obj^{(t)} \simeq \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) $$
通过一系列操作，目标函数可以写成加权平方损失的形式： $$ Obj^{(t)} = \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) - \text{constant} $$ 其中，$\text{constant} = \sum_{i=1}^n \frac{1}{2} \frac{g_i^2}{h_i}$ 是一个与 $f_t$ 无关的常数项。 所以，公式上天然二阶导$h_i$具有权重的性质，自然应当按照二阶导加权
稀疏感知算法
在实际工程中，输入数据往往会出现稀疏的情况，例如数据缺失、one-hot 编码等。为了高效处理稀疏数据，XGBoost 在构建树的过程中引入了一种特殊的策略：缺省方向（Default Direction）。
缺省方向的定义
- 在构建树的每个节点时，XGBoost 会为每个特征增加一个缺省方向，用于处理特征值缺失的样本。
- 当某个样本的特征值缺失时，它会被分配到缺省方向上（左分支或右分支），从而继续参与树的构建。
如何学习最优缺省方向
- 最优缺省方向通过从数据中学习得到。具体方法如下：
- 对于当前节点的每个特征，分别枚举将缺失值样本分配到左分支和右分支的情况。
- 计算每种分配方式对应的目标函数增益（Gain），选择使增益最大的分配方式作为该特征的缺省方向。
处理稀疏数据的优势
- 减少计算量：虽然枚举缺省方向可能会增加一定的计算量，但由于 XGBoost 在树的构建过程中只遍历非缺失值的样本，缺失值样本被直接分配到缺省方向上，因此实际所需的计算量大大减少。
- 提升效率：在处理稀疏数据时，这种策略可以显著加速树的构建过程。例如，作者在 Allstate-10K 数据集上的实验表明，稀疏算法比普通算法在处理数据上快了超过 50 倍。
XGBoost的工程实现
列块并行学习
在 XGBoost 的树生成过程中，每次寻找最佳分裂点都需要对特征值进行排序，这一步骤是计算中最耗时的部分。为了优化这一过程，XGBoost 在训练前会根据特征对数据进行排序，并保存到一个块结构中。每个块结构采用稀疏矩阵存储格式（Compressed Sparse Columns Format, CSC），这种格式在后续的训练过程中可以重复使用，从而显著减少了计算量。
具体来说，作者提出了一种按特征分块并排序的方法，在块中保存排序后的特征值及对应样本的引用。这种设计使得在遍历样本特征时，能够通过顺序访问已排序的块快速找到切分点。此外，由于不同特征之间的块存储互不干涉，XGBoost 可以利用多线程同时对多个特征进行切分点查找，从而实现特征的并行化处理。在节点分裂时，算法需要选择增益最大的特征作为分裂点，而各个特征的增益计算可以同时进行，这也是 XGBoost 能够支持分布式或多线程计算的关键原因。
缓存访问优化
虽然列块并行学习的设计大大减少了节点分裂时的计算量，但在顺序访问特征值时，通过样本索引访问一阶、二阶导数时，可能会遇到内存访问不连续的问题，从而导致 CPU 缓存命中率降低，影响算法的整体效率。
为了解决这一问题，XGBoost 引入了缓存访问优化算法。具体做法是为每个线程分配一个连续的缓存区，将所需的梯度信息预先存入缓存区中。这样做实现了从非连续内存空间到连续内存空间的转换，显著提升了缓存命中率，进而提高了算法效率。此外，适当调整块的大小也有助于进一步优化缓存性能。
“核外”块计算
当处理大规模数据集时，内存容量可能无法容纳所有数据，因此必须将部分数据暂存于硬盘中，并在需要时加载进内存。然而，硬盘的 IO 操作速度远低于内存的处理速度，这会导致算法性能瓶颈。为了解决这一问题，XGBoost 提出了“核外”计算优化方法。
具体操作如下：将数据集分成多个块并存储在硬盘中，使用一个独立的线程专门从硬盘读取数据并加载到内存中。这种方式使得算法在内存中处理数据的同时，可以与硬盘读取数据并行进行，从而减少了等待时间。此外，XGBoost 还采用了两种技术来进一步降低硬盘读写的开销：
-
块压缩（Block Compression）：论文中使用了按列进行压缩的方法，读取数据时使用单独的线程进行解压。对于行索引，只保存第一个索引值，后续索引则通过 16 位整数记录与第一个索引的差值。实验表明，当块大小设置为一定的样本数时，压缩比率可达到 26% 至 29%。
-
块分区（Block Sharding）：块分区是将特征块分布存储在不同的硬盘上，通过增加硬盘 IO 的并行性来提高吞吐量。这种方法进一步优化了大规模数据集的处理效率。
XGBoost的优点
精度更高：二阶泰勒展开
XGBoost 在损失函数中引入了二阶泰勒展开，相较于 GBDT 的一阶泰勒展开，其精度更高。具体实现方式如下：
- 二阶导数的引入：损失函数在 XGBoost 中被展开为二阶泰勒公式，即： $$ \mathcal{L}(\theta) \approx \mathcal{L}(\theta_0) + \nabla \mathcal{L}(\theta_0)^\top (\theta - \theta_0) + \frac{1}{2} (\theta - \theta_0)^\top \nabla^2 \mathcal{L}(\theta_0) (\theta - \theta_0) $$ 其中，$\nabla \mathcal{L}(\theta_0)$ 是一阶导数，$\nabla^2 \mathcal{L}(\theta_0)$ 是二阶导数。
- 自定义损失函数：由于泰勒展开的存在，XGBoost 可以灵活支持多种损失函数，只要这些函数可以计算一阶和二阶导数即可。例如，对于回归问题，可以使用平方损失函数；对于分类问题，可以使用对数损失函数。
- 计算增益时的优化：在节点分裂时，XGBoost 使用二阶导数信息来计算增益。增益公式为： $$ \text{Gain} = \frac{1}{2} \left[ \frac{(\sum_{i \in I_L} g_i)^2}{\sum_{i \in I_L} h_i + \lambda} + \frac{(\sum_{i \in I_R} g_i)^2}{\sum_{i \in I_R} h_i + \lambda} - \frac{(\sum_{i \in I} g_i)^2}{\sum_{i \in I} h_i + \lambda} \right] - \gamma $$ 其中，$g_i$ 是一阶导数，$h_i$ 是二阶导数，$\lambda$ 是正则化系数，$\gamma$ 是复杂性代价。
灵活性更强：支持多种基分类器和自定义损失函数
XGBoost 的灵活性体现在其支持多种基分类器以及自定义损失函数：
- 基分类器：XGBoost 不仅支持 CART 树作为基分类器，还支持线性分类器。使用线性分类器时，XGBoost 的目标函数等同于带有 L1 和 L2 正则化项的逻辑斯蒂回归（分类问题）或线性回归（回归问题）。
- 自定义损失函数：用户可以根据需求自定义损失函数，只要该函数支持一阶和二阶导数即可。例如，对于分类问题，用户可以使用对数损失函数；对于回归问题，可以使用 Huber 损失函数。
正则化：控制模型复杂度
XGBoost 通过引入正则化项来防止过拟合，具体实现如下：
- 正则化项的定义：目标函数中加入正则化项，形式为： $$ \Omega(f) = \gamma T + \frac{1}{2} \lambda \sum_{j=1}^T w_j^2 $$ 其中，$T$ 是树的叶子节点数，$w_j$ 是叶子节点的权重，$\gamma$ 和 $\lambda$ 是正则化参数。
- 防止过拟合：正则化项限制了模型的复杂度，使得模型不会过于复杂，从而降低了方差，提高了泛化能力。
Shrinkage（缩减）：控制学习速率
XGBoost 通过 Shrinkage 来削弱每棵树的影响，具体实现如下：
- Shrinkage 参数：在每次迭代后，叶子节点的权重会乘以一个缩减系数 $\eta$（通常取值为 0.01 到 0.1）。
- 减缓学习速度：通过缩减叶子节点的权重，模型在后续迭代中有更大的学习空间，避免过早收敛到局部最优解。
列抽样：降低过拟合和计算量
XGBoost 借鉴了随机森林的列抽样方法，具体实现如下：
- 列抽样的实现：在每次分裂时，XGBoost 随机选择一部分特征进行分裂，而不是使用所有特征。
- 减少过拟合：列抽样降低了模型的方差，减少了过拟合的风险。
- 减少计算量：由于只需处理部分特征，计算量显著减少。
缺失值处理：稀疏感知算法
XGBoost 对缺失值的处理非常高效，具体实现如下：
- 自动学习分裂方向：对于缺失特征值，XGBoost 通过稀疏感知算法自动学习其分裂方向。例如，在节点分裂时，算法会分别计算将缺失值分配到左子树和右子树的增益，选择增益较大的方向。
- 优化存储结构：缺失值在存储时被标记为缺失状态，从而在计算时无需额外处理。
并行化：特征粒度的并行
XGBoost 的并行化主要体现在特征粒度的处理上，具体实现如下：
- Block 结构：XGBoost 在训练前对数据进行排序，并保存为 Block 结构。每个 Block 存储一个特征的排序值及其对应样本的索引。
- 特征并行：在节点分裂时，不同特征的计算可以并行进行。例如，使用多线程同时计算每个特征的增益，最终选择增益最大的特征作为分裂点。
可并行的近似算法：高效生成候选分割点
为了在大规模数据集或分布式环境下高效生成候选分割点，XGBoost 提出了可并行的近似算法：
- 分位数策略：XGBoost 使用分位数策略生成候选分割点，而不是枚举所有可能的分割点。例如，对每个特征的值进行分位点划分，仅在这些分位点上计算增益。
- 并行计算：多个分位点的计算可以并行进行，从而大幅提升计算效率。
- 块压缩与分区：通过块压缩和分区技术，进一步减少了硬盘 IO 的开销，使得算法在大规模数据集上也能高效运行。
XGBoost 相关思考
为什么XGBoost泰勒二阶展开后效果就比较好呢？
可扩展性：从为什么会想到引入泰勒二阶的角度来说
XGBoost官网上有说，当目标函数是MSE时，展开是一阶项（残差）+二阶项的形式，而其它目标函数，如logistic loss的展开式就没有这样的形式。为了能有个统一的形式，所以采用泰勒展开来得到二阶项，这样就能把MSE推导的那套直接复用到其它自定义损失函数上。简短来说，就是为了统一损失函数求导的形式以支持自定义损失函数。
至于为什么要在形式上与MSE统一？是因为MSE是最普遍且常用的损失函数，而且求导最容易，求导后的形式也十分简单。所以理论上只要损失函数形式与MSE统一了，那就只用推导MSE就好了。
精确性：从二阶导本身的性质去说
二阶信息本身就能让梯度收敛更快更准确。这一点在优化算法里的牛顿法中已经证实。可以简单认为一阶导指引梯度方向，二阶导指引梯度方向如何变化。简单来说，相对于GBDT的一阶泰勒展开，XGBoost采用二阶泰勒展开，可以更为精准的逼近真实的损失函数。
XGBoost对缺失值是怎么处理的？
在普通的GBDT策略中，对于缺失值的方法是先手动对缺失值进行填充，然后当做有值的特征进行处理，但是这样人工填充不一定准确，而且没有什么理论依据。而XGBoost采取的策略是先不处理那些值缺失的样本，采用那些有值的样本搞出分裂点，在遍历每个有值特征的时候，尝试将缺失样本划入左子树和右子树，选择使损失最优的值作为分裂点。
XGBoost为什么可以并行训练？
- XGBoost的并行，并不是说每棵树可以并行训练，XGBoost本质上仍然采用boosting思想，每棵树训练前需要等前面的树训练完成才能开始训练。
- XGBoost的并行，指的是特征维度的并行：在训练之前，每个特征按特征值对样本进行预排序，并存储为Block结构，在后面查找特征分割点时可以重复使用，而且特征已经被存储为一个个block结构，那么在寻找每个特征的最佳分割点时，可以利用多线程对每个block并行计算。