集成学习概述

Posted by mudux on February 27, 2020

  集成学习(ensemble learning)结合多个学习器来完成学习任务,也就是“博采众长”。集成学习可以用于分类问题集成、回归问题集成、特征选取集成、异常点检测集成等等。

1. 集成学习概述

  从下图,可以对集成学习的思想做一个概括。对于训练集数据,通过训练若干个个体学习器,通过一定的结合策略,就可以最终形成一个强学习器。 1.1

  也就是说,集成学习有两个主要的问题需要解决,第一是如何得到若干个个体学习器,要想获得好的集成,个体学习器应该“好而不同”;第二是如何选择一种结合策略,将这些个体学习器集合成一个强学习器。

2. 集成学习之个体学习器

  集成学习的第一个问题就是如何得到若干个个体学习器。
  第一种就是所有的个体学习器都是一个种类的,或者说同质的。比如都是决策树个体学习器,或者都是神经网络个体学习器。第二种是所有的个体学习器不全是一个种类的,或者说异质的。比如一个分类问题,对训练集采用支持向量机个体学习器,逻辑回归个体学习器和朴素贝叶斯个体学习器来学习,再通过某种集合策略来确定最终的分类强学习器。
  目前来说,同质个体学习器的应用是最广泛的,一般常说的集成学习的方法都是指的同质个体学习器。而同质个体学习器使用最多的是CART决策树和神经网络。同质个体学习器按照个体学习器之间是否存在依赖关系可以分为两类,第一个是个体学习器之间存在强依赖关系,一系列个体学习器都需要串行生成,代表算法是boosting系列算法,第二个是个体学习器之间不存在强依赖关系,一系列个体学习器可以并行生成,代表算法是bagging和随机森林系列算法。

3. 集成学习之boosting

  boosting的算法原理可以用下图概括: 3.1

  Boosting的工作机制是首先从训练集用初始权重训练出一个基学习器1,根据基学习器1的学习误差率表现来更新训练样本的权重,使得之前基学习器1学习误差率高的训练样本点的权重变高,使得这些误差率高的点在后面的基学习器2中得到更多的重视。然后基于调整权重后的训练集来训练基学习器2,如此重复进行,直到基学习器达到事先 指定的数目$T$,最终将这$T$个弱学习器通过集合策略进行整合,得到最终的强学习器。
  Boosting算法要求基学习器能对特定的数据分布进行学习,这可通过“重赋权法” (re-weighting)实施,即在训练过程每一轮中,根据样本分布为每个训练样本重新赋予一个权重,对无法接受带权样本的基学习算法,则可通过“重采样法”(re-sampling)来处理,即在每一轮学习中,根据样本分布对训练集重新进行采样,再用重采样而得到的样本集对集学习器进行训练。一般而言,这两种做法没有显著的优劣差别。需注意的是,Boosting算法在训练的每一轮都要检查当前生成的基学习器是否满足基本条件(如Adaboost中检查当前基分类器是否比随机猜测好),一旦条件不满足,则当前基学习器即被抛弃,且学习过程停止。
  Boosting系列算法里最著名的算法主要有Adaboost算法和提升树(boosting tree)系列算法。提升树系列算法里面应用最广泛的是梯度提升树(Gradient Boosting Tree)。

4. 集成学习之bagging

  Bagging算法原理和Boosting不同,它的弱学习器之间没有依赖关系,可以并行生成,用下图可以概括:

4.1

  可以看出,bagging的个体基学习器的训练集是通过随机采样得到的。通过$T$次的随机采样,就可以得到$T$个采样集,对于这$T$个采样集,可以分别独立的训练出$T$个基学习器,再对这$T$个基学习器通过集合策略来得到最终的强学习器。
  这里的随机采样一般采用的是自助采样法(Bootstrp sampling),即对于$m$个样本的原始训练集,每次先随机采集一个样本放入采样集,接着把该样本放回,也就是说下次采样时该样本仍有可能被采集到,这样采集$m$次,最终可以得到$m$个样本的采样集,由于是随机采样,这样每次的采样集是和原始训练集不同的,和其它采样集也是不同的,这样得到多个不同的基学习器。
  随机森林是bagging的一个特化进阶版,所谓特化是因为随机森林的基学习器都是决策树。所谓进阶是随机森林在bagging的样本随机采样基础上,又加上了特征的随机选择,其基本思想没有脱离bagging的范畴。

