04b · XGBoost 的推导：从负梯度到闭式解

⏱ 52 分钟 ｜ ⭐⭐ 上一章的「为什么」——Kaggle 主力算法的引擎室

🎯 一句话

XGBoost 只做了一件事：把「下一棵树该怎么长」从一堆手工规则，改写成一个能求出闭式解的目标函数。 一旦目标函数写对了，最优叶子权重、分裂增益、预剪枝、缺失值处理全都是它的推论——LightGBM 和 CatBoost 后来所有的优化，也都挂在这两个公式上。

📍 你是从哪来的：04 章停在「GBDT 的每棵新树拟合损失函数的负梯度」。 这一章只是接着往下问一句：负梯度只告诉你往哪个方向走，那到底该走多远？ ⚠️ 没读过 04 章就先回去——这里默认你已经知道 Boosting 是串行纠错、GBDT 家族的树都是 CART 回归树、learning_rate 和树数是一对。

🎁 这一章可以跳吗：只想会用 → 可以跳，去 Kaggle 第 1 章按模板调参就行。 但如果你要面试、或者要自定义损失函数、或者想知道 LightGBM 凭什么快 —— 答案全在这一章，别处没有。

🧮 一、XGBoost 到底改了 GBDT 的什么

「每棵新树拟合负梯度」这句话是对的，但它只讲了一半：

梯度告诉你往哪个方向走，没告诉你该走多远。

GBDT 的做法是用 learning_rate 这个人工旋钮把步子统一压小——小步慢走，绕开了这个问题，而不是解决它。XGBoost 补上的就是缺的那一半。

先给直觉：一阶导给方向，二阶导给步长

⭐ 一句话： 一阶导（斜率）告诉你「往哪边走」，二阶导（曲率）告诉你「这个方向该迈多大步」。 坡陡但马上要拐弯 → 小步试探；坡缓而且笔直很远 → 可以大胆迈。

这正是梯度下降 vs 牛顿法的差别：梯度下降只知道方向，步长得你自己调；牛顿法多用一个二阶导，步长是算出来的。XGBoost 把这一招搬进了 Boosting。

第一步：把正则项写进目标函数

训练第 $t$ 棵树时，模型的预测是「前面所有树的和 + 这棵新树」：

$$\text{Obj}^{(t)}=\sum_{i=1}^{n} l\big(y_i,\ \hat y_i^{(t-1)}+f_t(x_i)\big)+\Omega(f_t),\qquad \Omega(f)=\gamma T+\frac{1}{2}\lambda\sum_{j=1}^{T}w_j^2$$

• $T$ = 这棵树有几个叶子，$w_j$ = 第 $j$ 个叶子输出的值
• $\gamma$ = 每多长一个叶子要交的「入场费」
• $\lambda$ = 叶子权重的 L2 惩罚（就是第 3 章那个 L2，只不过惩罚对象换成了叶子的输出值）

⭐ 这一步就已经和 GBDT 分岔了：GBDT 的正则（树深、最小样本数、事后剪枝）是长树时另外加的外挂规则，不在目标函数里；XGBoost 直接把它写进了要优化的式子。

第二步：二阶泰勒展开

$f_t(x_i)$ 是待求的未知量，套在损失函数 $l$ 里面没法直接优化。泰勒展开就是干这个用的：把 $f_t(x_i)$ 当成一个「小增量」，在 $\hat y^{(t-1)}$ 这一点把损失展成多项式。记：

$$g_i=\frac{\partial\, l(y_i,\hat y^{(t-1)})}{\partial\, \hat y^{(t-1)}}\ (\text{一阶}),\qquad h_i=\frac{\partial^2 l(y_i,\hat y^{(t-1)})}{\partial\, (\hat y^{(t-1)})^2}\ (\text{二阶})$$

展开到二阶，再扔掉与 $f_t$ 无关的常数项 $l(y_i,\hat y^{(t-1)})$：

$$\text{Obj}^{(t)}\approx\sum_{i=1}^{n}\Big[\,g_i\, f_t(x_i)+\tfrac{1}{2}h_i\, f_t(x_i)^2\,\Big]+\gamma T+\frac{1}{2}\lambda\sum_j w_j^2$$

⭐ 停下来看看这一步换到了什么：式子里再也没有 $l$ 了，只剩 $g_i$、$h_i$ 两串数。也就是说——你换任何损失函数，只要它二阶可导，后面的推导一个字都不用改。这就是 XGBoost 能让你自定义 objective（只要求你提供 g 和 h 两个函数）的原因，也是「为什么用二阶展开」最实在的一条回答。

第三步：从「每个样本」归并到「每个叶子」

树是分段常数函数：落进同一个叶子的样本，输出值完全一样。所以按叶子把样本归并，记 $I_j$ 为落进叶子 $j$ 的样本集合，$G_j=\sum_{i\in I_j}g_i$，$H_j=\sum_{i\in I_j}h_i$：

