经典机器学习系列之【集成学习】

  中国有句老古话,叫“三个臭皮匠顶个诸葛亮”,说的是人多力量大,可也有句成语叫“乌合之众”。在机器学习中也有一类算法,将这两种思想融合起来,取其精华,它就是集成学习,算法将不同的学习器融合在一起。

  在集成学习中,算法不要求每个学习器性能最好,但是期望它们对问题具有不同的看法,Good But Different (好而不同)。

  如果在分类问题上描述的话,所表示的就是具有不同的划分能力,对于一些样本学习器$A$能划分,对于另外一些样本,学习器$B$能划分。并不要求单个学习器对所有样本都具备划分能力。

  用专业一点的属于来说的话,就是不同的学习器具有不同的偏好模型,但是每一个都是弱监督模型,集成学习将多个弱监督模型组合,得到一个好的强监督模型。其思想是,不同的学习器之间相互地错误纠正,以达到最终准确率的提升。

集成学习基础知识

  集成学习,其英文名称叫做(ensemble learning),它通过将多个学习器集成在一起来达到学习的目的。主要是将有限的模型相互组合,其名称有时也会有不同的叫法,有时也会被称为多分类器系统(multi-classifier system)、委员会学习(committee learning)、Modular systems、classifier fusion、combination、aggregation等。这些概念相互之间互相联系,又有些许区别,对于概念的定义业界还没有达成共识。整个算法所表现出来的性能非常地强悍,许多高水平的竞赛(Knowledge Discovery and Data Mining、Kaggle)中都是首选。

  在机器学习,满足训练集的假设不一定在实际应用中有同样好的表现,这样学习算法选择哪个假设进行输出的时候就面临着一定的风险,把多个假设集成起来能够降低这种风险(这可以理解为通过集成使得各个假设和目标假设之间的误差得到一定程度的抵消)。

西瓜书中 集成学习示意图

  在周志华西瓜书中通过Hoeffding不等式证明了,随着集成中个体分类器数目的增大集成的错误率将指数级下降最终趋于零

  集成学习先产生一组“个体学习器”(individual learner),再通过某种策略将其结合起来。依据每个个体学习器所采用的学习算法是否相同,可以分为同质集成异质集成

  • 同质集成中,个体学习器由相同的学习算法生成,个体学习器称为基学习器
  • 异质集成中,个体学习器由不同的学习算法生成,个体学习器称为组件学习器

好而不同

  集成学习器性能要好于单个个体学习器需要满足好而不同的两点要求:

  1. 个体学习器要好于随机猜测的结果。
  2. 个体学习器要相互独立。

  第一个条件相对来说比较容易实现,在当前问题下训练一个模型,结果比瞎猜的结果好就行了。第二个条件是集成学习研究的核心问题。每个个体学习器学习的都是同一个问题,所以个体学习器不可能做到完全相互独立。想想小时候,老师让你发表不同的观点,想想写论文的时候找创新点,人都很难做到这样一件事情,何况它只是一个小小的学习算法。

集成学习常用方法

  想要在个体学习器足够好的前提下,增强其多样性,我们可以直观上来想象一下。整个的算法学习过程是从数据到模型再到输出。

  首先考虑输入。如果每个学习器学习不同的样本,那么可以学习出相对来说不同的个体学习器。那么现在的问题就是怎么划分训练样本,你可以随机抽取,或者利用不同的属性子集训练出不同的个体学习器。

  其次考虑模型,如果基学习器的模型不一样,也能训练出不同的个体学习器。

  最后考虑输出,如果我们依据标签的特性来进行划分,也能得到不同的个体学习器。

  依据上述三点概念,主要有以下5种方法:

1. 训练样本扰动

  从原始训练样本中产生不同的样本子集,然后利用不同的样本子集训练不同的个体学习器。如Bagging中使用的自助采样Boosting中使用的序列采样

  这种训练样本扰动的方法简单高效,但只对不稳定的基学习器有效,像决策树神经网络等;对于稳定的基学习器,如线性学习器、支持向量机、朴素贝叶斯、K-NN等,就效果不明显,产生这个问题的原因就是因为稳定的基学习器,“变通能力”并不是很强。

  说到Bagging和Boosting,这里详细介绍一下这两种经典的方法:集成学习分为个体学习其之间存在强以来关系、必须串行生成的序列化方法-Boosting和不存在强依赖关系,可同时生成并行化方法-Bagging

  • 1990年Robert E Schapire提出Boosting 方法。大体思想是对容易分类错误的训练实例加强学习,与人类重复背英语单词类似。其首次提出是在下图这篇论文中:

Boosting Bing学术搜索结果

  具体的实现方法是:首先给每一个训练样例赋予相同的权重,然后训练第一个基本分类器并用它来对训练集进行测试,对于那些分类错误的测试样例提高其权重(实际算法中是降低分类正确的样例的权重),然后用调整后的带权训练集训练第二个基本分类器,然后重复这个过程直到最后得到一个足够好的学习器。

  Boosting中最著名算法是1997年Yoav Freund所提出的AdaBoost(Adaptive Boosting)方法。下图是AdaBoost论文Bing学术搜索结果:

AdaBoost Bing学术搜索结果

  由于极术社区的这个markdown对公式支持度不是很好,而AdaBoost算法证明又涉及大量公式,这里将其单独拿出来,链接如下:AdaBoost算法证明解析

  • Bagging:1996年伯克利大学Leo Breiman 提出Bagging (Bootstrap AGGregatING)方法。其思想是对训练集有放回地抽取训练样例,从而为每一个基本分类器都构造出一个跟训练集同样大小但各不相同的的训练集,从而训练出不同的基本分类器。

