集成学习（Ensemble¹ Learning）通过构建并结合多个学习器来完成学习任务，有时也被称为多分类器系统（Multi-classifler System）、基于委员会的学习（Committee-based Learning）等。

1 个体与集成

集成学习的基本结构：先产生一组个体学习器（Individual Learner），再用某种策略将它们结合起来。集成中包含的个体学习器数目称为集成的规模。集成模型如下图所示，其中根据个体学习器的不同可将集成分为以下两类：

1. 同质（Homogeneous）集成：个体学习器都属于同一类别（由一个现有的学习算法通过训练数据产生），例如C4.5决策树、BP神经网络等。常将同质集成中的个体学习器称为基学习器（Base Learner），对应的学习算法为基学习算法（Base Learning Algorithm）。
2. 异质（Heterogenous）集成：个体学习器包含多种类型的学习算法，例如既有决策树又有神经网络等。此时可将个体学习器称为组件学习器（Component Learner）。

集成学习通过将多个学习器进行结合，常可获得比单一学习器显著优越的泛化性能。这对弱学习器²（Weak Learner）尤为明显。尽管集成好坏不一的多个学习器总能比只有最差的单一学习器要好一些，但为了胜过最好的单一学习器，集成个体应“好而不同”——个体学习器要有一定的准确性，即性能不能太差，且学习器之间要有一定的多样性（Diversity），即各输出要有足够的差异性。

以二分类任务为例（如下图所示，其中✔️表示分类正确，❌表示分类错误），集成学习的结果采用投票法（见后述）产生，即少数服从多数。

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

\begin{aligned}
P(h_i(\mathbf{x}) \ne f(\mathbf{x}))=\varepsilon
\end{aligned}

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

\begin{aligned}
H(\mathbf{x})=\text{sign}\left( \sum\limits_{i=1}^T h_i(\mathbf{x}) \right)
\end{aligned}

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

\begin{aligned}
P(H(\mathbf{x}) \ne f(\mathbf{x})) & = \sum\limits_{k=0}^{\left \lfloor T/2 \right \rfloor} \binom{T}{k}(1-\varepsilon)^k \varepsilon^{T-k}\\
 & \le \exp \left( -\frac{1}{2}T(1-2\varepsilon)^2 \right)
\end{aligned}

可见，集成器错误率随着基分类器的个数的增加呈指数下降，但前提是基分类器之间相互独立，在实际情形中显然是不可能的，假设有A,B两个分类器，对于某个测试样本，显然有P(A=1\mid B=1)\gt P(A=1)，因为它们是为了解决同一个问题而训练，因此在预测样本时存在着很大的联系。事实上，个体学习器的准确性”“差异性本身就是一对矛盾的变量，准确性高意味着牺牲多样性。因此，产生“好而不同”的个体学习器正是集成学习研究的核心。

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

1. 序列化方法：个体学习器间存在强依赖关系、必须串行生成，例如Boosting。
2. 并行化方法：个体学习器间不存在强依赖关系、可同时生成，例如Bagging和随机森林。

---

2 Boosting

Boosting是一族可将弱学习器提升为强学习器的算法，属于串行式的集成学习算法。该族算法的基本思想为：先从初始训练集训练出一个基学习器，再根据基学习器的表现对训练样本分布进行调整，使得先前基学习器做错的训练样本在后续受到更多关注，然后基于调整后的样本分布来训练下一个基学习器；如此重复进行，直至基学习器数目达到事先指定的值T，最终将这T个基学习器进行加权结合，产生学习器委员会。

设y_i\in \{-1,+1\}，f是真实函数。Boosting族算法最著名的代表是AdaBoost，通常基于加性模型（Additive Model）进行推导，即用基学习器的线性组合

\begin{aligned}
H(\mathbf{x})=\sum\limits_{t=1}^T \alpha_t h_t(\mathbf{x})
\end{aligned}

来最小化指数损失函数（Exponential Loss Function）

\begin{aligned}
\ell_{\exp} (H\mid \mathcal{D})=\mathbb{E}_{\mathbf{x}\sim \mathcal{D}}\left[ \text{e}^{-f(\mathbf{x})H(\mathbf{x})} \right]
\end{aligned}

AdaBoost的基本算法流程如下所示：

