6.1 概述与核心创新
XGBoost(eXtreme Gradient Boosting)是由 Tianqi Chen 和 Carlos Guestrin 于 2016 年在 ACM SIGKDD 会议(KDD 2016,论文 XGBoost: A Scalable Tree Boosting System)上提出的可扩展端到端树提升系统。它是对传统梯度提升决策树(GBDT)的算法与工程双重革新,通过引入二阶泰勒展开、显式正则化目标函数、加权分位数草图、稀疏感知分裂以及系统级优化(Block结构、缓存感知、核外计算),在速度和精度上均实现了显著突破。
XGBoost 的核心创新点可总结为以下五项:
- 正则化学习的目标函数:显式加入树复杂度惩罚项(论文中为叶子数惩罚 + 叶子权重的 L2 惩罚,实现中另外提供 L1 惩罚),将正则化直接融入树学习目标,而非仅作为后处理手段。
- 二阶泰勒展开:利用损失函数的二阶导数(Hessian)信息,实现牛顿型优化,收敛速度比仅使用一阶梯度的传统GBDT更快、更稳定。
- 加权分位数草图(Weighted Quantile Sketch):为大规模数据提供高效的分裂候选点搜索,以二阶导数作为样本权重;论文给出了一个支持合并与剪枝操作、带可证明误差保证的分布式加权分位数草图算法(证明见论文附录)。
- 稀疏感知分裂(Sparsity-aware Split Finding):将缺失值处理内置于树学习过程中,自动学习缺失值的默认方向,无需预处理填充。
- 系统级优化:列块存储(Column Block)、缓存感知预取(Cache-aware Prefetching)、核外计算(Out-of-core Computation),全面压榨硬件性能。
6.2 与GBDT的核心区别
下表从算法、正则化、系统优化三个维度对比 XGBoost 与传统 GBDT(Friedman 2001)的核心差异:
| 特性 | GBDT(Friedman 2001) | XGBoost(Chen & Guestrin 2016) |
|---|---|---|
| 优化阶数 | 一阶导数(梯度) | 一阶 + 二阶导数(梯度 + Hessian) |
| 目标函数正则化 | 无显式正则化 | L1 + L2 + 树复杂度惩罚($\gamma T$) |
| 分裂算法 | 精确贪心(预排序) | 精确贪心 + 近似算法 + 加权分位数草图 + 直方图 |
| 缺失值处理 | 需预处理(如均值/中位数填充) | 稀疏感知分裂,自动学习默认方向 |
| 列采样 | 原始算法未包含(scikit-learn 通过 max_features 支持分裂时的特征采样) | 支持按树/层级/节点三级列采样 |
| 行采样 | 支持(子采样) | 支持(子采样) |
| 并行化 | 不支持树内并行 | 特征级并行、Block列块结构、缓存感知 |
| 核外计算 | 不支持 | 支持,数据压缩分块存储与读取 |
| 分布式训练 | 不支持 | 支持(基于 AllReduce 的通信,早期版本由 Rabit 库实现) |
| 自定义目标函数 | 框架上支持任意可微损失,但常见实现(如 scikit-learn)只提供内置损失 | 支持(需提供一阶/二阶梯度) |
核心洞察:XGBoost 并非对 GBDT 的颠覆式替代,而是在 GBDT 一阶梯度框架基础上引入二阶信息和显式正则化,并辅以系统级工程优化,使树提升在精度和效率上均达到新的高度。
6.3 目标函数的完整推导
6.3.1 原始目标函数
在第 $t$ 轮迭代时,XGBoost 的目标函数定义为:
$$ \mathrm{Obj}^{(t)} = \sum_{i=1}^{n} L\left(y_i, \hat{y}_i^{(t-1)} + f_t(x_i)\right) + \Omega(f_t) $$符号表:
| 符号 | 含义 |
|---|---|
| $n$ | 训练样本数量 |
| $y_i$ | 样本 $i$ 的真实标签 |
| $\hat{y}_i^{(t-1)}$ | 前 $t-1$ 轮累加后的模型预测值 |
| $f_t(x_i)$ | 第 $t$ 轮新增树对样本 $i$ 的输出(即样本所落叶子的权重 $w_{q(x_i)}$) |
| $L(\cdot, \cdot)$ | 可微损失函数(如MSE、Log Loss) |
| $\Omega(f_t)$ | 第 $t$ 棵树的正则化惩罚项 |
6.3.2 二阶泰勒展开
XGBoost 的核心创新之一是使用二阶泰勒展开来近似损失函数。令 $x = \hat{y}_i^{(t-1)}$,$\Delta x = f_t(x_i)$,根据泰勒公式:
$$ f(x + \Delta x) \approx f(x) + f'(x)\Delta x + \frac{1}{2}f''(x)(\Delta x)^2 $$将 $L(y_i, \hat{y}_i^{(t-1)} + f_t(x_i))$ 在 $\hat{y}_i^{(t-1)}$ 处展开:
$$ \mathrm{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) $$其中一阶梯度 $g_i$ 和二阶 Hessian $h_i$ 定义为:
$$ g_i = \partial_{\hat{y}^{(t-1)}} L(y_i, \hat{y}_i^{(t-1)}) = \frac{\partial L(y_i, \hat{y}_i^{(t-1)})}{\partial \hat{y}_i^{(t-1)}} $$$$ h_i = \partial^2_{\hat{y}^{(t-1)}} L(y_i, \hat{y}_i^{(t-1)}) = \frac{\partial^2 L(y_i, \hat{y}_i^{(t-1)})}{\partial (\hat{y}_i^{(t-1)})^2} $$符号表:
| 符号 | 含义 |
|---|---|
| $g_i$ | 样本 $i$ 在当前预测处的一阶梯度(其相反数 $-g_i$ 就是 GBDT 中的伪残差) |
| $h_i$ | 样本 $i$ 在当前预测处的二阶 Hessian(曲率信息) |
由于 $\hat{y}_i^{(t-1)}$ 在前 $t-1$ 轮已确定,$L(y_i, \hat{y}_i^{(t-1)})$ 是常数,不影响优化,可移除。简化为:
$$ \mathrm{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) $$为什么二阶展开优于仅使用一阶?
- 一阶方法(如传统GBDT)用一阶梯度(伪残差)决定树的结构,相当于函数空间中的梯度下降;步长要靠学习率 $\eta$ 和额外的线搜索来确定(Friedman 的 GBDT 会对每个叶子做一维线搜索,见 Gradient Boosting Machine(梯度提升机)),树结构本身没有利用曲率信息。
- 二阶方法(牛顿提升)利用Hessian $h_i$ 的曲率信息,自适应调整步长:在损失曲率陡峭处($h_i$ 大)自动缩小更新幅度,在平坦处($h_i$ 小)允许更大步长。每个叶子的更新量 $-\frac{G_j}{H_j+\lambda}$ 正是带 L2 正则的一步牛顿-拉夫森(Newton-Raphson)更新,因此通常收敛更快、更稳定。
- 从统计角度看,二阶展开相当于对损失函数在局部做二次近似,能够更精确地刻画最优更新方向。
6.3.3 树结构正则化
XGBoost 对每棵树的复杂度定义了显式正则化项:
$$ \Omega(f) = \gamma T + \frac{1}{2}\lambda \sum_{j=1}^{T} w_j^2 + \alpha \sum_{j=1}^{T} \lvert w_j \rvert $$符号表:
| 符号 | 含义 |
|---|---|
| $T$ | 树的叶子节点数量 |
| $w_j$ | 第 $j$ 个叶子节点的输出权重 |
$\gamma$(gamma / min_split_loss) | 叶子数惩罚系数,控制树的复杂度(越大越倾向于简单树) |
$\lambda$(lambda / reg_lambda) | L2正则化系数,惩罚大权重(默认值为1) |
$\alpha$(alpha / reg_alpha) | L1正则化系数,产生稀疏权重(默认值为0) |
$\gamma T$ 项惩罚树的叶子数量,促使模型选择更简单的树结构;$\frac{1}{2}\lambda \sum_j w_j^2$ 为L2正则化,平滑叶子输出;$\alpha \sum_j \lvert w_j \rvert$ 为L1正则化,可把部分叶子权重压缩为 0。
论文与实现的区别 原论文的正则项只有 $\gamma T + \frac{1}{2}\lambda \lVert w \rVert^2$,L1 项 $\alpha$ 是 XGBoost 实现额外提供的参数(
alpha/reg_alpha)。下面 6.3.4–6.3.6 的推导与论文一致,取 $\alpha = 0$;$\alpha > 0$ 时的结果见 6.3.5 末尾。
6.3.4 按叶子节点重写目标函数
将样本按叶子节点分组。定义 $I_j = \{i \mid q(x_i) = j\}$ 为落入第 $j$ 个叶子的样本索引集合,其中 $q(x)$ 为树结构函数(将样本映射到叶子索引),于是 $f_t(x_i) = w_{q(x_i)}$。取 $\alpha = 0$,目标函数可重写为:
$$ \mathrm{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 $$定义叶子 $j$ 的梯度统计量:
$$ G_j = \sum_{i \in I_j} g_i, \quad H_j = \sum_{i \in I_j} h_i $$则目标函数变为简洁的二次形式:
$$ \mathrm{Obj}^{(t)} = \sum_{j=1}^{T}\left[ G_j w_j + \frac{1}{2}(H_j + \lambda)w_j^2 \right] + \gamma T $$6.3.5 最优叶子权重公式推导
对每个叶子 $j$,目标函数是关于 $w_j$ 的二次函数:
$$ \mathcal{L}_j(w_j) = G_j w_j + \frac{1}{2}(H_j + \lambda)w_j^2 $$对 $w_j$ 求导并令其为零:
$$ \frac{\partial \mathcal{L}_j}{\partial w_j} = G_j + (H_j + \lambda)w_j = 0 $$解得最优叶子权重(闭式解):
$$ \boxed{w_j^* = -\frac{G_j}{H_j + \lambda}} $$将 $w_j^*$ 代回目标函数,得到最优结构分数(Structure Score):
$$ \boxed{\mathrm{Obj}^* = -\frac{1}{2}\sum_{j=1}^{T}\frac{G_j^2}{H_j + \lambda} + \gamma T} $$符号表:
| 符号 | 含义 |
|---|---|
| $w_j^*$ | 第 $j$ 个叶子的最优输出权重 |
| $\mathrm{Obj}^*$ | 给定树结构下的最优目标函数值 |
| $G_j$ | 落入叶子 $j$ 的所有样本一阶梯度之和 |
| $H_j$ | 落入叶子 $j$ 的所有样本二阶Hessian之和 |
结构分数的物理意义:
- $\frac{G_j^2}{H_j + \lambda}$ 衡量叶子 $j$ 对降低整体损失的贡献:这个值越大,$-\frac{1}{2}\frac{G_j^2}{H_j+\lambda}$ 越小,说明该叶子把损失降得越多。
- $\gamma T$ 惩罚树的叶子数量,防止过拟合。当 $T$ 增大时,惩罚项线性增长。
- $\mathrm{Obj}^*$ 是损失的近似值,越小表示树结构越好(论文原话:“the smaller the score is, the better the structure is”)。它的作用类似决策树中的不纯度,用来给树结构打分;寻找分裂时,算法选择让 $\mathrm{Obj}^*$ 下降最多的分裂,即下一节的增益最大的分裂。
带 L1 正则($\alpha > 0$)时的最优叶子权重:此时每个叶子要最小化 $G_j w_j + \frac{1}{2}(H_j+\lambda) w_j^2 + \alpha \lvert w_j \rvert$。按 $w_j>0$、$w_j<0$、$w_j=0$ 三种情况分别求解,可得软阈值形式:
$$ w_j^* = -\frac{\operatorname{sign}(G_j)\max\left(\lvert G_j \rvert - \alpha,\ 0\right)}{H_j + \lambda} $$即 $\lvert G_j \rvert \le \alpha$ 时叶子权重直接为 0,这就是 L1 产生稀疏叶子权重的原因。代回后该叶子的最优值为 $-\frac{1}{2}\frac{\left(\max(\lvert G_j \rvert - \alpha, 0)\right)^2}{H_j+\lambda}$,相当于把下文各公式中的 $G^2$ 换成 $\left(\max(\lvert G \rvert - \alpha, 0)\right)^2$。
6.3.6 分裂增益公式推导
当对一个叶子节点进行分裂时,假设分裂为左子树 $L$ 和右子树 $R$。分裂前的结构分数为:
$$ \mathrm{Obj}_{\text{before}} = -\frac{1}{2}\frac{(G_L + G_R)^2}{H_L + H_R + \lambda} + \gamma $$分裂后的结构分数为:
$$ \mathrm{Obj}_{\text{after}} = -\frac{1}{2}\left(\frac{G_L^2}{H_L + \lambda} + \frac{G_R^2}{H_R + \lambda}\right) + 2\gamma $$分裂带来的增益(Gain)定义为分裂前目标函数值减去分裂后目标函数值:
$$ \boxed{\mathrm{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$ | 左子树所有样本Hessian之和 |
| $G_R = \sum_{i \in I_R} g_i$ | 右子树所有样本梯度之和 |
| $H_R = \sum_{i \in I_R} h_i$ | 右子树所有样本Hessian之和 |
| $\gamma$ | 分裂复杂度惩罚,必须至少减少 $\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$ 的代价,只有当 $\mathrm{Gain} > 0$(即损失下降超过 $\gamma$)时,这个分裂才值得保留。在 XGBoost 实现中,参数
gamma(别名min_split_loss,默认 0)就是这里的 $\gamma$;树长成后,prune更新器会剪掉损失下降小于min_split_loss的分裂(官方文档 Tree Methods 与updater参数说明),所以 $\gamma$ 也有后剪枝的效果。
min_child_weight 的含义:参数 min_child_weight(默认 1)是子节点中 $H = \sum_{i} h_i$ 的下限,分裂后任一子节点的 Hessian 之和小于它就放弃该分裂。$h_i$ 可以看成样本在二阶近似中的“权重”:对平方损失 $\frac{1}{2}(y-\hat{y})^2$ 有 $h_i = 1$,此时它就是子节点的最小样本数;对二分类对数损失有 $h_i = p_i(1-p_i) \le \frac{1}{4}$,模型对某些样本越有把握($p_i$ 接近 0 或 1),这些样本贡献的 $h_i$ 越小,含这类样本的节点就越难继续分裂。
与信息增益的区别:传统决策树使用信息增益或Gini不纯度,基于标签分布;XGBoost的增益基于梯度统计量 $G_j$ 和 $H_j$,直接优化损失函数的减少量,且融入正则化。
6.4 分裂增益公式推导(小结)
上述增益公式已完整推导。为进一步加深理解,考虑一个数值示例:假设某叶子节点包含10个样本,$G_{\text{parent}} = 5.0$,$H_{\text{parent}} = 8.0$,$\lambda = 1.0$,$\gamma = 0.1$。分裂后左子树 $G_L = 4.0, H_L = 3.0$,右子树 $G_R = 1.0, H_R = 5.0$。则:
$$ \mathrm{Gain} = \frac{1}{2}\left[\frac{16}{3+1} + \frac{1}{5+1} - \frac{25}{8+1}\right] - 0.1 \approx \frac{1}{2}\left[4 + 0.167 - 2.778\right] - 0.1 \approx 0.594 > 0 $$增益为正,因此该分裂被允许。分裂后两个叶子的最优权重分别为 $w_L^* = -\frac{4}{3+1} = -1$,$w_R^* = -\frac{1}{5+1} \approx -0.167$;若不分裂,父节点权重为 $-\frac{5}{8+1} \approx -0.556$。
6.5 分裂算法:精确贪心、近似算法、加权分位数草图
6.5.1 精确贪心算法(Exact Greedy Algorithm)
精确贪心算法枚举每个特征的所有可能分裂点,选择增益最大的分裂。它适用于数据量较小、可以完全放入内存且希望获得精确分裂点的场景;在较新的 XGBoost 实践中,大多数大规模任务会优先使用 hist 直方图方法。
伪代码:
- 输入:当前节点实例集合 $I$,特征维度 $d$
- 初始化:$\mathit{score} \leftarrow 0$,$G \leftarrow \sum_{i \in I} g_i$,$H \leftarrow \sum_{i \in I} h_i$
- 对于每个特征 $k = 1, 2, \dots, d$:
- 初始化:$G_L \leftarrow 0$,$H_L \leftarrow 0$
- 按特征值 $x_{jk}$ 对 $I$ 中样本升序排序
- 对于排序后的每个样本 $j$:
- $G_L \leftarrow G_L + g_j$,$H_L \leftarrow H_L + h_j$
- $G_R \leftarrow G - G_L$,$H_R \leftarrow H - H_L$
- $\mathit{score} \leftarrow \max\left(\mathit{score},\ \frac{G_L^2}{H_L+\lambda} + \frac{G_R^2}{H_R+\lambda} - \frac{G^2}{H+\lambda}\right)$
- 输出:$\mathit{score}$ 最大的分裂点(这里的 $\mathit{score}$ 是 $2(\mathrm{Gain}+\gamma)$,常数因子和 $\gamma$ 不影响比较)
复杂度分析:若在每个节点都重新排序,单个节点的代价约为 $O(d\, n \log n)$($n$ 为节点样本数,$d$ 为特征数)。XGBoost 的做法是训练前把每列排序一次存入列块(见 6.7.2),之后每层只需线性扫描。论文给出的整体复杂度是:设共 $K$ 棵树、最大深度为 $d_{\max}$、训练数据中非缺失项个数为 $\lVert \mathbf{x} \rVert_0$,原始稀疏感知精确算法为 $O(K d_{\max} \lVert \mathbf{x} \rVert_0 \log n)$,使用列块后降为 $O(K d_{\max} \lVert \mathbf{x} \rVert_0 + \lVert \mathbf{x} \rVert_0 \log n)$,其中 $O(\lVert \mathbf{x} \rVert_0 \log n)$ 是只做一次、可以摊销的预排序开销。
6.5.2 近似算法与加权分位数草图
对于大规模数据,精确贪心算法不可行。XGBoost提出近似算法,分为两个阶段:
阶段一:提案(Proposal)
- 根据特征分布的分位数提出候选分裂点集合。
- 全局策略:在树构建初始阶段一次性提出所有候选点,所有层级共享。
- 局部策略:每次分裂后重新提出候选点,更精确但计算开销更大。
阶段二:聚合与选择
- 将连续特征按候选点分桶(binning)。
- 在每个桶内聚合梯度统计量 $G$ 和 $H$。
- 在候选分裂点中找最大增益。
| 策略 | 提案时机 | 候选点数量 | 精度 | 计算开销 |
|---|---|---|---|---|
| 全局 | 树构建前一次性 | 较多 | 略低 | 较少 |
| 局部 | 每次分裂后 | 较少 | 更高 | 较多 |
实验证明,在Higgs 10M数据集上,局部策略可用更少的候选点达到与全局策略相同的精度。
加权分位数草图(Weighted Quantile Sketch):候选分裂点的选取不能简单按等频分位数,因为每个样本对损失的贡献不同。XGBoost以二阶导数 $h_i$ 为权重,定义加权秩函数:
记第 $k$ 个特征的取值与对应二阶导构成的多重集为 $\mathcal{D}_k = \{(x_{1k}, h_1), (x_{2k}, h_2), \dots, (x_{nk}, h_n)\}$,定义加权秩函数:
$$ r_k(z) = \frac{1}{\sum_{(x,h) \in \mathcal{D}_k} h} \sum_{(x,h) \in \mathcal{D}_k,\ x < z} h $$它表示特征 $k$ 取值小于 $z$ 的样本所占的 Hessian 比例。目标是找到候选分裂点 $\{s_{k1}, s_{k2}, \dots, s_{kl}\}$(其中 $s_{k1} = \min_i x_{ik}$,$s_{kl} = \max_i x_{ik}$),使得相邻点之间的加权秩差小于 $\epsilon$:
$$ \left\lvert r_k(s_{k,j}) - r_k(s_{k,j+1}) \right\rvert < \epsilon $$其中 $\epsilon$ 为近似因子,约产生 $1/\epsilon$ 个候选点。$h_i$ 作为权重的合理性可从目标函数配方看出:
$$ \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}^{n} \frac{1}{2}h_i\left(f_t(x_i) + \frac{g_i}{h_i}\right)^2 - \sum_{i=1}^{n}\frac{g_i^2}{2h_i} $$右边最后一项与 $f_t$ 无关,所以第 $t$ 轮的目标等价于加权平方损失:权重为 $h_i$,回归标签为 $-g_i/h_i$。Hessian 大的样本对损失影响大,切分点就应在这些样本附近排得更密。
论文中的符号笔误 原论文这一式写作 $\frac{1}{2}h_i\left(f_t(x_i) - g_i/h_i\right)^2$、标签写作 $g_i/h_i$,符号有误。展开即可验证正确形式是 $+g_i/h_i$,对应标签 $-g_i/h_i$(也就是一步牛顿更新的方向)。
6.5.3 直方图优化与三种 tree_method
在近似算法基础上,XGBoost进一步使用直方图方法:
- 对每个特征,将连续值分桶(bin)形成离散直方图。
- 在桶边界计算梯度统计量,而不是在每个唯一值处计算。
- 直方图聚合可并行化,且适合GPU加速。
参数控制:tree_method='hist' 启用直方图优化,max_bin 控制最大分桶数(默认 256,仅 hist / approx 使用)。
XGBoost 现有三种建树方法,区别如下(依据官方文档 Tree Methods):
tree_method | 候选分裂点的来源 | 特点 |
|---|---|---|
exact | 枚举数据中的全部取值(6.5.1) | 最精确但最慢;不支持外存训练、分布式训练、类别特征和 lossguide 生长策略 |
approx | 每棵树构建前用全部样本重新做一次草图,以 Hessian 为权重(6.5.2 的加权分位数草图) | 逐树更新候选点,Hessian 不恒定的目标上有时更准,但比 hist 慢 |
hist | 训练开始前只做一次草图,只使用用户提供的样本权重而不用 Hessian,之后各节点直方图都基于这份全局分桶 | 最快;auto(默认值,2.0 起)等同于 hist |
对 reg:squarederror 这类 Hessian 恒为常数的目标,加权草图与普通分位数没有区别,应优先用 hist。官方文档也指出,多数情况下 hist 配合更大的 max_bin 就能达到与 approx 相当甚至更好的精度。hist 和 approx 还支持 grow_policy='lossguide'(按损失下降最大的叶子生长,配合 max_leaves,与 LightGBM 的 Leaf-wise 类似,见 LightGBM)。
6.6 稀疏感知分裂(缺失值处理)
现实数据中稀疏性普遍存在,原因包括:缺失值、频繁出现的零值(统计稀疏性)、特征工程产物(如one-hot编码导致的大量零值)。传统方法需要预处理(如均值填充),可能引入偏差。XGBoost提出稀疏感知分裂,将缺失值处理内置于树学习过程中。
核心思想:默认方向学习
XGBoost在每个树节点中附加一个默认方向(default direction)。当样本在分裂特征上的值缺失时,沿默认方向走。关键是:默认方向不是预设的,而是从数据中学出来的。
对每个候选分裂,算法执行以下步骤:
- 仅使用非缺失值样本计算潜在分裂。
- 枚举缺失值样本的两种方向:
- 缺失值全部走左子树
- 缺失值全部走右子树
- 计算两种情况下对应的增益,选择增益更大的方向作为默认方向。
伪代码:
- 输入:当前节点实例集合 $I$,特征 $k$ 的非缺失值样本 $I_k = \{i \in I \mid x_{ik} \neq \text{missing}\}$
- 计算统计量:非缺失样本 $G_k = \sum_{i \in I_k} g_i$,$H_k = \sum_{i \in I_k} h_i$;缺失样本 $G_m = \sum_{i \in I \setminus I_k} g_i$,$H_m = \sum_{i \in I \setminus I_k} h_i$
- 初始化:$G_L \leftarrow 0$,$H_L \leftarrow 0$,$\mathit{score} \leftarrow 0$
- 对于按 $x_{jk}$ 升序排序后的每个非缺失样本 $j \in I_k$:
- $G_L \leftarrow G_L + g_j$,$H_L \leftarrow H_L + h_j$
- $G_R \leftarrow G_k - G_L$,$H_R \leftarrow H_k - H_L$
- $\mathit{score}_{\text{left}} \leftarrow \mathrm{Gain}(G_L + G_m, H_L + H_m, G_R, H_R)$ // 缺失值走左边
- $\mathit{score}_{\text{right}} \leftarrow \mathrm{Gain}(G_L, H_L, G_R + G_m, H_R + H_m)$ // 缺失值走右边
- $\mathit{score} \leftarrow \max(\mathit{score}, \mathit{score}_{\text{left}}, \mathit{score}_{\text{right}})$
- 输出:最优分裂及默认方向
原论文(Algorithm 3)的写法是对非缺失样本分别做一次升序扫描和一次降序扫描:升序扫描时缺失值被归入右侧,降序扫描时缺失值被归入左侧。上面的单次扫描写法与之等价。
性能与特性:
- 计算效率:稀疏感知算法只遍历非缺失值,计算复杂度与输入中非缺失值的数量成线性关系。在Allstate-10K数据集上,比朴素实现快50倍。
- 统一处理:同时处理缺失值、零值和one-hot编码稀疏性,无需区分来源。
- 预测阶段:已学习的树在预测时直接使用默认方向路由缺失值样本。
- 参数控制:
missing参数(DMatrix与 sklearn 接口均有,默认np.nan)可指定具体值(如-999)被识别为缺失。对稀疏矩阵输入(如scipy.sparse.csr_matrix),没有存储的元素同样按缺失处理,这正是稀疏感知算法只遍历非缺失项的来源。
6.7 列采样与并行优化(Block结构、缓存感知、核外计算)
6.7.1 列采样(Column Subsampling)
XGBoost借鉴随机森林的思想,引入三级列采样防止过拟合:
| 参数 | 作用层级 | 说明 |
|---|---|---|
colsample_bytree | 每棵树 | 构建每棵树前随机选取一定比例特征子集 |
colsample_bylevel | 每层 | 树每一层分裂时随机选取一定比例特征子集 |
colsample_bynode | 每个节点 | 每个节点分裂时随机选取一定比例特征子集 |
三个参数默认都是 1,并且是逐级嵌套、累乘的:每层的特征从本棵树选中的特征中再抽取,每个节点的特征又从本层选中的特征中再抽取。例如 64 个特征、三者都设为 0.5 时,每次分裂只剩 $64 \times 0.5^3 = 8$ 个候选特征(官方文档示例)。colsample_bynode 不支持 exact 方法。
论文提到,根据用户反馈,列采样防止过拟合的效果甚至比传统的行采样(subsample)更好,同时还能加快并行算法的计算。直观上,每棵树只看部分特征,各棵树之间更不容易犯同样的错误,这和随机森林的思路一致。
6.7.2 并行优化:Block结构
列块存储(Column Block):XGBoost将数据按列压缩存储(Compressed Columnar Format, CSC):
- 数据预先按每列特征值排序,存入名为Block的内存单元。
- 排序后的列块在训练各轮中可复用,避免重复排序。
- 分桶统计在排序列上变为线性扫描,极大加速近似算法。
- 块可以按行切分成多个小块分别存放,便于并行和分布式处理。对近似算法,论文实验发现每块 $2^{16}$ 个样本能较好地兼顾缓存命中和并行负载:块太小则每个线程工作量不足,块太大则梯度统计量放不进 CPU 缓存。
特征级并行:收集每列的统计量($G$ 和 $H$)可独立进行,天然并行化。树构建是顺序的(Boosting本质),但单棵树内的分裂查找可高度并行。
6.7.3 缓存感知访问(Cache-aware Access)
梯度统计量 $g_i$ 和 $h_i$ 按样本索引存储。在按排序后的特征值扫描时,样本索引非连续访问,导致缓存未命中(cache miss)。XGBoost的解决方案:
- 为每个线程分配内部缓冲区(internal buffer)。
- 使用缓存感知预取(cache-aware prefetching):先把接下来要用的梯度统计量按顺序取到缓冲区,再以小批量(mini-batch)方式做累加,把“读一个、立即累加一个”的直接读写依赖变成更长的依赖链,从而减少缓存未命中带来的停顿。
- 在 Allstate 和 Higgs 的 1000 万样本数据集上,缓存感知的精确贪心算法比朴素实现快约 2 倍;在 100 万样本的数据集上差别不明显,因为梯度统计量本身就能放进缓存。
6.7.4 核外计算(Out-of-core Computation)
当数据超过内存容量时:
- 数据分块(block)存储到磁盘,并在训练过程中重叠计算与磁盘读取。
- 块压缩(Block Compression):块按列压缩,由独立线程在加载时即时解压。论文在所测数据集上得到约 26%–29% 的压缩比。
- 分片(Sharding):将数据分片到多个磁盘,并行读取,突破磁盘I/O瓶颈。
- 压缩/解压开销远小于磁盘访问时间,整体加速显著。
6.8 XGBoost在Kaggle中的应用
XGBoost自2014-2015年起在Kaggle竞赛中确立主导地位:
- 2015年:Kaggle 官方博客在 2015 年发布的 29 个获奖方案中,17个使用了XGBoost(其中 8 个只用了 XGBoost,其余大多与神经网络集成)。
- KDD Cup 2015:前10名团队全部使用XGBoost。
- 应用领域:广告点击率预测(CTR)、保险理赔、客户行为分析、垃圾邮件/恶意软件分类、粒子物理(Higgs玻色子事件分类)等。
为什么XGBoost在竞赛中表现优异?
- 表格数据的天然优势:结构化/表格数据上,树模型的特征交互捕获能力优于线性模型。
- 特征工程的鲁棒性:对特征缩放不敏感,可处理各种特征类型(数值、类别、二元)。
- 自动处理缺失值:省去繁琐的预处理步骤。
- 正则化防止过拟合:显式正则化在竞赛中泛化能力强。
- 速度快:在相同精度下,训练速度远超传统GBDT,便于快速迭代。
- 可解释性:特征重要性、SHAP值支持模型解释。
6.9 Python API(原生接口+sklearn兼容接口)
XGBoost提供两种Python接口。
原生接口(Native API)
| |
Scikit-Learn兼容接口
| |
上面两段为演示直接把测试集当作早停用的验证集;实际项目中应另外划出验证集,否则测试集分数会偏乐观(见 调参指南与最佳实践 的早停与交叉验证部分)。
原生类别特征支持:XGBoost 1.5 起可以直接处理类别特征,不必先做 one-hot。做法是把类别列设为 pandas 的 category 类型,并在构造 DMatrix 或 sklearn 模型时传入 enable_categorical=True(需使用 hist 或 approx)。1.6 起加入了最优划分(optimal partitioning):类别数小于 max_cat_to_onehot 时按 one-hot 方式(一个类别对其余类别)分裂,否则按梯度统计量对类别排序后,把类别划分为两个子集分裂,思路与 LightGBM 的类别分裂相同(见 LightGBM 7.6 节;依据官方文档 Categorical Data 与 max_cat_to_onehot 参数说明)。
常用目标函数与评估指标:
目标函数 objective | 适用场景 |
|---|---|
reg:squarederror | 回归(均方误差) |
binary:logistic | 二分类(输出概率) |
binary:logitraw | 二分类(输出logit值) |
multi:softmax | 多分类(输出类别) |
multi:softprob | 多分类(输出概率) |
rank:pairwise | 排序学习 |
survival:aft | 生存分析 |
评估指标 eval_metric | 说明 |
|---|---|
rmse | 均方根误差 |
mae | 平均绝对误差 |
logloss | 对数损失 |
error | 分类错误率 |
auc | ROC曲线下面积 |
merror | 多分类错误率 |
ndcg | 归一化折损累积增益 |
6.10 伪代码与整体训练流程
XGBoost整体训练流程
flowchart TD
A["初始化预测值 y_hat_i = base_score"] --> B["For t = 1 to T"]
B --> C["计算每样本梯度 g_i 和 Hessian h_i"]
C --> D["构建第t棵树:寻找最优分裂"]
D --> E["计算最优叶子权重 w_j*"]
E --> F["更新预测值 y_hat_i += eta * f_t(x_i)"]
F --> G{"t < T ?"}
G -->|是| B
G -->|否| H["输出最终模型 F(x) = base_score + eta * sum_t f_t(x)"]
伪代码:
- 输入:训练集 $D = \{(x_i, y_i)\}_{i=1}^n$,迭代轮数 $T$,损失函数 $L$,正则化项 $\Omega$
- 初始化:$\hat{y}_i \leftarrow b_0$,对所有 $i$($b_0$ 即
base_score。XGBoost 2.0 起对多数内置目标会在训练前根据数据自动估计这个截距,也可手动指定,例如base_score=0.5) - 对于 $t = 1, 2, \dots, T$:
- 计算梯度统计量:
- 对于每个样本 $i = 1, \dots, n$:
- $g_i \leftarrow \frac{\partial L(y_i, \hat{y}_i)}{\partial \hat{y}_i}$
- $h_i \leftarrow \frac{\partial^2 L(y_i, \hat{y}_i)}{\partial \hat{y}_i^2}$
- 对于每个样本 $i = 1, \dots, n$:
- 按列块存储数据(可预先完成)
- 构建第 $t$ 棵树:$f_t \leftarrow \text{BuildTree}(\{(x_i, g_i, h_i)\}_{i=1}^n, \Omega)$
- 对于队列中每个节点:
- 初始化 $\mathit{best\_gain} \leftarrow 0$,$\mathit{best\_split} \leftarrow \text{None}$
- 对于每个特征 $k$:
- 获取候选分裂点(精确贪心或近似算法)
- 对于每个候选分裂点:
- $\mathit{gain} \leftarrow \operatorname{ComputeGain}(\text{node}, \text{candidate}, \Omega)$ // 按 6.3.6 计算,已扣除 $\gamma$;含稀疏感知处理
- 如果 $\mathit{gain} > \mathit{best\_gain}$:更新 $\mathit{best\_gain}$ 和 $\mathit{best\_split}$
- 如果 $\mathit{best\_gain} > 0$,且两个子节点的 Hessian 之和都不小于
min_child_weight、未超过max_depth:执行分裂,将子节点加入队列
- 对于每个叶子 $j$:$w_j^* \leftarrow -\frac{G_j}{H_j + \lambda}$
- 对于队列中每个节点:
- 更新预测(带shrinkage):$\hat{y}_i \leftarrow \hat{y}_i + \eta \cdot f_t(x_i)$,对所有 $i$
- 计算梯度统计量:
- 输出:最终模型 $F(x) = b_0 + \eta \sum_{t=1}^T f_t(x)$(输出的是 margin,分类任务还要经过 sigmoid / softmax 变换)
6.11 自定义目标函数示例
XGBoost支持自定义目标函数,只需返回每个样本的 $g_i$ 和 $h_i$。原生接口通过 xgb.train(..., obj=函数) 传入,函数签名为 (preds, dtrain),其中 preds 是未经变换的 margin:
| |
关于这个 Huber 示例 Huber 损失在 $\lvert \text{diff} \rvert > \delta$ 的区域二阶导为 0,这些样本对 $H_j$ 没有贡献:叶子权重 $-\frac{G_j}{H_j+\lambda}$ 可能很大,节点也容易因为 $H$ 小于
min_child_weight而无法分裂。实践中常改用二阶可导的 Pseudo-Huber 损失,XGBoost 已内置为objective='reg:pseudohubererror'(阈值参数huber_slope)。sklearn 接口也可以直接传objective=可调用对象,此时签名为(y_true, y_pred)。
6.12 详细注释的Python代码示例
| |
