【统计学习方法死磕系列】提升算法

写在前面

提升算法（Boosting）是机器学习中最重要的思想之一。它将多个”弱学习器”（weak learner，准确率仅略高于随机猜测的模型）串行组合成一个”强学习器”（strong learner，可以任意精确的模型）。Kearns 和 Valiant 在 1988 年提出了著名的”弱学习器能否被提升为强学习器？”的问题，Schapire 在 1990 年用构造性证明给出了肯定的答案，从而开创了 Boosting 理论。

从 1995 年的 AdaBoost，到 2001 年的 GBDT，再到 2016 年的 XGBoost 和 2017 年的 LightGBM，Boosting 算法已经统治了结构化/表格数据的机器学习领域长达二十年，至今仍是 Kaggle 竞赛和工业界 Tabular 数据建模的事实标准。

本文将从 AdaBoost 的指数损失和加法模型推导出发，逐步深入到 GBDT 的梯度提升框架、XGBoost 的二阶泰勒展开与正则化、LightGBM 的直方图加速与 GOSS 采样，以及 CatBoost 的有序目标编码。全文力求每个关键公式都有严密的推导。

1. AdaBoost

1.1 核心思想

AdaBoost（Adaptive Boosting）由 Freund 和 Schapire 于 1995 年提出，获得了 2003 年的 Godel 奖。其核心思想极其优雅：

每一轮训练一个弱分类器（通常是决策树桩，decision stump）
根据当前弱分类器的表现，提高被误分类样本的权重、降低被正确分类样本的权重
下一轮的弱分类器会”关注”那些之前被反复分错的”困难样本”
最终的强分类器是所有弱分类器的加权投票

1.2 算法形式化描述

输入：训练集 $D = {(x_1, y_1), \ldots, (x_N, y_N)}$，其中 $y_i \in {-1, +1}$。

输出：强分类器 $G(x) = \text{sign}\left(\sum_{m=1}^{M} \alpha_m G_m(x)\right)$

算法流程：

Algorithm: AdaBoost
1. 初始化样本权重分布 D_1 = (w_{11}, ..., w_{1N}),  w_{1i} = 1/N

2. for m = 1 to M:
3.     在权重分布 D_m 上训练弱分类器 G_m(x)
4.     计算 G_m(x) 在训练集上的分类误差率:
          e_m = Σ_{i: G_m(x_i) ≠ y_i} w_{mi}
5.     计算 G_m(x) 的系数（说话分量）:
          α_m = (1/2) ln((1 - e_m) / e_m)
6.     更新样本权重:
          w_{m+1,i} = w_{mi} · exp(-α_m y_i G_m(x_i)) / Z_m
          其中 Z_m = Σ_i w_{mi} exp(-α_m y_i G_m(x_i)) 是归一化因子
7. end for

8. 输出最终分类器:
      G(x) = sign( Σ_{m=1}^{M} α_m G_m(x) )

1.3 权重更新公式的推导：指数损失函数的视角

AdaBoost 可以被理解为使用指数损失函数（Exponential Loss）的前向分步加法模型（Forward Stagewise Additive Modeling）。

加法模型：$f(x) = \sum_{m=1}^{M} \beta_m b(x; \gamma_m)$，其中 $b(x; \gamma_m)$ 是基函数（弱分类器），$\beta_m$ 是系数。

指数损失函数：$L(y, f(x)) = \exp(-y f(x))$

每一轮，我们要找一个新的基函数及其系数来最小化当前的指数损失。

在第 $m$ 轮，已知 $f_{m-1}(x) = \sum_{j=1}^{m-1} \alpha_j G_j(x)$，我们要：

$$(\alpha_m, G_m) = \arg\min_{\alpha, G} \sum_{i=1}^{N} \exp(-y_i (f_{m-1}(x_i) + \alpha G(x_i)))$$

记 $\bar{w}{mi} = \exp(-y_i f{m-1}(x_i))$（可视为当前的样本权重），则：

$$\sum_{i=1}^{N} \bar{w}_{mi} \exp(-y_i \alpha G(x_i))$$

$$= \sum_{G(x_i)=y_i} \bar{w}_{mi} e^{-\alpha} + \sum_{G(x_i) \neq y_i} \bar{w}_{mi} e^{\alpha}$$

$$= e^{-\alpha} \sum_{y_i = G(x_i)} \bar{w}_{mi} + e^{\alpha} \sum_{y_i \neq G(x_i)} \bar{w}_{mi}$$

令 $w_{mi} = \frac{\bar{w}{mi}}{\sum_j \bar{w}{mj}}$（归一化权重），$e_m = \sum_{G(x_i) \neq y_i} w_{mi}$（加权误分率）。

则上式 = $\left(\sum_j \bar{w}_{mj}\right) \cdot [e^{-\alpha}(1 - e_m) + e^{\alpha} e_m]$

Step 1：对 $G$ 求最优

$\alpha > 0$ 时，$e^{-\alpha} < e^{\alpha}$。要使损失最小，需要让 $\sum_{G(x_i) \neq y_i} w_{mi}$（即 $e_m$）尽可能小。这意味着 $G_m$ 应当在当前的加权分布下最小化分类误差——即加权误差最小的分类器。这解释了步骤 3-4。

Step 2：对 $\alpha$ 求最优

固定 $G_m$ 后，对 $\alpha$ 求导令为 0：

$$\frac{\partial}{\partial \alpha} [e^{-\alpha}(1 - e_m) + e^{\alpha} e_m] = -e^{-\alpha}(1 - e_m) + e^{\alpha} e_m = 0$$

$$e^{\alpha} e_m = e^{-\alpha}(1 - e_m)$$

$$e^{2\alpha} = \frac{1 - e_m}{e_m}$$

$$\alpha_m = \frac{1}{2} \ln \frac{1 - e_m}{e_m}$$

这刚好是步骤 5 的公式。

Step 3：权重更新

由 $\bar{w}{m+1,i} = \exp(-y_i f_m(x_i)) = \exp(-y_i (f{m-1}(x_i) + \alpha_m G_m(x_i)))$

$$= \bar{w}_{mi} \cdot \exp(-\alpha_m y_i G_m(x_i))$$

归一化后得到步骤 6 的权重更新公式。

关键结论：AdaBoost 的权重更新不是启发式的，而是从最小化指数损失这个单一优化目标严格推导出来的。

1.4 弱分类器系数的含义

$$\alpha_m = \frac{1}{2} \ln \frac{1 - e_m}{e_m}$$

当 $e_m = 0.5$：$\alpha_m = 0$（弱分类器等同于随机猜测，完全无用，不给发言权）
当 $e_m < 0.5$：$\alpha_m > 0$（分类器有效，误差越小权重越大）
当 $e_m \to 0$：$\alpha_m \to \infty$（完美分类器获得极高的权重）

$\alpha_m$ 随 $e_m$ 的变化：

$e_m$	$\alpha_m$	含义
0.01	2.30	近乎完美
0.05	1.47	非常好
0.10	1.10	好
0.20	0.69	中等
0.30	0.42	弱
0.40	0.20	很弱
0.50	0.00	无效

1.5 AdaBoost 的训练误差界

可以证明，AdaBoost 的训练误差有上界：

$$\frac{1}{N} \sum_{i=1}^{N} \mathbf{1}\{G(x_i) \neq y_i\} \leq \prod_{m=1}^{M} Z_m$$

其中 $Z_m = \sum_i w_{mi} \exp(-\alpha_m y_i G_m(x_i))$。

且 $Z_m = 2\sqrt{e_m(1 - e_m)}$（在 $\alpha_m$ 取最优值时）。

