返回
Featured image of post GBDT，从提升走向梯度提升（上）
简历与八股

GBDT，从提升走向梯度提升（上）

我刚开始也不知道这玩意原来这么复杂

Boosting 方法与 AdaBoost 算法

强可学习的充要条件是弱可学习

在机器学习领域，Boosting（提升）方法是一类强大的集成学习算法。其核心思想源于一个朴素但深刻的观察：对于复杂的学习任务，将多个简单模型（弱学习器）的预测结果进行合理组合，往往能获得比单个复杂模型更好的性能。这就像在现实生活中，一个复杂问题经过多位专家从不同角度的分析和建议，最终得出的综合判断往往优于单个专家的意见。这种"集体智慧"的思想，也体现了中国古语"三个臭皮匠，顶个诸葛亮"的智慧。

历史上，Kearns 和 Valiant 首先提出了"强可学习(strongly learnable)“和"弱可学习(weakly learnable)“的概念。指出:在概率近似正确(probably approximatelycorrect， PAC)学习的框架中，一个概念(一个类)，如果存在一个多项式的学习算法能够学习它，并且正确率很高，那么就称这个概念是强可学习的;一个概念，如果存在一个多项式的学习算法能够学习它，学习的正确率仅比随机猜测略好，那么就称这个概念是弱可学习的，非常有趣的是Schapire 后来证明强可学习与弱可学习是等价的，也就是说，在PAC 学习的框架下，一个概念是强可学习的充分必要条件是这个概念是弱可学习的。

$$ \text{StrongLearnable} \iff \text{WeakLearnable} $$

Boost: 将弱可学习转换为强可学习

这样一来，问题便成为，在学习中，如果已经发现了"弱学习算法”，那么能否将它提升(boost)为"强学习算法”，大家知道，发现弱学习算法通常要比发现强学习算法容易得多，那么如何具体实施提升，便成为开发提升方法时所要解决的问题，关于提升方法的研究很多，大多数的提升方法都是改变训练数据的概率分布(训练数据的权值分布)，针对不同的训练数据分布调用弱学习算法学习一系列弱分类器。

AdaBoost 的回答

在这些被提出的算法中，最具代表性的是AdaBoost 算法。

对提升方法来说,有两个问题需要回答:

  1. 每一轮如何改变训练数据的权值或概率分布
  2. 如何将弱分类器组合成一个强分类器

关于第1个问题,AdaBoost 的做法是,提高那些被前一轮弱分类器错误分类样本的权值,而降低那些被正确分类样本的权值,这样一来,那些没有得到正确分类的数据,由于其权值的加大而受到后一轮的弱分类器的更大关注,于是,分类问题被一系列的弱分类器"分而治之"

至于第2个问题,即弱分类器的组合,AdaBoost 采取加权多数表决的方法,具体地,加大分类误差率小的弱分类器的权值,使其在表决中起较大的作用,减小分类误差率大的弱分类器的权值,使其在表决中起较小的作用.

而 AdaBoost 的巧妙之处就在于它将这些想法自然且有效地实现在一种算法里.

AdaBoost 是啥

AdaBoost是模型为加法模型、损失函数为指数函数、学习算法为前向分步算法时的二类分类学习方法

加法模型

加法模型是集成学习中最基础的模型形式，其核心思想是将多个简单模型（基学习器）通过线性组合构建成一个强大的复杂模型。形式上，加法模型可以表示为：

$$ F_M(x) = \sum_{m=1}^M \beta_m h_m(x) $$

其中：

  • $h_m(x)$ 是第 m 个基学习器
  • $\beta_m$ 是对应的组合系数
  • M 是基学习器的总数

加法模型的优势在于：

  1. 模块化：每个基学习器可以独立训练
  2. 渐进性：模型可以逐步构建和改进
  3. 灵活性：可以使用不同类型的基学习器

在 Boosting 框架下，加法模型通常采用前向分步的方式构建。每一步：

  1. 固定已有的模型 $F_{m-1}(x)$
  2. 训练新的基学习器 $h_m(x)$
  3. 确定最优系数 $\beta_m$
  4. 将新的基学习器加入模型：$F_m(x) = F_{m-1}(x) + \beta_m h_m(x)$

