Lecture 8：集成学习
408 学习笔记：Lecture 8：集成学习。保留原有知识内容、公式与图示；有对应原件时提供查看和下载入口。
本页目录
描述：本节说明集成学习“好而不同”的核心要求，区分 Boosting 与 Bagging，整理多样性度量、随机森林、AdaBoost 的完整算法，以及 AdaBoost 与指数损失、分类间隔的关系。
8.1 强可学习、弱可学习与集成
- 强可学习指存在多项式时间学习算法，能训练出错误概率足够小的模型。
- 弱可学习指学习效果只需稳定地略好于随机猜测。
- Boosting 理论关心：能否把多个弱学习器组合成强学习器。
- 集成学习把多个个体学习器组合起来共同解决一个问题。
若所有个体由同类算法生成，称为同质集成；若个体模型类型不同，称为异质集成。
- 同质集成易于统一比较和组合，但必须通过数据、特征、参数或训练顺序制造差异。
- 异质集成天然具有差异，但不同模型的输出尺度和语义可能不同，组合前常需校准或对齐。
- 产生个体学习器的算法称为基学习算法，生成的模型称为基学习器。
8.2 集成有效的条件：好而不同
源资料用三个准确率均为 $66.6%$ 的学习器说明：
- 若三个学习器犯错位置不同，多数投票可能把整体准确率提高到 $100%$。
- 若三个学习器在同一位置犯错，投票后仍只有 $66.6%$。
- 若每个学习器都很差，即使错误不同，多数投票也可能得到更坏结果。
因此有效集成要求：
- 个体学习器不能太差。
- 个体学习器之间要有足够差异。
8.3 误差-分歧分解
在平方损失等特定条件下，集成误差可分解为
$$ E=\bar E-\bar A, $$
其中：
-
$E$ 是集成误差。
-
$\bar E$ 是个体学习器平均误差。
-
$\bar A$ 是个体相对集成输出的平均分歧，也称 ambiguity 或 diversity。
-
希望 $\bar E$ 小，即个体准确。
-
希望 $\bar A$ 大，即个体多样。
-
“误差小”和“差异大”往往相互制约，实际算法要在二者之间平衡。
-
该等式依赖具体损失、组合规则和假设，不能无条件套用到所有分类集成。
8.4 两类主要集成方法
| 类型 | 训练关系 | 代表算法 | 核心方式 |
|---|---|---|---|
| 序列化 | 后一模型依赖前一模型 | AdaBoost、Gradient Boost | 逐轮关注前面未解决的问题 |
| 并行化 | 各模型可相对独立训练 | Bagging、Random Forest、Random Subspace | 重采样或随机特征制造差异 |
8.5 Boosting
- Boosting 先训练第一个学习器，再根据其错误调整训练分布或残差，使后续学习器更关注困难样本。
- 各学习器按顺序生成，后一学习器依赖前面学习器的结果。
- 最后使用加权组合得到集成输出。
- Boosting 主要降低偏差，能把许多弱学习器逐步增强。
8.6 Bagging
Bagging 是 Bootstrap Aggregating 的缩写。
- 从原始数据集通过有放回的自助采样生成多个训练集。
- 在每个自助样本集上独立训练一个基学习器。
- 分类任务使用投票，回归任务使用平均。
若原始数据有 $m$ 个样本，每个自助集抽取 $m$ 次，则一个样本至少被抽到一次的概率趋于
$$ 1-\frac{1}{e} \approx0.632. $$
- 每个自助集约含 $63.2%$ 个不重复的原始样本，其余抽样位置是重复样本。
- 源资料写作 $63.7%$，按极限公式正确近似值应为 $63.2%$。
- 不同自助集不完全相同，从而产生有差异的学习器。
- Bagging 可并行训练，常用于降低高方差模型的方差。
8.7 多样性度量
对两个二分类器 $h_i,h_j$，可按预测是否正确构造表：
| $h_i$ 正确 | $h_i$ 错误 | |
|---|---|---|
| $h_j$ 正确 | $a$ | $c$ |
| $h_j$ 错误 | $b$ | $d$ |
- 两者预测表现一致的样本数是 $a+d$。
- 两者表现不一致的样本数是 $b+c$。
- 源资料用
$$ \frac{b+c}{a+d} $$
或
$$ (b+c)-(a+d) $$
直观比较分歧。
- 常见标准化不合度为
$$ \operatorname{dis}(h_i,h_j)
\frac{b+c}{a+b+c+d}. $$
- 其他度量还包括相关系数、$Q$ 统计量和 $\kappa$ 统计量。
- 多样性必须结合个体准确率理解，差异越大并不自动意味着集成越好。
8.8 随机森林
随机森林是以决策树为基学习器的并行集成。
“随机”通常来自两方面：
- 每棵树使用原始训练集的自助采样子集。
- 每个结点划分时，只从随机选择的一部分候选特征中寻找最优划分。
基本过程：
- 设定树的数量、最大深度、每次候选特征数等超参数。
- 对每棵树生成自助训练集并独立训练。
- 分类取多数票，回归取平均值。
优点：
- 随机性与平均化通常使模型对噪声和异常点较稳健，不易出现单棵深树那样的高方差过拟合。
- 能处理高维数据，并可并行训练。
- 可给出基于划分或置换的特征重要性。
局限：
- 模型由许多树组成，整体不再像单棵小树那样容易逐路径解释。
- 特征重要性只表示统计贡献，不等于因果解释，并可能受特征尺度、基数和相关性影响。
- 随机森林常有较强稳健基线性能，但并非绝不会过拟合，也不能保证解决所有复杂任务。
8.9 AdaBoost
AdaBoost 是 Adaptive Boosting，即自适应增强。
- 先训练弱学习器。
- 降低已正确分类样本的权重，提高误分类样本的权重。
- 后续学习器更关注前面难以处理的样本。
- 最终按每个弱学习器的可靠程度加权组合。
它与 Bagging 的主要差异是：
| 对比 | Bagging/随机森林 | AdaBoost |
|---|---|---|
| 训练关系 | 相对独立、可并行 | 顺序依赖 |
| 数据变化 | 自助采样 | 调整样本权重 |
| 组合 | 常等权投票/平均 | 加权投票 |
| 主要效果 | 降低方差 | 逐步降低偏差 |
| 对异常点 | 通常较稳健 | 可能过度关注错分异常点 |
8.10 AdaBoost 算法
给定训练集
$$ D={(\boldsymbol{x}i,y_i)}{i=1}^{m}, \qquad y_i\in{-1,+1}, $$
基学习算法 $\mathcal L$ 和轮数 $T$。
8.10.1 初始化
每个样本初始权重相同：
$$ D_1(i)=\frac{1}{m}. $$
8.10.2 第 $t$ 轮
用当前分布训练弱学习器：
$$ h_t=\mathcal L(D,D_t). $$
加权错误率：
$$ \epsilon_t
\sum_{i=1}^{m} D_t(i) \mathbb I \left( h_t(\boldsymbol{x}_i)\neq y_i \right). $$
若
$$ \epsilon_t\geq 0.5, $$
该二分类弱学习器不优于随机猜测；$\epsilon_t=0.5$ 时 $\alpha_t=0$，本轮没有贡献，应停止、重新训练或换学习器。若 $\epsilon_t=0$，弱学习器已在当前加权训练集上完美分类，下面的对数公式会发散，应直接停止或在数值实现中裁剪误差。因此有限权重公式按 $0<\epsilon_t<0.5$ 使用。
学习器权重：
$$ \alpha_t
\frac{1}{2} \ln \frac{1-\epsilon_t}{\epsilon_t}. $$
更新样本分布：
$$ D_{t+1}(i)
\frac{ D_t(i) \exp \left[ -\alpha_ty_ih_t(\boldsymbol{x}_i) \right] }{ Z_t }, $$
其中 $Z_t$ 是归一化常数。
等价地：
$$ D_{t+1}(i)
\frac{D_t(i)}{Z_t} \begin{cases} e^{-\alpha_t}, &h_t(\boldsymbol{x}_i)=y_i,\ e^{\alpha_t}, &h_t(\boldsymbol{x}_i)\neq y_i. \end{cases} $$
归一化后，正确样本的权重可写为
$$ w_i^{\mathrm{new}}
\frac{1}{2(1-\epsilon_t)} w_i^{\mathrm{old}}, $$
错误样本的权重为
$$ w_i^{\mathrm{new}}
\frac{1}{2\epsilon_t} w_i^{\mathrm{old}}. $$
因为 $\epsilon_t<0.5$，错分样本权重会相对增大。
8.10.3 输出
最终强分类器为
$$ H(\boldsymbol{x})
\operatorname{sign} \left( \sum_{t=1}^{T} \alpha_t h_t(\boldsymbol{x}) \right). $$
- 错误率越小，$\alpha_t$ 越大，该弱学习器在最终投票中权重越高。
8.11 AdaBoost、指数损失与过拟合
8.11.1 统计观点
- 0-1 损失不连续，直接优化困难。
- AdaBoost 的样本权重更新与指数损失密切相关，可理解为逐步优化
$$ \sum_{i=1}^{m} \exp \left[ -y_iF(\boldsymbol{x}_i) \right]. $$
- 改变替代损失和优化方式可得到其他 Boosting 方法。
- 这一观点解释了权重更新和函数优化的联系，但不能单独保证 AdaBoost 永不过拟合。
8.11.2 间隔观点
对样本 $(\boldsymbol{x}_i,y_i)$，集成分类间隔可写为
$$ \operatorname{margin}_i
\frac{ y_i\sum_{t=1}^{T} \alpha_t h_t(\boldsymbol{x}i) }{ \sum{t=1}^{T}|\alpha_t| }. $$
- 间隔为正表示分类正确，间隔越大通常表示分类把握越强。
- 即使训练误差已降到 $0$，继续训练仍可能改善间隔分布，因此测试性能有时继续提高。
- 研究后来从只关注最小间隔，发展到关注平均间隔或整个间隔分布，并结合模型复杂度给出泛化界。
8.11.3 正确结论
- AdaBoost 在许多干净数据上表现出对继续训练的经验抗过拟合现象。
- 但它会持续提高错分样本权重，对标签噪声和异常点可能非常敏感，仍然可能过拟合。
- 因而不能简单断言“AdaBoost 不会过拟合”；应结合噪声、基学习器复杂度、轮数和验证性能判断。
8.12 易错点
- 集成不是模型越多越好；个体若高度相关或普遍很差，投票不能产生有效提升。
- 同质模型表示算法类型相同，不表示训练数据、参数和预测完全相同。
- Bagging 的单个自助训练集约含 $63.2%$ 个不同原始样本，不是 $63.2%$ 个抽样位置。
- 随机森林除样本随机外，还在结点划分时随机选择候选特征。
- 随机森林分类用投票，回归用平均。
- 多样性越大不一定越好，必须与个体误差同时考虑。
- AdaBoost 的弱学习器必须优于随机猜测，二分类中要求 $\epsilon_t<0.5$。
- $\epsilon_t=0.5$ 时弱学习器权重为 0，$\epsilon_t=0$ 时理论权重趋于无穷；两种边界都应在代入对数公式前单独处理。
- 错分样本权重变大，正确样本权重变小；弱学习器权重 $\alpha_t$ 随错误率下降而增大。
- AdaBoost 的最终结果是加权符号和，不是简单等权多数票。
- AdaBoost 可能在训练误差为 $0$ 后继续改善间隔，但噪声和异常点仍可使其过拟合。
相关知识
- 科目导航：复试常考科目导航
- 阅读顺序：上一篇：贝叶斯决策论 · 下一篇：聚类
- 关联专题：AdaBoost 与特征选择
8.13 本节复盘
- 集成学习用多个学习器共同预测，有效集成要求个体“好而不同”。
- 误差-分歧分解表明，在适用条件下，个体误差越小、分歧越大，集成误差越低。
- Boosting 顺序训练，后续模型关注前面错误；Bagging 用自助样本并行训练，再投票或平均。
- 自助训练集约含 $63.2%$ 个不同原始样本。
- 随机森林同时随机采样样本和候选特征，分类取众数，回归取均值。
- AdaBoost 依据加权错误率计算 $\alpha_t$，提高错分样本权重，最后输出 $\operatorname{sign}(\sum_t\alpha_th_t)$。
- 指数损失解释 AdaBoost 的函数优化过程，间隔理论解释训练误差为 $0$ 后仍可能提升泛化；但它并非绝不会过拟合。