定义 $\gamma_m = \frac{1}{2} - e_m$（分类器比随机猜测好多少）。则 $Z_m \leq \exp(-2\gamma_m^2)$。

如果每个弱分类器的 $\gamma_m \geq \gamma > 0$，则：

$$\text{Training Error} \leq \exp(-2M\gamma^2)$$

这意味着，只要每个弱分类器”稍微”比随机好一点（$\gamma > 0$），训练误差就随 $M$ 指数下降为 0。这就是 Kearns-Valiant 问题的严谨答案。

1.6 AdaBoost 的泛化分析

AdaBoost 之所以不会轻易过拟合（即使训练轮数 $M$ 很大），是因为它最大化margin。Schapire et al. (1998) 证明了 AdaBoost 的泛化误差上界不依赖于 $M$，而依赖于训练集的 margin 分布。

这个现象在实践中被称为”AdaBoost 对过拟合的抵抗力”——在某些实验中，即使训练误差降到 0，继续增加弱分类器数 $M$，测试误差仍在下降。

2. GBDT（梯度提升决策树）

2.1 从函数空间梯度下降理解 Boosting

AdaBoost 特化了指数损失函数。GBDT（Gradient Boosting Decision Tree, Friedman 2001）将 Boosting 推广到任意可微损失函数。

核心思想：

传统的梯度下降是在参数空间中：$\theta \leftarrow \theta - \eta \nabla_\theta L(\theta)$
Boosting 的梯度下降是在函数空间中：$f(x) \leftarrow f(x) - \eta \frac{\partial L}{\partial f(x)}$

每一轮，我们不更新参数，而是添加一个新的函数（决策树），这个函数拟合当前损失函数的负梯度方向（即”残差”）。

2.2 函数空间梯度下降的形式化推导

对于训练数据 ${x_i, y_i}{i=1}^{N}$，考虑加法模型 $f_M(x) = \sum{m=1}^{M} T(x; \Theta_m)$，其中每棵决策树 $T$ 的参数为 $\Theta_m$。

损失函数：$\mathcal{L} = \sum_{i=1}^{N} L(y_i, f_M(x_i))$。

贪心优化：在第 $m$ 轮，已有 $f_{m-1}$，我们希望找到 $\Theta_m$ 最小化：

$$\mathcal{L}_m = \sum_{i=1}^{N} L(y_i, f_{m-1}(x_i) + T(x_i; \Theta_m))$$

在 $f_{m-1}(x_i)$ 处对损失函数做一阶 Taylor 展开：

$$L(y_i, f_{m-1}(x_i) + T(x_i)) \approx L(y_i, f_{m-1}(x_i)) + \left.\frac{\partial L}{\partial f}\right|_{f=f_{m-1}(x_i)} \cdot T(x_i)$$

要最小化 $\mathcal{L}_m$，应使 $T(x_i)$ 在负梯度方向上尽可能接近：

$$T(x_i) \approx -\left.\frac{\partial L}{\partial f}\right|_{f=f_{m-1}(x_i)}$$

定义负梯度（伪残差）：

$$r_{im} = -\left[ \frac{\partial L(y_i, f(x_i))}{\partial f(x_i)} \right]_{f(x)=f_{m-1}(x)}$$

GBDT 的核心步骤：

用当前模型 $f_{m-1}$ 对每个样本计算负梯度 $r_{im}$（这就是第 $m$ 轮要拟合的”目标值”）
训练一棵回归树 $h_m(x)$ 去拟合 ${(x_i, r_{im})}_{i=1}^{N}$
搜索最优步长（学习率）$\rho_m = \arg\min_\rho \sum_i L(y_i, f_{m-1}(x_i) + \rho h_m(x_i))$
更新模型：$f_m(x) = f_{m-1}(x) + \eta \cdot \rho_m \cdot h_m(x)$（$\eta$ 是全局学习率，即 shrinkage）

2.3 常见损失函数对应的负梯度

损失函数	$L(y, f)$	负梯度 $-\partial L / \partial f$
平方误差 (MSE)	$\frac{1}{2}(y - f)^2$	$y - f$ （残差，residual）
绝对误差 (MAE)	$	y - f
Logistic Loss (二分类)	$\log(1 + e^{-yf})$	$\frac{y}{1+e^{yf}}$
指数损失	$\exp(-yf)$	$y \exp(-yf)$

对于平方误差损失，负梯度恰好是残差 $y - f$，这也是”拟合残差”这个说法的由来。但广义上 GBDT 拟合的是梯度，不只是残差。

2.4 GBDT 回归算法（伪代码）

Algorithm: GBDT Regression
Input: 训练集 {(x_i, y_i)}, 损失函数 L, 迭代次数 M, 学习率 η
Output: f_M(x)

1. 初始化 f_0(x) = argmin_c Σ_i L(y_i, c)
   // 例如 MSE 时 f_0(x) = mean(y); MAE 时 f_0(x) = median(y)

2. for m = 1 to M:
3.     for i = 1 to N:
4.         r_im = - [∂L(y_i, f(x_i)) / ∂f(x_i)] |_{f=f_{m-1}}
5.     训练一棵回归树 h_m(x) 拟合 {(x_i, r_im)}
6.     ρ_m = argmin_ρ Σ_i L(y_i, f_{m-1}(x_i) + ρ · h_m(x_i))
7.     f_m(x) = f_{m-1}(x) + η · ρ_m · h_m(x)
8. return f_M(x)

2.5 Shrinkage（学习率收缩）

$\eta$（通常 0.01-0.1）是 GBDT 的全局学习率。小的 $\eta$ 使每棵树只做很小的修正，需要更多的树（$M$ 更大）但泛化效果更好。

$$\text{shrinkage 的作用} = \text{正则化} + \text{使 boosting 过程更 smooth}$$

实践中，$\eta$ 和 $M$ 是互相影响的超参数：

$\eta$ 小 → 需要更多树（$M$ 大） → 训练慢但泛化好
$\eta$ 大 → 需要更少树（$M$ 小） → 训练快但可能跳过头
经验法则：$\eta \cdot M \approx \text{常数}$。例如 $\eta = 0.1, M = 100$ 和 $\eta = 0.01, M = 1000$ 在偏差上接近但后者方差更低。

2.6 子采样（Stochastic GBDT）

Friedman 提出在每轮 GBDT 迭代中，只随机采样一部分数据（如 50%-80%）来训练每棵树。这被称为 Stochastic Gradient Boosting。

$$\text{GBDT + Subsampling} \approx \text{Gradient Boosting + Bagging}$$

子采样有两个好处：

减少每棵树的训练时间
通过引入随机性，降低过拟合风险，提高泛化能力

典型子采样比例：0.5（若数据巨大）到 0.8（标准设置）。

3. XGBoost

3.1 XGBoost 的改进概述

XGBoost（eXtreme Gradient Boosting）由陈天奇于 2014 年提出（2016 年发表论文），在 GBDT 的基础上做了多个关键改进：

目标函数加入正则化项：控制模型复杂度
二阶泰勒展开：使用二阶导数信息，收敛更快更准
近似分裂查找：处理海量数据的分裂点搜索
系统优化：列块存储、缓存优化、并行化
内置缺失值处理：自动学习缺失值的最优分裂方向
列采样：类似 Random Forest 的特征采样

3.2 带正则化的目标函数

XGBoost 的目标函数：

$$\mathcal{L} = \sum_{i=1}^{N} L(y_i, \hat{y}_i) + \sum_{m=1}^{M} \Omega(f_m)$$

其中 $\Omega(f) = \gamma T + \frac{1}{2}\lambda |w|^2$，$T$ 是树的叶节点数，$w$ 是叶节点的权重向量。

