04B / XGBOOST · 先理解,再推导
先知道树为什么要长,
再决定要不要看推导。
一个叶子该改多少,什么时候值得分?
先看一个叶子怎么修正预测,再看一次分裂值不值得。
沿二阶近似推到叶值与分裂收益,知道每次除法和最优性结论需要哪些条件。
你先带走这句就够了
叶子算改多少,
Gain 算值不值得分。
把同一叶子的样本汇总起来,就能把“怎么长树”变成可以比较的数。
- 1先汇总
把样本的斜率 g 和曲率 h,加成叶子的 G、H。
- 2再算收益
比较分裂前后,目标函数能减少多少。
- 3最后选一刀
在约束允许时,选净收益最大的候选切分。
01 / 一个看得见的例子
一个叶子,4 个样本
使用半平方误差损失,g 是预测值减真实值,h = 1。
总梯度 G = 0−3 − 1 + 2 + 2 = 0
总曲率 H = 41 + 1 + 1 + 1 = 4
方向互相抵消:四个样本共用一个输出时,最佳修正为 0。分开之后呢?
02 / 叶子该改多少
最优叶子输出 w*
固定叶子里的样本,找让二阶近似目标最小的输出。
点公式里的 G、H、λ 或 w*,看它在这一步的作用。
- G:叶内斜率的总和,决定修正方向。
- H:叶内曲率的总和,影响修正幅度。
- λ:压小过大的叶子输出。
本例取 λ = 1,得到 w* = 0。同一个叶子无法同时满足相反的修正方向。
03 / 这一刀值不值得
分裂增益 Gain
比较“左右分开修正”和“仍然共用一个输出”,再扣掉新叶子的成本。
读法:½ ×(左叶改善 + 右叶改善 − 原叶改善)− 新叶成本。
G = −4,H = 2
输出约 +1.33
G = +4,H = 2
输出约 −1.33
取 λ = 1、γ = 0.5
这次切分有正的净收益
原先抵消的方向被分开了。满足深度、叶子样本数等约束时,这是一刀值得考虑的切分。
04b · XGBoost 的推导:从负梯度到闭式解
⏱ 52 分钟 | 🔬 进阶 · 可跳过 | ⭐⭐ 上一章的「为什么」——Kaggle 主力算法的引擎室
前置:02a(梯度、学习率)和 04a(GBDT)。会看图就够,泰勒展开不需要会推。跳过本页不影响 05 及之后的章节。
🎯 一句话
XGBoost 只做了一件事:把「下一棵树该怎么长」从一堆手工规则,改写成一个能求出闭式解的目标函数。 一旦目标函数写对了,最优叶子权重、分裂增益、预剪枝、缺失值处理全都是它的推论——LightGBM 和 CatBoost 后来所有的优化,也都挂在这两个公式上。
📍 你是从哪来的:04 章停在「GBDT 的每棵新树拟合损失函数的负梯度」。 这一章只是接着往下问一句:负梯度只告诉你往哪个方向走,那到底该走多远? ⚠️ 没读过 04a《集成学习与GBDT》就先回去——这里默认你已经知道 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$ 两串数。也就是说——对满足支持条件的可加、光滑损失,可套用这个局部二阶形式;叶子最小值还要求 H+λ>0。这就是 XGBoost 能让你自定义 objective(提供梯度与 Hessian,还需满足凸性等支持约束)的原因,也是「为什么用二阶展开」最实在的一条回答。
第三步:从「每个样本」归并到「每个叶子」
树是分段常数函数:落进同一个叶子的样本,输出值完全一样。所以按叶子把样本归并,记 $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 在做的事。⭐ 在相同树结构、半平方损失且 λ=0 等条件下,两者叶子值都可取残差均值;这不代表正则、分裂、采样等实现完全等价。
第五步:分裂增益——预剪枝直接长在判据里
把一个叶子拆成左右两个,收益就是拿分裂前的目标减分裂后的目标:
$$\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$$
三点必须读出来:
| 看哪一部分 | 它在说什么 |
|---|---|
| 中括号里 = 左分数 + 右分数 − 不拆的分数 | ⭐ 这就是「纯度提升」的 XGBoost 版——只不过量的不再是纯度,而是目标函数真正降了多少 |
| $-\gamma$ | 每多一个叶子固定扣 $\gamma$ 分。⭐ Gain 为负就别分——预剪枝直接写在判据里,不是长完再剪 |
| $\lambda$ 在分母 | 叶子里样本少($H$ 小)时,$\lambda$ 把权重往 0 拽。样本越少越不敢给大值——天然的收缩 |
图内可左右滑动;需要时可放大阅读。
和 GBDT 到底差在哪:三条
| 传统 GBDT | XGBoost | |
|---|---|---|
| 分裂判据 | 用负梯度当「伪残差」,再拿平方误差准则长一棵回归树去拟合它——是个代理目标 | 直接对真实目标(含正则)二阶展开,判据就是目标函数的下降量,没有代理 |
| 叶子值 | 树长完之后,对每个叶子再做一次一维线搜索补上 | 和分裂判据出自同一个闭式解 $-G/(H+\lambda)$,一步到位 |
| 正则 | 树深 / 最小样本数 / 事后剪枝这些外挂规则 | $\gamma$、$\lambda$ 在目标函数里,分裂那一刻就在算 |
⭐ 「为什么二阶收敛更快」的答案在这: 传统 GBDT 可在拟合方向后做线搜索或叶子值优化;
二阶方法把每个叶子的最优步长直接解出来($-G_j/(H_j+\lambda)$ 就是一步牛顿法)。 二阶近似提供一种候选更新;同样树数下的真实损失和验证效果仍需比较。 ⚠️ 但别把这句话说过头:learning_rate在 XGBoost 里照样要调、这里的 0.1 是示例值;官方 eta 默认值为 0.3,仍应验证调参。二阶解出来的是「当前正则化二阶近似的最优」,常结合收缩控制更新幅度,但不能保证不会过拟合。
顺带解决的两个工程问题
① 缺失值:不填,而是学一个「默认方向」 ⭐
XGBoost 不给你填缺失值。它在每一个候选分裂点上,把缺失样本先全扔左边算一次 Gain、再全扔右边算一次,哪边 Gain 大就把这个分裂点的「默认方向」定成哪边。
💡 所以缺失不是被猜出来的,是被当成一种信息学出来的(「这个字段为空」本身常常就是强信号——第 16 章那条 income_missing、附录 B 那条 amt_missing,都是同一个道理)。这套机制顺带让它在 one-hot 之后的稀疏矩阵上也跑得快:0 可以和缺失一样被跳过。
② 不试遍所有切分点:加权分位数草图
📐 为什么候选分位点要用 h 加权(想看再点)
精确贪心要把每个特征的每个取值都当候选切分点试一遍,数据一大就顶不住。近似算法改成只取若干个分位点当候选。但分位点该按什么加权? 把第 ② 步那个式子配个方:
$$\sum_i\Big[g_i f+\tfrac12 h_i f^2\Big]=\sum_i \tfrac12 h_i\Big(f-\big(-\tfrac{g_i}{h_i}\big)\Big)^2+\text{常数}$$
⭐ 右边是一个以 $h_i$ 为权重的加权平方误差——也就是说,$h_i$ 天然就是「这个样本有多重要」。所以候选点要按 $h$ 的分位数取,而不是按样本个数平均取。这就是论文里的 weighted quantile sketch。
💡 顺带解释了一个现象:logloss 下 $h=p(1-p)$,预测越靠近 0.5(越犹豫)的样本 $h$ 越大、越被当回事;已经很确定的样本 $h\to 0$,几乎不影响候选点的选取。
⚔️ 二、XGBoost / LightGBM / CatBoost:各自在优化哪一段
三者都能训练梯度提升树,但家族相同,不等于目标、建树和类别处理完全相同。上一节推导的是给定损失及正则项的 XGBoost 局部二阶目标,不是一份可原样套给三个框架的完整训练算法。
| 对照项 | XGBoost | LightGBM | CatBoost |
|---|---|---|---|
| 生长策略 | 默认 depthwise;hist/approx 也可选 lossguide | leaf-wise:选损失改善最大的叶子;设置最大深度后仍按叶生长 | 默认 SymmetricTree,同层共用分裂条件;也有 Depthwise/Lossguide |
| 类别输入 | 可指定类别 dtype、enable_categorical=True 及受支持的树方法,也可自行编码 | 指定类别特征,以类别整数编码交给原生类别分裂;不是把任意编号当连续大小 | 用 cat_features 声明类别;按配置使用内部 one-hot 或类别统计量(CTR) |
| 容量控制 | 深度/叶子数、最小 Hessian、正则与采样共同约束 | num_leaves、max_depth、min_data_in_leaf 等约束深而不平衡的树 | 深度/生长策略、叶子正则、采样等;类别处理不能代替验证与容量控制 |
| 值得试它的原因 | 二阶目标与多种树方法,方便结合约束和数据表示选择 | 直方图、做差、leaf-wise 等工程设计,值得评估训练时间与内存 | 将类别转换与树学习接在一起,类别多时值得作为候选 |
| 速度与精度 | 没有固定排名。统一训练/验证划分、指标、硬件和调参预算,再记录最好迭代数、耗时、峰值内存及验证分数;“默认参数”不等于各框架已获同等调优。 | ||
有了上一节,这张表就能从「结论」读成「为什么」了
把找切分点、长树、类别转换、boosting 更新分开看,就不会把一个机制误认成整个框架的专利:
| 优化的是哪一段 | XGBoost | LightGBM | CatBoost |
|---|---|---|---|
| 怎么找候选切分点 | exact 枚举取值;approx 按 Hessian 加权草图;hist 先建全局分箱,再累计节点直方图 | 直方图;max_bin 控制箱数,255 是常见默认上限,不是每列必须恰有255箱 | 数值特征量化后比较候选分裂;边界数等由配置决定 |
| 下一步长哪个节点 | depthwise 优先浅层节点;lossguide 优先损失改善大的叶子 | leaf-wise,并用深度/叶子/样本数约束 | 默认对称树同层共用条件;改生长策略后不再保证该结构 |
| 类别特征怎么办 | 原生类别分裂可选 one-hot 式或类别集合划分;需正确声明类型与支持配置 | 可按统计量给类别排序,再寻找类别集合划分;低基数也有 one-hot 式分裂 | 低基数可内部 one-hot;其他类别/组合可转为CTR,不是所有列都做同一种目标编码 |
| 抽样/更新是否固定 | 随目标、树方法及采样参数变化 | data_sample_strategy=goss 才启用GOSS;不能把支持它写成总是启用 | boosting_type 可为 Ordered 或 Plain,默认依设备、任务和样本量而变 |
LightGBM 的三种提速机制(不保证所有任务最快):
- 直方图与做差:对每列,建直方图仍需遍历相关样本,之后候选扫描才随箱数变化。只构建样本较少的子节点直方图,再用“父 − 子”得到另一个,减少重复遍历;这不等于端到端训练固定省一半。
- 可选GOSS:保留大梯度样本,对小梯度样本抽样并修正权重,近似维持分裂统计;它是采样选择,不是所有LightGBM训练的默认前提。
- EFB:把互斥或近似互斥的稀疏特征捆绑,减少需处理的特征表示;实际收益取决于稀疏性和冲突,不能预设固定倍数。
⚠️ leaf-wise 的代价:同样叶子数下可能更快降低训练损失,但也可能得到深而不平衡的树。联合约束 num_leaves、max_depth、min_data_in_leaf,再用验证集检查;$2^{\texttt{max\_depth}}$只是该深度二叉树的叶子数上界,不是安全的调参目标。
CatBoost的类别统计与Ordered boosting是两件相连但不同的事:有序目标统计为训练样本安排顺序,计算带标签的类别统计时只使用前面的样本并加先验,避免直接使用自身标签。Ordered boosting进一步处理boosting中的预测偏移;也可选经典的 Plain,不能只见“CatBoost”就断言启用了Ordered。两者都不保证杜绝时间穿越、错误划分等外部数据泄漏。
对称树(默认策略)同层共享分裂条件,可用每层判断组成叶子索引,并限制结构自由度。它有利于紧凑推理,但实际延迟仍要测;改成非对称策略后,不能继续沿用同样的结构解释。它也不推出“默认精度最好”。
🔑 把机制当成候选理由,把验证结果当成选择依据。XGBoost这一节帮你读懂二阶目标;LightGBM便于理解直方图、leaf-wise与可选采样;CatBoost便于理解类别统计、对称结构和可选Ordered更新。它们共享一些技术,并非互斥的三份标签。
📚 实现边界核对(官方文档)
参数与支持范围随版本变化,使用时应核对安装版本。这里依据 XGBoost参数、树方法与类别支持;LightGBM机制与参数;CatBoost生长/boosting参数、类别处理及类别统计。
🔗 这一章连到哪里
| 去哪 | 为什么要去那里 |
|---|---|
| 04 · 决策树与集成学习 | 回去看被这一章接住的那半句:GBDT 的每棵新树拟合的是负梯度,以及为什么分类也常用回归树来拟合梯度 |
| 16 · 特征工程基础 | ⭐ 那里的 OOF 目标编码同样在避免自身标签参与编码,但OOF划分与CatBoost的有序统计不是同一个算法——想真正搞懂 CatBoost 在防什么,去看那段泄漏演示 |
| 03 · 线性模型 | 目标函数里的 $\frac12\lambda\sum w_j^2$ 就是那一章的 L2 正则,只是惩罚对象从「特征权重」换成了「叶子输出值」 |
| 09 · 优化器与学习率 | 「一阶给方向、二阶给步长」这条线在那里有另一半:为什么深度学习不用二阶方法(Hessian 太大) |
| 数学原理 · 02 MAP 与正则化的真身 | $\lambda$ 不是随手加的一项,它对应一个先验分布 |
| Kaggle 第 1 章 | 推导看完了想真的去打榜:那里有 LightGBM 的实战参数模板和特征工程套路 |
✅ 检查点
共 8 题:8 道单选。点一个选项,马上显示对错并展开解析;没把握也可以直接展开解析。
单选1. XGBoost 为什么要做二阶泰勒展开?
看答案与解析
答案:A
一阶导只给方向,二阶导给步长(梯度下降 vs 牛顿法)。GBDT 是拿负梯度当伪残差、再用平方误差代理准则长一棵树去拟合,叶子值靠事后一维线搜索补上——判据和叶子值不是同一个东西;XGBoost 直接对真实目标(含正则)二阶展开,分裂判据和叶子值出自同一个闭式解。
单选2. 二阶展开之后,目标函数里每个样本只通过什么出现?
看答案与解析
答案:C
只剩 $g_i$ 和 $h_i$,损失函数 $l$ 消失了。好处:对满足可加、光滑、凸性等支持条件的损失,可以复用局部二阶形式;提供 g/h 之外仍需满足约束,闭式最小值要求 H+λ>0。(另一个好处是按叶子归并后每个叶子是抛物线,有闭式最优解。)
单选3. 最优叶子权重是哪一个?
看答案与解析
答案:B
$w_j^*=-\dfrac{G_j}{H_j+\lambda}$;$\text{Gain}=\frac12\Big[\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}\Big]-\gamma$。$\gamma$ 是每多一个叶子的入场费,所以 Gain 为负就不分裂 = 预剪枝写进了判据(不是长完再剪);$\lambda$ 在分母,叶子样本少($H$ 小)时把权重往 0 拽,是天然的收缩。
单选4. 分裂增益里的 $\gamma$ 和 $\lambda$ 各在管什么?
看答案与解析
答案:A
$w_j^*=-\dfrac{G_j}{H_j+\lambda}$;$\text{Gain}=\frac12\Big[\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}\Big]-\gamma$。$\gamma$ 是每多一个叶子的入场费,所以 Gain 为负就不分裂 = 预剪枝写进了判据(不是长完再剪);$\lambda$ 在分母,叶子样本少($H$ 小)时把权重往 0 拽,是天然的收缩。
单选5. 用 MSE 损失、$\lambda=0$ 时,XGBoost 的叶子权重退化成什么?
看答案与解析
答案:D
$g_i=\hat y_i-y_i$、$h_i=1$,$w_j^*$ 退化成这个叶子里残差的平均值($\lambda=0$ 时)——正是 GBDT 在做的事。说明 MSE 下两者等价,二阶展开的价值全在别的损失函数上(logloss、pairwise 排序、Poisson、自定义)。
单选6. XGBoost 怎么处理缺失值?
看答案与解析
答案:C
不填。每个候选分裂点上把缺失样本全扔左边算一次 Gain、全扔右边再算一次,哪边 Gain 大就把默认方向定成哪边——缺失是被当成信息学出来的,顺带让稀疏 one-hot 也跑得快。
单选7. 关于 LightGBM,下面哪一条是对的?
看答案与解析
答案:D
直方图把建表与候选扫描分开:建表仍遍历样本,扫描随箱数变化;做差减少重复构建。GOSS可选,大梯度保留、小梯度抽样并加权;EFB利用稀疏互斥结构。leaf-wise可能形成深而不平衡的树,需联合控制 num_leaves、max_depth、min_data_in_leaf并检查验证结果,不保证整次训练固定提速。
单选8. CatBoost 的有序目标统计在防什么?
看答案与解析
答案:A
有序目标统计按排列只用先前样本计算带标签的类别统计,避免直接使用自身标签;可选Ordered boosting针对预测偏移,不能与CTR或默认Plain混同。默认对称树同层共用条件,有利于紧凑叶子索引并限制结构自由度;更改生长策略后结构不同,不能据此保证速度、精度或所有外部泄漏均已解决。
本节回顾
- w* 决定一个叶子输出多少。
- Gain 比较一次切分值不值得。
- λ 管输出幅度,γ 管长叶子的成本。
⚡ 走神救援
先记住这几件事
- 这一轮的新树是在旧预测上加修正;目标同时考虑损失与树的复杂度。
- 先逐样本求 g、h,再按叶子汇总成 G、H;它们决定叶子的候选输出。
- 在 H+λ 为正的条件下,叶子最优输出是 −G/(H+λ)。
- Gain 比较分裂前后的目标改善,并扣除新增叶子的成本;不是只看训练样本更纯。
- 推导给出候选更新,学习率、缺失值处理和验证仍然需要单独检查。
下一节 👉 05-评估与过拟合.md ⭐⭐⭐ 全教程最重要的一章