$$\text{Obj}^{(t)}=\sum_{j=1}^{T}\Big[\,G_j w_j+\tfrac{1}{2}(H_j+\lambda)w_j^2\,\Big]+\gamma T$$

⭐ 这是整套推导的关键一步：$T$ 个叶子的项互相独立了。每个叶子单独看就是一条开口向上的抛物线（开口向上是因为 $H_j+\lambda>0$），可以各求各的最小值。

第四步：顶点公式一代，两个闭式解就出来了

一元二次 $aw^2+bw$ 的顶点在 $w=-\frac{b}{2a}$，直接套：

$$w_j^{*}=-\frac{G_j}{H_j+\lambda}\qquad\text{（最优叶子权重）}$$

代回目标函数：

$$\text{Obj}^{*}=-\frac{1}{2}\sum_{j=1}^{T}\frac{G_j^{2}}{H_j+\lambda}+\gamma T\qquad\text{（结构分数）}$$

⭐ 「结构分数」（structure score）就是：给定一棵树长成什么样，它到底有多好——一个数字说了算，越小越好。 XGBoost 里所有关于「要不要这么分」的决定，裁判都是它。

💡 拿 MSE 验一下这两个公式：$l=\frac12(y-\hat y)^2$ 时 $g_i=\hat y_i-y_i$（就是负残差），$h_i=1$，于是

$$w_j^{*}=\frac{\sum_{i\in I_j}(y_i-\hat y_i)}{n_j+\lambda}=\frac{\text{这个叶子里残差的和}}{\text{样本数}+\lambda}$$

$\lambda=0$ 时就是残差的平均值——正是 GBDT 在做的事。⭐ 所以在 MSE 下 XGBoost 和 GBDT 是同一个东西；差别全在别的损失上（logloss、pairwise 排序、Poisson、你自己写的……）。

第五步：分裂增益——预剪枝直接长在判据里

把一个叶子拆成左右两个，收益就是拿新的结构分数减旧的：

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

三点必须读出来：

和 GBDT 到底差在哪：三条

⭐ 「为什么二阶收敛更快」的答案在这： 一阶方法只知道方向，步长要靠 learning_rate 试； 二阶方法把每个叶子的最优步长直接解出来（$-G_j/(H_j+\lambda)$ 就是一步牛顿法）。 同样的树数下，走对步长的那个当然降得更多。 ⚠️ 但别把这句话说过头：learning_rate 在 XGBoost 里照样要调、默认照样是 0.1。二阶解出来的是「这一步理论上的最优」，仍然要打个折才不会过拟合。

顺带解决的两个工程问题

① 缺失值：不填，而是学一个「默认方向」 ⭐

XGBoost 不给你填缺失值。它在每一个候选分裂点上，把缺失样本先全扔左边算一次 Gain、再全扔右边算一次，哪边 Gain 大就把这个分裂点的「默认方向」定成哪边。

💡 所以缺失不是被猜出来的，是被当成一种信息学出来的（「这个字段为空」本身常常就是强信号——第 16 章那条 income_missing、附录 B 那条 amt_missing，都是同一个道理）。这套机制顺带让它在 one-hot 之后的稀疏矩阵上也跑得快：0 可以和缺失一样被跳过。

② 不试遍所有切分点：加权分位数草图

⚔️ 二、XGBoost / LightGBM / CatBoost：各自在优化哪一段

三者都是 GBDT 的工业级实现：

🔑 实用建议：大数据/要快 → LightGBM；类别特征多 → CatBoost；不确定 → 先 LightGBM。 三者精度差距通常在 0.1–0.5% 以内，选型不如调参和特征工程重要。

有了上一节，这张表就能从「结论」读成「为什么」了

⭐ 三者的目标函数是同一个（都是「二阶展开 + 正则 + 结构分数」那一套）。它们的区别在于各自在优化训练流程的不同段：

LightGBM 的三板斧（「为什么最快」的答案）：

• ⭐ 直方图算法：把连续特征预先分成 255 个 bin（一个 uint8 装得下）。找分裂点的复杂度从「O(样本数 × 特征数)」降到「O(bin 数 × 特征数)」，内存也降一个数量级。再加一个直方图做差——一个节点的两个孩子，算完左边直接用「父 − 左 = 右」拿到右边，省掉一半计算。
• GOSS（单边梯度采样）：梯度大的样本 = 还没学好的样本，全留；梯度小的随机采一部分，并把它们的权重放大补偿（不放大分布就偏了）。
• EFB（互斥特征捆绑）：one-hot 之后大量特征不会同时非零，把这些互斥的特征捆成一个存，特征数直接掉一大截。

⚠️ leaf-wise 的代价：同样的叶子数下它降损失更多，但树会长得又深又不平衡，小数据集上极易过拟合。刹车是 num_leaves（别超过 $2^{\texttt{max\_depth}}$）和 min_data_in_leaf。这就是那张表里「需注意」三个字背后的机理。

