集成学习

个体与集成

集成学习（ensemble^[1] learning）通过构建并结合多个学习器来完成学习任务，有时也被称为多分类器系统（multi-classifier system）、基于委员会的学习（committee-based learning）等。

考虑二分类问题 $y \in \left\lbrace -1, 1 \right\rbrace$ 与真实函数 $f$，假定基分类器错误率为 $\epsilon$，即对每个分类器 $h_i$ 有

$$P(h_i(x) \ne f(x)) = \epsilon$$

假设集成通过简单投票法结合了 $T$ 个基分类器，若有超过半数基分类器正确，则集成分类就正确（为简化讨论，假设 $T$ 为奇数）：

$$H(\bm{x}) = \operatorname{sign}\left( \sum_{i=1}^T h_i(\bm{x}) \right)$$

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

$$\begin{aligned} P(H(\bm{x}) \ne f(\bm{x})) &= \sum_{k=0}^{\left\lfloor T / 2 \right\rfloor} \dbinom{T}{k} (1-\epsilon)^{k} \epsilon^{T-k} \\ &\le \exp\left( -\frac{1}{2} T (1-2\epsilon)^2 \right) \end{aligned}$$

证明

令随机变量 $X_i$ 为第 $i$ 个学习器正确的次数，则有 $\mathbb{E}[X_i] = 1 - \epsilon$。

考虑随机变量的总和 $S_T = \displaystyle \sum_{i=1}^{T}X_i$ ，则 $\mathbb{E}[S_T] = (1-\epsilon)T$。

Hoeffding 不等式即^[2]

$$P(S_T - \mathbb{E}[S_T] \le -t) \le \exp\left( -\frac{2t^2}{T} \right)$$

则有

$$\begin{aligned} P(H(\bm{x}) \ne f(\bm{x})) &= P\left(S_T \le \tfrac{T}{2}\right)\\ &= P\left(S_T - \mathbb{E}[S_T] \le -\tfrac{T(1-2\epsilon)}{2}\right)\\ &\le \exp\left( -\tfrac{2 \left( \tfrac{T(1-2\epsilon)}{2} \right)^2}{T} \right)\\ &= \exp\left( -\frac{1}{2} T (1-2\epsilon)^2 \right) \end{aligned}$$

这表明，随着集成中个体分类器数目 $T$ 的增大，集成的错误率将指数级下降，最终趋向于零。

需要注意的是，上面的分析假设了基学习器的误差相互独立。在现实任务中，个体学习器是为解决同一个问题训练出来的，它们显然不可能相互独立。

事实上，个体学习器的「准确性」和「多样性」本身就存在冲突。一般的，准确性很高之后，要增加多样性就需牺牲准确性。如何产生并结合「好而不同」的个体学习器，恰是集成学习研究的核心。

根据个体学习器的生成方式，目前的集成学习方法大致可分为两大类，即

• 个体学习器间存在强依赖关系、必须串行生成的序列化方法
  • 代表：Boosting
• 个体学习器间不存在强依赖关系、可同时生成的并行化方法
  • 代表：Bagging，「随机森林」（Random Forest）

Boosting

Boosting 是一族可将弱学习器提升为强学习器的算法。

这族算法的工作机制类似：先从初始训练集训练出一个基学习器，再根据基学习器的表现对训练样本分布进行调整，使得先前基学习器做错的训练样本在后续受到更多关注，然后基于调整后的样本分布来训练下一个基学习器；如此重复进行，直至基学习器数目达到事先指定的值 $T$，最终将这 $T$ 个基学习器进行加权结合。

Boosting 族算法最著名的代表是 AdaBoost，算法描述如下图所示，其中 $y_i \in \left\lbrace -1, 1 \right\rbrace$，$f$ 是真实函数。

基于「加性模型」的算法推导方式

AdaBoost 算法有多种推导方式，下面是基于「加性模型」（additive model），即基学习器的线性组合的推导。

使用基学习器的线性组合

$$H(\bm{x}) = \sum_{t=1}^{T} \alpha_t h_t(\bm{x})$$

来最小化指数损失函数（exponential loss function）

$$\ell_{\text{exp}}(H \mid \mathcal{D}) = \mathbb{E}_{\bm{x} \sim \mathcal{D}} \left[ \exp\left( -f(\bm{x}) H(\bm{x}) \right) \right]$$

考虑该式对 $H(\bm{x})$ 的偏导，有