这里有两项正则化：

$\gamma T$：每多一个叶节点，损失加 $\gamma$（鼓励更浅的树）
$\frac{1}{2}\lambda |w|^2$：L2 正则化叶节点权重（防止权重过大）

3.3 二阶泰勒展开

在 GBDT 中，我们在 $f_{m-1}$ 处仅对损失做一阶展开。XGBoost 使用二阶展开：

$$L(y_i, f_{m-1}(x_i) + h_m(x_i)) \approx L(y_i, f_{m-1}(x_i)) + g_i h_m(x_i) + \frac{1}{2} h_i h_m(x_i)^2$$

其中：

$g_i = \partial L(y_i, \hat{y}_i) / \partial \hat{y}i |{\hat{y}i = f{m-1}(x_i)}$ 是一阶梯度
$h_i = \partial^2 L(y_i, \hat{y}_i) / \partial \hat{y}i^2 |{\hat{y}i = f{m-1}(x_i)}$ 是二阶梯度（Hessian）

去掉与 $h_m$ 无关的常数项，第 $m$ 轮的优化目标为：

$$\tilde{\mathcal{L}}^{(m)} = \sum_{i=1}^{N} \left[ g_i h_m(x_i) + \frac{1}{2} h_i h_m(x_i)^2 \right] + \gamma T + \frac{1}{2}\lambda \sum_{j=1}^{T} w_j^2$$

3.4 叶节点权重的闭式解

设树 $h_m$ 有 $T$ 个叶节点，叶节点 $j$ 包含的样本索引集合为 $I_j = {i | x_i \text{ 落入叶节点 } j}$。叶节点 $j$ 的预测值为 $w_j$。

则目标函数可以按叶节点重组：

$$\begin{aligned} \tilde{\mathcal{L}}^{(m)} &= \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 \\ &= \sum_{j=1}^{T} \left[ G_j w_j + \frac{1}{2} (H_j + \lambda) w_j^2 \right] + \gamma T \end{aligned}$$

其中 $G_j = \sum_{i \in I_j} g_i$，$H_j = \sum_{i \in I_j} h_i$。

对 $w_j$ 求导令为 0：

$$\frac{\partial \tilde{\mathcal{L}}}{\partial w_j} = G_j + (H_j + \lambda) w_j = 0$$

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

代回目标函数，得到该树结构的最优目标值（structural score）：

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

这个值可以用来评分任意树结构——值越小（越负），树结构越好。

3.5 分裂增益

从一个叶节点分裂为两个叶节点带来的增益为：

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

其中：

前两项分别对应分裂后左、右子节点的”分数”
第三项对应分裂前父节点的”分数”
$\gamma$ 是分裂的”门槛费”——只有当增益超过 $\gamma$ 时才值得分裂

这完美地实现了预剪枝：$\gamma$ 直接控制了分裂的惩罚——大的 $\gamma$ 产生更浅的树。

3.6 近似分裂查找

GBDT 在寻找最优切分点时，需要列举所有可能的切分点并计算每个的增益——当数据量极大或特征值是连续的时，这非常昂贵。

XGBoost 使用的近似方法：

对特征分布提出候选切分点（如按分位数），而非列举所有值
将连续特征映射到候选切分点对应的”桶”中
按桶聚合梯度统计量 $G$ 和 $H$，基于聚合统计量计算分裂增益

两种候选切分点提议策略：

Global：在树构建初始就提议好候选切分点（每个分裂都使用）
Local：每次分裂前重新提议候选切分点

Global 更快但需要更多候选点；Local 候选点更精确但开销更大。实际中 Global 策略配合 $\epsilon \approx 0.05$（5% 分位数间隔）通常是够用的。

3.7 XGBoost 的缺失值处理

XGBoost 对缺失值的处理方法是学习缺失值应该默认分到左还是右。

具体来说，在评估每个切分点时，将缺失值分别”假想”到左边和右边，计算两种情况的增益，选择增益更大的那个方向作为该特征缺失值的默认方向。

这比简单的填充（均值/中位数）或丢弃更优雅——模型自动学到了缺失值的最优决策路径。

3.8 XGBoost 的系统优化

XGBoost 的一大成功之处在于系统工程层面的优化：

列块存储（Column Block）：训练前将数据按列排序后存储为压缩的块（block）格式，每个块内特征值连续存储且已排序。这使得分裂查找极其高效（只需线性扫描块）。
缓存感知访问（Cache-aware Access）：对块的处理进行缓存优化，减少 CPU cache miss。
核外计算（Out-of-core）：独立线程负责从磁盘预取数据块，使 XGBoost 可以处理比内存还大的数据集。

4. LightGBM

LightGBM 由微软团队于 2017 年提出，针对大数据量、高维特征场景进行了深度优化。它的名字本身就揭示了核心策略——Light（轻量）。

4.1 GOSS（Gradient-based One-Side Sampling，基于梯度的单边采样）

GOSS 是一种数据采样策略，核心思想：

保留梯度绝对值大的样本（这些样本对信息增益的贡献大，应该全部保留）
随机采样梯度绝对值小的样本（这些样本训练已经较好，可以部分丢弃以节省计算）

具体步骤：

对每个样本的梯度绝对值排序
保留 top $a \times 100%$ 的大梯度样本（全部使用）
从剩余的小梯度样本中随机采样 $b \times 100%$ 的样本
对采样的小梯度样本，计算分裂增益时乘以权重 $\frac{1-a}{b}$ 以恢复原始数据分布

这样，GOSS 在不损失太多信息的前提下大幅减少了训练数据量，尤其适合极大规模数据集。

4.2 EFB（Exclusive Feature Bundling，互斥特征捆绑）

在高维稀疏数据中（如 one-hot 编码后的文本特征），很多特征是互斥的（它们几乎从不同时非零）。EFB 将这些互斥特征”捆绑”到单个特征中，减少特征维数。

具体做法：

将寻找互斥特征集问题转化为图着色问题：特征为节点，非互斥关系为边，贪心着色找到最少颜色数
在每个特征簇内，通过给特征值加上偏移量（offset）来区分不同特征，将它们捆绑为一个新特征

例如：特征 A 取值 ${0, 1, 2}$，特征 B 取值 ${0, 1}$，两者互斥。捆绑后：

A 仍用 ${0, 1, 2}$，B 映射为 ${0+3=3, 1+3=4}$。新特征取值 ${0, 1, 2, 3, 4}$，没有冲突。

EFB 可将特征维数降低到原来的 1/3-1/5（取决于数据的稀疏程度）。

4.3 直方图算法（Histogram-based Algorithm）

LightGBM 最核心的加速是直方图算法：

将连续特征值离散化为 $k$ 个整数（桶，bins，默认 $k=255$）
构建特征直方图：每个桶内聚合梯度统计量
基于直方图搜索最优分裂点（只需遍历 $k$ 个桶而非所有 $n$ 个值）

时间复杂度：从 $O(n_{\text{data}} \times n_{\text{features}})$ 降到 $O(k \times n_{\text{features}})$。

且直方图可以使用做差法快速更新：父节点直方图减去其中一个子节点直方图即可得到另一个子节点的直方图（选择样本数少的那边来计算），进一步减半计算量。

4.4 Leaf-wise 生长策略

传统决策树（包括 XGBoost 默认）使用 Level-wise（按层生长）策略：每层所有叶节点一起分裂。

LightGBM 使用 Leaf-wise（按叶生长）策略：每次选择增益最大的那个叶节点进行分裂。

生长策略	优点	缺点
Level-wise	方便并行，树结构规整	分裂一些增益低的节点，浪费计算
Leaf-wise	用同样的分裂次数获得更低损失	可能生长出极深的树，容易过拟合

