Press "Enter" to skip to content

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

本站内容均来自兴趣收集,如不慎侵害的您的相关权益,请留言告知,我们将尽快删除.谢谢.

以爱与青春为名,陪你一路成长

 

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

 

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

 

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

 

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

 

集成学习基础知识

 

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

 

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

西瓜书中 集成学习示意图

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

 

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

 

同质集成中,个体学习器由 相同 的学习算法生成,个体学习器称为 基学习器 。

 

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

 

好而不同

 

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

 

 

个体学习器要好于随机猜测的结果。

 

个体学习器要相互独立。

 

 

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

 

集成学习常用方法

 

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

 

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

 

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

 

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

 

依据上述三点概念,主要有以下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学术搜索结果

 

AdaBoost算法证明

 

本文以周志华西瓜书推导过程为例,以“ 加性模型 ”(additive model)进行解析:

 

将基学习器线性组合,则基学习器的线性组合表示为如下形式:

 

定义整个学习器的损失函数为指数损失函数( exponential loss function ),期望指数损失函数最小化:

 

其中是真实函数,,表示样本的权值分布(对于错误的样本权重要高一点,正确的样本权重要低一点,所有的样本组合起来就相当于有一个分布)。

 

若基学习器的线性组合能够使得指数损失函数最小化,一般的做法就是求偏导数,令其等于零,求解。由于取值只有两种,所以其求偏导数之后的结果如下所示:

 

令其偏导数为0,解得:

 

有:

 

这意味着若指数损失函数最小化,则分类错误率也将最小化。说明指数损失函数是原任务的替代函数,但由于其连续可微,所以用它替代 0/1 损失函数作为优化目标。上面这幺多就是说接下来用这个连续的指数损失函数做进一步的处理。

 

在AdaBoost算法中,第一个基分类器通过直接将基学习算法用于初始数据分布而得到;之后的和是通过迭代生成得到的。当基分类器基于分布产生之后,基分类器的权重应该使得最小化指数损失函数,只有在判断错误的基分类器给予较小权值,判断正确的基分类器给予较大权值,才能使得具有较准确的判断,从而最小化指数损失函数

 

其中,其实就是误判率。为了求得基分类器的权重,对其求导:

 

再令导数为0,可得:

 

到这里相当于自适应做完了,在这里,AdaBoost自适应的思想采取的是加权多数表决的方法,上述公式体现出来的就是加大分类器误差率小的弱分类器的权值,使其在表决中起较大作用。误差率较大的则相反。

 

现在要回到Boost的原理中对样本的处理,在改变这个样本的权值,或者说概率分布的时候,我们要实现的直观想法是: 提高那些被前一轮弱分类器错误分类样本的权值 , 降低那些被正确分类的样本的权值 。接下来我们去把这个公式证出来:

 

这里通过基学习器开始证明,看基学习器在什幺样本分布下能够学出来最小化分类误差。

 

AdaBoost 在得到之后,调整样本分布,使得能学出来之前的基学习器无法学习到的东西,能纠正的一些错误,那这个就能够最小化:

 

注意到,上式可使用的泰勒展开式近似为如下公式:

 

于是理想的基学习器:

 

注意到是一个常数。令表示一个分布:

 

依据数学期望的定义,等价于令:

 

由,,,有:

 

则理想的基学习器:

 

由此可见,理想的将在分布下最小化分类误差。和的关系有:

 

上述公式就是下图AdaBoost的第7步更新公式,整个的AdaBoost算法如下图所示:

 

AdaBoost 算法第五行检查当前基分类器是否比随机猜测好,一旦不满足条件,当前基学习器即被抛弃,且学习过程停止。在这个请款下就有可能导致集成中包含基学习器数量过少,导致整体性能不佳。采用“重采样法”(re-sampling)来处理,即在每一轮学习中,根据样本分布对训练集重新采样,再用重采样而得到的样本集对基学习器进行训练,则可获得重启动。

 

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

Bagging Bing学术搜索结果

 

Bagging算法解释

 

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

Bagging结构

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

Bagging

上图中表示自助采样产生的样本分布。

 

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中,对基决策树的每个结点, 先从该结点的属性集合中随机选择一个包含个属性的子集 , 然后再从这个子集中选择一个最优属性用于划分 。

 

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

 

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

 

3.算法参数扰动:

 

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

人工神经网络集成示意

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

 

4.输出标记扰动:

 

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

ECOC Bing学术搜索结果

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

 

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

 

5.混合扰动:

 

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

 

集成学习结合策略

 

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

 

简单平均法

 

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

 

加权平均法

 

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

 

绝对多数投票法(majority voting)

 

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

 

相对多数投票法(plurality voting)

 

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

 

加权投票法(weighted voting)

 

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

 

参考

 

https://ieeexplore.ieee.org/document/709601?

 

https://dl.acm.org/doi/10.1023/A%3A1010933404324

 

https://link.springer.com/article/10.1023%2FA%3A1018054314350

 

https://blog.csdn.net/yq_forever/article/details/54948564 arnumber=709601&filter%3DAND(p_IS_Number:15364)=

 

https://www.jianshu.com/p/a779f0686acc

 

https://www.cnblogs.com/Acceptyly/p/3556293.html

 

http://soft.cs.tsinghua.edu.cn/~keltin/docs/ensemble.pdf

 

Be First to Comment

发表评论

电子邮件地址不会被公开。 必填项已用*标注