CatBoost 在防的是另一件事：普通的目标编码（拿这个类别的历史平均标签当特征）用到了当前样本自己的标签——这就是第 16 章讲的目标泄漏。CatBoost 的 ordered target statistics（有序目标编码） 先给样本安排一个随机顺序，算某个样本的编码时只用排在它前面的样本，从结构上把泄漏堵死。同样的思路用在 boosting 上就是 ordered boosting，防的是「同一批数据既用来算残差又用来拟合残差」带来的预测偏移。

⭐ 对称树（oblivious tree）：同一层所有节点共用一个 (特征, 阈值)。整棵树因此退化成一张 $2^{\text{depth}}$ 的查找表，推理快得离谱（几条位运算就定位到叶子）；而且这个限制本身就是很强的正则——这是 CatBoost「默认参数最好用」的一部分原因。

🔑 一句话版本（可以直接当面试答案）： XGBoost 定义了这套框架（二阶展开 + 正则进目标函数 + 结构分数）； LightGBM 优化「怎么算得更快」（直方图 + 做差 + GOSS + EFB + leaf-wise）； CatBoost 优化「怎么不泄漏」（有序目标编码 + ordered boosting + 对称树）。 三者精度差距通常 0.1–0.5%，所以才说选型远不如调参和特征工程重要。

🔗 这一章连到哪里

✅ 检查点

1. XGBoost 为什么要做二阶泰勒展开？只用一阶（GBDT）差在哪？
2. 二阶展开之后，目标函数里还剩下什么？这件事带来了哪个直接的工程好处？
3. 写出最优叶子权重和分裂增益，并说出 $\gamma$ 和 $\lambda$ 各在管什么。
4. 用 MSE 损失时 XGBoost 的叶子权重退化成什么？这说明了什么？
5. XGBoost 怎么处理缺失值？
6. LightGBM 凭什么快（说出三样）？leaf-wise 的代价是什么、拿什么刹车？
7. CatBoost 的「有序目标编码」在防什么？对称树带来哪两个好处？

🛑 可以停在这里

⚡ 走神救援

补的是 04 章缺的那半句：⭐负梯度只给方向，不给步长——GBDT 用 learning_rate 统一压小步子，是绕开不是解决。⭐一阶导给方向、二阶导给步长（坡陡要拐弯就小步，坡缓笔直就大胆迈），即梯度下降 vs 牛顿法。六步推导：① 正则写进目标函数 Obj = Σl(y, ŷ+f) + γT + ½λΣw²（γ＝每多一个叶子的入场费，λ＝叶子权重的 L2；⭐GBDT 的正则是长树时另加的外挂规则、不在目标函数里，这一步就分岔了）；② 二阶泰勒展开扔掉常数项，⭐式子里再也没有 l 了，只剩 g 和 h——换任何二阶可导的损失推导一字不改，这就是自定义 objective 只要你给 g 和 h 的原因；③ 树是分段常数，按叶子归并成 Gⱼ、Hⱼ，⭐T 个叶子的项互相独立了；④ 每个叶子是开口向上的抛物线（H+λ>0），顶点公式一代，w*＝−G/(H+λ)；⑤ 代回去得结构分数 Obj*＝−½ΣG²/(H+λ)+γT，⭐给定树结构一个数字说了算，越小越好；⑥ 分裂增益＝左分数+右分数−不拆的分数−γ：中括号里是「纯度提升」的 XGBoost 版（量的是目标函数真降了多少）、⭐Gain 为负就不分裂＝预剪枝写进判据、λ 在分母＝叶子样本少就把权重往 0 拽。💡MSE 验算：g＝ŷ−y、h＝1，w* 退化成残差平均值——正是 GBDT 在做的事，所以 MSE 下两者等价，二阶的价值全在别的损失上。⚠️别说过头：learning_rate 照样要调、默认照样 0.1。缺失值：不填，每个分裂点把缺失全扔左、全扔右各算一次 Gain，哪边大就定哪边当默认方向。加权分位数：目标函数能配方成以 h 为权的加权平方误差，所以候选点按 h 的分位数取。⭐三巨头目标函数同源，各优化一段：XGBoost 定义框架；LightGBM 优化「算得快」——255 个 bin 的直方图把复杂度从 O(样本×特征) 降到 O(bin×特征)、做差「父−左＝右」省一半、GOSS、EFB、leaf-wise（⚠️小数据极易过拟合，刹车是 num_leaves 和 min_data_in_leaf）；CatBoost 优化「不泄漏」——有序目标编码只用排在前面的样本、ordered boosting、对称树退化成 2^depth 查找表所以推理极快，本身也是强正则。⭐三者精度差 0.1–0.5%，选型远不如调参和特征工程重要。

下一节 👉 05-评估与过拟合.md ⭐⭐⭐ 全教程最重要的一章