$$\dfrac{\partial \ell_{\text{exp}}(H \mid \mathcal{D})}{\partial H(\bm{x})} = -\e^{-H(\bm{x})}P(f(\bm{x}) = 1 \mid \bm{x}) + \e^{H(\bm{x})}P(f(\bm{x}) = -1 \mid \bm{x})$$

令上式为零解得

$$H(\bm{x}) = \dfrac{1}{2} \ln \dfrac{P(f(\bm{x}) = 1 \mid \bm{x})}{P(f(\bm{x}) = -1 \mid \bm{x})}$$

从而有^[3]

$$\begin{aligned} \operatorname{sign}\left( H(\bm{x}) \right) &= \operatorname{sign}\left( \dfrac{1}{2} \ln \dfrac{P(f(\bm{x}) = 1 \mid \bm{x})}{P(f(\bm{x}) = -1 \mid \bm{x})} \right)\\ &= \begin{cases} 1, & \text{if } P(f(\bm{x}) = 1 \mid \bm{x}) > P(f(\bm{x}) = -1 \mid \bm{x})\\ -1, & \text{if } P(f(\bm{x}) = 1 \mid \bm{x}) < P(f(\bm{x}) = -1 \mid \bm{x}) \end{cases}\\ &= \argmax_{y \in \left\lbrace -1, 1 \right\rbrace} P(f(\bm{x}) = y \mid \bm{x}) \end{aligned}$$

这意味着 $\operatorname{sign}\left( H(\bm{x}) \right)$ 达到了贝叶斯最优错误率。换言之，若指数损失函数最小化，则分类错误率也将最小化。

这说明指数损失函数是分类任务原本 0/1 损失函数的「一致的」（consistent）替代函数。由于这个替代函数有更好的数学性质，因此我们用它替代 0/1 损失函数作为优化目标。

在 AdaBoost 算法中，第一个基分类器 $h_1$ 是通过直接将基学习算法用于初始数据分布而得。此后迭代地生成 $h_t, \alpha_t$，当基分类器 $h_t$ 基于分布 $\mathcal{D}_t$ 产生后，该基分类器的权重 $\alpha_t$ 应使得 $\alpha_t h_t$ 最小化指数损失函数

$$\begin{aligned} \ell_{\text{exp}}(\alpha_t h_t \mid \mathcal{D}_t) &= \mathbb{E}_{\bm{x} \sim \mathcal{D}_t} \left[ \exp\left( -f(\bm{x}) \alpha_t h_t(\bm{x}) \right) \right] \\ &= \mathbb{E}_{\bm{x} \sim \mathcal{D}_t}\left[\e^{-\alpha_t} \mathbb{I}(f(\bm{x}) = h_t(\bm{x})) + \e^{\alpha_t} \mathbb{I}(f(\bm{x}) \ne h_t(\bm{x}))\right]\\ &= \e^{-\alpha_t} P_{\bm{x}\sim\mathcal{D}_t}(f(\bm{x}) = h_t(\bm{x})) + \e^{\alpha_t} P_{\bm{x}\sim\mathcal{D}_t}(f(\bm{x}) \ne h_t(\bm{x}))\\ &= \e^{-\alpha_t}(1 - \epsilon_t) + \e^{\alpha_t} \epsilon_t \end{aligned}$$

其中 $\epsilon_t = P_{\bm{x}\sim\mathcal{D}_t}(f(\bm{x}) \ne h_t(\bm{x}))$ 为基分类器 $h_t$ 的错误率。

考虑指数损失函数的导数

$$\dfrac{\partial \ell_{\text{exp}}(\alpha_t h_t \mid \mathcal{D}_t)}{\partial \alpha_t} = -\e^{-\alpha_t}(1 - \epsilon_t) + \e^{\alpha_t} \epsilon_t$$

令上式为零解得

$$\alpha_t = \dfrac{1}{2} \ln \dfrac{1 - \epsilon_t}{\epsilon_t}$$

这也正是上图算法中第 6 行的分类器权重更新公式。

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

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

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

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

于是理想的基学习器

$$\begin{aligned} h_t(\bm{x}) &= \argmin_h \ell_{\text{exp}}(H_{t-1} + h \mid \mathcal{D})\\ &= \argmin_h \mathbb{E}_{\bm{x} \sim \mathcal{D}} \left[ \e^{-f(\bm{x})H_{t-1}(\bm{x})} \left( 1 - f(\bm{x})h(\bm{x}) + \dfrac{1}{2} \right) \right]\\ &= \argmax_h \mathbb{E}_{\bm{x} \sim \mathcal{D}} \left[ \e^{-f(\bm{x})H_{t-1}(\bm{x})} f(\bm{x})h(\bm{x}) \right]\\ &= \argmax_h \mathbb{E}_{\bm{x} \sim \mathcal{D}} \left[ \dfrac{\e^{-f(\bm{x})H_{t-1}(\bm{x})}}{\mathbb{E}_{\bm{x} \sim \mathcal{D}} \left[ \e^{-f(\bm{x})H_{t-1}(\bm{x})} \right]} f(\bm{x})h(\bm{x}) \right] \end{aligned}$$

