梯度提升 — 算法 — 计算机科学

2001 年，斯坦福大学教授杰罗姆·弗里德曼（Jerome Friedman）发表论文《贪婪函数近似：梯度提升机》，将函数空间的梯度下降与集成学习结合，创造了梯度提升（Gradient Boosting）框架。此后，以此为基础的 XGBoost（2016）、LightGBM（2017）和 CatBoost（2017）横扫了数据科学竞赛——在 Kaggle 上，每年大量冠军方案的核心都是梯度提升树。

破除误解：提升不是更强的随机森林

随机森林和梯度提升都用决策树作为基础元件，但策略根本不同：

随机森林（Bagging）：并行训练大量独立的树，用多样性减少方差。
梯度提升（Boosting）：串行训练树，每棵树专门修正前面所有树的错误，用迭代减少偏差。

随机森林的树互相独立；梯度提升的树高度依赖——每棵树都是针对"当前模型的残差"训练的。

核心思想：在函数空间做梯度下降

弗里德曼的关键洞见：把集成模型 $F(x) = \sum_m h_m(x)$ 看作函数空间中的一个点，每次迭代添加一个新函数 $h_m$ ，方向是损失函数对当前模型的负梯度。

这与参数空间的梯度下降完全类比：

参数空间梯度下降	函数空间梯度提升
参数向量 $\theta$	函数 $F(x)$
参数梯度 $\nabla_\theta L$	函数梯度（伪残差） $r_i$
参数更新步	添加弱学习器 $h_m$
学习率 $\eta$	收缩率 $\nu$ （Shrinkage）

标准梯度提升算法

算法框架（以均方误差回归为例）：

初始化：F_0(x) = 常数（如目标均值）
对 m = 1, 2, ..., M：
  计算伪残差：r_i = -[∂L(y_i, F(x_i)) / ∂F(x_i)]
                  （对 MSE：r_i = y_i - F_{m-1}(x_i)）
  训练一棵回归树 h_m 来拟合伪残差 {r_i}
  通过线搜索确定最优步长 γ_m
  更新：F_m(x) = F_{m-1}(x) + ν · γ_m · h_m(x)