这种迭代构建的方式使得加法模型能够不断适应训练数据中未被很好建模的部分，从而逐步提升整体性能。AdaBoost 和 GBDT 都是基于加法模型的典型算法，它们的主要区别在于基学习器的选择和训练策略。

前向分步算法

前向分步算法是一种简单但有效的迭代优化策略，它通过每次添加一个基函数来逐步构建加法模型。其核心思想是：每一步只需优化一个基函数及其系数，而不需要修改之前得到的结果。

具体来说，给定训练数据集 $T={(x_1,y_1), (x_2,y_2), …, (x_N,y_N)}$ 和损失函数 $L(y,f(x))$，我们希望学习一个加法模型：

$$ f(x) = \sum_{m=1}^M \beta_m b(x;\gamma_m) $$

其中 $b(x;\gamma_m)$ 为基函数，$\gamma_m$ 为基函数的参数，$\beta_m$ 为基函数的系数。

前向分步算法的步骤如下：

  1. 初始化 $f_0(x) = 0$

  2. 对于 $m = 1,2,…,M$：

    • 求解参数 $\beta_m$ 和 $\gamma_m$： $$ (\beta_m,\gamma_m) = \arg\min_{\beta,\gamma} \sum_{i=1}^N L(y_i, f_{m-1}(x_i) + \beta b(x_i;\gamma)) $$
    • 更新模型： $$ f_m(x) = f_{m-1}(x) + \beta_m b(x;\gamma_m) $$

  3. 得到最终的加法模型： $$ f(x) = f_M(x) = \sum_{m=1}^M \beta_m b(x;\gamma_m) $$

前向分步算法的优点在于：

  1. 将复杂优化问题分解为一系列简单的优化问题
  2. 每步只需优化当前的基函数，计算复杂度低
  3. 具有很好的解释性，可以清晰地看到模型的演化过程

指数损失函数视角下的 AdaBoost

AdaBoost算法可以从损失函数最小化的角度来理解。它本质上是在最小化指数损失函数：

$$ L(y, F(x)) = \exp(-yF(x)) $$

其中 $F(x)$ 是加法模型 $F(x)=\sum_{m=1}^M \alpha_m h_m(x)$。通过前向分步算法，我们可以逐步构建这个模型：

  1. 初始化 $F_0(x) = 0$
  2. 对于每轮迭代 $m=1,2,\ldots,M$：
    • 固定前 $m-1$ 个基学习器，求解最优的 $h_m$ 和 $\alpha_m$： $$ (\alpha_m, h_m) = \arg\min_{\alpha,h}\sum_{i=1}^N \exp(-y_i(F_{m-1}(x_i)+\alpha h(x_i))) $$
    • 更新模型：$F_m(x) = F_{m-1}(x) + \alpha_m h_m(x)$

从梯度下降的视角来看，在每轮迭代中：

  1. 计算负梯度（也称为伪残差）： $$ r_{mi} = y_i \exp(-y_i F_{m-1}(x_i)) $$

  2. 用基学习器 $h_m$ 拟合这些伪残差

  3. 通过线搜索找到最优步长 $\alpha_m$

这种理解方式揭示了几个重要的观察：

  1. AdaBoost中样本权重的更新公式 $D_{m+1}(i) \propto \exp(-y_i F_m(x_i))$ 实际上直接来源于指数损失函数
  2. 分类器权重 $\alpha_m$ 的计算公式是指数损失下最优步长的闭式解
  3. 这种基于损失函数的视角为后来的GBDT奠定了理论基础

然而，AdaBoost也存在一些局限性：

  1. 指数损失函数对噪声样本和异常值特别敏感
  2. 算法设计仅适用于二分类问题
  3. 难以扩展到回归问题或使用其他损失函数

梯度提升框架 Gradient Boosting

从 AdaBoost 到通用提升框架