注意到 $\mathbb{E}_{\bm{x} \sim \mathcal{D}} \left[ \e^{-f(\bm{x})H_{t-1}(\bm{x})} \right]$ 是一个常数。令 $\mathcal{D}_t$ 表示一个分布

$$\mathcal{D}_t(\bm{x}) = \dfrac{\mathcal{D}(\bm{x})\e^{-f(\bm{x})H_{t-1}(\bm{x})}}{\mathbb{E}_{\bm{x} \sim \mathcal{D}} \left[ \e^{-f(\bm{x})H_{t-1}(\bm{x})} \right]}$$

根据数学期望的定义，有

$$\begin{aligned} h_t(\bm{x}) &= \argmax_h \mathbb{E}_{\bm{x} \sim \mathcal{D}_t} [f(\bm{x})h(\bm{x})] \end{aligned}$$

而 $f(\bm{x}), h(\bm{x}) \in \left\lbrace -1, +1 \right\rbrace$，从而有

$$f(\bm{x}) h(\bm{x}) = 1 - 2 \mathbb{I}(f(\bm{x}) \ne h(\bm{x}))$$

则理想的基学习器有

$$h_t(\bm{x}) = \argmin_h \mathbb{E}_{\bm{x} \sim \mathcal{D}_t} [\mathbb{I}(f(\bm{x}) \ne h(\bm{x}))]$$

由此可见，理想的基学习器 $h_t$ 将在分布 $\mathcal{D}_t$ 下最小化分类误差。

因此，弱分类器将基于分布 $\mathcal{D}_t$ 来训练，且针对 $\mathcal{D}_t$ 的分类误差应小于 $0.5$。这在一定程度上类似「残差逼近」的思想。

考虑到 $\mathcal{D}_t$ 和 $\mathcal{D}_{t+1}$ 的关系，有

$$\begin{aligned} \mathcal{D}_{t+1}(\bm{x}) &= \dfrac{\mathcal{D}(\bm{x})\e^{-f(\bm{x})H_{t}(\bm{x})}}{\mathbb{E}_{\bm{x} \sim \mathcal{D}} \left[ \e^{-f(\bm{x})H_{t}(\bm{x})} \right]}\\ &= \dfrac{\mathcal{D}(\bm{x})\e^{-f(\bm{x})H_{t-1}(\bm{x})}\e^{-f(\bm{x})\alpha_t h_t(\bm{x})}}{\mathbb{E}_{\bm{x} \sim \mathcal{D}} \left[ \e^{-f(\bm{x})H_{t}(\bm{x})} \right]}\\ &= \mathcal{D}_t(\bm{x}) \cdot \e^{-f(\bm{x})\alpha_t h_t(\bm{x})} \dfrac{\mathbb{E}_{\bm{x} \sim \mathcal{D}}\left[ \e^{-f(\bm{x})H_{t-1}(\bm{x})} \right] }{\mathbb{E}_{\bm{x} \sim \mathcal{D}}\left[ \e^{-f(\bm{x})H_t(\bm{x})} \right] } \end{aligned}$$

这也正是算法第 7 行的样本分布更新公式。

于是我们从基于加性模型迭代式优化指数损失函数的角度，推导出了 AdaBoost 算法。

Boosting 算法要求基学习器能对特定数据分布进行学习：

• 「重赋权法」（re-weighting）：在训练过程的每一轮中，根据样本分布为每个训练样本重新赋予一个权重；
• 「重采样法」（re-sampling）：对无法接受带权样本的基学习器，可根据样本分布对训练集重新进行采样，再用重采样而得的样本集对基学习器进行训练。

Boosting 算法在训练的每一轮都要检查当前生成的基学习器是否满足基本条件（如上面算法的第 5 行，检查当前基分类器是否比随机猜测好），一旦条件不满足，则当前基学习器即被抛弃，学习过程停止。

在这种情形下，初始设置的学习轮数 $T$ 也许还远未达到，可能导致最终集成中只包含很少的基学习器而性能不佳。