应对 Leaf-wise 易过拟合的方法：限制 max_depth 或 num_leaves。

4.5 LightGBM vs XGBoost 对比

维度	XGBoost	LightGBM
树生长策略	Level-wise（默认）	Leaf-wise
分裂查找	近似分位数 + 列块	直方图算法（bin k=255）
数据采样	列采样	GOSS + 列采样
特征降维	无	EFB（互斥特征捆绑）
类别特征	需手动编码	原生支持类别特征
内存消耗	中	低（直方图只需存 bin）
训练速度	快	更快（特别是高维稀疏数据）
小数据集（<10k）	通常更稳	Leaf-wise 可能过拟合
大数据集（>1M）	慢于 LightGBM	显著更快

5. CatBoost

CatBoost 由 Yandex 团队于 2017 年提出，名称源于”Categorical Boosting”，特色是对类别特征的原生支持。

5.1 有序目标编码（Ordered Target Encoding）

传统 GBDT 对类别特征的处理方式是 one-hot 编码（导致极高维稀疏特征，对树模型不友好）或标签编码（赋予类别一个任意整数，但决策树可能把 “3 > 2 > 1” 这个伪顺序当真）。

CatBoost 使用目标统计（Target Statistics）编码：将类别值替换为该类别对应的目标均值。

目标泄露问题：直接用训练数据计算每个类别的目标均值会导致数据泄漏（Data Leakage）——模型在训练时就”偷看”了标签信息，导致训练损失虚低而测试效果差。

CatBoost 的解决方案——Ordered TS：

引入一个人工的时间序列（Artificially Generated Time）：

随机打乱数据顺序
对每个样本，只用它之前的样本计算目标统计量（避免使用当前样本的标签）

具体公式：

$$\hat{x}_k^{i} = \frac{\sum_{x_j \in D_k, j < i} y_j + a \cdot P}{\sum_{x_j \in D_k, j < i} 1 + a}$$

其中 $D_k$ 是类别 $k$ 对应的样本子集，$j < i$ 表示只用样本 $i$ 之前的样本，$a > 0$ 是平滑参数，$P$ 是先验（通常为全体样本的目标均值）。

这种编码方式等价于对每个样本用一个”因果”模型（只用历史数据）来估计类别均值，完全避免了数据泄漏。

5.2 有序提升（Ordered Boosting）

标准 GBDT 的一个问题是预测偏移（Prediction Shift）：在训练第 $m$ 棵树时，训练集上每个 $x_i$ 对应的 $f_{m-1}(x_i)$ 使用了样本 $i$ 的标签（因为 $f_{m-1}$ 是在包含样本 $i$ 的数据上训练的）。这导致第 $m$ 棵树拟合梯度时存在偏差。

CatBoost 的 Ordered Boosting 同样利用”时间序列”：对每个样本 $x_i$，只用其”历史”样本训练一个只属于它的模型版本 $M_i$，计算梯度时使用 $M_i$。这保证了对样本 $i$ 来说，$M_i$ 从未在它身上训练过——保持了严格的”训练-梯度计算”分离。

在实践中，为了效率，CatBoost 只维持少量的模型快照（snapshot），而非每个样本一个模型。

5.3 对称树（Oblivious Trees / Symmetric Trees）

CatBoost 默认使用对称决策树（Symmetric Decision Tree）作为基学习器。这在深度学习的推理效率方面是巨大的优势。

对称树的特性：

同一层的所有内部节点使用相同的分裂特征和切分点
树的结构完全对称——树可以被紧凑地表示为一个查找表

优势：

推理极快：预测一个新样本等价于串联的 if-else，可被编译器优化为条件跳转序列
模型紧凑：存储一棵对称树只需 $O(d \cdot 2^d)$ 而非 $O(2^d)$
天然正则化：强制的对称结构本身限制了模型的表达能力（是一把双刃剑）

劣势：同样的表达能力下，对称树需要更深的深度

5.4 CatBoost vs LightGBM vs XGBoost 综合对比

维度	XGBoost	LightGBM	CatBoost
提出者/年	陈天奇, 2016	微软, 2017	Yandex, 2017
类别特征	需手动编码	支持但不处理泄漏	原生支持（Ordered TS）
树结构	CART（非对称）	CART（非对称）	对称树（默认）
分裂查找	近似分位数+列块	直方图	直方图
正则化	$\ell_2$ 正则	$\ell_2$ 正则	Ordered Boosting
缺失值	学习默认方向	学习默认方向	学习默认方向
多分类	需训练 K 棵树/轮	需训练 K 棵树/轮	原生多分类
GPU 支持	好	好	好
调参难度	中（参数多）	低	极低（默认参数很强）
小数据（<1k）	易过拟合	更易过拟合	稳健
大数据（>1M）	中等	最快	快

6. 提升算法的理论：偏差-方差分解与 AdaBoost 边缘理论

6.1 Boosting 的偏差降低机制

每一轮 Boosting 新加入的基学习器拟合的是当前模型的残差（梯度）。这意味着：

第 1 棵树拟合原始目标：$f_1(x) \approx y$
第 2 棵树拟合第 1 棵树的误差：$f_2(x) \approx y - f_1(x)$
第 3 棵树拟合前两棵树的误差：$f_3(x) \approx y - f_1(x) - f_2(x)$

$$f_M(x) = \sum_{m=1}^{M} f_m(x) \approx y$$

每次新增的树都在”填补”当前模型的不足。这个过程类似于对未知函数 $y = f^*(x)$ 做正交基展开——每棵树对应一个基函数，Boosting 对应贪婪的前向选择。

因此 Boosting 主要降低偏差：弱学习器（如 depth=3 的决策树）本身是高偏差低方差的，Boosting 通过串行组合逐步加强表达能力，将偏差压低。这就是为什么 Boosting 用浅树——每棵树不需要强，但合在一起很强。

6.2 为什么 Boosting 不容易过拟合？

直觉上，Boosting 随着迭代次数增加，训练误差持续下降，但测试误差并不一定会随之上升（有时甚至继续下降）。原因：

Margin 理论（Schapire et al.）：AdaBoost 即使在训练误差为 0 后继续增加弱分类器，margin 仍在增大，泛化性能可能继续提升。
Shrinkage（$\eta < 1$）：每棵树只走一小步，Boosting 过程是 smooth 的，相当于在函数空间中做小步长的梯度下降。小步长天然具有正则化效果。
早停（Early Stopping）：在实践中，Boosting 最终还是会过拟合（只是较慢）。通常使用验证集上的早停来选择最优的 $M$（即 n_estimators）。

6.3 Boosting vs Bagging 的统计视角

	Bagging (Random Forest)	Boosting (GBDT/XGBoost)
核心目标	降方差	降偏差
基学习器	强（深树）	弱（浅树）
组合方式	并行平均	串行加性
过拟合风险	低（平均削峰）	中（最终会过拟合但较慢）
训练方式	可完美并行化	串行（但内部操作可并行）
适用场景	高方差高噪数据	低偏差结构化数据
典型性能	方差低，偏差中	偏差低，方差中

7. XGBoost 系统优化深度剖析

7.1 稀疏感知分裂（Sparsity-aware Split Finding）

现实数据中，稀疏性无处不在：缺失值、one-hot 编码产生的 0、统计意义上的零值等。XGBoost 对稀疏性的处理不是在数据预处理阶段填充缺失值，而是将稀疏性视为一种信息。

XGBoost 为每个树节点添加了默认方向（Default Direction）：当样本在某特征上缺失时，算法学习该特征的最优”默认子节点”（左或右）。

