相关引用：

梯度提升树(GBDT)原理小结

周末苏州的天气很暖和，一度到了28度，着实很适合出去溜达。去吃了顿烧烤，打了会球，回来刚好还有时间，顺便更新一下博客。

变态辣翅

上篇博文回顾了Bagging和Boosting，这次继续扩展一下Boosting下的GBDT，以及由它衍生出的后续模型。

GBDT原理

和Adaboost不同，Adaboost利用每轮学习器的误差率来更新样本权重，以此进行迭代，这种方式并不限制学习器的类型。而GBDT使用了前向分步算法，并且限制了每轮的弱学习器只能是CART回归树。

为什么GBDT的弱学习器是回归树？原因在于Adaboost通过调整样本权重来优化模型，它只关心弱学习器是否能正确预测目标，所以只要学习器能计算分类错误率就能够参与前向分步。GBDT则通过拟合负梯度（残差）直接修正预测误差。每一轮新模型的目标是拟合当前模型输出与真实值的梯度方向，而不是调整样本权重，这就要求损失函数需要可导，因此弱学习器需要能输出连续值。

模型表达形式

假设我们

有数据集： $\mathcal{D} = \{(x_i, y_i)\}_{i=1}^N$
损失函数是 $\mathcal{L}(y, F(x))$

此时我们希望拟合一个函数 $F(x)$ 来最小化损失函数： $\hat{F} = \arg\min_F \sum_{i=1}^N \mathcal{L}(y_i, F(x_i))$ 。这个函数就是我们想要训练的模型。

GBDT 将 $F(x)$ 表达为若干CART的加和： $F(x) = \sum_{m=1}^M \gamma_m h_m(x)$ 。其中 $h_m(x)$ 是第 $m$ 颗回归树， $\gamma_m$ 是其权重，这个和Adaboost是类似的。

前向分步优化

现在可以开始训练了，在训练过程中，每次迭代模型 $m$ ，都会保持已有模型 $F_{m-1}(x)$ 不变，并优化新增一颗树： $F_m(x) = F_{m-1}(x) + \gamma_m h_m(x)$

为了降低整体的损失，我们需要最小化所有树加和的预测损失。此时我们的目标是找到一个新函数 $h_m(x)$ 和它的权重系数 $\gamma_m$ 来让整体损失最小：

$(\gamma_m, h_m) = \arg\min_{\gamma, h} \sum_{i=1}^N \mathcal{L}\left(y_i, F_{m-1}(x_i) + \gamma h(x_i)\right)$

这是一个通用的目标，但是由于函数空间 $\mathcal{H}$ 中所有可能的 $h(x)$ 非常庞大，也就是可能存在非常多的回归树，我们不能直接枚举的选出其中最佳的弱学习器 $h(x)$ 。

既然不能直接得到最优解，但可以采用一种“贪心且局部”的近似：在当前模型 $F_{m-1}(x)$ 的基础上，向最能降低损失的方向前进一步，也就是梯度下降。这时，把最终的目标函数 $F(x)$ 视为一个函数空间上的向量，而在我们目前所处的 $F_{m-1}(x)$ ，朝着负梯度的位置走一步，得到

$h_m(x) = - \left[ \frac{\partial \mathcal{L}(y_i, F(x_i))}{\partial F(x_i)} \right]$

也就是说，我们想要预测得到的下一颗树，从原来的拟合最小残差树，变成了拟合当前模型的负梯度方向一步。

然后我们训练一棵回归树 $h_m(x)$ 来拟合这些伪残差： $h_m(x) \approx r^{(m)} = \text{CART}(x, r^{(m)})$

至此，我们得到了下一个弱学习器，迭代此过程到损失函数最小，即得到了最终的模型。

工程实现角度

基本流程

初始化模型：

$F_0(x) = \arg\min_\gamma \sum_i \mathcal{L}(y_i, \gamma)$
对于 $m = 1$ 到 $M$ ：
- 计算残差 $r_i^{(m)}$
- 拟合回归树 $h_m(x)$
- 计算每个叶节点的输出 $\gamma_m$
- 更新模型： $F_m(x) = F_{m-1}(x) + \gamma_m h_m(x)$
最终预测为 $F_M(x)$

衍生模型

XGBoost