若采用「重采样法」，则可获得「重启动」的机会以避免训练过程过早停止，即在抛弃不满足条件的当前基学习器之后，可根据当前分布重新对训练样本进行采样，再基于新的采样结果重新训练出基学习器，从而使得学习过程可以持续到预设的 $T$ 轮完成。

从偏差-方差分解的角度看，Boosting 主要关注降低偏差，因此 Boosting 能基于泛化性能相当弱的学习器构建出很强的集成。

下面是以决策树桩为基学习器，在西瓜数据集 $3.0 \alpha$ 上运行 AdaBoost 算法，不同规模（size）的集成及其基学习器所对应的分类边界（集成是红色的，基学习器是黑色的）：

Bagging 与随机森林

由第一节可知，欲得到泛化性能强的集成,集成中的个体学习器应尽可能相互独立。虽然「独立」在现实任务中无法做到，但可以设法使基学习器尽可能具有较大的差异。

给定一个训练数据集，一种可能的做法是对训练样本进行采样，产生出若干个不同的子集，再从每个数据子集中训练出一个基学习器。这样，由于训练数据不同，我们获得的基学习器可望具有比较大的差异。

然而，为获得好的集成，我们同时还希望个体学习器不能太差。如果采样出的每个子集都完全不同，则每个基学习器只用到了一小部分训练数据，甚至不足以进行有效学习，这显然无法确保产生出比较好的基学习器。

为解决这个问题，我们可考虑使用相互有交叠的采样子集。

Bagging

Bagging（Bootstrap aggregating）并行式集成学习方法最著名的代表，它直接基于自助采样法：给定包含 $m$ 个样本的数据集，我们先随机取出一个样本放入采样集中，再把该样本放回初始数据集，使得下次采样时该样本仍有可能被选中，这样，经过 $m$ 次随机采样操作，我们得到含小个样本的采样集，初始训练集中有的样本在采样集里多次出现，有的则从未出现。

照这样，我们可采样出 $T$ 个含 $m$ 个训练样本的采样集，然后基于每个采样集训练出一个基学习器，再将这些基学习器进行结合.这就是 Bagging 的基本流程。

在对预测输出进行结合时，Bagging 通常对分类任务使用简单投票法，对即每个基学习器使用相同权重的投票、平均； 回归任务使用简单平均法。

若分类预测时出现两个类收到同样票数的情形，则最简单的做法是随机选择一个，也可进一步考察学习器投票的置信度来确定最终胜者。

Bagging 的算法描述如下图所示：

假定基学习器的计算复杂度为 $O(m)$，则 Bagging 的复杂度大致为 $T\left(O(m) + O(s)\right)$，其中 $O(s)$ 为「采样与投票/平均过程的复杂度」，这个通常很小，而且 $T$ 通常是一个不太大的常数，因此训练一个 Bagging 集成与直接使用基学习算法训练一个学习器的复杂度同阶。这说明 Bagging 是一个很高效的集成学习算法。

另外标准 AdaBoost 只适用于二分类任务，而 Bagging 能不经修改地用于多分类、回归等任务。

由于每个基学习器只使用了初始训练集约 $63.2\%$ 的样本，剩下约 $36.8\%$ 的样本可用作验证集对泛化性能进行「包外估计」（out-of-bag estimate）。

为此需要记录每个基学习器所使用的训练样本，不妨令 $D_t$ 表示 $h_t$ 实际使用的训练样本集，令 $H^{\text{oob}}$ 表示对样本 $\bm{x}$ 的包外预测，即仅考虑那些未使用 $\bm{x}$ 训练的基学习器在 $\bm{x}$ 上的预测，有

$$H^{\text{oob}}(\bm{x}) = \argmax_{y \in \mathcal{Y}} \sum_{t=1}^{T} \mathbb{I}(h_t(\bm{x}) = y) \cdot \mathbb{I}(\bm{x} \notin D_t)$$

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

$$\epsilon^{\text{oob}} = \frac{1}{|D|} \sum_{(\bm{x}, y) \in D} \mathbb{I}(H^{\text{oob}}(\bm{x}) \ne y)$$

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

从偏差-方差分解的角度上看，Bagging 主要关注降低方差，因此它在不剪枝决策树、神经网络等易受样本扰动的学习器上效用更为明显。

随机森林

随机森林（Random Forest, RF）是 Bagging 的一个扩展变体。RF 在以决策树为基学习器构建 Bagging 集成的基础上，进一步在决策树的训练过程中引入了随机属性选择。

