Jiayu Lab
← Back to Learning Notes

Lecture 8：集成学习

Chinese-language Computer Science 408 note: Lecture 8：集成学习. Original source available where applicable.

Computer Science 408Record date11 min read
408Interview Subjects
View original PDF Download original
On this page

This note is currently available in Chinese. The original wording, formulas and diagrams are preserved to avoid an unverified technical translation.

描述：本节说明集成学习“好而不同”的核心要求，区分 Boosting 与 Bagging，整理多样性度量、随机森林、AdaBoost 的完整算法，以及 AdaBoost 与指数损失、分类间隔的关系。

8.1 强可学习、弱可学习与集成

  • 强可学习指存在多项式时间学习算法，能训练出错误概率足够小的模型。
  • 弱可学习指学习效果只需稳定地略好于随机猜测。
  • Boosting 理论关心：能否把多个弱学习器组合成强学习器。
  • 集成学习把多个个体学习器组合起来共同解决一个问题。

若所有个体由同类算法生成，称为同质集成；若个体模型类型不同，称为异质集成。

  • 同质集成易于统一比较和组合，但必须通过数据、特征、参数或训练顺序制造差异。
  • 异质集成天然具有差异，但不同模型的输出尺度和语义可能不同，组合前常需校准或对齐。
  • 产生个体学习器的算法称为基学习算法，生成的模型称为基学习器。

8.2 集成有效的条件：好而不同

源资料用三个准确率均为 $66.6%$ 的学习器说明：

  • 若三个学习器犯错位置不同，多数投票可能把整体准确率提高到 $100%$。
  • 若三个学习器在同一位置犯错，投票后仍只有 $66.6%$。
  • 若每个学习器都很差，即使错误不同，多数投票也可能得到更坏结果。

因此有效集成要求：

  1. 个体学习器不能太差。
  2. 个体学习器之间要有足够差异。

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 的缩写。

  1. 从原始数据集通过有放回的自助采样生成多个训练集。
  2. 在每个自助样本集上独立训练一个基学习器。
  3. 分类任务使用投票，回归任务使用平均。

若原始数据有 $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 随机森林

随机森林是以决策树为基学习器的并行集成。

“随机”通常来自两方面：

  1. 每棵树使用原始训练集的自助采样子集。
  2. 每个结点划分时，只从随机选择的一部分候选特征中寻找最优划分。

基本过程：

  1. 设定树的数量、最大深度、每次候选特征数等超参数。
  2. 对每棵树生成自助训练集并独立训练。
  3. 分类取多数票，回归取平均值。

优点：

  • 随机性与平均化通常使模型对噪声和异常点较稳健，不易出现单棵深树那样的高方差过拟合。
  • 能处理高维数据，并可并行训练。
  • 可给出基于划分或置换的特征重要性。

局限：

  • 模型由许多树组成，整体不再像单棵小树那样容易逐路径解释。
  • 特征重要性只表示统计贡献，不等于因果解释，并可能受特征尺度、基数和相关性影响。
  • 随机森林常有较强稳健基线性能，但并非绝不会过拟合，也不能保证解决所有复杂任务。

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$ 后继续改善间隔，但噪声和异常点仍可使其过拟合。

相关知识

8.13 本节复盘

  • 集成学习用多个学习器共同预测，有效集成要求个体“好而不同”。
  • 误差-分歧分解表明，在适用条件下，个体误差越小、分歧越大，集成误差越低。
  • Boosting 顺序训练，后续模型关注前面错误；Bagging 用自助样本并行训练，再投票或平均。
  • 自助训练集约含 $63.2%$ 个不同原始样本。
  • 随机森林同时随机采样样本和候选特征，分类取众数，回归取均值。
  • AdaBoost 依据加权错误率计算 $\alpha_t$，提高错分样本权重，最后输出 $\operatorname{sign}(\sum_t\alpha_th_t)$。
  • 指数损失解释 AdaBoost 的函数优化过程，间隔理论解释训练误差为 $0$ 后仍可能提升泛化；但它并非绝不会过拟合。