集成学习(Ensemble learning)

2019-08-06 本文已影响0人 _与谁同坐_

摘要：本文是理解adaboost算法与xgboost算法的前奏篇，主要介绍集成学习（Ensemble learning）的含义，在模型选择、训练数据过多或过少、数据融合及置信度估计等几方面的应用，同时介绍了集成学习的两个重要方面，即生成模型的算法，如bagging、boosting，以及组合模型结果的方法，如平均、投票等。对后续理解adaboost算法与xgboost算法起到了很好的铺垫。同时，非常推荐读者直接阅读参考资料，值得推荐，本文仅是学习笔记。

在我们的日常生活中，通常做出某个最终决定之前会综合几个“专家”的意见。例如购买商品（特别是高价商品）之前阅读用户评论；在确定复杂疾病的治疗方案之前会由多个专家进行会诊讨论；发表一篇官方正式文章之前要经过多人审阅等。这样做的主要目的是尽量降低购买劣质产品、减少医疗事故、发表劣质文章或误导性文章的可能性。多年来，综合预测的原则一直被多个领域关注。金融预测界几十年来一直在股票投资组合的场景下分析模型组合；早在20世纪90年代，机器学习社区贡献了从数据中自动构造模型和组合模型的方法，是我们本文要讨论的集成学习的两个重要方面。

一. 什么是集成学习

集成学习是这样一个过程，按照某种算法生成多个模型，如分类器或者称为专家，再将这些模型按照某种方法组合在一起来解决某个智能计算问题。集成学习主要用来提高模型（分类，预测，函数估计等）的性能，或者用来降低模型选择不当的可能性 $^{[1]}$ 。集成算法本身是一种监督学习算法，因为它可以被训练然后进行预测，组合的多个模型作为整体代表一个假设（hypothesis）。

二. 集成学习的应用场景

2.1 模型选择（Model Selection）

模型选择可能是集成算法在实践中应用的主要原因。在实践中，面对一个给定的机器学习问题，选择模型是件复杂且有风险的事。

例如一个分类问题，选择哪个分类器比较好？这个问题可以进一步分为两个问题：
i）在功能类似的模型中到底选择哪个，是多层感知器（MLP）、支持向量机（SVM）、决策树还是朴素贝叶斯？
ii）如果i）已经选定，该算法怎么实现？例如，在其他参数保持不变的情况下，MLP的不同初始化参数可以产生不同的决策边界。

面对上面的问题，我们通常的做法是：选择在测试集误差最小的分类器。但这种做法有缺陷，因为即使用交叉验证法（cross-validation）选择一个在训练误差（training error）和泛化误差（genelization error，或者说测试集误差）比较好的算法，在面对未知的数据时仍然可能表现不好；另外，如果所有算法的训练误差和泛化误差都一样，该怎样选择？最终我们可能会随机选一个，会不会选择一个对未知数据性能较差的模型？有可能。相比于只选择一个模型，集成学习对模型集合中所有模型的输出按照某种方法进行组合，例如简单的取平均，可以降低模型选择不当的风险。

不过需要强调的是集成的模型组合不一定总是比单个成员模型的性能好，可能会比其中性能最好的模型要差，但集成的模型组合降低了整体模型选择不当的风险。

集成学习之所以能提高整体性能，即具有纠正某些成员模型错误的能力，完全取决于集成学习系统中成员模型，如分类器的多样性。因为假设所有成员模型的输出都一样，就无法纠正错误了。实现分类器多样性的方法有多种，最流行的方法是使用不同的数据集来训练每一个分类器，这些数据集通过从总体数据集中有放回的随机采样获得，例如bootstrapping或bagging技术，我们后面会讲到；在分类的场景中，可使用弱分类器或者不稳定模型（unstable model）作为成员模型来提高多样性，因为即使对训练参数进行微调，也会得到完全不同的决策边界；也可以使用不同类型的分类器，如决策树，最近邻，支持向量机等混合到一起来增加多样性；还有一些其他增加多样性的方法就暂不做介绍了。

总之，如果能达到适当的多样性，每个分类器的误差不同，通过一定策略进行组合可以减少总误差。如下图所示，每个分类器在不同的训练子集上进行训练，误差不同（看图中标记的加粗黑框标记的样本），但将三个分类器进行组合后得到了最好的分类边界。

集成分类器降低分类误差

2.2 数据太多/太少

当处理大量数据或缺乏足够的数据时，这里缺乏足够的数据可以理解为数据太少以至于不能体现分布，集成学习可能非常有用：
i）当训练数据量太大，以至难以使用单一分类器训练时，可以将数据按照一定策略划分为较小的子集。然后使用每个子集来训练单独的分类器，再用恰当的方法对分类器输出进行组合；
ii）如果训练数据量太小，那么使用bootstrapping技术可以从总体数据集中有放回的随机采样获得多个样本集，每个样本集作为训练集对分类器进行训练，这些样本集可以看作是从总体分布中得到的独立样本集。

