Chapter 8: 集成学习

约 2089 个字 1 张图片 预计阅读时间 7 分钟

1. 个体与集成

弱学习器/Weak Learner 常指泛化性能略高于随机猜测的学习器。

在一般经验中，如果将好坏不等的东西掺杂在一起，往往得到的东西比最坏的要好一些，比最好的要坏一些；或者干脆遵循木桶短板理论。集成学习需要避免这么悲催的事情，因此我们引入多样性这一概念：

考虑二分类问题 \(y \in \{-1,+1\}\) 和真实函数 \(f\)，假定基分类器的错误率为 \(\epsilon\)，即对每个基分类器 \(h_i\) 有

\[P(h_i(\boldsymbol{x}) \neq f(\boldsymbol{x})) = \epsilon.\]

假设集成通过简单投票法结合 \(T\) 个基分类器，若有超过半数的基分类器正确，则集成分类就正确：

\[H(\boldsymbol{x}) = \text{sign}\left(\sum_{i=1}^T h_i(\boldsymbol{x})\right).\]

假设基分类器的错误率相互独立，则由 Hoeffding 不等式可知，集成的错误率为

\[P(H(\boldsymbol{x}) \neq f(\boldsymbol{x})) = \sum_{k=\lfloor T/2 \rfloor + 1}^T \begin{pmatrix} T \\ k \end{pmatrix} \epsilon^k(1-\epsilon)^{T-k} \leq \exp\left(-\frac{1}{2}T(1-2\epsilon)^2\right).\]

上式显示出，随着集成中个体分类器数目 \(T\) 的增大，集成的错误率将指数级下降，最终趋向于零。

但是我们有一个关键假设：基学习器的误差相互独立。在现实任务中，个体学习器是为解决同一个问题训练出来的，它们显然不可能相互独立！事实上，个体学习器的准确性和多样性本身出现冲突，一般地，准确性很高之后，要增加多样性就需牺牲准确性。如何产生并结合“好而不同”的个体学习器，是集成学习研究的核心。

根据个体学习器的生成方式，目前的集成学习方法大致可分为两大类，即个体学习器间存在强依赖关系、必须串行生成的序列化方法，以及个体学习器间不存在强依赖关系、可同时生成的并行化方法；前者的代表是 Boosting，后者的代表是 Bagging 和“随机森林”。

2. Boosting

分类器权重更新公式：

样本更新公式：AdaBoost 算法在获得 \(H_{t-1}\) 之后样本分布进行调整，使得下一轮的基学习器 \(h_t\) 能纠正 \(H_{t-1}\) 的一些错误，理想的 \(h_t\) 能纠正 \(H_{t-1}\) 的全部错误，即最小化：

\[\begin{aligned} \ell_{\exp}(H_{t-1}+h_t|\mathcal{D}) &= \mathbb{E}_{x\sim\mathcal{D}}[e^{-f(x)(H_{t-1}(x)+h_t(x))}] \\ &= \mathbb{E}_{x\sim\mathcal{D}}[e^{-f(x)H_{t-1}(x)}e^{-f(x)h_t(x)}] \end{aligned}\]

注意到 \(f^2(x)=h_t^2(x)=1\)，上式可使用 \(e^{-f(x)h_t(x)}\) 的泰勒展式近似为：

\[\begin{aligned} \ell_{\exp}(H_{t-1}+h_t|\mathcal{D}) &= \mathbb{E}_{x\sim\mathcal{D}}\left[e^{-f(x)H_{t-1}(x)}\left(1-f(x)h_t(x)+\frac{f^2(x)h_t^2(x)}{2}\right)\right] \\ &= \mathbb{E}_{x\sim\mathcal{D}}\left[e^{-f(x)H_{t-1}(x)}\left(1-f(x)h_t(x)+\frac{1}{2}\right)\right] \end{aligned}\]

于是，理想的基学习器满足：

\[\begin{aligned} h_t(x) &= \arg\min_h \ell_{\exp}(H_{t-1}+h|\mathcal{D}) \\ &= \arg\min_h \mathbb{E}_{x\sim\mathcal{D}}\left[e^{-f(x)H_{t-1}(x)}\left(1-f(x)h(x)+\frac{1}{2}\right)\right] \\ &= \arg\max_h \mathbb{E}_{x\sim\mathcal{D}}\left[e^{-f(x)H_{t-1}(x)}f(x)h(x)\right] \\ &= \arg\max_h \mathbb{E}_{x\sim\mathcal{D}}\left[\frac{e^{-f(x)H_{t-1}(x)}}{\mathbb{E}_{x\sim\mathcal{D}}[e^{-f(x)H_{t-1}(x)}]}f(x)h(x)\right] \\ &= \arg\max_h \mathbb{E}_{x\sim\mathcal{D}_t}[f(x)h(x)] \end{aligned}\]