具体算法是在计算每个可能切分点的增益时，分别考虑将缺失值全部归入左节点和全部归入右节点两种情况，取增益较大者。这使得缺失值处理与分裂查找天然内嵌在一起，不需要额外的数据预处理步骤。

与简单的均值/中位数填充相比，这种方法的优势是：

保留了缺失本身可能是信号的可能性（例如：收入缺失可能意味着失业或不愿透露，本身就是有价值的特征）
默认方向是根据数据自动学习的最优决策

7.2 列块存储与缓存优化

XGBoost 使用 Block 结构来组织数据。训练开始前，将数据按列（特征）存储在内存中：

每个 Block 包含该特征的所有样本值，按特征值预排序
同时存储对应的样本索引和梯度统计量指针
分裂查找时，只需线性扫描该特征的 Block，聚合 $G$ 和 $H$ 统计量

Block 结构使得分裂查找变为：

for each feature:
    G_L = 0, H_L = 0
    for each sample in sorted order:
        G_L += g_i,  H_L += h_i
        G_R = G_total - G_L,  H_R = H_total - H_L
        score = Gain(G_L, H_L, G_R, H_R)
        update best if score > best

缓存命中优化：由于 Block 按特征值排序，访问梯度统计量 $g_i, h_i$ 时使用的是样本索引，这会导致非连续内存访问（cache miss）。XGBoost 使用预取（Prefetching）技术，在 CPU 需要数据之前将其从主存加载到缓存。

对于近似分裂算法，XGBoost 更进一步：只需聚合每个分位数桶内的 $G, H$，桶的数量远小于样本数，自然减少了 cache miss。

7.3 多线程并行策略

虽然 Boosting 的迭代是串行的，但每一轮内部构建单棵树的过程可以并行化。XGBoost 的并行发生在多个层级：

特征级并行：不同特征的分裂增益计算可以并行（每个特征独立扫描自己的 Block）
节点级并行：树的同一层中不同节点的分裂可以并行（因为节点间的样本集是不相交的）
I/O 并行：使用独立线程进行磁盘读取（Out-of-core）

在核外计算场景中，XGBoost 使用块压缩（Block Compression）和分片（Block Sharding）技术，将压缩数据小块交替地读入主存，由计算线程处理。I/O 线程负责从磁盘预读，计算线程负责运算，二者以流水线方式运作。

7.4 加权分位数草图（Weighted Quantile Sketch）

XGBoost 的近似分裂算法依赖分位数切分点，但不是普通的分位数，而是加权分位数——每个样本的权重为其二阶梯度 $h_i$。

给二阶导数 $h_i$ 大的样本分配更大的权重意味着：模型在这些样本处”曲率大”（变化剧烈），需要在附近设置更密的候选切分点来提高精度。

XGBoost 支持合并式（mergeable）加权分位数草图数据结构，可以高效地处理分布式场景下的分位数合并。这是论文中一个被广泛引用但不常被业务人员提及的技术亮点。

8. 超参数调优实战

8.1 通用调参顺序（适用于 XGBoost / LightGBM）

调参有一个共识的优先级顺序。以下按重要性从高到低排列：

第一步：确定 n_estimators（树的数量）

使用默认参数（或经验值），仅通过早停（early stopping）确定最优的树数量。设置一个较大的 n_estimators（如 5000），配合 early_stopping_rounds（如 50）。

# XGBoost
model = xgb.XGBClassifier(n_estimators=5000, early_stopping_rounds=50, eval_set=[(X_val, y_val)])

第二步：调节树的复杂度（防过拟合）

max_depth（典型搜索范围 3-10）或 num_leaves（LightGBM，通常设为 $2^{\text{max_depth}}-1$ 再下调），min_child_weight / min_data_in_leaf（增大可防过拟合），gamma（XGBoost 的分裂门槛）。

第三步：调节随机性和正则化

subsample（行采样率，通常 0.6-1.0），colsample_bytree / feature_fraction（列采样率，通常 0.6-1.0），reg_lambda（L2 正则化），reg_alpha（L1 正则化）。

第四步：调节学习率

降低 learning_rate（如 0.01），同时按比例增加 n_estimators，重新用早停选择。这是获得最终精度提升的最后一步。

8.2 各框架核心参数速查

参数	XGBoost	LightGBM	CatBoost	说明
学习率	`learning_rate` / `eta`	`learning_rate`	`learning_rate`	默认 0.3，实际常用 0.01-0.1
树数量	`n_estimators`	`n_estimators` / `num_iterations`	`iterations`	配合早停
树深度	`max_depth`	`max_depth`	`depth`	默认 6
叶节点数	-	`num_leaves`	-	LightGBM 特有，建议 < $2^{\text{max_depth}}$
最小子节点权重	`min_child_weight`	`min_data_in_leaf` / `min_sum_hessian_in_leaf`	-	增大防过拟合
行采样	`subsample`	`bagging_fraction`	`subsample`	每棵树随机采样行比例
列采样（by tree）	`colsample_bytree`	`feature_fraction`	-	每棵树随机采样特征比例
L2 正则化	`lambda` / `reg_lambda`	`lambda_l2`	`l2_leaf_reg`	默认 1
L1 正则化	`alpha` / `reg_alpha`	`lambda_l1`	-	默认 0
分裂门槛	`gamma`	`min_split_gain`	-	需增益超过门槛才分裂
早停轮数	`early_stopping_rounds`	`early_stopping_round`	`early_stopping_rounds`	验证集上轮数无改善则停止

8.3 常见问题排查

症状	可能原因	解决方案
训练损失快速降到接近 0，验证损失不降	过拟合	增大正则化、减小 max_depth、增加 min_child_weight
训练损失也不怎么降	欠拟合/学习率太小	增加 max_depth、减小正则化、增大 learning_rate
训练很慢	树太深、数据太大	减小 max_depth、启用 GPU、使用直方图模式（XGBoost `tree_method='hist'`）
内存不够	数据量太大	使用 LightGBM（更低内存）、增加 bin 数（减少反而省内存）、核外计算
类别特征处理不佳	使用了默认的 one-hot	LightGBM 用 `categorical_feature`，CatBoost 用 `cat_features`

9. 深入推导与数值案例

9.1 GBDT 函数空间梯度下降的严格推导

我们从一个更严格的视角来审视 GBDT。定义函数空间 $\mathcal{F}$ 和损失泛函 $\mathcal{L}[f] = \sum_{i=1}^{N} L(y_i, f(x_i))$。

GBDT 在每一步求解：

$$h_m = \arg\min_{h \in \mathcal{H}} \sum_{i=1}^{N} L(y_i, f_{m-1}(x_i) + h(x_i))$$

其中 $\mathcal{H}$ 是基学习器（决策树）构成的函数空间。

对 $L(y_i, f_{m-1}(x_i) + h(x_i))$ 在 $f_{m-1}(x_i)$ 处做一阶 Taylor 展开：

$$L(y_i, f_{m-1}(x_i) + h(x_i)) \approx L(y_i, f_{m-1}(x_i)) + g_i \cdot h(x_i)$$

其中 $g_i = \frac{\partial L}{\partial f}|{f=f{m-1}(x_i)}$。

去掉常数项 $L(y_i, f_{m-1}(x_i))$，优化目标变为：

$$\min_{h \in \mathcal{H}} \sum_{i=1}^{N} g_i \cdot h(x_i)$$

对于任意 $h$，取 $h(x_i) = -\rho g_i$ 时上式最小（在 $\rho > 0$ 的条件下）。但由于 $h$ 必须是 $\mathcal{H}$ 中的函数，我们转而找一个 $h$ 使得 $h(x_i)$ 与 $-g_i$ 尽可能接近。

