跳到正文

站内搜索

机器学习算法

机器学习算法05-提升方法 (Boosting)

蚂蚁能够众志成城,齐心协力地将大昆虫尸体搬回蚁巢大快朵颐;做小组作业时,你是不是会用 “三个臭皮匠,顶个诸葛亮” 来安慰自己在ddl来临前干完不敢再看第二遍的报告?在学习算法里,科学家们也发现了若每个基础模型的学习力仅仅是+1,也可以使用权重+概率的魔法把它们组合到接近无限的能力!模型也能boosting,我们也可以(●’◡’●)!

本文从 Boosting 的理论根基出发,思维导图如下

1. 从”可学习”到”提升”:Boosting 的故事

1.1 什么是”可学习”?

在机器学习理论中,”可学习”是一个有被定义的概念。在概率近似正确(Probably Approximately Correct,PAC)学习的框架下,一个假设类 $\mathcal{H}$ 是 PAC 可学习的,意味着存在一个多项式组成的的学习算法,该算法在面对任意数据分布和任意标签函数时,只需要足够多的样本,就能以很高的概率学出任意高精度的分类器。

1.2 强可学习与弱可学习

历史上,Kearns 和 Valiant 在 PAC 框架中提出了两个重要概念:

  • 强可学习:一个概念,如果存在一个多项式的学习算法能够学习它,表现的正确率优异,那么就称这个概念是强可学习的。
  • 弱可学习:一个概念,如果存在一个多项式的学习算法能够学习它,学习的正确率仅比随机猜测略好一点,那么就称这个概念是弱可学习的。

举个例子:如果随机猜一枚硬币正反面,期望准确率是 50%。一个弱学习器只需要做到 55% 的准确率就算合格;而强学习器要求你做到 99% 甚至更高。

1.3 为什么追求弱可学习?

道理很简单——容易实现。正如参考资料中指出的那样:对于一些我们感兴趣的假设类,寻求对应的经验风险最小化(ERM)假设可能从计算上来说是不可行的。也就是说,我们想要一个”强学习器”。给定分布 $\mathcal{D}$ 以及目标标签函数 $f$,是否存在一种误差略优于随机猜测但可高效计算的学习算法?这就是弱学习器定义的出发点——通过大幅降低精度门槛,让本来在计算上不可行的问题变得可行。

1.4 提升-从弱到强

有意思的是,Schapire 后来证明强可学习与弱可学习是等价的 。也就是说,在 PAC 学习的框架下,强可学习的充分必要条件是这个概念也是弱可学习的。

这样一来,若在学习中,如果已经发现了弱学习算法,那么能否将它提升为强学习算法?

Boosting 正是完成这一途径的方法论。它可以将这些弱学习器们聚合得到近似最优的预测器,而这些预测器可以适用于复杂任务。AdaBoost 源自于能否由高效的弱学习器聚合为高效的强学习器这样一个问题。

2. AdaBoost 算法

2.1 AdaBoost 核心思想

AdaBoost(Adaptive Boosting)是最具代表性的提升算法。提升方法基于这样一种思想:对于一个复杂任务来说,将多个专家的判断进行适当的综合所得出的判断,要比其中任何一个专家单独的判断好。

对于分类问题而言,给定一个训练样本集,求比较粗糙的分类规则(弱分类器)要比求精确的分类规则(强分类器)容易得多。提升方法就是从弱学习算法出发,反复学习,得到一系列弱分类器(又称为基本分类器),然后组合这些弱分类器,构成一个强分类器。

2.2 AdaBoost 算法流程

AdaBoost 算法可以得到一个假设,而这个假设是一些基本假设的线性组合。也就是说,AdaBoost 依赖于假设类族,而这些假设类则是通过一些简单类的线性组合而得。

算法 8.1(AdaBoost):

输入:训练数据集为 $T = \{(x_1,y_1),(x_2,y_2),\dots,(x_N,y_N)\}$,其中 $x_i \in \mathcal{X} \subseteq \mathbf{R}^n$,$y_i \in \{-1,+1\}$;弱学习算法若干。

输出:最终分类器 $G(x)$。

1) 初始化训练数据的权值分布,均分