• 输入：训练集D=\{ (\mathbf{x}_1,y_1),(\mathbf{x}_2,y_2),\dots,(\mathbf{x}_m,y_m) \}；基学习算法\mathfrak{L}；训练轮数T
• 过程：
  • 初始化样本权值分布\mathcal{D}_1(\mathbf{x})=\dfrac{1}{m}
  • for t=1,2,\dots,T do
    • 基于分布\mathcal{D_t}从数据集D中训练出分类器h_t=\mathfrak{L}(D,\mathcal{D}_t)
    • 估计分类器h_t的误差\varepsilon_t =P_{\mathbf{x}\sim \mathcal{D}_t}(h_t(\mathbf{x})\ne f(\mathbf{x}))
    • if \varepsilon_t \gt 0.5 then break
    • 确定分类器h_t的权重\alpha_t=\dfrac{1}{2}\ln \left( \dfrac{1-\varepsilon_t}{\varepsilon_t} \right)
    • 更新样本分布（其中Z_t为规范化因子，以确保\mathcal{D}_{t+1}是一个分布）

      \begin{aligned}
      \mathcal{D}_{t+1}(\mathbf{x}) &=\frac{\mathcal{D}_t(\mathbf{x})}{Z_t}\times \begin{cases}
      \exp(-\alpha_t), & \text{if }\ h_t(\mathbf{x})= f(\mathbf{x}) \\
      \exp(\alpha_t), & \text{if }\ h_t(\mathbf{x})\ne f(\mathbf{x})
      \end{cases} \\
      & = \frac{\mathcal{D}_t(\mathbf{x})\exp(-\alpha_t f(\mathbf{x}) h_t(\mathbf{x}))}{Z_t}
      \end{aligned}

  • end for
• 输出：H(\mathbf{x})=\text{sign}\left(\sum\limits_{t=1}^T \alpha_t h_t(\mathbf{x}) \right)

可见，AdaBoost的核心步骤就是计算基学习器权重和样本权重分布。证明过程极为繁杂，暂略。

从AdaBoost的算法流程来看，标准的AdaBoost只适用于二分类问题。

Boosting算法要求基学习器能对特定分布的数据进行学习，即每次都更新样本分布权重，通常存在以下两种方法：

1. 重赋权法（Re-weighting）：对每个样本附加一个权重，注意此时涉及到样本属性与标签的计算时均需乘上一个权值。
2. 重采样法（Re-sampling）：适用于无法接受带权样本的基学习算法。根据各样本的权重，对训练数据进行重采样。初始时样本权重相同，即每个样本被采样到的概率相同；每次从N个原始训练样本中按权重有放回采样N个样本作为训练集，计算训练集错误率，再调整权重；重复采样，从而集成多个基学习器。

从偏差-方差分解（见“模型的评估与选择”篇）来看，Boosting算法主要关注降低偏差，每轮迭代都关注训练过程中预测错误的样本，将弱学习提升为强学习器。因此Boosting能基于泛化性能相当弱的学习器构建出很强的集成。

---

3 Bagging

Bagging（Bootstrap Aggregating）是一种并行式的集成学习方法，直接基于自助采样法（Bootstrap sampling）（见“模型的评估与选择”篇之“数据集的划分方法”）：对于包含m个样本的训练集，进行m次有放回的随机采样操作，从而得到m个样本的采样集，这样训练集中约有36.8%的样本未被采到（\lim\limits_{m\mapsto \infty} \left( 1-\dfrac{1}{m} \right)^m\mapsto \dfrac{1}{\text{e}} \approx 0.368）。按相同方式反复进行，可采集出T个包含m个样本的数据集，从而训练出T个基学习器，最终对这T个基学习器的输出进行结合。

在对预测输出进行结合时，Bagging通常对分类任务使用简单投票法，对回归任务使用简单平均法，若分类预测时出现两个类收到同样票数的情形，则最简单的做法是随机选择一个，也可进一步考察学习器投票的置信度来确定最终胜者。基本算法流程如下所示：

• 输入：训练集D=\{ (\mathbf{x}_1,y_1),(\mathbf{x}_2,y_2),\dots,(\mathbf{x}_m,y_m) \}；基学习算法\mathfrak{L}；训练轮数T
• 过程：
  • for t=1,2,\dots,T do
    • h_t=\mathfrak{L}(D,\mathcal{D}_{\text{bs}})，其中\mathcal{D}_{\text{bs}}是自助采样产生的样本分布
  • end for
• 输出：H(\mathbf{x})=\underset{y\in \mathcal{Y}}{\arg \max}\sum\limits_{t=1}^{T} \mathbb{I}(h_t(\mathbf{x})=y)

可见，Bagging主要通过样本扰动来增加基学习器之间的多样性。若基学习器的计算复杂度为O(m)，则Bagging的复杂度为O(m)+O(s)，其中O(s)为采样与投票/平均过程的极小的复杂度，故训练一个Bagging集成与直接使用基学习算法训练一个学习器的复杂度同阶。

与只适用于二分类任务的标准AdaBoost不同，Bagging可直接用于多分类、回归等任务。