2.3 分而治之

有些机器学习问题很难用一个模型来解决，例如不同类别的决策边界非常复杂，考虑下图中的分类问题该怎样解决：两个特征纬度feature1和feature2，两个类别 $O$ 和 $X$ ，可以看出区分类别 $O$ 和类别 $X$ 的决策边界非常复杂（橘红色粗线框），很明显，决策边界是圆形的分类器无法表示这个复杂边界：

我们知道线性分类器能够表示线性边界，但无法表示复杂的非线性边界。但是适当的组合线性分类器，就能够做到表示非线性边界。例如对于上图的问题，我们有一个能够生成圆形决策边界的分类器，这个分类器无法得到上图中的复杂决策边界，那么我们考虑生成这种分类器的集合，如下图所示：

每个分类器根据数据落在圆形决策边界内和边界外来标记类别 $O$ 和 $X$ ，最终根据大多数原则来判定类别是 $O$ 还是 $X$ ，这样就可以轻松解决这个复杂的非圆形决策边界问题了。不过这里需要注意两点：分类器的输出是独立的；至少半数以上的分类器分类正确。

从某种意义上来说，集成学习系统遵循一种分而治之的方法，将数据空间划分为更小、更易于学习的分区，其中每个模型只学习其中一个更简单的分区。然后通过不同方法来适当组合模型的输出来近似复杂决策边界。

2.4 数据融合

在许多需要自动决策的应用程序中，接收来自不同来源的数据并提供补充信息是很常见的。这种信息的适当组合被称为数据或信息融合，与仅根据任何单个数据源进行决策相比，可以提高分类决策的准确性。

例如，对于神经系统疾病的诊断，神经学家可以使用脑电图（一维时间序列数据）、核磁共振成像MRI、核磁共振功能成像fMRI或PET扫描（二维空间数据）、脑脊液中某些化学物质的量，以及患者的年龄、性别、教育程度等统计学上的数据。将各种各样的特征数据一起来训练一个分类器很困难，同时性能也不一定好，这种情况下可以对每个特征独立地使用一个分类器去训练，再将结果进行合并，至于合并的方法我们后面就会讲到。

2.5 置信度估计

集成学习系统的结构对决策提供置信度具有天然优势，考虑对一个分类问题训练一个分类器集合，如果集合中绝大多数分类器决策一致，那么就认为整体决策的结果具有较高置信度；然而，如果集合中一半的分类器做出一个决定，另一半做出一个不同的决定，那么就认为整体决策的结果具有较低置信度。不过这里同样需要注意的是，置信度较高的决策不一定是正确的决策，同样置信度较低的决策不一定是错误的决策。然而，研究表明，一个经过适当训练的集合决策在其置信度较高时通常是正确的，在其置信度较低时通常是错误的。可以使用集合的决策结果来估计分类的后验概率（Muhlbaier 2005）。

三. 模型集合的组合方法

在第一节我们介绍集成学习时可以看出，集成学习主要包括两个部分：获得一组成员模型的学习方法，以及对成员模型的决策结果的组合方法。这一节我们假设已经有了一组模型，我们来探索下将它们的输出组合起来的常用方法，包含分类和回归问题。

模型集合的组合方法有很多，我们这里主要介绍在实践中最常用的三种：线性组合、乘积组合和投票组合。

3.1 线性组合

线性组合用于输出实数的模型，因此适用于回归模型结果的集成，或分类模型集成中估计类别的概率，这里我们介绍后一种。假设有模型 $f_t(y|\textbf{x})$ ，即给定输入向量 $\textbf{x}$ ，估计类别 $y$ 的概率。现有上述模型的集合， $t=\{1...T \}$ ，那么模型集合整体对类别 $y$ 的概率估计为：
$\overline f(y|\textbf{x}) = \sum_{t=1}^{T}w_t f_t(y|\textbf{x})$
对于 $\forall t$ ，如果权重相同，即 $w_t = \frac{1}{T}$ ，上述公式表示概率估计的平均值，当然可以根据模型的准确度来设置不相同的权重，只是权重确定比较困难，还存在过拟合的风险，因此平均权重是最常用的。

3.2 乘积组合

对于输入向量 $\textbf{x}$ ，乘积组合如下所示：
$\overline f(y|\textbf{x}) = \frac{1}{Z}\prod_{t=1}^{T} f_t(y | \textbf{x})^{w_t}$
其中 $Z$ 是个归一化因子来保证 $\overline f$ 是个合法分布（满足概率分布性质）。在各模型的类别条件概率估计相互独立的假设下，乘积组合在理论上是最好的组合策略，但是在实际中，这种假设很难成立，同时权重与线性组合一样不好确定。

