第十一讲 · AdaBoost 与目标检测

AdaBoost 的直觉很朴素：让一群“只比随机猜测好一点”的弱分类器轮流做题，每轮都把上一轮做错的题加粗，最后按可靠程度加权投票。单个弱分类器可能只是一条阈值线，组合后却能形成复杂的非线性边界。

一、为什么要反复改变样本权重

若每轮都在同一份等权数据上训练，弱分类器很可能反复做出相似判断。AdaBoost 维护一个样本分布 $D_t$：

• 分错的样本在下一轮权重变大；
• 分对的样本权重变小；
• 下一位弱学习器被迫关注当前集成模型的薄弱处。

这不是简单地“多训练几次”，而是让每一轮面对一个重新加权的问题。最终分类器是各轮结果的加权和。

二、AdaBoost 二分类算法

训练集为 $\{(x_i,y_i)\}_{i=1}^n$，其中 $y_i\in\{-1,+1\}$。初始时每个样本等权：

$$D_1(i)=\frac1n.$$

第 $t$ 轮执行以下步骤。

1. 训练误差最小的弱分类器

在当前分布下寻找 $h_t(x)\in\{-1,+1\}$，使加权错误率最小：

$$\varepsilon_t =\sum_{i=1}^n D_t(i)\,\mathbb I\bigl[h_t(x_i)\ne y_i\bigr].$$

2. 计算弱分类器的投票权

$$\alpha_t=\frac12\ln\frac{1-\varepsilon_t}{\varepsilon_t}.$$

$\varepsilon_t$ 越小，$\alpha_t$ 越大；若错误率恰为 $0.5$，则 $\alpha_t=0$，等于没有发言权。若 $\varepsilon_t>0.5$，通常翻转分类器输出或停止这一轮。

3. 更新样本分布

$$D_{t+1}(i) =\frac{D_t(i)\exp\bigl(-\alpha_t y_i h_t(x_i)\bigr)}{Z_t},$$

其中 $Z_t$ 是让权重和重新变成 $1$ 的归一化常数。因为 $y_i h_t(x_i)$ 在分对时为 $+1$、分错时为 $-1$：

• 分对：乘 $e^{-\alpha_t}$；
• 分错：乘 $e^{+\alpha_t}$。

最终强分类器为

$$H(x)=\operatorname{sign}\left(\sum_{t=1}^T\alpha_t h_t(x)\right).$$

三、一个两轮数值例子

设有 5 个等权样本，第一轮弱分类器 $h_1$ 只分错第 5 个样本。于是

$$\varepsilon_1=\frac15=0.2, \qquad \alpha_1=\frac12\ln4\approx0.693.$$

更新前每个样本权重都是 $0.2$。分对样本的未归一化权重为 $0.2e^{-0.693}=0.1$，分错样本为 $0.2e^{0.693}=0.4$。总和 $Z_1=0.8$，归一化后：

样本	1	2	3	4	5
$D_2$	0.125	0.125	0.125	0.125	0.5

第 5 个样本独占一半权重，下一轮无法再被忽略。假设 $h_2$ 把第 5 个样本分对，只分错第 1 个样本，则

$$\varepsilon_2=0.125, \qquad \alpha_2=\frac12\ln7\approx0.973.$$

若 $h_1$ 对第 5 个样本投错票 $-1$，$h_2$ 投对票 $+1$，集成得分为

$$-0.693+0.973=0.280>0,$$

最终就能纠正第一轮的错误。这也说明投票不是一人一票，而是按本轮可靠度加权。

四、从指数损失理解权重公式

记当前集成得分为 $F(x)=\sum_t\alpha_t h_t(x)$。AdaBoost 可以看作逐轮最小化指数损失

$$\sum_i \exp\bigl(-y_iF(x_i)\bigr).$$

$y_iF(x_i)$ 称为分类间隔：符号表示是否分对，绝对值表示信心。间隔为负或很小的样本指数损失大，自然会在下一轮得到更多关注。

课件还追问 AdaBoost 是否总能得到最大间隔。答案是否定的：它通常会改善样本间隔，但优化目标是指数损失，不等同于 SVM 的显式最大几何间隔。

多个线性弱分类器的加权和还可以形成非线性边界。例如异或的四个点无法被一条直线分开，但若用若干水平、竖直阈值切出不同区域，再组合投票，就能表达异或。组合代价是模型越来越长；若部署要求极低延迟，可以剪掉冗余弱分类器或用模型蒸馏压缩，但压缩不是原始 AdaBoost 算法的一部分。