大名鼎鼎的XGBoost在竞赛领域里经久不衰，作为 GBDT 的工业级实现，可以算的上是目前应用最广泛的 GBDT 框架之一。它的优化点也是经典面试八股文了：

数学优化

加入正则项：

XGBoost 在 GBDT 基础上加入了正则项。原本的损失函数是 $\mathcal{L}^{(t)} = \sum_{i=1}^N l(y_i, \hat{y}_i^{(t)})$ ，在后面加上了

$\sum_{k=1}^{t} \Omega(f_k)$ ，其中的 $\Omega(f_k)$ 是对第 $k$ 棵树 $f_k$ 的正则化项， $\Omega(f) = \gamma T + \frac{1}{2} \lambda \sum_{j=1}^{T} w_j^2$ 。

$T$ ：树的叶子数，反映树的结构复杂度（越大越复杂）
$w_j$ ：第 $j$ 个叶子节点的得分（预测输出）

我们看下每棵树的正则项，它由两个超参数组成：

$\gamma$ ：叶子节点数量惩罚因子
$\lambda$ ：叶子节点得分的 L2 正则项系数

可以看到， $\lambda$ 越大，每个叶子的输出 $w_j$ 就会被“压缩”得越小。 $\gamma$ 越大，分裂的叶子数越小。

二阶泰勒展开：

GBDT使用一阶导的负梯度近似损失函数，XGBoost改用了二阶导，目的是为了让模型更快收敛：

$\mathcal{L}^{(t)} \approx \sum_{i=1}^N [g_i f_t(x_i) + \frac{1}{2} h_i f_t(x_i)^2] + \Omega(f_t)$

其中：

$g_i = \partial_{\hat{y}^{(t-1)}} \mathcal{L}(y_i, \hat{y}_i^{(t-1)})$
$h_i = \partial^2_{\hat{y}^{(t-1)}} \mathcal{L}(y_i, \hat{y}_i^{(t-1)})$

在GDBT中，一阶导数告诉我们哪个方向能让损失最快的减少。而二阶导数是告诉我们损失在这个方向上的曲率，变化的快不快。如果二阶导很小，说明当前很陡，需要慢一点增加下一棵树，如果很大，则说明梯度损失曲线比较平稳。

更改了树节点分裂的增益系数：

原本的CART树通过基尼系数来判断要不要分裂叶子节点，而XGBoost通过最大化增益来分裂。增益系数的公式是：

\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$ 、 $H_L$ ：叶子节点上的一阶/二阶导数累加值
$\lambda$ ：控制叶子输出的大小（因为最终输出是 $w_j = -\frac{G_j}{H_j + \lambda}$ ）
$\gamma$ ：控制是否值得多生成一个叶子节点（结构正则）

工程优化

缓存导数计算

可以看到XGBoost的一大更新是二阶导数，因此在每次迭代前，都会提前计算并缓存所有样本的 $g_i$ 和 $h_i$ ，这样在分裂节点时可以快速计算增益。

支持缺失值处理

传统机器学习流程中需要先填补缺失值，这是因为决策树需要根据分裂条件进行分裂。例如当特征x<3.5，前往左子树，反之前往右子树。而如果是Nan的就无法判断怎么走了，因此往往需要分配一个值来填补缺失值。

XGBoost在特征分裂时，对于某个分裂条件（例如feature_x < 3.5）都会尝试：如果所有缺失该特征的样本都走左子树，以及所有缺失该特征的样本都走右子树，这两种情况下各自的损失。哪种损失小，就作为缺失值样本的默认分配方向。

基于列的 block 结构加快分裂

在XGBoost中，还对做了一系列优化。默认的树在分裂时都需要遍历所有特征的所有样本来计算梯度和增益：

for feature in features:
   for sample in samples:
       scan feature_value, gradient, etc.

这样显然很慢，因此XGBoost把每列特征都预处理为一个block，每个block记录该特征下所有样本的关键信息：非零值（压缩稀疏特征），位置索引（row id），对应的梯度和 Hessian。这样就类似于加强版的稀疏矩阵。

并且这种改进还为它带来了分布式并行训练的能力，每个特征都可以在不同节点上分裂和计算。

LightGBM

在XGBoost之后，微软开源了LightGBM（Light Gradient Boosting Machine）。它相较于传统的GBDT（如 XGBoost）做了大量优化，在大规模数据和高维稀疏特征下表现出色。

