集成学习

第8章 集成学习

  • Page171: 多分类器系统(multi-classifier system)

    即集成学习。

  • Page171: 个体学习器(individual learner)

    集成学习的一般结构是:先产生一组“个体学习器”,再用某种策略将它们结合起来,个体学习器通常由一个现有的学习算法从训练数据产生。

  • Page171: 基学习器(base learner)

    集成中只包含同种类型的个体学习器,这样的集成是同质的。同质集成中的个体学习器亦称“基学习器”,相应的学习算法称为“基学习算法”。

  • Page171: 基学习算法(base learning algorithm)

    见基学习器。

  • Page171: 集成学习(311)(ensemble learning)

    集成学习通过构建并结合多个学习器来完成学习任务,有时也被称为多分类器系统(multi-classifier system),基于委员会的学习(committee-based learning)。

  • Page171: 弱学习器(weak learner)

    集成学习通过将多个学习器进行结合,常可获得比单一学习器显著优越的泛化性能,这对弱学习器尤为明显,基学习器有时也被直接称为弱学习器。

  • Page172: AdaBoost

    AdaBoost算法有多种推导方式,比较容易理解的是基于“加性模型”,即基学习器的线性组合

    H(x)=t=1Tαtht(x)H(x) = \sum_{t=1}^T \alpha_t h_t (x)

    来最小化指数损失函数(exponential loss function)

    lexp(HD)=Ex D[ef(x)H(x)]l_{exp}(H|D) = \mathbb{E}_{x~D}[e^{-f(x)H(x)}]

  • Page172: 多样性(diversity)

    学习器之间具有差异。

  • Page172: 投票法(225)(voting)

    少数服从多数。

  • Page173: Boosting(page139)

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

  • Page173: 加性模型

    见AdaBoost

  • Page177: 重采样(re-sampling)

    在每一轮学习中,根据样本分布对训练集重新进行采样,再用重采样而得的样本集对基学习器进行训练。

  • Page177: 重赋权(re-weighting)

    在训练过程的每一轮中,根据样本分布为每个训练样本重新赋予一个权重,对无法接受带权样本的基学习算法,则可通过重采样法处理,两种做法没有显著的优劣差别。

  • Page178: Bagging(Boostrap AGGregatING)

    Bagging是并行式集成学习方法最著名的代表,基于自助采样法,给定包含m个样本的数据集,先随机取出一个样本放入采样集中,再把该样本放回初始数据集,使得下次采样时该样本仍有可能被选中,这样经过m次随机采样操作,我们得到含m个样本的采样集,初始训练集中有的样本在采样集里多次出现,有的从未出现。采样出T个含m个训练样本的采样集,然后基于每个采样集训练出一个基学习器,再将这些基学习器进行结合,这就是Bagging的基本流程。

  • Page178: 自助采样法(Boostrap sampling)

    见Bagging。

  • Page179: 随机森林(Random Forest,RF)

    是Bagging的一个扩展变体,RF在以决策树为基学习器构建Bagging集成的基础上,进一步在决策树的训练过程中引入随机属性选择。具体来说,传统决策树在选择划分属性时是在当前结点的属性集合(假定有d个属性)中选择一个最优属性,,而在RF中,对基决策树的每个结点,先从该结点的属性集合中随机选择一个包含k个属性的子集,然后再从这个子集中选择一个最优属性用于划分,这里的参数k控制了随机性的引入程度:若令k=d,则基决策树的构建与传统决策树相同;若令k=1,则是随机选择一个属性用于划分;一般情况下,推荐k=log2dk=log_2d

  • Page182: 加权平均(225)(weighted averaging)

    假定集成包含T个基学习器h1,h2,...hT{h_1,h_2,...h_T},其中hih_i在示例xx上的输出为hi(x)h_i(x),加权平均结合hih_iH(x)=i=1Twihi(x)H(x)=\sum_{i=1}^Tw_ih_i(x)

    其中wiw_i是个体学习器hih_i的权重,通常要求wi0,i=1T=1w_i\geqq0, \sum_{i=1}^T=1

  • Page182: 简单平均(simple averaging)

    H(x)=1Ti=1Thi(x).H(x)=\frac{1}{T}\sum_{i=1}^Th_i(x).

    符号含义见加权平均。

  • Page182: 绝对多数投票(majority voting) 对分类任务来说,学习器hih_i将从类别标记集合c1,c2,...,cN{c_1,c_2,...,c_N}中预测出一个标记,最常见的结合策略是使用投票法,将hih_i在样本xx上的预测输出表示为一个N维向量(hi1(x);hi2(x);...;hiN(x))(h_i^1(x);h_i^2(x);...;h_i^N(x)),其中hij(x)h_i^j(x)hih_i在类别标记cjc_j上的输出。

    绝对多数投票法:

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

  • Page183: 加权投票(225)(weighted voting)

    H(x)=cargmaxji=1Twihij(x)H(x)=c_{argmax_j\sum_{i=1}^Tw_ih_i^j(x)}

    与加权平均法类似,wiwihih_i的权重,通常wi0,i=1Twi=1wi\geq0, \sum_{i=1}^Tw_i=1.

  • Page183: 相对多数投票(plurality votiing)

    H(x)=cargmaxji=1Thij(x)H(x) = c_{argmax_j\sum_{i=1}^Th_i^j(x)}

    即预测为得票最多的标记,若同时又多个标记获得最高表,则从中随机选取一个,绝对多数投票和相对多数投票统称为多数投票法。

  • Page184: Stacking

    一种集成学习方法,先从初始数据集训练出初级学习器,然后生成一个新数据集用于训练次级学习器,在新数据集中,初级学习器的输出被当作样例输入特征,而初始样本的标记仍被当做样例标记。

  • Page185: 贝叶斯模型平均(Bayes Model Averaging)

    基于后验概率来为不同模型赋予权重,可视为加权平均法的一种特殊实现,理论上,若数据生成模型恰在当前考虑的模型中,且数据噪声少,则BMA不差于Stacking;然而,在现实应用中无法确保数据生成模型一定在当前考虑的模型中,甚至可能难以用当前考虑的模型来进行近似,因此,Stacking通常优于BMA,更鲁棒,BMA对模型近似误差更敏感。

  • Page185: 分歧(304)(ambiguity)

    假定我们用个体学习器h1,h2,...,hTh_1,h_2,...,h_T通过加权平均法结合产生的集成来完成回归学习任务f:RdRf:\mathbb{R}^d\mapsto\mathbb{R},对示例xx,定义学习器hih_i的“分歧”为:

    A(hix)=(hi(x)H(x))2A(h_i|x)=(h_i(x)-H(x))^2

    则集成的“分歧”是 A(hx)=i=1TwiA(hix)=i=1Twi(hi(x)H(x))2\overline{A}(h|x) = \sum_{i=1}^Tw_iA(h_i|x) = \sum_{i=1}^Tw_i(h_i(x)-H(x))^2

    这里的分歧表征了个体学习器在样本x上的不一致性,在一定程度上反映了个体学习器的多样性。

  • Page185: 误差-分歧分解(error-ambiguity decomposition)

    E=EAE=\overline{E}-\overline{A}

    EE: 集成泛化误差,E\overline{E}: 个体学习器泛化误差的加权均值,A\overline{A}表示个体学习器的加权分歧值。这个分解明确提出:个体学习器准确性越高,多样性越大,集成越好。

  • Page187: 差异性度量

    同多样性度量。

  • Page187: 多样性度量(diversity measure)

    度量集成中个体分类器的多样性,估算个体学习器的多样化程度,典型做法是考虑个体分类器的两两相似/不相似性,常用度量有不合度量,相关系数,Q-统计量,K-统计量

  • Page189: 属性子集

    训练样本通常由一组属性描述,不同的子空间(即属性子集)提供了观察数据的不同视角。

  • Page189: 随机子空间(random subspace)

    依赖输入属性扰动产生随机的属性子集。

  • Page189: 稳定基学习器(stable base learner)

    对数据样本扰动不敏感的学习器,例如线性学习器、支持向量机、朴素贝叶斯,k近邻学习器。

  • Page189: 子空间(227)(subspace)

子空间一般指从初始的高维属性空间投影产生的低维属性空间,描述低维空间的属性是通过初始属性投影变换而得,未必是初始属性。

  • Page191: 集成修剪(ensemble pruning)

    集成产生之后再视图通过去除一些个体学习器来获得较小的集成,称为集成修剪,有助于减小模型的存储开销和预测时间开销,减小集成规模常导致泛化性能下降,并行化集成进行修剪能在减小规模的同时提升泛化性能,并催生了基于优化的集成修剪技术。

  • Page191: 选择性集成(selective emsemble)

    对并行化集成的修剪亦称“选择性集成”,但现在一般将选择性集成用作集成修剪的同义语,亦称集成选择(ensemble selection)。