Bagging Bing学术搜索结果

Bagging算法解释

  是并行式集成学习方法著名代表,基于自助采样法(bootstrap sampling),给定包含$m$个样本的数据集,有放回随机采样,经过$m$次得到含有$m$个样本的采样集,这样的采样,初始训练集中约有$63.2\%$的样本出现在采样集中。

Bagging结构

  照这样采样出$ T $个含$ m $个训练样本的采样集,然后基于每个采样集训练一个基学习器,再将这些基学习器进行结合。在预测输出时,Bagging通常对分类任务使用简单投票法。对回归任务使用简单平均法

Bagging 算法

  上图中$\mathcal{D}_{bs}$表示自助采样产生的样本分布。

2. 输入属性扰动

  输入属性扰动通常是从初始属性集中抽取出若干个属性子集,然后利用不同的属性子集训练出不同的个体学习器。比如有:

  • 1998年Tin Kam Ho所提出的随机子空间方法,英文Random subspace method(RSM),又叫attribute bagging 或者 feature bagging。随机子空间(RSM)通过使用随机的部分特征,而不是所有特征来训练每个分类器,来降低每个分类器之间的相关性。

    • RSM的方法常用于特征数比较多的场景中,如核磁共振、基因组序列、CSI(信道状态信息)。
    • 在训练完成之后,依据预测结果再做进一步的处理,如投票或结合先验概率。

RSM Bing学术搜索结果

  • 2001年Leo Breiman所提出的随机森林(Random Forests)算法。是一个包含多个决策树的分类器, 并且其输出的类别是由个别树输出的类别的众数而定。

RF Bing学术搜索结果

RF算法解释

  RF在以决策树为基学习器构建Bagging集成的基础上,进一步在决策树的训练过程中引入随机属性。传统决策树在选择划分属性时是在当前结点的属性集合中选择一个最优属性;而在RF中,对基决策树的每个结点,先从该结点的属性集合中随机选择一个包含$k$个属性的子集然后再从这个子集中选择一个最优属性用于划分

  随机森林中基学习器多样性不仅来自样本扰动,还来自属性扰动,使得最终集成的泛化性能可通过个体学习器之间差异度的增加而进一步提升。

  但这类输入属性扰动的方法只对大量冗余属性的数据集有效,但若数据集只包含少量属性,或者冗余属性很少,则不宜使用。随机森林由于起始引入了属性扰动,性能会比Bagging差一点,但随着个体数量增多,随机森林通常会收敛到更低的泛化误差。

3. 算法参数扰动

  算法参数扰动指的是通过随机设置不同的参数来训练差别较大的个体学习器。如下图所示的神经网络的隐层神经元数、初始连接权值等不同。

人工神经网络集成示意

  此类方法对参数较多的算法有效,对参数较少的算法,可通过将其学习过程中某些环节用其他类似方法代替?从而达到扰动的目的。这可能也是发论文的一个点吧,自己以后可能也不咋用这个算法,就不去做算法调研了。

4. 输出标记扰动

  输出标记扰动是对训练样本的类别标记稍作变动,将原来的多分类问题随机转化多个二分类问题来训练基学习器。经典的一个算法就是纠错输出编码法(Error-Correcting Output Codes,ECOC)

ECOC Bing学术搜索结果

  将每个类别对应一个长度为n的二进制位串(称为码字),共形成m个码字,这些码字的同一位描述了一个二值函数。学习结束后获得n个二分器,在分类阶段,每个二分器对输入样本产生的输出形成输出向量,然后由决策规则判定输入样本的类别。

  这类方法对类数足够多的数据集有效,但若数据集包含的类数较少,则不宜使用。

5. 混合扰动

  混合扰动在同一个集成算法中同时使用上述多种扰动方法。比如随机森林就同时使用了训练样本扰动和输入属性扰动。

集成学习结合策略

  上文五点讨论的是如何产生好而不同的个体学习器。那产生了好而不同的个体学习器之后,我们如何结合这些策略?主要有平均法和常见的投票法(voting),具体包括:

  • 简单平均法

  简单地将输出结果平均一下

  • 加权平均法

  乘以权值系数将其加起来。

  • 绝对多数投票法(majority voting)

  即若某标记得票过半数,则分类为该标记,否则拒绝分类。

  • 相对多数投票法(plurality voting)

  分类为得票最多的标记,若同时有多个标记获最高票,则从中随机选取一个。

  • 加权投票法(weighted voting)

  给每个个体学习器预测的类标记赋一个权值,分类为权值最大的标记。这里的权值通常为该个体学习器的分类置信度(类成员概率)。

我的微信公众号名称:深度学习先进智能决策
微信公众号ID:MultiAgent1024
公众号介绍:主要研究深度学习、强化学习、机器博弈等相关内容!期待您的关注,欢迎一起学习交流进步!

参考

arnumber=709601&filter%3DAND(p_IS_Number:15364)=

推荐阅读
关注数
284
文章数
44
公众号:深度学习与先进智能决策
目录
极术微信服务号
关注极术微信号
实时接收点赞提醒和评论通知
安谋科技学堂公众号
关注安谋科技学堂
实时获取安谋科技及 Arm 教学资源
安谋科技招聘公众号
关注安谋科技招聘
实时获取安谋科技中国职位信息