具体来说，传统决策树在选择划分属性时，是在当前结点的属性集合（假设有 $d$ 个属性）中选择一个最优属性；而 RF 中，对基决策树的每个结点，先从该结点的属性集合中随机选择一个包含 $k$ 个属性的子集，然后再从这个子集中选择一个最优属性用于划分。

这里的参数 $k$ 控制了随机性的引入程度：若 $k = d$，则基决策树的构建与传统决策树相同；若 $k = 1$，则是随机选择一个属性用于划分。一般情况下推荐值 $k = \log_2 d$。

随机森林简单、容易实现、计算开销小，但同时在很多现实任务中展现出强大的性能，被誉为「代表集成学习技术水平的方法」。

RF 对 Bagging 只做了小改动，但与 Bagging 中基学习器的「多样性」仅通过样本扰动（通过对初始训练集采样）而来不同，RF 中基学习器的多样性不仅来自样本扰动，还来自于属性扰动，这就使得最终集成的泛化性能可通过个体学习器之间的差异度的增加而进一步提升。

RF 的收敛性与 Bagging 相似。

如图所示，RF 的初始性能往往相对较差，特别是在集成中只包含一个基学习器时。因为通过引入属性扰动，RF 中个体学习器的性能往往有所降低。然而随着个体学习器数目的增加，RF 通常会收敛到更低的泛化误差。

RF 的训练效率常优于 Bagging，因为在个体决策树的构建过程中，Bagging 使用的是确定型决策树，在划分属性时要对结点的所有属性进行考察，而 RF 使用的是随机决策树，在划分属性时只需考察一个属性子集。

结合策略

学习器结合可能从下面三个方面带来好处：

• 从统计的方面来看，由于学习任务的假设空间往往很大，可能有多个假设在训练集上达到同等性能，此时若使用单学习器可能因误选而导致泛化性能不佳，结合多个学习器则会减小这一风险；
• 从计算的方面来看，学习算法往往会陷入局部极小，有的局部极小点所对应的泛化性能可能很糟糕，而通过多次运行之后进行结合，可降低陷入糟糕局部极小点的风险；
• 从表示的方面来看，某些学习任务的真实假设可能不在当前学习算法所考虑的假设空间中，此时若使用单学习器则肯定无效，而通过结合多个学习器，由于相应的假设空间有所扩大，有可能学得更好的近。

假定集成包含 $T$ 个基学习器 $\left\lbrace h_1, h_2, \cdots, h_T \right\rbrace$，其中 $h_i$ 在示例 $\bm{x}$ 输出为 $h_i(\bm{x})$。下面介绍几种对 $h_i$ 进行结合的常见策略。

平均法

对数值型输出 $h_i(\bm{x}) \in \R$，最常见的结合策略是使用平均法（averaging）

• 简单平均法（simple averaging）
  • $H(\bm{x}) = \dfrac{1}{T} \displaystyle \sum_{i=1}^T h_i(\bm{x})$
• 加权平均法（weighted averaging）
  • $H(\bm{x}) = \displaystyle \sum_{i=1}^T w_i h_i(\bm{x})$
    • 其中 $w_i$ 为个体学习器 $h_i$ 的权重
    • 通常要求 $w_i \ge 0,\, \displaystyle \sum_{i=1}^T w_i = 1$

加权平均法的权重一般是从训练数据中学习而得，现实任务中的训练样本通常不充分或存在噪声，这将使得学出的权重不完全可靠。尤其是对规模比较大的集成来说，要学习的权重比较多，较容易导致过拟合。

一般而言，在个体学习器性能相差较大时宜使用加权平均法，而在个体学习器性能相近时宜使用简单平均法。

投票法

对分类任务来说，学习器 $h_i$ 将从类别标记集合 $\left\lbrace c_1, c_2, \cdots, c_N \right\rbrace$ 中预测出一个标记，最常见的结合策略是使用投票法（voting）。

为了便于讨论，将 $h_i$ 在样本 $\bm{x}$ 上的预测输出表示为一个 $N$ 维向量 $\left( h_i^1(\bm{x}), h_i^2(\bm{x}), \cdots, h_i^N(\bm{x}) \right)$，其中 $h_i^{j}(\bm{x})$ 表示 $h_i$ 在类别标记 $c_{j}$ 上的输出。

• 绝对多数投票法（majority voting）
  • $H(\bm{x}) = \begin{cases} c_{j}, & \text{if } \sum\limits_{i=1}^T h_i^{j}(\bm{x}) > \dfrac{1}{2}\sum\limits_{k=1}^{N}\sum\limits_{i=1}^{T}h_i^{k}(\bm{x})\\ \text{reject}, & \text{otherwise} \end{cases}$
  • 即若某标记得票过半数，则预测为该标记；否则拒绝预测。
