本文摘自周志华《机器学习》，部分内容有修改。
个体与集成
集成学习
集成学习(ensemble learning)通过构建并结合多个学习器来完成学习任务，有时也被称为多分类系统(multi-classifier system)、基于委员会的学习(committee-based learning)等。
上图显示出集成学习的一般结构：先产生一组个体学习器(individual learner)，再用某种策略将它们结合起来。个体学习器通常由一个现有的学习算法从训练数据中产生，例如 $\text{C4.5}$ 决策算法、$\text{BP}$ 神经网络算法等。
- 若集成中只包含同种类型的个体学习器，例如“决策树集成”中全是决策树，“神经网络集成”中全是神经网络，这样的集成是同质的(homogeneous)。同质集成中的个体学习器亦称基学习器(base learner)，相应的学习算法称为基学习算法(base learning algorithm)。
- 集成也可以包含不同类型的个体学习器，例如同时包含决策树和神经网络，这样的集成是异质的(heterogenous)。异质集合中的个体学习器由不同的学习算法生成，这时就不再有基学习算法了；相应的，个体学习器一般不称为基学习器，常称为组件学习器(component learner)或直接称为个体学习器。
集成学习的原因
集成学习通过将多个学习器进行结合，常可获得比单一学习器显著优越的泛化性能。这对弱学习器(weak learner)尤为明显，因此集成学习的很多理论研究都是针对弱学习器进行的，而基学习器有时也被直接称为弱学习器。
弱学习器常指泛化性能略优于随机猜测的学习器，例如在二分类问题上精度略高于 $50\%$ 的分类器。但需注意的是，虽然从理论上来说使用弱学习器集成足以获得好的性能，但在实践中出于种种考虑，例如希望使用较少的个体学习器，或是重用关于常见学习器的一些经验等，人们往往会使用比较强的学习器。
在一般经验中，如果把好坏不等的东西掺到一起，那么通常结果会是比最坏的好一些，比最好的坏一些。要获得好的集成性能，个体学习器应该“好而不同”：即个体学习器要有一定的“准确性”，性能至少不差于弱学习器，否则集成可能起到负作用；并且要有多样性(diversity)，学习器之间要具有差异，否则集成可能不起作用。
考虑二分类问题 $y\in{-1,+1}$ 和真实函数 $f$，假设基分类器的错误率为 $\epsilon$，即对每个基分类器 $h_i$ 有：
\[P(h_i(\boldsymbol{x})\ne f(\boldsymbol{x}))=\epsilon\]假设集成通过简单投票法结合 $T$ 个基分类器（假设 $T$ 为奇数），若有超过半数的基分类器正确，则集成分类就正确：
\[H(\boldsymbol{x})=\text{sign}\Bigg(\sum_{i=1}^Th_i(\boldsymbol{x})\Bigg)\]假设基分类器的错误率相互独立，则由 $\text{Hoeffding}$ 不等式可知，集成的错误率为：
\[\begin{align}P(H(\boldsymbol{x})\ne f(\boldsymbol{x}))&=\sum_{k=0}^{\lfloor T/2\rfloor}\dbinom{T}{k}(1-\epsilon)^k\epsilon^{T-k}\\&\le\exp\Bigg(-\frac{1}{2}T(1-2\epsilon)^2\Bigg)\end{align}\]可以看到，随着集成中个体分类器数目 $T$ 的增大，集成的错误率将指数级下降，最终趋向于零。
集成学习的难点
但是上面的分析有一个关键假设：基学习器的误差相互独立。在现实任务中，个体学习器是为解决同一个问题训练出来的，它们显然不可能相互独立。事实上，个体学习器的准确性和多样性本身就存在冲突。一般的，准确性很高之后，要增加多样性就需要牺牲准确性。事实上，如何产生并结合“好而不同”的个体学习器，恰是集成学习研究的核心。
根据个体学习器的生成方式，目前的集成学习方法大致可分为两大类，即：
- 个体学习器之间存在强依赖关系，必须串行生成的序列化方法。这类方法的代表是 $\text{Boosting}$。
- 个体学习器之间不存在强依赖关系，可同时生成的并行化方法。这类方法的代表是 $\text{Bagging}$ 和随机森林(Random Forest)。
Boosting
$\text{Boosting}$ 是一种可将弱学习器提升为强学习器的算法族，它的工作机制类似：先从初始训练集训练出一个基学习器，再根据基学习器的表现对训练样本分布进行调整，使得先前基学习器做错的训练样本在后续受到更多关注，然后基于调整后的样本分布来训练下一个基学习器；如此重复进行，直至基学习器数目达到事先指定的值 $T$，最终将这 $T$ 个基学习器进行加权结合。
$\text{Boosting}$ 族算法最著名的代表是 $\text{AdaBoost}$，算法描述如下所示，其中 $y_i\in{-1,+1}$，$f$ 是真实函数。
输入：训练集 $D={(\boldsymbol{x}_1,y_1),(\boldsymbol{x}_2,y_2),\cdots,(\boldsymbol{x}_m,y_m)}$；基学习算法 $\mathcal{L}$；训练轮数 $T$。
过程：
1: $\mathcal{D}_1(\boldsymbol{x})=1/m$ 初始化样本权值分布
2: $\textbf{for } t=1,2,\cdots,T \textbf{ do}$
3: $\quad h_t=\mathcal{L}(D,\mathcal{D}_t)$ 基于分布 $\mathcal{D}_t$ 从数据集 $D$ 中训练出分类器 $h_t$
4: $\quad \epsilon_t=P_{\boldsymbol{x}\sim\mathcal{D}_t}(h_t(\boldsymbol{x})\ne f(\boldsymbol{x}))$ 估计 $h_t$ 的误差
5: $\quad \textbf{if } \epsilon\gt0.5 \textbf{ then break}$
6: $\quad \alpha_t=\frac{1}{2}\ln\Big(\frac{1-\epsilon_t}{\epsilon_t}\Big)$ 确定分类器 $h_t$ 的权重
7: $\quad \mathcal{D}_{t+1}(\boldsymbol{x})=\frac{\mathcal{D}_t(\boldsymbol{x})}{Z_t}\times\begin{cases}\exp(-\alpha_t),& \text{if } h_t(\boldsymbol{x})=f(\boldsymbol{x})\\exp(\alpha_t),& \text{if } h_t(\boldsymbol{x})\ne f(\boldsymbol{x})\end{cases}=\frac{\mathcal{D}_t(\boldsymbol{x})\exp(-\alpha_t f(\boldsymbol{x})h_t(\boldsymbol{x}))}{Z_t}$
$\quad\quad$更新样本分布，其中 $Z_t$ 是规范化因子，以确保 $\mathcal{D}_{t+1}$ 是一个分布
8: $\textbf{end for}$
输出：$H(\boldsymbol{x})=\text{sign}\big(\sum_{t=1}^T\alpha_th_t(\boldsymbol{x})\big)$
$\text{Boosting}$ 算法要求基学习器能对特定的数据分布进行学习，这可通过重赋权法(re-weighting)实施，即在训练过程的每一轮中，根据样本分布为每个训练样本重新赋予一个权重。对于无法接受带权样本的基学习算法，则可通过重采样法(re-sampling)来处理，即在每一轮学习中，根据样本分布对训练集重新进行采样，再用重采样得到的样本集对基学习器进行训练。一般而言，这两种做法没有显著的优劣差别。
注意，$\text{Boosting}$ 算法在训练的每一轮都要检查当前生成的基学习器是否满足基本条件（例如上面 $\text{AdaBoost}$ 算法的第 5 步，检查当前基分类器是否比随机猜测好），一旦条件不满足，则当前基学习器即被抛弃，学习过程停止。在此情形下，初始设置的学习轮数 $T$ 也许还远未达到，可能导致最终集成中只包含很少的基学习器而性能不佳。
若采用“重采样法”，则可获得“重启动”机会以避免训练过程过早停止，即在抛弃不满足条件的当前基学习器之后，可根据当前分布重新对训练样本进行采样，再基于新的采样结果重新训练出基学习器，从而使得学习过程可以持续到预设的 $T$ 轮完成。
从偏差-方差分解的角度看，$\text{Boosting}$ 主要关注降低偏差，因此 $\text{Boosting}$ 能基于泛化性能相当弱的学习器构建出很强的集成。
Bagging与随机森林
前面我们说过，想要得到泛化性能强的集成，集成中的个体学习器应尽可能相互独立。虽然“独立”在现实任务中无法做到，但是可以设法使基学习器尽可能具有较大的差异。给定一个训练数据集，一种可能的做法是对训练样本进行采样，产生出若干个不同的子集，再从每个数据子集中训练出一个基学习器。这样，由于训练数据不同，我们获得的基学习器可望具有比较大的差异。
然而，为获得好的集成，我们同时还希望个体学习器不能太差。如果采样出的每个子集都完全不同，则每个基学习器都只用到了一小部分训练数据，甚至不足以进行有效学习，这显然无法确保产生出比较好的基学习器。为了解决这个问题，我们可以考虑使用相互交叠的采样子集。
Bagging
$\text{Bagging}$ 是并行式集成学习方法最著名的代表$。\text{Bagging}$ 是由 Bootstrap AGGregatING 缩写而来，从名字即可看出，它直接基于自助采样法(bootstrap sampling)。给定包含 $m$ 个样本的数据集，我们先随机取出一个样本放入采样集中，再把该样本放回初始数据集，使得下次采样时该样本仍可能被选中，这样，经过 $m$ 次随机采样操作，我们得到含 $m$ 个样本的采样集，初始训练集中有的样本在采样集里多次出现，有的则从未出现。可以证明，初始训练集中约有 $63.2\%$ 的样本出现在采样集中。
这样，我们可以采样出 $T$ 个含 $m$ 个训练样本的采样集，然后基于每个采样集训练出一个基学习器，再将这些基学习器进行结合，这就是 $\text{Bagging}$ 的基本流程。在对预测输出进行结合时，$\text{Bagging}$ 通常对分类任务使用简单投票法，对回归任务使用简单平均法。若分类预测时出现两个类收到同样票数的情形，则最简单的做法是随机选择一个，也可进一步考察学习器投票的置信度来确定最终胜者。$\text{Bagging}$ 的算法描述如下所示（$\mathcal{D}_{bs}$ 是自助采样产生的样本分布）：
输入：训练集 $D={(\boldsymbol{x}_1,y_1),(\boldsymbol{x}_2,y_2),\cdots,(\boldsymbol{x}_m,y_m)}$；基学习器算法 $\mathcal{L}$；训练轮数 $T$。
过程：
1: $\textbf{for } t=1,2,\cdots,T \textbf{ do}$
2: $\quad h_t=\mathcal{L}(D,\mathcal{D}_{bs})$
3: $\textbf{end for}$
输出：$H(\boldsymbol{x})=\mathop{\arg\max}\limits_{y\in\mathcal{Y}}\sum_{t=1}^T\mathbb{I}(h_t(\boldsymbol{x})=y)$
假定基学习器的计算复杂度为 $O(m)$，则 $\text{Bagging}$ 的复杂度大致为 $T(O(m)+O(s))$，考虑到采样与投票/平均过程的复杂度 $O(s)$ 很小，而 $T$ 通常是一个不太大的常数，因此，训练一个 $\text{Bagging}$ 集成与直接使用基学习算法训练一个学习器的复杂度同阶，这说明 $\text{Bagging}$ 是一个很高效的集成学习算法。另外，与标准 $\text{AdaBoost}$ 不同，$\text{Bagging}$ 能不经修改地用于多分类、回归等任务。
自助采样过程还给 $\text{Bagging}$ 带来了另一个优点：由于每个基学习器只使用了初始训练集中约 $63.2\%$ 的样本，剩下约 $36.8\%$ 的样本可用作验证集来对泛化性能进行包外估计(out-of-bag estimate)。为此需要记录每个基学习器所使用的训练样本。不妨令 $D_t$ 表示 $h_t$ 实际使用的训练样本集，令 $H^{oob}(\boldsymbol{x})$ 表示对样本 $\boldsymbol{x}$ 的包外预测，即仅考虑那些未使用 $\boldsymbol{x}$ 训练的基学习器在 $\boldsymbol{x}$ 上的预测，有：
\[H^{oob}(\boldsymbol{x})=\mathop{\arg\max}\limits_{y\in\mathcal{Y}}\sum_{t=1}^T\mathbb{I}(h_t(\boldsymbol{x})=y)\cdot\mathbb{I}(\boldsymbol{x}\notin D_t)\]则 $\text{Bagging}$ 泛化误差的包外估计为：
\[\epsilon^{oob}=\frac{1}{|D|}\sum_{(\boldsymbol{x},y)\in D}\mathbb{I}(H^{oob}(\boldsymbol{x})\ne y)\]事实上，包外样本还有许多其他用途。例如当基学习器是决策树时，可以使用包外样本来辅助剪枝，或用于估计决策树中各结点的后验概率以辅助对零训练样本结点的处理；当基学习器是神经网络时，可以使用包外样本来辅助早期停止以减小过拟合风险。
从偏差-方差分解角度看，$\text{Bagging}$ 主要关注降低方差，因此它在不剪枝决策树、神经网络等易受样本扰动的学习器上效用更为明显。
随机森林
随机森林(Random Forest)是 $\text{Bagging}$ 的一个扩展变体。随机森林在以决策树为基学习器构建 $\text{Bagging}$ 集成的基础上，进一步在决策树的训练过程中引入了随机属性选择。具体来说，传统决策树在选择划分属性时是在当前结点的属性集合（假定有 $d$ 个属性）中选择一个最优属性；而在随机森林中，对基决策树的每个结点，先从该结点的属性集合中随机选择一个包含 $k$ 个属性的子集，然后再从这个子集中选择一个最优属性用于划分。这里的参数 $k$ 控制了随机性的引入程度：若令 $k=d$，则基决策树的构建与传统决策树相同；若令 $k=1$，则是随机选择一个属性用于划分；一般情况下，推荐值 $k=\log_2d$。
随机森林简单、容易实现、计算开销小，令人惊奇的是，它在很多现实任务中展现出强大的性能，被誉为“代表集成学习技术水平的方法”。
可以看出，随机森林对 $\text{Bagging}$ 只做了小改动，但是与 $\text{Bagging}$ 中基学习器的“多样性”仅通过样本扰动（通过对初始训练集采样）而来不同，随机森林中基学习器的多样性不仅来自样本扰动，还来自属性扰动，这就使得最终集成的泛化性能可通过个体学习器之间的差异度的增加而进一步提升。
随机森林的收敛性与 $\text{Bagging}$ 相似。如上图所示，随机森林的起始性能往往相对较差，特别是在集成中只包含一个基学习器时。这很容易理解，因为通过引入属性扰动，随机森林中个体学习器的性能往往有所降低。然而，随着个体学习器数目的增加，随机森林通常会收敛到更低的泛化误差。而且随机森林的训练效率常优于 $\text{Bagging}$，因为在个体决策树的构建过程中，$\text{Bagging}$ 使用的是“确定型”决策树，在选择划分属性时要对结点的所有属性进行考察，而随机森林使用的“随机型”决策树则只需考察一个属性子集。
结合策略
学习器结合可能会从三个方面带来好处：
- 从统计的方面来看，由于学习任务的假设空间往往很大，可能有多个假设在训练集上达到同等性能，此时若使用单学习器可能因误选而导致泛化性能不佳，结合多个学习器则会减小这一风险。
- 从计算方面来看，学习算法往往会陷入局部极小，有的局部极小点所对应的泛化性能可能很糟糕，而通过多次运行之后进行结合，可降低陷入糟糕局部极小点的风险。
- 从表示方面来看，某些学习任务的真实假设可能不在当前学习算法所考虑的假设空间中，此时若使用单学习器则肯定无效，而通过结合多个学习器，由于相应的假设空间有所扩大，有可能学得更好的近似。
假定集成包含 $T$ 个基学习器 ${h_1,h_2,\cdots,h_T}$，其中 $h_i$ 在示例 $\boldsymbol{x}$ 上的输出为 $h_i(\boldsymbol{x})$。下面介绍几种对 $h_i$ 进行结合的常见策略。
平均法(averaging)
对数值型输出 $h_i(\boldsymbol{x})\in\mathbb{R}$，最常见的结合策略是使用平均法(averaging)：
-
简单平均法(simple averaging)
\[H(\boldsymbol{x})=\frac{1}{T}\sum_{i=1}^T h_i(\boldsymbol{x})\] -
加权平均法(weighted averaging)
\[H(\boldsymbol{x})=\sum_{i=1}^T w_ih_i(\boldsymbol{x})\]其中 $w_i$ 是个体学习器 $h_i$ 的权重，通常要求 $w_i \ge 0$，$\sum_{i=1}^T w_i=1$。
显然，简单平均法是加权平均法令 $w_i=1/T$ 的特例。加权平均法在集成学习中具有特别的意义，集成学习的各种结合方法都可以视为其特例或变体。加权平均法可以认为是集成学习研究的基本出发点，对给定的基学习器，不同的集成学习方法可视为通过不同的方式来确定基学习器的权重。
加权平均法的权重一般是从训练数据中学习而得，例如估计出个体学习器的误差，然后令权重大小与误差成反比。现实任务中的训练样本通常不充分或存在噪声，这将使得学出的权重不完全可靠。尤其是对规模比较大的集成来说，要学习的权重比较多，较容易导致过拟合。因此，实验和应用均显示出，加权平均法未必一定优于简单平均法。
一般而言，在个体学习器性能相差较大时宜使用加权平均法，而在个体学习器性能相近时宜使用简单平均法。
投票法(voting)
对分类任务来说，学习器 $h_i$ 将从类别标记集合 ${c_1,c_2,\cdots,c_N}$ 中预测出一个标记，最常见的结合策略是使用投票法(voting)。为便于讨论，我们将 $h_i$ 在样本 $\boldsymbol{x}$ 上的预测输出表示为一个 $N$ 维向量 $(h_i^1(\boldsymbol{x});h_i^2(\boldsymbol{x});\cdots;h_i^N(\boldsymbol{x}))$，其中 $h_i^j(\boldsymbol{x})$ 是 $h_i$ 在类别标记 $c_j$ 上的输出。
-
绝对多数投票法(majority voting)
\[H(\boldsymbol{x})=\begin{cases}c_j,&&\text{if }\sum_{i=1}^T h_i^j(\boldsymbol{x}) \gt 0.5 \sum_{k=1}^N\sum_{i=1}^T h_i^k(\boldsymbol{x})\\\text{reject},&&\text{otherwise}\end{cases}\]即若某标记得票数过半数，则预测为该标记；否则拒绝预测。
-
相对多数投票法(plurality voting)
\[H(\boldsymbol{x})=c_{\mathop{\arg\max}\limits_j \sum_{i=1}^T h_i^j(\boldsymbol{x})}\]即预测为得票数最多的标记，若同时有多个标记获得最高票，则从中随机选取一个。
-
加权投票法(weighted voting)
\[H(\boldsymbol{x})=c_{\mathop{\arg\max}\limits_j \sum_{i=1}^T w_ih_i^j(\boldsymbol{x})}\]与加权平均法类似，$w_i$ 是 $h_i$ 的权重，通常 $w_i \ge 0$，$\sum_{i=1}^T w_i=1$。
在现实任务中，不同类型的个体学习器可能产生不同类型的 $h_i^j(\boldsymbol{x})$ 值，常见的有：
- 类标记：$h_i^j(\boldsymbol{x})\in{0,1}$，若 $h_i$ 将样本 $\boldsymbol{x}$ 预测为类别 $c_j$ 则取值为 $1$，否则为 $0$。使用类标记的投票亦称硬投票(hard voting)。
- 类概率：$h_i^j(\boldsymbol{x})\in [0,1]$，相当于对后验概率 $P(c_j\mid\boldsymbol{x})$ 的一个估计。使用类概率的投票亦称软投票(soft voting)。
不同类型的 $h_i^j(\boldsymbol{x})$ 值不能混用。对于一些能在预测出类别标记同时产生分类置信度的学习器，其分类置信度可转化为类概率使用。有趣的是，虽然分类器估计出的类概率值一般都不太准确，但基于类概率进行结合却往往比直接基于类标记进行结合性能更好。注意，若基学习器的类型不同，则其类概率值不能直接进行比较，通常可将类概率转化为类标记（例如将类概率最大的 $h_i^j(\boldsymbol{x})$ 设为 $1$，其他设为 $0$），然后再投票。
学习法
当训练数据很多时，一种更为强大的结合策略是使用“学习法”，即通过另一个学习器来进行结合。$\text{Stacking}$ 是学习法的典型代表。这里我们把个体学习器称为初级学习器，用于结合的学习器称为次级学习器或元学习器(meta-learner)。
$\text{Stacking}$ 本身是一种著名的集成学习方法，且有不少集成学习算法可视为其变体或特例。它也可看作一种特殊的结合策略。
$\text{Stacking}$ 先从初始数据集训练出初级学习器，然后“生成”一个新数据集用于训练次级学习器。在这个新数据集中，初级学习器的输出被当做样例输入特征，而初始样本的标记仍被当作样例标记。$\text{Stacking}$ 的算法描述如下，这里假定初级学习器使用不同的学习算法产生，即初级集成是异质的（初级学习器也可是同质的）。
输入：训练集 $D={(\boldsymbol{x}_1,y_1),(\boldsymbol{x}_2,y_2),\cdots,(\boldsymbol{x}_m,y_m)}$；初级学习算法 $\mathcal{L}_1,\mathcal{L}_2,\cdots,\mathcal{L}_T$；次级学习算法 $\mathcal{L}$。
过程：
1: $\textbf{for } t=1,2,\cdots,T \textbf{ do}$
2: $\quad h_t=\mathcal{L}_t(D)$ 使用初级学习算法 $\mathcal{L}_t$ 产生初级学习器 $h_t$
3: $\textbf{end for}$
4: $D’=\varnothing$ 生成次级训练集
5: $\textbf{for }i=1,2,\cdots,m \textbf{ do}$
6: $\quad \textbf{for } t=1,2,\cdots,T \textbf{ do}$
7: $\quad \quad z_{it}=h_t(\boldsymbol{x}_i)$
8: $\quad \textbf{end for}$
9: $\quad D’=D’\bigcup((z_{i1},z_{i2},\cdots,z_{iT}),y_i)$
10: $\textbf{end for}$
11: $h’=\mathcal{L}(D’)$ 在 $D’$ 上用次级学习算法 $\mathcal{L}$ 产生次级学习器 $h’$
输出：$H(\boldsymbol{x})=h’(h_1(\boldsymbol{x}),h_2(\boldsymbol{x}),\cdots,h_T(\boldsymbol{x}))$
在训练阶段，次级训练集是利用初级学习器产生的，若直接用初级学习器的训练集来产生次级训练集，则过拟合风险会比较大；因此，一般通过使用交叉验证或留一法这样的方式，用训练初级学习器未使用的样本来产生次级学习器的训练样本。
以 $k$ 折交叉验证为例，初始训练集 $D$ 被随机划分为 $k$ 个大小相似的集合 $D_1,D_2,\cdots,D_k$。令 $D_j$ 和 $D_\text{others}=D \backslash D_j$ 分别表示第 $j$ 折的测试集和训练集。给定 $T$ 个初级算法，初级学习器 $h_t^{(j)}$ 通过在 $D_\text{others}$ 上使用第 $t$ 个学习算法而得。对 $D_j$ 中每个样本 $\boldsymbol{x}_i$，令 $z_{it}=h_t^{(j)}(\boldsymbol{x}_i)$，则由 $\boldsymbol{x}_i$ 所产生的次级训练样例的特征部分为 $\boldsymbol{z}_i=(z_{i1},z_{i2},\cdots,z_{iT})$，标记部分为 $y_i$。于是，在整个交叉验证结束后，从这 $T$ 个初级学习器产生的次级训练集是 $D’={(\boldsymbol{z}_i,y_i)}_{i=1}^m$，然后 $D’$ 将用于训练次级学习器。
次级学习器的输入属性表示和次级学习算法对 $\text{Stacking}$ 集成的泛化性能有很大影响。有研究表明，将初级学习器的输出类概率作为次级学习器的输入属性，用多响应线性回归(Multi-response Linear Regression, MLR)作为次级学习算法效果较好，在 $\text{MLR}$ 中使用不同的属性集更佳。
MLR 是基于线性回归的分类器，它对每个类分别进行线性回归，属于该类的训练样例所对应的输出被置为 $1$，其他类置为 $0$；测试样例将被分给输出值最大的类。
本文摘自周志华《机器学习》，部分内容有修改。