5. 集成学习之结合策略

  学习器结合可能从三个方面带来好处:首先,从统计的方面来看,由于学习任务的假设空间往往很大,可能有多个假设在训练集上达到同等性能,此时若使用单学习器可能因误选而导致泛化性能不佳,结合多个学习器则会减小这一风险;第二,从计算的方面来看,学习算法往往会陷入局部极小,有的局部极小点所对应的泛化性能可能很差,而通过多次运行之后进行结合,可降低陷入局部极小点的风险;第三,从表示的方面来看,某些学习任务的真实假设可能不在当前学习算法所考虑的假设空间中,此时若使用单学习器则肯定无效,而通过结合多个学习器,由于相应的假设空间有所扩大,有可能学得更好地近似。

5.1 平均法

  对于数值类的回归预测问题,通常使用的结合策略是平均法,也就是说,对于若干个基学习器的输出进行平均得到最终的预测输出。

  • 简单平均法

  • 加权平均法 如果每个个体学习器有一个权重$w$,则最终预测是:

    其中$w_i$是个体学习器$h_i$的权重,通常有

  简单平均法是加权平均法的特例。集成学习中的各种结合方法都可视为加权平均法的特例或变体。事实上,加权平均法可认为是集成学习研究的基本出发点,对给定的基学习器,不同的集成学习方法可视为通过不同的方式来确定加权平均法中的基学习器权重。

5.2 投票法

  对于分类问题的预测,通常使用投票法。假设预测类别是,对于任意一个预测样本$x$,$T$个基学习器的预测结果分别是$(h_1(x), h_2(x),\cdots, h_T(x))$。

  • 相对多数投票法

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

  • 绝对对数投票法

    即若得票数过半数,则预测为该标记;否则拒绝预测。

  • 加权投票法

    $w_i$是$h_i$的权重,通常$w_i \ge 0, \sum\limits_{i=1}^Tw_i=1$

  标准的绝对多数投票法提供了“拒绝预测”选项,这在可靠性要求较高的学习任务重是一个很好的机制。
  在现实任务中,不同类型个体学习器可能产生不同类型的$h_i^j(x)$值,常见的有:

  • 类标记:,若$h_i$将样本$x$预测为类别$c_j$则取值为1,否则为0。使用类标记的投票亦称“硬投票”。
  • 类概率:$h_i^j(x)\in \left[0, 1\right]$,相当于对后验概率 的一个估计。使用类概率的投票亦称“软投票”.

  不同类型的$h_i^j(x)$值不能混用。对一些能在预测出类别标记的同时产生分类置信度的学习器,其分类置信度可转化为类概率使用。有趣的是,虽然分类器估计出的类概率值一般都不太准确,但基于类概率进行结合却往往比直接基于类标记进行结合性能更好。

5.3 学习法

  当训练数据很多事,一种更为强大的结合策略是使用“学习法”,即通过另一个学习器来进行结合。Stacking是学习方法的典型代表。通常把个体学习器称为初级学习器,用于结合的学习器称为次级学习器或元学习器(meta-learner)。
  Stacking先从初始数据集训练出初级学习器,然后“生成”一个新数据集用于训练次级学习器。在这个新数据集中,初级学习器的输出被当作样例输入特征,而初始样本的标记仍被当作样例标记。
  在训练阶段,次级训练集是利用初级学习器产生的,若直接用初级学习器的训练集来产生次级训练集,则过拟合风向会比较大;因此,一般是通过使用交叉验证或留一法这样的方式,用训练初级学习器未使用的样本来产生次级学习器的训练样本。

6. 偏差与方差

  上面介绍了集成学习的基本概念,这节主要介绍下如何从偏差和方差的角度来理解集成学习。

6.1 集成学习的偏差与方差

  偏差(bias)描述的是预测值和真实值之差;方差(variance)描述的是预测值作为随机变量的离散程度。见下图所示:

6.1

  • 偏差:描述样本拟合出的模型的预测结果的期望与样本真实结果的差距,要想偏差表现好,就需要复杂模型,增加模型的参数,但这样容易过拟合。
  • 方差:描述样本上训练出来的模型在测试集上的表现,要想方差表现好,需要简化模型,减少模型的复杂度,但这样容易欠拟合。

  我们常说的集成学习中的基学习器都是弱模型,通常来说弱模型是偏差高(在训练集上准确度低)方差小(防止过拟合能力强)的模型,但并不是所有集成学习框架中的基模型都是弱模型。Bagging和Stacking中的基模型为强模型(偏差低,方差高),而Boosting中的基模型为弱模型(偏差高,方差低)
  在Bagging和Boosting框架中,通过计算基模型的期望和方差可以得到整体模型的期望和方差。为了简化模型,假设基模型的期望为$\mu$,方差为$\sigma^2$,模型的权重为$r$,两两模型相关系数为$\rho$相等。由于Bagging和Boosting的基模型都是线性组成的,那么有:
模型总体期望:

模型总体方差:

6.2 Bagging的偏差与方差

  对于Bagging来说,每个基模型的权重等于$\frac{1}{m}$且期望近似相等,可以得到:

  可以看出:

  • 整体模型的期望等于基模型的期望,意味着整体模型的偏差和基模型的偏差近似;
  • 整体模型的方差小于等于基模型的方差,当且仅当相关性为1时取等号,随着基模型数量增多,整体模型的方差较少,从而防止过拟合能力增强,模型的准确度得到提高。

  在此知道了为什么Bagging中的基模型一定要为强模型,如果Bagging使用弱模型则会导致整体模型的偏差提高,而准确度降低。
  Random Forest是经典的基于Bagging框架的模型,并在此基础上通过引入特征采样和样本采样来降低模型间的相关性,在公式中显著降低方差公式中的第二项,略微升高第一项,从而使得整体模型方差降低。

6.3 Boosting的偏差与方差

  对于Boosting来说,由于基模型共用一套训练集,所以基模型间具有强相关性,故模型间的相关系数近似等于1,简化公式为:

  可以看出:

  • 整体模型的方差等于基模型的方差,如果基模型不是弱模型,其方差较大,这将导致整体模型的方差较大,即无法达到防止过拟合的效果。因此,Boosting框架中的基模型必须为弱模型;
  • Boosting框架中采用基于贪心策略的前向加法,整体模型的期望由基模型的期望累加而成,所以随着基模型的增多,整体模型的期望值增加,整体模型的准确度提高。

  基于Boosting框架的Gradient Boosting Decision Tree模型中基模型为树模型,同随机森林,可以对特征进行随机抽样

7. 集成学习之多样性增强

  在集成学习中需有效地生成多样性大的个体学习器。与简单地直接使用初始数据训练出个体学习器相比,如何增强多样性?一般思路是在学习过程中引入随机性,常见的做法是对数据样本、输入属性、输出表示、算法参数进行扰动。

7.1 数据样本扰动

  给定初始数据集,可从中产生出不同的数据子集,再利用不同的数据子集训练出不同的个体学习器。数据样本扰动通常是基于采样法,如Bagging使用自助采样,在Adaboost中使用序列采样。此类做法简单高效,使用最广。对很多常见的基学习器,例如决策树、神经网络等,训练样本稍加变化就会导致学习器有显著变动,数据样本扰动法对这样的“不稳定基学习器”很有效;然而,有一些基学习器对数据样本的扰动不敏感,例如线性分类器、支持向量机、朴素贝叶斯、$k$近邻学习器等,这样的基学习器称为稳定基学习器,对此类基学习器进行集成往往需使用输入属性扰动等其他机制。

7.2 输入属性扰动

  训练样本通常有一组属性描述,不同的子空间提供了观察数据的不同视角。显然,从不同子空间训练出的个体学习器必然有所不同。
  对包好大量冗余属性的数据,在子空间中训练个体学习器不仅能产生多样性大的个体,还会因属性数的减少而大幅节省时间开销,同时,由于冗余属性多,减少一些属性后训练出的个体学习器也不至于太差。若数据只包含少量属性,或者冗余属性很少,则不宜使用输入属性扰动法。

7.3 输出表示扰动

  此类做法的基本思路是对输出表示进行操纵以增强多样性,可对训练样本的类标记稍作变动。如“翻转法”随机改变一些训练样本的标记;也可对输出表示进行转化,如“输出调制法”将分类输出转化为回归输出后构建个体学习器。

7.4 算法参数扰动

  基学习算法一般都有参数需进行设置,例如神经网络的隐层神经元树、初始连接权值等,通过随机设置不同的参数,往往可产生差别较大的个体学习器。
  不同的多样性增强机制可以同时使用,例如随机森林中同时使用了数据样本扰动和输入属性扰动。

8. Reference

1 集成学习原理小结
2. 决策树(中)
3 机器学习第八章-周志华