自助采样过程还给Bagging带来了另一个优点：由于每个基学习器只使用了初始训练集中约63.2%的样本，剩下约36.8%的样本可用作验证集来对泛化性能进行包外估计（Out-of-bag Estimate）。为此需记录每个基学习器所使用的训练样本。令D_t表示h_t实际使用的训练样本集，H^{\text{oob}}(\mathbf{x})表示对样本\mathbf{x}的包外预测，即仅考虑那些未使用\mathbf{x}训练的基学习器在\mathbf{x}上的预测，有

\begin{aligned}
H^{\text{oob}}(\mathbf{x})= \underset{y\in \mathcal{Y}}{\arg \max}\sum\limits_{t=1}^{T} \mathbb{I}(h_t(\mathbf{x})=y)\cdot \mathbb{I}(\mathbf{x} \notin D_t)
\end{aligned}

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

\begin{aligned}
\varepsilon^{\text{oob}}= \frac{1}{|D|} \sum\limits_{(\mathbf{x},y)\in D} \mathbb{I}(H^{\text{oob}}(\mathbf{x})\ne y)
\end{aligned}

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

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

---

4 随机森林

随机森林（Random Forest，RF）是Bagging的一个扩展变体，以决策树为基学习器。除了Bagging的样本扰动外，RF还引入了一种属性扰动，在决策树的训练过程中引入了随机属性选择：选择划分属性时，先从候选属性集（假定有d个属性）中随机选出一个包含k个属性的子集，再从该子集中选择最优划分属性，一般推荐k=\log_2 d。

由此可见，RF中基学习器的多样性不仅来自样本扰动，还来自属性扰动，这就使得最终集成的泛化性能可通过个体学习器之间差异度的增加而进一步提升。

相比决策树的Bagging集成，RF的起始性能较差（由于属性扰动，基决策树的准确度有所下降），但随着基学习器数目的增多，RF往往会收敛到更低的泛化误差。此外，不同于Bagging中决策树从所有属性集中选择最优划分属性，随机森林只在属性集的一个子集中选择划分属性，因此训练效率更高。

---

5 结合策略

结合策略指在训练完基学习器后，如何将这些基学习器的输出进行结合，产生集成模型的最终输出的方法。

假定集成包含T个基学习器\{h_1,h_2,\dots,h_T\}，其中h_i在示例\mathbf{x}上的输出为h_i(\mathbf{x})。前述几种算法的介绍中已经涉及了部分策略，本节对所有常用结合策略进行详细介绍。

5.1 平均法

对于数值型输出h_i(\mathbf{x}) \in \mathbb{R}的回归问题，最常见的结合策略为平均法（Averaging）：

1. 简单平均法（Simple Averaging）：实为加权平均法中权重w_i=\dfrac{1}{T}的特例

\begin{aligned}
H(\mathbf{x})=\frac{1}{T} \sum\limits_{i=1}^T h_i(\mathbf{x})
\end{aligned}

2. 加权平均法：个体学习器h_i的权重w_i \ge 0，\sum\limits_{i=1}^T w_i=1

\begin{aligned}
H(\mathbf{x})=\sum\limits_{i=1}^T w_ih_i(\mathbf{x})
\end{aligned}

加权平均法可认为是集成学习研究的基本出发点。但由于数据集中样本不充分或存在噪声等原因，大规模集成模型要学习的权重越多，越容易导致过拟合，故加权平均法不一定优于简单平均法。一般而言，在个体学习器性能相差较大时宜使用加权平均法，而在个体学习器性能相差较小时宜使用简单平均法。

5.2 投票法

对于从类别标记集合\{c_1,c_2,\dots,c_N\}中预测出一个标记的分类任务，最常见的结合问题为投票法（Voting）。以下将学习器h_i在样本\mathbf{x}上预测输出表示为一个N维向量(h_i^1(\mathbf{x});h_i^2(\mathbf{x});\dots;h_i^N(\mathbf{x}))，其中h_i^j(\mathbf{x})是h_i在类别标记c_j上的输出，则

1. 绝对多数投票法（Majority Voting，或直接称为Voting）：若某标记得票过半数，则预测为该标记，否则拒绝预测

\begin{aligned}
H(\mathbf{x})=\begin{cases}
 c_j, & \text{if }\ \sum\limits_{i=1}^T h_i^j(\mathbf{x}) \gt 0.5 \sum\limits_{k=1}^N \sum\limits_{i=1}^T h_i^k(\mathbf{x}) \\
 \text{reject}, & \text{otherwise }
\end{cases}
\end{aligned}

2. 相对多数投票法（Plurality Voting）：预测为得票最多的标记，若同时有多个标记获最高票，则从中随机选取一个

