资料来源参考：

清华大学出版社 周志华 《机器学习》 第八章

清华大学出版社 李航 《统计学习方法》 第八章

引子

我们知道，想得到一个泛化性能强的集成学习器，不仅需要个体学习器的准确度足够高，还需要个体学习器之间尽可能的相互独立。尽管“独立”再现实任务中不是那么容易做到，但也还是有方法可以让基学习器之间保持较大的差异。一种比较可行的方法，就是在给定一个数据集后，对训练样本采样产出若干个不同的子集，再从每个子集中训练处一个基学习器。这样，由于数据集之间的差异，基学习器之间也会有比较大的差异。

但是，另一方面，我们又不希望个体学习器的性能太差，因为如果采样出的每个子集都完全不同，则每个基学习器都只学习了一小部分数据，甚至有时候还不足以进行有效地学习，这就无法保证产出效果好的基学习器。因此，为了解决这个问题，我们可以考虑使用相互有交叠的子集。

Bagging

基本思路

Bagging（Bootstrap AGGregatING）是并行化集成学习方法的著名代表。它直接基于自助采样法（bootstrap sampling）进行学习，即假设给定包含m个样本的数据集，我们先随机取出一个样本放入采样集中，再把该样本放回初始数据集，使得下次采样时该样本仍有可能被选中，经过m次这种随机采样操作之后，我们就可以得到含m个样本的采样集，并且，我们知道初始训练集有的采样样本会再采样集里多次出现，有的则从未出现。我们可以计算得到，初始训练集中约有63.2%的样本出现在采样集中（换句话说，就是有约36.8%的样本没有被采样，关于这个数字的计算我们将会在这章之后的部分讨论）

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

在对预测输出进行结合时，Bagging通常对分类任务采用简单投票法（即每个基学习器使用相同权重的投票方式决出输出类型），对回归任务使用简单平均法（即每个基学习器的输出结果的平均）。若分类预测时发现有两个类收到的票数是一样的，最简单的办法就是随机选取其中一个，又或者是通过考察基学习器的确信度来决定要选择的类。

Bagging算法

Bagging的具体算法如图：

其中$D_{bs}$是自助采样产生的样本分布。

性能评估

假设基学习器的计算复杂度为$O(m)$，那么Bagging的复杂度大致为$T(O(m)+O(s))$，考虑到采样与投票/平均过程的复杂度$O(s)$很小，而且T通常也是一个不算多大的常数，因此我们可以认为训练一个Bagging集成与直接使用基学习器算法训练一个学习器的复杂度同阶（复杂度同阶不代表运行的时间是一样的），换句话说，这证明了Bagging是一个高效的集成学习算法。另外，与标准的AdaBoost算法仅适用于二分类任务的情况不同（若要处理多分类或者回归任务，AdaBoost需要进行一些修改；目前已有适用的变体算法），Bagging不需要经过修改也可以用于多分类、回归等任务。

自助采样过程还给Bagging带来了另一个优点：由于初始训练集中仅有63.2%的样本被一个基学习器使用，因此剩下约36.8%的样本还可以用作验证集来对泛化性能进行包外评估（out-of-bag estimate）。要利用这个效果，我们就需要记录每个基学习器所使用的训练样本。

设$D_t$表示$h_t$实际使用的样本训练集，令$H^{oob}(x)$表示对样本x的包外预测，也即仅考虑那些未使用样本x训练的基学习器在该样本x上的预测，对此我们有：

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

包外样本在不同的情况下还有不同的用处，例如当基学习器是决策树时，就可以使用包外样本辅助剪枝，或者是用于估计决策树中各节点的后验概率以辅助对零训练样本节点的处理。

从偏差-方差的角度来看，Bagging主要关注降低方差，正因此，它在不剪枝决策树、神经网络等易受样本扰动（后面我们再对这个词进行讨论）的学习器上效用更加明显。

我们来看一个以基于信息增益划分的决策树为基学习器，在西瓜数据集3.0α上运行Bagging算法，不同规模的集成及其基学习器所对应的分类边界的图例：

随机森林

基本思路

随机森林（Random Forest ，简称RF）是Bagging的一个扩展变体。

RF是以决策树为基学习器构建的Bagging集成。但不同的是，RF的基学习器决策树引入了随机属性选择：

