集成学习与随机森林
理解为什么多个弱一些但互补的模型结合起来，常常比单个强模型更稳。掌握 Boosting（串行纠错）与 Bagging（并行扰动）两类集成策略的数学动机、算法流程与性能差异。
从课程脉络看：C03 引入了概率视角下的多模型融合（贝叶斯模型平均），C04 则从频率派角度给出另一条路——不建模概率分布，而是直接组织多个学习器做加权投票。同时，集成思想在 L07 的 Dropout 等正则化技术中会以新的形式再次出现。
前置知识回顾
- 偏差-方差分解：单个模型的泛化误差可分解为偏差（系统性偏移）与方差（对数据扰动敏感度）。作用：理解 Boosting 降偏差、Bagging 降方差的分工。去哪里补：L02 线性模型。
- 决策树：集成方法中最常用的基学习器。作用：Bagging 和随机森林都以树为基本组件。去哪里补：周志华《机器学习》第 4 章。
- 信息增益与熵：决策树分裂准则的核心度量。作用：理解随机森林中节点分裂如何被特征子集约束。去哪里补：25C04 课件第 24–28 页。
单个学习器容易受数据划分、噪声和模型容量影响。训练过程本身的随机性（数据采样、参数初始化、特征选择）意味着同一算法在不同训练集上可能产出差异很大的模型。集成学习的动机非常朴素：如果个体学习器准确率都高于随机猜测，且错误彼此不完全重叠，那么投票或加权组合后的预测可以比任何一个单模型都更稳。
课件用一张三分类器的投票表（$h_1, h_2, h_3$）清楚展示了这个直觉：即使每个个体都犯了错，但错误位置不同，集成就可能全部判对。
定义 / 符号
集成学习 (Ensemble Learning)：通过构建并结合多个学习器来完成学习任务，又名多分类器系统 (Multi-classifier System) 或基于委员会的学习 (Committee-based Learning)。
- 同质集成：所有个体学习器为同种类型，称为基学习器 (Base Learner)。
- 异质集成：个体学习器为不同类型，称为组件学习器 (Component Learner)。
集成学习按个体学习器的依赖关系分为两大家族：
| 家族 | 依赖关系 | 代表方法 | 核心思路 |
|---|---|---|---|
| Boosting | 强依赖、串行生成 | AdaBoost, Gradient Boosting | 逐轮纠错，降低偏差 |
| Bagging | 无强依赖、并行生成 | Bagging, 随机森林 | 样本/特征扰动，降低方差 |
AdaBoost（Adaptive Boosting）是 Boosting 家族最经典的代表。它的算法框架如下：
AdaBoost 算法流程
输入：训练集 $D = \{(x_1, y_1), \ldots, (x_N, y_N)\}$，$y_i \in \{-1, +1\}$；基学习器空间 $\mathcal{H}$；训练轮数 $T$。
- 初始化：样本权值分布 $D_1(i) = 1/N$。
- for $t = 1, 2, \ldots, T$：
- 基于分布 $D_t$ 从 $D$ 中训练出基分类器 $h_t(x)$。
- 估计 $h_t$ 的加权误差：$e_t = \sum_{i=1}^N D_t(i) \cdot \mathbb{I}[h_t(x_i) \neq y_i]$。
- 确定 $h_t$ 的权重：$\alpha_t = \frac{1}{2} \ln \frac{1 - e_t}{e_t}$。
- 更新样本分布：$D_{t+1}(i) = \frac{D_t(i)}{Z_t} \exp\bigl(-\alpha_t \, y_i \, h_t(x_i)\bigr)$，其中 $Z_t$ 为归一化因子。
- 输出：$H(x) = \mathrm{sign}\!\left(\sum_{t=1}^T \alpha_t \, h_t(x)\right)$。
这个递推结构的设计包含了三层直觉：
- 误差 $e_t$ 驱动权重：$e_t$ 越小，$\alpha_t$ 越大——越准的分类器在最终投票中话语权越重。
- 指数更新放大难样本：被 $h_t$ 分错的样本（$y_i h_t(x_i) = -1$），下一轮权值被放大 $e^{\alpha_t}$ 倍；分对的则缩小 $e^{-\alpha_t}$ 倍。
- 归一化因子 $Z_t$：确保 $D_{t+1}$ 仍是合法概率分布。
Bagging（Bootstrap Aggregating）不走串行纠错路线，而是通过数据扰动制造多样性：
Bagging 算法流程
- 对训练集 $D$ 做 $T$ 次有放回采样（Bootstrap），得到 $T$ 个子集 $D_1, D_2, \ldots, D_T$。
- 在每个子集上独立训练基学习器 $h_1, h_2, \ldots, h_T$。
- 分类任务用多数投票，回归任务用简单平均。
随机森林在 Bagging 基础上引入了第二层随机性：属性扰动。在构建每棵决策树时，每个节点不再遍历全部 $n$ 个特征，而是先随机选 $K$ 个特征子集，再在其中找最优分裂。常用设置：$K = \log_2 n$（分类）或 $K = n/3$（回归）。
偏差-方差分解（回顾）
单个模型的期望泛化误差可分解为：$\mathbb{E}[\text{Error}] = \text{Bias}^2 + \text{Variance} + \text{Noise}$。集成方法的性能差异，主要来自它们分别对这个分解的不同项做了优化。
| 维度 | AdaBoost | Bagging | 随机森林 |
|---|---|---|---|
| 个体生成方式 | 串行、逐轮改权重 | Bootstrap 并行训练 | Bootstrap + 随机特征子集 |
| 主要降低 | 偏差 | 方差 | 方差 + 个体相关性 |
| 基学习器要求 | 弱于随机即可 | 不稳定的学习器效果最好 | 不稳定的学习器效果最好 |
| 多样性来源 | 样本权值重分配 | 样本扰动 | 样本扰动 + 属性扰动 |
| 计算效率 | 必须串行 | 可并行 | 可并行 |
| 对噪声敏感度 | 较高（会过拟合噪声样本） | 较低 | 较低 |
课件第 35 页展示了一组 UCI 数据集上的实验：随着树数量增加，随机森林的泛化误差收敛且始终低于 Bagging，证明了属性扰动的额外收益。
例题：AdaBoost 权值更新手算
题目：给定 10 个训练样本（二分类，$y \in \{-1, +1\}$），基分类器形式为"阈值分割"（$h(x) = \mathrm{sign}(x - \theta)$）。要求手动迭代 3 轮 AdaBoost。
目标：理解每轮权值如何变化、$\alpha_t$ 如何计算、最终强分类器如何形成。
- 初始化：$D_1(i) = 1/10 = 0.1$，所有样本等权。
- 第 1 轮：训练 $h_1$，假设加权错误率 $e_1 = 0.3$。则 $\alpha_1 = \frac{1}{2}\ln\frac{0.7}{0.3} \approx 0.4236$。被 $h_1$ 分错的 3 个样本在 $D_2$ 中权值升高，分对的 7 个样本权值降低。
- 第 2 轮：新的权值分布 $D_2$ 使前一轮分错的样本占比更高。训练 $h_2$，假设 $e_2 = 0.2$，则 $\alpha_2 = \frac{1}{2}\ln\frac{0.8}{0.2} \approx 0.6931$。
- 第 3 轮：类似地训练 $h_3$，得到 $\alpha_3$。
- 最终分类器：$H(x) = \mathrm{sign}(\alpha_1 h_1(x) + \alpha_2 h_2(x) + \alpha_3 h_3(x))$。
观察：第 1 轮错误率为 30%，第 2 轮降到 20%——因为 $D_2$ 让 $h_2$ 更关注 $h_1$ 分错的难点。这正是 Boosting "逐轮纠错"的直观体现。
例题：随机森林为什么比单棵树和纯 Bagging 都稳？
题目：在相同数据集上对比三种方案的泛化表现，解释差异来源。
- 单棵决策树：高方差。数据中微小的扰动就可能让分裂路径完全不同，导致预测大变。
- Bagging：通过 Bootstrap 采样训练多棵树再投票。样本扰动引入了多样性，降低了集成后的方差。但个体树仍然每次看全部特征，分裂逻辑容易趋同。
- 随机森林：在 Bagging 基础上限制每次分裂只看 $K$ 个随机特征。这意味着即使两棵树的训练集很相似，它们在关键分裂点上也可能走向不同方向。
答案：随机森林的额外属性扰动进一步降低了个体之间的相关性。在偏差-方差分解中，集成的方差正比于 $\bar{\sigma}^2 \cdot \rho$（平均方差 × 相关系数），所以降低 $\rho$ 直接降低总方差。
课件给出的两个经典应用场景帮助理解集成方法的落地：
| 应用 | 方法 | 核心思路 |
|---|---|---|
| 数字分类 | AdaBoost + 阈值分类器 | 每轮找一个新阈值，逐步聚焦错分区域，三轮后分类边界远比单阈值复杂 |
| 人脸检测（Viola-Jones） | AdaBoost + Haar-like 特征 | 级联结构：每层用 AdaBoost 筛出少量强特征，逐层过滤非人脸区域，实现实时检测 |
后续用途 / 连接
- L05 压缩感知：集成学习强调"多样性"，压缩感知强调"稀疏性"——二者在高维数据中相互补充。多字典集成（Ensemble Dictionary）就是两者结合的典型思路。
- L07 神经网络：Dropout 训练时随机丢弃神经元，本质上是隐式地训练了 $2^n$ 个子网络的集成。这种"在线集成"的思想直接来自 Bagging 的启发。
- C03 → C04 桥梁：贝叶斯模型平均（后验加权预测）与集成学习（频率派加权投票）解决的是同一类"多假设融合"问题，只是哲学出发点不同。
复习速查
- 核心准则：好而不同——个体准确且错误不重叠。
- AdaBoost：串行纠错，指数更新权值，$\alpha_t = \frac{1}{2}\ln\frac{1-e_t}{e_t}$，主要降偏差。
- Bagging：Bootstrap 采样 + 并行训练 + 投票/平均，主要降方差。
- 随机森林：Bagging + 属性扰动（$K$ 个随机特征），进一步降低个体相关性。
- 选择策略：基学习器不稳定时用 Bagging/RF；基学习器欠拟合时用 Boosting。
参考来源
- 课程课件：25C04 第 4–5 页（投票示例与好而不同）
- 课程课件：25C04 第 8–15 页（Boosting 机制、AdaBoost 算法、手算示例）
- 课程课件：25C04 第 21–23 页（Bagging 算法）
- 课程课件：25C04 第 32–35 页（随机森林与误差曲线）
- 公开参考：Sebastian Raschka, STAT 451 Ensemble Notes（https://sebastianraschka.com/pdf/lecture-notes/stat451fs20/07-ensembles__notes.pdf）
- 公开参考：scikit-learn Ensembles 文档（https://scikit-learn.org/stable/modules/ensemble.html）
- 公开参考：Weinan Zhang, Ensemble and Boosting Algorithms（http://wnzhang.net/teaching/cs420/slides/6-ensemble-boosting.pdf）