注意到 \(\mathbb{E}_{x\sim\mathcal{D}}[e^{-f(x)H_{t-1}(x)}]\) 是一个常数，所以 \(\mathcal{D}_t\) 为下面的分布：

\[\mathcal{D}_t(x) = \frac{\mathcal{D}(x)e^{-f(x)H_{t-1}(x)}}{\mathbb{E}_{x\sim\mathcal{D}}[e^{-f(x)H_{t-1}(x)}]}\]

3. Bagging 与随机森林

欲得到泛化性能强的集成，集成中的个体学习器应该尽可能相互独立，虽然独立在现实任务中无法做到，但是可以设法使基学习器尽可能具有较大的差异。给定一个训练数据集，一种可能的做法是对训练样本进行采样，产生出若干个不同的子集，再从每个数据子集中训练出一个基学习器。这样，由于训练数据不同，我们获得的基学习器可望具有比较大的差异。然而，为获得好的集成，我们同时还希望个体学习器不能太差。如果采样出的每个子集都完全不同，则每个基学习器只用到了一小部分训练数据，甚至不足以进行有效学习，这显然无法确保产生出比较好的基学习器。为解决这个问题，我们考虑使用相互有交叠的采样子集。

3.1 Bagging

Bagging 方法是并行式集成学习方法最著名的代表，基于自助采样法/Bosstrap Sampling。给定包含 \(m\) 个样本的数据集，我们先随机取出一个样本放入采样集中，再把该样本放回初始数据集，使得下次采样时该样本仍有可能被选中，这样，经过 \(m\) 次随机采样操作，我们得到含 \(m\) 个样本的采样集。初始训练集中大约有 63.2% 的样本出现在采样集中。

照这样，我们可采样出 \(T\) 个含 \(m\) 个训练样本的采样集，然后基于每个采样集训练出一个基学习器，再将这些基学习器进行结合。这就是 Bagging 的基本流程。在对预测输出进行结合时，Bagging 通常对分类任务使用简单投票法，对回归任务使用简单平均法。若分类预测时出现两个类收到同样票数的情形，则最简单的做法是随机选择一个，也可进一步考察学习器投票的置信度来确定最终胜者。

Bagging 的算法描述如下：

假定基学习器的计算复杂度为 \(O(m)\)，采样和投票的复杂度为 \(O(s)\)，则 Bagging 的复杂度大致为 \(T(O(m) + O(s))\)，考虑到采样与投票的复杂度 \(O(s)\) 很小，而 \(T\) 通常是一个不太大的常数，因此，训练一个 Bagging 集成与直接使用基学习算法训练一个学习器的复杂度同阶，这说明 Bagging 是一个很高效的集成学习算法。另外，与标准 AdaBoost 只适用于二分类任务不同，Bagging 能不经修改地用于多分类和回归任务。

除此之外，自助采样还可以用于 Bagging 泛化误差的估计。不妨令 \(D_t\) 表示第 \(t\) 个基学习器实际使用的训练样本集，令 \(H^{oob}(x)\) 表示对样本 \(x\) 的包外预测，即仅考虑那些未使用 \(x\) 训练的基学习器在 \(x\) 上的预测，有：

\[H^{oob}(x) = \underset{y\in\mathcal{Y}}{\arg\max}\sum_{t=1}^T \mathbb{1}(h_t(x)=y) \cdot \mathbb{1}(x \notin D_i)\]

则 Bagging 泛化误差的包外估计为：

\[\epsilon^{oob} = \frac{1}{|D|}\sum_{(x,y)\in D}\mathbb{1}(H^{oob}(x) \neq y)\]

除此之外，包外样本还有许多其他用途。例如当基学习器是决策树时，可使用包外样本来辅助剪枝，或用于估计决策树中各结点的后验概率以辅助对零训练样本结点的处理；当基学习器是神经网络时，可使用包外样本来辅助早期停止以减小过拟合风险。

3.2 随机森林

4. 结合策略

5. 多样性

5.1 误差-分歧分解

欲得到泛化性能强的集成，个体学习器应好而不同，

5.2 多样性度量

5.3 多样性增强

• 数据样本扰动：给定初始数据集，可以从中产生出不同的数据子集，再利用不同的数据子集训练出不同的个体学习器。数据样本扰动通常是基于采样法，例如在 Bagging 中使用自助采样，在 AdaBoost 中使用序列采样。数据样本扰动对于神经网络、决策树等易受样本扰动的学习器特别有效。
• 输入属性扰动：
• 输出表示扰动：
• 算法参数扰动：