对于一个传统的决策树，我们对它的节点的每一次划分都会从当前节点的属性集合中（假设有d个属性）选择一个最优属性进行划分；而在RF中，对决策树的每个节点我们会先从节点包含的d个属性中随机的挑选出包含k个属性的子集，再从这个子集中选择一个最优的属性用于划分，参数k控制了随机性的引入程度：若k=d，则基决策树等同于传统决策树；若k=1，则基决策树的每个节点都是随机选择一个属性用于划分。一般来说，$k=log_2d$是最适合的值。

性能评估

随机森林的实现非常简单，并且计算开销很小，更令人惊奇的是，它在很多现实任务中也能展现出强大的性能，甚至被誉为“代表集成学习技术水平的方法”。

随机森林对Bagging仅做出了一点小小的改动（或许会认为是对传统决策树算法的改动？但是这个改动确实也得基于Bagging才有意义，所以说是基于Bagging的改动是严谨的），但是与Bagging中基学习器的“多样性”仅通过样本扰动（通过对初始训练集采样）体现不同，随机森林中基学习器的多样性不仅来自于样本扰动，还来自属性扰动，这也使得最终集成的泛化性能可通过个体学习器之间的差异度的提升而进一步提高。

随机森林的收敛性类似于Bagging，如下图所示，随机森林的其实性能往往相对较差，特别是当集成中仅包含一个基分类器时（显然，这是因为样本扰动加上属性扰动使得个体学习器的随机性相较于Bagging更高导致的），但是，随着个体学习器数目的增加，随机森林往往会收敛到更低的泛化误差：

有趣的是，随机森林的训练效率通常会比Bagging更高，因为在个体决策树的构建过程中，Bagging使用的“确定性”的决策树要对每一个节点的所有属性进行考察，使得计算开销比RF中的“随机性”决策树要大不少。

结合策略

Boosting和Bagging是学习器结合的常用策略，现在我们来从更广泛的一个角度讨论一下结合策略。

优点

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

1. 首先，从统计的方面来看，由于学习任务的假设空间往往很大，可能有多个假设（hypothesis，或说输出函数）在训练集上达到同等性能，此时若仅采用单个学习器可能会因为误选而导致泛化性能不佳，因此若能结合多个学习器往往可以有效地降低这种风险
2. 从计算的角度看，单个学习算法很容易会在实际问题中陷入局部最优解，有的局部极小点对应的泛化性能可能会很糟糕。若是能通过多次运行之后将多个学习器结合，可以降低学习算法陷入糟糕局部极小点的风险
3. 从表示的方面来看，某些学习任务的真实假设可能不在当前学习算法所考虑的假设空间中（例如我们曾在支持向量机中遇到过的非线性问题），此时单学习器不具有解决这个问题的能力。而通过结合多个学习器，由于相应的假设空间有所扩大，就有可能学得更好的近似解

我们可以从下面这副图中比较直观地观察到学习器结合带来的三个好处：

假设集成包含T个基学习器$\{h_1,h_2,...,h_T\}$，其中$h_i$在样本x上的输出为$h_i(x)$，接下来我们介绍几种对$h_i$进行结合的常见策略。

平均法

对数值型输出$h_i(x)∈R$，最常见的结合策略就是使用平均法（averaging）:

• 简单平均法（simple averaging）

• 加权平均法（weighted averaging）

其中$w_i$是个体学习器$h_i$的权重，通常要求$w_i≥0.\sum^T_{i=1}w_i=1$

（Breiman[1996b]在研究Stacking回归时发现，必须使用非负权重才能确保集成性能优于单一最佳个体学习器，因此在集成学习中一般对学习器的权重施以非负约束）

我们可以看出，加权平均法的特例就是简单平均法。在二十世纪五十年代，加权平均法就已被广泛使用[Markowitz,1952],[Perrone and Cooper,1993]正式将其用于集成学习。集成学习中的各种结合方法实际上都可以看作是它的特例或者变体。事实上，加权平均法可以认为是集成学习研究的基本出发点。

简单平均法看起来似乎性能不如加权平均法，但事实上，由于加权平均法的权重一般是直接从训练数据中习得（例如估计出个体学习器的误差，然后令权重大小与误差大小成反比），而现实任务中的训练数据集又往往不够充分或者包含噪音，尤其是对于规模较大的集成来说，要学习的权重也比较多，会比较容易导致过拟合。

因此，实验和应用均表明，加权平均法未必就一定强于简单平均法。一般而言，在个体学习器性能差异较大时宜使用加权平均法，而在个体学习器性能相近时使用简单平均法。

投票法