输出：F_M(x)
```

伪残差是损失函数对模型输出的负梯度。对均方误差 $L = (y - F)^2 / 2$ ，负梯度恰好是残差 $y_i - F(x_i)$ ，这就是"残差拟合"这一说法的来源。但梯度提升框架更通用——对任意可微损失函数都适用，包括分类的对数损失、排序的损失等。

值得点明的是："拟合残差"只是均方误差下的巧合。换成二分类的对数损失，令 $p = \sigma(F)$ ，伪残差变成 $y_i - p_i$ ——形式上仍像"残差"，但它是概率之差而非数值之差；换成排序损失或分位数损失，伪残差就完全不长残差的样子了。把梯度提升理解成"一棵接一棵拟合残差"，会在换损失函数时立刻卡住；理解成"在函数空间沿负梯度走"，则任何可微损失都是同一套流程。

手算一轮：数字比公式清楚

四个样本，特征 $x$，标签 $y$：

$x$	1	2	3	4
$y$	10	12	20	24

第 0 步： $F_0 = \bar{y} = 16.5$ 。此时平方误差总和 $= 6.5^2 + 4.5^2 + 3.5^2 + 7.5^2 = 131$ 。

第 1 步：伪残差（MSE 下即残差） $r = [-6.5,\ -4.5,\ +3.5,\ +7.5]$ 。用一棵深度 1 的树（只切一刀）去拟合它。在 $x \le 2$ 处切开最划算：

左叶：$(-6.5 + -4.5)/2 = -5.5$
右叶：$(3.5 + 7.5)/2 = +5.5$

更新（收缩率 $\nu = 0.1$ ）：

$F_1(x) = 16.5 + 0.1 \times h_1(x) \Rightarrow \begin{cases} 16.5 - 0.55 = 15.95 & x \le 2 \\ 16.5 + 0.55 = 17.05 & x > 2\end{cases}$

新的平方误差总和 $= 5.95^2 + 3.95^2 + 2.95^2 + 6.95^2 = 108.01$ 。

一轮下来，131 → 108.01，降了 17.6%。注意那棵树本身给出的修正量是 $\pm 5.5$ ，但我们只采纳了 $\pm 0.55$ ——九成的修正被主动扔掉了。这就是收缩率的含义：不相信任何单棵树，让上百棵树各出一点力。所以"学习率小 + 树多"比"学习率大 + 树少"泛化更好，也所以梯度提升的训练时间是它的固有代价，不是实现不够优化。

XGBoost 的真正内核：二阶展开

前面弗里德曼的框架只用了一阶梯度。XGBoost 的数学起点是把损失做二阶泰勒展开——这是它比早期实现更快更稳的根源，也是很多教程漏掉的部分。

记当前预测下每个样本的一阶、二阶导数：

$g_i = \frac{\partial l(y_i, \hat{y}_i)}{\partial \hat{y}_i}, \qquad h_i = \frac{\partial^2 l(y_i, \hat{y}_i)}{\partial \hat{y}_i^2}$

（对 MSE： $g_i = \hat{y}_i - y_i$ ， $h_i = 1$ ；对对数损失： $g_i = p_i - y_i$ ， $h_i = p_i(1-p_i)$ 。）

第 $t$ 轮的目标近似为

$\tilde{\mathcal{L}}^{(t)} = \sum_i \left[g_i f_t(x_i) + \tfrac12 h_i f_t(x_i)^2\right] + \gamma T + \frac{\lambda}{2}\sum_j w_j^2$

树结构一旦固定，这就是每片叶子上一个独立的一元二次函数。令 $G_j = \sum_{i \in I_j} g_i$ 、 $H_j = \sum_{i \in I_j} h_i$ （ $I_j$ 是落到叶 $j$ 的样本集），直接求导取零即得叶权重的闭式解：

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

代回去，这棵树的"结构得分"是

$\tilde{\mathcal{L}}^* = -\frac12 \sum_{j=1}^{T} \frac{G_j^2}{H_j + \lambda} + \gamma T$

于是分裂增益有了精确表达式——切一刀值不值，直接算：

$\text{Gain} = \frac12\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$

这个式子有三件事同时发生：

叶权重不再靠线搜索猜，有解析解，一步到位。
正则化直接进了分裂判据。 $\lambda$ 惩罚权重幅度、 $\gamma$ 是"每多切一刀必须挣回这么多分"的门槛——增益减去 $\gamma$ 若为负就不切。这不是事后剪枝，是建树时就在算是否值得。
$h_i$ 成了样本权重。 $h_i = p(1-p)$ 在 $p \approx 0.5$ （模型最不确定的样本）时最大，在 $p \approx 0$ 或 $1$ 时趋零。二阶信息自动把注意力放在难分样本上——这一层自适应，纯一阶方法拿不到。

现场：一场物理竞赛让它出圈

上面这套数学写在 2016 年 KDD 的论文里，但 XGBoost 的成名要早两年，而且不在机器学习圈。

2014 年，欧洲核子研究中心（CERN）的 ATLAS 实验把一批模拟碰撞数据放上 Kaggle，办了「希格斯玻色子机器学习挑战赛」——任务是从海量背景事件里筛出希格斯玻色子衰变的信号。这是个典型的表格数据 + 极度不平衡 + 特征有物理含义的问题，正好是提升树的主场。

陈天奇当时开发 XGBoost 的动机很朴素：他自己的研究代码太慢了。他和何通（Tong He）组成的 Crowwork 队用它参赛，最终成绩 3.72，略低于冠军 Gábor Melis 的 3.81，但拿下了大会专设的「高能物理 × 机器学习」奖——评委给的理由是：这个方案在性能与简洁性之间取得了极好的平衡，并且有望改进高能物理界当时在用的工具。

比奖项更重要的是副作用：竞赛期间大量参赛者（包括排名靠前的队伍）都换用了这个工具，XGBoost 从一份命令行研究代码变成了有 Python / R 封装的开源库。此后十年，Kaggle 上表格数据类比赛的冠军方案里几乎总能看到它。

一个值得注意的对照：同期深度学习正在 ImageNet 上狂飙，但在这类结构化表格数据上，胜出的是一个把决策树串起来的方法。这不是巧合，后面「代价与争议」会回到这一点。

XGBoost 与后继者：工程如何决定成败

陈天奇 2016 年在 KDD 发表的 XGBoost 论文，一半篇幅在讲上面那套二阶数学，另一半在讲怎么让它在真实硬件上跑得快——后者同样是它胜出的原因：

近似分裂点（Weighted Quantile Sketch）：不穷举每个特征的每个取值，而是按 $h_i$ 加权取分位点作为候选切点。候选从上百万降到几百个，精度几乎不损。
稀疏感知的缺失值处理：每个节点学一个「默认方向」，缺失样本整批走默认边。这意味着缺失值不需要预先填补——在真实业务数据里省掉一整个预处理环节。
列块（Column Block）：数据按列预排序并压缩存储，一次排序供所有树复用，把建树中最贵的排序开销从每轮一次降到全程一次。
缓存感知的梯度访问：预取 $g_i, h_i$ 到连续缓冲区，避免按行索引跳着取梯度造成的缓存缺失。

LightGBM（微软，2017）换了两个思路：GOSS（基于梯度的单边采样）保留大梯度样本、对小梯度样本随机抽样，因为已经拟合得好的样本对下一棵树信息量低；EFB（互斥特征捆绑）把几乎不同时非零的稀疏特征打包成一个，直接降低特征维度。它还把 XGBoost 的按层生长（level-wise）换成按叶生长（leaf-wise）——每次只分裂增益最大的那片叶子，同样的叶子数下损失降得更多，但树更不平衡、更易过拟合，所以必须配合 num_leaves 上限。

CatBoost（Yandex，2017）解决的是另一个更隐蔽的问题：目标泄漏。传统做法把类别特征换成「该类别下标签的平均值」，但这个平均值用到了当前样本自己的标签，模型在训练集上看到的统计量比测试时更「准」，导致预测偏移（prediction shift）。CatBoost 的有序提升（Ordered Boosting）给样本一个随机顺序，计算每个样本的目标统计量时只用排在它前面的样本——相当于给每个样本造一个「不含自己」的历史。这是三者中唯一在统计正确性上而非速度上做的改进。

实战调参要点

梯度提升对超参数比随机森林敏感得多：

超参数	作用	典型范围
`n_estimators`	树的数量	100–10000
`learning_rate`	收缩率 $\nu$	0.01–0.3（与树数量反比）
`max_depth`	每棵树的深度	3–8
`subsample`	行采样比例	0.5–0.9
`colsample`	列采样比例	0.5–0.9
`lambda`, `alpha`	L2/L1 正则化	依问题调整

经验法则：学习率小，树数量多，通常比学习率大、树数量少更好，但训练更慢。早停（Early Stopping）用验证集误差自动确定最优树数量。

代价与争议

串行训练，不易并行：每棵树依赖前一棵，树的生成本质上是串行的（虽然每棵树内部的节点分裂可以并行）。这使得梯度提升训练比随机森林慢。

过拟合风险：学习率过大或树太多太深，梯度提升很容易过拟合。需要仔细调参或使用早停。

不适合流式数据：串行依赖使在线学习困难，而随机森林更易扩展到流式设置。

可解释性有限：虽有特征重要性和 SHAP 值（SHapley Additive exPlanations），但预测过程仍然是黑盒。更麻烦的是内置的「特征重要性」有已知偏差——按分裂次数或增益统计，会系统性偏爱高基数（取值多）的特征，因为它们有更多切点可选。SHAP（Lundberg & Lee, 2017）用博弈论的 Shapley 值给出公理化的贡献分配，是目前更可信的解释工具，代价是计算量大得多。

一场没结束的争议：它凭什么还没被深度学习取代？

2012 年之后，深度学习在图像、语音、文本上依次全面胜出，于是「表格数据也终将属于神经网络」成了一种默认预期。十几年过去了，这件事没有发生。

Grinsztajn、Oyallon 与 Varoquaux 在 NeurIPS 2022（Datasets & Benchmarks 赛道）做了一次口径严格的基准测试：45 个具备典型表格数据特征的数据集，对树模型与多种（含最新）深度模型都做同等预算的超参数搜索。结论是在中等规模数据（约 1 万样本量级）上树模型仍是最优，而且这个结论在不计入树模型明显更快的训练速度时就已成立。

他们进一步给出了归因——差别在归纳偏置：

神经网络倾向于学平滑函数，而表格数据里的真实规律常常是不平滑的阶跃（「年龄满 18」「余额低于 0」），树天生就在拟合阶跃。
表格数据里存在大量无信息特征，树的分裂判据会直接不选它们，MLP 却会被它们干扰。
树对特征的单调变换不敏感（只看排序），而神经网络对量纲与旋转敏感；表格数据的列各自有独立含义，「旋转不变性」在这里是缺点而不是优点。

这场争议仍在推进——TabPFN 一类基于先验拟合的 Transformer 在小样本上已展示出竞争力。但目前的诚实表述是：在表格数据上，梯度提升树不是「还没被取代的旧方法」，而是与数据结构匹配得更好的方法。

跨域连接

最优化：把集成模型看作函数空间里的一个点，每加一棵树就是沿负梯度走一步，收缩率就是学习率。"拟合残差"只是平方损失下的巧合——换成对数损失，伪残差变成概率之差；换成分位数损失就完全不像残差了。理解成函数空间的梯度下降，任何可微损失都是同一套流程；理解成拟合残差，一换损失就卡住。
随机森林：并行集成靠误差不相关降方差，串行提升靠逐步修正降偏差，两者的树因此性质相反——前者要互相独立，后者高度依赖前面所有树。可检验的后果很干脆：加树对随机森林几乎无害，对提升树则会过拟合，所以后者必须配早停与收缩率，而前者不必。
博弈论：贡献分配用的是合作博弈里的沙普利值，有效性、对称性、虚拟性与可加性四条公理唯一确定了这个方案。唯一性定理正是它比内置特征重要性可信的原因：后者按分裂次数或增益统计，会系统性偏爱取值多的特征，因为它们可选的切点更多。代价是精确计算的开销随特征数爆炸。
计量经济学基础：树的集成擅长拟合阶跃与高阶交互，却给不出可解释的边际效应。预测精度与因果参数是两个目标：前者只要求条件期望拟合得好，后者要求系数在干预下依然成立。把特征重要性读成"影响大小"，等于用相关性冒充因果，而模型从未被要求识别后者。
粒子加速器：探测器的事件筛选是典型的表格数据加极端不平衡，信号事件比例极低，而每个特征都有明确的物理含义。它在这里胜过黑箱网络的理由不只是精度——判据可以逐条审查、可以与已知的物理选择条件对照，而实验结论必须经得起这种复核。归纳偏置匹配加上可审查性，才是它留下来的原因。

参考文献

Friedman, J. H. Greedy Function Approximation: A Gradient Boosting Machine. Annals of Statistics 29(5), 1189–1232 (2001).
Chen, T. & Guestrin, C. XGBoost: A Scalable Tree Boosting System. KDD 2016. arXiv:1603.02754.（二阶展开、叶权重闭式解、分裂增益与工程优化）
Chen, T. & He, T. Higgs Boson Discovery with Boosted Trees. JMLR W&CP vol. 42, 69–80 (2015).（希格斯挑战赛方案）
Ke, G. et al. LightGBM: A Highly Efficient Gradient Boosting Decision Tree. NeurIPS 2017.（GOSS 与 EFB）
Prokhorenkova, L. et al. CatBoost: unbiased boosting with categorical features. NeurIPS 2018. arXiv:1706.09516.（有序提升与预测偏移）
Lundberg, S. M. & Lee, S.-I. A Unified Approach to Interpreting Model Predictions. NeurIPS 2017.
Grinsztajn, L., Oyallon, E. & Varoquaux, G. Why do tree-based models still outperform deep learning on typical tabular data? NeurIPS 2022, Datasets & Benchmarks Track.
Freund, Y. & Schapire, R. E. A Decision-Theoretic Generalization of On-Line Learning and an Application to Boosting. Journal of Computer and System Sciences 55(1), 119–139 (1997).

破除误解：提升不是更强的随机森林#

核心思想：在函数空间做梯度下降#

标准梯度提升算法#

手算一轮：数字比公式清楚#

XGBoost 的真正内核：二阶展开#

现场：一场物理竞赛让它出圈#

XGBoost 与后继者：工程如何决定成败#

实战调参要点#

代价与争议#

跨域连接#

参考文献#

延伸阅读#