在 $L^2$ 范数下，这等价于最小二乘拟合：

$$h_m = \arg\min_{h \in \mathcal{H}} \sum_{i=1}^{N} (h(x_i) - (-g_i))^2 = \arg\min_{h \in \mathcal{H}} \sum_{i=1}^{N} (h(x_i) + g_i)^2$$

等号成立的条件：当 $L$ 是平方损失时，Taylor 展开的一阶近似是精确的（因为平方损失在 $f$ 上是二次的），此时拟合负梯度等价于拟合原始残差。

9.2 损失函数梯度对比：一个数值示例

考虑一个回归问题，对某个样本 $x_i$，真实值 $y_i = 3.0$，当前预测值 $f(x_i) = 1.0$（差值为 2.0）。

平方损失 $L(y, f) = \frac{1}{2}(y - f)^2$：

梯度：$g = -(y - f) = -(3 - 1) = -2.0$
负梯度：$-g = 2.0 = y - f$（恰好是残差）
新预测：$f_{\text{new}} = 1.0 + \eta \times 2.0 = 1.0 + 2.0\eta$

绝对损失 $L(y, f) = |y - f|$：

梯度：$g = -\text{sign}(y - f) = -\text{sign}(2) = -1.0$
负梯度：$-g = 1.0$（符号方向，大小恒为 1）
新预测：$f_{\text{new}} = 1.0 + \eta \times 1.0 = 1.0 + \eta$

对于绝对损失，无论差距多大，每次只走固定步长 $\eta$，这使得它对异常值（outliers）比平方损失更鲁棒——大残差的样本不会主导模型更新方向。

Huber 损失（综合平方损失和绝对损失的优点）：

$$L_\delta(y, f) = \begin{cases} \frac{1}{2}(y-f)^2 & \text{if } |y-f| \leq \delta \\ \delta |y-f| - \frac{1}{2}\delta^2 & \text{if } |y-f| > \delta \end{cases}$$

小残差：平方损失（精确拟合）
大残差：线性损失（鲁棒性）

梯度是分段线性的，实现时只需加一个 if 判断。

9.3 XGBoost 叶子权重公式的完整推导

在第 3.4 节我们给出了结果，这里给出完整推导。

设第 $m$ 轮需要优化目标：

$$\tilde{\mathcal{L}}^{(m)} = \sum_{j=1}^{T} \left[ G_j w_j + \frac{1}{2}(H_j + \lambda) w_j^2 \right] + \gamma T$$

其中 $G_j = \sum_{i \in I_j} g_i$, $H_j = \sum_{i \in I_j} h_i$。

对 $w_j$ 求导：

$$\frac{\partial \tilde{\mathcal{L}}}{\partial w_j} = G_j + (H_j + \lambda) w_j$$

令为 0：

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

代入目标函数求该树结构对应的最优损失：

$$\begin{aligned} \tilde{\mathcal{L}}^* &= \sum_{j=1}^{T} \left[ G_j \left(-\frac{G_j}{H_j+\lambda}\right) + \frac{1}{2}(H_j+\lambda)\frac{G_j^2}{(H_j+\lambda)^2} \right] + \gamma T \\ &= \sum_{j=1}^{T} \left[ -\frac{G_j^2}{H_j+\lambda} + \frac{1}{2}\frac{G_j^2}{H_j+\lambda} \right] + \gamma T \\ &= -\frac{1}{2}\sum_{j=1}^{T} \frac{G_j^2}{H_j+\lambda} + \gamma T \end{aligned}$$

分裂增益：将叶节点 $j$ 分裂为左子节点 $L$ 和右子节点 $R$ 后的损失变化：

$$\begin{aligned} \text{Gain} &= \tilde{\mathcal{L}}_{\text{before}} - \tilde{\mathcal{L}}_{\text{after}} \\ &= \left[-\frac{1}{2}\frac{(G_L+G_R)^2}{H_L+H_R+\lambda} + \gamma\right] - \left[-\frac{1}{2}\frac{G_L^2}{H_L+\lambda} -\frac{1}{2}\frac{G_R^2}{H_R+\lambda} + 2\gamma\right] \\ &= \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 \end{aligned}$$

Gain > 0 意味着分裂后损失减小（结构更优）。XGBoost 选择 Gain 最大的 $(feature, split)$ 对进行分裂。

这个公式的优雅之处在于：它不需要知道单个样本的预测值，只需要对每个叶节点聚合的 $G_j$ 和 $H_j$（一阶导和二阶导之和）。这就是 XGBoost 能够高效训练的核心数学性质。

9.4 LightGBM 直方图做差法的数学原理

假设父节点 $P$ 分裂为左子节点 $L$ 和右子节点 $R$。$L$ 和 $R$ 对应的样本集是 $P$ 的一个划分（不相交且覆盖 $P$）。

父节点直方图在每个 bin 上存的是 ($G_P, H_P$)。构建子节点的直方图：

构建较小的子节点（设为 $L$）的直方图：遍历 $L$ 中的所有样本，聚合到对应 bin
$R$ 的直方图 = $P$ 的直方图 - $L$ 的直方图：对每个 bin，$G_R = G_P - G_L$, $H_R = H_P - H_L$

这样我们只为样本较少的子节点构建直方图（做差法省去了另一半计算量）。由于 $L$ 和 $R$ 中总有一个 $\leq |P|/2$，做差法将每层的直方图构建成本从 $O(|P|)$ 降到 $O(\min(|L|, |R|)) \leq O(|P|/2)$，再叠加每层 2 倍于上一层的节点数，总体节省约 40%-50%。

9.5 提升算法的特征重要性

GBDT/XGBoost/LightGBM 提供了几种特征重要性度量：

类型 1：分裂次数（split / weight）：特征 $j$ 被用作分裂节点的次数。

类型 2：增益（gain）：在所有使用特征 $j$ 的分裂中，不纯度减少（或 Gain）的总和。这是实践中最有意义的特征重要性度量。

$$\text{importance}_{\text{gain}}(j) = \sum_{t: \text{split on } j} \text{Gain}_t$$

类型 3：覆盖度（cover）：在所有使用特征 $j$ 的分裂中，涉及样本的总数。

$$\text{importance}_{\text{cover}}(j) = \sum_{t: \text{split on } j} N_t$$

对于 XGBoost，Gain 即第 3.5 节定义的 $\text{Gain}$ 值。对于 LightGBM，split 和 gain 是主要参考指标。

注意：基于树模型的特征重要性存在偏倚——倾向于高估高基数特征的重要性（与信息增益偏向多值特征同源）。permutation importance 是更无偏的替代方案。

10. 提升算法的演进：从理论到工业

10.1 提升方法的”算法家族树”

Kearns & Valiant (1988)
  "Can weak learners be boosted to strong learners?"
      │
      ▼
Schapire (1990)
  构造性证明：Yes, they can!
      │
      ▼
AdaBoost (Freund & Schapire, 1995)
  样本权重 + 加权投票
  Godel Prize 2003
      │
      ├──► LogitBoost (Friedman et al., 2000)
      │      用 logistic 损失替代指数损失
      │
      ├──► GBDT (Friedman, 2001)
      │      任意可微损失 + 函数空间梯度下降
      │      │
      │      ├──► Stochastic GBDT (Friedman, 2002)
      │      │      加入子采样，类似 Bagging
      │      │
      │      ├──► LambdaMART (Burges, 2010)
      │      │      GBDT + Ranking 损失 → 搜索排序神器
      │      │
      │      ├──► XGBoost (Chen & Guestrin, 2016)
      │      │      二阶展开 + 正则化 + 系统优化
      │      │
      │      ├──► LightGBM (Ke et al., 2017)
      │      │      直方图 + GOSS + EFB + Leaf-wise
      │      │
      │      └──► CatBoost (Prokhorenkova et al., 2017)
      │             Ordered TS + Ordered Boosting
      │
      └──► Gradient Boosting 在深度学习中的应用
            ├── TabNet (Arik & Pfister, 2019)
            └── NODE (Popov et al., 2019)