• 相对多数投票法（plurality voting）
  • $H(\bm{x}) = c_{\argmax\limits_{j}\sum_{i=1}^{T}h_i^{j}(\bm{x})}$
  • 即预测为得票最多的标记，若同时有多个标记获最高票，则从中随机选取一个。
• 加权投票法（weighted voting）
  • $H(\bm{x}) = c_{\argmax\limits_{j}\sum_{i=1}^{T}w_ih_i^{j}(\bm{x})}$
  • 与加权平均法类似，通常要求 $w_i \ge 0,\, \displaystyle \sum_{i=1}^T w_i = 1$

标准的多数投票法提供了「拒绝预测」选项，这对于可靠性要求较高的学习任务中是一个很好的机制。

但若学习任务要求必须提供预测结果，则绝对多数投票法将退化为相对多数投票法。在不允许拒绝预测的任务中，绝对多数、相对多数投票法统称为「多数投票法」。

上面的式子没有限制个体学习器输出值的类型，现实任务中常见的 $h_i^{j}(\bm{x})$ 值有：

• 类标记：$h_i^{j}(\bm{x}) \in \left\lbrace 0, 1 \right\rbrace$
  • 若 $h_i$ 将样本 $\bm{x}$ 预测为类别 $c_{j}$ 则取值为 $1$，否则为 $0$。
  • 使用类标记的投票亦称为「硬投票」（hard voting）。
• 类概率：$h_i^{j}(\bm{x}) \in [0, 1]$
  • 相当于对后验概率 $P(c_{j} \mid \bm{x})$ 的一个估计
  • 使用类概率的投票亦称为「软投票」（soft voting）。

不同类型的 $h_i^{j}(\bm{x})$ 不能混用。

对一些能在预测出类别标记的同时产生分类置信度的学习器，其分类置信度可转化为类概率使用。若此类值未进行规范化，例如支持向量机的分类间隔值，则必须使用一些技术等进行「校准」（calibration）后才能作为类概率使用。

虽然分类器估计出的类概率值一般都不太准确，但基于类概率进行结合却往往比直接基于类标记进行结合性能更好。

需注意的是，若基学习器的类型不同，则其类概率值不能直接进行比较；在此种情形下，通常可将类概率输出转化为类标记输出（例如将类概率输出最大的 $h_i^{j}(\bm{x})$ 设为 $1$，其他设为 $0$）然后再投票。

学习法

当训练数据很多时，一种更为强大的结合策略是使用「学习法」，即通过另一个学习器来进行结合。Stacking^[4] 是学习法的典型代表。

Stacking 先从初始数据集训练出初级学习器，然后「生成」一个新数据集用于训练次级学习器。在这个新数据集中，初级学习器的输出被当作样例输入特征，而初始样本的标记仍被当作样例标记。

Stacking 的算法描述如下图所示，这里假定初级学习器使用不同学习算法产生，即初级集成是异质的。

在训练阶段，次级训练集是利用初级学习器产生的，若直接用初级学习器的训练集来产生次级训练集，则过拟合风险会比较大。

因此，一般是通过使用交叉验证或留一法这样的方式，用训练初级学习器未使用的样本来产生次级学习器的训练样本。

以 $k$ 折交叉验证为例，初始训练集 $D$ 被随机划分为 $k$ 个大小相似的集合 $D_{1}, D_{2}, \dots, D_{k}$。令 $D_{j}$ 和 $\bar{D}_{j}=D \setminus D_{j}$ 分别表示第 $j$ 折的测试集和训练集。给定 $T$ 个初级学习算法，初级学习器 $h_{t}^{(j)}$ 通过在 $\bar{D}_{j}$ 上使用第 $t$ 个学习算法而得。对 $D_{j}$ 中每个样本 $\bm{x}_{i}$，令 $z_{i t}=h_{t}^{(j)}\left(\bm{x}_{i}\right)$，则由 $\bm{x}_{i}$ 所产生的次级训练样例的示例部分为 $\bm{z}_{i}=\left(z_{i 1} ; z_{i 2} ; \dots ; z_{i T} \right)$，标记部分为 $y_{i}$。于是，在整个交叉验证过程结束后，从这 $T$ 个初级学习器产生的次级训练集是 $D^{\prime}=\left\{\left(\bm{z}_{i}, y_{i}\right)\right\}_{i=1}^{m}$，然后 $D^{\prime}$ 将用于训练次级学习器。