3.3 投票组合

线性组合和乘积组合适用于模型的输出是实数，当模型的输出是类别时，可以使用投票组合。每个分类器对某个类别投票，获得多数票的类别作为集成模型整体的输出。例如，一个二分类问题，分类器输出类别 $h_t(x) ∈ \{−1, +1 \}$ ，集成学习系统输出可以表示为：
$H(\textbf{x}) = sign( \sum_{t=1}^{T}w_t h_t(y|\textbf{x} ) )$
同样，权重可以是均匀的，也可以不均匀。

四. 模型集合的学习算法

在日常生活中，如果我们成立一个委员会来举手表决一个决定，我们肯定不希望他们同时做出同样的错误判断。同样的道理，一个集成学习的模型集合，我们希望其中的模型在群体中表现出一定的“多样性”，同时仍然保持着良好的个体表现。

算法的原则是需要鼓励多样性，这里可分为两种：含蓄的和明确的。模型集成方法中按大多数原则投票就是含蓄的，算法为每个成员学习器分配不同的随机训练子集，以促进多样性的发生。从总体样本中随机抽样就是“含蓄地”鼓励多样性：任何时候都不采取措施确保多样性的出现。数据集之间的随机差异可能存在于样本选择（bagging算法）、特征选择（Random Subspaces or Rotation Forests）或二者的组合（the Random Forests algorithm）等等。

另一种是明确鼓励多样性，用一些措施来确保其成员之间有实质性区别。Boosting算法通过改变每个成员的训练样本分布来实现这一点，从而鼓励对之前的成员模型预测错误的样本上有更准确地预测。接下来，我们将了解文献中最受关注的三种算法。

4.1 Bagging

在Bagging算法中，模型集合中的每个成员学习器均从不同的训练集得到，成员的预测结果可以通过第三节中介绍的方法组合。每个训练集通过bootstrapping方法得到，如图所示，通过从总体样本数据N(N=12)中有放回的随机选取M(M=5)个样本：

每个训练集称为bootstrap，Bagging即是Bootstrap AGGregatING的首字母缩略词。由于每个bootstrap的M个样本是有放回随机选取的，因此每个样本不被选中的概率为 $p=(1 - \frac{1}{N})^M$ 。当N和M都非常大时，比如N=M=10000，一个样本不被选中的概率p = 36.8%。因此一个bootstrap约包含原样本63.2%，约36.8%的样本未被选中。

类似其他的集成方法，Bagging在不稳定模型（unstable models）集合中表现比较好。这里说的不稳定的模型，即在训练数据发生微小变化时产生不同泛化行为的模型，也称为高方差模型，如决策树和神经网络。Bagging在过于简单模型集合中表现并不好，因为Bagging是从总体数据集随机选取样本来训练模型，过于简单的模型可能会产生相同的预测结果，失去了多样性。Bagging算法如下：

这里需要注意的是，成员学习器之间不存在强依赖关系，因此可并行化生成，而下一小节介绍的Boosting，成员学习器之间存在强依赖关系，必须串行生成。

4.2 Boosting

Boosting是一族可将弱学习器（即成员学习器/基学习器）提升为强学习器的算法。这族算法的工作机制类似：先从初始训练集训练出一个基学习器，再根据基学习器的表现对训练样本分布进行调整，使得先前基学习器做错的训练样本在后续受到更多关注，然后基于调整后的样本分布来训练下一个基学习器；如此重复进行，直至基学习器数目达到事先指定的值 $N$ ，最终将这 $N$ 个基学习器进行加权结合。主要思想是，后续模型应该能够补偿早期模型所造成的错误。Adaboost是Boosting算法家族中最著名的一个，详见集成学习之AdaBoost。

4.3 Mixtures of Experts

Mixture of experts (MoE)也是一种创建模型集合的算法。适用于处理数据集中的数据产生方式不同的情况，根据数据涞源进行分离训练多个模型，各个模型被称为专家（Expert），专家对输入（input）有预测或者观点，而Gating net模型的实际输出为各个模型的输出与Gating net 模块的权重组合，如下图所示，因为目前只了解了思想，所以暂不多阐述了。

参考资料：

scholarpedia, Ensemble_learning
Claude Sammut, Geoffrey I. Webb (Eds.)，Gavin Brown, Encyclopedia of Machine Learning, Springer Press 2010, Ensemble Learning
Joseph Rocca, Ensemble methods: bagging, boosting and stacking,Understanding the key concepts of ensemble learning.
Trevor Hastie, Robert Tibshirani, Jerome Friedman(2009). The Elements of Statistical Learning: Data Mining, Inference, and Prediction (2nd Ed.), Springer, New York, 329-331