10.2 每种方法的历史定位

**AdaBoost (1995)**：理论的胜利。证明了”弱学习器可提升为强学习器”不仅是理论上的可能性，而且是可行的算法。它的影响超越了机器学习本身——它启发了集成学习和 margin 理论的发展。
**GBDT (2001)**：工程的奠基。Friedman 的三大贡献——(1) 泛化到任意损失函数、(2) 函数空间梯度下降、(3) Stochastic Boosting——奠定了现代 Boosting 的理论框架。此后所有改进（XGBoost, LightGBM, CatBoost）都是在 GBDT 的框架内做加法。
**XGBoost (2016)**：工业化的标志。陈天奇的贡献主要在于将 GBDT 做成了一个”计算产品”——系统层面的优化（列块、缓存、并行、核外）使 XGBoost 成为 2016 年后 Kaggle 竞赛中最常用的算法。
**LightGBM (2017)**：极致效率。微软对训练速度和内存使用的压倒性优化。GOSS+EFB+直方图三个技术叠加，使得在亿级数据上训练 GBDT 变得可行。
**CatBoost (2017)**：零调参哲学。Yandex 的目标是让 GBDT “开箱即用”——默认参数就能给出有竞争力的结果。Ordered TS/Boosting 解决了类别特征和预测偏移两个痛点，”用 CatBoost 做 baseline”已成为许多数据科学团队的习惯。

10.3 提升方法 vs 深度学习（表格数据）

2023 年以后，虽然深度学习在 CV/NLP 领域占据主导，但在结构化/表格数据（tabular data）领域，GBDT 系列方法仍然：

在 Kaggle 竞赛的 Tabular 赛道上、
在工业界的 CTR 预估、金融风控、医疗诊断、供应链预测中、
与深度学习方法（如 TabNet, FT-Transformer, SAINT）的比较中

持续占据领先或在误差范围内平手的位置。主要原因是：

表格数据的特征通常是异构和语义化的（年龄、收入、类别），不像图像像素那样具有平移不变性等归纳偏置
树模型天然处理异构特征（连续 + 离散 + 缺失），而神经网络需要大量预处理
树模型的决策边界是轴平行的（axis-aligned），这在表格数据上恰好是一个有用的归纳偏置
GBDT 的集成结构天然鲁棒于异常值和尺度差异
训练成本对比：GBDT 可以在 GPU 上极快训练，而 Transformer 类模型训练计算量是其 10-100 倍

因此，对于从业者来说，掌握 Boosting 方法的理论和实践技能，仍然是机器学习领域最具”投入产出比”的知识投资之一。

11. 面试高频问答

Q1: AdaBoost 的样本权重更新公式是怎么推导出来的？

A: AdaBoost 本质上是在最小化指数损失函数 $\sum_i \exp(-y_i f(x_i))$ 的框架下，使用前向分步加法模型。在第 $m$ 轮，当前模型为 $f_{m-1}$，新的基分类器 $G_m$ 和权重 $\alpha_m$ 通过最小化 $\sum_i \exp(-y_i(f_{m-1}(x_i) + \alpha G_m(x_i)))$ 得到。将这个目标重写为 $e^{-\alpha}(1 - e_m) + e^{\alpha} e_m$（其中 $e_m$ 是加权误差率），对 $\alpha$ 求导令为 0 得到 $\alpha_m = \frac{1}{2}\ln\frac{1-e_m}{e_m}$。权重更新 $w_{m+1,i} \propto w_{mi} \exp(-\alpha_m y_i G_m(x_i))$ 直接来自指数损失函数的乘法结构。这不是启发式的，是严格的最优性推导。

Q2: GBDT 拟合的是什么？残差还是梯度？

A: GBDT 拟合的是负梯度，而不是残差。但在平方误差损失函数下，负梯度恰好等于残差 $y - f(x)$，所以很多人误以为 GBDT 拟合残差。实际上，对于其他损失函数（如绝对误差的梯度是 sign($y-f$)，Logistic 损失的梯度是 $y/(1+e^{yf})$），负梯度不等于残差。正确的理解是：GBDT 的每一棵树去拟合损失函数在当前模型预测值处的负梯度方向——这等价于在函数空间中进行梯度下降。

Q3: XGBoost 相比 GBDT 的核心改进有哪些？

二阶泰勒展开：使用 Hessian 信息（二阶导数），比仅用一阶梯度的 GBDT 收敛更快更准。叶节点权重有闭式解 $w_j^* = -G_j/(H_j+\lambda)$。
显式正则化：加入 $\gamma T$（叶节点数惩罚）和 $\frac{1}{2}\lambda|w|^2$（权重 L2 正则），等价于内置剪枝。
近似分裂查找：通过分位数提议候选切分点，支持大规模数据。
列块存储 + 缓存优化：系统层的优化使训练速度远超原生 GBDT。
缺失值自动处理：学习缺失值的最优默认方向。
列采样：类似 Random Forest 的特征采样，减少过拟合。
此外，XGBoost 还支持自定义损失函数（只需提供一阶导和二阶导函数）。

Q4: LightGBM 为什么比 XGBoost 训练更快？

A: 三个核心加速：

直方图算法：将连续值离散化为 255 个 bins，分裂查找复杂度从 $O(n)$ 降到 $O(255)$。配合做差法，子节点直方图可以 $O(255)$ 从父节点计算。
GOSS（基于梯度的单边采样）：保留梯度大的样本，随机采样梯度小的样本。在不显著损失信息的前提下大幅减少训练样本数。
EFB（互斥特征捆绑）：将高维稀疏数据中互斥的特征捆绑，将特征维数压缩到原来的 1/3-1/5。

另外，Leaf-wise 生长策略使每次分裂的增益更大（直接用最优点分裂），相比 Level-wise（按层全部分裂）用更少的分裂次数达到同样的损失。

Q5: XGBoost 中 $\gamma$ 和 $\lambda$ 参数的作用是什么？

A: 这两个参数出现在 XGBoost 的正则化项 $\Omega(f) = \gamma T + \frac{1}{2}\lambda|w|^2$ 中。

$\gamma$（gamma）：控制叶节点数的惩罚，是分裂的”最低门槛”。只有分裂增益 > $\gamma$ 时才进行分裂。更大的 $\gamma$ 产生更浅的树，相当于更强的预剪枝。默认值 0（不惩罚）。
$\lambda$（lambda / reg_lambda）：控制叶节点权重的 L2 正则化。权重公式 $w_j^* = -G_j/(H_j+\lambda)$ 中，$\lambda$ 出现在分母——更大的 $\lambda$ 压缩权重，防止单棵树”抢话”。默认值 1。

调参建议：在过拟合时增大 $\gamma$ 和 $\lambda$，在欠拟合时减小它们。

Q6: CatBoost 的 Ordered Target Encoding 解决了什么问题？

A: 传统目标编码（将类别替换为该类别的目标均值）存在数据泄漏（Data Leakage）问题：计算类别 $A$ 的目标均值时使用了样本 $i$ 自身的标签，导致模型在训练时就已经”偷看”了正确答案。这使训练误差虚低，但测试时泛化差。

