集成学习
原理
8.1 个体与集成
- 集成学习(ensemble learning) 通过构建并结合多个学习器来完成学习任务，有时也被称为多分类器系统(multi-classifier system)、基于委员会的学习(committee-based learning)等。
- 先产生一组“个体学习器” (individual learner)，再用某种策略将它们结合起来。个体学习器通常由一个现有的学习算法从训练数据产生，例如决策树算法、BP神经网络算法等，此时集成中只包含同种类型的个体学习器，例如“决策树集成”中全是决策树，“神经网络集成”中全是神经网络，这样的集成是“同质”的(homogeneous)。同质集成中的个体学习器亦称“基学习器”(base learner)，相应的学习算法称为“基学习算法”(base learning algorithm)。集成也可包含不同类型的个体学习器，例如同时包含决策树和神经网络，这样的集成是“异质”的(heterogenous)。异质集成中的个体学习器由不同的学习算法生成，这时就不再有基学习算法；相应的，个体学习器一般不称为基学习器，常称为“组件学习器”(component learner)或直接称为个体学习器。
- 集成学习通过将多个学习器进行结合，常可获得比单一学习器显著优越的泛化性能。这对“弱学习器”(weak learner)尤为明显，因此集成学习的很多理论研究都是针对弱学习器进行的，而基学习器有时也被直接称为弱学习器。弱学习器常指泛化性能略优于随机猜想的学习器。但需注意的是，虽然从理论上来说使用弱学习器集成足以获得很好的性能，但在实践中出于种种考虑，例如希望使用较少的个体学习器，或是重用关于常见学习器的一些经验等，人们往往会使用比较强的学习器。
- 考虑一个简单的例子：在二分类任务中，假定三个分类器在三个测试样本上的表现，用√表示分类正确，X表示分类错误，集成学习的结果通过投票法(voting)产生，即“少数服从多数”。要获得好的集成，个体学习器应“好而不同”，即个体学习器要有一定的“准确性”，并且要有“多样性”(diversity)，即学习器间具有差异。
- 在现实任务中，个体学习器是为解决同一个问题训练出来的，它们显然不可能相互独立！事实上，个体学习器的“准确性”和“多样性”本身就存在冲突。一般的，准确性很高之后，要增加多样性就需牺牲准确性。事实上，如何产生并结合“好而不同”的个体学习器，恰是集成学习研究的核心。
- 根据个体学习器的生成方式，目前的集成学习方法大致可分为两大类，即个体学习器间存在强依赖关系、必须串行生成的序列方法，以及个体学习器间不存在强依赖关系、可同时生成的并行化方法；前者的代表是Boosting，后者的代表是 Bagging 和“随机森林” (Random Forest)。
8.2 Boosting
- Boosting 是一族可将弱学习器提升为强学习器的算法。这族算法的工作机制类似：先从初始训练集训练出一个基学习器，再根据基学习器的表现对训练样本分布进行调整，使得先前基学习器做错的训练样本在后续受到更多关注，然后基于调整后的样本分布来训练下一个基学习器；如此重复进行，直至基学习器数目达到事先指定的值T，最终将这 T 个基学习器进行加权结合。
- Boosting 族算法最著名的代表是 AdaBoost。
- Boosting 算法要求基学习器能对特定的数据分布进行学习，这可通过“重赋权法”(re-weighting)实施，即在训练过程的每一轮中，根据样本分布为每个训练样本重新赋予一个权重。对无法接受带权样本的基学习算法，则可通过“重采样法”(re-sampling)来处理，即在每一轮学习中，根据样本分布对训练集重新进行采用，再用重采样而得的样本集对基学习器进行训练。一般而言，这两种做法没有显著的优劣差别。
- 需要注意的是，Boosting算法在训练的每一轮都要检查当前生成的基学习器是否满足条件（例如检查当前基分类器是否比随机猜测好），一旦条件不满足，则当前基学习器即被抛弃，且学习过程停止。在此种情形下，初始设置的学习轮数 T 也许还远未达到，可能导致最终集成中只包含很少的基学习器而性能不佳。若采用“重采样法”，则可获得“重启动”机会以避免训练过程过早停止，即在抛弃不满足条件的当前基学习器之后，可根据当前分布重新对训练样本进行采用，再基于新的采样结果重新训练出基学习器，从而使得学习过程可以持续到预设的T轮完成。
- 从偏差-方差分解的角度看，Boosting主要关注降低偏差，因此Boosting能基于泛化性能相当弱的学习器构造出很强的集成。
8.3 Bagging与随机森林
- 欲得到泛化性能强的集成，集成中的个体学习器应尽可能相互独立；虽然“独立”在现实任务中无法做到，但可以设法使基学习器尽可能有较大的差异。给定一个训练数据集，一种可能的做法是对训练样本进行采用，产生出若干个不同的子集，再从每个数据子集中训练出一个基学习器。这样，由于训练数据不同，我们获得的基学习器可望具有比较大的差异。然而，为获得好的集成，我们同事还希望个体学习器不能太差。如果采样出的每个子集都完全不同，则每个基学习器只用到了一小部分训练数据，甚至不足以进行有效学习，这显然无法确保产生出比较好的基学习器。为解决这个问题，我们可考虑使用相互有交叠的采样子集。
8.3.1 Bagging
- Bagging 是并行式集成学习方法最著名的代表，从名字可以看出，它直接基于我们的自助采样法(bootstrap sampling)。给定包含 m 个样本的数据集，我们先随机取出一个样本放入采样集中，再把该样本放回初始数据集，使得下次采样时该样本仍有可能被选中，这样，经过 m 次随机采样操作，我们得到含 m 个样本的采样集，初始训练集中有的样本在采样集里多次出现，有的则从未出现。初始训练集中约有63.2%的样本在采样集中。
- 照这样，我们可采样出 T 个含 m 个训练样本的采样集，然后基于每个采样集训练出一个基学习器，再将这些基学习器进行结合。这就是 Bagging 的基本流程。在对预测输入进行结合时，Bagging 通常对分类任务使用简单投票法，对回归任务使用简单平均法。若分类预测时出现两个类收到同样票数的情形，则最简单的做法是随机选择一个，也可进一步考察学习器投票的置信度来确定最终胜者。
- 假定基学习器的计算复杂度为 O(m)，则 Bagging 的复杂度大致为 T(O (m) + O(s))，考虑到采样与投票/平均过程的复杂度 O(s) 很小，而 T 通常是一个不太大的常数，因此，训练一个 Bagging 集成与直接使用基学习算法训练一个学习器的复杂度同阶，这说明 Bagging 是一个很高效的集成学习算法。另外，与标准 AdaBoost 只适用于二分类任务不同，Bagging 能不经修改地用于多分类、回归等任务。
- 值得一提的是，自助采样过程还给Bagging带来了另一个优点：由于每个基学习器只使用了初始训练集中约63.2%的样本，剩下约36.8%的样本可用作验证集来对泛化性能进行“包外估计”(out-of-bag estimate)。为此需记录每个基学习器所使用的训练样本。
- 事实上，包外样本还有许多其他用途。例如当基学习器是决策树时，可使用包外样本来辅助剪枝，或用于估计决策树中各节点的后验概率以辅助对零训练样本节点的处理；当基学习器是神经网络时，可使用包外样本来辅助早期停止以减小过拟合风险。
- 从偏差-方差分解的角度看，Bagging主要关注降低方差，因此它在不剪枝决策树、神经网络等易受样本扰动的学习器上效用更为明显。
8.3.2 随机森林
- 随机森林(Random Forest, RF) 是Bagging的一个扩展变体。RF在以决策树为基学习器构建 Bagging 集成的基础上，进一步在决策树的训练过程中引入了随机属性选择。具体来说，传统决策树在选择划分属性时是在当前结点的属性集合(假定有d个属性)中选择一个最优属性；而在RF中，对基决策树的每个结点，先从该结点的属性集合中随机选择一个包含k个属性的子集，然后再从这个子集中选择一个最优属性用于划分。这里的参数k控制了随机性的引入程度：若令 k = d，则基决策树的构建与传统决策树相同；若令 k = 1，则是随机选择一个属性用于划分；一般情况下，推荐值 k = log2 d。
- 随机森林简单、容易实现、计算开销小，令人惊奇的是，它在很多现实任务中展现出强大的性能，被誉为“代表集成学习技术水平的方法”。可以看出，随机森林对 Bagging 只做了小改动，但是与 Bagging 中基学习器的“多样性”仅通过样本扰动（通过对初始训练集采样）而来不同，随机森林中基学习器的多样性不仅来自样本扰动，还来自属性扰动，这就使得最终集成的泛化性能可通过个体学习器之间差异度的增加而进一步提升。
- 随机森林的收敛性与 Bagging 相似。随机森林的起始性能往往相对较差，特别是在集成中只包含一个基学习器时。这很容易理解，因为通过引入属性扰动，随机森林中个体学习器的性能往往有所降低。然而，随着个体学习器数据的增加，随机森林通常会收敛到更低的泛化误差。值得一提的是，随机森林的训练效率常优于 Bagging，因为在个体决策树的构建过程中，Bagging使用的是“确定型”决策树，在选择划分属性时要对结点的所有属性进行考察，而随机森林使用的“随机型”决策树则只考察一个属性子集。
8.4 结合策略
- 学习器结合可能会从三个方面带来好处：首先，从统计的方面来看，由于学习任务的假设空间往往很大，可能有多个假设在训练集上达到同等性能，此时若使用单学习器可能因误选而导致泛化性能不佳，结合多个学习器则会减小这一风险；第二，从计算的方面来看，学习算法往往会陷入局部极小，有的局部极小点所对应的泛化性能可能很糟糕，而通过多次运行之后进行结合，可降低陷入糟糕局部极小点的风险；第三，从表示的方面来看，某些学习任务的真实假设可能不在当前学习算法所考虑的假设空间中，此时若使用单学习器则肯定无效，而通过结合多个学习器，由于相应的假设空间有所扩大，有可能学得更好的近似。
8.4.1 平均法
对数值型输出，最常见的结合策略是使用平均法(averaging)
- 简单平均法(simple averaging)
- 加权平均法(weighted averaging)
加权平均法的权重一般是从训练数据中学习而得，现实任务中的训练样本通常不充分或存在噪声，这将使得学出的权重不完全可靠，尤其是对规模比较大的集成来说，要学习的权重比较多，较容易导致过拟合。因此，实现和应用均显示出，加权平均法未必一定优于简单平均法。一般而言，在个体学习器性能相差较大时宜使用加权平均法，而个体学习器性能相近时宜使用简单平均法。
8.4.2 投票法
对分类任务来说， 学习器将从标记集合中预测出一个标记，最常见的结合策略是使用投票法(voting)。
- 绝对多数投票法(majority voting)。若某标记得票过半数，则预测为该标记；否则拒绝预测。
- 相对多数投票法(plurality voting)。预测为得票最多的标记，若同时有多个标记获最高票，则从中随机选取一个。
- 加权投票法(weighted voting)。与加权平均法类似。
标准的绝对多数投票法提供了“拒绝预测”选项，这在可靠性要求较高的学习任务中是一个很好的机制。但若学习任务要求必须提供预测结果，则绝对多数投票法将退化为相对多数投票法。因此，在不允许拒绝预测的任务中，绝对多数、相对多数投票法统称为“多数投票法”。
- 类标记：使用类标记的投票亦称为“硬投票”(hard voting)。
- 类概率：使用类概率的投票亦称为“软投票”(soft voting)。
8.4.3 学习法
- 当训练数据很多时，一种更为强大的结合策略是使用“学习法”，即通过另一个学习器来进行结合。Stacking 是学习法的典型代表，这里我们把个体学习器称为初级学习器，用于结合的学习器称为次级学习器或元学习器(meta-learner)。
- Stacking 先从初始数据集训练出初始学习器，然后“生成”一个新数据集用于训练次级学习器。在这个新数据集中，初级学习器的输出被当作样例输入特征，而初始样本的标记仍被当作样例标记。
- 在训练阶段，次级训练集是利用初级学习器产生的，若直接用初级学习器的训练集来产生次级训练集，则过拟合风险会比较大；因此，一般是通过使用交叉验证或留一法这样的方式，用训练初级学习器未使用的样本来产生次级学习器的训练样本。
- 次级学习器的输入属性表示和次级学习算法对 Stacking 集成的泛化性能有很大影响。有研究表明，将初级学习器的输出类概率作为次级学习器的输入属性，用多响应线性回归(Multi-response Linear Regression, MLR) 作为次级学习算法效果最好，在MLR中使用不同的属性集更佳。
- 贝叶斯模型平均(Bayes Model Averagign, BMA)基于后验概率来为不同模型赋予权重，可视为加权平均法的一种特殊实现。Stacking 和 BMA 进行比较，理论上来说，若数据生成模型恰在当前考虑的模型中，且数据噪声很少，则BMA不差于Stacking；然而，在现实应用中无法确保数据生成模型一定在当前考虑的模型中，甚至可能难以用当前考虑的模型来进行近似，因此，Stacking通常优于BMA，因为其鲁棒性比BMA更好，而且BMA对模型近似误差非常敏感。
8.5 多样性
8.5.1 误差-分歧分解
- 欲构建泛化能力强的集成，个体学习器应“好而不同”。现在我们来做一个简单的理论分析。
- 个体学习器准确性越高、多样性越大，则集成越好。“误差-分歧分解”(error-ambiguity decomposition)
8.5.2 多样性度量
- 多样性度量(diversity measure)是用于度量集成个体分类器的多样性，即估算个体学习器的多样化程度，典型做法是考虑个体分类器的两两相似/不相似性。
- 不合度量(disagreement measure)
- 相关系数(correlation coefficient)
- Q-统计量(Q-statistic)
- k-统计量(k-statistic)
8.5.3 多样性增强
- 数据样本扰动：给定初始数据集，可从中产生出不同的数据子集，再利用不同的数据子集训练出不同的个体学习器。数据样本扰动通常是基于采样法，例如在 Bagging 中使用自助采样，在 AdaBoost 中使用序列采样。此类做法简单高效，使用最广。对很多常见的基学习器，例如决策树、神经网络等，训练样本稍加变化就会导致学习器由显著变动，数据样本扰动法对这样的“不稳定基学习器”很有效；然而，有一些基学习器对数据样本的扰动不敏感，例如线性学习器、支持向量机、朴素贝叶斯、k近邻学习器等，这样的基学习器称为稳定基学习器(stable base learner)，对此类基学习器进行集成往往需使用输入属性扰动等其他机制。
- 输入属性扰动：训练样本通常由一组属性描述，不同的“子空间”(subsapce，即属性子集)提供了观察数据的不同视角。显然，从不同子空间训练出的个体学习器必然有所不同。著名的随机子空间(random subspace)算法就依赖于输入属性扰动，该算法从初始属性集中抽取出若干个属性子集，再基于每个属性子集训练一个基学习器。对包含大量冗余属性的数据，在子空间中训练个体学习器不仅能产生多样性大的个体，还会因属性数的减少而大幅节省时间开销，同时，由于荣誉属性多，减少一些属性后训练出的个体学习器也不至于太差。若数据只包含少量属性，或者冗余属性很少，则不宜使用输入属性扰动法。
- 输出表示扰动：此类做法的基本思路是对输出表示进行操纵以增强多样性。可对训练样本的类标记稍作变动，如“翻转法”(Filpping Output)随机改变一些训练样本的标记；也可对输出表示进行转化，如“输出调制法”(Output Smearing)将分类输出转化为回归输出后构建个体学习器；还可将原任务拆解为多个可同时求解的子任务，如 ECOC法利用纠错输出码将多分类任务拆解为一系列二分类任务来训练基学习器。
- 算法参数扰动：基学习算法一般都有参数需进行设置，例如神经网络的隐层神经元数、初始连接权值等，通过随机设置不同的参数，往往可产生差别较大的个体学习器，例如“负相关法”(Negative Correlation)显式地通过正则化项来强制个体神经网络使用不同的参数。对参数算法较少的算法，可通过将其学习过程中某些环节用跟其他类似方式代替，从而达到扰动的目的，例如可将决策树使用的属性选择机制替换成其他的属性选择机制。值得指出的是，使用单一学习器时通常需使用交叉验证等方法来确定参数值，这事实上已使用了不同参数训练出多个学习器，只不过最终仅选择其中一个学习器进行使用，而集成学习则相当于把这些学习器都利用起来；由此也可以看出，集成学习技术的实际计算开销并不比使用单一学习器大得多。
