跳转至

Boosting ｜ GBDT⚓︎

约 2329 个字 1 张图片 预计阅读时间 8 分钟 总阅读量 次

前置内容 决策树（用于回归的 CART）、AdaBoost。

用作回归任务。区别于Adaboost在于，不用小的 Stump 了，而是用一些尺寸相同但是限制规模的 树 （比如，8个叶子，或者32个叶子节点）组成森林。

更重要的是，我们不再单单对预测值进行学习，而是对“某个预测值的残差进行学习”。

每一个新建立的小树，都会学习先前的残差 （加上一个特定的学习率），类似一次走一小步，每次逼近一点“正确的方向”。每次都在前一个“预测值”的基础上，学习残差。

终止条件是：Residual 的减少不明显了，或者到达一定迭代次数了。

GBDT (Gradient Boosting Decision Tree)，即梯度提升决策树，是当今工业界和数据科学竞赛中使用最广泛、效果最好的机器学习算法之一。它也是理解 XGBoost、LightGBM 和 CatBoost 等更先进算法的基础。

GBDT 是一种同样采用加法模型（Additive Model）和前向分步算法（Forward Stagewise Algorithm）的 Boosting 算法。与 AdaBoost 通过提升错分样本的权重来学习不同，GBDT 的核心思想是，每一棵新的树都是为了拟合和修正上一棵树留下的残差（Residual）。更一般地说，是拟合损失函数的负梯度。

1. 使用场景⚓︎

GBDT 是一个非常通用的框架，既能用于回归问题，也能用于分类问题，并且在两者上都表现出色。

  • 回归问题：这是 GBDT 最直观的应用。例如预测房价、预测股票价格、预测用户停留时长等。
  • 分类问题：通过使用不同的损失函数（如对数损失函数），GBDT 在分类任务上同样强大。例如广告点击率（CTR）预测、信用风险评估、用户流失预测等。
  • 排序问题：GBDT 也可以用于学习排序（Learning to Rank），如搜索结果排序。

由于其高精度、可解释性（可以输出特征重要性）以及对多类型数据的良好处理能力，GBDT 在各大公司的推荐、风控、搜索等核心业务中扮演着至关重要的角色。

2. 核心思想：拟合残差与梯度下降⚓︎

GBDT 的思想比 AdaBoost 更进了一步，也更为通用。我们可以从两个层面来理解它。

  1. 直观理解（以回归为例）： 假设我们正在做一个预测年龄的任务，第一个基学习器（一棵树）预测某人的年龄是30岁，但他的真实年龄是35岁。那么模型就留下了 5 岁的残差（residual = 35 - 30 = 5）。GBDT 的下一步就是训练第二棵树，这棵树不再以人的特征为输入、年龄为输出来学习，而是以人的特征为输入、刚才那个5岁的残差为输出来学习。如果第二棵树成功预测了这个残差，那么 新预测 = 30 + 5 = 35，就命中了真实值。当然，第二棵树也不可能完美预测，它会留下新的、更小的残差。GBDT 就是这样一轮一轮地通过训练新树来不断减少之前模型留下的总残差，从而逼近真实值。

  2. 数学理解（梯度下降）： GBDT 的精髓。GBDT 将模型的优化过程看作是在函数空间（Function Space）中的梯度下降。

    • 我们的目标是找到一个模型 \(F(x)\)，使得所有样本的损失函数 \(L(y, F(x))\) 之和最小。
    • GBDT 是一个加法模型，最终模型 \(F_M(x)\) 是由 \(M\) 棵树累加而成的：\(F_M(x) = F_0(x) + F_1(x) + ...\)。
    • 在第 \(m\) 步，我们已经有了模型 \(F_{m-1}(x)\)，我们希望找到一棵新树 \(h_m(x)\)，使得损失函数进一步下降：\(L(y, F_{m-1}(x) + h_m(x))\)。
    • GBDT 使用了梯度下降的思路来近似求解。它计算出当前损失函数相对于模型预测值 \(F_{m-1}(x)\) 的负梯度，并将这个负梯度值作为本轮要拟合的目标（即“残差”）。
    \[
\text{本轮拟合目标} \approx - \left[ \frac{\partial L(y_i, F(x_i))}{\partial F(x_i)} \right]_{F(x) = F_{m-1}(x)}
\]

    这个负梯度被称为伪残差（Pseudo-residual）。 * 当损失函数是均方误差 \(L = \frac{1}{2}(y - F(x))^2\) 时，其负梯度恰好就是 \(y - F(x)\)，也就是我们直观理解中的“残差”。 * 当损失函数是其他函数（如用于分类的对数损失）时，负梯度就不再是简单的“真实值-预测值”，但其作为“修正方向”的意义是不变的。

    因此，GBDT 的每一轮迭代，都是在训练一棵树来拟合当前所有样本损失函数的负梯度。

3. 算法流程 (回归任务 + CART 树为例)⚓︎

