集成学习

集成学习(ensemble learning)的主要思想是利用一定的手段学习出多个分类器,然后将多个分类器进行组合预测。核心思想就是如何训练处多个弱分类器以及如何将这些弱分类器进行组合。若集成中只包含同种类型的个体学习器,则这样的集成是“同质”的,其个体学习器称为“基学习器”。若包含的是不同类型的个体学习器,则称为“异质”,其基学习器称为“组件学习器”。

集成学习通过将多个学习器进行结合,常可获得比单一学习器显著优越的泛化性能,对“弱学习器” 尤为明显。弱学习器常指泛化性能略优于随机猜测的学习器。集成学习的结果通过投票法产生,即“少数服从多数”。个体学习不能太坏,并且要有“多样性”,即学习器间具有差异。

集成学习可以分为两类

  • 个体学习器间存在强依赖关系,必须串行生成的序列化方法,如Boosting。
  • 个体学习器间不存在强依赖关系,可同时生成的并行化方法,如Bagging和随机森林(Random Forest)。

Boosting

Boosting是一族可以将弱学习器提升为强学习器的算法。它的工作原理是:从初始训练集训练出一个基学习器,再根据学习器的表现对训练样本分布进行调整,使得先前基学习器做错的训练样本在后续受到更多关注,然后基于调整后的样本分布来训练下一个基学习器;如此重复进行直至基学习器数目达到事先指定的值T,最终将这T个基学习器进行加权结合。

Boosting算法的代表是AdaBoost,其基于“加性模型”(additive model),即基学习器的线性组合H(x)=t=1Tαtht(x)H(x) = \sum^T_{t=1} \alpha_t h_t(x) 来最小化指数损失函数:

算法流程为

Boosting算法要求基学习器能对特定的数据分布进行学习,这可通过“重赋权法”(re-weighting)实施。对无法接受带权样本的基学习算法,则可通过“重采样法”(re-sampling)来处理。若采用“重采样法”,则可获得“重启动”机会以避免训练过程过早停止。可根据当前分布重新对训练样本进行采样,再基于新的采样结果重新训练处基学习器。 从偏差-方差分解的角度看,Boosting主要关注降低偏差,因此Boosting能基于泛化性能相当弱的学习器构建出很强的集成。

Bagging

欲得到泛化性能强的集成,集成中的个体学习器应尽可能相互独立;无法做到独立,也可设法使基学习器尽可能具有较大的差异。一种可能的做法是对训练样本进行采样,产生不同子集,每个子集训练一个基学习器,但如果采样的子集不足以进行有效学习,就无法确保产生比较好的基学习器,因此可以考虑使用相互有交叠的采样子集。

Bagging是并行式集成学习方法最著名的代表。它基于自助采样(bootstrap sampling)得到多个采样集,然后基于每个采样集训练一个基学习器,再将这些基学习器进行组合。对预测输出进行组合时,Bagging通常对分类任务使用简单投票法,回归使用平均法。若分类预测时出现两个类收到同样票数的情形,则随机选择一个,也可进一步考察学习器投票的置信度来确定最终胜者。

与标准AdaBoost只适用于二分类任务不同,Bagging能不经修改地用于多分类、回归等任务。值得一提的是,自助采样过程给Bagging带来的另一个优点:由于每个基学习器只使用了初始训练集中约63.2%的样本,剩下约36.8%的样本可用作验证集来对泛化性能进行“包外估计”(out-of-bag estimate)。事实上,包外样本有许多用途,如

  • 当基学习器是决策树时,可使用包外样本辅助剪枝,或估计决策树中各结点的后验概率以辅助对零训练样本结点的处理;
  • 当基学习器是神经网络时,可使用包外样本来辅助早期停止以减小过拟合风险。

从偏差-方差分解的角度看,Bagging主要关注降低方差。因此它在不剪枝决策树、神经网络等易受样本扰动的学习器上效用更为明显。

随机森林

随机森林(Random Forest,简称RF)是Bagging的一个扩展变体,其进一步在决策树的训练过程中引入了随机属性选择。传统决策树在选择划分属性时在当前结点的属性集合(假定有d个属性)中选择一个最优属性;而在RF中,对基决策树的每个结点,先从该结点的属性集合中随机选择一个包含k个属性的子集,然后再从这个子集中选择一个最优属性用于划分。一般来说,推荐值k=log2dk=log_2 d

随机森林简单,容易实现,只对Bagging做了很小改动。而且,随机森林中基学习器的多样性不仅来自样本扰动,还来自属性扰动,这就使得最终集成的泛化性能可通过个体学习器之间的差异度的增加而进一步提升。

结合策略

学习器结合可以带来很多好处,比如从统计上提升泛化性能、从计算上降低陷入局部极小点的风险、从表示上扩大假设空间以更好的近似。

常用的结合方法包括

  • 平均法
    • 简单平均法 H(x)=1Ti=1Thi(x)H(x) = \frac{1}{T} \sum_{i=1}^{T} h_i(x),用于个体学习器性能相近时
    • 加权平均法 H(x)=1Ti=1Twihi(x)H(x) = \frac{1}{T} \sum_{i=1}^{T} w_i h_i(x),其中 wi0w_i \ge 0,用于个体学习器性能相差较大时
  • 投票法
    • 绝对多数投票法:若某标记得票过半数,则预测为该标记;否则拒绝预测
    • 相对多数投票法:预测为得票最多的标记,若同时有多个标记获最高票,则从中随机选取一个
    • 加权投票法:类似于加权平均的投票法
  • 学习法:即通过另外一个学习器来结合,典型代表是Stacking。Stacking先从初始数据集训练出初级学习器,然后“生成”一个新数据集用于训练次级学习器。在这个新数据集中,初级学习器的输出被当做样例输入特征,而初始样本的标记仍被当做样例标记。为了避免过拟合问题,一般通过使用交叉验证或留一法的方式,用训练初级学习器未使用的样本来产生次级学习器的训练样本。次级学习器的输入属性表示和次级学习器算法对Stacking集成的泛化性能有很大影响,将初级学习器的输出类概率作为次级学习器的输入属性,用多响应线性回归(Multi-response Linear Regression,简称MLR)作为次级学习算法效果较好。在MLR中使用不同的属性集效果更佳。

多样性

欲构建泛化能力强的集成,个体学习器应“好而不同”。个体学习器准确性越高、多样性越大,则集成越好。如何度量个体分类器的多样性就是一个比较重要的问题。

常见的多样性度量方法有

  • 不合度量(disagreement measure)
  • 相关系数(correlation coefficient)
  • Q-统计度量(Q-statistic)
  • κ\kappa统计度量

也可以设法增强个体学习器的多样性,一般的思路是在学习过程中引入随机性,如对数据样本、输入属性、输出表示、算法参数等进行扰动。

© Pengfei Ni all right reserved,powered by GitbookUpdated at 2017-10-25 22:16:31

results matching ""

    No results matching ""