对分类任务来说，学习器$h_i$将从类别标记集合$\{c_1,c_2,...,c_N\}$中预测出一个标记（label），最常见的集合策略就是使用投票法（voting）。为了方便讨论，我们假设$h_i$在样本x上的预测输出表示为一个N维向量$(h_i^1(x);h^2_i(x);...;h^N_i(x))$，其中$h_i^j(x)$是$h_i$在类别标记$c_j$上的输出。

• 绝对多数投票法（majority voting）

即若某类标记得票数超过半数，则预测为该类别，否则拒绝预测。

• 相对多数投票法（plurality voting）

即若某类标记得票数在所有类别的得票数中最多，就预测为该类，若有多个类别一样多，就随机预测一个。

（它与绝对多数投票法不同的有，绝对多数投票法可以做出“不预测”的决定，但是相对多数投票法必然会预测出一个结果）

• 加权投票法（weighted voting）

与加权平均法类似，$w_i$是$h_i$的权重，通常$w_i≥0,\sum^T_{i=1}w_i=1$ 。

标准的绝对多数投票法提供了“拒绝预测”的选项，这在对可靠性要求比较高的学习任务中是一个很好的机制。但若学习任务要求必须提供预测结果，绝对多数投票法就可以退化为相对多数投票法。因此，我们在不允许拒绝预测的任务中，绝对多数、相对多数投票法统称为“多数投票法”（英文术语中有时候称majority voting，有时候称voting）。

在现实任务中，我们还需要给不同类型的个体学习器规定输出格式。因为我们知道，不同类型的个体学习器可能会产生不同类型的$h^j_i(x)$值，常见的有：

• 类标记：$h^j_i(x)∈\{0,1\}$，若$h_i$将样本x预测为类别$c_j$则取值为1，否咋为0。这种使用类标记的投票也称作硬投票（hard voting）。
• 类概率：$h^j_i(x)∈[0,1]$，相当于是对后验概率$P(c_j\mid x)$的一个估计。使用类概率的投票亦称为软投票（soft voting）。

不同类型的$h^j_i(x)$值不能混用。

对一些能在预测出类别标记的额同时产生分类置信度的学习器（像是，支持向量机），其分类置信度可以转化为类概率使用。若这类值未进行规范化，像是支持向量机的分类间隔值，就必须使用一些技术如Platt缩放（Platt scailing）、等分回归（isotonic regression）等进行“校准”（calibration）后才能作为类概率使用。（这些暂时不讨论）

尽管分类器估计出的类概率值一般都不太准确（？），但基于类概率进行结合往往要比直接基于类标记进行结合的性能更好。需注意的是，若基学习器的类型不同，其类概率值之间是无法进行比较的；在这种情况下，通常可以将类概率转化为类别标记输出（例如将类概率最大的$h_i^j(x)$设为1，其它设为0）然后再投票。

学习法

当训练数据很庞大时，一种更为强大的结合策略就是使用学习法，即通过另一个学习器来进行结合。Stacking就是学习法的典型代表。在这里，我们将个体学习器称为初级学习器，用于结合的学习器称为次级学习器或元学习器（meta-learner）。

Stacking算法

Stacking先从初始数据集训练出初级学习器，然后“生成”一个新数据集用于训练次级学习器。在这个新数据集中，初级学习器的输出被当作是样例的输入特征，而初始样本的标记仍然被当作样例标记。上图是Stacking算法的结构描述图，在上图中我们假定初级学习器使用不同学习算法产生，也即是说初级集成是异质的（初级学习器也可以是同质的）。

在训练阶段，次级训练集是利用初级学习器产生的，若是直接用初级学习器的训练集来产生次级训练集，则会有较大的过拟合风险；因此，一般我们会用交叉验证或者留一法这样的方式，用训练初级学习器未使用的样本来产生次级学习器的训练样本。

以k折交叉验证为例，初始训练集D被随机划分为k个大小相似的集合$D_1,...,D_k$，令$D_j$和$\bar{D}_j=D / D_j$分别表示第j折的测试集和训练集。假设我们有T个初级学习算法，初级学习器$h_t^{(j)}$通过在$\bar{D}_j$上使用第t个学习算法得到。对$D_j$中每个样本$x_i$，令$z_{it}=h_t^{(j)}(x_i)$，则由$x_i$所产生的次级训练样例的实例部分为$z_i=(z_{i1};z_{i2};...;z_{iT})$，标记部分为$y_i$。于是，在整个交叉验证过程结束后，从这T个初级学习器产生的次级训练集是$D'=\{(z_i,y_i)\}^m_{i=1}$，然后$D'$将用于训练那次级学习器。

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