叶子优先的生长策略

首先，在决策树当中，每个叶子节点都表示着一组样本，每个非叶子节点表示的是一个决策条件。当我们在训练决策树时，我们希望对还未分割的叶子节点进行分裂，也就是决定这个候选节点里的样本要怎么分成左右两个子节点。在分裂节点的时候，就会为每个特征计算增益，最终选出增益最大的特征和切分点，用它来切分节点。这是节点分裂的定义。

现在，我们先看下XGBoost是怎么做节点的分裂的：XGBoost会对当前层的所有节点分别计算最优分裂点，如果信息增益大于阈值，就会分裂节点。我们可以想象，XGBoost会产生一颗很宽的树，因为每层都会为所有节点进行分裂，因此训练过程会比较慢。

而LightGBM则是深度优先，在每层分裂时，只挑所有叶子节点中增益最大的叶子节点进行分裂。每次只分一个节点，可想而知，最终生成的树是很深的。

GBDT的训练目标是每个弱学习器都要最大程度的降低损失，因此当采用深度优先的时候，它通过每次只找最佳节点进行分裂，因此这相比广度优先的方式能更快的收敛损失。当然，更快收敛也导致LightGBM容易过拟合。

简单的例子：假设现在有 3 个叶子节点（A/B/C），它们的最优分裂增益如下：

叶子节点	增益（信息增益）
A	0.3
B	0.2
C	0.05

Level-wise：会把 A、B、C 都分了 → 总共带来增益 = 0.3 + 0.2 + 0.05 = 0.55，但效率不高；
Leaf-wise：只分 A（0.3），带来最强的一步梯度下降，下一轮再挑新的最优。

Leaf-wise 的本质是：每轮都最大化对当前梯度的拟合效果（贪心策略），因此在相同轮数下比 Level-wise 学得更快、误差下降得更多。

副作用

Leaf-wise 虽然下降快，但容易在某些“局部区域”长得很深 → 过拟合。并且由于树结构不平衡，部署时可能消耗很大的资源更多。为了解决这个问题，需要用正则 + 参数限制来防止过拟合：

max_depth
num_leaves
min_data_in_leaf
lambda_l1 / lambda_l2

基于直方图的特征分裂

基于直方图的特征分裂是LightGBM里的一个核心优化点。前面我们能注意到，GBDT在每次训练弱学习器时，都需要先遍历每个特征的所有取值，尝试每个可能的分裂点，再计算信息增益，最后选最佳分裂点。从计算复杂度上，涉及遍历非常耗时。

现在LGBM选择将连续特征进行分箱，把将连续的特征值离散化为有限个有序的bins，只在这些bin的边界上尝试分裂。例如：将一个连续特征 [2.1, 3.3, 7.9, 8.2, 10.5] 离散为 4 个 bins，比如：

原始值	Bin Index
2.1	0
3.3	1
7.9	2
8.2	2
10.5	3

默认LGBM会将连续特征分成255个bin，这个分箱密度已经足够保证一定的精度，而带来的训练速度提升是巨大的。分箱之后，在节点分裂时，会用bin的边界作为分裂点。例如在上面的例子里，模型可能会分裂出是否bin<=2，也就是代表数值是否小于等于7.9。

对于分类离散变量的支持

传统的数据模型对于分类变量的支持并不友好，需要进行One-Hot 编码或者Label Encoding。前者让维度大大增加，后者会由于数值大小带来偏差。

此外One-Hot 编码在树模型还有更大的影响，就是每个节点由于单个类别vs其余所以类别，在类别很多的情况下很容易出现数据不平衡。

LGBM直接使用类别的整数ID进行处理，并在训练中使用类别直方图和最优类别分裂计算最佳分裂点。

最优类别分裂是LGBM的创新点之一。传统的树模型里，一个节点的分裂通过二分法实现，在特征类别很多的时候，会很容易导致数据不平衡。LGBM提供了两种改进：one vs rest，best subset split。

One vs Rest（单类别 vs 其他）

核心思想：

计算每个类别的梯度直方图统计量（梯度总和 $G_k$ 和 Hessian 总和 $H_k$ ）。
计算每个类别单独作为一组 vs 其他类别作为另一组时的分裂增益。
选择增益最大的类别进行分裂。