五、从 AdaBoost 到 Viola–Jones 人脸检测

经典 Viola–Jones 检测器把三个点组合起来：Haar-like 矩形特征、积分图、AdaBoost 特征选择与级联分类器。

1. Haar-like 矩形特征

在 $24\times24$ 的检测窗口中放置两矩形、三矩形或四矩形模板，用亮区像素和减去暗区像素和。不同位置、尺度和方向组合会产生数万个候选特征。

这些特征表达能力不如现代卷积特征，但计算极快，适合在整张图的海量滑动窗口上重复评估。

2. 积分图把矩形求和变成常数时间

积分图定义为

$$II(x,y)=\sum_{x'\le x,\,y'\le y}I(x',y').$$

若矩形四角的积分图值分别为左上 $A$、右上 $B$、左下 $C$、右下 $D$，矩形像素和为

$$S=D-B-C+A.$$

无论矩形多大，都只需固定次数的数组访问。课件写成 $II(4)+II(1)-II(2)-II(3)$，本质就是同一个容斥公式。

3. AdaBoost 同时做分类与特征选择

每个弱分类器只使用一个 Haar 特征及其阈值。AdaBoost 每轮从数万个候选中选出当前加权错误率最低的特征，因此最终强分类器只保留一小部分有判别力的特征。

课件中的 200 特征检测器在特定实验上可取得约 $0.95$ 检出率和约 $10^{-4}$ 假阳性率；这些数字依赖当时的数据集与阈值，只用于理解“许多便宜特征组合后也能很强”，不能直接当作现代数据上的性能承诺。

4. 级联：让绝大多数背景尽早退出

一张图片的滑窗绝大多数都是背景。若每个窗口都跑完整强分类器，计算仍然昂贵。级联把检测器排成多级：

1. 前几级非常便宜，快速拒绝明显背景；
2. 只有通过前级的困难窗口才进入后级；
3. 后级更复杂，专门减少假阳性。

训练时，第 $k$ 级重点使用能通过前 $k-1$ 级的困难负样本。若每级正样本通过率为 $d_k$、假阳性率为 $f_k$，总通过率与总假阳性率分别为

$$D=\prod_k d_k, \qquad F=\prod_k f_k.$$

例如 10 级都保留 $99\%$ 正样本，则总检出率约为 $0.99^{10}\approx90.4\%$；若每级只让 $50\%$ 背景通过，总假阳性率约为 $0.5^{10}\approx0.098\%$。

课件记录的训练集包含 4916 个对齐、归一化到 $24\times24$ 的正样本，以及从 9500 张无人脸图片中抽取的 10000 个负窗口；测试使用 MIT+CMU 正面人脸集的 130 张图、507 张标注人脸。这些规模解释了为什么需要难负样本挖掘，也同样只代表当时实验口径。

课件结尾还对比了另一类历史检测器：用基于部件的小波特征与似然比检验，通过训练阶段的概率表估计似然，再用 AdaBoost 改善性能。它说明 Boosting 并不绑定 Haar 特征；只要能提供弱分类器，就可以组合其他特征与判别规则。

六、AdaBoost、随机森林与 SVM 的区别

方法	每轮/每棵模型的关系	主要机制	典型关注点
AdaBoost	串行，后轮依赖前轮错误	重加权样本并加权投票	难样本与间隔
随机森林	多棵树可并行	随机样本与随机特征后平均	降低方差与树相关性
SVM	一个整体凸优化问题	最大间隔与支持向量	决策边界附近样本

AdaBoost 原生是二分类。多类任务可以使用 one-vs-rest，也可以用 AdaBoost.M1、SAMME 等直接多类扩展。

七、常见误区与 sanity check

• 更新的是样本权重分布，不是把分错样本简单复制一次。
• $D_t(i)$ 每轮归一化后必须非负且总和为 $1$。
• 弱分类器必须优于随机猜测；二分类下应有 $\varepsilon_t<0.5$。
• $\alpha_t$ 随错误率下降而增大。若算出错误率更低反而投票权更小，公式符号写反了。
• 级联的目标不是提高单个窗口的表达能力，而是用“先便宜拒绝、再精细判断”降低平均计算量。