从名字可以看出来，MLR是基于线性回归的分类器，它对每个类分别进行线性回归，属于该类的训练样本所对应的输出被置为1，其他类置为0；测试样本将被分给输出值最大的类。

贝叶斯模型平均（Bayes Model Averaging，BMA）基于后验概率来为不同模型赋予权重，可视为加权平均法的一种特殊实现。Clarke[2003]对Stacking和BMA进行了比较，理论上说，若数据生成模型恰好在当前考虑的模型中，且数据噪声很少，则BMA不比Stacking差；然而，在现实应用中我们无法保证数据生成模型一定在当前考虑的模型中，甚至可能难以用当前考虑的模型来进行近似，因此，Stacking通常优于BMA，因为其鲁棒性（Robust）（或说健壮性）比BMA更好，而且BMA对模型近似误差非常敏感。

多样性

我们曾讨论过，要构建泛化能力强的集成，个体学习器应“好而不同”。现在我们就来对其做一个简单的理论分析。

误差-分歧分解

假设我们用个体学习器$h_1,h_2,...,h_T$通过加权平均法结合产生的集成来完成回归学习任务$f:R^d\rightarrow R$。对样本x，定义学习器$h_i$的分歧（ambiguity）为：

则集成的“分歧”是：

（即所有个体学习器与集成的分歧之和）

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

令$\bar{E}(h\mid x)=\sum^T_{i=1}w_i·E(h_i\mid x)$表示个体学习器误差的加权均值，对此我们有：

即集成的分歧可以由个体学习器误差的加权均值与集成H的平方误差的差得到。

这个式子对所有的样本x均成立，因此，如果我们假设$p(x)$表示样本的概率密度，则在全样本上有：

类似地，个体学习器$h_i$在全样本上的泛化误差和分歧项分别为（这里$E_i,A_i$是$E(h_i),A(h_i)$的简化表示）：

集成的泛化误差（$E(H)$由$E$简化表示）：

将$E_i,A_i,E$待会到式子（8.32）中，再令$\bar{E}=\sum^T_{i=1}w_iE_i$表示个体学习器泛化误差的加权均值，$\bar{A}=\sum^T_{i=1}w_iA_i$表示个体学习器的加权分歧值，可以得到：

这个简洁明了的式子就是我们希望得到的结果，它明确的表示：个体学习器准确性越高，多样性越大，集成就越好。这个分析首先由Krogh and Vedelsby [1995]给出，被称为误差-分歧分解（error-ambiguity decomposition）

我们或许会联想到有些学习算法是通过最小化误差来求解模型的，这个时候我们又有了一个误差的表达式，是否可以通过最小化这个表达式的值来最小化误差呢？答案是否定的，因为在现实任务中不仅由于这个表达式是定义在整个样本空间上的，还由于$\bar{A}$不是一个可以直接操作的多样性度量，它尽在集成构造好之后才能进行估计。

还有一点需要注意的就是，上面的推导方式仅适用于回归学习，难以直接推广到分类学习的任务中。（一部分原因可能是因为只有加权平均法相关的连续值能够体现分歧和误差的量度）

多样性度量

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

给定数据集$D=\{(x_1,y_1),...,(x_m,y_m)\}$，对二分类任务，$y_i∈\{-1,+1\}$，分类器$h_i$与$h_j$的预测结果列联表（contingency table）（这部分内容我们将在之后的混淆矩阵中详细讨论，现在我们可以先将其类比为卡方检验）为：

其中a表示$h_i$与$h_j$均预测为正类的样本数目；b,c,d含义由此类推，$a+b+c+d=m$。基于这个列联表，下面给出一些常见的多样性度量：

不合度量（disagreement measure（看英文似乎更像不“和”度量？））

式中$dis_{ij}$的值域为$[0,1]$。值越大则多样性越大（分歧越大）

相关系数（correlation coefficient）

式中$ρ_{ij}$的值域为$[-1,1]$，如果$h_i$与$h_j$无关，则值为0，若$h_i$与$h_j$为正相关则值为正，负相关则为负。

Q-统计量（Q-statistic）

上式$Q_{ij}$的符号与相关系数$ρ_{ij}$的符号相同，且$\mid Q_{ij}\mid≤\mid ρ_{ij}\mid$

k-统计量（k-statistic）