数学公式：

\text{Gain} = \frac{G_k^2}{H_k + \lambda} + \frac{(G_{\text{all}} - G_k)^2}{(H_{\text{all}} - H_k) + \lambda} - \frac{G_{\text{all}}^2}{H_{\text{all}} + \lambda}

其中：

$G_k$ 是类别 $k$ 的梯度和， $H_k$ 是类别 $k$ 的 Hessian 和。
$G_{\text{all}}, H_{\text{all}}$ 是所有数据的梯度和 Hessian 和。
$\lambda$ 是正则化参数。

假设 color 有 3 个类别：

color = ["red", "blue", "green"]

计算 red vs (blue, green）的分裂增益
计算 blue vs (red, green）的分裂增益
计算 green vs (red, blue）的分裂增益
选择增益最大的那个类别进行分裂

这种方式是对传统树模型里分类特征的改进处理，因此数据不平衡的特征也没有解决。

Best Subset Split（最优子集分裂）

当类别数量较多时，LightGBM 会尝试找到最优的类别子集组合，即：

不是单个类别 vs 其他，而是多个类别组合 vs 其他类别组合。

核心步骤：

计算每个类别的梯度直方图统计量。
通过贪心算法找到最佳类别组合，使分裂增益最大化。

示例： 假设 color 变量有 5 个类别：

color = ["red", "blue", "green", "yellow", "purple"]

LightGBM 可能找到最优的分裂：

{"red", "blue"} vs {"green", "yellow", "purple"}

即： $\text{Split: } \{0, 1\} \text{ vs } \{2, 3, 4\}$

这种方法比 One-vs-Rest 更灵活，在类别较多的情况下可以带来更好的效果。

GOSS（Gradient-based One Side Sampling）

GOSS是对XGBoost的改进，在XGBoost训练时，需要在每次计算梯度和二阶信息时遍历全部样本，然后计算特征分裂增益，这样显然计算开销非常大。LightGBM认为并非所有样本对决策树的分裂贡献相同，梯度较大的样本更重要（因为它们的损失较高，模型需要重点学习），类似Adaboost。

从表现上来看，这两种算法有点类似，但目的不同。前者通过保留高梯度样本，后者调整样本权重，前者的目标是加速计算，后者目的是加强对难分类样本的预测精度。

GOSS的实现分为两步：

按照梯度绝对值，保留头部梯度的样本。
对于剩下的样本进行随机采样。
对低梯度样本的梯度进行放缩，以补偿采样后样本量减少的梯度损失。

GOSS的例子（摘自Chatgpt）：

假设有一个训练集包含 6 个样本，模型正在训练一个二分类问题。每个样本的梯度（即损失函数对模型预测的导数）已计算出来，并且我们知道这些样本的梯度大小。

样本及其梯度：

样本 1：梯度 $g_1 = 0.5$

样本 2：梯度 $g_2 = 1.2$

样本 3：梯度 $g_3 = 0.1$

样本 4：梯度 $g_4 = 0.8$

样本 5：梯度 $g_5 = 0.05$

样本 6：梯度 $g_6 = 0.3$

设定：

假设决定 保留 50% 的高梯度样本，即保留梯度较大的样本。

假设将 低梯度样本采样 50%，即从梯度较小的样本中随机选取一半，并对它们进行放缩。

GOSS 过程

步骤 1：计算每个样本的梯度

已经给出了每个样本的梯度，梯度值直接反映了模型在这些样本上的“错误”程度，通常我们会希望优化模型，减少大的梯度值，因为它们代表了模型的误差。

步骤 2：确定高梯度样本和低梯度样本

首先按照梯度的大小将样本分成两类：

高梯度样本（梯度较大的样本）：梯度值较大的样本通常表明模型在这些样本上的误差较大，需要关注它们。

低梯度样本（梯度较小的样本）：梯度值较小的样本通常表示模型在这些样本上已经拟合较好，不需要额外关注它们。

对于本例，我们可以选择一个阈值（比如梯度大于某个值的样本为高梯度样本），也可以选择按梯度大小的排名来确定高梯度和低梯度样本。例如：

高梯度样本：样本 2 (梯度 1.2) 和样本 4 (梯度 0.8)

低梯度样本：样本 1 (梯度 0.5)、样本 3 (梯度 0.1)、样本 5 (梯度 0.05) 和样本 6 (梯度 0.3)

步骤 3：对低梯度样本进行采样

在 GOSS 中，我们对 低梯度样本 进行采样。假设我们按 50% 的比例对低梯度样本进行采样（从 4 个低梯度样本中随机选择 2 个）。假设我们选择了 样本 1 和样本 6 作为低梯度样本进行保留。

步骤 4：对采样后的低梯度样本进行梯度放缩

为了补偿低梯度样本数量减少带来的信息损失，我们对 低梯度样本 的梯度进行放缩，使它们的梯度值增大。假设我们保留了高梯度样本的 100%，而低梯度样本采样比例为 50%。则放缩因子为：

$\text{放缩因子} = \frac{(1-a)}{b} = \frac{(1 - 0.5)}{0.5} = 1$

这里，a = 0.5 是高梯度样本的比例，b = 0.5 是低梯度样本的采样比例。放缩因子为 1，表示我们不改变梯度。

对于选中的低梯度样本（样本 1 和样本 6），它们的梯度被放大为：

样本 1 的梯度：放缩后的梯度 $g_1{\prime} = 1 \times g_1 = 0.5$

样本 6 的梯度：放缩后的梯度 $g_6{\prime} = 1 \times g_6 = 0.3$

步骤 5：合成最终的梯度

现在，我们将保留的高梯度样本的梯度与放缩后的低梯度样本的梯度合并，得到最终用于训练的梯度。

高梯度样本：样本 2 (梯度 $g_2 = 1.2$ ) 和样本 4 ( $梯度 g_4 = 0.8$ )

放缩后的低梯度样本：样本 1 (梯度 $g_1{\prime} = 0.5$ ) 和样本 6 ( $梯度 g_6{\prime} = 0.3$ )

最终得到用于训练的梯度集：

$g_2 = 1.2$

$g_4 = 0.8$

$g_1{\prime} = 0.5$

$g_6{\prime} = 0.3$

步骤 6：使用这些梯度进行模型更新

这些最终的梯度将被用来更新模型的参数，通过进一步训练来降低损失函数值。高梯度样本的贡献较大，低梯度样本的贡献较小，但通过放缩，它们仍然对最终模型更新起到作用。

总结 GOSS 流程

计算每个样本的梯度。

根据梯度大小分为高梯度样本和低梯度样本。

从低梯度样本中进行随机采样，例如采样 50% 的低梯度样本。

对采样后的低梯度样本进行梯度放缩，放大它们的梯度值。

将保留的高梯度样本和经过放缩后的低梯度样本合并，得到用于训练的最终梯度。

通过这种方式，GOSS 可以在保证训练质量的同时，大幅度减少低梯度样本的计算开销，从而提高训练效率。

整体而言，GOSS是一种采样方式，并对下采样样本进行梯度补偿。最终效果是减少了特征分裂时的样本量，加速计算效率。

EFB（Exclusive Feature Bundling）

LightGBM的很大改进都针对计算效率，EFB也是同样的目的。它的目的是通过捆绑高维稀疏变量来大大减少特征维度。这个相对比较好理解，对于互斥的特征，LightGBM会把它们捆绑拼接成一个单独的特征。

假设例如有一个数据集，包含以下三个特征：

ID	Feature A	Feature B	Feature C
1	1	0	0
2	0	1	0
3	0	0	1
4	1	0	0
5	0	1	0

其中，Feature A、Feature B 和 Feature C 互斥，即它们不能同时为 1。因此，LightGBM将这三个特征捆绑在一起，形成一个新的复合特征，这个过程就是EFB。

最终的复合特征如下：

ID	复合特征
1	100
2	010
3	001
4	100
5	010

捆绑后的特征维度明显减少，原来三维的特征现在只有一维，但它仍然保留了原有的信息。

CatBoost

核心优化

专注于类别变量处理
无需手动独热编码，使用统计方式编码：
基于目标编码（target statistics）
采用“排列顺序”（permutation）防止 target leakage

工程亮点

支持 CPU + GPU 训练
使用对称树结构，提高推理速度
避免梯度偏移，提升泛化能力

2025/3/23 于苏州

重读统计学习方法：GBDT及其改进