1. 什么是提升树算法（Boosting Tree）
提升树（Boosting Tree）是一类集成学习方法，其核心思想是：通过迭代地训练一系列弱学习器（通常是浅层决策树），每一棵树都试图纠正前一棵树的错误，最终将所有树的预测结果加权求和得到最终预测。
1.1 加法模型与前向分步算法
提升树模型可以表示为加法模型（Additive Model）：
$$ \hat{y}_i = \sum_{k=1}^{K} f_k(x_i), \quad f_k \in \mathcal{F} $$
其中，$\mathcal{F}$ 是回归树空间（CART），$K$ 是树的数量。
训练目标是最小化正则化目标函数：
$$ \mathcal{L}(\phi) = \sum_{i=1}^{n} l(\hat{y}_i, y_i) + \sum_{k=1}^{K} \Omega(f_k) $$
这里的 $\Omega(f) = \gamma T + \frac{1}{2}\lambda ||w||^2$，其中 $T$ 是叶子节点数量，$w$ 是叶子权重向量。
前向分步算法（Forward Stagewise Additive Modeling）的核心在于：在第 $t$ 轮迭代时，保持前 $t-1$ 棵树不变，仅优化第 $t$ 棵树。此时的预测值为：
$$ \hat{y}_i^{(t)} = \hat{y}_i^{(t-1)} + f_t(x_i) $$
对应的目标函数变为：
$$ \mathcal{L}^{(t)} = \sum_{i=1}^{n} l(y_i, \hat{y}_i^{(t-1)} + f_t(x_i)) + \Omega(f_t) $$
1.2 梯度提升 vs 传统提升
传统的 AdaBoost 通过调整误分类样本的权重来引导后续学习器关注困难样本。而梯度提升（Gradient Boosting）则直接从函数空间梯度下降的角度出发：每一轮新加入的树 $f_t(x)$ 被训练去拟合当前模型在损失函数上的负梯度方向。
以平方损失 $l(y_i, \hat{y}_i) = \frac{1}{2}(y_i - \hat{y}_i)^2$ 为例，第 $t$ 轮的负梯度（伪残差）为：
$$ -\frac{\partial l(y_i, \hat{y}_i^{(t-1)})}{\partial \hat{y}_i^{(t-1)}} = y_i - \hat{y}_i^{(t-1)} $$
这正是上一轮的预测残差。新树 $f_t$ 的任务就是去拟合这些残差。
但对于一般损失函数（如 LogLoss），负梯度的表达式更为复杂，且添加新树后损失函数的变化无法直接由梯度完全刻画。这就引出了 XGBoost 的核心创新之一：二阶泰勒展开近似。
2. 可扩展端到端提升树系统
陈天奇在 2016 年发表的 XGBoost 论文提出了一个端到端的可扩展提升树系统。相比传统的 GBM（Gradient Boosting Machine），XGBoost 在以下方面进行了深入优化：
2.1 正则化目标函数的二阶泰勒展开
XGBoost 使用损失函数的二阶泰勒展开来近似目标函数，这是其与 GBDT（Gradient Boosting Decision Tree）最本质的区别。
回顾第 $t$ 轮的目标函数：
$$ \mathcal{L}^{(t)} = \sum_{i=1}^{n} l(y_i, \hat{y}_i^{(t-1)} + f_t(x_i)) + \Omega(f_t) $$
在 $\hat{y}_i^{(t-1)}$ 处进行二阶泰勒展开：
$$ 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) $$
其中 $g_i = \partial_{\hat{y}^{(t-1)}} l(y_i, \hat{y}^{(t-1)})$ 是一阶梯度，$h_i = \partial^2_{\hat{y}^{(t-1)}} l(y_i, \hat{y}^{(t-1)})$ 是二阶梯度（Hessian）。
去掉常数项后，第 $t$ 轮的近似目标函数为：
$$ \tilde{\mathcal{L}}^{(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) $$
为什么二阶展开优于仅用一阶梯度？
| 方面 | 一阶梯度（GBDT） | 二阶梯度（XGBoost） |
|---|---|---|
| 优化精度 | 仅用梯度方向 | 同时利用曲率信息 |
| 步长控制 | 需要单独学习率 | Hessian 提供自适应步长 |
| 对 Hessian 的利用 | 无 | 可刻画样本”难度” |
| 分裂增益计算 | 启发式 | 有闭式解 |
2.2 叶子权重的闭式解
将 $f_t(x)$ 展开为树结构表示：对于落在叶子 $j$ 上的样本集合 $I_j = {i \mid q(x_i) = j}$，有 $f_t(x_i) = w_{q(x_i)}$，其中 $q: \mathbb{R}^d \to {1, 2, …, T}$ 是树的结构函数。
带入 $\Omega(f_t) = \gamma T + \frac{1}{2}\lambda \sum_{j=1}^{T} w_j^2$，目标函数变为：
$$ \tilde{\mathcal{L}}^{(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 $$
这是一个关于 $w_j$ 的二次函数，可求得最优叶子权重 $w_j^*$：
$$ w_j^* = -\frac{\sum_{i \in I_j} g_i}{\sum_{i \in I_j} h_i + \lambda} $$
代入后的最小损失为：
$$ \tilde{\mathcal{L}}^{(t)*} = -\frac{1}{2} \sum_{j=1}^{T} \frac{(\sum_{i \in I_j} g_i)^2}{\sum_{i \in I_j} h_i + \lambda} + \gamma T $$
这个闭式解可以用来衡量一个树结构的”好坏”，也即 结构分数（Structure Score）。
2.3 节点分裂增益
给定一个树结构，分裂一个叶子节点的增益定义为分裂前后的结构分数之差：
$$ \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 = \sum_{i \in I_L} g_i$, $H_L = \sum_{i \in I_L} h_i$（左子节点）
- $G_R = \sum_{i \in I_R} g_i$, $H_R = \sum_{i \in I_R} h_i$（右子节点）
- $\gamma$ 是分裂带来的复杂度惩罚
当 Gain 为正时分裂才有利，否则不分裂。$\gamma$ 可以看作分裂所需的最小损失减少量，起到了预剪枝的作用。
2.4 几种常见损失函数的梯度推导
平方损失（Squared Error）：
$$ l(y, \hat{y}) = \frac{1}{2}(y - \hat{y})^2 $$
$$ g_i = \hat{y}_i - y_i, \quad h_i = 1 $$
逻辑损失（Logistic Loss）：
$$ l(y, \hat{y}) = y \ln(1 + e^{-\hat{y}}) + (1-y) \ln(1 + e^{\hat{y}}) $$
令 $p_i = \frac{1}{1+e^{-\hat{y}_i}}$，则：
$$ g_i = p_i - y_i, \quad h_i = p_i (1 - p_i) $$
3. 分裂查找算法（Split Finding）
分裂查找是决策树训练中最耗时的步骤。XGBoost 提供了两种算法：精确贪心算法和近似算法。
3.1 精确贪心算法（Exact Greedy Algorithm）
对于连续特征，精确贪心算法按以下步骤进行：
Algorithm: Exact Greedy Split Finding |
该算法的时间复杂度为 $O(n \log n \times d)$（每个特征的排序开销），其中 $n$ 是样本数，$d$ 是特征数。当数据无法全部装入内存时，这种精确方法变得不可行。
3.2 近似算法（Approximate Algorithm）
为了处理大规模数据和分布式场景，XGBoost 提出了基于特征分位点（quantile）的近似算法。核心思想是：不检查所有可能的分裂点，而是根据特征值的分布提出一组候选分裂点（candidate splits），然后在这些候选点中搜索最佳分裂。
Algorithm: Approximate Split Finding |
近似算法可以在以下两种模式下工作：
- Global：在树构建初期提出所有候选分裂点，整棵树使用同一组分位点
- Local：每次分裂时重新提出候选分裂点
Global vs Local 对比：
| 策略 | 候选点提出次数 | 内存开销 | 准确性 |
|---|---|---|---|
| Global | 1 次（构建开始） | 低 | 需要更多候选点达到相同精度 |
| Local | 每次分裂时 | 中（但候选点少） | 用较少候选点即可达到高精度 |
实验表明，Local 策略在候选点数量较少时更有优势，而 Global 策略在候选点足够多（eps 足够小）时可以达到与精确贪心算法相近的精度。
3.3 加权分位点草图（Weighted Quantile Sketch）
近似算法的关键在于如何提出候选分裂点。XGBoost 的一个重要创新是：以 Hessian（二阶梯度）为权重来构造加权分位点。
为什么用 $h_i$ 作为权重？回顾目标函数：
$$ \tilde{\mathcal{L}}^{(t)} = \sum_{i=1}^{n} \frac{1}{2} h_i (f_t(x_i) + \frac{g_i}{h_i})^2 + \Omega(f_t) + \text{constant} $$
这可以重写为以 $h_i$ 为权重的加权平方损失形式。因此，在构造候选分裂点时，应以样本的 Hessian 为权重，确保”重要”样本（Hessian 大，即预测不确定性高）附近有更密集的候选分裂点。
加权分位点草图（Weighted Quantile Sketch）数据结构：
XGBoost 实现了一个支持 merge 和 prune 操作的数据结构，用于高效地维护带权重的分位点摘要。该结构能在分布式环境下将多个分区的分位点摘要合并，实现全局排序。
核心操作：
merge：将两个加权分位点摘要合并为一个prune：在一定精度 $\epsilon$ 下截断以控制摘要大小
算法通过维护满足以下条件的候选点序列 ${s_{k1}, s_{k2}, …, s_{kl}}$ 来近似分位点：
$$ | r_k(s_{k,j}) - r_k(s_{k,j+1}) | < \epsilon $$
其中 $r_k(s) = \frac{1}{\sum h_i} \sum_{x_{ik} < s} h_i$ 是特征 k 在值 s 处的加权排序函数。
3.4 稀疏感知（Sparsity-aware）分裂
现实世界数据中经常存在缺失值、零值过多、One-Hot 编码等稀疏情况。XGBoost 为每个节点添加了一个默认方向（default direction）来处理缺失值。
Algorithm: Sparsity-aware Split Finding |
这样做有两个好处：
- 统一处理各种稀疏性（缺失值、零值、One-Hot）
- 计算效率高：只需要对非缺失值进行排序，缺失值样本只需一次聚合计算
4. 系统设计：列块并行化
4.1 列块（Column Block）结构
这是 XGBoost 系统设计中最关键的优化。传统 GBDT 实现中，每次分裂都需要对每个特征重新排序，排序开销占总时间的很大一部分。
XGBoost 的策略是：在训练开始前，将所有数据预先按列（特征）排序，并压缩存储为内存单元（Column Block）。
Column Block 结构示意： |
每个 Column Block 中的数据按特征值排序，并以 CSC（Compressed Sparse Column）格式存储。这样在训练过程中，可以并行地处理多个列块，每个列块独立完成分裂查找。
列块 vs 行块对比：
| 维度 | 列块（Column Block） | 行块（Row Block） |
|---|---|---|
| 适用场景 | 特征数 < 样本数 | 特征数 > 样本数 |
| 分裂查找 | O(列内样本数)，无需重复排序 | 需要每次排序 |
| 内存布局 | 列连续，利于特征遍历 | 行连续，利于梯度更新 |
| 并行粒度 | 按列并行 | 按行并行 |
| XGBoost 默认 | Yes | No |
4.2 缓��感知的预取（Cache-aware Prefetch）
虽然列块并行化显著提高了计算效率，但它引入了非连续内存访问问题。当通过排序后的 sample_id 索引去获取对应的梯度和 Hessian 值时，访问模式是不规则的（indirect index lookup），容易导致 CPU 缓存未命中（cache miss）。
XGBoost 的解决方案：
方案 1：缓存感知预取（Cache-aware Prefetch）
在每个线程内部维护一个缓冲区，将梯度统计量的累积操作延迟到缓冲满后进行。具体做法是：先按排序顺序预取对应的 g 和 h 到内部缓冲区（一次连续取出多个），然后在缓冲区内完成累加操作。
Pseudo-code for cache-aware prefetch: |
方案 2：内存预取指令（Prefetch Intrinsics）
利用 CPU 的 _mm_prefetch 内在指令，在处理当前样本的同时提前将后续样本的 g, h 数据从主存加载到 CPU 缓存中。
4.3 核外计算（Out-of-Core Computation）
当数据量超过物理内存时，XGBoost 支持磁盘上的核外计算。核心策略包括：
块压缩（Block Compression）：将列块按 2^16 行进行分组，每组独立压缩（使用通用压缩算法）。在读取时整组解压，实现了”部分加载、部分解压”的 IO 模式。
块分片（Block Sharding）：当有多个磁盘时，将压缩数据分布到不同磁盘上，每个磁盘有一个独立的预取线程，将数据提前加载到内存缓冲区。
这两种技术配合，使得 XGBoost 可以在不牺牲太多速度的情况下处理远超物理内存的数据集。
4.4 并行化策略总结
XGBoost 的并行化在不同的层面展开：
| 层级 | 并行策略 | 说明 |
|---|---|---|
| 特征级 | 列块并行 | 多个特征同时进行分裂查找 |
| 数据级 | 数据分片 + AllReduce | 分布式环境下，每台机器持有部分数据 |
| 树级 | 不支持 | Boosting 的迭代依赖决定了树之间只能串行 |
| 节点级 | 同层节点间可并行 | 同一层的不同节点分裂可并行 |
5. 超参数指南
XGBoost 的超参数可以分为三类：通用参数、树参数和学习任务参数。
5.1 核心参数详解
通用参数（General Parameters）：
| 参数 | 含义 | 典型值 |
|---|---|---|
booster |
提升器类型 | gbtree（默认）, gblinear, dart |
nthread |
并行线程数 | 通常设为 CPU 核心数 |
verbosity |
日志级别 | 0 (silent), 1 (warning), 2 (info), 3 (debug) |
树参数（Tree Parameters）：
| 参数 | 含义 | 建议范围 | 调参优先级 |
|---|---|---|---|
max_depth |
树的最大深度 | 3-10，默认 6 | 高 |
min_child_weight |
叶子节点最小 Hessian 和 | 1-10，默认 1 | 高（控制过拟合） |
gamma |
分裂所需最小损失减少量 | 0-0.5，默认 0 | 中 |
subsample |
行采样比例 | 0.5-1.0，默认 1.0 | 高 |
colsample_bytree |
建树时的列采样比例 | 0.3-1.0，默认 1.0 | 高 |
colsample_bylevel |
每层分裂时的列采样比例 | 0.3-1.0 | 中 |
colsample_bynode |
每节点分裂时的列采样比例 | 0.3-1.0 | 低 |
lambda (reg_lambda) |
L2 正则化系数 | 0-10，默认 1 | 中 |
alpha (reg_alpha) |
L1 正则化系数 | 0-10，默认 0 | 中 |
eta (learning_rate) |
学习率/收缩率 | 0.01-0.3，默认 0.3 | 高 |
学习任务参数：
| 参数 | 含义 | 典型值 |
|---|---|---|
objective |
损失函数 | reg:squarederror, binary:logistic, multi:softmax 等 |
eval_metric |
评估指标 | rmse, logloss, auc, merror 等 |
seed |
随机种子 | 任意整数 |
5.2 调参流程建议
# 调参的标准流程（由粗到细） |
5.3 常见的参数组合（Cheat Sheet）
快速 benchmark（追求速度）：
{'max_depth': 4, 'eta': 0.3, 'subsample': 0.8, |
高精度（追求精度）：
{'max_depth': 8, 'eta': 0.01, 'subsample': 0.9, |
防止过拟合：
{'max_depth': 3, 'eta': 0.1, 'subsample': 0.6, |
处理大规模稀疏数据：
{'max_depth': 6, 'eta': 0.1, 'subsample': 0.8, |
6. XGBoost 在 Kaggle 中的主导地位
2015-2017 年间，Kaggle 竞赛获奖方案中 XGBoost 的使用率超过 50%。几个典型案例：
6.1 Higgs Boson（HiggsML 挑战赛）
这是一个二分类问题（信号/背景），数据量约 25 万行，30 个特征。XGBoost 拿到该竞赛的第一名，关键配置：
- 使用 AMS（Approximate Median Significance）作为自定义评估指标
- 多类参数组合平均（ensemble of XGBoost with different params）
6.2 Otto Group Product Classification
九分类问题，约 6.2 万样本，93 个特征。获胜方案：
- 多通道 XGBoost 模型（不同深度、列采样）做 stacking
- 二阶特征交互信息
6.3 为什么 XGBoost 在表格数据上难以被超越？
| 因素 | XGBoost | 深度学习（MLP/TabNet） |
|---|---|---|
| 训练速度 | 快（分钟级） | 慢（需 GPU） |
| 不需要大量归一化 | Yes | No（需要标准化） |
| 对缺失值鲁棒 | 内建支持 | 需要预处理 |
| 可解释性 | 高（特征重要性） | 低 |
| 对小数据集 | 极好 | 通常过拟合 |
| 超参数调优成本 | 低-中 | 高 |
| 在大规模表格数据上 | 极好（GPU Hist 版本） | 一般 |
7. 与其他 Boosting 库的对比
| 特性 | XGBoost | LightGBM | CatBoost |
|---|---|---|---|
| 树生长策略 | Level-wise | Leaf-wise | Symmetric (Oblivious) |
| 分裂算法 | 预排序 + Hist | Hist (GOSS + EFB) | Ordered Boosting |
| 类别特征 | 需自行编码 | 内建支持 | 最优类别特征处理 |
| GPU 支持 | 优秀 | 优秀 | 优秀 |
| 内存消耗 | 较高（预排序） | 较低 | 中等 |
| 默认超参数 | 一般 | 较好 | 较好 |
| 速度（CPU） | 快 | 更快（小数据） | 慢（小数据） |
| 速度（GPU） | 非常快 | 非常快 | 快 |
7.1 LightGBM 的 Leaf-wise 生长策略
与 XGBoost 的 Level-wise（按层生长）不同，LightGBM 采用 Leaf-wise（按叶生长）：每轮选择当前所有叶子中分裂增益最大的那个进行分裂。这通常可以更快地降低损失，但也更容易导致过拟合（尤其在数据量小时）。
7.2 CatBoost 的 Ordered Boosting
CatBoost 的核心创新是 Ordered Boosting，它通过对每个样本使用”不含该样本的历史数据”来训练模型，以消除传统 boosting 中的预测偏移（prediction shift）问题。CatBoost 对类别特征的处理也是三者中最优的（使用 Ordered Target Statistics）。
8. 实现细节与伪代码
8.1 XGBoost 训练主循环
Algorithm: XGBoost Training |
8.2 BuildTree 的递归伪代码
Function BuildTree(node, instances I, G_parent, H_parent): |
9. 数学补充与推导
9.1 结构分数的另一种推导视角
从信息论角度看，结构分数可以理解为”最大对数后验的近似”。对于每个叶子节点 $j$：
- 假设叶子内所有样本共享相同的预测值 $w_j$
- 损失函数是 $l(y, w_j)$ 的样本求和
- 在 $w_j$ 上加上 L2 正则化
在 $w_j$ 上的最大后验（MAP）估计等价于最小化：
$$ \min_{w_j} \sum_{i \in I_j} l(y_i, w_j) + \frac{1}{2}\lambda w_j^2 $$
用牛顿法做 1 步迭代（二阶展开 + 令导数为 0），恰好得到：
$$ w_j^* = -\frac{\sum g_i}{\sum h_i + \lambda} $$
9.2 为什么 $h_i$ 对平方损失恒为 1？
对于平方损失 $l(y, \hat{y}) = \frac{1}{2}(y - \hat{y})^2$：
一阶导数：$\frac{\partial l}{\partial \hat{y}} = \hat{y} - y \equiv g_i$
二阶导数：$\frac{\partial^2 l}{\partial \hat{y}^2} = 1 \equiv h_i$
$h_i = 1$ 恒成立意味着：当使用平方损失时，所有样本的权重相同，XGBoost 退化为仅用一阶梯度的 GBDT。这也解释了为什么 XGBoost 的分类问题（使用 LogLoss）比回归问题（使用平方损失）更具优势——因为分类问题的 Hessian $p(1-p)$ 携带了额外的曲率信息。
9.3 DART (Dropouts meet Multiple Additive Regression Trees)
除了标准的 GBDT 提升器，XGBoost 还实现了 DART 提升器。DART 借鉴了深度学习中 Dropout 的思想：在每轮迭代中，随机丢弃一部分已有的树，然后训练新树来弥补被丢弃树的贡献。
DART 的更新规则：
$$ \hat{y}_i^{(t)} = \hat{y}_i^{(t-1)} - \eta \cdot k \cdot \sum_{m \in \text{dropped}} f_m(x_i) + \eta \cdot f_t(x_i) $$
其中 k 是一个归一化因子，用于补偿被丢弃树的影响。
DART 的优势：
- 缓解了 GBDT 中先期树对最终预测贡献过大的问题（即树的”重要性”过度集中在早期迭代中）
- 在部分任务上能得到更好的泛化能力
10. 面试高频问答
Q1: XGBoost 与 GBDT 的核心区别是什么？
XGBoost 使用损失函数的二阶泰勒展开，引入了 Hessian 信息，使得每一步的目标函数可以写成关于叶子权重的显式二次形式，从而求出叶子权重的闭式解。而 GBDT 仅使用一阶梯度（负梯度）来拟合残差，每棵树的学习率（shrinkage）是手动指定的。此外，XGBoost 在目标函数中显式加入了正则化项 $\gamma T + \frac{1}{2}\lambda ||w||^2$，而 GBDT 通常没有。
Q2: 为什么 XGBoost 使用 Hessian 作为加权分位点的权重？
通过重写目标函数可以发现，XGBoost 的优化目标实际上等价于一个以 $h_i$ 为权重的加权平方损失问题。以 $h_i$ 为权重意味着那些预测不确定性高的样本（Hessian 大）在构造候选分裂点时被赋予更大的关注，确保这些”困难样本”附近有更密集的分裂候选点。从优化角度看，这近似于在 Hessian 加权空间中做等频分桶。
Q3: 列块（Column Block）并行化的原理和局限性？
在训练开始前，XGBoost 将每个特征的数据预先排序并存储为独立的列块。在分裂查找时，多个线程可以同时处理不同的列块，因为每个列块内部的排序顺序是独立的。局限性在于：通过排序后的 sample_id 索引获取梯度和 Hessian 值时，会产生不连续的内存访问（scatter-gather），在缓存不友好时性能下降。这使得 XGBoost 在特征数量较少但样本量极大的场景下优于 LightGBM，而在高维特征场景下可能不如 LightGBM。
Q4: XGBoost 如何处理缺失值？
XGBoost 为每个树节点维护一个默认方向（default direction）。当一个样本在某个特征上缺失时，它会被分到默认方向。默认方向是通过数据驱动的：在训练时对于每个分裂点，尝试将缺失值分配到左子节点和右子节点，选择增益更大的方案作为该节点的默认方向。这种方法在一个统一的框架下处理了所有类型的稀疏性。
Q5: 解释 XGBoost 的 Gain 公式中每一项的含义。
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 $$
- 第一项 $\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}$：不分裂时（父节点）的结构分数，即两个子节点损失的”参照基准”
- 前两项之和减去第三项即为”分裂带来的损失减少量”
- $-\gamma$：分裂的复杂度惩罚，只有净收益超过 $\gamma$ 时才分裂
- 因子 $\frac{1}{2}$：来自目标函数二阶展开中的系数