\begin{aligned}
H(\mathbf{x})=c_{\underset{j}{\arg \max}\sum_{i=1}^T h_i^j(\mathbf{x})}
\end{aligned}

3. 加权投票法（Weighted Voting）：与加权平均法类似，个体学习器h_i的权重w_i \ge 0，\sum\limits_{i=1}^T w_i=1

\begin{aligned}
H(\mathbf{x})=c_{\underset{j}{\arg \max}\sum_{i=1}^T w_i h_i^j(\mathbf{x})}
\end{aligned}

绝对多数投票法提供了拒绝选项，这在可靠性要求很高的学习任务中是一个很好的机制。同时，对于分类任务，各个基学习器的输出值有以下两种类型：

• 类标记：h_i^j(\mathbf{x})\in \{0,1\}，若h_i将样本\mathbf{x}预测为类别c_j则取值为1，否则为0。使用类标记的投票称为硬投票（Hard Voting）。
• 类概率：h_i^j(\mathbf{x})\in [0,1]，相当于对后验概率P(c_j\mid \mathbf{x})的一个估计。使用类概率的投票称为软投票（Soft Voting）。

一些在产生类别标记的同时也生成置信度的学习器，置信度可转化为类概率使用，一般基于类概率进行结合往往比基于类标记进行结合的效果更好。

注意对于异质集成，其类概率不能直接进行比较，此时需将类概率转化为类标记输出后再进行投票。

5.3 学习法

学习法是一种更高级的结合策略，即学习出一种用于投票的学习器，其中Stacking是学习法的典型代表。以下将个体学习器称为初级学习器，用于结合的学习器称为次级学习器或元学习器（Meta-learner）。

Stacking的基本思想：先从初始数据集（m个样本）训练出T个初级学习器，再将这些初级学习器的输出与该样本的真实标记作为新数据集（m\times T个样本），来训练次级学习器。

Stacking的算法描述如下所示，此处假定初级学习器使用不同学习算法产生（亦可是同质的），即初级集成是异质的：

• 输入：训练集D=\{ (\mathbf{x}_1,y_1),(\mathbf{x}_2,y_2),\dots,(\mathbf{x}_m,y_m) \}；初级学习算法\mathfrak{L}_1,\mathfrak{L}_2,\dots,\mathfrak{L}_T；次级学习算法\mathfrak{L}
• 过程：
  • for t=1,2,\dots,T do
    • 使用初级学习算法\mathfrak{L}_t产生初级学习器h_t=\mathfrak{L}_t(D)
  • end for
  • 生成次级训练集D'=\empty
  • for i=1,2,\dots,m do
    • for t=1,2,\dots,T do
      • z_{it}=h_t(\mathbf{x}_i)
    • end for
    • D'=D' \cup ((z_{i1},z_{i2},\dots,z_{iT}),y_i)
  • end for
  • 在D'上用次级学习算法\mathfrak{L}产生次级学习器h'=\mathfrak{L}(D')
• 输出：H(\mathbf{x})=h'(h_1(\mathbf{x}),h_2(\mathbf{x}),\dots,h_T(\mathbf{x}))

次级学习器的输入属性表示与次级学习算法对Stacking集成的泛化性能有很大影响。有研究表明，采用类概率作为输入属性、选用多响应线性回归（Multi-response Linear Regression，MLR）作为次级学习算法效果较好。

---

6 多样性

在集成学习中，基学习器之间的多样性（Diversity）是影响集成器泛化性能的重要因素。因此增加多样性对于集成学习研究十分重要，一般思路为在学习过程中引入随机性，常见做法如下：

• 数据样本扰动：利用具有差异的数据集来训练不同的基学习器，例如有放回自助采样法。此类做法对决策树、神经网络学习器等不稳定基学习器十分有效，略微改动训练集就会导致学习器显著变动；但像线性学习器、SVM、朴素贝叶斯、K-临近学习器等这类稳定基学习器（Stable Base Learner）对数据样本的扰动不敏感，需要使用其他机制。
• 输入属性扰动：随机选取原空间的一个子空间（Subspace，即属性子集）来训练基学习器，著名的随机子空间（Random Subspace）算法就基于该机制。例如对于随机森林，从初始属性集中抽取子集，再基于每个子集来训练基学习器。但若训练集只包含少量属性，则不宜使用属性扰动。
• 输出表示扰动：此类做法可对训练样本的类标稍作变动，或对基学习器的输出进行转化。ECOC（见前述“多分类学习”）亦基于此类做法进行多分类任务拆解。
• 算法参数扰动：通过随机设置不同的参数，例如在神经网络中，随机初始化权重与随机设置隐含层节点数。

另有误差-分歧分解、多样性度量等领域专门内容，此处暂不做赘述。