2) 对 $m = 1, 2, \dots, M$

  • 使用具有权值分布 $D_m$ 的训练数据集学习,得到基本分类器 $G_m(x): \mathcal{X} \to \{-1, +1\}$。
  • 计算 $G_m(x)$ 在训练数据集上的加权分类误差率:
  • 计算 $G_m(x)$ 的系数:
  • 更新训练数据集的权值分布:

其中 $Z_m$ 是规范化因子,使得 $D_{m+1}$ 作为概率可以归一化

3) 构建基本分类器的线性组合:

得到最终分类器:

总结一下:

  1. 如何在每一轮改变训练数据的权值?提高那些被前一轮弱分类器错误分类样本的权值,而降低那些被正确分类样本的权值。这样一来,那些没有得到正确分类的数据,由于其权值的加大而受到后一轮的弱分类器的更大关注。

  2. 如何将弱分类器组合成强分类器?加大分类误差率小的弱分类器的权值,使其在表决中起较大的作用;减小分类误差率大的弱分类器的权值,使其在表决中起较小的作用。

2.3 系数 $\alpha_m$ 推导

我在第一次学习这个概念时,最大的问题就是为什么系数 $\alpha_m$ 要取 $\frac{1}{2}\ln\frac{1-e_m}{e_m}$ 这个特定值。其实可以通过另一个角度思考这个问题。

AdaBoost 可以看为前向分步算法,且它实际上优化的损失函数是指数损失:

在第 $m$ 轮迭代时,前 $m-1$ 轮的模型 $f_{m-1}(x)$ 已经固定可以看为常数,现在要学习第 $m$ 个弱分类器 $G_m(x)$ 及其系数 $\alpha_m$。目标是最小化:

利用指数函数性质 $e^{a+b} = e^a \cdot e^b$ 展开,将 $m-1$ 轮是为常数设为 $w_{mi} = e^{-y_i f_{m-1}(x_i)}$,目标函数简化为:

由于 $y_i$ 和 $G(x_i)$ 都只取 $\{-1, +1\}$,按分类结果可以得出

  • 分类正确($y_i = G(x_i)$):出现 $e^{-\alpha}$,权重之和为 $1 - e_m$ (分类正确率)
  • 分类错误($y_i \neq G(x_i)$):出现 $e^{\alpha}$,权重之和为 $e_m$ (分类误差率)

目标函数变为:

对 $\alpha$ 求导并令导数为 0:

这就是 AdaBoost 系数公式的严格推导。取这个值能让指数损失函数下降最快,是贪心策略下的最优解。

3. AdaBoost 算法示例

下面李航老师书上的一个例题演示adaboost。

假设训练数据集如下,共有 10 个样本,$x$ 的取值为 0 到 9,标签 $y$ 如表所示:

序号 $i$ 1 2 3 4 5 6 7 8 9 10
$x_i$ 0 1 2 3 4 5 6 7 8 9
$y_i$ +1 +1 +1 -1 -1 -1 +1 +1 +1 -1

第 1 轮

初始化权值分布:$D_1$ 中每个样本权重为 $w_{1i} = 0.1$。

训练弱分类器:在加权分布 $D_1$ 下,选取一个阈值进行划分。假设以 $x=2.5$ 为阈值,$x \le 2.5$ 判为 $+1$,$x > 2.5$ 判为 $-1$。分类结果:

$x_i$ 0 1 2 3 4 5 6 7 8 9
$y_i$ +1 +1 +1 -1 -1 -1 +1 +1 +1 -1
$G_1(x_i)$ +1 +1 +1 -1 -1 -1 -1 -1 -1 -1
对错 ✓ ✓ ✓ ✓ ✓ ✓ ✗ ✗ ✗ ✓

被错误分类的样本是第 7、8、9 号,共 3 个。

计算加权误差率:

计算系数:

更新权值分布:

  • 正确分类的样本权重乘以 $e^{-\alpha_1} \approx 0.655$
  • 错误分类的样本权重乘以 $e^{\alpha_1} \approx 1.527$

更新后归一化,第 7、8、9 号样本的权重从 0.1 增加,其余样本的权重从 0.1 减小。这意味着下一轮弱分类器会更加关注第 7、8、9 号样本。

第 2 轮

在新的权值分布 $D_2$ 下训练弱分类器。由于第 7、8、9 号样本(标签为 $+1$)的权重变大,算法可能选择其他阈值来正确分类它们。以 $x=8.5$ 为阈值,$x \le 8.5$ 判为 $+1$,$x > 8.5$ 判为 $-1$。这样第 7、8、9 号样本被正确分类了,但第 3、4、5 号样本(标签为 $-1$)可能被误分。

