机器学习算法
机器学习算法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) 构建基本分类器的线性组合:
得到最终分类器:
总结一下:
如何在每一轮改变训练数据的权值?提高那些被前一轮弱分类器错误分类样本的权值,而降低那些被正确分类样本的权值。这样一来,那些没有得到正确分类的数据,由于其权值的加大而受到后一轮的弱分类器的更大关注。
如何将弱分类器组合成强分类器?加大分类误差率小的弱分类器的权值,使其在表决中起较大的作用;减小分类误差率大的弱分类器的权值,使其在表决中起较小的作用。
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)$ 求极值,等价于:
右边恰好就是当前模型残差!也就是说,在平方误差损失下,提升树每一步只需要用一棵新的决策树去拟合当前模型的残差即可。
算法流程:
- 初始化 $f_0(x) = 0$
- 对 $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)$
- 输出 $\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 的核心优势
梯度提升树的设计使得提升方法具备了极强的泛化能力:
- 统一框架:通过”负梯度”这一桥梁,GBDT 将”拟合残差”的直观思想推广到了任意可微损失函数。
- 灵活选择损失函数:分类任务可以用对数损失(Log Loss),回归任务可以用 Huber 损失(对异常值鲁棒),排序任务可以用 Lambda 损失……
- 逐步纠错:每棵新树都在修正前一棵树的”错误”,类似于函数空间中的梯度下降。
8. 总结
正如我们在开头所说:蚂蚁众志成城,三个臭皮匠顶个诸葛亮。Boosting 告诉我们,即使每一个基本模型都只是”比随机猜测好一点”,只要我们有合适的机制将它们组合起来,就能创造出接近无限的强大能力。模型能 boosting,我们也能 (●’◡’●)!