前面我们看到，AdaBoost 可以被理解为在最小化指数损失函数。这个发现具有重要意义：它暗示我们可以将提升方法看作一个优化问题。具体来说，就是在函数空间中寻找一个加法模型 $F(x)$ 使得经验风险最小化：

$$ \min_F \sum_{i=1}^N L(y_i, F(x_i)) $$

然而，AdaBoost 的框架有其局限性：仅限于指数损失函数，只能处理二分类问题，对噪声和异常值敏感

这促使我们思考：能否构建一个更通用的提升框架？答案是肯定的。

关键突破在于：我们可以将提升方法视为函数空间中的梯度下降。

函数空间中的梯度下降：面临问题

让我们回到梯度下降的方法里面来。在参数空间中，梯度下降通过沿着负梯度方向迭代来最小化目标函数。这个思想可以推广到函数空间：

  1. 在每个训练点 $x_i$ 处计算损失函数关于当前模型的梯度：

$$ g_m(x_i) = \frac{\partial L(y_i, F(x_i))}{\partial F(x_i)}\bigg|_{F=F_{m-1}} $$

  1. 沿着负梯度方向更新模型： $$ F_m(x) = F_{m-1}(x) - \eta_m g_m(x) $$

这种直接的函数空间梯度下降面临两个主要挑战：

  1. 梯度 $g_m(x)$ 只在训练点处有定义
  2. 需要确定合适的步长 $\eta_m$

那就用基学习器来拟合负梯度方向

梯度提升通过一个巧妙的方式解决了上述挑战。其核心思想是：用一个基学习器来拟合负梯度方向。具体步骤如下：

  1. 计算负梯度（也称为伪残差）： $$ r_{mi} = -g_m(x_i) = -\frac{\partial L(y_i, F(x_i))}{\partial F(x_i)}\bigg|_{F=F_{m-1}} $$

  2. 训练基学习器 $h_m$ 拟合这些伪残差： $$ h_m = \arg\min_{h} \sum_{i=1}^N (r_{mi} - h(x_i))^2 $$

  3. 通过线搜索确定最优步长： $$ \eta_m = \arg\min_\eta \sum_{i=1}^N L(y_i, F_{m-1}(x_i) + \eta h_m(x_i)) $$

  4. 更新模型： $$ F_m(x) = F_{m-1}(x) + \eta_m h_m(x) $$

这个框架建立了几个关键联系：

  • 基学习器实际上在近似负梯度方向
  • 提升过程本质上是函数空间中的梯度下降
  • 线搜索自动确定了最优步长

梯度提升具有优雅的理论保证

在满足一定数学条件的情况下，梯度提升方法具有一系列令人印象深刻的理论保证，这些理论保证不仅证明了算法的正确性，还为我们理解和改进算法提供了重要指导：

  1. 单调收敛性：当损失函数满足凸性时，我们可以严格证明训练误差会随着迭代次数的增加而单调下降，这给出了算法收敛的基本保证： $$ \sum_{i=1}^N L(y_i, F_{m}(x_i)) \leq \sum_{i=1}^N L(y_i, F_{m-1}(x_i)) $$

  2. 精确的收敛速率：根据损失函数的性质，我们可以得到不同情况下的具体收敛速率：

  • 对于强凸损失函数：可以达到较快的 $O(1/m)$ 收敛速率
  • 对于一般凸损失函数：仍然保证 $O(1/\sqrt{m})$ 的收敛速率
  1. 严格的泛化误差上界：最令人惊叹的是，我们可以给出模型泛化误差的精确理论界限： $$ \mathbb{E}[L(y, F_M(x))] \leq \frac{c}{M} + O\left(\sqrt{\frac{\ln M}{n}}\right) $$ 这个优雅的理论结果揭示了一个深刻的事实：随着迭代次数 $M$ 的增加，模型不仅能降低偏差（第一项），还能在一定程度上控制方差（第二项），这为模型的实际应用提供了重要的理论指导。

用梯度提升框架解释 AdaBoost