次级学习器的输入属性表示和次级学习算法对 Stacking 集成的泛化性能有很大影响。有研究表明，将初级学习器的输出类概率作为次级学习器的输入属性，用多响应线性回归（Multi-response Linear Regression, MLR）作为次级学习算法效果较好，在 MLR 中使用不同的属性集更佳。

贝叶斯模型平均（Bayes Model Averaging, BMA）基于后验概率为不同模型赋予权重，可视为加权平均法的一种特殊实现。理论上若数据生成模型恰在当前考虑的模型中，且数据噪声很少，则 BMA 不差于 Stacking；然而在现实应用中，Stacking 通常优于 BMA，因为其鲁棒性比 BMA 更好，而且 BMA 对模型近似误差非常敏感。

多样性

误差-分歧分解

欲构建泛化性能强的集成，个体学习器应「好而不同」。下面进行一个简单的理论分析。

假定用个体学习器 $h_1, h_2, \cdots, h_T$ 通过加权平均法结合产生的集成来完成回归学习任务 $f\colon \R^d \to \R$。对示例 $\bm{x}$，定义学习器 $h_i$ 的分歧（ambiguity）为

$$A(h_i \mid \bm{x}) = (h_i(\bm{x}) - H(\bm{x}))^2$$

则集成的分歧为

$$\begin{aligned} \bar{A}(h \mid \bm{x}) &= \sum_{i=1}^{T} w_i A(h_i \mid \bm{x})\\ &= \sum_{i=1}^{T} w_i (h_i(\bm{x}) - H(\bm{x}))^2 \end{aligned}$$

这里的分歧项，表征了个体学习器在样本 $\bm{x}$ 上的不一致性，即在一定程度上反映了个体学习器的多样性。个体学习器 $h_i$ 和集成 $H$ 的平方误差分别为

$$\begin{aligned} E(h_i \mid \bm{x}) &= (f(\bm{x}) - h_i(\bm{x}))^2\\ E(H \mid \bm{x}) &= (f(\bm{x}) - H(\bm{x}))^2 \end{aligned}$$

令 $\bar{E}(h \mid \bm{x}) = \displaystyle \sum_{i=1}^{T} w_i E(h_i \mid \bm{x})$ 表示个体学习器误差的加权均值，有

$$\begin{aligned} \bar{A}(h \mid \bm{x}) &= \sum_{i=1}^{T} w_i E(h_i \mid \bm{x}) - E(H \mid \bm{x})\\ &= \bar{E}(h \mid \bm{x}) - E(H \mid \bm{x}) \end{aligned}$$

上式对所有样本 $\bm{x}$ 均成立，令 $p(\bm{x})$ 表示样本的概率密度，则在全样本上有

$$\sum_{i=1}^{T} w_i \int A(h_i \mid \bm{x}) p(\bm{x}) \d \bm{x} = \sum_{i=1}^{T} w_i \int E(h_i \mid \bm{x}) p(\bm{x}) \d \bm{x} - \int E(H \mid \bm{x}) p(\bm{x}) \d \bm{x}$$

类似的，个体学习器 $h_i$ 在全样本上的泛化误差和分歧项分别为^[5]

$$\begin{aligned} E_i &= \int E(h_i \mid \bm{x}) p(\bm{x}) \d \bm{x}\\ A_i &= \int A(h_i \mid \bm{x}) p(\bm{x}) \d \bm{x} \end{aligned}$$

集成的泛化误差为

$$E = \int E(H \mid \bm{x}) p(\bm{x}) \d \bm{x}$$

把这三项代入，并令 $\bar{E} = \displaystyle \sum_{i=1}^{T} w_i E_i$ 表示个体学习器泛化误差的加权均值，$\bar{A} = \displaystyle \sum_{i=1}^{T} w_i A_i$ 表示个体学习器的加权分歧值，则有

$$\begin{equation} E = \bar{E} - \bar{A} \label{1} \end{equation}$$

这个式子表明了，个体学习器准确性越高、多样性越大，则集成越好，称为「误差-分歧分解」（error-disagreement decomposition）。

为什么不能直接把 $\bar{E} - \bar{A}$ 作为优化目标来求解？因为现实任务中很难直接对其进行优化：

• 它们定义在整个样本空间上
• $\bar{A}$ 不是一个可直接操作的多样性度量
• 上面的推导过程只适用于回归学习，难以直接推广到分类学习任务上去

多样性度量

