🎯 02-机器学习 · 推导笔记 9:AdaBoost(手写全流程)¶
AdaBoost(Adaptive Boosting,自适应提升)是第一个实用的大规模 boosting 算法,也是理解 GBDT 的必经之路: “把一堆只比瞎猜好一点的弱分类器,组合成一个强分类器”。
💡 一句话类比:三个臭皮匠顶个诸葛亮。每次新请一个“专家”,专挑前一批专家集体犯错的样本下功夫;最后每个专家按水平(权重)投票,水平越高票越重。
💡 更形象的版本:一个班轮流讲错题——第 1 轮大家平均练;第 2 轮重点练第 1 轮做错的题;第 3 轮再重点练前两轮都错得多的题。练完每个人把自己最有把握的题拿出来投票。
运行环境:Python 3.8+,仅依赖 numpy(对照 cell 需要 sklearn)。
核心概念¶
(a) 🗂️ AdaBoost:指数损失、前向分步加法模型与样本权重更新¶
AdaBoost 是第一个实用的大规模 boosting 算法:"三个臭皮匠顶个诸葛亮",把只比瞎猜好一点的弱分类器组合成强分类器。本篇从指数损失推出全部公式。
flowchart TB
N1["🎯 集成学习三兄弟"] --> N2["AdaBoost 直觉与算法流程"]
N2 --> N3["前向分步 + 指数损失"]
N3 --> N4["弱分类器权重 α:推导"]
N3 --> N5["样本权重更新 D:推导"]
N4 --> N6["训练误差上界"]
N5 --> N7["为什么不容易过拟合"]
N6 --> N8["AdaBoost vs GBDT"]
N8 --> N9["自测清单"]
- N1 · 集成学习三兄弟:Bagging 并行训练互相独立(随机森林)、Boosting 串行训练逐个纠错(AdaBoost/GBDT)、Stacking 用元模型融合多个模型输出——先建好这个框架。
- N2 · AdaBoost 直觉:每轮训练一个弱分类器,专门"喂"给它上一轮被分错的样本(加大它们的权重);最后按各自的表现加权投票。三句话讲清流程。
- N3 · 前向分步 + 指数损失:为什么这样设计能行?数学上它等价于"前向分步加法模型 + 指数损失":每轮只优化一个弱分类器和它的权重,目标是把指数损失最小化。
- N4 · 弱分类器权重 α:对指数损失求导令其为 0,得到 α = ½ln((1−ε)/ε):错误率 ε 越小,这个分类器的话语权越大。
- N5 · 样本权重更新 D:正确样本权重乘 e⁻ᵅ(变小)、错误样本乘 eᵅ(变大),再归一化——这正是"下一轮重点照顾错题"的数学形式。
- N6 · 训练误差上界:指数损失总和 ≤ 每轮错误率平方根连乘,只要每轮错误率 < 0.5,误差就指数级下降——从数学上保证"不比你瞎猜差"。
- N7 · 为什么不容易过拟合:它专注把"边界样本"分清,模型的间隔(margin)会变大,泛化性好;但样本噪声很大时也会被放大,这是它的代价。
- N8 · AdaBoost vs GBDT:AdaBoost 每轮改样本权重、用指数损失(对噪声敏感);GBDT 每轮拟合负梯度(伪残差)、损失可换、更稳健——面试必背对比。
- N9 · 自测清单:能手推 α 和 D 的更新公式、能画出算法流程、能回答"AdaBoost 为什么不轻易过拟合"。
📖 本章导读¶
这一章讲什么(全书第 7 章):三个臭皮匠——加法模型 + 指数损失。一切结论(权重 $\alpha$、样本权重更新 $D$、误差上界)都从指数损失的两个求导推出。
学完本章,你应该能:
- 从指数损失推出 $\alpha_m=\frac12\ln\frac{1-e_m}{e_m}$(对 $\alpha$ 求导);
- 推出样本权重更新 $D_{m+1}(i)\propto D_m(i)e^{-\alpha_m y_i G_m(x_i)}$(错题权重放大);
- 解释训练误差上界 $\prod_m 2\sqrt{e_m(1-e_m)}$ 为什么指数衰减;
- 对比 AdaBoost(重数据)与 GBDT(重残差),说清 AdaBoost 怕噪声。
📌 全书第 7 章。阅读路径:本章导读 → 指数损失 · 权重推导 · 上界 → 自测清单 → 本章小结。
§1 集成学习三兄弟(先建框架)¶
| 方法 | 核心思想 | 并行/串行 | 主要降低 | 代表 |
|---|---|---|---|---|
| Bagging | 自助采样多份数据,各自训练,投票/平均 | 并行 | 方差 | 随机森林 |
| Boosting | 串行训练,每轮重点学前一轮的错误 | 串行 | 偏差 | AdaBoost、GBDT |
| Stacking | 用第一层模型的输出当第二层模型的输入 | 并行+串行 | 偏差+方差 | 各种冠军方案 |
为什么 Bagging 降方差、Boosting 降偏差:
- Bagging:多个独立模型平均 → 方差除以约 $B$(独立假设下),偏差不变;
- Boosting:每轮拟合残差/难样本 → 一步步把偏差压小,但可能放大方差(所以树深要浅)。
📊 图 3:AdaBoost 流程——带权重数据 → 一串“专攻难题”的树桩 h₁…hₘ → 加权投票得强分类器 F(x)。
§2 AdaBoost 直觉与算法流程¶
训练集 $(x_1, y_1), \dots, (x_n, y_n)$,$y_i \in \{-1, +1\}$。每个样本带一个权重 $D_m(i)$(第 $m$ 轮),初始均匀 $D_1(i) = 1/n$。
每一轮 $m = 1, \dots, M$:
- 在带权数据上训练弱分类器 $G_m(x)$(如决策树桩)——目标是加权错误率最小:
$$e_m = \sum_{i: G_m(x_i) \neq y_i} D_m(i)$$
- 算该分类器的发言权(错误率越低,权重越大):
$$\alpha_m = \frac{1}{2} \ln \frac{1 - e_m}{e_m}$$
- 更新样本权重:被分错的样本权重放大,分对的缩小:
$$D_{m+1}(i) = \frac{D_m(i) \, e^{-\alpha_m y_i G_m(x_i)}}{Z_m}, \qquad Z_m = \sum_i D_m(i) e^{-\alpha_m y_i G_m(x_i)}$$
分对时 $y_i G_m(x_i) = +1 \Rightarrow$ 乘 $e^{-\alpha_m} < 1$(权重变小);分错时乘 $e^{+\alpha_m} > 1$(权重变大)。
- 加权投票得到最终分类器:
$$F(x) = \sum_{m=1}^{M} \alpha_m G_m(x), \qquad G(x) = \operatorname{sign}\big(F(x)\big)$$
💡 直观理解:错误率 $e_m$ 越接近 0,$\alpha_m$ 越大(专家越牛,话语权越大);若 $e_m > 0.5$ 就反着用(把 $G_m$ 取反,错误率变 $1-e_m$)。
✍️ §2.1 手算 AdaBoost 两轮:错题权重如何"越练越重"¶
公式 $\alpha=\tfrac12\ln\frac{1-e}{e}$ 与 $D$ 更新,用李航《统计学习方法》例 8.1 的 10 个一维样本跑两轮。
设定:$x=0,1,\dots,9$;标签 $y=[1,1,1,-1,-1,-1,1,1,1,-1]$;初始权重 $D_1(i)=0.1$(10 个样本均匀)。
第 1 轮:选阈值 2.5 的树桩 $G_1$($x\le2.5\Rightarrow+1$,否则 $-1$)
$x=6,7,8$ 三个样本被分错($y=+1$ 却被判 $-1$),加权错误率:
$$e_1 = D_1(6)+D_1(7)+D_1(8) = 3\times0.1 = 0.3$$
$$\alpha_1 = \tfrac12\ln\frac{1-e_1}{e_1} = \tfrac12\ln\frac{0.7}{0.3} = \tfrac12\ln2.333 = 0.4236$$
更新样本权重(分错乘 $e^{\alpha}=e^{0.4236}=1.5276$,分对乘 $e^{-\alpha}=0.6547$):
$$D_2(i) \propto D_1(i)\,e^{-\alpha_1 y_i G_1(x_i)},\qquad Z_1 = 7\times0.0655+3\times0.1528=0.9165$$
$$D_2 = \frac{[0.0655\times7,\ 0.1528\times3]}{0.9165} = [0.0714\times7,\ 0.1667\times3]$$
被分错的 3 个样本权重从 0.1 涨到 0.1667,分对的从 0.1 降到 0.0714——下一轮分类器被迫优先照顾它们。
第 2 轮:在 $D_2$ 上选最优阈值 8.5 的树桩 $G_2$($x\le8.5\Rightarrow+1$)
这次 $x=3,4,5$ 被分错,加权错误率:
$$e_2 = 3\times D_2(3) = 3\times0.0714 = 0.2143\Rightarrow \alpha_2 = \tfrac12\ln\frac{0.7857}{0.2143} = 0.6496$$
第 3 轮收尾(书中示例):阈值 5.5 反着用($x\le5.5\Rightarrow-1$),$e_3=0.1818$、$\alpha_3=0.7520$,组合后:
$$G(x)=\operatorname{sign}\big(0.4236\,G_1 + 0.6496\,G_2 + 0.7520\,G_3\big)$$
10 个样本全部分类正确。注意 $\alpha$ 一轮比一轮大——每轮"专家"越来越有把握。
手算收获:
- $e<0.5\Rightarrow\alpha>0$:只比瞎猜好一点(0.3)的分类器也有正话语权;$e\to0$ 时 $\alpha\to\infty$
- 权重更新的本质:分错样本权重乘 $>1$、分对乘 $<1$,再归一化——"越练越重"就是数值事实
- 第二轮最优阈值从 2.5 挪到 8.5:因为第一轮留下的难样本(6,7,8)在左侧,第二轮去补右侧(3,4,5)
下面 numpy 复算。
# ---- §2.1 验证:numpy 复算 AdaBoost(李航例 8.1)----
import numpy as np
x = np.arange(10, dtype=float)
y = np.array([1, 1, 1, -1, -1, -1, 1, 1, 1, -1], dtype=float)
D = np.full(10, 0.1)
def stump(v, flip=False):
G = np.where(x <= v, 1.0, -1.0)
return -G if flip else G
# 第 1 轮
G1 = stump(2.5)
e1 = D[G1 != y].sum()
a1 = 0.5 * np.log((1 - e1) / e1)
D = D * np.exp(-a1 * y * G1); Z1 = D.sum(); D /= Z1
print(f'第1轮: e1={e1:.4f} α1={a1:.4f} Z1={Z1:.4f}')
print(' D2 =', np.round(D, 4))
# 第 2 轮(搜最优阈值)
G2 = stump(8.5)
e2 = D[G2 != y].sum()
a2 = 0.5 * np.log((1 - e2) / e2)
D = D * np.exp(-a2 * y * G2); Z2 = D.sum(); D /= Z2
print(f'第2轮: e2={e2:.4f} α2={a2:.4f}')
print(' D3 =', np.round(D, 4))
# 第 3 轮
G3 = stump(5.5, flip=True)
e3 = D[G3 != y].sum()
a3 = 0.5 * np.log((1 - e3) / e3)
print(f'第3轮: e3={e3:.4f} α3={a3:.4f}')
F = a1 * G1 + a2 * G2 + a3 * G3
pred = np.sign(F).astype(int)
print('\n组合预测 =', pred, '\n真实标签 =', y.astype(int))
print('全部正确:', np.all(pred == y.astype(int)))
assert abs(e1 - 0.3) < 1e-9 and abs(a1 - 0.4236) < 1e-3
assert abs(e2 - 0.2143) < 1e-3 and abs(a2 - 0.6496) < 1e-3
assert np.all(pred == y.astype(int))
print('✓ 与手算一致')
§3 从“前向分步加法模型 + 指数损失”推出 AdaBoost(面试核心)¶
AdaBoost 不是拍脑袋想出来的,它是加法模型 + 指数损失 + 前向分步优化的必然结果。
加法模型:
$$F_M(x) = \sum_{m=1}^{M} \alpha_m G_m(x)$$
指数损失:
$$L(y, f(x)) = e^{-y f(x)}$$
(分对 $yf(x)>0 \Rightarrow$ 损失 < 1;分错 $\Rightarrow$ 损失 > 1,错得越离谱惩罚越大。)
前向分步:第 $m$ 步固定前 $m-1$ 个分类器,只优化新加的第 $m$ 个:
$$(\alpha_m, G_m) = \arg\min_{\alpha, G} \sum_{i=1}^{n} e^{-y_i \left( F_{m-1}(x_i) + \alpha G(x_i) \right)}$$
令 $w_i^{(m)} = e^{-y_i F_{m-1}(x_i)}$(与 $\alpha, G$ 无关的常数),目标变为:
$$\sum_i w_i^{(m)} e^{-\alpha y_i G(x_i)} = e^{-\alpha} \sum_{y_i = G(x_i)} w_i^{(m)} + e^{\alpha} \sum_{y_i \neq G(x_i)} w_i^{(m)}$$
先优化 $G_m$(与 $\alpha$ 无关的部分):最小化第二项 $\sum_{y_i \neq G(x_i)} w_i^{(m)}$,即在权重 $w^{(m)}$ 下最小化加权错误率——这正是算法第 1 步,且 $w^{(m)} \propto D_m$(归一化后即样本权重)。
再优化 $\alpha_m$:对 $\alpha$ 求导置零,得
$$\alpha_m = \frac{1}{2} \ln \frac{1 - e_m}{e_m}, \qquad e_m = \sum_{y_i \neq G_m(x_i)} w_i^{(m)}$$
权重更新:因为 $w_i^{(m+1)} = e^{-y_i F_m(x_i)} = w_i^{(m)} \cdot e^{-\alpha_m y_i G_m(x_i)}$,除以归一化常数 $Z_m$ 即得算法第 3 步。
✅ 结论:AdaBoost = 前向分步加法模型 + 指数损失。这一个推导解释了全部三个更新公式,面试背这一条链路即可。
# ---- matplotlib 中文字体(防图内中文乱码)----
import matplotlib
matplotlib.rcParams['font.sans-serif'] = ['Microsoft YaHei', 'SimHei', 'Songti SC', 'Arial Unicode MS', 'DejaVu Sans']
matplotlib.rcParams['axes.unicode_minus'] = False
# -------------------------------------------
import numpy as np
class DecisionStump:
"""决策树桩:在某个特征 j 上按阈值 t 切分,输出 +1 / -1"""
def __init__(self):
self.j, self.t, self.polarity = None, None, 1
self.err = 1.0
def fit(self, X, y, D):
n, d = X.shape
best = None
for j in range(d):
vals = np.unique(X[:, j])
thresholds = (vals[:-1] + vals[1:]) / 2.0 # 相邻取值中点
for t in thresholds:
for polarity in (1, -1):
pred = np.where(X[:, j] <= t, polarity, -polarity)
err = D[pred != y].sum()
if err < self.err:
self.err, self.j, self.t, self.polarity = err, j, t, polarity
return self
def predict(self, X):
return np.where(X[:, self.j] <= self.t, self.polarity, -self.polarity)
class AdaBoost:
"""手写 AdaBoost:M 个决策树桩 + 加权投票"""
def __init__(self, M=30):
self.M = M
self.stumps, self.alphas = [], []
def fit(self, X, y):
n = len(X)
D = np.full(n, 1.0 / n) # 初始样本权重均匀
for _ in range(self.M):
stump = DecisionStump().fit(X, y, D)
if stump.err >= 0.5:
print("弱分类器错误率 >= 0.5,提前停止")
break
alpha = 0.5 * np.log((1 - stump.err) / stump.err)
# 权重更新 + 归一化
D = D * np.exp(-alpha * y * stump.predict(X))
D = D / D.sum()
self.stumps.append(stump)
self.alphas.append(alpha)
return self
def predict(self, X):
score = np.zeros(len(X))
for a, s in zip(self.alphas, self.stumps):
score += a * s.predict(X)
return np.sign(score)
def score(self, X, y):
return float(np.mean(self.predict(X) == y))
# ---- 演示:两个交叠高斯簇(树桩错误率约 0.3,Boosting 逐步提升)----
rng = np.random.default_rng(0)
half = 100
X = np.vstack([rng.normal([-1.5, 0], 1.2, (half, 2)),
rng.normal([1.5, 0], 1.2, (half, 2))])
y = np.array([-1.0] * half + [1.0] * half) # 类0=-1, 类1=+1
idx = rng.permutation(len(X))
X_tr, y_tr = X[idx[:140]], y[idx[:140]]
X_te, y_te = X[idx[140:]], y[idx[140:]]
# 单个树桩:一条轴平行直线只能粗分
single = DecisionStump().fit(X_tr, y_tr, np.full(len(X_tr), 1 / len(X_tr)))
print(f"单个树桩测试准确率 = {np.mean(single.predict(X_te) == y_te):.3f}")
# AdaBoost 组合 30 个树桩
for M in [1, 5, 10, 30, 50]:
ada = AdaBoost(M=M).fit(X_tr, y_tr)
print(f"AdaBoost M={M:3d} 测试准确率 = {ada.score(X_te, y_te):.3f}")
# ---- sklearn 对照:手写 AdaBoost vs sklearn AdaBoostClassifier ----
from sklearn.ensemble import AdaBoostClassifier
from sklearn.tree import DecisionTreeClassifier
# sklearn 标签用 0/1;把 -1/1 映射过去比较预测
y_tr01 = (y_tr + 1) / 2
y_te01 = (y_te + 1) / 2
ada_sk = AdaBoostClassifier(
estimator=DecisionTreeClassifier(max_depth=1, random_state=0),
n_estimators=30, algorithm="SAMME", random_state=0,
)
ada_sk.fit(X_tr, y_tr01)
pred_sk = ada_sk.predict(X_te)
pred_my = (ada.predict(X_te) + 1) / 2 # 手写模型映射到 0/1
print(f"sklearn AdaBoost 准确率 = {np.mean(pred_sk == y_te01):.3f}")
print(f"手写 AdaBoost 准确率 = {np.mean(pred_my == y_te01):.3f}")
print(f"两个模型预测一致率 = {np.mean(pred_sk == pred_my):.3f}")
§4 训练误差上界与“为什么不容易过拟合”¶
误差上界(经典结论):训练误差满足
$$\frac{1}{n} \sum_i \mathbb{1}[G(x_i) \neq y_i] \;\le\; \prod_{m=1}^{M} 2\sqrt{e_m(1-e_m)} \;\le\; \exp\left(-2 \sum_{m=1}^{M} \gamma_m^2\right), \quad \gamma_m = \tfrac{1}{2} - e_m$$
只要每个弱分类器错误率略低于 0.5($\gamma_m > 0$),上界就指数下降——这就是“弱可学习 → 强可学习”的数学保证。
为什么 AdaBoost 增加迭代一般不过拟合?
- 指数损失是光滑的凸损失,同时近似于最大化间隔(margin):AdaBoost 持续把分错的样本权重抬高,相当于在拉大分类间隔,泛化边界更稳;
- 弱分类器“弱”(树桩/浅树),单轮自由度小,组合后总容量仍受限;
- 但要小心:噪声极大或类别严重错标时,AdaBoost 会疯狂放大噪声样本权重 → 过拟合。所以实际常配合:限制迭代轮数、早停、降低学习率。
§5 AdaBoost vs GBDT(必背对比)¶
| 对比项 | AdaBoost | GBDT |
|---|---|---|
| 损失函数 | 指数损失 $e^{-y f}$(推导出闭式权重更新) | 任意可导损失(用负梯度拟合) |
| 权重更新 | 解析公式(乘 $e^{\pm \alpha}$) | 无显式权重,靠残差/负梯度驱动 |
| 对噪声敏感度 | 指数损失对错分样本惩罚指数放大 → 较敏感 | 取决于损失(平方/Huber 更稳) |
| 输出 | 分类(也可回归,用残差版本) | 回归/分类通用 |
| 弱分类器 | 通常树桩/浅树 | 回归树(CART),可控制深度 |
| 扩展 | 多分类用 SAMME/SAMME.R | XGBoost/LightGBM(二阶+正则) |
💡 一句话记忆:AdaBoost 是“指数损失的特例版 boosting”,GBDT 是“任意损失的通用版 boosting”——GBDT 用负梯度代替了 AdaBoost 的解析权重更新,所以能换任意损失。
AdaBoost vs 随机森林:AdaBoost 串行、每轮重训(难并行)、降偏差;RF 并行、降方差。数据噪声大 → RF 更稳;数据干净 → AdaBoost 更准(通常如此)。
§6 常见 bug 与边界(面试踩坑区)¶
- 标签必须转成 $\pm1$:手写版本用 0/1 标签会让指数损失失效;
- $e_m = 0$:$\alpha_m \to +\infty$,权重更新爆炸——加极小值(如
alpha = min(alpha, 15))或直接停止; - $e_m = 0.5$:$\alpha_m = 0$,这轮白干——该弱分类器不比随机好,应换更强的或提前停;
- 权重 $D_m$ 归一化因子 $Z_m$ 漏除 → 权重总和漂移,后续 $e_m$ 含义失真;
- 弱分类器太强(深树):第一轮就把训练集分完,权重退化,boosting 失去意义(树桩/浅树是精髓);
- 预测时忘记把 $\alpha_m$ 带上——最终投票是加权和,不是简单多数。
§7 自测清单(L1 必会 / L2 进阶 / L3 挑战)¶
L1 必会(8 问)¶
- 1. 口述 AdaBoost 四步流程(训练弱分类器→算 α→更新样本权重→加权投票)
- 2. 写出 $e_m$、$\alpha_m$、$D_{m+1}$ 三个公式
- 3. 解释“分错的样本权重放大”背后的指数机制
- 4. Bagging vs Boosting(并行/串行、方差/偏差)
- 5. 为什么弱分类器错误率略低于 0.5 即可
- 6. AdaBoost 与 GBDT 损失函数的区别
- 7. 指数损失为什么对噪声敏感
- 8. 树桩 vs 深树的取舍
L2 进阶(6 问)¶
- 9. 从前向分步加法模型推导出三个更新公式
- 10. 训练误差上界 $\prod 2\sqrt{e_m(1-e_m)}$ 的含义
- 11. 为什么 AdaBoost 通常增加轮数不易过拟合
- 12. SAMME 与 SAMME.R 的区别(离散 vs 概率)
- 13. AdaBoost 多分类怎么做
- 14. 样本权重初始值与归一化细节
L3 挑战(4 问)¶
- 15. 手写 AdaBoost 并在异或数据上跑通
- 16. 解释 margin 理论与 AdaBoost 泛化
- 17. AdaBoost 对错标样本的“病态放大”如何缓解(剪枝/降学习率)
- 18. 从贝叶斯视角解释指数损失为何是分类代理损失
自测要点¶
- 10 分钟内盲写 AdaBoost 三个公式
- 能现场推导“前向分步 + 指数损失 → 权重更新”链路
- 能对比 AdaBoost / GBDT / 随机森林三者的损失与适用场景
🏁 本章小结¶
- 原理一句话:AdaBoost = 加法模型 + 指数损失 → 错题权重指数放大 → 按靠谱程度加权投票。
- 必会公式:$\alpha_m=\frac12\ln\frac{1-e_m}{e_m}$;$D_{m+1}(i)\propto D_m(i)e^{-\alpha_m y_i G_m(x_i)}$;误差上界 $\prod_m 2\sqrt{e_m(1-e_m)}\le e^{-2\sum(\frac12-e_m)^2}$。
- 面试怎么考:指数损失推导两步;为什么弱分类器略好于随机($e_m<0.5$)即可指数级收敛;AdaBoost vs GBDT。
- 易错点:$\alpha$ 与「分对者权重」方向别记反;对噪声敏感(错样本权重指数放大)。
自测清单没把握的条目,回到对应小节重读后再打勾。