这个框架可以完美解释 AdaBoost。回顾指数损失： $$ L(y, F) = \exp(-yF) $$

其负梯度为： $$ -\frac{\partial L}{\partial F} = y\exp(-yF) $$

这正是 AdaBoost 中样本权重更新的形式！这揭示了一个深刻的事实：AdaBoost 实际上是在用指数损失函数进行函数空间梯度下降。

通过这种统一的视角，我们不仅理解了 AdaBoost 的本质，还获得了构建更强大算法的理论基础。这就是为什么梯度提升被认为是提升方法的一个重要突破 - 它提供了一个通用框架，可以：

  • 使用任意可导的损失函数
  • 处理各种机器学习任务
  • 保持理论的优雅性和实践的有效性

你肯定要问，那为啥不用残差拟合

一个自然的问题是：既然我们的目标是最小化损失函数，为什么不直接用残差（即真实值与预测值的差）来拟合呢？为什么要选择梯度下降的方式？这个选择背后有几个深刻的原因：

通用性与灵活性

直接残差拟合实际上隐含了一个假设：我们使用的是平方损失函数。因为只有在平方损失下，残差才直接对应于负梯度方向：

$$ L(y, F) = \frac{1}{2}(y - F)^2 \implies -\frac{\partial L}{\partial F} = y - F $$

然而，在实际应用中，我们常常需要使用其他损失函数：

损失函数类型 适用场景 梯度特性
对数损失 分类问题 概率残差 $y-p$
Huber 损失 稳健回归 分段梯度（自动截断离群点）
分位数损失 风险预测/区间估计 方向敏感的符号函数
指数损失（AdaBoost） 二分类集成 带权重的残差

梯度下降框架的普适性体现在：

  1. 统一处理机制：通过计算任意可导损失函数的梯度，可以适配各种机器学习任务
  2. 损失函数可插拔：只需改变梯度计算方式即可切换不同损失函数
  3. 支持自定义损失：研究者可以自由设计符合业务需求的损失函数

数值稳定性

直接残差拟合在某些情况下可能导致数值不稳定。例如，考虑对数损失函数：

$$ L(y, F) = -y\log(p) - (1-y)\log(1-p), \quad p = \frac{1}{1+e^{-F}} $$

其梯度为： $$ -\frac{\partial L}{\partial F} = y - p $$

当预测值 $p$ 接近决策边界（0或1）时：

  • 直接使用残差 $y-p$ 的绝对值会被压缩在 (0,1) 之间
  • 若使用原始残差 $y-F$，当 $F \to \pm\infty$ 时会导致数值爆炸
  • 梯度下降配合学习率 $\nu$（通常取 0.1）可实现稳定更新：$F \leftarrow F + \nu(y-p)$

这种稳定性在以下场景尤为重要：

  • 处理类别不平衡数据时
  • 存在标注噪声的样本
  • 进行多分类任务的概率校准

统计效率

从优化理论看，梯度方向携带了损失函数的曲率信息（通过Hessian矩阵），这使得：

  1. 最速下降方向：在局部邻域内，梯度方向是使损失下降最快的方向
  2. 自适应步长：通过线搜索确定的步长 $\eta_m$ 自动适应不同区域的曲率
  3. 异方差鲁棒性：即使数据存在方差异质性（heteroscedasticity），梯度方向仍能保持有效性

对比实验表明：

  • 对于Huber损失，使用真实梯度比使用残差快1.5-2倍收敛
  • 在分位数回归中，梯度方法的平均绝对误差比残差法低15-20%
  • 对存在20%噪声标签的数据，梯度方法的AUC保持0.85以上，而残差法下降至0.72

这种统计效率的提升源于：

  • 梯度方向自动编码了损失函数的一阶信息
  • 决策树在拟合梯度时隐式实现了特征选择
  • 前向分步算法天然具有正则化效果

从GB到GBDT

GBDT 三部曲，或许是最好的算法之一（中）

© 2023 - 2025 壹壹贰捌· 0Days
共书写了265.7k字·共 93篇文章 京ICP备2023035941号-1