多样性度量（diversity measure）是用于度量集成个体中个体分类器的多样性，即估算个体学习器的多样化程度。典型做法是考虑个体分类器的两两相似/不相似性。

给定数据集 $D = \left\lbrace (\bm{x}_i, y_i) \right\rbrace_{i=1}^m$，对二分类任务 $y_i \in \left\lbrace -1, 1 \right\rbrace$，分类器 $h_i, h_{j}$ 的预测结果列联表（contingency table）为

	$h_i = +1$	$h_i = -1$
$h_j = +1$	$a$	$c$
$h_j = -1$	$b$	$d$

基于这个列联表，能给出一些常见的多样性度量：

• 不合度量（disagreement measure）
  • $\mathrm{dis}_{ij} = \dfrac{b+c}{m}$
  • 值域为 $[0, 1]$。值越大则多样性越大。
• 相关系数（correlation coefficient）
  • $\rho_{ij} = \dfrac{ad - bc}{\sqrt{(a+b)(a+c)(c+d)(b+d)}}$
  • 值域为 $[-1, 1]$。若 $h_i, h_{j}$ 无关，则值为 $0$；若 $h_i, h_{j}$ 正相关，则值为正；若 $h_i, h_{j}$ 负相关，则值为负。
• $Q$-统计量（$Q$-statistic）
  • $Q_{ij} = \dfrac{ad - bc}{ad + bc}$
  • 与相关系数 $\rho_{ij}$ 符号相同，且 $|Q_{ij}| \le |\rho_{ij}|$。
• $\kappa$-统计量（$\kappa$-statistic）
  • $\kappa_{ij} = \dfrac{p_0 - p_e}{1 - p_e}$
  • $p_0 = \frac{a+d}{m}$ 为两个分类器 $h_i, h_{j}$ 取得一致的概率
  • $p_e = \frac{(a+b)(a+c) + (c+d)(b+d)}{m^2}$ 为两个分类器 $h_i, h_{j}$ 偶然达成一致的概率。
  • 若分类器 $h_i, h_{j}$ 在 $D$ 上完全一致，则 $\kappa = 1$；若它们仅是偶然达成一致，则 $\kappa = 0$。$\kappa$ 通常取非负值，仅在 $h_i, h_{j}$ 达成一致的概率甚至低于偶然性的情况下取负值。

上面介绍的都是「成对型」（pairwise）多样性度量，可以通过二维图绘制出来。例如下图的「$\kappa$-误差图」，就是将每一对分类器作为图上的一个点，横坐标是这对分类器的 $\kappa$ 值 ，纵坐标是它们的平均误差。

显然，数据点云的位置越高，则个体分类器准确性越低；点云的位置越靠右，则个体学习器的多样性越小。

虽然有很多「多样性」（diversity）的度量，但并没有能被广泛接受的定义。什么是「多样性」仍然是集成学习研究的重要课题。

多样性增强

常用策略

• 数据样本扰动
  • 通常是基于采样法
    • Bagging 中的自助采样
    • AdaBoost 中的序列采样
  • 对数据样本的扰动敏感的基学习器（不稳定基学习器）
    • 如决策树、神经网络等
  • 对数据样本的扰动不敏感的基学习器（稳定基学习器）
    • 如线性学习器、支持向量机、朴素贝叶斯、$k$ 近邻等
• 输入属性扰动
  • 随机子空间算法（random subspace）
    
• 输出表示扰动
  • 翻转法（Flipping Output）：随机改变一些训练样本的标记
  • 输出调制法（Output Smearing）：将分类输出转化为回归输出后构建个体学习器
  • 将原任务拆解为可多个同时求解的子任务
• 算法参数扰动
  • 随机设置不同的参数
    • 如神经网络
  • 对参数较少的算法，可通过将其学习过程中某些环节用其他类似方式代替，从而达到扰动的目的
    • 如决策树的剪枝方式

---

1. 舶来词，源自中古法语词 ensemblée，音标为 /ɑnˈsɑmbəl/。 ↩︎

2. 具体可参见「概率论」笔记。 ↩︎

3. 这里忽略了 $P(f(\bm{x}) = 1 \mid \bm{x}) = P(f(\bm{x}) = -1 \mid \bm{x})$ 的情况。 ↩︎

4. Stacking 本身是一种著名的集成学习方法，且有不少集成学习算法可视为其变体或特例。它也可看作一种特殊的结合策略。 ↩︎

5. 为了简化，用 $E_i, A_i$ 表示 $E(h_i), A(h_i)$。下同，用 $E$ 简化表示 $E(H)$。 ↩︎