其中$p_1$是两个分类器取得一致的概率；$p_2$是两个分类器偶然达成一致的概率，它们可由数据集D估算：

（我相信这个时候我们都对$p_2$究竟为什么这样算感到很疑惑，但这个我们最好之后再做讨论）

若分类器$h_i$与$h_j$在D上完全一致，则$k=1$；若它们也仅是偶然达成一致，则$k=0$。通常来说k为非负值，仅在$h_i$与$h_j$达成一致的概率低于偶然性的情况下取负值。

以上我们介绍的都是成对型（pairwise）多样性度量，我们可以用一个二维图将它们表示出来。

著名的“k-误差图”就是i将每一对分类器作为图上的一个点，横坐标表示该对分类器的k值，纵坐标表示该对分类器的平均误差，做出的二维图。如下图这个两例子：

我们可以看出来，点越靠上说明个体分类器准确性越低（因为误差越大），越靠右说明个体学习器的多样性越小（因为达成一致的概率越高）

增强多样性

在了解如何度量多样性后，我们可以了解一下如何加强算法的多样性。

一般常见的加强集成学习的多样性的方法是在学习过程中引入随机性，在这之中，常见的做法主要是对数据样本、输入属性、输出表示、算法参数进行扰动。

数据样本扰动

给定初始数据集，可以从中产出不同的数据子集，再利用不同的数据子集训练处不同的个体学习器。数据样本扰动通常是基于采样法（像Bagging中使用的自助采样法，AdaBoost中的序列采样）。此类做法通常简单高效使用广，对很多常见的基学习器，像决策树，神经网络等，训练样本稍加变化就会打字学习器有显著变动，而数据样本扰动法就对这样的不稳定基学习器很有效。

然而，也有一些基学习器对数据样本的扰动不敏感，像线性学习器（线性回归，逻辑回归）、支持向量机、朴素贝叶斯、k近邻学习器等等，这样的基学习器我们就统称为稳定基学习器（stable base learner），对此类基学习器进行集成往往需要使用输入属性扰动或者其它扰动机制。

输入属性扰动

训练样本通常由一组属性描述，不同的子空间（subspace，即属性子集；子空间一般指从初始的高维属性空间投影产生的低维属性空间。描述低维属性空间的属性是通过初始属性（高维属性空间中的属性特征）投影变换而得，有时候未必是初始属性）提供了观察数据的不同视角。显然，从不同子空间训练出的个体学习器必然有所不。著名的随机子空间（random subspace）算法就依赖于输入属性扰动，该算法从初始属性集中抽取出若干个属性子集，再基于每个属性子集训练一个基学习器，其算法结构如图：

对包含大量冗余属性的数据，在子空间中训练个体学习器不仅能产生多样性大的个体，还会因为属性数的减少而大幅节省时间开销，同时，由于冗余属性多，减少一些属性后训练出的个体学习器也不至于太差。

但是如果数据仅包含少量属性，或者冗余属性很少，则不宜使用输入属性扰动法。

输出表示扰动

这种方法就是通过对输出内容进行操作来增强多样性。像翻转法（Flipping Output）就是随机改变一些训练样本的标记，这种是通过对训练样本的类标记做变动达到目的；还可以对输出表示转化，像输出调制法（Output Smearing）就是将分类输出转化为回归输出后构建个体学习器；还可以将原任务拆解为多个可同时求解的子任务，像ECOC法（详情之后再讨论，或查阅西瓜书3.5节）就是利用纠错输出码将多分类任务拆解为一系列二分类任务来训练基学习器。

算法参数扰动

基学习算法往往需要我们设置一些参数（超参数），通过随机设置不同的参数，往往也可以产生差别较大的个体学习器。

像是负相关法（Negative Correlation），就显式地通过正则化项来强制个体神经网络使用不同的参数。对参数较少的算法，可以通过将其学习过程中某些环节用其它类似方式代替，从而达到扰动的目的。例如将决策树使用的属性选择机制替换成其它的属性选择机制（像是将信息增益替换成基尼系数）。值得一提的是，我们往往会在使用单一学习器时使用交叉验证等方法来确定参数值，这事实上已经使用了不同的参数训练出多个学习器，只不过在使用单一学习器时我们只挑选表现最好的那个，而集成学习会把这些学习器都利用起来；由此我们也可以发现，集成学习的实际计算开销并不会比使用单一学习器大多少。

不同的多样性增强机制是可以同时使用的，像是随机森林就是同时加入了数据样本扰动和输入属性扰动。