CatBoost 的解决方案是时间序列仿真：打乱数据后，对每个样本只使用其”前面”的样本来计算该类别目标统计量：$\hat{x}k^i = \frac{\sum{j \in D_k, j < i} y_j + aP}{\sum_{j \in D_k, j < i} 1 + a}$。这样保证了对样本 $i$ 来说，其自身的标签从未参与编码计算。$a$ 是平滑参数，$P$ 是先验——这等价于一个 Bayesian 收缩估计。

这一设计保证了编码过程中没有信息泄漏，是 CatBoost 相比 LightGBM/XGBoost 在处理大量类别特征时的核心优势。

Q7: 为什么 Boosting 用浅树（depth=3-6）而 Random Forest 用深树？

A: 这源于两者在 Bias-Variance 谱系中的不同定位：

Boosting 降偏差：每个浅树是高偏差、低方差的学习器。多棵浅树串行组合逐渐降低偏差（就像逐段线性逼近曲面）。如果 Boosting 用深树，每棵树已经是低偏差的了，再加更多树容易过拟合且计算浪费。
Random Forest 降方差：每棵深树是低偏差、高方差的学习器。多棵高方差但互不相关的树并行平均来降低方差（就像采样取均值）。如果用浅树，每棵树偏差太高，平均之后偏差不降。

因此：Boosting → 浅树（depth 3-6），Random Forest → 深树（depth 10+，甚至完全生长不剪枝）。

Q8: GBDT 中 shrinkage（学习率 $\eta$）和 n_estimators（树的数量）之间有什么关系？

A: 经验上，$\eta$ 和 $M$（n_estimators）呈反比关系：$\eta \times M \approx \text{常数}$。例如 $\eta = 0.1, M = 100$ 和 $\eta = 0.01, M = 1000$ 在偏差意义上接近。但更小的 $\eta$ + 更多的树通常能获得更好的泛化（类似 SGD 中小学习率 + 多 epoch）。实践中：

$\eta = 0.01-0.1$ 是常见范围
通过早停（early stopping）来自动选择最优 $M$，而不是手动指定
如果计算资源允许，建议 $\eta$ 设小（如 0.01），用验证集早停选择 $M$

Q9: 在什么情况下 Boosting 的效果可能不如 Random Forest？

数据噪声极大：Boosting 串行地将每棵树拟合误差，噪声数据中的随机误差被模型”学会了”。RF 通过并行平均，噪声被相互抵消。在高噪声场景下，Boosting 可能严重过拟合，而 RF 的方差缩减能产生更好的泛化。
样本量很少（如 < 1000）：Boosting 需要足够的数据来逐步学习复杂边界，样本太少时每棵树拟合的梯度不够稳定。
高维 + 低信号：大量无用特征时，Boosting 的每棵树面临大量噪声特征，而 RF 的随机特征子集虽然也受影响，但集成的去相关性反而有帮助。
需要可复现的训练：RF 的随机种子影响相对较小（多棵树平均），而 Boosting 由于串行误差累积，对随机种子的敏感度更高。

Q10: LightGBM 的 leaf-wise 生长策略会不会导致过拟合？如何防止？

A: Leaf-wise 每次选择增益最大的叶节点分裂，这使得同样的分裂次数下树可能非常深且不对称——最深的一条路径可以包含非常多的特征交互（在 level-wise 中，所有路径深度一致，最深路径被限制了）。这意味着 leaf-wise 确实有更强的过拟合倾向。

防治方法：

**限制 num_leaves**（而不是 max_depth）：num_leaves = 31 相当于一个 depth=5 的平衡树。建议从 $2^{\text{max_depth}} - 1$ 开始逐步降低。
**增大 min_data_in_leaf**：限制叶节点最少样本数
**增大 min_sum_hessian_in_leaf**：限制叶节点最小 Hessian 和（类似 XGBoost 的 min_child_weight）
**增大 lambda_l1 / lambda_l2**：正则化叶节点权重
**限制 max_depth**（即使 leaf-wise 也通常设置）：提供一个硬上限
使用早停：最关键的保护机制

在实践中，leaf-wise + 适当限制通常是优于 level-wise 的选择（这也是 LightGBM 默认策略）。

12. 总结

从 1995 年的 AdaBoost 到 2017 年的 CatBoost，Boosting 算法经历了一个从理论到实践日臻完美的演进过程。理解这条演进脉络，等于理解了机器学习在过去二十多年里最成功的算法家族：

**AdaBoost (1995)**：开创了”提升”的概念——弱学习器的加权组合可以成为强学习器。指数损失的最小化严格导出了权重更新公式。
**GBDT (2001)**：将 Boosting 推广到任意可微损失函数。”拟合负梯度”这一函数空间梯度下降的视角，将 Boosting 纳入了通用优化框架。
**XGBoost (2016)**：二阶泰勒展开 + 显式正则化 + 系统工程优化。将 GBDT 做成了一个”工业级的机器学习算法”——既能处理极大数据，又自带防过拟合机制。
**LightGBM (2017)**：直方图算法 + GOSS + EFB + Leaf-wise。针对海量高维稀疏数据场景的极致速度优化。
**CatBoost (2017)**：Ordered TS + Ordered Boosting + 对称树。解决类别特征编码中的数据泄漏问题，默认参数即可获得 competitive 的结果。

选型建议：

数据量 < 10k，特征简单 → XGBoost（稳健，社区成熟）
数据量 > 100k，特征维数高 → LightGBM（快）
大量类别特征，不想手动编码 → CatBoost（开箱即用）
作为 baseline → 先用 CatBoost（无需调参就能有不错结果），再考虑是否切换

本系列下一篇文章将深入探讨隐马尔可夫模型（HMM）——从马尔可夫链到三大经典问题，敬请期待。

Boosting 性能对比简表（典型 Kaggle 数据集上的相对精度，DeepTab 基准）：

方法	Relative LogLoss	训练时间 (相对)	内存 (相对)
Random Forest	1.00 (baseline)	1.0x	1.0x
GBDT (sklearn)	0.95 (better)	1.5x	1.2x
XGBoost	0.91	1.2x	1.5x
LightGBM	0.90	0.8x (最快)	0.6x
CatBoost	0.89 (最优)	2.0x	2.5x
FT-Transformer	0.90	10x+	5x+

在表格数据上，GBDT 系方法（特别是 LightGBM/CatBoost）在精度-速度-内存的综合 Pareto 前沿上仍然占据优势。深度学习方法通常需要 10x+ 的训练成本才能达到相近甚至略低的精度。

从 1990 年 Schapire 的构造性证明、1995 年的 AdaBoost、2001 年的 GBDT 到 2016-2017 的 XGBoost/LightGBM/CatBoost 三剑客，Boosting 的发展史就是机器学习从理论走向工程、从学术走向工业的缩影。掌握它不仅仅是掌握一个算法——是掌握了现代数据科学中最有价值的生产力工具。

这是本系列的第五篇。深度学习方法通常需要 10x+ 的训练成本才能达到相近甚至略低的精度。

扩展阅读推荐：

Friedman (2001), Greedy Function Approximation: A Gradient Boosting Machine — GBDT 的奠基之作
Chen & Guestrin (2016), XGBoost: A Scalable Tree Boosting System — XGBoost 论文
Ke et al. (2017), LightGBM: A Highly Efficient Gradient Boosting Decision Tree — LightGBM 论文
Prokhorenkova et al. (2018), CatBoost: unbiased boosting with categorical features — CatBoost 论文
Schapire & Freund (2012), Boosting: Foundations and Algorithms — Boosting 的理论圣经
Nielsen (2016), Tree Boosting With XGBoost — Why Does XGBoost Win “Every” Machine Learning Competition? (thesis)