假设训练集为 \(T = \{(x_1, y_1), ..., (x_N, y_N)\}\)，损失函数为均方误差 \(L(y, F(x)) = \frac{1}{2}(y - F(x))^2\)，迭代次数为 \(M\)，弱学习器为 CART 回归树。

  1. 初始化模型 用一个常数值来初始化模型，使得损失函数最小。对于均方误差，这个值就是所有样本 \(y\) 值的平均数。

    \[
F_0(x) = \bar{y} = \frac{1}{N}\sum_{i=1}^{N} y_i
\]

  2. 进行 M 轮迭代 对 \(m = 1, 2, ..., M\)：

    a. 计算伪残差（负梯度）：对每一个样本 \(i=1, ..., N\)，计算它在当前模型 \(F_{m-1}(x)\) 下的伪残差。

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

    b. 训练一棵回归树：将伪残差 \(r_{im}\) 作为新的目标值，将原始特征 \(x_i\) 作为输入，得到一个新的训练集 \(\{(x_i, r_{im})\}_{i=1}^N\)。使用这个新数据集训练一棵 CART 回归树 \(h_m(x)\)。这棵树会将输入空间划分为 \(J_m\) 个不相交的区域（叶子节点）\(R_{1m}, R_{2m}, ..., R_{J_m m}\)。

    c. 更新模型的叶子节点输出：对于每个叶子节点区域 \(R_{jm}\)，计算出该区域内使损失函数最小的最佳拟合值 \(\gamma_{jm}\) (也称作叶子节点的权重)。对于均方误差，这个值就是该区域内所有样本残差的平均值。

    \[
\gamma_{jm} = \arg\min_{\gamma} \sum_{x_i \in R_{jm}} L(y_i, F_{m-1}(x_i) + \gamma) \approx \text{mean}_{x_i \in R_{jm}}(r_{im})
\]

    d. 更新总模型：将新生成的树加入到总模型中，通常会乘以一个学习率（Learning Rate） \(\eta\) ，用于防止过拟合。

    \[
F_m(x) = F_{m-1}(x) + \eta \cdot h_m(x)
\]

    其中 \(h_m(x)\) 的输出是对应叶子节点的 \(\gamma_{jm}\) 值。

  3. 最终模型 经过 \(M\) 轮迭代，最终的强学习器就是所有树的加权（通过学习率）累加。

    \[
F_M(x) = F_0(x) + \eta \sum_{m=1}^{M} h_m(x)
\]

4. 算法复杂度⚓︎

  • 训练复杂度： 训练过程是 GBDT 最耗时的部分。其复杂度主要取决于迭代次数 \(M\) 和每轮迭代中决策树的构建成本。

    • 在每一轮迭代中，首先要计算所有 \(N\) 个样本的伪残差，复杂度为 \(O(N)\)。
    • 接下来是训练一棵决策树，这是最耗时的步骤。对于一棵深度为 \(D_{tree}\) 的树，使用 \(N\) 个样本和 \(d\) 个特征，构建成本近似为 \(O(N \cdot d \cdot D_{tree})\) 或 \(O(N \cdot d \cdot \text{num\_leaves})\)。更精确地，如果对每个特征的取值进行排序来寻找分裂点，复杂度会接近 \(O(N \log N \cdot d)\)。
    • 总的训练复杂度为： $$ \text{复杂度}{\text{train}} \approx O(M \cdot (N \cdot d \cdot D)) $$ 由于是串行过程，GBDT 的训练通常比较慢。

  • 推理复杂度： 与 AdaBoost 类似，GBDT 的推理过程很快。对于一个新样本 \(x\)：

    • 需要将它输入到 \(M\) 棵树中，分别得到预测值（叶子节点值）。
    • 每棵树的预测过程是沿树的路径从根走到叶，复杂度为 \(O(D_{tree})\)。
    • 将所有树的结果与学习率相乘并累加。
    • 总的推理复杂度为： $$ \text{复杂度}{\text{inference}} = O(M \cdot D) $$ 这个复杂度与训练样本数 \(N\) 和特征维度 \(d\) 无关，因此推理速度很快。

5. 优缺点总结⚓︎

优点: * 预测精度高：GBDT 在各类数据集上通常都能取得非常高的精度。 * 适用范围广：能处理回归、二分类、多分类等多种任务。 * 对异常值有一定鲁棒性：相较于 AdaBoost，如果使用一些对异常值不敏感的损失函数（如 Huber loss），GBDT 的鲁棒性更强。 * 可解释性强：可以输出特征重要性，便于理解模型决策。

缺点: * 训练过程串行，难以并行：同 AdaBoost 一样，后一棵树的训练依赖于前一棵树的结果，难以并行化，导致训练速度较慢。 * 参数众多，调参复杂：GBDT 的超参数较多（如学习率 learning_rate、树的数量 n_estimators、树的深度 max_depth、子采样比例 subsample 等），调参需要一定的经验。 * 容易过拟合：如果参数设置不当（如树的数量太多、深度太深），GBDT 也很容易过拟合。