集成学习

集成学习综述梁英毅摘要机器学习方法在生产、科研和生活中有着广泛应用，而集成学习则是机器学习的首要热门方向[1]。集成学习是使用一系列学习器进行学习，并使用某种规则把各个学习结果进行整合从而获得比单个学习器更好的学习效果的一种机器学习方法。本文对集成学习的概念以及一些主要的集成学习方法进行简介，以便于进行进一步的研究。一、引言机器学习是计算机科学中研究怎么让机器具有学习能力的分支，[2]把机器学习的目标归纳为“给出关于如何进行学习的严格的、计算上具体的、合理的说明”。[3]指出四类问题的解决对于人类来说是困难的甚至不可能的，从而说明机器学习的必要性。目前，机器学习方法已经在科学研究、语音识别、人脸识别、手写识别、数据挖掘、医疗诊断、游戏等等领域之中得到应用[1,4]。随着机器学习方法的普及，机器学习方面的研究也越来越热门，目前来说机器学习的研究主要分为四个大方向[1]：a)通过集成学习方法提高学习精度；b)扩大学习规模；c)强化学习；d)学习复杂的随机模型；有关MachineLearning的进一步介绍请参考[5,1,3,4,6]。本文的目的是对集成学习的各种方法进行综述，以了解当前集成学习方面的进展和问题。本文以下内容组织如下：第二节首先介绍集成学习；第三节对一些常见的集成学习方法进行简单介绍；第四节给出一些关于集成学习的分析方法和分析结果。二、集成学习简介1、分类问题分类问题属于概念学习的范畴。分类问题是集成学习的基本研究问题，简单来说就是把一系列实例根据某种规则进行分类，这实际上是要寻找某个函数)(xfy=，使得对于一个给定的实例x，找出正确的分类。机器学习中的解决思路是通过某种学习方法在假设空间中找出一个足够好的函数来近似，这个近似函数就叫做分类器[7]。yhfh2、什么是集成学习传统的机器学习方法是在一个由各种可能的函数构成的空间（称为“假设空间”）中寻找一个最接近实际分类函数的分类器h[6]。单个分类器模型主要有决策树、人工神经网络、朴素贝叶斯分类器[6]等等。集成学习的思路是在对新的实例进行分类的时候，把若干个单个分类器集成起来，通过对多个分类器的分类结果进行某种组合来决定最终的分类[8，9]，以取得比单个分类器更好的性能。如果把单个分类器比作一个决策者的话，集成学习的方法就相当于多个决策者共同进行一项决策。f图表1表示了集成学习的基本思想。图表1中的集成分类器包括了N个单一的人工神经网络分类器，对于同样的输入，N个人工神经网络分别给出各自的输出（），然后这些输出通过整合以后得到集成分类器整体的输出结果作为最终分类。nOOO,,,21L图表1人工神经网络集成示意在各种文献中集成学习（EnsembleLearning）也被称为committee、classifierfusion、combination、aggregation等等[9]，但是他们都是指把一系列的学习器集成起来共同解决一个问题。3、为什么集成学习有效ThomasG.Dietterich[8,7]指出了集成学习有效可以归为三个方面的原因：统计上、计算上和表示上：a)统计上的原因对于一般的学习任务，往往要搜索的假设空间十分巨大，但是能够用于训练分类器的训练集中实例个数不足够用来精确地学习到目标假设，这个时候学习的结果便可能是一系列满足训练集的假设，而学习算法之能够选择这些假设的其中之一作为学习到的分类器进行输出。然而通过机器学习的过拟合问题[6]我们看到，能够满足训练集的假设不一定在实际应用中有同样好的表现，这样学习算法选择哪个假设进行输出的时候就面临着一定的风险，把多个假设集成起来能够降低这种风险（这可以理解为通过集成使得各个假设和目标假设之间的误差得到一定程度的抵消）。b)计算上的原因已经证明了在人工神经网络学习和决策树学习中，学习到最好的人工神经网络或者是决策树是一个NP-hard问题[1,8]，其他的分类器模型也面临着类似的计算复杂度的问题。这使得我们只能用某些启发式的方法来降低寻找目标假设的复杂度，但这样的结果是找到的假设不一定是最优的。通过把多个假设集成起来能够使得最终的结果更加接近实际的目标函数值。c)表示上的原因由于假设空间是人为规定的，在大多数机器学习的应用场合中实际目标假设并不在假设空间之中，如果假设空间在某种集成运算下不封闭，那么我们通过把假设空间中的一系列假设集成起来就有可能表示出不在假设空间中的目标假设。关于表示上的原因比较特别，进一步的说明可以参考[8,9]。4、集成学习有效的条件虽然以上几方面的原因使得集成学习可能取得更好的学习效果，但是并不是所有的集成方式都有效的，集成学习有效的条件是每个单一的学习器错误率都应当低于0.5，否则集成的结果反而会提高错误率[11,12,9,10]。此外，进行集成学习的每个分类器还应当各不相同，这个要求可以这样理解：如果每个基本分类器分类结果差不多，则集成后的分类器整体和单个分类器做出的决策实际上没有什么差异，这样集成后的分类器就难以保证比单个分类器有更好的性能了。三、集成学习方法介绍从前面对集成学习的介绍可以看出，考察一个集成学习方法的时候应该考虑以下几方面的问题：a)基本分类器之间是什么关系？b)怎么样生成多个不同的基本分类器？c)如何把多个基本分类器的分类结果整合起来？我们下面将以这三个问题为线索对现在主要的集成学习方法进行简单的介绍：1、基本分类器之间的关系按照基本分类器之间的种类关系可以把集成学习方法划分为异态集成学习和同态集成学习两种[10]。a)异态集成学习异态集成学习指的是使用各种不同的分类器进行集成，异态集成学习的两个主要代表是叠加法（StackGeneralization）[13]和元学习法（MetaLearning）[14]。叠加法的思想是把基本学习器分布在多个层次上，用多层的学习器来完成学习任务[13]。第一层学习器按照一般学习器的方式来进行分类预测，然后第一层的预测结果作为第二层的输入由第二层再进行预测……WilliamW.Cohen等在[15]中利用叠加法的思想构造了一种新的串行学习算法，并且指出这种串行学习方法比不串行的单个学习器性能上有所改进。[13]中对叠加法进行了详细的介绍。元学习法的思想是训练一个元分类器来对所有的基本学习器的输出进行处理，最终得到问题的输出。元学习法主要有仲裁法（arbiter）和合并法（combiner）两种，仲裁法是元分类器从所有基本分类器的输出中选择合理的结果作为输出，例如投票方式；合并法是用某种组合方法把所有基本分类器的输出合并成最终输出，Bagging、Boosting等集成方法都是属于合并法。[14]中对元学习法给出了一个综述。关于异态分类器的进一步资料可以参考[16]。b)同态集成学习同态集成学习是指集成的基本分类器都是同一种分类器，只是这些基本分类器之间的参数有所不同。同态集成的分类器包括有朴素贝叶斯集成、决策树集成[17]、人工神经网络集成[18,19,20]、K-近邻集成等等[10]，其中以决策树集成和人工神经网络集成居多。2、不同的基本分类器的获得方式基本分类器的多样性是评价集成学习算法的重要标准[10]，因此如何获取不同的基本分类器对集成学习的效果有着重要影响。对于异态集成学习方法，基本分类器的不同来源于他们本身种类的不同；对于同态集成学习方法，基本分类器的不同来自于多种可能，以下把不同基本分类器的获取方式划分为五类，并分别予以说明：a)基本分类器种类不同如果一种集成学习方式采用异态集成的方案，则所得到的基本分类器很明显不同。但是由于有效的分类器基本模型并不多，因此进行异态集成学习的时候往往需要对于每一种分类器都给出若干不同的实例，这些同一种分类器的不同实例的产生需要用到下面几种获取方式。b)对训练数据进行处理i.BaggingBagging（BootstrapAGGregatING）是Breiman在[21]中提出的，其思想是对训练集有放回地抽取训练样例，从而为每一个基本分类器都构造出一个跟训练集同样大小但各不相同的训练集，从而训练出不同的基本分类器。Bagging算法如图表2所示：图表2Bagging算法示意Bagging是基于对训练集进行处理的集成方法中最简单、最直观的一种。使用Bagging算法的时候，理论上每个基本分类器的训练集中有63.2%的重复样例[21,10]。Breiman在[21]中同时指出，要使得Bagging有效，基本分类器的学习算法必须是不稳定的，也就是说对训练数据敏感。基本分类器的学习算法对训练数据越敏感，Bagging的效果越好，因此对于决策树和人工神经网络这样的学习算法Bagging是相当有效的。另外由于Bagging算法本身的特点，使得Bagging算法非常适合用来并行训练多个基本分类器，这也是Bagging算法的一大优势。那么使用Bagging算法的时候应该用多少个基本分类器合适呢？Breiman指出基本分类器数目应当随着分类种数增多而增加。[22,23]给出了Bagging算法和其他集成算法的实验结果比较。关于Bagging的更多资料请参考[24,25,23,8,16]等等。ii.BoostingBoosting最先由RobertT.Schapire在[26]中提出，其思想是对每那些容易分类错的训练实例加强学习，就好像一个人背英语单词一样，首先第一遍背完以后有一些容易记住的单词就记住了，还有一些不容易记住的，则第二遍的时候对那些不容易记住的单词多看几眼，第三遍又对第二遍还记不住的单词再多看几眼……具体实施的时候Boosting方法是这样进行的：首先给每一个训练样例赋予相同的权重，然后训练第一个基本分类器并用它来对训练集进行测试，对于那些分类错误的测试样例提高其权重（实际算法中是降低分类正确的样例的权重），然后用调整后的带权训练集训练第二个基本分类器，然后重复这个过程直到最后得到一个足够好的学习器。图表3给出了最常用的Boosting算法——由YaovFreund和Schapire[27]共同提出的AdaBoost（AdaptiveBoosting）算法的描述。图表3AdaBoost算法Boosting的基本目标是把一个弱学习器转化为一个任意高精度的学习器[26]，什么是弱学习器呢？Schapire指出弱学习器是指一个学习效果比随机分类略好的学习器[26]。Boosting方法为什么有效呢？近年的研究指出Boosting算法实际上是一个逐阶段最小化一个特定的误差函数的梯度下降过程[8]。Boosting的原本目的是用于学习二值分类器，但是应用到训练多值分类器的方法也已经被研究过了[10]。与Bagging对于噪声容忍程度比较好不同，Boosting似乎对噪声容忍程度不高[8]。关于Boosting算法的实验结果比较可以参考[22,23]，进一步的资料可以参考[28,9,29,17,30,32,31]等。iii.交叉验证交叉验证法来自于K重交叉验证（K-foldCrossValidation）的测试方法，属于无放回抽抽样[1,9,10]。K重交叉验证的思想是把整个训练集合划分为互不相交的K等份，然后每次选定一份作为测试集，其他的K-1份作为训练集来进行学习，用这种思路可以训练出K个不同的基本分类器。跟Bagging一样，这种集成方法也适用于多个基本分类器并行进行训练。c)对输入特征进行处理这种方法的思想是对于具有多种输入特征的实例，通过抽取不同的输入特征子集分别进行训练，从而获得不同的分类器[10,8,9]，把这些分类器的分类结果适当整合能够获得比任何一个基本分类器的分类精度都要高的分类器[7]。特征子集的选取又叫做集成特征选取（EnsembleFeatureSelection），根据特征子集的选取方式不同，又有随机子空间法（随机抽取特征子集）和少量余留法（InputDecimation，只抽取和问题最相关的那些特征）[9]；AlexeyTsymba等在[33]中介绍了一种新的遗传搜索方法来选择输入特征子集，并指出这种方法虽然比一般方法耗时长，但是具有更佳的学习效果。