按照同样的流程,计算新的 $e_2$、$\alpha_2$,并更新权值分布 $D_3$。

第 n 轮 …

重复以上过程,经过多轮迭代后,最终将所有弱分类器按各自的 $\alpha_m$ 加权求和:

最终分类器 $G(x)$ 在训练集上的准确率将会理论上高于任何单个弱分类器。

4. AdaBoost 训练误差下降速率

在之前的第 2.3 节中我就曾经提过,AdaBoost 可以看作隐式优化指数函数,为什么呢?通过对误差上界进行证明,可发现误差居然可以指数速率下降。

4.1 误差上界的推导

证明训练误差满足:

利用不等式进行放缩,若预测出错则 $y_i$, $f(x_i)$异号,有 $e^{-y_i f(x_i)}> 1$ :

将 $f(x) = \sum_{m=1}^M \alpha_m G_m(x)$ 代入:

利用指数函数性质 $e^{a+b} = e^a \cdot e^b$ 将连加拆为连乘:

由样本权重更新公式:

变形得:

代入后消去:

  • $Z_m$ 与 $i$ 无关,提到求和外面:$\prod_{m=1}^M Z_m$
  • 权重比值连乘 $\frac{w_{2,i}}{w_{1,i}} \cdot \frac{w_{3,i}}{w_{2,i}} \cdots \frac{w_{M+1,i}}{w_{M,i}} = \frac{w_{M+1,i}}{w_{1,i}}$

结合 $w_{1,i} = \frac{1}{N}$ 和 $\sum w_{M+1,i} = 1$:

得证

4.2 为什么误差会以指数级下降?

进一步分析 $Z_m$ 的值:

令 $e_m = \frac{1}{2} - \gamma_m$,满足弱可学习的定义,也就比随机猜测好那么一点:

利用泰勒展开推出的不等式 $\sqrt{1-x} \le e^{-x/2}$:

因此:

这意味着:只要每个弱分类器的误差率 $e_m < 0.5$(即 $\gamma_m > 0$),训练误差上界就会随迭代轮次 $M$ 的增加而以指数级速度下降.

4.3 思考 $Z_m$

$Z_m$ 表面上是权重更新公式中的归一化分母,确保更新后的权重之和为 1。但它实际上量化了当前这一步对降低总误差的贡献:

  • $Z_m \to 1$:分类器接近随机猜测,误差上界几乎不变。
  • $Z_m \to 0$:分类器非常好,误差上界被大幅压低。

AdaBoost 在每一轮自动选择让 $Z_m$ 最小的 $\alpha_m$,从而让误差下降最快。

5. AdaBoost 的另一种视角:前向分步加法模型

5.1 什么是前向分步算法?

AdaBoost 另一种理解是模型是加法模型、损失函数是指数函数、学习算法是前向分步算法时的学习方法 。

考虑一般的加法模型:

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

如果直接联合优化所有 $\beta_m$ 和 $\gamma_m$,问题会非常复杂。前向分步算法采用贪心策略:从前向后,每一步只学习一个基函数及其系数,逐步逼近优化目标。

在第 $m$ 步,假设已经学了前 $m-1$ 个基函数,固定 $f_{m-1}(x)$,只优化:

5.2 前向分步算法与 AdaBoost 的等价性证明

要证明 AdaBoost 正是前向分步算法在指数损失函数下的具体实现,只需证明在指数损失 $Loss(y, f) = e^{-y \cdot f(x)}$ 下,前向分步算法推导出的 $\alpha_m$ 和权重更新公式与 AdaBoost 完全一致。

第 $m$ 步的目标函数:

令 $w_{mi}^{‘} = \exp(-y_i f_{m-1}(x_i))$,目标函数化简为:

注意,归一化后的 $w_{mi} = w_{mi}^{‘} / \sum_j w_{mj}^{‘}$ 恰好就是 AdaBoost 第 $m$ 轮的样本权值分布。

按分类正误分组,设加权误差率为 $e_m$:

对 $\alpha$ 求导令其为零,解得:

将最优 $\alpha_m$ 代回,更新后的样本权重:

归一化后即:

这完全就是 AdaBoost 的算法!

6. 提升树(Boosting Tree)

6.1 从分类到回归:以决策树为基学习器

前面介绍的 AdaBoost 主要针对分类问题,基学习器通常是简单的”决策桩”(decision stump)。提升方法更具体、更强大的实例是提升树(Boosting Tree)——以决策树为基本学习器的提升方法。提升树算法由 Friedman 等人于 2000 年提出,同样采用加法模型与前向分步算法,但将基函数替换为决策树:

其中 $T(x; \Theta_m)$ 表示第 $m$ 棵决策树,$\Theta_m$ 是该树的结构与参数。

6.2 残差拟合的学习方法

针对不同问题,提升树的主要区别在于使用的损失函数不同。对于回归问题,若采用平方:

数学推导变得非常简单。在第 $m$ 步,前向分步算法的目标是:

对 $T(x)$ 求极值,等价于:

右边恰好就是当前模型残差!也就是说,在平方误差损失下,提升树每一步只需要用一棵新的决策树去拟合当前模型的残差即可。

算法流程:

  1. 初始化 $f_0(x) = 0$
  2. 对 $m = 1, 2, \dots, M$:
    • 计算残差 $r_{mi} = y_i - f_{m-1}(x_i)$
    • 拟合一棵回归树 $T_m(x)$ 到残差 $\{(x_i, r_{mi})\}$
    • 更新模型 $f_m(x) = f_{m-1}(x) + T_m(x)$
  3. 输出 $\hat{f}(x) = f_M(x)$

这个算法非常直观:第一棵树拟合原始数据,第二棵树拟合第一棵树的残差(即第一棵树没学好的部分),第三棵树拟合前两棵树的残差……层层递进,每棵树都在”纠正”前面所有树犯的错误。

7. 梯度提升树(GBDT)

7.1 从残差到负梯度

残差拟合的方法虽然直观优雅,但它有一个致命的局限——仅适用于平方误差损失函数。当损失函数变为一般函数(如绝对值损失、Huber 损失、对数损失等)时,直接求解最优树并不像平方损失那样简单。

针对这一问题,Friedman 提出了梯度提升(Gradient Boosting)算法 [13]。其核心思想是:借鉴数值优化中的最速下降法,用损失函数的负梯度来作为残差的近似值。

7.2 负梯度的计算

在最优化理论中,对于目标函数 $L(y, f(x))$,如果我们想让 $L$ 最小化,可以沿着负梯度方向更新:

在函数空间中,损失函数关于当前模型输出 $f_{m-1}(x_i)$ 的梯度为:

因此,假的类似的残差定义为负梯度:

7.3 梯度提升树算法流程

输入:训练数据集 $\{(x_i, y_i)\}_{i=1}^N$,可微损失函数 $L(y, f)$

步骤 1:初始化

(仅含根结点的常数树,输出值使损失最小)

步骤 2:对 $m = 1, 2, \dots, M$:

(a) 计算每个样本的负梯度(伪残差):

(b) 对伪残差 $\{(x_i, r_{mi})\}$ 拟合一棵回归树 $T_m$,得到 $J$ 个叶结点区域 $R_{m1}, R_{m2}, \dots, R_{mJ}$。

(c) 对每个叶结点区域,利用线性搜索计算最优输出值 $c_{mj}$:

(d) 更新模型:

步骤 3:输出最终模型 $\hat{f}(x) = f_M(x)$。

7.4 GBDT 的核心优势

梯度提升树的设计使得提升方法具备了极强的泛化能力:

  1. 统一框架:通过”负梯度”这一桥梁,GBDT 将”拟合残差”的直观思想推广到了任意可微损失函数。
  2. 灵活选择损失函数:分类任务可以用对数损失(Log Loss),回归任务可以用 Huber 损失(对异常值鲁棒),排序任务可以用 Lambda 损失……
  3. 逐步纠错:每棵新树都在修正前一棵树的”错误”,类似于函数空间中的梯度下降。

8. 总结

正如我们在开头所说:蚂蚁众志成城,三个臭皮匠顶个诸葛亮。Boosting 告诉我们,即使每一个基本模型都只是”比随机猜测好一点”,只要我们有合适的机制将它们组合起来,就能创造出接近无限的强大能力。模型能 boosting,我们也能 (●’◡’●)!